akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main() {
  long long N;
  cin >> N;
  long long count = 0;
  for (int i = 0; i < N; i++){
    long long a;
    cin >> a;
    if (a % 2 == 1) count++;
  }
  
  if (count % 2 == 0) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define all(v) (v).begin(), (v).end()
using vi = vector<int>;
using vvi = vector<vi>;


int main(){
  int n,x;
  int ans;
  while(true){
    ans = 0;
    cin>>n>>x;
    if(n==0 && x==0)break;
    for(int i=1; i<=n; i++){
      for(int j=i+1; j<=n; j++){
        if(i+j==x)break;
        for(int k=j+1; k<=n; k++){
          if(i+j+k==x)ans++;
        }
      }
    }
    cout<<ans<<endl;
  }
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define INF9 1000000000 //10^9
#define MOD 1000000007 //10^9+7
#define fi first
#define sc second
using ll=long long;
using pii=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
using vb=vector<bool>;
ll n,ans;
vll a,b;

int fizzbuzz(int x){
    // if(x%3==0 && x%5==0) return "FiizzBuzz";
    // if(x%3==0) return "Fizz";
    // if(x%5==0) return "Buzz";
    if(x%3==0 && x%5==0) return 0;
    if(x%3==0) return 0;
    if(x%5==0) return 0;
    return x;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);

    cin >> n;
    ans = 0;
    rng(i,1,n+1){
        ans+=fizzbuzz(i);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3652
/**-------------------------
|--------From A.R.A--------|
-------------------------**/

#include <bits/stdc++.h>

#define ll            long long int
#define pb            push_back
#define ull           unsigned long long int
#define endl          "\n"
#define sz(c)         (c).size()
#define sall(c)       sort((c).begin(),(c).end())
#define rsall(c)      sort((c).rbegin(),(c).rend())
#define rev(c)        reverse((c).begin(),(c).end())
#define FOR(i,n)      for(ll i=0;i<n;i++)
#define max3(a,b,c)   max(max(a,b),c)
#define min3(a,b,c)   min(min(a,b),c)
#define input(a,i,n)  for(ll i=1;i<=n;i++){      cin>>a[i];}
#define output(a,i,n) for(ll i=1;i<=n;i++){cout<<a[i]<<" ";}

using namespace std;
int main()
{
    string s;
    cin>>s;
    if(s[0]=='?' && sz(s)==1){s[0]='D';}
    if(s[0]=='?' && s[1]=='D'){s[0]='P';}
    else if(s[0]=='?' && s[1]=='P'){s[0]='D';}
    else if(s[0]=='?' && s[1]=='?'){s[0]='P';s[1]='D';}
    for(int i=0;i<sz(s)-1;i++){
        if(s[i]=='P' && s[i+1]=='?'){s[i+1]='D';}
        if(s[i]=='D' && s[i+1]=='?'){
            if(i+1==sz(s)-1 || s[i+2]=='P'){s[i+1]='D';}
            else{s[i+1]='P';}
        }
    }
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 3720
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string.h>
#include<string>
#include<set>
#include<limits.h>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<list>
#include<functional>
#include<stack>
#include<deque>
#include<queue>
using namespace std;

signed main() {
	int a, b, c, d; cin >> a >> b >> c >> d;
	if (a + b > c + d)puts("Left");
	else if (a + b < c + d)puts("Right");
	else puts("Balanced");
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;

int main() {
    int n;
    cin >> n;
    ll a[n];
    for(int i=0; i<n; i++) cin >> a[i];

    ll sum_first=0, sum_second=0, cnt_first=0, cnt_second=0;

    //a[odd]<0 && a[even]>0
    for(int i=0; i<n; i+=2) {
        if(sum_first+a[i]<=0) {
            cnt_first += abs(1-sum_first-a[i]);
            sum_first = 1;
        } else {
            sum_first+=a[i];
        }

        if(sum_second+a[i]>=0) {
            cnt_second += abs(-1-sum_second-a[i]);
            sum_second = -1;
        } else {
            sum_second+=a[i];
        }


        if(i!=n-1) {
            if(sum_first+a[i+1]>=0) {
                cnt_first += abs(-1-sum_first-a[i+1]);
                sum_first = -1;
            } else {
                sum_first += a[i+1];
            }

            if(sum_second+a[i+1]<=0) {
                cnt_second += abs(1-sum_second-a[i+1]);
                sum_second = 1;
            } else {
                sum_second+=a[i+1];
            }
        }
    }

    cout << ((cnt_first<cnt_second)?cnt_first:cnt_second) << endl;
    return 0;
}


Measured memory_bytes: 1024
import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

class Main{

    static class Edge{
        int[] v=new int[2];
        int[] cnt=new int[2];
        long w;
        Edge(int u1,int u2){v[0]=u1;v[1]=u2;}
    }

    static List<Edge> edges[];
    static boolean[] used;
    static int dfs(int v){
        used[v]=true;
        int res =1;
        for(Edge e : edges[v]){
            int i = e.v[0]==v ? 1:0;
            if(used[e.v[i]])continue;
            e.cnt[i]=dfs(e.v[i]);
            res += e.cnt[i];
        }
        return res;
    }

    static long dfs2(int v){
        used[v]=true;
        long res =0;
        for(Edge e: edges[v]){
            int i = e.v[0]==v ? 1:0;
            if(used[e.v[i]])continue;
            res += dfs2(e.v[i]);
            res += e.w*(long)e.cnt[i];
        }
        return res;
    }
    

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        edges = new ArrayList[N];
        used = new boolean[N];
        List<Edge> edgeList = new ArrayList<>();
        for(int i=0;i<N;++i)edges[i]=new ArrayList<>();
        for(int i=0;i<N-1;++i){
            int a = scan.nextInt()-1;
            int b = scan.nextInt()-1;
            Edge e = new Edge(a, b);
            edgeList.add(e);
            edges[a].add(e);
            edges[b].add(e);
        }
        long[] s = new long[N];
        for(int i=0;i<N;++i)s[i]=scan.nextLong();
        dfs(0);
        for(Edge e: edgeList){
            if(e.cnt[0]==0)e.cnt[0]=N-e.cnt[1];
            else e.cnt[1]=N-e.cnt[0];
        }
        Edge equal=null;
        for(Edge e:edgeList){
            if(e.cnt[0]==e.cnt[1]){
                equal=e;
                e.w=0;
            }
            else e.w = ((s[e.v[0]] - s[e.v[1]])/((long)(e.cnt[1]-e.cnt[0])));
        }
        if(equal != null){
            Arrays.fill(used, false);
//            System.out.println(dfs2(equal.v[0]));
            equal.w = (s[equal.v[0]] - dfs2(equal.v[0])) / (equal.cnt[0]);
        }
        for(Edge e:edgeList)System.out.println(e.w);
    }
}

Measured memory_bytes: 130140
#include <iostream>

using namespace std;

int main()
{
    int n,k;
    
    cin>>n;
    
    cin>>k;
    
    int a[n];
    for(int i=0; i<n; i++){
        cin>>a[i];
    }

    // Sort
    int temp = 0, x=0;
    for(int j=1; j<n; j++){
        x=j-1;
        temp=a[j];
        while(temp < a[x] && x >= 0){
            a[x+1] = a[x];
            --x;
        }
        a[x+1] = temp;
    }
    int sum = 0;
    for(int y=0; y<k; y++){
        sum += a[y];
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
#define ll long long
using namespace std;

/*ll power(ll x,ll y)
{
    ll res = 1;
    while(y>0){
        if(y&1)
            res *= x;
        y>>=1;
        x*=x;
    }
    return res;
}*/

//int a[1010][1010];

int main()
{
    unsigned ll n;
    cin>>n;
    unsigned ll  ans = (n*(n-1))/2;
    cout<<ans<<'\n';
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
S = input()
K = int(input())
s_len = len(S)
s_set = set()
for i in range(1, s_len+1):
    j = 0
    if i > K:
        break
    else:
        while j+i <= s_len:
            s_set.add(S[j:j+i])
            j += 1
    
s_sort = sorted(list(s_set))
print(s_sort[K-1])

Measured memory_bytes: 4592
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
	int N;
	string S;
	cin >> N >> S;
	map<pair<string, string>, ll> pre;
	for (int i = 0; i < (1 << N); i++) {
		string s1, s2;
		for (int j = 0; j < N; j++) {
			if (i & (1 << j)) {
				s1.push_back(S[j]);
			}
			else {
				s2.push_back(S[j]);
			}
		}
		reverse(s2.begin(), s2.end());
		int cnt = __builtin_popcount(i);
		int len = min(s1.size(), s2.size());
		pre[make_pair(s1, s2)] += 1;
	}
	ll res = 0;
	for (int i = 0; i < (1 << N); i++) {
		string s1, s2;
		for (int j = 0; j < N; j++) {
			if (i & (1 << j)) {
				s1.push_back(S[N + j]);
			}
			else {
				s2.push_back(S[N + j]);
			}
		}
		reverse(s1.begin(), s1.end());
		int cnt = __builtin_popcount(i);
		res += pre[make_pair(s1, s2)];
	}
	cout << res << endl;
	return 0;
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n, q;
  cin >> n >> q;
  vector<vi32> g(n);
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  vi32 s(n);
  rep(i, q) {
    int p, x;
    cin >> p >> x;
    p--;
    s[p] += x;
  }
  vi32 ans(n, 1e9);
  using T = tuple<int, int>;
  queue<T> que;
  que.emplace(0, s[0]);
  while (sz(que)) {
    int u, sum;
    tie(u, sum) = que.front();
    que.pop();
    if (ans[u] != 1e9) continue;
    ans[u] = sum;
    for (auto v : g[u]) {
      que.emplace(v, sum + s[v]);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 17268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxM = 1e5+7;
const int maxV = 90010;

const int MOD = 1e9+7;

int T;
const int maxN = 1e2+8;
const ll INF = 1000000000000000010LL;
const int K = 15;

int main() {
	int r;
	cin>>r;
	int ans = 3 * r * r;
	cout<<ans<<endl; 
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(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()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>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)swap(a,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);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	double T,X;
	cin >> T >> X;
	cout << fixed;
	cout << setprecision(8) << T/X << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<climits>
#include<vector>
#include<utility>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) std::cout<<arg<<"\n"
#define prin2(arg1,arg2) std::cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) memset(arg,n,sizeof(arg))
using std::cin;
typedef long long ll;
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
const int INF=1e+9;
const ll INFLL=1e+17;
int N;
std::string s[10010];
void solve(){
  int cnt=0,cnta=0,cntb=0,cntba=0;
  rep(i,N){
    int ss=s[i].size();
    rep(j,ss-1){
      if(s[i][j]=='A'&&s[i][j+1]=='B') cnt++;
    }
    if(s[i][0]=='B'){
      if(s[i][ss-1]=='A') cntba++;
      else cntb++;
    }
    else if(s[i][ss-1]=='A') cnta++;
  }
  //  prin(cnt);
  //  prin(cnta);
  //  prin(cntb);
  //  prin(cntba);  
  if(cntba!=0){
    cnt+=cntba-1;
    if(cntb!=0){
      cnt++;
      cntb--;
    }
    if(cnta!=0){
      cnt++;
      cnta--;
    }
  }
  cnt+=std::min(cnta,cntb);
  prin(cnt);
}
int main(){
  cin>>N;
  rep(i,N) cin>>s[i];
  solve();
  return 0;
}


Measured memory_bytes: 768
//52行目から編集
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > vvi;
typedef vector<vector<ll> > vvl;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;

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

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(20);
    ll x,y,a,b,c;cin >> x >> y >> a >>b >> c;
    vl p(a);rep(i,a)cin >> p[i];
    vl q(b);rep(i,b)cin >> q[i];
    vl r(c);rep(i,c)cin >> r[i];
    sort(all(p));reverse(all(p));
    sort(all(q));reverse(all(q));
    sort(all(r));reverse(all(r));
    
    vector<pair<ll,ll>> g;
    rep(i,a){
        g.pb(mp(p[i],1));
    }
    rep(i,b){
        g.pb(mp(q[i],2));
    }
    rep(i,c){
        g.pb(mp(r[i],0));
    }
    
    ll pend = 0;
    ll ans = 0;
    sort(all(g));reverse(all(g));
    rep(i,g.size()){
        if(g[i].second == 0){
            pend++;
            ans += g[i].first;
        }else{
            if(g[i].second == 1){
                if(x == 0)continue;
                x--;
                ans += g[i].first;
            }else{
                if(y == 0)continue;
                y--;
                ans += g[i].first;
            }
        }
        if(x+y == pend){
            break;
        }
    }
    cout << ans << '\n';
    return 0;
}
/*
 *!!CHECK!! 
 * intの掛け算をしてる場合：overflowは大丈夫？
 * 制約の下限・上限は大丈夫？
 * 木構造は一直線にした時TLEしない？
 * */


Measured memory_bytes: 13036
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int x, min, p;
    int count = 0;
    scanf("%d", &x);

    for (int i = 1; i <= x; i++)
    {
        scanf("%d", &p);
        if (i == 1)
            min = p;
        if (p <= min)
            count++;
        if (min > p)
        {
            min = p;
        }
    }
    printf("%d", count);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long
#define ulli unsigned long long int
#define ld long double  
using namespace std; 

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);

    for (int& x: v) {
        cin >> x;
    }

    int mid = k / 2;

    int sum = 0;
    for (int i = 0; i < (int)v.size(); i++) {
        if (v[i] <= mid) {
            sum += v[i] * 2;
        } else {
            sum += (k - v[i]) * 2;
        }
    }

    cout << sum << "\n";
}

int main() 
{ 
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
  
    int t = 1; 
    //cin >> t; 
    while (t--) { 
        solve(); 
    } 
  
    cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl; 
    return 0; 
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <numeric>
#define ll long long
#define int ll

#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define irep(itr, st) for(auto itr = (st).begin(); itr != (st).end(); ++itr)
#define irrep(itr, st) for(auto itr = (st).rbegin(); itr != (st).rend(); ++itr)

#define pb emplace_back
#define mp make_pair

using namespace std;

const ll MOD = 998244353;
const ll INF = (ll)1000000007 * 1000000007;

#ifdef DEBUG
#define PRINT(A) std::cout << (#A) << ":" << (A) << std::endl;
#else
#define PRINT(A)
#endif

typedef pair<ll, ll> P;

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;
}

ll R, C, N, K;

bool v[15][10005];

ll a[20];

signed main() {

    cin >> N >> K;


    rep(i,N){
        cin >> a[i];
    }

    int minCost = INF;
    rep(i, 1ll << N){
        ll newA[15];
        rep(j,N) newA[j] = a[j];
        int count = 0;
        rep(j, N){
            if(i >> j & 1){
                count ++;
            }
        }
        if(count == K){
            rep(j,N){
                if(i >> j & 1){
                    rep(k,j){
                        chmax(newA[j], newA[k]+1);
                    }
                }
            }
            
            int cost = 0;
            rep(j,N){
                PRINT(newA[j])
                cost += (newA[j] - a[j]);
            }
            PRINT(cost)
            chmin(minCost, cost);
        }
    }

    cout << minCost << endl;
}


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

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

int main(){
  int n;
  cin >> n;
  long sum=0;
  for(int i = 1; i <= n; i++){
  for(int j = 1; j <= n; j++){
  for(int k = 1; k <= n; k++){
    sum+=gcd(gcd(i,j),k);
  }
  }
  }
 cout << sum << endl;
 return 0; 
}

Measured memory_bytes: 3644
s=input()
t=input()
n1,n2=len(s),len(t)
dp=[[0]*(n1+1) for i in range(n2+1)]
st=''
for i in range(1,n2+1):
    for j in range(1,n1+1):
        if s[j-1]==t[i-1]:
            dp[i][j]=dp[i-1][j-1]+1
            #st+=s[j-1]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
while i>0 and j>0:
    if t[i-1]==s[j-1]:
        st=s[j-1]+st
        i-=1
        j-=1
    elif dp[i][j-1]>dp[i-1][j]:
        j-=1
    else:
        i-=1
print(st)

Measured memory_bytes: 112220
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <functional>
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<(x)<<endl
#define fi first
#define se second

#define INF 2147483600

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

  int cnt=0;
  rep(i,s.size()-1) if(s[i]!=s[i+1]) cnt++;

  cout<<cnt<<endl;

  return 0;
}


Measured memory_bytes: 512
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define INIT    \
    cin.tie(0); \
    ios::sync_with_stdio(false);

template <class T>
inline bool chmax(T& a, T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline bool chmin(T& a, T b) {
    return a = (a > b) ? b : a;
}

ll const INF = 1LL << 60;
ll const MOD = 1000000007;

int main() {
    INIT;

    ll N;
    cin >> N;
    vector<ll> a(N);
    rep(i, N) cin >> a[i];

    vector<ll> sum(N, 0);
    vector<ll> diff(N, 0);

    sum[0] = a[0];
    rep(i, N) { sum[i + 1] = sum[i] + a[i + 1]; }

    diff[N - 1] = a[N - 1];
    for (ll i = N - 1; i >= 1; i--) {
        diff[i - 1] = diff[i] + a[i - 1];
    }

    // repv(sum) { cout << *it << "\t"; }
    // cout << endl;

    // repv(diff) { cout << *it << "\t"; }
    // cout << endl;

    ll ans = INF;

    rep(i, N - 1) { chmin(ans, abs(sum[i] - diff[i + 1])); }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 7948
#include<iostream>
#include<string>
#include<cmath>
#include<utility>
using namespace std;
typedef pair<int, int>P;

int main() {
	int n;
	while (cin >> n, n) {
		P p[120];
		string s;

		cin >> s;

		for (int i = 0;i < n;i++) {
			int a, b;
			cin >> a >> b;
			p[i] = make_pair(a, b);
		}

		for (int i = n - 1;i > -1;i--) {
			swap(s[p[i].first - 1], s[p[i].second - 1]);
			int dif = abs(p[i].first - p[i].second)%26;
			int a = p[i].first;
			int b = p[i].second;

			s[a - 1] -= 26;
			s[a - 1] += dif;
			if (s[a - 1] < 'a')s[a - 1] += 26;
			s[b - 1] -= 26;
			s[b - 1] += dif;
			if (s[b - 1] < 'a')s[b - 1] += 26;
		}
		cout << s << endl;
	}
	return 0;
}

Measured memory_bytes: 3184
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <string>
#include <map>
#include <list>
using namespace std;

int main() {
  int a,b,k;
  cin >> a >> b >> k;

  int count=0;

  for(int i = min (a , b); i >= 1; --i){
    if(a%i==0 && b%i==0){
      count++;
      if(count==k){
        cout << i << endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 3580
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

N, M = map(int, input().split())

graph = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    graph[A].append(B)
    graph[B].append(A)


parent = [-1] * N
q = deque()
q.append(0)
visited = set()
visited.add(0)

while len(q) != 0:
    cur = q.popleft()
    for n in graph[cur]:
        if n not in visited:
            visited.add(n)
            parent[n] = str(cur + 1)
            q.append(n)

print('Yes')
ans = '\n'.join(parent[1::])
print(ans)


Measured memory_bytes: 114120
#include <bits/stdc++.h>
#define ll long long int
#define forr(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define oo 1000000000000000000LL
using namespace std;


void _sol(){
    ll x = 1000;
    ll n; cin >> n;
    ll cnt =1;
    while(cnt * x < n) cnt++;
    cout << cnt*x - n;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1; //cin >> t;
    while(t--) _sol();
}


Measured memory_bytes: 3620
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC066C
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] a = new int[n];
            int[] b = new int[n];
            string[] vals = Console.ReadLine().Split(' ');

            for(int i=0; i < n; i++)
            {
                a[i] = int.Parse(vals[i]);
            }

            int x, y;
            x = n / 2;
            y = n / 2 - 1;

            for(int i = 0; i < n; i++)
            {
                if(i % 2 == 0)
                {
                    b[x] = a[i];
                    x++;       
                }
                else
                {
                    b[y] = a[i];
                    y--;
                }
            }

            if(n % 2 == 1)
            {
                Array.Reverse(b);
            }

            for(int i=0; i < n; i++)
            {
                if(i == n-1)
                {
                    Console.Write(b[i]);
                }
                else
                {
                    Console.Write(b[i] + " ");
                }
            }
            Console.WriteLine();
        }
    }
}


Measured memory_bytes: 36960
import java.util.Scanner;

public class Main {

     static Scanner scanner;

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

         long N=gl();
         String x=gs();

         long popc=0;
         for (int i=0; i<N;i++) {
        	 char c=x.charAt(i);
        	 if(c=='1') popc++;
         }

         long mpc =popc-1;
         long ppc=popc+1;
         long mpcx=0;
         long ppcx=0;

         if (mpc>0) {
        	 for (int i=0; i<N;i++) {
        		 char c=x.charAt(i);
            	 if(c=='1') {
            		 mpcx+=modpow(2,N-i-1, mpc);
            		 mpcx%=mpc;
            	 }
        	 }
         }

         for (int i=0; i<N;i++) {
    		 char c=x.charAt(i);
        	 if(c=='1') {
        		 ppcx+=modpow(2,N-i-1, ppc);
        		 ppcx%=ppc;
        	 }
    	 }

         for (int i=0;i<N;i++) {
        	 char c=x.charAt(i);
        	 if(c=='0') {
        		 long sx=ppcx+modpow(2, N-i-1, ppc);
    			 sx%=ppc;
    			 System.out.println(1+f(sx));
        	 } else {
        		 if(mpc==0) {
        			 System.out.println(0);
        		 } else {
        			 long sx=mpcx-modpow(2, N-i-1, mpc);
        			 sx=(sx+mpc)%mpc;
        			 System.out.println(1+f(sx));
        		 }
        	 }
         }

         //System.out.println(ans);
     }

     public static long f(long x) {
    	 long ret=0;
    	 while(x>0) {
    		 ret++;
    		 x=x%popx(x);
    	 }
    	 return ret;
     }

     public static long popx(long n) {
    	 long ret=0;
    	 while(n>0) {
    		 if(n%2==1)ret++;
    		 n=n>>1;
    	 }

    	 return ret;
     }

     // a^nをmodで割ったあまり
     public static long modpow(long a, long n, long mod) {
         long res=1;
         while(n>0) {
             if((n & 1) == 1) res=res*a%mod;
             a=a*a%mod;
             n=n>>1;
         }

         return res;
     }

     // 文字列として入力を取得
     public static String gs() {
          return scanner.next();
     }

     // intとして入力を取得
     public static int gi() {
          return Integer.parseInt(scanner.next());
     }

     // longとして入力を取得
     public static long gl() {
          return Long.parseLong(scanner.next());
     }

     // doubleとして入力を取得
     public static double gd() {
          return Double.parseDouble(scanner.next());
     }
}

Measured memory_bytes: 57752
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//絶対値
long long int change_plus(long long int a) {
	if (a < 0) { return -a; }
	if (a >= 0) { return a; }
}
//大小比較(大)
long long int big(long long int a, long long int b) {
	if (a >= b) {
		return a;
	}
	else {
		return b;
	}
}

//大小比較(小)
long long int small(long long int a, long long int b) {
	if (a >= b) {
		return b;
	}
	else {
		return a;
	}
}

int main() {
	long long int n, m, k,p=3;
	char str[30],str2[15],str3[15];
	scanf("%lld%lld%lld",&n,&m,&k);
	p = (n + m)*k / 2;
	
		printf("%lld",p);
	
}

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

using ll = long long;
using P = pair<int, int>;

const int MAX = 1e5 + 10;
const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

vector<vector<int> > graph(MAX);
vector<int> ans;
bool used[MAX];

int main() {
  // 入力
  int N, M;
  cin >> N >> M;
  int a, b;
  for (int i = 0; i < M; i++) {
    cin >> a >> b;
    a--, b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  // まず、適当なパスを作る
  ans.push_back(0);
  used[0] = true;
  ans.push_back(graph[0][0]);
  used[graph[0][0]] = true;

  // 条件を満たすまで、パスを伸ばしていく
  while (1) {
    bool flag = false;
    int s = ans[0];
    int t = ans[ans.size()-1];
    for (int i = 0; i < graph[s].size(); i++) {
      int to = graph[s][i];
      if (used[to]) continue;

      ans.insert(ans.begin(), to);
      used[to] = true;
      flag = true;
      break;
    }
    if (flag) continue;
    for (int i = 0; i < graph[t].size(); i++) {
      int to = graph[t][i];
      if (used[to]) continue;

      ans.push_back(to);
      used[to] = true;
      flag = true;
      break;
    }
    if (!flag) break;
  }

  // 解答
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++) cout << ans[i] + 1 << " ";
  cout << endl;

  return 0;
}


Measured memory_bytes: 6904
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#pragma region Macros
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define ALL(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
#define CEIL(a,b) ((a+b-1)/b)
#define LAST(X) X[X.size()-1]
#define MOD 1000000007
int GCD(int a, int b) // assuming a,b >= 1
{
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	if (a % b == 0)
		return b;
	return GCD(b, a % b);
}
int LCM(int a, int b) // assuming a,b >= 1
{
	return  a * b / GCD(a, b);
}
inline bool BETWEEN(int x, int min,int max) {
	if (min <= x && x <= max)
		return true;
	else
		return false;
}

using namespace std;
#pragma endregion
signed main() {
	int A,B,C,D;
	cin >> A >> B >> C >>D;
	cout << max(A*B,C*D);
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<tuple>
using namespace std;
char x[500][500]; int H, W;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++)cin >> x[i][j];
	}
	int CNT = 0;
	while (true) {
		int cnt = 0;
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (x[i][j] != '.')continue;
				vector<tuple<char, int, int>>vec;
				for (int k = 0; k < 4; k++) {
					int cx = i, cy = j;
					while (cx >= 0 && cx < H && cy >= 0 && cy < W) {
						if (x[cx][cy] != '.') { vec.push_back(make_tuple(x[cx][cy], cx, cy)); break; }
						cx += dx[k]; cy += dy[k];
					}
				}
				for (int k = 0; k < vec.size(); k++) {
					for (int l = k + 1; l < vec.size(); l++) {
						if (get<0>(vec[k]) == get<0>(vec[l])) {
							x[get<1>(vec[k])][get<2>(vec[k])] = '.'; cnt++;
							x[get<1>(vec[l])][get<2>(vec[l])] = '.'; CNT += 2;
						}
					}
				}
			}
		}
		if (cnt == 0)break;
	}
	cout << CNT << endl;
	return 0;
}

Measured memory_bytes: 3328
import sys
input = sys.stdin.readline

n = int(input())
a = [int(a) for a in input().split()]
s = [None] * n; s[0] = a[0]
for i in range(n-1): s[i+1] = s[i] + a[i+1]

mixi = abs(s[0] - (s[n-1] - s[0]))
for i in range(1, n-1): mixi = min(mixi, abs(s[i] - (s[n-1] - s[i])))   # 全部取るのはダメ

print(mixi)

Measured memory_bytes: 24680
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

long long int gcd(long long int a, long long int b) {
    if (a < b)swap(a, b);
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}


LL A,B,C,D;
LL calc(LL x){
    LL ccnt = x / C;
    LL dcnt = x / D;
    LL lcm = C / gcd(C,D) * D;
    LL cdcnt = x / lcm;
    return x - ccnt - dcnt + cdcnt;
}

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> A>>B>>C>>D;

    cout << calc(B) - calc(A-1) << endl;

}

Measured memory_bytes: 256
//inlclude before define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<type_traits>
#include<numeric>
#include<assert.h>
#include<deque>
#include<iomanip>
#include<set>
#include<tuple>
#include<map>

using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef pair<int, int> P1;
typedef long long int ll;

//define
#define INF 1e9
#define NUM 1000000007
#define all(x) begin(x),end(x)
#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)
#define REP(i,a,b) for(int i=int(a);i<int(b);i++)
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))

//function

/*ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a%b);
}*/

/*ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a * (b / g);
}*/

int main() {
	int n;
	string s,ans;
	bool flag = true;
	VI rec(27), mem(27),fir(27);
	cin >> n;
	rep(i, n) {
		cin >> s;
		rep(i, 27) mem[i] = 0;
		if (i == 0) {
			rep(j, s.size()) rec[s[j] - 'a']++;
		} else {
			rep(j, s.size()) mem[s[j] - 'a']++;
			rep(j, 27) {
				if (rec[j] > 0 && mem[j] == 0) {
					rec[j] = 0;
				} else {
					rec[j] = min(rec[j], mem[j]);
				}
			}
			/*rep(i, 27) {
				cout << rec[i] << " " << mem[i] << "\n";
			}*/
		}
	}
	//rep(i, 27) cout << rec[i] << "\n";
	//cout << "\n";

	rep(i, 27) {
		rep(j, rec[i]) {
			ans += 'a' + i;
		}
	}
	sort(all(ans));
	cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define MOD 1000000007
#define INF 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define req(i, j, n) for(int i = j; i <= (int)(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main() {
ll n;
  cin>>n;
  
  ll a,b;
  cin>>a>>b;
  
  ll ans=0;
  if((b-a)%2==0){
    cout<<(b-a)/2<<endl;
    return 0;}
  
  
  
  
  cout<<min(a+(b-a-1)/2, n-b+1+(b-a-1)/2)  <<endl;
  return 0;
  
  

}


Measured memory_bytes: 384
#include<stdio.h>
int main(void){
    int S,h,m,s;
    h=0;m=0;s=0;
    scanf("%d", &S);
    while(S>=3600){
        S -= 3600;
        h +=1;
    }
    while(S>=60){
        S -=60;
        m +=1;
    }
    s=S;
    printf("%d:%d:%d\n", h, m, s);
    return 0;
}


Measured memory_bytes: 2048
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int,int> P;
int arr[200005];
vector<P> v;
int main() {
	int n,k;
	scanf("%d%d",&n,&k);
	int in;
	for(int i=0;i<n;++i) {
		scanf("%d",&in);
		arr[in]++;
	}
	for(int i=0;i<=200000;++i) {
		if(arr[i]) {
			v.push_back(P(arr[i],i));
		}
	}
	sort(v.begin(),v.end());
	int ans=0;
	int mx=v.size()-k;
	for(int i=0;i<((mx<0)?0:mx);++i) {
		ans+=v[i].first;
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 3188
import java.io.InputStreamReader;
import java.io.LineNumberReader;

/**
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_8_D
 * 
 * @author eitatsuro
 * 
 */
public class Main {
    
    public static void main(String[] args) {
        try {
            LineNumberReader lineNumReader = new LineNumberReader(
                    new InputStreamReader(System.in));

            String inputStr = null;
            String s = null;
            String p = null;
            boolean answer = false;
            
            while ((inputStr = lineNumReader.readLine()) != null) {

                if (lineNumReader.getLineNumber() == 1) {
                    s = inputStr;
                }
                
                if (lineNumReader.getLineNumber() == 2) {
                    p = inputStr;
                    break;
                }
            }

            // p???s??????????????????????????????.
            // ?????????p????????????s?????°??±???????????????????????§??????????????§???
            // ?????????p??¨s??????????????????????????????
            // ?????????????????????s??????????????????
            StringBuilder longS = new StringBuilder();
            for ( int i=0; i < 2+ p.length()/s.length(); i++){
                longS.append(s);
            }
            

            if (longS.indexOf(p) <= -1) {
                answer = false;
            } else {
                answer = true;
            }

            
            // ??¢???????????????
            if (answer) {
                 System.out.println("Yes");
            } else {
                System.out.println("No");
            }

            lineNumReader.close();
        } catch (Exception e) {
            System.exit(-1);
        }
        
    }
}

Measured memory_bytes: 24276
x1, y1, x2, y2 = map(int, input().split())

disx = x2 - x1
disy = y2 - y1

x3 = x2 - disy
y3 = y2 + disx
x4 = x1 - disy
y4 = y1 + disx


print(x3, y3, x4, y4)

Measured memory_bytes: 3060
import java.util.*;
public class Main{
public static void main(String arg[]){
	Scanner sc=new Scanner(System.in);
	String a=sc.next();
	if(a.charAt(0)=='A')
	System.out.println("T");
    if(a.charAt(0)=='T')
		System.out.println("A");
	if(a.charAt(0)=='C')
		System.out.println("G");
	if(a.charAt(0)=='G')
		System.out.println("C");
	}
}

Measured memory_bytes: 20692
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, b = map(int, input().split())
    bits = 0
    for i in map(int, input().split()):
        bits = bits | (1 << (i - 1))
    keys.append([a, bits])

dp = [[INF] * (2 ** N + 10) for _ in range(M + 10)]
dp[0][0] = 0

for i in range(M):
    for j in range(2 ** N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][j | keys[i][1]] = min(dp[i + 1][j | keys[i][1]], dp[i][j] + keys[i][0])
print(dp[M][2 ** N - 1] if dp[M][2 ** N - 1] != INF else -1)

Measured memory_bytes: 101608
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;

int main(){
  int A,B;
  cin>>A>>B;
  bool ok = false;
  if(A%3==0) ok = true;
  if(B%3==0) ok = true;
  if((A+B)%3==0) ok = true;
  cout << (ok ? "Possible" : "Impossible") << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define reg register
typedef long long ll;
using namespace std;
const int MN=2e5+5;
int to[MN<<1],nxt[MN<<1],h[MN],cnt;
inline void ins(int s,int t){
	to[++cnt]=t;nxt[cnt]=h[s];h[s]=cnt;
	to[++cnt]=s;nxt[cnt]=h[t];h[t]=cnt;
}
int n,a[MN],f[MN],d[MN],len;
int solve(int x){
	reg int l=1,r=len,mid,ans=0;
	while(l<=r){
		mid=(l+r>>1);
		if(d[mid]<x)ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
void dfs1(int st,int fa=0){
	reg int pos=solve(a[st]),pre;
	if(pos==len)len++,pre=-1;
	else pre=d[pos+1];
	f[st]=pos+1;d[pos+1]=a[st];
	for(reg int i=h[st];i;i=nxt[i])
		if(to[i]!=fa)dfs1(to[i],st);
	if(pre<0)d[len--]=0;
	else d[pos+1]=pre;
}
void dfs2(int st,int fa=0){
	f[st]=max(f[st],f[fa]);
	for(reg int i=h[st];i;i=nxt[i])
		if(to[i]!=fa)dfs2(to[i],st);
}
int main(){
	scanf("%d",&n);
	for(reg int i=1;i<=n;i++)scanf("%d",a+i);
	for(reg int i=1,s,t;i<n;i++)
		scanf("%d%d",&s,&t),ins(s,t);
	dfs1(1);dfs2(1);
	for(reg int i=1;i<=n;i++)printf("%d\n",f[i]);
	return 0;
}

Measured memory_bytes: 23448
// https://beta.atcoder.jp/contests/abc104
// http://drken1215.hatenablog.com/entry/2018/08/05/224100_1

#define SUBMIT

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <cmath>
#include <unordered_map>
#include <map>

using namespace std;
using ui64 = unsigned long long;
using i64 = long long;

const int MOD = 1000000007;

string S;
// dp[i][0] i - 1文字目まで考えたときにABCとの照合をスタートすらしていない個数
// dp[i][1] i - 1文字目まで考えたときにABCとの照合をAまでは照合させた個数
// dp[i][2] i - 1文字目まで考えたときにABCとの照合をBまでは照合させた個数
// dp[i][3] i - 1文字目まで考えたときにABCとの照合をCまでは照合させた個数
ui64 dp[100000 + 1][3 + 1];


int main() {
#ifdef SUBMIT
    cin >> S;
#else
    S = "????C?????B??????A???????";
#endif
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    for (int i = 0; i < S.length(); ++i) {
        for (int j = 0; j < 3 + 1; ++j) {
            if (S[i] != '?') dp[i + 1][j] += dp[i][j];
            else dp[i + 1][j] += (dp[i][j] * 3) % MOD;

            dp[i + 1][j] %= MOD;
        }

        if (S[i] == 'A' || S[i] == '?') {
            dp[i + 1][1] += dp[i][0];
            dp[i + 1][1] %= MOD;
        }
        if (S[i] == 'B' || S[i] == '?') {
            dp[i + 1][2] += dp[i][1];
            dp[i + 1][2] %= MOD;
        }
        if (S[i] == 'C' || S[i] == '?') {
            dp[i + 1][3] += dp[i][2];
            dp[i + 1][3] %= MOD;
        }
    }

    cout << dp[S.length()][3] << endl;
    return 0;
}

Measured memory_bytes: 3584
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	private void doit() {
		while (true) {
			int [] data = new int[6];
			boolean flg = true;
			for(int i = 0; i < 6; i++){
				data[i] = sc.nextInt();
				if(data[i] != 0) flg = false;
			}
			if(flg) break;
			int plus = data[0] * 15 + data[1] * 15 + data[2] * 7 + data[3] * 2 + data[0] * 5 * 13 + data[1] * 3 * 13;
			int minus = (data[5] - data[4] - data[0] * 5 - data[1] * 3) * 3;
			System.out.println(plus + 100 - minus);
		}
	}


	private void debug(Object... o) {
		System.out.println("debug = " + Arrays.deepToString(o));
	}

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

Measured memory_bytes: 20812
import numpy as np


n = input()
n = int(n)

class abc:
    def __init__(self, index, number):
        self.index = index
        self.number = number

ls = []

temp_input = input().split()

for i in range(n):
    temp = temp_input[i]
    temp = int(temp)
    ls += [abc(i, temp)]

ls.sort(key = lambda abc:abc.number)
a = n // 2
output = []

for i in range(n):
    if(i < a):
        number = ls[a].number
        index = ls[i].index
    else:
        number = ls[a - 1].number
        index = ls[i].index
    output += [abc(index, number)]

output.sort(key = lambda abc:abc.index)

for i in range(n):
    print(output[i].number)

Measured memory_bytes: 114236
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
#include <complex>
using namespace std;
 
#define ll long long
#define vvi vector< vector<int> >
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back 
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
 
int main(){

  while(1){
    int n,r;
    cin>>n >>r;
    if(n==0&&r==0)  break;
    int cards[n-1];
    REP(i,n){
      cards[i] = (n-i);
    }
    int help[100]={0};
    int p[100];
    int c[100];
    REP(i,r){
      cin>>p[i]>>c[i];
      REP(j,c[i]){
	help[c[i]-j-1] = cards[p[i]+c[i]-2-j];
      }
      for(int j=0;(p[i]-1-j)>=0;j++){
	if((p[i]-1-j)<0) break;
	cards[p[i]+c[i]-2-j] = cards[p[i]-2-j];
      }
      REP(j,c[i]){
	cards[j]=help[j];
      }
    }
    cout << cards[0] << endl;
  }
  return 0;
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int ispal(string k)
{
    string r=k;
    reverse(r.begin(),r.end());
    if(r==k)
    return 1;
    else
    return 0;
}
int main()
{
   ll l;
   cin>>l;
   double k=double(l)/3;
   double ans=k*k;
   ans=ans*k;
   printf("%0.9f\n",ans);
   return 0;
}


Measured memory_bytes: 256
N = gets.to_i
rm = nil
ans = N
(0...N).map{ x,l = gets.split.map &:to_i; [x-l,x+l] }.sort_by{ |range| range[0] }.each{ |l,r|
  if !rm
    rm = r
  else
    if rm <= l
      rm = r
    else
      rm = [rm, r].min
      ans -= 1
    end
  end
}

p ans


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

typedef double du ;
typedef string st ;
typedef long long ll ;
typedef long double ld ;
typedef long long int lli ;

#define vi vector <lli>
#define loop(num) for (lli i = 0 ; i < num ; i ++ )
#define loopcin(num , ar ) for (lli i = 0 ; i < num ; i ++ ) {cin >> ar [i] ;}
#define loopcout(num , ar) for (lli i = 0 ; i < num ; i ++ ) {cout << ar [i] << ' '; }
#define looppu(num , ar) for (lli i = 0 ; i < num ;  i++) {lli x ; cin >> x ; ar . push_back (x) ;}
#define loopin(num , ar) for (lli i = 0 ; i < num ;  i++) {lli x ; cin >> x ; ar . insert (x) ;}

#define forr(num1 , num2) for (lli i = num1 ; i < num2 ; i ++ )
#define forrcin(num1 , num2 , ar ) for (lli i = num1 ; i < num2 ; i ++ ) {cin >> ar [i] ;}
#define forrcout(num1 , num2 , ar) for (lli i = num1 ; i < num2 ; i ++ ) {cout << ar [i] << ' '; }

#define D2forrcin(num1_1 , num1_2 , num2_1 , num2_2 , A ) for (lli i = num1_1 ; i < num1_2 ; i ++){ for (lli j = num2_1 ; j < num2_2 ; j++){cin >> A[i][j] ;}}
#define D2forrcout(num1_1 , num1_2 , num2_1 , num2_2 , A ) for (lli i = num1_1 ; i < num1_2 ; i ++){ for (lli j = num2_1 ; j < num2_2 ; j++){cout << A[i][j] << ' ' ;}cout << endl ;}

#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

#define F first
#define S second

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

signed main ()
{
    fastio
    lli n , cnt  = 0 ;
    cin >> n ;
    lli a[n] ;
    loopcin(n , a) ;

    for (ll i = 1 ; i < n - 1 ; i ++)
    {
        if (a[i] < a[i - 1] && a[i] > a[i + 1] || a[i] > a[i - 1] && a[i] < a[i + 1])
            cnt ++ ;
    }
    cout << cnt << endl ;

    return 0 ;
}

/*___________________________________________________________________functions___________________________________________________________________________*/



Measured memory_bytes: 256