akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 5e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

int main() {
    init();
    string S;
    cin >> S;
    ll sn = S.size();
    bool cor = (S[0] == S[sn - 1]);
    
    if((cor and sn&1) or (!cor and !(sn&1)))
        cout << "Second" << endl;
    else
        cout << "First" << endl;
}

Measured memory_bytes: 512
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > Mat;
typedef tuple<int, int, int, int> T;

const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int N, K;
  cin >> N >> K;
  ll g = 0, m = 0;
  rep(i, N) {
    ll A;
    cin >> A;
    if (g == 0)
      g = A;
    else
      g = gcd(g, A);
    m = max(m, A);
  }

  if (K % g == 0 && K <= m)
    cout << "POSSIBLE\n";
  else
    cout << "IMPOSSIBLE\n";

  return 0;
}

Measured memory_bytes: 256
def power(x, n, mod):
    ans = 1
    while n > 0:
        if n % 2 == 1:
            ans = ans * x % mod
        n //= 2
        x = x * x % mod
    return ans

def eular(n):
    ans = 1
    if n % 2 == 0:
        x = 1
        while n % 2 == 0:
            n //= 2
            x *= 2
        ans *= x - x // 2
    i = 3
    while i * i <= n:
        if n % i == 0:
            x = 1
            while n % i == 0:
                n //= i
                x *= i
            ans *= x - x // i
        i += 2
    if n != 1:
        ans *= n - 1
    return ans

k = int(input())

if k % 2 == 0 or k % 5 == 0:
    print(-1)
    quit()
elif k % 7 == 0:
    l = 9 * k // 7
else:
    l = 9 * k

phi_l = eular(l)
ans = phi_l
d, x = 10, 1
while x * x <= phi_l:
    if phi_l % x == 0:
        if d % l == 1:
            ans = x
            break
        else:
            y = phi_l // x
            if pow(10, y, l) == 1:
                ans = y
    d = d * 10 % l
    x += 1
print(ans)



Measured memory_bytes: 63444
total = []

N = int(input())

for i in range(1, N + 1):
    if i % 3 == 0 and i % 5 == 0:
        pass
    elif i % 3 == 0:
        pass
    elif i % 5 == 0:
        pass
    else:
        total.append(i)

print(sum(total))

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

int main() {
  int x, y, a, b, c, t, ka(0), kb(0), k(0);
  cin >> x >> y >> a >> b >> c;
  long long ans(0);
  priority_queue<pair<int, int>> pq;
  while (a + b + c) {
    cin >> t;
    pq.push({t, a && a-- ? 1 : b && b-- ? -1 : c-- ? 0 : 0});
  }
  while (x + y - k) {
    auto p = pq.top();
    pq.pop();
    if (p.second == 1 && x - ka || p.second == -1 && y - kb || !p.second) {
      ans += p.first;
      k++;
      if (p.second == 1) ka++;
      if (p.second == -1) kb++;
    }
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 6512
N,M = map(int,input().split())

dic = {i+1:[] for i in range(N)}
for i in range(M):
    p,y = map(int,input().split())
    dic[p].append((i,y))

for i in range(N):
    dic[i+1].sort(key=lambda x:x[1])

ans = [0] * M
for k,vs in dic.items():
    order = 1
    for city,year in vs:
        ans[city] = (k,order)
        order += 1

for city, order in ans:
    print('{:06d}{:06d}'.format(city,order))

Measured memory_bytes: 44512
N, A, B = map(int, input().split())

df = abs(A - B)
dA = A - 1
dB = N - B
ans = 0

if df % 2 == 0:
    ans = int(df // 2)
    print(ans)
else:
    if dA > dB:
        #端までの距離
        ans += dB + 1 + ((B-A) // 2)
        print(ans)
    else:
        ans += dA + 1 + ((B-A) // 2)
        print(ans)



Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e18)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))


int main(){
	ll N;
	string S;
	cin >> N >> S;

	ll ans = 1;
	ll cnt = 1;//まだ結ばれてない
	if(S[0]=='W'||S[2*N-1]=='W'){
		cout << 0 << endl;
		return 0;
	}
	FOR(i,1,2*N){
		if(cnt%2==0){//偶
			if(S[i]=='B'){//自分黒
				cnt++;
			}else{
				ans *= cnt;
				cnt--;
				ans %= MOD;
				if(cnt<0){
					cout << 0 << endl;
					return 0;
				}
			}
		}else{
			if(S[i]=='W'){
				cnt++;
			}else{
				ans *= cnt;
				cnt--;
				ans %= MOD;
				if(cnt<0){
					cout << 0 << endl;
					return 0;
				}
			}	
		}
	}
	FOR(i,1,N+1){
		(ans*=i)%=MOD;
	}
	if(cnt==0){
		cout << ans << endl;
	}else{
		cout << 0 << endl;
	}

}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	string s, t;
	cin >> s >> t;

	bool flag = true;
	if (t.length() > s.length())
		flag = false;

	vector<string> answer;

	if (flag) {
		//시작 가능한 위치 판별
		bool possible;
		vector<int> startIdx;

		for (int i = 0; i <= s.length() - t.length(); ++i) {
			possible = true;
			for (int j = 0; j < t.length(); ++j) {
				if (s[i + j] == '?') continue;
				if (s[i + j] != t[j]) {
					possible = false;
					break;
				}
			}
			if (possible) {
				startIdx.push_back(i);
			}
		}

		if (startIdx.size() == 0) {
			flag = false;
		}

		if (flag) {
			string temp;
			for (int i = 0; i < startIdx.size(); ++i) {
				temp = s;
				for (int j = 0; j < t.length(); ++j) {
					temp[startIdx[i] + j] = t[j];
				}
				for (int j = 0; j < s.length(); ++j) {
					if (temp[j] == '?')
						temp[j] = 'a';
				}
				answer.push_back(temp);
			}
		}

		sort(answer.begin(), answer.end());
	}

	if (flag) {
		cout << answer[0];
	}
	else {
		cout << "UNRESTORABLE";
	}
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int a[] = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        int flag = 0;
        for (int i = 0; i < n; i++) {
            if (max < (i * 10)) {
                flag = 1;
            }
            if (a[i] + (10 * i) > max) {
                max = a[i] + (10 * i);
            }

        }
        max = 0;
        for (int i = 0; i < n; i++) {
            if (max < (i * 10)) {
                flag = 1;
            }
            if (a[n - 1 - i] + (10 * i) > max) {
                max = a[n - 1 - i] + (10 * i);
            }

        }
        if (flag == 1) {
            System.out.println("no");
        } else {
            System.out.println("yes");
        }

    }
}



Measured memory_bytes: 104412
M = []
F = []
R = []
grade = []
m = 0; f = 0; r = 0
while 1:
    m, f, r = map(int, input().split())
    if m == -1 and f == -1 and r == -1:
        break
    M.append(m)
    F.append(f)
    R.append(r)


for i in range(len(M)):
    if M[i] == -1 or F[i] == -1 or M[i] + F[i] < 30:
        print('F')
    elif M[i] + F[i] >= 80:
        print('A')
    elif 65 <= M[i] + F[i] < 80:
        print('B')
    elif 50 <=  M[i] + F[i] < 65:
        print('C')
    elif 30 <= M[i] + F[i] < 50:
        if R[i] >= 50:
            print('C')
        else:
            print('D')





Measured memory_bytes: 5608
def merge(l,r,a):
    l1 = len(l)
    r1 = len(r)
    i,j,k = 0,0,0
    while j<l1 and k<r1:
        if l[j]<r[k]:
            a[i] = l[j]
            j+=1
        elif l[j] == r[k]:
            a[i]=l[j]
            j+=1
            global res
            print("NO")
            quit()
            return 0
        else:
            a[i] = r[k]
            k+=1
        i+=1
    while j<l1:
        a[i] = l[j]
        j+=1
        i+=1
    while k<r1:
        a[i] = r[k]
        k+=1
        i+=1
    return a

def mergeSort(a):
    n = len(a)
    if n == 1:
        return a
    else:
        mid = n//2
        left = []
        right = []
        for i in range(mid):
            left.append(a[i])
        for i in range(mid, n):
            right.append(a[i])
        mergeSort(left)
        mergeSort(right)
        merge(left,right,a)
        return a


n = int(input())
a = list(map(int,input().split()))
res = True
s = mergeSort(a)
if res:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 25544
#include<stdio.h>
int main(void){
int a,b,c,d,i;
scanf("%d%d%d%d",&a,&b,&c,&d);
for(i=2;i<104;i++){
c-=b;
if(c<=0){ puts("Yes");break;}
a-=d;
if(a<=0){ puts("No");break;}
}
return 0;
}


Measured memory_bytes: 1660
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i <(n) ; ++i)
using namespace std;
using ll = long long;
void self_max(int &a,int b){
  a = max(a,b);
}

int main(){
  string s; cin >>s;
  rep(i,3){
    if(s[i] == s[i+1]) {
      cout << "Bad" << endl;
      return 0;
    }
  }

  cout << "Good" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int a,b,c,d,e;
  
  	cin >> a;	
  	b = a / 1000;
  	c = ( a - b * 1000 ) / 100;
  	d = ( a - b * 1000 - c * 100 ) / 10;
   	e = a - b * 1000 - c * 100 - d * 10;
  
  	if ( ( b == c  && c == d ) || ( c == d && d == e ) ) {
    	cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
  string s ;
  cin >> s ;
  
  if(s=="Sunny"){
  cout << "Cloudy" << endl ;
  }else if(s=="Cloudy"){
      cout << "Rainy" << endl ;
  }else{
      cout << "Sunny" << endl ;
  }
  
  
    return 0 ;
}


Measured memory_bytes: 256
/**
  @date Time-stamp: <2019-05-19 21:05:29 tagashira>
  @file a.cpp
  @title A - Changing a Character
  @brief https://atcoder.jp/contests/abc126/tasks/abc126_a
**/

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
  int N, K;
  cin >> N >> K;
  string S;
  cin >> S;

  string newS;
  for (int i = 0; i < N; i++) {
    if (i == K - 1) {
      if (S[i] == 'A') {
        newS += 'a';
      } else if (S[i] == 'B') {
        newS += 'b';
      } else if (S[i] == 'C') {
        newS += 'c';
      }

    } else {
      newS += S[i];
    }
  }

  cout << newS << "\n";

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
// #include <fstream>

using namespace std;

typedef long long ll;


ll x[100001], v[100001];
ll v_sum_right[100001], v_sum_left[100001];
ll g[100001];
ll g2[100001];

int main() {
    ll N, C;
    ll i;
    ll ans;

    // ifstream cin("input.txt");
    cin >> N >> C;
    for (i = 0; i < N; i++) {
        cin >> x[i] >> v[i];
    }

    v_sum_right[0] = v[0];
    for (i = 1; i < N; i++) {
        v_sum_right[i] = v_sum_right[i - 1] + v[i];
    }

    v_sum_left[N] = 0;
    for (i = N - 1; i >= 0; i--) {
        v_sum_left[i] = v_sum_left[i + 1] + v[i];
    }


    // g計算
    g[0] = 0;
    g2[0] = 0;
    for (i = 1; i <= N; i++) {
        g[i] = max(g[i - 1], v_sum_right[i - 1] - x[i - 1]);
        g2[i] = max(g2[i - 1], v_sum_right[i - 1] - 2 * x[i - 1]);
    }
        
    // 探査
    ans = v_sum_left[0] - C + x[0];
    for (i = 1; i < N; i++) {
        ans = max(ans, v_sum_left[i] + g[i] - 2 * (C - x[i]));
        ans = max(ans, v_sum_left[i] - C + x[i] + g2[i]);
    }
    ans = max(ans, g[N]);

    
    // ofstream cout("output.txt");
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4992
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
L,R = map(int,input().split())
c = 0
for i in range(L,R+1):
    if i % 2019 == 0:
        print(0)
        c = 1
        break
if c == 0:
    MIN = 3000
    for i in range(L,R):
        for j in range(i+1,R+1):
            a = (i*j)%2019
            MIN = min(a,MIN)
    print(MIN)

Measured memory_bytes: 14644
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
int gcd(int a,int b){return b?gcd(b,a%b):a;}

using namespace std;
int main(void){
    // Your code here!
    int N;
    int H[100000];
    int de[100000];
    int de_idx[100000];
    int de_cnt = 0;
    cin >> N;
    rep(i, N) {
        cin >> H[i];
    }
    
    rep(i, N-1) {
        if(H[i] > H[i+1]) {
          for(int j=0; j<=i; j++) {
            if(H[j] > H[i+1] + 1) {
              cout << "No" << endl;
              return 0;
            }
          }
        }
    }
    
    cout << "Yes" << endl;
}


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

int main(){
    int N;
  	cin >> N;
    vector<int> D1(N,0);
    vector<int> D2(N,0);

    
    rep(i,N) {
        cin >> D1.at(i) >> D2.at(i); 
    }

    int count = 0;

    rep(i,N) {
        if(D1.at(i)==D2.at(i)) {
            count += 1;
        } else {
            count = 0;
        }

        if(count==3) {
            break;
        }
    }

    if(count==3) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,n) for (int i=(n-1);i >= 0;i--)
#define all(v) v.begin(),v.end()
#define sz(v) (int)((v).size())
#define MAX(v) *max_element(all(v))
#define MIN(v) *min_element(all(v))
using namespace std; using ll = long long; using P = pair<int,int>;
using vl = vector<ll>; using vvl = vector<vl>;
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
template<class T>bool chmax(T &a, const T &b) {if(a<b){a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if(b<a){a=b; return 1;} return 0;}
const ll INF = 1LL << 60;
const int dx[8] = {1,0,-1,0,1,1,-1,-1}; const int dy[8] = {0,1,0,-1,1,1,-1,-1};

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    ll n;
    string s;
    cin >> n >> s;
    vl dir(n);
    rep(i,n){
        // 左は0、右は1
        if(s[i]=='E') dir[i]=1;
        else dir[i]=0;
    }

    vl s0(n+1,0),s1(n+1,0);
    rep(i,n){
        s0[i+1] = s0[i] + 1-dir[i];
        s1[i+1] = s1[i] + dir[i];
    }

    ll ans = INF;
    chmin(ans,s1[n]-s1[1]);
    chmin(ans,s0[n-1]);
    rep(i,1,n-1){
        chmin(ans,s0[i]+s1[n]-s1[i+1]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 7700
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <cmath>         // sqrt
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <bits/stdc++.h> // isupper, islower, isdigit, toupper, tolower
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, n) for (int i = (a); i < (n); i++)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> Pl;
typedef pair<int, int> P;
typedef tuple<ll, ll, string> Tlls;

ll N, M, Q, ans;
vector<ll> a, b, c, d;
void dfs(vector<ll> A)
{
  if (A.size() == N + 1)
  {
    ll now = 0;
    rep(i, Q)
    {
      if (A.at(b.at(i)) - A.at(a.at(i)) == c.at(i))
      {
        now += d.at(i);
      }
      ans = max(ans, now);
    }
    return;
  }

  A.push_back(A.back());
  while (A.back() <= M)
  {
    dfs(A);
    A.back()++;
  }
}

int main()
{
  cin >> N >> M >> Q;
  a = b = c = d = vector<ll>(Q);
  rep(i, Q)
  {
    cin >> a.at(i) >> b.at(i) >> c.at(i) >> d.at(i);
  }
  dfs(vector<ll>(1, 1));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3612
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=200005;

LL n,k;
LL a[N],f[N];

bool Check(LL tim) {
	LL t=k;
	for(int i=1;i<=n;i++) {
		LL ti=a[i]*f[n-i+1];
		if(ti>tim) {
			t-=(ti-tim+f[n-i+1]-1)/f[n-i+1];
			if(t<0) return false;
		}
	}
	return true;
}
LL BS() {
	LL l=-1,mid,r=1e12;
	while(l+1<r) {
		mid=(l+r)>>1;
		if(Check(mid))
			r=mid;
		else l=mid;
	}
	return r;
}
int main() {
	scanf("%lld %lld",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int j=1;j<=n;j++)
		scanf("%lld",&f[j]);
	sort(a+1,a+n+1);
	sort(f+1,f+n+1);
	printf("%lld\n",BS());
	return 0;
}

Measured memory_bytes: 3328
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>
#include <numeric>
#include <functional>
#include <climits>



using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main(int argc, char *argv[]){
  size_t n;
  cin >> n;
  vector<int> v(n);
  for (size_t i = 0; i < n; i++) {
    cin >> v[i];
  }

  bool flag = true;
  int ret = 0;
  while(flag){
    flag = false;
    for (size_t i = n-1; i > 0; i--) {
      if(v[i] < v[i-1]){
        ret++;
        int x = v[i];
        v[i] = v[i-1];
        v[i-1] = x;
        flag = true;
      }
    }
  }

  for (size_t i = 0; i < n-1; i++) {
    cout << v[i] << " ";
  }
  cout << v[n-1] << endl;
  cout << ret << endl;


  
  return 0;
}

Measured memory_bytes: 1204
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_dec_float.hpp>

using namespace std;
using ll = long long;
#define MOD 1e9+7

vector< int > z_algorithm(const string &s) {
  vector< int > prefix(s.size());
  for(int i = 1, j = 0; i < s.size(); i++) {
    if(i + prefix[i - j] < j + prefix[j]) {
      prefix[i] = prefix[i - j];
    } else {
      int k = max(0, j + prefix[j] - i);
      while(i + k < s.size() && s[k] == s[i + k]) ++k;
      prefix[i] = k;
      j = i;
    }
  }
  prefix[0] = (int) s.size();
  return prefix;
}

int main(){
    int N;cin >> N;
    string s;cin >> s;
    ll ans = 0;
    for(int i = 0;i < N;i++){
        vector<int> uku = z_algorithm(s.substr(i, N));
        for(int j = 0;j < uku.size();j++){
            ans = max((int)ans, min(uku.at(j), j));
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 384
import java.util.*;
 
public class Main {
	public static void main (String[] args) {
		Scanner in = new Scanner(System.in);
		
		int ollm = in.nextInt();
		int hous = in.nextInt();
		int fast = in.nextInt();
		int memo = fast;
		int second =  0;
		int last = 0;
		int now =  0;
		long sum = 0;
		long maxm = 0;
		
		for(int i = 0;i < hous -1;i++){
		   second = in.nextInt();
		   now = second - fast;
		   if(maxm < now){
		       maxm = now;
		   }
		    sum = sum + now;
		    fast = second;
		}
		
		last = ollm-(second - memo);
		sum = sum + last;
		if(maxm< last){
		    maxm = last;
		}
		
		System.out.println(sum - maxm);
      
	}
}

Measured memory_bytes: 65588
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

int main(){
  int i;
  cin>>i;
  cout << (i==3 || i==5 || i==7 ? "YES" : "NO" ) << endl;
  return 0;
}


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

class Node{
    public:
        int id;
        int parent;
        int depth;
        string type;
        vector<int> child;
        Node():id(-1),parent(-1),depth(-1),type(""){};
};

vector<Node> root;

void dfs(int id,int d){
    if(root[id].depth<d)
        root[id].depth=d;
    for(int i=0;i<root[id].child.size();i++){
        dfs(root[id].child[i],d+1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); 

    int n, num,tmp;
    cin>>n;
    for(int i=0;i<n;i++){
        Node node;
        cin>>node.id>>num;
        for(int j=0;j<num;j++){
            cin>>tmp;
            node.child.push_back(tmp);
        }
        root.push_back(node);
    }

    sort(begin(root),end(root),
            [](const Node &r, const Node &l){
            return r.id < l.id;
    });

   for(int i=0; i<n; i++){
        for(int j=0; j<root[i].child.size(); j++){
            root[root[i].child[j]].parent=root[i].id;
            /*親をセット*/
        }
   }
   /*深さをセット*/
   for(int i=0;i<n;i++){
       dfs(i,0);
   }
   for(int i=0;i<n;i++){  
        if(root[i].parent==-1){
            root[i].type="root,";
        }else{
            if(root[i].child.size()!=0){
                root[i].type="internal node,";
            }else{
                root[i].type="leaf,";
            }
        }
    }

    for(int i=0; i<n; i++){
        cout<<"node "<<root[i].id<<": parent = "<<root[i].parent<<", depth = "<<root[i].depth<<", "<<root[i].type<<" [";
        for(int j=0;j<root[i].child.size();j++){
            cout<<root[i].child[j];
            if(j!=root[i].child.size()-1){
               cout<<", ";
            }
        }
        cout<<"]"<<endl;
    }

    return 0; 
}

Measured memory_bytes: 11352
#include "bits/stdc++.h"

using ll = long long;
#define int long long

using namespace std;

//0 -> a-1
#define rep(i, a) for (int i = 0; (i) < (int)(a); (i)++)
//a -> b-1
#define reps(i, a, b) for (int i = (int)(a); (i) < (int)(b); (i)++)
//a-1 -> 0
#define rrep(i, a) for (int i = (int)a - 1; (i) >= 0; (i)--)
//a-1 -> b
#define rreps(i, a, b) for (int i = (int)(a)-1; (i) >= (int)(b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
//next_permutation(all(v))
#define PERM(v) next_permutation(all(v))
/*sort(all(v));
(v).erase(unique(all(v)), v.end())*/
#define UNIQUE(v) \
	sort(all(v)); \
	(v).erase(unique(all(v)), v.end())
#define CIN(type, x) \
	type x;          \
	cin >> x
#define YES(f) if ((f)) {cout << "YES" << endl;} else {cout << "NO" << endl;}
#define Yes(f) if ((f)) {cout << "Yes" << endl;} else {cout << "No" << endl;}
#define MINV(v) min_element(all(v))
#define MAXV(v) max_element(all(v))
#define MIN3(a, b, c) min(min(a, b), c)
#define MIN4(a, b, c, d) min(MIN3(a, b, c), d)
#define MIN5(a, b, c, d, e) min(MIN4(a, b, c, d), e)
#define MIN6(a, b, c, d, e, f) min(MIN5(a, b, c, d, e), f)
#define MAX3(a, b, c) max(max(a, b), c)
#define MAX4(a, b, c, d) max(MAX3(a, b, c), d)
#define MAX5(a, b, c, d, e) max(MAX4(a, b, c, d), e)
#define MAX6(a, b, c, d, e, f) max(MAX5(a, b, c, d, e), f)
//b is [a, c)
#define RANGE(a, b, c) ((a) <= (b) && (b) < (c))
//c is [a, e) && d is [b, f)
#define RANGE2D(a, b, c, d, e, f) (RANGE((a), (c), (e)) && RANGE((b), (d), (f)))
#define chmin(a, b) a = min(a, (b))
#define chmin3(a, b, c) a = MIN3(a, (b), (c))
#define chmin4(a, b, c, d) a = MIN4(a, (b), (c), (d))
#define chmin5(a, b, c, d, e) a = MIN5(a, (b), (c), (d), (e))
#define chmin6(a, b, c, d, e, f) a = MIN6(a, (b), (c), (d), (e), (f))
#define chmax(a, b) a = max(a, (b))
#define chmax3(a, b, c) a = MAX3(a, (b), (c))
#define chmax4(a, b, c, d) a = MAX4(a, (b), (c), (d))
#define chmax5(a, b, c, d, e) a = MAX5(a, (b), (c), (d), (e))
#define chmax6(a, b, c, d, e, f) a = MAX6(a, (b), (c), (d), (e), (f))
#define fcout cout << fixed << setprecision(12)
#define RS resize
#define CINV(v, N)             \
	do                         \
	{                          \
		v.RS(N);               \
		rep(i, N) cin >> v[i]; \
	} while (0);

#define RCINV(v, N)             \
	do                          \
	{                           \
		v.RS(N);                \
		rrep(i, N) cin >> v[i]; \
	} while (0);
#define MOD 1000000007

template <class T>
inline T GET()
{
	T x;
	cin >> x;
	return x;
}

void init();
void solve();

signed main()
{
	init();
	solve();
}

void init()
{
	map<char, char> m;
	m['A'] = 'T';
	m['T'] = 'A';
	m['G'] = 'C';
	m['C'] = 'G';
	char c;
	cin >> c;
	cout << m[c] << endl;
}

void solve()
{
}

Measured memory_bytes: 256
function Main(arg) {
    var arg = arg.trim().split('\n');
    let n = Number(arg[0].split(' ')[0]);
    let k = Number(arg[0].split(' ')[1]);
    let p = arg[1].split(' ').sort(
      (a,b) => {
        if(Number(a)<Number(b))return -1;
        if(Number(a)>Number(b))return 1;
        return 0;
      }
    );
    let ans = 0;
    for(i = 0; i < k;i++){
      ans = ans + Number(p[i]);
    }
    console.log(ans);
    return;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 31588
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define LOOP(i,x,n) for(int i=(x);i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
const int MOD=1e9+7;
const int INF=1e10;

int f(int n,int s,int m){
  int tmp=0;
  if(n==0&&s==0)return 1;
  LOOP(i,m,10)if(s-i>=0)tmp+=f(n-1,s-i,i+1);
  return tmp;
}

signed main(){
  int n,s;
  while(cin>>n>>s,n){
    cout<<f(n,s,0)<<endl;
  }
  return 0;
}



Measured memory_bytes: 3072
H, W, A, B = map(int, input().split())

M = [[0 for w in range(W)] for h in range(H)]

for h in range(B):
    for w in range(A):
        M[h][w] = 1

for h in range(B, H):
    for w in range(A, W):
        M[h][w] = 1

for h in range(H):
    print(''.join(list(map(str, M[h]))))

Measured memory_bytes: 12916
#include<iostream>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>

unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

#define LOCAL  1
#define UPLOAD 2

using namespace std;
typedef long long ll;

template <class T = ll>
T input(){T x;cin >> x;return x;}

template <class T>
void output(T x){cout << x << endl;}

//#define int long log

#define debug(x) cerr << #x<< ": " << x<< '\n';

int main()
{
#if ENVIRONMENT == LOCAL
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif

  int N = input();
  int D = input();
  vector<vector<int>> X;
  for(int i=0;i<N;i++){
    vector<int> temp;
    for(int j=0;j<D;j++){
      temp.push_back(input());
    }
    X.push_back(temp);
  }

  int count = 0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      int sum = 0;
      for(int d=0;d<D;d++){
        sum += pow(X[i][d]-X[j][d],2);
      }
      float d = sqrt(sum);
      if(d == (float)((int)d))count++;
    }  
  }

  output(count);

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int n,count;
int main(){
	cin >>n;
	count =0;
	while(n>1){
		if(n%3==0){
			n/=3;
		}else{
			n=n/3+1;
		}
		count++;
	}
	cout<<count<<endl;
}

Measured memory_bytes: 3056
import java.util.*;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "YES";
    private static final String NO = "NO";

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] A = new int[N];
        for (int i=0; i<N; i++) {
            A[i] = sc.nextInt();
        }

        System.out.println(solve(N, K, A));
    }

    private static int solve(int N, int K, int[] A) {
        int sum = 0;
        for (int i=0; i<N; i++) {
            sum += A[i];
        }
        List<Integer> divideList = divideList(sum);
        Collections.sort(divideList, Collections.reverseOrder());

        for (int d : divideList) {
            if (solveD(N, K, A, d)) {
                return d;
            }

        }

        return 1;
    }

    private static boolean solveD(int N, int K, int[] A, int d) {
        int[] r = new int[N];
        int divSum = 0;
        for (int i=0; i<N; i++) {
            r[i] = A[i]%d;
            divSum += r[i];
        }
        Arrays.sort(r);
        // ここではrを昇順にしているので，
        // 上位 N-(rの和)/d 個が0に減らす, その他 (rの和)/d 個がdに増やす操作

        int split = N - divSum / d;
        // System.err.println("split=" + split);
        int ops = 0;
        for (int i=0; i<split; i++) {
            ops += r[i];
        }
        // System.err.println(ops);
        if (ops > K) return false;
        ops = 0;
        for (int i=split; i<N; i++) {
            ops += d - r[i];
        }
        // System.err.println(ops);
        if (ops > K) return false;

        return true;
    }

    private static List<Integer> divideList(int sum) {
        List<Integer> list = new ArrayList<>();

        for (int i=1; i<=Math.sqrt(sum); i++) {
            if (sum%i == 0) {
                list.add(i);
                list.add(sum/i);
            }
        }

        return list;
    }
}

Measured memory_bytes: 26052
N, L = map(int, input().split())
s = sum(L + i - 1 for i in range(1, N + 1))
ans = sum(L + i - 1 for i in range(2, N + 1))
for i in range(1, N + 1):
    s1 = s - (L + i - 1)
    if abs(s - ans) > abs(s - s1):
        ans = s1
print(ans)


Measured memory_bytes: 3060
n, m = map(int, input().split())
checker = [1 for _i in range(n+1)]
r = [0 for i in range(n+1)]
r[1] = 1
for _i in range(m):
    x, y = map(int, input().split())
    checker[x] -= 1
    checker[y] += 1
    if r[x]>0:
        r[y] = 1
    if (r[x]>0) and (checker[x]==0):
        r[x] = 0
print(sum(r))

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

using Int = int;
using namespace std;

#define ARC(i, a, b) for(Int i = (a); i < (b); ++i)
#define RC(i, n) ARC(i, 0, n)
#define ARCH(i, a, b) for(Int i = (a) - 1; i >= (b); --i)
#define RCH(i, n) ARCH(i, n, 0)
template<class T> T ant(const T &a, const T &b){ return a > b ? a : b; };
template<class T> T ont(const T &a, const T &b){ return a < b ? a : b; };
template<class T> T th(T &a, const T &b, T (*f)(const T &, const T &)){ return a = f(a, b); }
#define anth(a, b) th(a, b, ant)
#define onth(a, b) th(a, b, ont)

int main(){
	Int n, m;
	cin >> n >> m;
	vector<pair<Int, Int>> robot(m);
	RC(i, m) cin >> robot[i].first >> robot[i].second;
	sort(robot.begin(), robot.end());

	Int ans[n][2];

	RC(i, n){
		ans[i][0] = i;
		ans[i][1] = i + 1;
	}

	RC(i, m){
		onth(ans[robot[i].second][0], ans[robot[i].second - 1][0]);
		anth(ans[robot[i].second - 1][1], ans[robot[i].second][1]);

		/*
		RC(i, n){
			cout << ans[i][0] << ' ' << ans[i][1] << endl;
		}
		cout << endl;
		*/

	}
	RC(i, n){
		cout << ans[i][1] - ans[i][0] << " \n"[i == n - 1];
	}
}



Measured memory_bytes: 5160
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
f = True
mod = 10 ** 9 + 7

if N % 2:
  for i in range(N):
    if A[i] != (i+1) // 2 * 2:
      f = False
      
else:
  for i in range(N):
    if A[i] != i // 2 * 2 + 1:
      f = False

if f:
  print(2 ** (N//2) % mod)
else:
  print(0)

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

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;

#define rep(idx, N) for (u64 idx = 0; idx < N; idx++)


int main() {
    string s;
    cin >> s;

    rep(i,s.length()){
        cout << 'x';
    }

  return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <string>
#include <vector>
#include<algorithm>

using namespace std;

int main(void) {
	long long int n, a, b,ans=0;

	cin >> n >> a >> b;
	
	ans = a * (n / (a + b));
	

	if (n % (a + b) < a) {
		ans += n%(a+b);
	}
	else {
		ans += a;
	}

	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

int n;
vector<int> a;
vector<ll> S;
vector<vector<ll>> dp;

ll memo_rec(int Left = 0, int Right = n){
    if(dp[Left][Right] != -1)   return dp[Left][Right];
    if(Right - Left == 1)   return dp[Left][Right] = 0;

    ll res = 1e+15;
    ll Size = S[Right] - S[Left];
    for(int i = Left + 1; i < Right; ++i){
        ll sum = Size + memo_rec(Left, i) + memo_rec(i, Right);
        chmin(res, sum);
    }

    return dp[Left][Right] = res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    a.resize(n);
    S.resize(n + 1);
    dp.assign(n + 5, vector<ll>(n + 5, -1));
    S[0] = 0;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        S[i + 1] = S[i] + a[i];
    }
    cout << memo_rec() << endl;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

template<class T, class Cond>
struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  bool operator()(T& a, const T& b) const {
    if(cond(a, b)) { a = b; return true; }
    return false;
  }
};
template<class T, class Cond>
chain<T, Cond> make_chain(Cond cond) { return chain<T, Cond>(cond); }

int main() {
  double A, B, H, M;
  cin >> A >> B >> H >> M;
  auto pi = std::acos(-1);
  auto theta_A = (H / 12) * 2 * pi + (M / 60) * 2 * pi / 12;
  auto theta_B = (M / 60) * 2 * pi;
  auto Ax = A * std::cos(theta_A);
  auto Bx = B * std::cos(theta_B);
  auto Ay = A * std::sin(theta_A);
  auto By = B * std::sin(theta_B);
  auto dx = Ax - Bx;
  auto dy = Ay - By;
  std::cout << setprecision(10) << fixed << std::sqrt(dx * dx + dy * dy) << endl;
}


Measured memory_bytes: 4124
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
using vl = vector<ll>;
using vvl = vector<vl>;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    ll N, A, B;
    cin >> N >> A >> B;
    if(A > B) {
        cout << 0 << endl;
        return 0;
    }
    if(N == 1 and A != B) {
        cout << 0 << endl;
        return 0;
    }
    if(N == 1 and A == B) {
        cout << 1 << endl;
        return 0;
    }
    ll ma = A + B + (N - 2) * B;
    ll mi = A + B + (N - 2) * A;
    cout << ma - mi + 1 << endl;
    return 0;
}

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

#include <climits>
#include <cmath>
#include <cstring>

#include <iomanip>

using namespace std;

#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL); 
#define endl "\n"

typedef long long int  ll;
typedef unsigned long long int ull;


int main()
{
	FAST;
	int n;
	cin >> n;
	int temp[n];
	int arr[n];
	for(int i=0 ; i<n ; i++)
		cin >> arr[i];
	
	for(int i=1 ; i<=n ; i++)
		temp[i-1] = abs( (n-i) - (i-1));
		
	sort(arr , arr+n);
	sort(temp , temp+n);

	int ans = 1;
	for(int i=0 ; i<n ; i++)
	{
	    if(arr[i] != temp[i])
		{
			cout << "0";
			return 0;
		}
		if(i < n/2)
		{
			ans = (ans * 2)%1000000007;
		}
	}

	cout << ans;
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#define abs(x) ((x)<0 ? -(x) : (x))

int main(){
  int h, w;  scanf("%d %d", &h, &w);
  int field[22][22] = {0};
  for(int i=0; i<h; i++){
    char s[22];  scanf("%s", s);
    for(int j=0; j<w; j++)
      if(s[j] == '.')
	field[i+1][j+1] = 1;
  }

  int ans = 0;
  for(int sh=1; sh<=h; sh++)
    for(int sw=1; sw<=w; sw++){
      if(!field[sh][sw])  continue;
      for(int gh=1; gh<=h; gh++)
	for(int gw=1; gw<=w; gw++){
	  if(abs(sh-gh)+abs(sw-gw)<=1)  continue;
	  int table[22][22] = {0}, nowh, noww;
	  int queue[500][2], front = 0, rear = 0;
	  queue[rear][0] = sh, queue[rear][1] = sw, rear++;
	  while(front != rear){
	    nowh = queue[front][0], noww = queue[front][1], front++;
	    for(int s=-1; s<=1; s+=2){
	      if(field[nowh+s][noww] && !table[nowh+s][noww]){
		table[nowh+s][noww] = table[nowh][noww] + 1;
		queue[rear][0] = nowh+s, queue[rear][1] = noww, rear++;
	      }
	      if(field[nowh][noww+s] && !table[nowh][noww+s]){
		table[nowh][noww+s] = table[nowh][noww] + 1;
		queue[rear][0] = nowh, queue[rear][1] = noww+s, rear++;
	      }
	    }
	  }
	  ans = ans>table[gh][gw] ? ans : table[gh][gw];
	}
    }

  if(!ans)  ans = 1;
  printf("%d\n", ans);
  return 0;
}
    


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

int main() {
  int r,g,b; cin >> r >> g >> b;
  
  if ((r*100+g*10+b) %4 == 0) 
	      cout << "YES" << endl;
  else    cout << "NO" << endl;
  return 0;
}


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

int main() {
    int n, m;
    cin >> n >> m;

    dsu d(n);

    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        d.merge(a - 1, b - 1);
    }

    cout << d.groups().size() - 1 << endl;
}


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

#define ll long long
using namespace std;

map<int, int> mp;

int a[100000];

int sum[100000];


int main() {

    int n, k, Q;
    cin >> n >> k >> Q;
    for (int i = 1; i <= Q; i++) cin >> a[i],mp[a[i]]++;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        sum[i] = k;
    }
    for (int i = 1; i <= n; i++) {
        if(k-(Q-mp[i])>0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 6144
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	int n;
	cin >> n;
	map<int, int> da, db;
	for (int i = 0; i < n / 2; ++i) {
		int a, b;
		cin >> a >> b;
		++da[a];
		++db[b];
	}
	vector<pair<int, int> > va = { make_pair(0, -1) }, vb = { make_pair(0, -2) };
	for (pair<int, int> i : da) {
		va.push_back(make_pair(i.second, i.first));
	}
	for (pair<int, int> i : db) {
		vb.push_back(make_pair(i.second, i.first));
	}
	sort(va.begin(), va.end(), greater<pair<int, int> >());
	sort(vb.begin(), vb.end(), greater<pair<int, int> >());
	int ans = n;
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			if (va[i].second != vb[j].second) {
				ans = min(ans, n - va[i].first - vb[j].first);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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

// repetition
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

// container util
#define all(x) (x).begin(), (x).end()

// typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

// const value
// const ll MOD = 1e9 + 7;
// const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
// const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

// conversion
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
inline ll toLL(string s) {
  ll v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T> inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {
  return a > b && (a = b, true);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n, k, s;
  cin >> n >> k >> s;
  rep(i, n) {
    if(k > 0) {
      cout << s << " ";
      k--;
    } else {
      if(s == 1) {
        cout << 2 << " ";
      } else if(s == 2) {
        cout << 3 << " ";
      } else if(s % 2 == 0)
        cout << (s / 2) + 1 << " ";
      else
        cout << s / 2 << " ";
    }
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N,K,R,S,P;
string T;
int dp[100100][2][3];

int rsp(char te, int b) {
    switch (te) {
        case 'r':
            if (b != 2) return 0;
            else return P;
        case 's':
            if (b != 0) return 0;
            else return R;
        case 'p':
            if (b != 1) return 0;
            else return S;
    }
    return -10000;
}

void solve() {
    cin >> N >> K >> R >> S >> P >> T;
    memset(dp, 0, sizeof(dp));
    int ans[K];
    memset(ans, 0, sizeof(ans));
    for (int i = 0; i < N; ++i) {
        int gi = i % K;
        int gn = (i / K) % 2;
        int gn2 = (gn + 1) % 2;
        char te = T[i];
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (j == k) continue;
                int add = dp[gi][gn][j] + rsp(te, k);
                int x= max(dp[gi][gn2][k], add);
                dp[gi][gn2][k] = x;
            }
        }
        for (int j = 0; j < 3; ++j) {
            ans[gi] = max(ans[gi], dp[gi][gn2][j]);
        }
    }
    ll a = 0;
    for (int i = 0; i < K; ++i) {
        a += ans[i];
    }
    cout << a << endl;
}

int main() {
    solve();
    return 0;
}



Measured memory_bytes: 3200
# Aizu Problem ALDS_1_2_C: Selection Sort
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def printA(A):
    print(' '.join([str(a) for a in A]))

def selection_sort(A):
    swaps = 0
    for i in range(len(A)):
        mini = i
        for j in range(i, len(A)):
            if A[j] < A[mini]:
                mini = j
        if mini != i:
            swaps += 1
            A[i], A[mini] = A[mini], A[i]
    return A, swaps

        
N = int(input())
A = [int(_) for _ in input().split()]
A, swaps = selection_sort(A)
printA(A)
print(swaps)

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


int main() {
	
	int a, b;
	cin >> a >> b;
	if ( (a == 1) && (b == 1) ) cout << "Draw";
	else if (a == 1) cout << "Alice";
	else if (b == 1) cout << "Bob";
	else if (a == b) cout << "Draw";
	else if (a > b) cout << "Alice";
	else cout << "Bob";
	
	return 0;
}

Measured memory_bytes: 384
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <atcoder/all>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define endl '\n'
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

using namespace atcoder;

int main(){
    int n,q;
    cin >> n >> q;
    fenwick_tree<ll> fen(n);
    rep(i,n){
        ll x;
        cin >> x;
        fen.add(i,x);
    }
    rep(i,q){
        ll tp;
        cin >> tp;
        if(tp==0){
            ll p,x;
            cin >> p >> x;
            fen.add(p,x);
        }
        else{
            ll l,r;
            cin >> l >> r;
            cout << fen.sum(l,r) << endl;
        }
    }
    return 0;
}

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

#define ll long long
#define ld long double
#define ff first
#define ss second
#define eps 1e-9
#define pi acos(-1.0)
#define all(v) v.begin(),v.end()

#define MAX 500005

vector<ll> p;
bool vis[MAX];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll x;
    cin >> x;

    if(x<30) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 3640
def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    ar = a[0]
    for i1 in range(1, n):
        ar ^=  a[i1]
    res = []
    for i1 in range(n):
        rt = ar ^ a[i1]
        res.append(rt)
    print(*res)

if __name__ == '__main__':
    main()


Measured memory_bytes: 120944