akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// Disjoint Set
template<typename T>
class UnionFind {
 public:
  // n要素で生成
  explicit UnionFind(T n) : _size{n}, _parent{vector<T>(n, -1)} {}
  // 木の根を求める
  T find(T x) {
    if (x < 0 || x >= _size) return x;
    if (_parent[x] < 0) return x;
    return _parent[x] = find(_parent[x]);
  }
  // xとyの属する集合を併合する
  bool unite(T x, T y) {
    if (x < 0 || x >= _size || y < 0 || y >= _size) return false;
    x = find(x), y = find(y);
    if (x == y) return false;
    if (size(x) > size(y)) {
      _parent[x] += _parent[y];
      _parent[y] = x;
    } else {
      _parent[y] += _parent[x];
      _parent[x] = y;
    }
    return true;
  }
  // xとyが同じ集合に属するか
  bool same(T x, T y) { return find(x) == find(y); }
  // xの属する集合の個数を求める
  T size(T x) {
    if (x < 0 || x >= _size) return 1;
    return -_parent[find(x)];
  }
  // 全体の個数を求める
  T size() { return _size; }
 private:
  T _size;
  vector<T> _parent; // 親の番号（親自身はー（マイナス）集合要素の個数）
};

constexpr int MAX_N = 1e5;
set<int> like[MAX_N];
int ans[MAX_N];

int main() {
  int N, M, K;
  cin >> N >> M >> K;
  UnionFind<int> uf(N);
  for (int i{}; i < M; ++i) {
    int A, B;
    cin >> A >> B;
    --A, --B;
    like[A].insert(B), like[B].insert(A);
    uf.unite(A, B);
  }
  for (int i{}; i < K; ++i) {
    int C, D;
    cin >> C >> D;
    --C, --D;
    like[C].insert(D), like[D].insert(C);
  }

  for (int i{}; i < N; ++i) {
    int root = uf.find(i);
    ans[i] = uf.size(i) - 1;
    for (const auto &j : like[i]) {
      if (root == uf.find(j)) --ans[i];
    }
  }

  cout << ans[0];
  for (int i{1}; i < N; ++i) {
    cout << ' ' << ans[i];
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 25088
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
using namespace std;
namespace adaptor = boost::adaptors;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
typedef long long ll;

void Main()
{
	int N, K, Q;
  	cin >> N >> K >> Q;
    vector<int> A(Q);
    rep(i,Q) {
    	cin >> A[i];
        A[i]--;
    }
    
    vector<int> point(N,0);
	
    rep(i,Q){
    	point[A[i]]++;
    }
    rep(i,N){
		if(K-Q+point[i] > 0){ puts("Yes"); }
    	else { puts("No"); }
	}	
    return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}




Measured memory_bytes: 1408
while True:
    h,w = map(int,input().split())
    if h == 0 and w == 0:
        break
    ans = ''
    for i in range(h):
        if i % 2 == 0:
            for j in range(w):
                if j % 2 == 0:
                    ans += '#'
                else:
                    ans += '.'
        else:
            for j in range(w):
                if j % 2 == 0:
                    ans += '.'
                else:
                    ans += '#'
        print(ans)
        ans = ''
    print("")


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

bool YYMM(vector<char> S){
    if (S[2]=='0' && S[3] != '0') return true;
    else if (S[2]=='1' && (S[3]=='0' || S[3]=='1' || S[3]=='2')) return true;
    else return false;
}
  
bool MMYY(vector<char> S){
    if (S[0]=='0'&& S[1] != '0') return true;
    else if (S[0]=='1' && (S[1]=='0' || S[1]=='1' || S[1]=='2')) return true;
    else return false;
}

int main() {
  vector<char> S(4);
  rep(i, 4) cin >> S[i];
  
  
  
  if (YYMM(S)){
    if (MMYY(S)) puts("AMBIGUOUS");
    else puts("YYMM");
  }
  else if (MMYY(S)) puts("MMYY");
  else puts("NA");
  
  
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <complex>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::cerr;

using std::string;
using std::to_string;
using std::vector;
using std::set;
using std::queue;
using std::stack;
using std::priority_queue;

using std::min;
using std::max;
using std::sort;
using std::abs;

typedef long long int ll;
const int MOD = 1e9 + 7;

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

    int n = s.length();

    if (s[n / 2] == '1') {
        for (int i = 0; i < n; i++) {
            s[i] = s[i] == '0' ? '1' : '0';
        }
    }

    string a0 = s.substr(0, n / 2);
    std::reverse(a0.begin(), a0.end());

    string a1 = s.substr(n - n / 2, n);

    //cout << a0 << endl;
    //cout << a1 << endl;

    int p0 = n / 2;
    for (int i = 0; i < n / 2; i++) {
        if (a0[i] == '1') {
            p0 = i;
            break;
        }
    }

    int p1 = n / 2;
    for (int i = 0; i < n / 2; i++) {
        if (a1[i] == '1') {
            p1 = i;
            break;
        }
    }

    int p = min(p0, p1);
    int h = n / 2 - p;
    cout << n - h << endl;

    return 0;
}


Measured memory_bytes: 512
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define fore(x, c) for(auto &&x : c)
#define rep(i, a, n) for(int i = a, i##len = (int)(n); i < i##len; ++i)
#define rrep(i, a, n) for(int i = (int)(n - 1); i >= a; --i)
#define sz(c) ((int)c.size())
#define contains(c, x) (c.find(x) != end(c))
#define inseg(l, x, r) ((l) <= (x) && (x) < (r))
#define dump(...)
#define pb push_back
#define eb emplace_back
#define _ 0
const signed INF_ = 1001001001; const long long INF = 1001001001001001001LL;
const int DX[9] = {0,1,0,-1,1,1,-1,-1,0}, DY[9] = {-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os, const vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is, vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
  is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a, const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a, const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap = priority_queue<T, deque<T>, greater<T>>;
struct before_main_function {
  before_main_function() {
      cin.tie(nullptr); ios::sync_with_stdio(false);
      cout << setprecision(15) << fixed;
  }
} before_main_function;
// clang-format on
//------------------8<------------------------------------8<--------------------

signed main() {
  char x;
  cin >> x;
  if (isupper(x))
    cout << 'A' << endl;
  else
    cout << 'a' << endl;
  return (0 ^ _ ^ 0);
}



Measured memory_bytes: 3652
#include <stdio.h>
#include <stdlib.h>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN+1];
int head, tail, n;

void enqueue(P x){
  Q[tail] = x;
  tail = (tail + 1) % LEN;
}

P dequeue(){
  P x = Q[head];
  head = (head + 1) % LEN;
  return x;
}

int min(int a, int b){
  return a < b ? a : b;
}


int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);

  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head = 1;
  tail = n + 1;
  while(head != tail){
    u = dequeue();
    c = min(q, u.t);
    u.t -= c;
    elaps += c;
    if(u.t > 0)enqueue(u);
    else printf("%s %d\n",u.name,elaps);
  }
  return 0;
}



Measured memory_bytes: 11852
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define el '\n'
#define MOD 1000000007

int n,q;
string s;

int dp[100005];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> q >> s;
    dp[1]=0;
    if(s[0]=='A' && s[1]=='C'){
        dp[2]=1;
    }
    for(int i=2;i<n;i++){
        if(s[i]=='C' && s[i-1]=='A'){
            dp[i+1]=dp[i-1]+1;
        } else {
            dp[i+1]=dp[i];
        }
    }
    

    while(q--){
        int l,r;
        cin >> l >> r;

        cout << dp[r]-dp[l] << el;
    }
    return 0;
}

Measured memory_bytes: 1488
#include<stdio.h>
int main()
{
	int W, H, x, y, r;
	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

	if ((0 <= x - r) && (W >=x + r)&&(0<=y-r)&&(H>=y+r)){
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return 0;

}

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


int main(void)
{ 
  int n,x,l[100],i,j,k,ans,a,b;
  cin>>n>>x;
  for(i=0;i<n;i++){cin>>l[i];}
  k=0;
  ans=0;
  if(0<=x){ans++;}
  for(i=0;i<n;i++)
  {
    k=k+l[i];
    if(k<=x){ans++;}
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T> >;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define repb(i, n) for(ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for(ll i = (a); i < (b); i++)
#define reprb(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; }
inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; }
inline ll powint(unsigned long long x, ll y){ ll r=1; while(y){ if(y&1) r*=x; x*=x; y>>=1; } return r; }
inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; }
template<class S, class T>inline bool chmax(S &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class S, class T>inline bool chmin(S &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif

void PR(bool f){
    cout << (f ? "YES" : "NO") << endl;
    exit(0);
}
vvll g;

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n, m;
    cin >> n >> m;
    vll a(m), b(m);
    rep(i, m){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
    g.resize(n, vll());
    rep(i, m){
        g[a[i]].emplace_back(b[i]);
        g[b[i]].emplace_back(a[i]);
    }
    rep(i, n){
        if(SZ(g[i]) & 1) PR(0);
    }
    PR(1);
    return 0;
}

Measured memory_bytes: 7680
import sys
input=sys.stdin.readline
n=int(input())
s_list=[0]+[int(input()) for i in range(n)]
dp=[[False]*10001 for i in range(n+1)]
dp[0][0]=True
for i in range(1,n+1):
    for j in range(10001):
        if j>=s_list[i]:
            dp[i][j]=dp[i-1][j] or dp[i-1][j-s_list[i]]
        else:
            dp[i][j]=dp[i-1][j]
ans=0
for i in range(1,10001):
    if dp[n][i]:
        if i%10==0:
            pass
        else:
            ans=i
print(ans)









Measured memory_bytes: 48876
X, Y, A, B, C = list(map(int, input().split(" ")))
p_list = sorted(list(map(int, input().split(" "))), reverse=True)
q_list = sorted(list(map(int, input().split(" "))), reverse=True)
c_list = sorted(list(map(int, input().split(" "))), reverse=True)
p_list = p_list[:X]
q_list = q_list[:Y]
all_list = p_list+q_list+c_list
all_list.sort(reverse=True)
print(sum(all_list[0:X+Y]))


Measured memory_bytes: 22460
/* Akshat Sharma @akshat98 */
#include <iostream>
#include <bits/stdc++.h>
#define IOS  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define mp   make_pair
#define pb   push_back
#define F    first
#define S    second
#define ll   long long
#define MOD  1000000007
#define MAX  1000000001
#define vi   vector<int>
#define vl   vector<ll>
#define vpi  vector<pair<int,int> >
#define vpl  vector<pair<ll,ll> >
#define rep(i,a,b) for(i=a;i<b;i++)
#define reqp(i,a,b) for(i=a;i<=b;i++)
#define ren for(i=0;i<n;i++)
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;


int main()
{

	ll i,j,k,l,n,test_case,m,r;
	test_case=1;
	//cin>>test_case;
	while(test_case--){
		cin>>n;
		ll dp[n+1][4];

		rep(i,0,n){
			rep(j,0,4){
				dp[i][j]=LLONG_MIN;
			}
		}
		vl vec(n);
		ren cin>>vec[i];

		dp[0][0]=vec[0];
		dp[1][1]=vec[1];
		dp[2][0]=vec[0]+vec[2];
		dp[2][2]=vec[2];
		rep(i,3,n){
			dp[i][0]=vec[i]+dp[i-2][0];
			dp[i][1]=max(vec[i]+dp[i-3][0],vec[i]+dp[i-2][1]);
			dp[i][2]=(max(vec[i]+dp[i-2][2],vec[i]+dp[i-3][1]));
			if(i>=4)
			dp[i][2]=max(dp[i][2],vec[i]+dp[i-4][0]);
		}
		ll ans=LLONG_MIN;
		if(n&1){
			ans=max(ans,dp[n-1][2]);
			ans=max(ans,dp[n-2][1]);
			ans=max(ans,dp[n-3][0]);
		}else{
			ans=max(ans,dp[n-1][1]);
			ans=max(ans,dp[n-2][0]);
		}
		cout<<ans<<"\n";



	}
	
	return 0;
}


Measured memory_bytes: 11168
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;

    int max = 0;
    vector<int> A(N);
    for (int i=0; i<N; i++) {
        cin >> A[i];
        if (max < A[i]) {
            max = A[i];
        }
    }

    int half = max / 2;

    int min = 1e9;
    int answer = 0;
    for (int i=0; i<N; i++) {
        if (A[i] == max) continue;
        int diff = abs(A[i] - half);
        if (diff < min) {
            answer = A[i];
            min = diff;
        }
    }

    cout << max << " " << answer << endl;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <math.h>
int main(void){
	int n,a,i,ans=0,t;
	double h,diff;
	scanf("%d %d %d",&n,&t,&a);
	scanf("%lf",&h);
	diff = fabs((t-0.006*h)-a);
	for(i=1;i<n;i++){
		scanf("%lf",&h);
		double x = fabs((t-0.006*h)-a);
		if(x<diff){
			diff=x;
			ans=i;
		}
	}
	printf("%d",ans+1);
	return 0;
}

Measured memory_bytes: 128
"use strict"

const main = arg => {
  arg = arg.trim().split("\n");
  const str = arg[0];
  const len = str.length;
  const k   = parseInt(arg[1]);

  const initials = [...new Set(str.split(''))].sort();
  let index = 0;
  const dic = new Set();

  while(dic.size < k) {
    for(let i=0; i<len; i++) {
      let j = 1;
      if(str.slice(i, i + j) !== initials[index]) continue;

      while(i + j <= len && j <= 5) {
        dic.add(str.slice(i, i + j));
        j += 1;
      }
    }
    
    index++;
  }
  
  const ans = [...dic].sort()[k - 1];
  console.log(ans);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 8088
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n, m, i, j, k, a, b, c, h[N], v[N];
struct AB{
	int a, b, c, n;
} d[N*2];
void cun(int a, int b, int c){
	d[++k].n = h[a], h[a] = k;
	d[k].a = a, d[k].b = b, d[k].c = c;
}
void dfs(int a){
	int b, c, i;
	for(i=h[a]; i; i=d[i].n){
		b = d[i].b, c = d[i].c;
		if(!v[b]){
			v[b] = v[a] + c;
			dfs(b);
		}
	}
}
int main(){
	scanf("%d", &n);
	for(i=1; i<n; i++){
		scanf("%d%d%d", &a, &b, &c);
		cun(a, b, c);
		cun(b, a, c);
	}
	dfs(v[1] = 1);
	for(i=1; i<=n; i++){
		printf("%d\n", v[i]&1);
	}
	return 0;
}

Measured memory_bytes: 5632
fun main(args: Array<String>) {
    val (n, t) = readLine()!!.split(" ").map(String::toInt)
    val ct = (1..n).map { readLine()!!.split(" ").map(String::toInt) }
            .filter { it[1] <= t }
            .sortedBy { it[0] }

    val ans = if (ct.isEmpty()) { "TLE" } else { ct[0][0] }
    println(ans)
}

Measured memory_bytes: 37996
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using ll = unsigned long long int;
using namespace std;

int main() {
    fastIO;
    size_t n;
    cin >> n;

    vector<ll> Lucas(n + 1);
    Lucas.at(0) = 2;
    Lucas.at(1) = 1;
    for (size_t i = 2; i <= n; i++) {
        Lucas.at(i) = Lucas.at(i - 1) + Lucas.at(i - 2);
        // cout << Lucas.at(i) << endl;
    }
    cout << Lucas.at(n) << endl;
}

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

struct ToUpper {
    char operator()(char c) { return toupper(c); }
};

int main(void)
{
	string a;
	getline(cin,a);
	transform(a.begin(),a.end(),a.begin(),ToUpper());
	cout<<a<<endl;
	return 0;
}

Measured memory_bytes: 1176
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;

int main() {
    int a, b, p, q, r;
    cin >> a >> b >> p >> q >> r;

    double x = (b - a) * q, y = p * b;
    cout << setprecision(18) << b + (y - x) / (r + q) << endl;

}


Measured memory_bytes: 3292
#include "bits/stdc++.h"
using namespace std;
#ifndef LOCAL
#define endl '\n'
#endif

#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define pf push_front
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound

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

int pct(int x) { return __builtin_popcount(x); }
int pct(ll x) { return __builtin_popcountll(x); }
int bt(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))
int bt(ll x) { return 63 - __builtin_clzll(x); } // floor(log2(x))
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
ll cdiv(ll a, ll b) { return a / b + !(a < 0 || a % b == 0); }
int nxt_C(int x) { int c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }
ll nxt_C(ll x) { ll c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }

vector<int> get_bits(int mask) {
	vector<int> bb;
	while(mask) { int b = bt(mask); bb.pb(b); mask ^= (1 << b); }
	reverse(all(bb));
	return bb;
}

int get_mask(vector<int> v) {
	int mask = 0;
	for(int x : v) { mask ^= (1 << x); }
	return mask;
}

template<typename T>
void uniq(vector<T> &v) { sort(all(v)); v.resize(unique(all(v)) - v.begin()); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r){
	uniform_int_distribution<ll> uid(l, r);
	return uid(rng);
}

void sc() {}

template <typename Head, typename... Tail>
void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }

#ifdef LOCAL
#define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// #ifndef LOCAL
// string to_string(__int128 x) {
// 	string s = "";
// 	bool neg = 0;
// 	if(x < 0) { s += "-"; neg = 1; x = -x; }
// 	if(!x) s += '0';
// 	while(x) {
// 		int rem = x % 10;
// 		s += to_string(rem);
// 		x /= 10;
// 	}
// 	reverse(s.begin() + neg, s.end());
// 	return s;
// }
// #endif

const int mod = 1e9 + 7; // 998244353;

int pwr(int a,ll b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = (ans * 1LL * a) % mod;
		a = (a * 1LL * a) % mod;
		b >>= 1;
	}
	return ans;
}

/*
	Lookout for overflows!!
	Check array sizes!!
	Clear before test cases!!
	Use the correct modulo!!
	Check for corner cases!!
	Are you forgetting something?!
	Read problem statement carefully!!!
*/

const int N = 1e5 + 5;
vector<int> g[N];

int dfs(int u,int p) {
    int ans = 0;
    for(int v : g[u]) {
        if(v != p) {
            ans ^= (dfs(v, u) + 1);
        }
    }
    return ans;
}

void solve() {
	int n;
    sc(n);
    fr(i, 1, n - 1) {
        int u, v;
        sc(u, v);
        g[u].pb(v);
        g[v].pb(u);
    }
    int ans = dfs(1, 0);
    cout << ((ans) ? "Alice" : "Bob");
}

int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	// cin >> t;
	for(int tt = 1; tt <= t; tt++) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 10368
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func fact(x, mod int) int {
	result := 1
	for i := 0; i < x; i++ {
		result = result * (i + 1) % mod
	}
	return result
}

func swapInt(x, y int) (int, int) {
	return y, x
}

func inv(x, mod int) int {
	b := mod
	u := 1
	v := 0

	for b > 0 {
		t := x / b
		x -= t * b
		x, b = swapInt(x, b)
		u -= t * v
		u, v = swapInt(u, v)
	}
	u %= mod
	if u < 0 {
		u += mod
	}
	return u
}

func main() {
	var mod int = 1000000007

	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	input := scanner.Text()
	inputList := strings.Split(input, " ")
	x, _ := strconv.Atoi(inputList[0])
	y, _ := strconv.Atoi(inputList[1])

	aNum := 0
	bNum := 0
	if (x+y)%3 != 0 || 2*x < y || 2*y < x {
		fmt.Println(0)
	} else {
		aNum = y - x + ((x+y)-(y-x)*3)/6
		bNum = x - y + ((x+y)-(x-y)*3)/6
		n := fact(aNum+bNum, mod)
		a := fact(aNum, mod)
		b := fact(bNum, mod)
		n = n * inv(a, mod) % mod
		n = n * inv(b, mod) % mod

		fmt.Println(n)
	}
}

// 1,2をA、2,1をBとすると、XYにたどり付けるAB列を作ってその並べ替えが数になる


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
string s;
int len;
int main()
{
	cin>>s;
	len=s.length();
	if(s[0]==s[len-1])
	{
		if(len&1)
		    printf("Second");
		else
		    printf("First");
	}
	else
	{
		if(len&1)
		    printf("First");
		else
		    printf("Second");
	}
	return 0;
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        string s = Console.ReadLine();
        int k = int.Parse(Console.ReadLine());

        string ans = "";

        for (int i = 0; i < n; i++)
        {
            if (s[i] != s[k - 1]) ans += "*";
            else ans += s[i];
        }

        Console.WriteLine(ans);
    }
}

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

int len = 0;
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> pq;

int ask(string s) {
    cout << "? " << s << endl;
    int ret; cin >> ret; return ret;
}

string repeat(char c, int t) {
    string s = "";
    for (int i = 0; i < t; i++) {
        s += c;
    }
    return s;
}

string merge(string s, string t) {
    string ans = "";
    while (!s.empty() && !t.empty()) {
        string tmp = ans + t[0] + s;
        if (ask(tmp) != len - (int)tmp.size()) {
            ans += s[0];
            s.erase(0, 1);
        } else {
            ans += t[0];
            t.erase(0, 1);
        }
    }
    return ans + s + t;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for (char c = 'a'; c <= 'z'; c++) {
        string s = repeat(c, 128 - ask(repeat(c, 128)));
        len += s.size();
        pq.push({s.size(), s});
    }
    for (char c = 'A'; c <= 'Z'; c++) {
        string s = repeat(c, 128 - ask(repeat(c, 128)));
        len += s.size();
        pq.push({s.size(), s});
    }
    for (char c = '0'; c <= '9'; c++) {
        string s = repeat(c, 128 - ask(repeat(c, 128)));
        len += s.size();
        pq.push({s.size(), s});
    }
    while (pq.size() > 1) {
        string s = pq.top().second; pq.pop();
        string t = pq.top().second; pq.pop();
        string me = merge(s, t);
        pq.push({me.size(), me});
    }
    cout << "! " << pq.top().second << endl;
}


Measured memory_bytes: 3748
#include <bits/stdc++.h>
using namespace std;
#define maxn 1500000
#define INF 199999999
int W, H, n, top, top2, S[maxn], S2[maxn];
int ans, mark[maxn], mx[maxn];

int read()
{
	int x = 0, k = 1;
	char c; c = getchar();
	while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * k;
}

struct node
{
	int x, y;
	friend bool operator <(const node& a, const node& b)
	{ return a.y < b.y; }
}P[maxn];

void Push_Down(int p)
{
	if(!mark[p]) return;
	mark[p << 1] += mark[p], mark[p << 1 | 1] += mark[p];
	mx[p << 1] += mark[p], mx[p << 1 | 1] += mark[p];
	mark[p] = 0;
}

void Update(int p, int l, int r, int L, int R, int x)
{
	if(L > R) return;
	if(L <= l && R >= r)
	{
		mark[p] += x, mx[p] += x;
		return;
	}
	if(L > r || R < l) return;
	Push_Down(p);
	int mid = (l + r) >> 1;
	Update(p << 1, l, mid, L, R, x); Update(p << 1 | 1, mid + 1, r, L, R, x);
	mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
}

int Query(int p, int l, int r, int L, int R)
{
	if(L <= l && R >= r) return mx[p];
	if(L > r || R < l) return 0;
	int mid = (l + r) >> 1; Push_Down(p);
	return max(Query(p << 1, l, mid, L, R), Query(p << 1 | 1, mid + 1, r, L, R));
}

void Work()
{
	memset(mx, 0, sizeof(mx)); memset(mark, 0, sizeof(mark));
	top = top2 = 0; int mid = W >> 1; 
	for(int i = 1; i <= n; i ++)
	{
		if(i > 1) ans = max(ans, (P[i].y + Query(1, 1, n, 1, i - 1)) * 2);
		Update(1, 1, n, i, i, W - P[i].y);
		if(P[i].x <= mid)
		{
			int last = 0, rec = i;
			while(top && P[S[top]].x <= P[i].x)
			{
				Update(1, 1, n, S[top], rec - 1, -(P[i].x - last));
				last = P[S[top]].x, rec = S[top]; top --;	
			}
			Update(1, 1, n, S[top], rec - 1, -(P[i].x - last));
			S[++ top] = i;
		}
		else
		{
			int last = W, rec = i;
			while(top2 && P[S2[top2]].x >= P[i].x)
			{
				Update(1, 1, n, S2[top2], rec - 1, P[i].x - last);
				last = P[S2[top2]].x, rec = S2[top2], top2 --;	
			}
			Update(1, 1, n, S2[top2], rec - 1, P[i].x - last);
			S2[++ top2] = i;
		}
	}
}

int main()
{
	W = read(), H = read(), n = read();
	int X1 = 0, Y1 = 0, X2 = INF, Y2 = INF;
	for(int i = 1; i <= n; i ++) P[i].x = read(), P[i].y = read();
	for(int i = 1; i <= n; i ++)
	{
		X1 = max(X1, P[i].x), Y1 = max(Y1, P[i].y);
		X2 = min(X2, P[i].x), Y2 = min(Y2, P[i].y);
	}
	if(X2 && Y2) P[++ n].x = 0, P[++ n].y = 0;
	if(X1 != W && Y1 != H) P[++ n].x = W, P[++ n].y = H;
	ans = max(ans, (H + max(X2, (W - X1))) * 2);
	ans = max(ans, (W + max(Y2, (H - Y1))) * 2);
	sort(P + 1, P + 1 + n); Work();
	for(int i = 1; i <= n; i ++) swap(P[i].x, P[i].y);
	swap(W, H); sort(P + 1, P + 1 + n); Work();
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 20736
#include<bits/stdc++.h>
#include<iomanip>
#include<numeric>

using namespace std;
using ll = long long;
constexpr int mo = 1e9+7;
constexpr int  mod = mo;
constexpr int inf = 1<<30;
int main(){
    int n,a,b;
    cin>>n>>a>>b;
    cout << min(b,a*n) << endl;
    return 0;
}



Measured memory_bytes: 764
indexes = readlines.map { |l|
  w, p = l.chomp.split
  [w, p.to_i]
}

indexes_table = Hash.new { |h, k| h[k] = [] }
indexes.each { |w, p| indexes_table[w] << p }
indexes_table.keys.sort.each do |i|
  puts "#{i}\n#{indexes_table[i].sort.join(' ')}"
end

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

const int INF = 1e9;

vector<int> divisor(int n) {
  vector<int> v;
  for (int i = 1; i * i <= n; ++i) {
    if (n % i == 0) {
      v.push_back(i);
      v.push_back(n / i);
    }
  }
  return v;
}

int n, k;
int main() {
  cin >> n >> k;
  vector<int> v = divisor(k);
  
  int mx = 0;
  for (int a : v) {
    if ((long)n * a <= k) {
      mx = max(mx, a);
    }
  }
  cout << mx << endl;
}


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

int main(){
  long A,B,C,K,n=0;
  cin >> A >> B >> C >> K;
  if(A>=K){
    n += K;
  }else if(A+B>=K){
    n += A;
  }else{
    n += 2*A-K+B;
  }
  cout << n << endl;
}

Measured memory_bytes: 3644
#include <cstdio>
using namespace std;
int main(){
  int A,B;
  scanf("%d %d",&A,&B);
  if(A%3==0) printf("Possible\n");
  else if(B%3==0) printf("Possible\n");
  else if((A+B)%3==0) printf("Possible\n");
  else printf("Impossible\n");
  return 0;
}


Measured memory_bytes: 128
/*input
3 21
1 2 3
*/
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define mpr make_pair
#define MX 1000000007
#define ui unsigned int
#define ll long long
#define ld long double
#define fi first
#define se second
#define testcases int testcases;cin>>testcases;while(testcases--)
#define printvector(v) for(int i=0;i<v.size();i++) cout<<v[i]<<" ";  cout<<endl
#define printarray(v,n)  for(int i=0;i<n;i++) cout<<v[i]<<" ";  cout<<endl
#define inputarray(v,n)  for(int i=0;i<n;i++)cin>>v[i]
#define debug(i) cout<<"debug: "<<i<<endl
#define pr(i) cout<<i<<endl
#define timetaken cerr<<clock()/double(CLOCKS_PER_SEC)<<endl
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll powmod(ll base,ll exp,ll MOD){ll res=1;while(exp>0){if(exp%2==1) res=(res*base)%MOD;base=(base*base)%MOD;exp/=2;}return (res%MOD);}
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }


// class graph{
//     unordered_map<int,vector<int>> adjList;
//     int n;
// public:
//     graph(int n){
//         this->n = n;
//     }
//     void addEdge(int a, int b){
//         adjList[a].pb(b);
//     }
    
//     int dfs(int from, vector<int>&dp){
//         if(dp[from] != -1)return dp[from];
//         int mx = 0;
//         for(auto to : adjList[from]){
//             mx = max(mx, dfs(to,dp));
//         }
//         return dp[from] = 1 + mx;
//     }
// };

int dp[1000000];

bool cal(vector<int> &a, int n, int k){
    if(dp[k] != -1) return dp[k];

    bool ans = 1;
    for(int i=0;i<n;++i){
        if(k>=a[i])
            ans &= cal(a,n,k-a[i]);
    }

    return dp[k] = !ans;
}

int main() {
    fast_io
    int n,k;
    cin>>n>>k;
    vector<int>a(n); inputarray(a,n);
    memset(dp,-1,sizeof(dp));
    int mn = INT_MAX;
    for(int i=0;i<n;++i) mn = min(mn,a[i]);

    for(int i=0;i<mn;++i)dp[i] = 0;
    
    bool ans = cal(a,n,k);
    if(ans)pr("First");
    else pr("Second");

}

Measured memory_bytes: 10368
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cstdlib>
#include <typeinfo>

using namespace std;

#define FOR(i,n) for(i=0;i<n;++i)


int i,j;

int main(void){
    
    int a,b,c;
    cin >> a >> b >> c;
    
    FOR(i,100000000){
        
        //cout<<(a*i)%b<<" ";
        
        if((a*i)%b==c){
            cout<<"YES";
            return 0;
        }
    }
    
    cout<<"NO";
    return 0;
    
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		in.close();

		int div = 1;
		while ( div < 10 ) {
			int rem = n % div;
			int quo = n / div;
			if ( rem == 0 && quo < 10 ) {
				System.out.println("Yes");
				return;
			} else {
				div++;
			}
		}
		System.out.println("No");
	}
}


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

#define rep(i,n) for(ll i=0;i<n;i++)
#define repm(i,m,n) for(ll i=m;i<n;i++)
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define YesNo(a) (a)?cout<<"Yes"<<endl:cout<<"No"<<endl
#define YESNO(a) (a)?cout<<"YES"<<endl:cout<<"NO"<<endl
#define INF (2e9)
#define PI (acos(-1))
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007

typedef long long ll;

int main(){
  int x; cin >> x;

  int ans = 0;

  ans += (x/500)*1000;
  x %= 500;
  ans += (x/5)*5;

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define vec vector
#define rep(i,n) for (int i=0; i<(n); i++)
#define reps(i,s,n) for (int i=(s); i<(n); i++)
#define rep1(i,n) for (int i=1; i<=(n); i++)
#define repr(i,s,n) for (int i=(s)-1; i>=(n); i--)
#define print(a) cout << a << endl
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()


template<typename Monoid>
struct Seg {
  //Binary-op that merges the elements of two sub-arrays
  using F = function<Monoid(Monoid, Monoid)>;
  int sz;
  vector<Monoid> seg;
  const F f;
  const Monoid M1; // identity element of monoid
  Seg(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz<n) sz <<= 1;
    seg.assign(2*sz, M1);
  }
  void set(int k, const Monoid &x) {
    seg[k+sz] = x;
  }
  void build() {
    for(int k=sz-1; k>0; k--) {
      seg[k] = f(seg[2*k], seg[2*k+1]);
    }
  }
  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k>>=1) {
      seg[k] = f(seg[2*k], seg[2*k+1]);
    }
  }
  // f[a,b)
  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }
  Monoid operator[](const int &k) const {
    return seg[k+sz];
  }
  template< typename C >
  int find_subtree(int a, const C &check, Monoid &M, bool type) {
    while(a<sz) {
      Monoid nxt = type ? f(seg[2*a+type], M) : f(M, seg[2*a+type]);
      if(check(nxt)) a = 2*a+type;
      else M = nxt, a = 2*a+1-type;
    }
    return a - sz;
  }
  //return a first element-num of x that satisfy check in [a,x)
  template< typename C >
  int find_first(int a, const C &check) {
    Monoid L = M1;
    if(a <= 0) {
      if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
      return -1;
    }
    int b = sz;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) {
        Monoid nxt = f(L, seg[a]);
        if(check(nxt)) return find_subtree(a, check, L, false);
        L = nxt;
        ++a;
      }
    }
    return -1;
  }
  //return a last element-num of x that satisfy check in [x,b)
  template< typename C >
  int find_last(int b, const C &check) {
    Monoid R = M1;
    if(b >= sz) {
      if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
      return -1;
    }
    int a = sz;
    for(b += sz; a < b; a >>= 1, b >>= 1) {
      if(b & 1) {
        Monoid nxt = f(seg[--b], R);
        if(check(nxt)) return find_subtree(b, check, R, true);
        R = nxt;
      }
    }
    return -1;
  }
};


int main() {
  string S,T;
  cin >> S >> T;
  int slen = S.size(),tlen = T.size();
  function<int(int,int)> f = [&](int a,int b){ return (a+b)%3; };
  Seg<int> s(slen,f,0),t(tlen,f,0);
  rep(i,slen) {
    s.set(i,(S[i] == 'A')?1:2);
  }
  rep(i,tlen) {
    t.set(i,(T[i] == 'A')?1:2);
  }
  s.build();
  t.build();
  int Q;
  cin >> Q;
  rep(i,Q) {
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    a--; c--;
    print(((s.query(a,b) == t.query(c,d))?"YES":"NO"));
  }
  return 0;
}

Measured memory_bytes: 5616
n = int(input())
tp = 0
hp = 0
for i in range(n):
    tarou, hanako = map(str,input().split())
    if(tarou > hanako):
        tp += 3
    elif(tarou < hanako):
        hp += 3
    else:
        tp += 1
        hp += 1
print("%d %d" %(tp,hp))


Measured memory_bytes: 5600
#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 5000 + 5 ;
int n, q, d[N], sum[N], pre[N], c[N] ; 
signed main()
{
	n = gi(), q = gi() ;
	rep( i, 1, n ) d[i - 1] = gi() ; 
	while( q-- ) {
		int l = gi(), x = gi(), M = gi() ;
		int Ans = 0, sum = 0, ans = 0 ; x %= M ;
		for( re int i = 0; i < n; ++ i ) {
			c[i] = d[i] % M, sum += c[i] ; 
			if( c[i] != 0 ) ++ ans ;
		}
		int mt = ( l - 1 ) / n ;
		int sumx = ( x + mt * sum ) ;
		Ans = ans * mt - ( sumx / M ) ;
		sumx %= M ; 
		for( re int i = 0; i < ( l - 1 ) % n; ++ i ) {
			sumx += c[i] ; 
			if( c[i] != 0 ) ++ Ans ; 
			if( sumx >= M ) sumx -= M, -- Ans ;
		}
		cout << Ans << endl ;
	}
	return 0 ;
}


Measured memory_bytes: 764
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n ; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;

int main(void){
    int tree, d; cin >> tree >> d;
    cout << (tree - 1) / (d * 2 + 1) + 1 << endl;
}

Measured memory_bytes: 256
def Mmul(a, b):  # 行列の積
    # [ｍ×ｎ型][ｎ×ｐ型]
    m = len(a)
    n = len(a[0])
    if len(b) != n:
        raise ValueError('列と行の数が一致しません')
    p = len(b[0])
    ans = [[0]*p for _ in range(m)]
    for i in range(m):
        for j in range(p):
            for k in range(n):
                ans[i][j] += a[i][k]*b[k][j] % MOD
    return ans


def Mfactorial(n, p):  # n^p 繰り返し二乗法+行列の積
    if (p == 1):
        return n
    if (p % 2 == 0):
        t = Mfactorial(n, p // 2)
        return Mmul(t, t)
    return Mmul(Mfactorial(n, p - 1), n)


n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
MOD = 10**9+7
print(sum([sum(i) % MOD for i in Mfactorial(a, k)]) % MOD)


Measured memory_bytes: 69084
from math import gcd


def lgcd(x: list):
    res = x[0]
    for i in range(1, len(x)):
        res = gcd(res, x[i])

    return res


n, k = map(int, input().split())
a = list(map(int, input().split()))

m = max(a)
g = lgcd(a)

print(["IMPOSSIBLE", "POSSIBLE"][int(k % g == 0 and k <= m)])


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

using namespace std;


int main() {
    int N; cin >> N;
    long long int ans = 0ll;
    vector<long long int> A(N+1);
    for(auto& a : A) cin >> a;

    long long int b;
    for(int i=0;i<N;i++) {
        cin >> b;
        if(A[i] < b) {
            ans += A[i];
            b -= A[i];
        } else {
            ans += b;
            b = 0ll;
        }

        if(A[i+1] < b) {
            ans += A[i+1];
            A[i+1] = 0ll;
        } else {
            ans += b;
            A[i+1] -= b;
        }
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
/*......................*/
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double   ld;

//#include <ext/pb_ds/assoc_container.hpp>   
//#include <ext/pb_ds/tree_policy.hpp>  
//#include <functional> 
//using namespace __gnu_pbds;  
//typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> OST;           //unique elements  

#define    f(i,j,n)                 for(int i = j; i <= n; i++)
#define    r(i,n,j)                 for(int i = n; i >= j; i--)
#define    mod                      1000000007
#define    speed                    ios_base::sync_with_stdio(false);
#define    upp                       cin.tie(NULL);
#define    pb                       push_back
#define    mp                       make_pair
#define    T                        int t; cin >> t; while(t--)
#define    ff                       first
#define    ss                       second
#define    all(container)           container.begin() , container.end()
#define    sz(container)            (int)container.size()
#define    pii                      pair <int , int>
#define    pll                      pair <long long int , long long int>
#define    ook(x)                   order_of_key(x)
#define    fbo(x)                   find_by_order(x)

multiset <ll> ms;
ll arr[100005];
int ans = 0 , n;

int main(){                                       //constraints , long long
     speed upp
     cin >> n;
     f(i,1,n){
         cin >> arr[i];
     }
     r(i,n,1){
         ll x = arr[i];
         auto it = ms.upper_bound(x);
         if(it == ms.end()){
             ans++;
             ms.insert(x);
         }
         else{
             ms.erase(it); 
             ms.insert(x);
         }
     }
     cout << ans << '\n';
}

Measured memory_bytes: 5760
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
struct mint {
    int x;
    mint(int x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(int t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    mint inv() const {
        return pow(mod - 2);
    }
    mint& operator/=(const mint a) {
        return *this *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};
mint dp[1010][1010];
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W;
    cin >> H >> W;
    string S[1010];
    rep(i, H) cin >> S[i];
    dp[0][0] = 1;
    rep(i, H) {
        rep(j, W) {
            if(j + 1 < W && S[i][j + 1] != '#') dp[i][j + 1] += dp[i][j];
            if(i + 1 < H && S[i + 1][j] != '#') dp[i + 1][j] += dp[i][j];
        }
    }
    cout << dp[H - 1][W - 1].x << endl;

    return 0;
}


Measured memory_bytes: 12652
#include <stdio.h>
#define MAX 1000000007
int main(void){
    // Your code here!
    
    long int step[100001];
    long int N;
    long int i;
    long int max,tmp;
    
    scanf("%ld",&N);
    max = 0;
    tmp = 0;
    
    for(i=1;N>=i;i++){
        scanf("%ld",&step[i]);
        if(i!=1){
            if(step[i-1]>=step[i]){
                tmp++;
            }
            else{
                tmp = 0;
            }
            if(tmp>=max) max = tmp;

        }
    }
    
    printf("%ld\n",max);
    return 0;
}


Measured memory_bytes: 1024
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef map<char,int> mci;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<pair<int,int>> vii;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define in insert
#define sz(v) v.size()
#define mina(a,b) (a)=min((a),(b));
#define maxa(a,b) (a)=max((a),(b));
const ll INF = 1e18 + 5;

void solve(){
    int n; cin>>n;
    vi v(n),ans(n);
    for(int i = 0; i < n; i++) cin>>v[i];
    for(int i = 0; i < n; i++){
        if(i%2) ans[0]-=v[i];
        else ans[0]+=v[i];
    }
    v[0]-=ans[0]/2;
    v[n-1]-=ans[0]/2;
    for(int i = 1; i < n; i++){
        ans[i]=v[i-1]*2;
        v[i]-=v[i-1];
    }
    for(int it:ans) cout<<it<<" ";
}
int main(){
    int T=1;        //! COMMENT IF THERE IS NO TEST CASES
    //cin>>T;
    for(int i = 0; i < T; i++) solve(); 
}

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

mint f(int n) {
  if (n == 0) return 1;
  mint x = f(n/2);
  x *= x;
  if (n%2 == 1) x *= 2;
  return x;
}

mint choose(int n, int a) {
  mint x = 1, y = 1;
  rep(i,a) {
    x *= n-i;
    y *= i+1;
  }
  return x / y;
}

int main() {
  int n, a, b;
  cin >> n >> a >> b;
  mint ans = f(n);
  ans -= 1;
  ans -= choose(n,a);
  ans -= choose(n,b);
  cout << ans.x << endl;
  return 0;
}


Measured memory_bytes: 3624
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
from collections import defaultdict
def resolve():
    N,=pin()
    a=defaultdict(int)

    for i in range(N):
        temp=input()
        a[temp]+=1

    t=a["AC"]+a["WA"]+a["TLE"]+a["RE"]
    #print(a)
    assert t==N
    print("AC x",a["AC"])
    print("WA x",a["WA"])
    print("TLE x",a["TLE"])
    print("RE x",a["RE"])    
#%%submit!
resolve()


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

#define ONLINE_JUDGE
#define pb(a) push_back(a)
#define ALL(a) a.begin(), a.end()
#define FOR(x,to) for(x=0;x<(to);x++)

using ll = long long;

const int E5 = 1e5;

//////////// Solution /////////////////////////////////

void solve() {	
	int c[3][3];
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> c[i][j];
		}
	}

	int a[3],b[3];
	for (a[0] = 0; a[0] <= 100; ++a[0]) {
		for (a[1] = 0; a[1] <= 100; ++a[1]) {
			for (a[2] = 0; a[2] <= 100; ++a[2]) {
				bool ok = true;
				for (int j = 0; j < 3; ++j) {
					b[j] = c[0][j] - a[0];
				}
				for (int i = 0; i < 3; ++i) {
					for (int j = 0; j < 3; ++j) {
						if (c[i][j] != a[i] + b[j]) {
							ok = false;
						}
					}
				}
				if (ok) {
					cout << "Yes\n";
					return;
				}
			}
		}
	}

	cout << "No\n";
}	

/////////// End Solution ///////////////////////////////////////

//////// Initialization ////////////////////////////////////

int main() {

	#ifndef ONLINE_JUDGE
	FILE *FIN = freopen("/home/danil/prog/input.txt", "r", stdin);
	clock_t time_start = clock();
	#endif

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	solve();

	#ifndef ONLINE_JUDGE
	fclose(FIN);
	cerr << "\x1b[031m\n-----------------\nTime=" << (ll)((double)(clock()-time_start) / CLOCKS_PER_SEC * 1000) << "ms\n\x1b[0m";
	#endif

	return 0;
}

//////// End Initialization ///////////////////////////////////////

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define MOD 1000000007;

using namespace std;
using namespace __gnu_pbds;
//typedef tree<TYPE, null_type, less<TYPE>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//typedef tree<TYPE, null_type, less_equal<TYPE>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;

int n, arr[200001];

int main(){
	//IO("input.txt", "output.txt");
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> arr[i];
	int k = 1, cnt = 0;
	for(int i = 1; i <= n; i++, k++)
		if(arr[i] != k) k--, cnt++;
	if(cnt == n) cout << "-1\n";
	else cout << cnt << "\n";
 	return 0;
}

Measured memory_bytes: 1024
S = input()

if S == 'SUN':
  result = 7
elif S == 'MON':
  result = 6
elif S == 'TUE':
  result = 5
elif S == 'WED':
  result = 4
elif S == 'THU':
  result = 3
elif S == 'FRI':
  result = 2
elif S == 'SAT':
  result = 1

print(result)

Measured memory_bytes: 2940
import itertools
url = "https://atcoder.jp//contests/abc057/tasks/abc057_a"

def main():
    k, s = list(map(int, input().split()))
    count = 0
    for x, y in itertools.product(range(k+1), range(k+1)):
        z = s - x - y
        if 0 <= z <= k:
            count += 1
    print(count)


if __name__ == '__main__':
    main()

Measured memory_bytes: 9272