akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef pair<int,int> P;

int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};

int main(){
	const int INF=9999999;
	int H,W,c=0;
	cin>>H>>W;
	//迷路を表す配列
	char meiro[50][50];
	//各マスまでの最短距離を表す配列
	int d[50][50];
	//迷路の入力と、各マスまでの最短距離をINFで初期化。また「#」の数を数えておく
	REP(i,H)
		REP(j,W){
		cin>>meiro[i][j];
		d[i][j]=INF;
		if(meiro[i][j]=='#')c++;
		}
	//スタートマスまでの最短距離は0
	d[0][0]=0;
	queue<P> que;
	//キューにスタートマスを入れる
	que.push(P(0,0));
	//キューが空になるまで繰り返す
	while(!que.empty()){
		//キューの先頭を取り出す
		P p=que.front();
		que.pop();
		//取り出したマスの座標
		int x=p.first,y=p.second;
		//取り出したのがゴールマスだったら打ち切る
		if(x==H&&y==W)break;
		//上下左右に移動
		REP(i,4){
			//移動先をnx,nyとする
			int nx=x+dx[i],ny=y+dy[i];
			//移動先が迷路の範囲内で移動可能か、さらにこれまでに訪れたことがないか判定
			if(0<=nx&&nx<H&&0<=ny&&ny<W&&d[nx][ny]==INF&&meiro[nx][ny]!='#'){
				//移動先のマスまでの最短距離をpまでの距離+1とする
				d[nx][ny]=d[x][y]+1;
				//移動先のマスをキューに入れる
				que.push(P(nx,ny));
			}
		}
	}
	int l=d[H-1][W-1];
	if(l==INF)cout<<"-1";
	else cout<<H*W-l-c-1;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) {
    
    new Main().run();
  }

  public void run() {
    
    try(BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {

      String[] lines = in.readLine().split(" ");
      int h = Integer.parseInt(lines[0]);
      int w = Integer.parseInt(lines[1]);

      char[][] table = new char[h][w];
      String line;
      for(int i=0; i<h; i++) {
        line = in.readLine();
        for(int j=0,k=0; j<w; j++, k+=2) {
          table[i][j] = (char)Character.getNumericValue(line.charAt(k));
        }
      }

      int n = 0;
      StringBuilder buf = new StringBuilder();
      for(int i=0; i<h-1; i++) {
        for(int j=0; j<w; j++) {
          if((table[i][j] & 1) == 1) {
            table[i][j]--;
            table[i+1][j]++;
            n++;
            buf.append(i+1).append(" ").append(j+1).append(" ")
               .append(i+2).append(" ").append(j+1).append("\n");
          }
        }
      }

      for(int j=0; j<w-1; j++) {
        if((table[h-1][j] & 1) == 1) {
          table[h-1][j]--;
          table[h-1][j+1]++;
          n++;
          buf.append(h).append(" ").append(j+1).append(" ")
             .append(h).append(" ").append(j+2).append("\n");
        }
      }
      StringBuilder ans = new StringBuilder();
      ans.append(n).append("\n").append(buf);

      System.out.print(ans);
    }
    catch(IOException e) {
      System.err.println(e);
    }
  }
}

Measured memory_bytes: 49144
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fast_IO ios::sync_with_stdio(0);cin.tie(0);
using namespace std;

int wa[105000];
bool ac[105000];


int main() {
    int n,m;
    cin>>n>>m;
    
    for(int i=0;i<n;i++){
        wa[i]=0;
        ac[i]=false;
    }

    int wan=0,acn=0;

    int p;string s;
    while(m--){
        cin>>p>>s;

        if(ac[p]==true)continue;
        if(s=="AC"){
            ac[p]=true;
            acn++;
            wan+=wa[p];
        }
        else if(s=="WA"){
            wa[p]++;
        }

    }

    cout<<acn<<" "<<wan<<endl;
    
    return 0;

}



Measured memory_bytes: 768
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P; 

int main()
{
	int a,b,c;
	cin >> a >> b >> c;
	int s[3] = {a,b,c};
	sort(s,s+3);
	cout << s[0] + s[1] + s[2] * 10 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
#include<chrono>
using namespace std;
using namespace std::chrono;
//using namespace __gnu_pbds;
#define fastio     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi         first
#define se         second
#define int         long long
#define pb         push_back
#define emp        emplace_back
#define vv(x)      vector<x>
#define mp(x,y)    map<x,y>
#define dq(x)      deque<x>
#define pql(x)     priority_queue<x>
#define pqs(x)     priority_queue<x,vv(x),greater<x> >
#define M          1000000007
#define forf(i,a,b) for(int i=a;i<b;i++)
#define it(x)      x::iterator
#define ll         long long
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d)  for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false); debug("%s time : %.4fs", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
#define vii        vector<int>
#define big        3e18
#define sm         -2e9
#define mkr        make_pair
#define vpi        vector<pair<int,int> >
#define pii        pair<int,int>
#define rng        500005
#define sz(x)      (int)x.size()
#define rv(x)      reverse(x.begin(),x.end())
#define out(x)     cout<<x.fi<<" "<<x.se<<endl;
 
//#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
 
void pr_init()
{
 
#ifndef ONLINE_JUDGE
  freopen("gin.txt", "r", stdin);
  freopen("gout.txt", "w", stdout);
 
#endif
}

//dp[i][j] -- > number of ways we can arrange first i integers with j being the last
int dp[3001][3001] , cum[3001];
void solve()
{
  int n;
  cin >> n;
  string s;
  cin >> s;

  dp[0][1] = 1 , cum[1] = 1;
  for(int j=2;j<=3000;j++) cum[j]=1;

  for(int i=1;i<n;i++)
  {
    for(int j=1;j<=i+1;j++)
    {
      if(s[i-1]=='<')dp[i][j] += (cum[j-1] - cum[0] + M)%M ;
      else dp[i][j] += (cum[3000] - cum[j-1] + M) % M;

      dp[i][j] %= M;
    }
    cum[1] = dp[i][1];
    for(int k=2;k<=3000;k++)
    {
      cum[k] = cum[k-1] + dp[i][k];
      cum[k] %= M; 
    }
  }
  
  int an = 0 ;
  for(int i=1;i<=n;i++) an += dp[n-1][i];

  cout<<an%M<<"\n";  

}
 
 
int32_t main()
{
  pr_init();
  //fastio;
 
  auto start = high_resolution_clock::now();
 
  solve();
  auto stop = high_resolution_clock::now();
  auto duration = duration_cast<microseconds>(stop - start);
  // cout << "Time taken by function: "
  //       << duration.count() << " microseconds" << endl;
 
}
 

Measured memory_bytes: 49756
import java.util.*;
import java.math.BigInteger;
// warm-up
public class Main {

	static Set<Integer> a = new HashSet<Integer>();
	static Set<Integer> b = new HashSet<Integer>();

	static void solve() {
		Scanner sc = new Scanner(System.in);
		BigInteger m = new BigInteger("1000000007");
		int n=sc.nextInt();
		while (n-->0) {
			int c = sc.nextInt();
			if (c==0) continue;
			if (a.contains(c)) b.add(c);
			else a.add(c);
		}
		if (a.size()==b.size()) System.out.println(new BigInteger("2").pow(a.size()).mod(m));
		else System.out.println(0);
		sc.close();				
	}

	public static void main(String args[]) {
		solve();
	}

}

Measured memory_bytes: 64772
import java.io.*;
import java.util.*;

public class Main {
	
	public static int[] swap (int[] sticks, int s, int g) {
		
		int work = 0;
		
		work = sticks[g];
		sticks[g] = sticks[s];
		sticks[s] = work;
		
		return sticks;
		
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = 
			new BufferedReader(new InputStreamReader(System.in));
		
		int[] sticks = new int[Integer.parseInt(br.readLine()) + 1];
		int n = Integer.parseInt(br.readLine());
		
		for (int i = 1; i < sticks.length; i++) {
			sticks[i] = i;
		}
		
		for (int i = 0; i < n; i++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine(),",");
			sticks = swap(sticks,Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
			
		}
		
		for (int s : sticks) {
			if (s == 0) continue;
			System.out.println(s);
		}
		
	}
	
}

Measured memory_bytes: 8908
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val list: List<Int> = readLine()!!.split(" ").map { it.toInt() }
    insertionSort(list.toIntArray(),n)
}

fun insertionSort(A:IntArray, N:Int) // N個の要素を含む0-オリジンの配列A
{
    var v:Int
    println(A.joinToString(" "))
    for (i in (1..(N - 1))) {
        v = A[i]
        var j:Int = i - 1
        while ((j >= 0) && (A[j] > v)) {
            A[j + 1] = A[j]
            j--
        }
        A[j + 1] = v
        println(A.joinToString(" "))
    }
}


Measured memory_bytes: 33920
/*
 * 16-11-12_AGC007_A.cpp
 *
 *  Created on: 2016/11/12
 *      Author: ryoma
 */
#include<iostream>

using namespace std;

int H,W;
char a[10][10];
int cnt;
int main(){
	cin >> H >> W;
	for(int i=0;i<H;i++)
		for(int j=0;j<W;j++){
			cin >> a[i][j];
			if(a[i][j]=='#')
				cnt++;
		}
	cout<<(cnt==H+W-1? "Possible":"Impossible")<<endl;
	return 0;
}





Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  int a,b;
  scanf("%d%d",&a,&b);
  int all = 1,count = 0;
  while(all<=b-1){
    all -= 1;
    all += a;
    count++;
  }
  printf("%d\n",count);
  return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <iostream>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <queue>
#include <math.h>
#include <queue>
#include <map>

using namespace std;

#define INF (1ll<<60)
#define INFint (1<<30)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;
// typedef pair<ll,ll> P;

#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)

template<class T>
bool umax(T &a, const T &b){
    if (a<b) {
        a=b; return true;
    }
    return false;
}

template<class T>
bool umin(T &a, const T &b) {
    if (b<a) {
        a=b; return true;
    }
    return false;
}

// gcd
template<typename T>
T gcd(T a, T b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}

int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);
    return result;
}

template<typename T>
T lcm( T m, T n ){
    // 引数に0がある場合は0を返す
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;
    return ((m/gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}


int dx[5]={1,0,-1,0};
int dy[5]={0,1,0,-1};

// v.front() = -BOUND;
// v.back() = BOUND;

//struct edge{
//    int cost, to;
//
//    edge(int in_cost, int in_to){
//        cost=in_cost;
//        to=in_to;
//    }
//    bool operator<(const edge &a) const
//    {
//        return cost > a.cost;
//    }
//};
vector<int>G[10010];
vector<int>c(10010,0);
int num[10010];
bool used[10010];
int now_c=0;
int dfs(int s){
    if(used[s]){
        return 0;
    }else{
        used[s]=true;
    }

    num[s]=c[now_c];
    now_c++;

    for(int i=0; i<G[s].size(); i++){
        dfs(G[s][i]);
    }
    return 0;
}


int main() {
    int N; cin >> N;
    vector<int>a(N);
    rep(i,N){
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    cout << a[N/2]-a[N/2-1]<< endl;

    return 0;
}

Measured memory_bytes: 896
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    dat = [LI() for _ in range(N)]
    dat.sort()
    yo = [y for _,y in dat]
    yo.sort()

    up = [0] * N
    dw = [0] * N

    bit = [0] * (N+1)

    def bit_add(i):
        while i <= N:
            bit[i] += 1
            i += i & -i

    def bit_sum(i):
        ret = 0
        while i > 0:
            ret += bit[i]
            i -= i & -i
        return ret

    for i in range(N):
        x,y = dat[i]
        y = bisect.bisect_left(yo,y) + 1
        up[i] = bit_sum(y)
        bit_add(y)

    bit = [0] * (N+1)
    for i in range(N-1,-1,-1):
        x,y = dat[i]
        y = bisect.bisect_left(yo,y) + 1
        dw[i] = bit_sum(y)
        bit_add(y)

    ans = N * pow(2,N-1,MOD)
    for i in range(N):
        a = i - up[i]
        b = up[i]
        c = N-(i+1) - dw[i]
        d = dw[i]
        p = (pow(2,a+d,MOD)-1) - (pow(2,a,MOD)-1) - (pow(2,d,MOD)-1)
        q = (pow(2,b+c,MOD)-1) - (pow(2,b,MOD)-1) - (pow(2,c,MOD)-1)
        x = p * (pow(2,b,MOD) + pow(2,c,MOD)-1)
        y = q * (pow(2,a,MOD) + pow(2,d,MOD)-1)
        z = p * q
        ans = (ans + x + y + z) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 124220
#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	int N;
	int a[110];
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> a[i];

	sort(a, a + N, greater<int>());

	int Alice = 0;
	int Bob = 0;

	for (int i = 0; i < N; ++i) {
		if (i % 2 == 0)
			Alice += a[i];
		else
			Bob += a[i];
	}
	cout << Alice - Bob << endl;
}

Measured memory_bytes: 256
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n)]
from collections import defaultdict
from math import gcd
d=defaultdict(int)
for a,b in ab:
  if a==0 and b==0:
    d[(0,0)]+=1
  elif a==0:
    d[(1,0)]+=1
  elif b==0:
    d[(0,1)]+=1
  else:
    if a<0:
      a*=-1
      b*=-1
    g=gcd(a,b)
    d[(a//g,b//g)]+=1
mod=pow(10,9)+7
ans=1
keys=d.keys()
for k in keys:
  if k==(0,0):
    continue
  else:
    a,b=k
    x=b if b>0 else -b
    y=-a if b>0 else a
    k0=tuple([x,y])
    if k0 in d:
      ans*=pow(2,d[k],mod)-1+pow(2,d[k0],mod)-1+1
      ans%=mod
      d[k]=0
      d[k0]=0
    else:
      ans*=pow(2,d[(a,b)],mod)
      ans%=mod
ans+=d[(0,0)]
ans-=1
print(ans%mod)


Measured memory_bytes: 83212
<?php
    function check($v, $sa, $c) {
        for ($i = 0; $i < $c; $i++) {
            if (strpos($v, $sa[$i]) !== false)
                return true;
        }
        return false;
    }

    list($n, $a) = explode(" ", rtrim(fgets(STDIN)));
    $da = Array();
    $da = explode(" ", rtrim(fgets(STDIN)));
    for($p = $n; true; $p++) {
       if (check($p, $da, $a) == false)
           break;
    }
    echo "$p\n";
 


Measured memory_bytes: 3704
#include <bits/stdc++.h> 
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(vec) vec.begin(), vec.end()
typedef long long ll;ll MM = 1000000000;ll mod = MM + 7; ll MMM=9223372036854775807;
ll GCD(ll x, ll y) {if (x % y == 0) return y;else return GCD(y, x % y);}
ll LCM(ll x, ll y) { return x * y / GCD(x, y);}

int main(){
 ll n,m=MMM; cin>>n;
rep(i,5){
ll t; cin>>t;
  m=min(m,t);
}
  cout<<4+(n+m-1)/m<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define F first
#define S second

#define ONLINE_JUDGE 1

using namespace std;

const int mod = 1e9+7;

void solve(){
	int n;
	cin >> n;
	vector<int> c(n+1);
	for(int i = 0; i + 1 < n; i++){
		int x; cin >> x;
		c[x]++;
	}	
	for(int i = 1; i <= n; i++){
		cout << c[i] << "\n";
	}
}

int main(){
	#ifndef ONLINE_JUDGE	
		freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);		
	int t = 1;
	//cin >> t;
	while(t--)
		solve();
	return 0;
}

Measured memory_bytes: 3976
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> p(n), q(n);
    rep(i,n){
        cin >> p[i];
        --p[i];
        q[p[i]] = i+1;
    }
    vector<ll> a(n), b(n);
    rep(i,n){
        a[i] = 20005 * (i + 1);
        b[i] = 20005 * (n - 1 - i) + q[i];
    }
    rep(i,n-1) cout << a[i] << " ";
    cout << a[n-1] << endl;
    rep(i,n-1) cout << b[i] << " ";
    cout << b[n-1] << endl;
    return 0;
}


Measured memory_bytes: 3964
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define endl '\n'

#define si(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) 
#define rep2(i, n, m) for (ll i = n; i <= (ll)(m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (ll)(m); --i)

template<class T, class U> bool chmax(T &a, U b) { if (a < b) a = b; return true; }
template<class T, class U> bool chmin(T &a, U b) { if (a > b) a = b; return true; }

using ll = long long;
using ld = long double;
using namespace std;

constexpr ll MOD = 1000000007;

signed main()
{
  cout << fixed << setprecision(20);
  ios::sync_with_stdio(false);
  cin.tie(0);

  int a, b; cin >> a >> b;

  string s, t;
  rep(i, b) s += to_string(a);
  rep(i, a) t += to_string(b);

  cout << min(s, t) << endl;

  return (0);
}


Measured memory_bytes: 3680
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

int main() {
  ll n,m;
  cin>>n>>m;
  vector<ll> a(n+1);
  rep(i,n) cin>>a[i+1];
  rep(i,n) a[i+1]=a[i]+a[i+1];
  rep(i,n+1) a[i]%=m;
  unordered_map<ll,ll> mp;
  rep(i,n+1) {
    if(mp.find(a[i])!=mp.end()) mp[a[i]]++;
    else mp[a[i]]=1;
  }
  ll ans=0;
  for(auto& p : mp) {
    ll x=p.second;
    ans+=x*(x-1)/2;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4492
def small_ink(paper,x,y):
  paper[x][y] += 1
  if 0 <= x-1 and x-1 < 10:
    paper[x-1][y] += 1
  if 0 <= y-1 and y-1 < 10:
    paper[x][y-1] += 1
  if 0 <= x+1 and x+1 < 10:
    paper[x+1][y] += 1
  if 0 <= y+1 and y+1 < 10:
    paper[x][y+1] += 1
  return paper

def middle_ink(paper,x,y):
  paper = small_ink(paper,x,y)
  if (0 <= x-1 and x-1 < 10) and (0 <= y-1 and y-1 < 10):
    paper[x-1][y-1] += 1
  if (0 <= x-1 and x-1 < 10) and (0 <= y+1 and y+1 < 10):
    paper[x-1][y+1] += 1
  if (0 <= x+1 and x+1 < 10) and (0 <= y-1 and y-1 < 10):
    paper[x+1][y-1] += 1
  if (0 <= x+1 and x+1 < 10) and (0 <= y+1 and y+1 < 10):
    paper[x+1][y+1] += 1
  return paper

def large_ink(paper,x,y):
  paper = middle_ink(paper,x,y)
  if (0 <= x-2 and x-2 < 10):
    paper[x-2][y] += 1
  if (0 <= y-2 and y-2 < 10):
    paper[x][y-2] += 1
  if (0 <= y+2 and y+2 < 10):
    paper[x][y+2] += 1
  if (0 <= x+2 and x+2 < 10):
    paper[x+2][y] += 1
  return paper

paper = [([0 for _ in range(10)]) for _ in range(10)]

while True:
  try:
    x,y,s = map(int, input().split(','))
  except EOFError:
    break
  if s == 1:
    paper = small_ink(paper,x,y)
  elif s == 2:
    paper = middle_ink(paper,x,y)
  elif s == 3:
    paper = large_ink(paper,x,y)

sum0 = 0
max_ink = 0
for i in range(10):
  for j in range(10):
    if paper[i][j] == 0:
      sum0 += 1
    if paper[i][j] > max_ink:
      max_ink = paper[i][j]
print(sum0)
print(max_ink)


Measured memory_bytes: 5620
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
      _n: usize,
      m: usize,
      abs: [[usize; 2]; m]
    }
    let mut abs = abs;
    abs.sort_by_key(|v| v[1]);
    let mut x = 0;
    let mut ans = 0;
    for i in 0..m {
        if x < abs[i][0] {
            x = abs[i][1] - 1;
            ans += 1;
        }
    }
    println!("{}", ans);
}



Measured memory_bytes: 10492
#include<iostream>
using namespace std;

int main(void){
    string S;
    cin >> S;

    if(S=="SUN"){
        cout << 7 << endl;
    }
    else if(S=="MON"){
        cout << 6 << endl;
    }
    else if(S=="TUE"){
        cout << 5 << endl;
    }
    else if(S=="WED"){
        cout << 4 << endl;
    }
    else if(S=="THU"){
        cout << 3 << endl;
    }
    else if(S=="FRI"){
        cout << 2 << endl;
    }
    else if(S=="SAT"){
        cout << 1 << endl;
    }
}


Measured memory_bytes: 256
#![allow(dead_code, unused_imports, non_snake_case)]

use std::io::*;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::str::FromStr;

const MOD: i32 = 1_000_000_007;

fn main() {
    let (_, mut k): (usize, usize) = input();
    let t: Vec<i64> = input();
    let mut plus = Vec::new();
    let mut minus = Vec::new();
    for &x in &t {
        if x == 0 {
            k -= 1;
        } else if x < 0 {
            minus.push(x.abs() as usize);
        } else {
            plus.push(x.abs() as usize);
        }
    }
    plus.sort();
    minus.sort();
//    println!("{:?}", plus);
//    println!("{:?}", minus);

    if k == 0 {
        println!("0");
        return;
    }

    let mut ans: usize = 1 << 29;

    // 片方だけ
    if plus.len() >= k {
        ans = min(ans, plus[k-1]);
    }
    if minus.len() >= k {
        ans = min(ans, minus[k-1]);
    }

    // ターンする
    for i in 1..k {
        if i <= minus.len() && k-i <= plus.len() {
            ans = min(ans, minus[i-1]*2 + plus[k-i-1]);
        }
        if i <= plus.len() && k-i <= minus.len() {
            ans = min(ans, plus[i-1]*2 + minus[k-i-1]);
        }
    }
    println!("{}", ans);
}

trait Read {
    fn read(s: &str) -> Self;
}

fn input<T: Read>() -> T {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    T::read(buf.trim_right())
}

macro_rules! read_impl {
    ($($t:ty)*) => ($(
        impl Read for $t {
            fn read(s: &str) -> $t{
                s.parse().unwrap()
            }
        }
    )*)
}
read_impl! { usize u8 u16 u32 u64 isize i8 i16 i32 i64 f32 f64 }

impl Read for String {
    fn read(s: &str) -> Self {
        s.to_string()
    }
}

impl Read for Vec<char> {
    fn read(s: &str) -> Self {
        s.chars().collect()
    }
}

impl<T: Read> Read for Vec<T> {
    fn read(s: &str) -> Self {
        s.split_whitespace().map(T::read).collect()
    }
}

impl<A: Read, B: Read> Read for (A, B) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]))
    }
}

impl<A: Read, B: Read, C: Read> Read for (A, B, C) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]), C::read(tokens[2]))
    }
}

impl<A: Read, B: Read, C: Read, D: Read> Read for (A, B, C, D) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]), C::read(tokens[2]), D::read(tokens[3]))
    }
}

Measured memory_bytes: 8444
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int a[2020];
int t[2020],tt[2020],nt;
int aa[2020],an;
bool ch[2020],in[2020];
bool cmp(int x,int y)
{
	return a[x]<a[y];
}
int main()
{
	int n,k,q;
	int ans=2147483647;
	scanf("%d%d%d",&n,&k,&q);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	memset(in,0,sizeof(in));
	for(int i=1;i<=n;i++)
		t[i]=i;
	sort(t+1,t+1+n,cmp);
	an=0;
	for(int i=n;i>=1;i--)
	{
		ch[t[i]]=true;
		nt=0;
		an=0;
		for(int j=1;j<=n+1;j++)
		{
			if(ch[j])
				tt[++nt]=j;
			else
			{
				sort(tt+1,tt+1+nt,cmp);
				for(int kk=1;kk<=nt-k+1;kk++)
					aa[++an]=a[tt[kk]];
				nt=0;
			}
		}
		sort(aa+1,aa+an+1);
		if(an>=q)
			ans=min(ans,aa[q]-aa[1]);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = ReadInt();
            var K = ReadInt();
            var xs = ReadIntArray();
            int ret = 0;
            for (int i = 0; i < xs.Length; i++)
            {
                ret += Math.Min(xs[i] * 2, ((K - xs[i]) * 2));
            }

            Console.WriteLine(ret);
        }
        private static readonly Func<string> Read = () => Console.ReadLine();
        private static readonly Func<string[]> ReadStringArray = () => Console.ReadLine().Split();
        private static readonly Func<int> ReadInt = () => int.Parse(Console.ReadLine());
        private static readonly Func<long> ReadLong = () => long.Parse(Console.ReadLine());
        private static readonly Func<int[]> ReadIntArray = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
        private static readonly Func<long[]> ReadLongArray = () => Console.ReadLine().Split().Select(long.Parse).ToArray();
        private static readonly Action<string> Cw = str => Console.WriteLine(str);
    }
}

Measured memory_bytes: 13396
#include <iostream>
#include <limits.h>
#include <cmath>

using namespace std;

double averageTempeture(int T, int x)
{
    return T - x * 0.006;
}

int main()
{
    int N, T, A;
    cin >> N >> T >> A;

    double temp[N + 1];

    for (int i = 1; i <= N; i++)
    {
        int h_i;
        cin >> h_i;
        temp[i] = averageTempeture(T, h_i);
    }

    double ans = 0;
    double min = INT_MAX;

    for (int i = 1; i <= N; i++)
    {
        if (abs(temp[i] - A) < min)
        {
            min = abs(temp[i] - A);
            ans = i;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main(){
    int n, tmp;
    cin >> n;
    vector<int> b(n + 1,0);
    for(int i=2;i < n+1;i++){
        cin >> tmp;
        ++b[tmp];
    }
    for(int i=1;i < n+1;i++) cout << b[i] << endl;

    return 0;

}


Measured memory_bytes: 4052
#include <iostream>
#include <cstdlib>
#include <complex>

using namespace std;

int main(int argc, const char * argv[]) {
    
    string a,b,x;
    int num;
    double root,kiriage;
    
    cin >> a >> b;
    x=a+b;
    num=atoi(x.c_str());
    
    root=sqrt(num);
    kiriage=ceil(root);
    
    if(root==kiriage) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    
    
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,n) for(int i=1;i<=(int)(n);i++)
#define rep3(i,n) for(int i=0;i<=(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
#define repll(i,n) for(ll i=0;i<(ll)(n);i++)
#define repll2(i,n) for(ll i=1;i<=(ll)(n);i++)
#define REPLL(i,m,n) for(ll i=m;i<(ll)(n);i++)
#define INF (int)1e9  //
#define LINF (ll)4e18  //
#define MOD (1e9)+7
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define PI 3.1415926535898

//------------------------------------------------------

int main() {
    int h, w, d;
    cin >> h >> w >> d;
    map<int, pii> mp;

    rep(i, h) {

        rep(j, w) {
            int a;
            cin >> a;
            a--;
            mp[a] = MP(i, j);
        }
    }

    int q;
    cin >> q;

    map<pii, int> s;

    rep(i, d) {
        int num = i;
        int c = 0;

        s[{i, 0}] = 0;
        while (1) {
            if (num + d >= h * w) break;

            s[{i, c + 1}] = s[{i, c}] + abs(mp[num + d].first - mp[num].first) + abs(mp[num + d].second - mp[num].second);
            c++;
            num += d;
        }


    }

    rep(k, q) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        cout << s[{r % d, r / d}] - s[{l % d, l / d}] << endl;

    }



    return 0;
}



Measured memory_bytes: 12416
R,G,B,N=map(int,input().split())

#R*r+G*g+B*b==n
ir=int(N/R)+1
ig=int(N/G)+1
ib=int(N/B)+1
s=0
for r in range(ir):
    for g in range(ig):
        if(R*r+G*g>N):
            break;
        if((N-R*r-G*g)%B==0):
            s+=1
print(s)


Measured memory_bytes: 40560
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int H = Integer.parseInt(sc.next());
		int W = Integer.parseInt(sc.next());
		int K = Integer.parseInt(sc.next());
		char s[][] = new char[H][W];
		int table[][] = new int[H][W];
		boolean[] row = new boolean[H];
		String line;
		for(int i=0;i<H;i++) {
			line = sc.next();
            s[i]= line.toCharArray();
            row[i]=line.contains("#");
        }
        sc.close();
        int now=1;
        for(int i=0;i<H;i++){
            boolean first=true;
            if(row[i]){
                for(int j=0;j<W;j++){
                    if(s[i][j]=='#'){
                        if(!first) now++;
                        else first=false;
                    }
                    table[i][j]=now;
                }
                now++;
            }
        }

		int ins1=-1,ins2=-1;
		for(int i=0;i<H;i++) {
			if(!row[i]) {
                    for(int k=i;k<H;k++) {
                        if(row[k]) {
                            ins1 = k;
                            break;
                        }
                    }
                    for(int k=i;k>=0;k--) {
                        if (row[k]) {
                            ins2 = k;
                            break;
                        }
                    }
                    table[i] = table[Math.max(ins1, ins2)];
				}
        }
        
		for(int i=0;i<H;i++) {
			for(int j=0;j<W;j++) {
				System.out.print(table[i][j] + " ");
			}
			System.out.println("");
		}
	}

}


Measured memory_bytes: 44856
#include<bits/stdc++.h>
#define ll long long
const ll mod=1e9+7;
const int maxn=1000000;
using namespace std;
 /*#ifndef ONLINE_JUDGE
      freopen("input.txt","r",stdin);
    #endif*/
int main()

{ 
#ifndef ONLINE_JUDGE
      freopen("input.txt","r",stdin);
    #endif
   ll x,k,d;
   cin>>x>>k>>d;
   x=abs(x);
   ll a=x/d;
   if(a>=k)
   {
   	  cout<<x-k*d;
   }
   else
   {
   	  if(x%d!=0)a++;
   	  ll b=k-a;
   	  if(b%2==1)
   	  {
   	  	cout<<abs(x-a*d+d);
		 }
		 else
		 {
		 	cout<<abs(x-a*d);
		 }
   	  //cout<<a<<" "<<b<<endl;
   	  
   }
}

Measured memory_bytes: 3684
#include<bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define mkp make_pair
#define rint register int
#define INF ((1ll << 60) - 1)
#define FI(n) FastIO::read(n)
#define FO(n) FastIO::write(n)
#define Pair pair < int, int >
#define mst(a,b) memset(a,b,sizeof(a))
#define foR(i, k, j) for(rint i = (k); i >= (j); i--)
#define For(i, k, j) for(rint i = (k); i <= (j); i++)
#define Foe(i, u) for(rint i = lst[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout)
#define int long long
const int P = 1000000007; //
using namespace std;
inline void ckmax(int &a, int b) {a = max(a, b);}
inline void ckmin(int &a, int b) {a = min(a, b);}
inline void mulmod(int &a, int b) {a = 1ll * a * b % P;}
inline void addmod(int &a, int b) {int t = a + b; a = (t >= P ? t - P : t); }
inline int ksm(int a, int b) {int ans=1; for(;b;b>>=1) {if(b&1) ans=1ll*ans*a%P;a=1ll*a*a%P;}return ans;}
inline int inv(int a) {return ksm(a, P-2);}
 
inline void printarray(int *a, int n) {For(i, 1, n) fprintf(stderr, "%d ", a[i]); fprintf(stderr, "\n");}
namespace FastIO {
    const int SIZE=1<<16; char buf[SIZE], obuf[SIZE], str[64]; int bi=SIZE, bn=SIZE, opt;
    int read(char *s) {
        while (bn) {for (;bi<bn&&buf[bi]<=' ';bi++);if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}
        int sn=0;while (bn) {for (;bi<bn&&buf[bi]>' ';bi++) s[sn++]=buf[bi];if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}s[sn]=0;return sn;
    }
    bool read(int& x) {if(x)x=0;int bf=0,n=read(str); if(!n) return 0; int i=0; if (str[i]=='-') bf=1,i=1; for(x=0;i<n;i++) x=x*10+str[i]-'0'; if(bf) x=-x; return 1;}
    void write(int x) {
        if(!x) obuf[opt++] = '0'; else {if(x<0) obuf[opt++]='-',x=-x;int sn=0; while(x)str[sn++]=x%10+'0',x/=10;for (int i=sn-1;i>=0;i--) obuf[opt++]=str[i];}
        if (opt>=(SIZE>>1)){fwrite(obuf, 1, opt, stdout); opt=0;}
    }
    void write(char x) {obuf[opt++]=x;if (opt>=(SIZE>>1)){fwrite(obuf, 1, opt, stdout); opt=0;}}
    void Fflush() { if (opt) fwrite(obuf, 1, opt, stdout); opt=0;}
};
int n, m, f[1000005];
inline int find(int x) {
	while(x != f[x]) x = f[x] = f[f[x]];
	return x;
}
signed main()
{
    #ifndef ONLINE_JUDGE
        file("pro");
    #endif
    cin >> n >> m;
    For(i, 1, n) f[i] = i;
    For(i, 1, m) {
    	int u, v; scanf("%lld %lld", &u, &v);
    	u = find(u), v = find(v);
    	if(u != v) f[v] = u;
	}
	int res = -1;
	For(i, 1, n) {
		res += (f[i] == i);
	}
	cout << res << endl;
    return FastIO::Fflush(), 0;
}

Measured memory_bytes: 4436
#include<bits/stdc++.h>
using namespace std;
int main(){
	int i,n,m;
	cin>>n>>m;
	vector<bool> vis(n+1,false);
	bool ans=false;
	for (i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		if(a==1){
			if(vis[b]){
				ans=true;
			}
			vis[b]=true;
		}else if(b==n){
			if(vis[a]){
				ans=true;
			}
			vis[a]=true;
		}
	}
	if(!ans) cout<<"IM";
	cout<<"POSSIBLE";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
using namespace std;
ll gcd(ll a,ll b){
    if(a<b){
        ll temp=a;
        a=b;
        b=temp;
    }
    ll r=a%b;
    while(r>0){
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}
int main(){
    ll n;
    cin>>n;
    vector<ll> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }    

    for(int i=0;i<n-1;i++){
        ll g=gcd(a[i],a[i+1]);
        a[i+1]=g;
    }
    cout<<a.back()<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 9999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(25) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 9999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(25) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 1000000007
#define MAX 10000000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
map<lli,lli>mp;
map<string,lli>ms;
set<string>ss;
set<lli>si;
set<char>sc;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli A,B,C,D,E,F,N,M,K,L,X,Y,Z,H,W,sum=0,num=0,flag=0;string S,T;
  cin >> N >> M >> X;
  Vec(Q,lli,N,0);
  DV(P,lli,N,M,0);
  rep(i,0,N){
    cin >> Q[i];
    rep(j,0,M)cin >> P[i][j];
  }
  sum=INF;
  for(lli i=0;i < (1<<N);i++){
    num=0;
    Vec(G,lli,N,0);
    rep(j,0,N){
      if(i&(1<<j)){
        num+=Q[j];
        rep(k,0,M)G[k]+=P[j][k];
      }
    }
    flag=1;
    rep(j,0,M)if(G[j]<X)flag=0;
    if(flag)chmin(sum,num);
  }
  if(sum==INF)Out("-1");
  else Out(sum);
}


Measured memory_bytes: 3664
#include<stdio.h>
int main()
{
	char c;
	int i=0,j=0,k=0,l=0;
	while(~scanf(" %c", &c))
	{
		if(c=='E')
			i=1;
		else if(c=='W')
			j=1;
		else if(c=='N')
			k=1;
		else if(c=='S')
			l=1;
	}
	if(i==j && k==l) printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int x;
    cin >> x;
    int MAX = 100003;
    vector<int> is_prime(MAX+1, 1);
    is_prime[0] = 0; is_prime[1] = 0;
    for (int i=2; i<is_prime.size(); i++) {
        for (int j=i*2; j<=MAX; j+=i) {
            is_prime[j] = 0;
        }
    }
    for (int i=x; i<=MAX; i++) {
        if (is_prime[i] == 1) {
            cout << i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 640
def solve(N, H):
    cnt = 0
    for i in range(N):
        if i == 0:
            cnt += 1
            continue
        max_height = max(H[:i])
        if max_height <= H[i]:
            cnt += 1
    return cnt


N = int(input())
H = list(map(int, input().split()))

print(solve(N, H))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

struct edge {
    int from, to; ll cost;
    edge(int s, int t, ll w = 0) : from(s), to(t), cost(w) {}
};

int main() {
    init();
    
    int n, m; ll l; cin >> n >> m >> l;

    vector<VL> dis(n, VL(n, LLINF));
    FOR(i, 0, n)dis[i][i] = 0;
    FOR(i, 0, m) {
        int a, b; ll c;
        cin >> a >> b >> c;
        a--, b--;
        if (c > l)continue;
        dis[a][b] = c;
        dis[b][a] = c;
    }

    FOR(k, 0, n)FOR(i, 0, n)FOR(j, 0, n) {
        chmin(dis[i][j], dis[i][k] + dis[k][j]);
    }

    vector<VL> dis2(n, VL(n, LLINF));
    FOR(i, 0, n)dis2[i][i] = 0;
    FOR(i, 0, n)FOR(j, i + 1, n) {
        if (dis[i][j] <= l) {
            dis2[i][j] = 1;
            dis2[j][i] = 1;
        }
    }

    FOR(k, 0, n)FOR(i, 0, n)FOR(j, 0, n) {
        chmin(dis2[i][j], dis2[i][k] + dis2[k][j]);
    }

    int q; cin >> q;
    FOR(i, 0, q) {
        int s, t; cin >> s >> t;
        s--, t--;
        cout << (dis2[s][t] == LLINF ? -1 : dis2[s][t] - 1) << "\n";
    }

}


Measured memory_bytes: 1920
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for(int (i)=(a);i<(b);i++)
#define INF 100000000
#define MAX_N 50010
using namespace std;
int N,L[MAX_N];

int main(){
    string s;
    cin>>s;
    rep(i,1,s.size()){
        //cout<<s<<endl;
        if(s[i-1]=='S'&&s[i]=='T'){
            s.erase(i-1,2);
            i-=2;
        }
    }
    cout<<s.size()<<endl;
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;

int main(void){
    long long int n;
    cin >> n;
    vector<long long> a(n);
    map<long long,long long> num;
    for(long long int i = 0;i < n;i++)cin >> a[i];
    vector<long long> s(n+1,0);
    for(long long int i = 0;i < n;i++)s[i+1] = s[i] + a[i];
    for(long long int i = 0;i < n+1;i++)num[s[i]]++;
    long long int sum = 0;
    for(auto it:num){
        long long b = it.second;
        sum += b * (b-1) / 2;
    }
    cout << sum;
} 

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    string s,t;
    cin >> s >> t;
    set<char> sset;
    for(i = 0;i < s.size();++i){
        sset.insert(s.at(i));
    }
    for(i = 0;i < t.size();++i){
        if(!sset.count(t.at(i))){
            cout << -1 << endl;
            return 0;
        }
    }
    map<char,vector<ll>> mp;
    for(i = 0;i < s.size();++i){
        mp[s.at(i)].push_back(i);
    }
    ll ans = 0;
    ll now = 0;
    i = 0;
    while(i < t.size()){
        auto x = lower_bound(all(mp[t.at(i)]), now);
        if(x == mp[t.at(i)].end()){
            ans /= s.size();
            ans = (ans+1)*s.size();
            now = 0;
            continue;
        }else{
            now = *x+1;
            ++i;
        }
    }
    ans += now;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1728
#include <iostream>

using namespace std;

int main(){
    int m = 100000;
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        m += m*0.05;
        if(m%1000){
            m = m-(m%1000)+1000;
        }
    }
    cout << m << endl;
}

Measured memory_bytes: 1160
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")*/

using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define ld long double
#define mp make_pair
#define what_is(x) cerr << #x << " is " << x << endl;

typedef tree<
        int,
        null_type,
        less<int>,
        rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set;


const int p = 998244353;


int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int add(int a, int b) {
    int s = (a+b);
    s = s%p;
    if (s<0) s+=p;
    return s;
}

int sub(int a, int b) {
    int s = (a-b);
    s = s%p;
    if (s<0) s+=p;
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}

vector<int> Z(vector<int> s)
{
    int n = s.size();
    vector<int> z(n);
    int L = 0, R = 0;
    for (int i = 1; i < n; i++) {
        if (i > R) {
            L = R = i;
            while (R < n && s[R-L] == s[R]) R++;
            z[i] = R-L; R--;
        } else {
            int k = i-L;
            if (z[k] < R-i+1) z[i] = z[k];
            else {
                L = i;
                while (R < n && s[R-L] == s[R]) R++;
                z[i] = R-L; R--;
            }
        }
    }
    return z;
}

mt19937 rnd(time(0));
/*
struct Line {
    mutable ll k, m, p;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};

struct CHT : multiset<Line, less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    const ll inf = LLONG_MAX;
    ll div(ll a, ll b) { // floored division
        return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = inf; return false; }
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }
};
*/


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int m, d;
    cin>>m>>d;
    int cnt = 0;
    for (int i = 10; i<=d; i++)
    {
        if (i/10<2 || (i%10)<2) continue;
        int res = (i/10)*(i%10);
        if (1<=res && res<=m) cnt++;
    }
    cout<<cnt;

}


Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
#define IN freopen("input.txt","r",stdin);
#define MAX5 100005
#define MAX6 1000005
#define MAX7 1000005
#define sf scanf
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
typedef long long int ll;
int TEST=1,CASE=1;
struct vpair{
    int a;
    int b;
    vpair(int a,int b){this->a=a;this->b=b;}
};
bool cmp(vpair &a,vpair &b){
    if(a.b<b.a)return true;
    else if(a.a==b.a){
        if(a.b<b.a)return true;
        else return false;
    }else return false;
}
int a,b,w;
int main(void){
    cin>>w>>a>>b;
    if(b<=a+w && b>=a){
        cout<<0<<endl;
        return 0;
    }
    if(b>a+w){
        cout<<b-(a+w)<<endl;
        return 0;
    }
    if(b+w>=a && b+w<=a+w){
        cout<<0<<endl;
        return 0;
    }
    if(b+w<a){
        cout<<a-(b+w)<<endl;
        return 0;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#include<cstdio>
#define r(i,n) for(int i=0;i<n;i++)


int main(void){
    string s;
    cin>>s;
    int num=s.size();
    cout<<s.at(0)<<num-2<<s.at(s.size()-1)<<endl;




return 0;

}


Measured memory_bytes: 256
import bisect

def solve():
    n=int(raw_input())
    m=int(raw_input())
    dist=[0]+[int(raw_input()) for _ in xrange(n-1)]+[d]
    dist.sort();

    ans=0
    for i in xrange(m):
        q=int(raw_input())
        l=bisect.bisect_left(dist,q)-1
        r=bisect.bisect_left(dist,q)
        ans+=min(abs(q-dist[l]),abs(dist[r]-q))

    return ans

while 1:
    d=int(raw_input())
    if d==0:break
    ans=solve()
    print ans

Measured memory_bytes: 10304
#include<bits/stdc++.h>
using namespace std;
const int N = 2009, Mod = 1e9 + 7;
int n, m, A[N], B[N], dp[N][N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &A[i]), dp[i][0] = 1;
    for (int i = 1; i <= m; i ++)
        scanf("%d", &B[i]), dp[0][i] = 1;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % Mod;
            dp[i][j] = (dp[i][j] + Mod - dp[i - 1][j - 1]) % Mod;
            if (A[i] == B[j])
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % Mod;
        }
    return !printf("%d\n", dp[n][m]);
}

Measured memory_bytes: 16000