akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int INF = 987654321;
const int MOD = 1000000007;
//const long double PI = (acos(-1));
//const long double EPS = 0.0000000001;

const int MAX_N = 100;
int n, k;

int combi(int a, int b) {
	if(a < b) return 0;
	if(a == b || b == 0) return 1;
	return combi(a-1,b-1) + combi(a-1,b);
}

int main(void) {
	ios_base::sync_with_stdio(false); 
	cin.tie(0); 
	cout.tie(0);
	//freopen("in.txt", "r", stdin);
	cin >> n >> k;
	int limit = n-2 + combi(n-2,2);
	if(limit < k) {
		cout << -1 << endl;
		return 0;
	}
	int m = n-1;
	vector<pii> edge;
	edge.pb(mp(0,1));
	rep(i,2,n) {
		edge.pb(mp(1,i));
	}

	int cnt = limit - k;
	int here = 0;
	while(cnt) {
		if(here == 0) {
			int limit = min(cnt, n-2);
			for(int i=2; i<2+limit; ++i) {
				edge.pb(mp(0,i));
			}
			cnt -= limit;
			m += limit;
			here = 2;
			continue;
		}

		int limit = min(cnt, n-1-here);
		for(int i=here+1; i<here+1+limit; ++i) {
			edge.pb(mp(here, i));
		}
		cnt -= limit;
		m += limit;
		here++;
	}

	cout << m << endl;
	rep(i,0,sz(edge)) {
		cout << edge[i].F+1 << ' ' << edge[i].S+1 << '\n';
	}
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main() {
  char s[3];
  int flg=0, count=0, idx=0;
  string msg1 =": not in range <error>";
  cin >> s;
  if( strlen(s) != 3 ){ cout << "length" + msg1  << endl;flg=1;}
  if( s[0] !='0' && s[0] !='1') { cout << "s1" + msg1  << endl;flg=1;}
  if( s[1] !='0' && s[1] !='1') { cout << "s2" + msg1  << endl;flg=1;}
  if( s[2] !='0' && s[2] !='1') { cout << "s3" + msg1  << endl; flg=1;}
  if(flg) return 1;
  for( idx=0; idx < 3; idx++) if( s[idx]=='1' ) count++;
  cout << count << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        
        if(a < b && b < c){
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


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

using namespace std;

#define vt          vector
#define sz(x)       int((x).size())
#define all(x)      (x).begin(), (x).end()
#define rall(x)     (x).rbegin(), (x).rend()
#define fi          first
#define se          second

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

template <class T, class OP>
struct SegTree {
    OP op;
    T id;
    int n;
    vt<T> a;

    SegTree(vt<T> _a, OP _op, T _id = 0) :
            op(_op), id(_id), 
            n(1 << __lg(sz(_a) * 2 - 1)), a(n * 2) {
        copy(all(_a), a.begin() + n);
        for (int i = n - 1; i; i--)
            a[i] = op(a[i * 2], a[i * 2 + 1]);
    }

    T query(int l, int r) {
        T ret = id;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
            if (l & 1) ret = op(ret, a[l++]);
            if (r & 1) ret = op(ret, a[--r]);
        }
        return ret;
    }

    void update(int i, T u) {
        a[i += n] = u;
        for (i /= 2; i; i /= 2)
            a[i] = op(a[i * 2], a[i * 2 + 1]);
    }
};

const int maxn = 3e5 + 1;

auto f = [](int x, int y) {
        return max(x, y);
};

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

    SegTree<int, decltype(f)> st(vt<int>(maxn), f);

    int ans = 0;
    while (n--) {
        int x;
        cin >> x;
        int res = st.query(max(0, x - k), min(x + k, maxn)) + 1;
        ans = max(ans, res);
        st.update(x, res);
    }
    cout << ans;
}

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

    int tcs = 1;
    for (int tc = 1; tc <= tcs; tc++) {
        // cout << "Case " << tc << ": ";
        solve();
    }
}



Measured memory_bytes: 8476
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void){

    int N;

    scanf("%d", &N);

    int T[N+1];
    int sum = 0;

    for(int i = 1; i <= N; i++){
        scanf("%d", &T[i]);
        sum += T[i];
    }

    int M;

    scanf("%d", &M);

    int P[M+1], X[M+1];

    for(int i = 1; i <= M; i++){
        scanf("%d%d", &P[i], &X[i]);
    }

    for(int i = 1; i <= M; i++){
        printf("%d\n", sum + (X[i] - T[P[i]]));
    }

    return 0;
}

Measured memory_bytes: 1672
#include <iostream>

int main(){
    int n;
    std::cin >> n;

    int t = 0, h = 0;
    std::string str1, str2;
    for(int i = 0; i < n; ++i){
        std::cin >> str1 >> str2;
        if(str1 < str2){
            h += 3;
        }else if(str1 == str2){
            ++t;
            ++h;
        }else{
            t += 3;
        }
    }

    std::cout << t << " " << h << std::endl;
    
    return 0;
}


Measured memory_bytes: 3212
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ls( s) (s&(-s))
#define ll long long
#define inf 0x3f3f3f3f
const ll N = 500030;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =    1e9+7;
int arr[N][2];
map<pair<int,int>,int >mp;
int n,k,l;
int find(int z,int par)
{
	if(arr[z][par]!=z)
	arr[z][par]=find(arr[z][par],par);
	return arr[z][par];
}
void Union(int x,int y,int par)
{
	int a=find(x,par);
int b=find(y,par);
	if(a!=b)
	arr[a][par]=b;
}
int main()
{
		ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
   cin>>n>>k>>l;
   rep(i,1,n+1)
   {
   	arr[i][0]=i;
   	arr[i][1]=i;
   }
   rep(i,0,k)
   {
   	int x,y;
   	cin>>x>>y;
   	Union(x,y,0);
   }
   rep(i,0,l)
   {
   	int x,y;
   	cin>>x>>y;
   	Union(x,y,1);
   }
  rep(i,1,n+1)
  {
  	mp[{find(i,0),find(i,1)}]++;
  }
  rep(i,1,n+1)
  cout<<mp[{find(i,0),find(i,1)}]<<" ";
}

Measured memory_bytes: 13568
import java.util.*;

public class Main {
    public static int maxCandies(int a[][], int i, int j, int sum) {
        if(i >= 2 || j >= a[0].length) {
            return 0;
        }
        if(i == 1 && j == a[0].length - 1)
            return a[i][j];
        sum += Math.max(a[i][j] + maxCandies(a, i+1, j, sum), a[i][j] + maxCandies(a, i, j+1, sum));
        return sum;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int a[][] = new int[2][n];
        for(int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++)
                a[i][j] = in.nextInt();
        }
        System.out.println(maxCandies(a, 0, 0, 0));
        in.close();
    }

}

Measured memory_bytes: 21972
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<queue>
#include<map>
#include<cstring>
#include<functional>

using namespace std;

int main()
{
	//freopen("input.txt", "r", stdin);

	int d, s, t;

	scanf("%d %d %d", &d, &t, &s);

	if (s*t >= d)
	{
		printf("Yes\n");
	}

	else
	{
		printf("No\n");
	}

	return 0;
}

Measured memory_bytes: 1664
x,y=map(int,input().split())
g1=[1,3,5,7,8,10,12]
g2=[4,6,9,11]
g3=[2]
s=[x,y]

if (len(set(g1)-set(s))==(len(g1)-len(s)))or(len(set(g2)-set(s))==(len(g2)-len(s)))or(len(set(g3)-set(s))==(len(g3)-len(s))):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 38256
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define int ll
using namespace std;
using ll=long long;
using pii=pair<int,int>;

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n,k; cin>>n>>k;
	long double ans=0;
	cout<<fixed<<setprecision(15);
	For(i,1,n)
	{
		long double t=log10((double)k/(double)i)/log10(2);
		//cout<<t<<"\n";
		t=pow(0.5,max((long double)0,ceil(t)))/n;
		ans+=t;
	}
	cout<<ans<<"\n";
	return 0;
}















Measured memory_bytes: 768
N, M = [int(_) for _ in input().split()]
P = [0] + [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


def same(x, y):
    return find(x) == find(y)


for x, y in XY:
    unite(x, y)

ans = 0
for i in range(1, N + 1):
    if same(i, P[i]):
        ans += 1
print(ans)


Measured memory_bytes: 31384
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pb push_back
#define mk make_pair
#define f first
#define s second
#define MOD 1000000007

int main()
{  
  ll n;
  cin>>n;
  ll x[n+1][4]={0};
  for(ll i=1;i<=n;i++)
    cin>>x[i][1]>>x[i][2]>>x[i][3];
  ll dp[n+1][4]={0};
  //ll vis[n+1]={0};
   dp[1][1]=x[1][1];
   dp[1][2]=x[1][2];
   dp[1][3]=x[1][3];
  for(ll i=2;i<=n;i++)
  {
       //ll t1=max(dp[i-1][1],max(dp[i-1][2],dp[i-1][3]));
       dp[i][1]=x[i][1]+max(dp[i-1][2],dp[i-1][3]);
       //dp[i][1]=max(dp[i][1],dp[i-1][1]);
       dp[i][2]=x[i][2]+max(dp[i-1][1],dp[i-1][3]);
       //dp[i][2]=max(dp[i][2],dp[i-1][2]);
       dp[i][3]=x[i][3]+max(dp[i-1][2],dp[i-1][1]);
       //dp[i][3]=max(dp[i][3],dp[i-1][3]);

  }
  cout<<max(dp[n][1],max(dp[n][2],dp[n][3]));
  
   

 }
  
              
              

  

  
  
          
      
    







  
 

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

const int MAX_N = 2e5 + 10, MOD = 1e9 + 7;

int c[MAX_N];

int64_t anses[MAX_N];

int res[MAX_N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> c[i];
	int64_t ans = 1;
	for (int i = 0; i < n; ++i) {
		res[i] = ans;
		if (c[i] == c[i + 1])
			continue;
		ans += anses[c[i]];
		ans %= MOD;
		anses[c[i]] += res[i],
		anses[c[i]] %= MOD;
		res[i] = ans;
	}
	cout << ans % MOD << "\n";
	return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <queue>
#include <map>
#include <list>
#include <vector>
#include <string>
#include <stack>
#include <limits>
#include <cassert>
#include <fstream>
#include <cstring>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <ciso646>
#include <set>
#include <array>

using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

#define inf 0x3f3f3f3f
#define INF INT_MAX/3
#define PB push_back
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define SET(a,c) memset(a,c,sizeof a)
#define CLR(a) memset(a,0,sizeof a)
#define pii pair<int,int>
#define pcc pair<char,char>
#define pic pair<int,char>
#define pci pair<char,int>
#define VS vector<string>
#define VI vector<int>
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
#define pi 2*acos(0.0)
#define INFILE() freopen("in0.txt","r",stdin)
#define OUTFILE()freopen("out0.txt","w",stdout)
#define ll long long
#define ull unsigned long long
#define eps 1e-14
#define FST first
#define SEC second
#define SETUP cin.tie(0), ios::sync_with_stdio(false), cout << setprecision(15)

namespace {
	struct input_returnner {
		int N; input_returnner(int N_ = 0) :N(N_) {}
		template<typename T> operator vector<T>() const { vector<T> res(N); for (auto &a : res) cin >> a; return std::move(res); }
		template<typename T> operator T() const { T res; cin >> res; return res; }
		template<typename T> T operator - (T right) { return T(input_returnner()) - right; }
		template<typename T> T operator + (T right) { return T(input_returnner()) + right; }
		template<typename T> T operator * (T right) { return T(input_returnner()) * right; }
		template<typename T> T operator / (T right) { return T(input_returnner()) / right; }
		template<typename T> T operator << (T right) { return T(input_returnner()) << right; }
		template<typename T> T operator >> (T right) { return T(input_returnner()) >> right; }
	};
	template<typename T> input_returnner in() { return in<T>(); }
	input_returnner in() { return input_returnner(); }
	input_returnner in(int N) { return std::move(input_returnner(N)); }
}

void solve();
/// ---template---
signed main(void) {
	SETUP;
	solve();
	return 0;
}

struct Point {
	int x;
	int y;
	Point(int x_, int y_):x(x_),y(y_){}
	Point() {}
};

bool operator < (list<Point> left, list<Point> right) {
	return left.size() < right.size();
}

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

void solve() {
	string S = in();
	ll K = in();

	REP(i, S.size()) {
		if (K <= 0) break;
		ll cost = 'z' - S[i] + 1;
		cost %= ('z' - 'a' + 1);
		if (K - cost >= 0) {
			S[i] = 'a';
			K -= cost;
		}
	}

	if(K > 0) K %= ('z' - 'a' + 1);
	RFOR(i,0,S.size()) {
		if (K <= 0) break;
		ll cost = min((ll)K, (ll)('z' - S[i]));
		S[i] += cost;
		K -= cost;
	}
	cout << S << endl;
}

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

std::bitset<2000010> lty;

int main() {
	int n;
	int tot = 0;
	scanf("%d", &n);
	lty[0] = 1;
	for (int i = 1; i <= n; i++) {
		int tmp;
		scanf("%d", &tmp);
		lty |= lty << tmp;
		tot += tmp;
	}
	
	for (int i = (tot + 1) / 2; i <= tot; i++) {
		if (lty[i]) {
			printf("%d\n", i);
			exit(0);
		}
	}
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
using namespace std;
ll a[200005];
ll n,k;
ll ans=inf;
bool check(ll m)
{
    ll tot=0;
    for(int i=0; i<n; i++)
    {
        tot=tot+(a[i]%m==0?(a[i]/m):(a[i]/m+1))-1;
    }
    if(tot<=k)
        return true;
    else
        return false;
}
ll bound(ll l,ll r)
{
    if(l==r||l+1==r)
    {
        if(check(l))
            ans=min(ans,l);
        if(check(r))
            ans=min(ans,r);
        return ans;
    }
    ll mid=(l+r)>>1;
    if(check(mid))
    {
        ans=min(ans,mid);
        return bound(l,mid);
    }
    else
        return bound(mid+1,r);
}
int main()
{
    cin>>n>>k;
    for(int i=0; i<n; i++)
        cin>>a[i];
    cout<<bound(1,1e9)<<endl;
    return 0;
}


Measured memory_bytes: 5168
#include<stdio.h>
#include<stdlib.h>
int main(){
    char a[11], b[11], c[11], ans;
    int i;

    scanf("%s %s %s", a, b, c);

    for(i = 0; a[i] != '\0'; i++);
    if(a[i - 1] != b[0]){
        printf("NO");
        exit(0);
    }
    for(i = 0; b[i] != '\0'; i++);
    if(b[i - 1] != c[0]){
        printf("NO");
        exit(0);
    }
    printf("YES");
    return 0;
}

Measured memory_bytes: 128
K = [str(input()) for _ in range(5)]

L = []

for k in K:
    if int(k[-1]) == 0:
        pass
    else:
        L.append(int(k[-1]))

K_int = [int(k) for k in K]

if len(L) == 0:
    ans = sum(K_int)
else:
    ans = sum(K_int) + len(L)*10 -sum(L) - (10 - min(L))

print(ans)

Measured memory_bytes: 3060
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <tuple>

#define DEBUG(x) cout<<#x<<": "<<x<<endl

using namespace std;

int main(){

	int A, B, C;

	cin >> A >> B >> C;
	
	if((A - C) * ( B - C) <= 0 ){
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
def main():
  n=int(input())
  ab=[list(map(int,input().split())) for _ in range(n-1)]
  g=[[] for _ in range(n)]
  for i,abi in enumerate(ab):
    a,b=abi
    g[b-1].append([a-1,i])
    g[a-1].append([b-1,i])
  seen=[-1]*(n-1)
  todo=[[0,-1]]
  while len(todo)>0:
    a,ca=todo.pop()
    l=g[a]
    c=0
    for li in l:
      if seen[li[1]]==-1:
        c+=1 if c+1!=ca else 2
        seen[li[1]]=c
        todo.append([li[0],c])
  print(max(seen))
  for s in seen:
    print(s)
if __name__=='__main__':
  main()


Measured memory_bytes: 64160
#include<stdio.h>
int main()
{
	int n,s,i;
	while(scanf("%d",&n),n)
	{
		for(s=-n,i=1;i*i<=n;++i)if(n%i==0)if(i*i-n)s+=i+n/i;else s+=i;
		puts(n==s?"perfect number":(n<s?"abundant number":"deficient number"));
	}
	return 0;
}

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

int main () {
  int N;
  cin >> N;
  int ANS=0;
  vector<int> B(N);
  
  for(int i=0; i<N-1; i++){
    cin >> B[i];
  }
  
  for(int i=0; i<N-2; i++){
  ANS += min(B.at(i),B.at(i+1));
  }
  
  
  ANS += B[0];
  ANS += B[N-2];
  
  cout << ANS << endl;
}


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

typedef long long ll;

int main(void){
    ll n;
    cin >> n;
    vector<ll> c(n-1), s(n-1), f(n-1);
    for(ll i=0; i<n-1; i++){
        cin >> c.at(i) >> s.at(i) >> f.at(i);
    }
    for(ll i=0; i<n; i++){
        ll p = i, t = 0;
        while(p < n-1){
            if(t <= s.at(p)){
                t = s.at(p) + c.at(p);
            }else{
                t += (f.at(p) - t%f.at(p))%f.at(p) + c.at(p);
            }
            p++;
        }
        cout << t << endl;
    }

    return 0;
}

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

n, t = map(int, input().split())
dish = [tuple(map(int, input().split())) for _ in range(n)]
dish.sort()
# print(*dish, sep='\n')

dp = [[0] * (t + 1) for _ in range(n + 1)]
for i in range(n):
    for t0 in range(t):
        dp[i + 1][t0] = dp[i][t0]
    for t0 in range(t):
        t1 = min(t0 + dish[i][0], t)
        dp[i + 1][t1] = max(dp[i + 1][t1], dp[i][t1], dp[i][t0] + dish[i][1])

ans = max(dp[n])
# print(*dp, sep='\n')
# print([dp[i][-1] for i in range(n + 1)])
print(ans)


Measured memory_bytes: 114396
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define pb push_back
#define ll long long
#define ae addEdge
#define mp make_pair
#define vi vector<int>
#define vll vector<long long>
#define si set<int>
#define vvi vector< vector<int> >
#define pii pair <int,int>
#define sortv sort(v.begin(),v.end())
#define sorta sort(a.begin(),a.end())
#define sortb sort(b.begin(),b.end())
#define sorts sort(s.begin(),s.end())

int main(){
	int n; cin>>n;
	int v[n][3];
	int a,b,c;
	for(int i=0;i<n;i++){
		//cin>>a>>b>>c;
		cin>>v[i][0]>>v[i][1]>>v[i][2];
	}
	int dp[n][3];
	dp[0][0]=v[0][0]; dp[0][1]=v[0][1]; dp[0][2]=v[0][2];
	for(int i=1;i<n;i++){
		dp[i][0]=max(dp[i-1][1]+v[i][0],dp[i-1][2]+v[i][0]);
		dp[i][1]=max(dp[i-1][0]+v[i][1],dp[i-1][2]+v[i][1]);
		dp[i][2]=max(dp[i-1][1]+v[i][2],dp[i-1][0]+v[i][2]);
	}
	cout << max( dp[n-1][0], max(dp[n-1][1],dp[n-1][2])) << endl;
}

Measured memory_bytes: 2560
def main():
	
	from collections import deque
	n,m = map(int,input().split())
	l = [list(map(int, input().split())) for i in range(m)]
	graph = [[] for _ in range(n+1)]
	
	for i in range(m):
		a,b = l[i]
		graph[a].append(b)
		graph[b].append(a)

	dist = [-1] * (n+1)
	dist[0] = 0
	dist[1] = 0

	d = deque()
	d.append(1)

	while d:
		v = d.popleft()
		for i in graph[v]:
			if dist[i] != -1:
				continue
			dist[i] = dist[v] + 1
			d.append(i)

	if graph[1] == '':
		print("No")
	else:
		print("Yes")
		for i in range(2,n+1):
			if dist[i] == 1:
				print(1)
			else:
				for room in range(len(graph[i])):
					if dist[i]-1 == dist[graph[i][room]]:
						print(graph[i][room])
						break
	


if __name__ == '__main__':
	main()

Measured memory_bytes: 125496
#include <cstdio>
#include <utility>
#include <cctype>
#include <vector>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std;

#ifdef __linux
#define _U(s) s##_unlocked
#else
#define _U(s) _##s##_nolock
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#define gcu _U(getchar)
#define pcu _U(putchar)
#define _DEF(r, n, ...) inline r n(__VA_ARGS__) noexcept
#define _T template <typename T>
#define _HT template <typename H,typename... T>
#define _OP(t) inline operator t()
struct _in {
#ifdef _GLIBCXX_STRING
	_OP(string){string s;char c;while(isspace(c = gcu()));do{s+=c;}while(c=gcu(),c!=' '&&c!='\n'&&c!=EOF);return s;}
#define _S
#endif
	_OP(char){char c=gcu();gcu();return c;}
	_OP(double){double d; scanf("%lf",&d); gcu();return d;}
	_T _OP(T){T n{},m{1},c;while(isspace(c = gcu()));if(c=='-')m=-1,c=gcu();do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m*n;}
} in;
#define _SCAN(...) _DEF(bool,scan,__VA_ARGS__)
#ifdef _S
_SCAN(string &o) {int c{gcu()};if(c==EOF)return false;else{ungetc(c,stdin);string t=move(in);o=t;return true;}}
#endif
_T _SCAN(T &o) {int c{gcu()};return c==EOF?false:(ungetc(c,stdin),o=in,true);}
_HT _SCAN(H &h,T&&... t){return scan(h)&&scan(t...);}
#define _OUT(...) _DEF(void,out,__VA_ARGS__)
#define _OUTL(...) _DEF(void,outl,__VA_ARGS__)
_OUT(bool b){pcu('0'+b);}
_OUT(const char *s){while(*s)pcu(*s++);}
_OUT(char c){pcu(c);}
#ifdef _S
_OUT(string &s){for(char c:s)pcu(c);}
#endif
_T _OUT(T n){static char b[20];char *p=b;T m=n<0?pcu('-'),-1:1;
	if(!n)*p++='0';else while(n)*p++=(char)(n%10*m+'0'),n/=10;while(p!=b)pcu(*--p);}
_OUTL(){out('\n');}
#ifdef _GLIBCXX_VECTOR
	_T _OUT(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);}
#endif
	_HT _OUT(H &&h, T... t){out(h);out(t...);}
	template <typename... T> _OUTL(T... t){out(t...);outl();}
	struct range{
		int e,b=0,s=1;range(int _b,int _e,int _s):e(_e),b(_b),s(_s){} range(int _b,int _e): e(_e), b(_b){} range(int _e):e(_e){}
		struct it{int v,s; it(int _v,int _s):v(_v),s(_s){} operator int()const{return v;} operator int&(){return v;}int operator*()const{return v;}
			it& operator++(){v+=s;return *this;} }; it begin(){return {b,s};} it end(){return {e,s};}};
#define times(i,n) for(int i=n;i;i--)

template <typename T>
using V = vector<T>;

int main() {
	int v {in}, e {in};
	V<V<int>> g(v, V<int>());
	times(i, e) {
		int s {in};
		g[s].push_back(in);
	}

	V<int> ids(v, -1), low(v, -1);
	function<void(int)> dfs = [&] (int a) {
		static int id = 0;
		static stack<int> s;
		static V<bool> on(v);
		s.push(a);
		on[a] = true;
		ids[a] = low[a] = id++;
		for (int t: g[a]) {
			if (ids[t] == -1)
				dfs(t);
			if (on[t])
				low[a] = min(low[a], low[t]);
		}
		int n;
		if (ids[a] == low[a])
			do {
				n = s.top();
				s.pop();
				on[n] = false;
				low[n] = ids[a];
			} while (n != a);
	};
	for (int i: range(v))
		if (ids[i] == -1)
			dfs(i);
	times(i, in)
		outl(low[in] == low[in]);
}


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

struct edge{int u, v, cost;};

#define MAX_N 100001
#define MAX_E 100001

int par[MAX_N];
int rank[MAX_N];
edge es[MAX_E];
int V, E;

int kruskal();
void init(int n);
int find(int x);
void unite(int x, int y);
bool same(int x, int y);
bool comp(const edge& e1, const edge& e2);

int main()
{
    cin >> V;
    while (V) {
        cin >> E;
        for (int i = 0; i < E; i++) {
            scanf("%d,%d,%d", &es[i].u, &es[i].v, &es[i].cost);
        }
        cout << kruskal() << endl;
        cin >> V;
    }

    return 0;
}


int kruskal()
{
    sort(es, es + E, comp);
    init(V);
    int res = 0;
    for (int i = 0; i < E; i++) {
        edge e = es[i];
        if (!same(e.u, e.v)) {
            unite(e.u, e.v);
            if (e.cost < 100) {
                res += 1;
            } else {
                res += (e.cost-1) / 100;
            }
        }
    }
    return res;
}

void init(int n) 
{
    for (int i = 0; i < n; i++) {
        par[i] =  i;
        rank[i] = 0;
    }
}

int find(int x)
{
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y) 
{
    x = find(x);
    y = find(y);
    if (x == y) {
        return ;
    }

    if (rank[x] < rank[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (rank[x] == rank[y]) {
            rank[x]++;
        }
    }
}

bool same(int x, int y) 
{
    return find(x) == find(y);
}

bool comp(const edge& e1, const edge& e2)
{
    return e1.cost < e2.cost;
}

Measured memory_bytes: 3304
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <tuple>
#include <queue>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#ifdef _DEBUG_
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl
#else
#define dump(val)
#endif

using namespace std;

typedef long long int ll;
typedef tuple<int, ll> Edge;

template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}
template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m, x;
    cin >> n >> m >> x;
    vector<ll> H(n);
    REP(i, 0, n) {
        cin >> H[i];
    }
    vector<vector<Edge>> G(n);
    REP(i, 0, m) {
        int a, b, t;
        cin >> a >> b >> t;
        a--;
        b--;
        if (H[a] >= t) {
            G[a].emplace_back(b, t);
        }
        if (H[b] >= t) {
            G[b].emplace_back(a, t);
        }
    }
    // to, cost, height
    using Data = tuple<int, ll, ll>;
    auto cmp = [](Data &d1, Data &d2) {
        ll a, b;
        tie(ignore, a, ignore) = d1;
        tie(ignore, b, ignore) = d2;
        return a > b;
    };
    priority_queue<Data,vector<Data>, decltype(cmp)> pq(cmp);
    pq.emplace(0, 0, x);
    const ll inf = 1LL << 60;
    vector<ll> Cost(n, inf);
    Cost[0] = 0;
    while (pq.size()) {
        int to;
        ll cost, height;
        tie(to, cost, height) = pq.top();
        pq.pop();
        if (Cost[to] < cost) continue;
        for (auto &e: G[to]) {
            int nxt;
            ll dist;
            tie(nxt, dist) = e;
            ll nheight = 0;
            if (height - dist >= H[nxt]) {
                dist += height - dist - H[nxt];
                nheight = H[nxt];
            } else if (height - dist <= 0) {
                nheight = 0;
                dist += dist - height;
            } else {
                nheight = height - dist;
            }
            if (nxt == n - 1) {
                dist += H[n - 1] - nheight; 
            }
            if (dist + cost < Cost[nxt]) {
                Cost[nxt] = dist + cost;
                pq.emplace(nxt, Cost[nxt], nheight);
            }
        }
    }
    cout << (Cost[n - 1] == inf ? -1 : Cost[n - 1]) << endl;
    return 0;
}



Measured memory_bytes: 21440
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f(i,x,n) for(int i=x;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=200005,INF=1<<30;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    while(1){
        int N,L,R;cin>>N>>L>>R;
        if(N+L+R==0) break;
        
        vector<int> A(N);
        for(int i=0;i<N;i++) cin>>A[i];
        int ans=0;
        
        for(int i=L;i<=R;i++){
            for(int j=0;j<N;j++){
                if(i%A[j]==0){
                    if(j%2==0) ans++;
                    break;
                }
                if(j==N-1&&N%2==0) ans++;
            }
        }
        
        cout<<ans<<endl;
    }
}



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

void solve(long long N, std::vector<long long> L){
    sort(L.begin(),L.end());
    ll ans =0;
    for(int i=0;i<N;i++)for(int j=i+1;j<N;j++)for(int k=j+1;k<N;k++){
        if(L[i] + L[j] > L[k] && (L[i] != L[j]) && (L[j] != L[k]) && (L[k] != L[i])){
            ans++;
        }
    }
    cout << ans << endl;

}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> L(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&L[i]);
    }
    solve(N, std::move(L));
    return 0;
}


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

#define FLASH ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define MAX 1e9
#define MIN -1e9
#define mod 1000000007
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define output(x) cout << ( x ? "YES" : "NO" ) << '\n' ;
#define mxn 100005
using namespace std;

void solve(){
    string s;
    cin >> s;
    int cnt = 0;
    for(int i = 0; i < 3; i++)
        if(s[i] == 'R')cnt++;
        else if(cnt > 0)break;
    cout << cnt;
}

int main()
{
    FLASH
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}



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

int main()
{
	int r,c,max,i,j,x,count=0,countAll=0;
	vector<int> v;

	cin >> r >> c ;

	max = r*c;

	for(i=0;i<max;i++)
	{
		cin >> x ;
		v.push_back(x);
	}

	for(i=0;i<max;i++)
	{
		cout << v[i] << ' ' ;
		count += v[i] ; 

		if(((i+1)%c)==0)
		{
			cout << count << endl ;
			countAll += count;
			count = 0;
		}
	}

	for(i=0;i<c;i++)
	{
		for(j=0;j<r;j++)
		{
			count += v[i+(c*j)];
		}

		cout << count << ' ' ;
		countAll += count ;
		count=0;
	}

	countAll = countAll / 2 ;

	cout << countAll << endl;

	return 0;
}

Measured memory_bytes: 1324
l = [[[0]*10 for _ in range(3)]for _ in range(4)]
for _ in range(int(input())):
    b,f,r,v = map(int,input().split())
    l[b-1][f-1][r-1] += v
for i in range(4):
    for j in range(3):
        print(" " + " ".join(map(str,l[i][j])))
    if i != 3:
        print("#"*20)


Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long a, b, c, k, i;
    cin >> a >> b >> c >> k;
    for(i=0;i<k;i++){
        if(b<=a) b*=2;
        else if(c<=b) c*=2;
    }
    if(b>a && c>b) cout << "Yes" <<endl;
    else cout << "No" <<endl;
    return 0;
}



Measured memory_bytes: 3616
#include <stdio.h>

int main(void)
{
	int w;
	int h;
	int x;
	int y;
	int r;
	
	scanf("%d %d %d %d %d", &w, &h, &x, &y, &r);
	
	if (((x - r) >= 0) && ((y - r) >= 0) && ((x + r) <= w) && ((y + r) <= h)){
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	
	return (0);
}

Measured memory_bytes: 584
import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        long k = sc.nextInt();
        long a = sc.nextInt();
        long b = sc.nextInt();
        long d = b-a;

        long r1 = 1 + k;

        long r2 = 0;
        if (a-1 <= k) {
            r2 = a;
            k -= (a-1);
            r2 = a + (k/2*d) + (k%2);
        }

        System.out.println(Math.max(r1, r2));

    }

}


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

int main(){
    string ans = "No";

    int x, y;
    cin >> x >> y;
    for (int i = 0; i <= x; ++i){
        int head2 = i;
        int head4 = x - head2;
        //cout << head2 << " " << head4 << endl;

        int legs = head4*4 + head2*2;
        if (legs==y){
            ans = "Yes";
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3628
/*
    @uthor: Amit Kumar
    user: CodeChef: dr_virus_ ; Codeforces,Hackerearth,Hakerrank: dr_virus;
*/
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;
//#define ln mp::cpp_int;
#define ll long long
#define ld double
#define pp pair<ll,ll>
#define endl "\n"
#define nfrep(a) for(size_t i=0;i<a;i++)
#define fnrep(a,b) for(size_t i=a;i<=b;i++)
#define nbrep(a) for(size_t i=a;i>=0;i--)
#define bnrep(a,b) for(size_t i=a;i>=b;i--)
 
const ll mod = 1e9+7;
const ll inf = 1e18;
 
 
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
 /* #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif */
 ll n,m,sum=0;
  cin>>n>>m;
  
  for(auto i=0;i<m;i++){
  ll t;
  cin>>t;
  sum+=t;
  }
  if(sum<=n) cout<<n-sum;
  else cout<<"-1";
  //cerr<<"Time Elapsed: "<<clock()/(double)CLOCKS_PER_SEC<<endl;
    return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k,t[ohara];
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>n>>c>>k;
    rep(i,n)cin>>t[i];
    sort(t,t+n);
    ll basnin,ti;
    basnin=1;
    ans=1;
    ti=t[0]+k;
    rrep(i,1,n){
        if(basnin==c||t[i]>ti){
            ans++;
            basnin=1;
            ti=t[i]+k;
        }
        else{
        if(t[i]<=ti){
            basnin++;
        }
        }
    }
    Cout(ans);
    return 0;
}


Measured memory_bytes: 1024
import java.util.*;
import java.io.*;
import java.math.*;
class Main{
	static int mod = (int)1e9+7;
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	public static void main(String sp[])throws IOException{
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		int k = sc.nextInt();
		int arr[] = new int[n+3];
		for(int i=1;i<=n;i++)
			arr[i]=sc.nextInt();
		int dp[] = new int[n+3];
		Arrays.fill(dp,Integer.MAX_VALUE);
		dp[1]=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=k;j++){
				if(i+j>n)
					continue;
				int y = arr[i+j]-arr[i];
				if(y<0)
					y*=-1;
				dp[i+j]=(Math.min(dp[i+j],(dp[i]+y)));
			}
		}
		System.out.println(dp[n]);
	}
	
	
	
	public static class pair{
		long a;
		long b;
	}
	
	public static class comp implements Comparator<pair>{
		public int compare(pair o1, pair o2){
			return Long.valueOf(o2.a-o2.b).compareTo(Long.valueOf(o1.a-o1.b));
		}
	}
	
	
	
	public static long sum(long a, long d, long n){
		
		long total = ((n)*((2*a)+(n-1)*d))/2;
		return total;
	}
	
	public static class trie{
		char ch;
		HashMap<Character,trie> hm = new HashMap<>();
		int count;
		boolean isterminal;
	}
	
	
	public static int partition(int [] arr, int s, int e){
		
		int index=s;
		int pivot = arr[e];
		for(int i=s;i<=e-1;i++){
			if(arr[i]<=pivot){
				arr = swap(arr, index, i);
				index++;
			}
		}
		swap(arr,index,e);
		print(arr);
		return index;
	}
	
	public static int[] swap(int[] arr, int low, int high){
		int temp = arr[low];
		arr[low]=arr[high];
		arr[high]=temp;
		return arr;
	}
	
	
	public static long gcd(long a, long b){
		if(a==0)
			return b;
		
		return gcd(b%a,a);
	}
	
	public static void print(int[] arr){
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
		System.out.println();
	}
	
 
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
	
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return st.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
}

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

namespace MINPRO2019A
{
    class Program
    {
        static void Main(string[] args)
        {
            var nk = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = nk[0];
            int K = nk[1];

            if (N > 2 * (K - 1))
                Console.WriteLine("YES");
            else Console.WriteLine("NO");

            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 13268
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <functional>

using namespace std;
typedef long long int ll;

#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define rrep(i,a) for(ll i=a-1;i>=0;i--)

int main(){
  ll A, B;
  cin >> A;
  cin >> B;

  ll ans;
  if (A>B) ans = 2 * A - 1;
  else if (A<B) ans = 2 * B - 1;
  else ans = A * 2;

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


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

using namespace std;

#define FaSt ios::sync_with_stdio(0),cin.tie(0);
#define random uniform_int_distribution<long long>(1, 2000000000000000LL)(rng)

const int N = 21 + 3, K = (1 << 21) + 3, M = 1e9 + 7;
int n, a[N][N];
long long dp[N][K];
bool solved[N][K];

long long calc(int i, int k)
{
    if (i == n)
    {
        if (__builtin_popcount(k) == n)
        {
            return 1;
        }
        return 0;
    }
    
    if (solved[i][k])
    {
        return dp[i][k];
    }
    
    for (int j = 0; j < n; j++)
    {
        if (a[i][j] == 1 && (((k >> j) & 1) == 0))
        {
            dp[i][k] += calc(i + 1, k | (1 << j));
            dp[i][k] %= M;
        }
    }
    
    solved[i][k] = 1;
    return dp[i][k];
}

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


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

int main() {
    string S,T;
    bool judge = false;
    cin >>S>>T;
    for(int i=0;i<S.size();i++){
        if(S==T){
            judge = true;
            break;
        }
        S =S.back()+S.substr(0,S.size()-1);
    }
    if(judge)cout<<"Yes"<<endl;
    else cout <<"No"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll mod = 1e9+7;
const int N=2e5+9;
int main()
{
    FASTINOUT;
    char a;
    cin>>a;
    if (a=='A')
        cout<<'T';
    else if (a=='T')
        cout<<'A';
    else if (a=='G')
        cout<<'C';
    else
        cout<<'G';
    return 0;
}


Measured memory_bytes: 256
gengo = {
    "meiji"   => 18680908..19120729,
    "taisho"  => 19120730..19261224,
    "showa"   => 19261225..19890107,
    "heisei"  => 19890108..99999999,
}

while gets
    y, m, d = $_.split
    date = sprintf("%4d%02d%02d\n", y, m, d).to_i
    puts "pre-meiji" unless gengo.any? do |g, range|
        if range === date
            gy = date / 10000 - range.min / 10000 + 1
            puts "#{g} #{gy} #{m} #{d}"
            break true
        end
    end
end

Measured memory_bytes: 8572
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int MOD = 1000003;

int pot[MOD + 5], z, x, d, n, licz, mian, r;

// rozwiązuje równanie ax=1(%MOD), gdy MOD pierwsze
int inverse(int a, int n = MOD - 2) {
	int r = 1;
	while (n) {
		if (n % 2) r = (r * 1LL * a) % MOD;
		a = (a * 1LL * a) % MOD;
		n >>= 1;
	}
	return r;
}

// (a^b)%c
int poteguj (int a, int b, int c = MOD) {
	int r = 1, m = a;
	while (b) {
      	if (b % 2) r = (r * 1LL * m) % c;
      	m = (m * 1LL * m) % c;
      	b /= 2;
	}
	return r;
}

int main() {
pot[0] = 1;
for (int i=1;i<MOD;i++) pot[i] = (pot[i - 1] * 1LL * i) % MOD;
scanf("%d", &z);
while (z--) {
	scanf("%d %d %d", &x, &d, &n);
	if (x == 0 || d == 0) {
		printf("%d\n", poteguj(x, n));
		continue;
	} else if (d == 1) {		
		if (x + n - 1 >= MOD) printf("0\n"); else {
			r = (pot[x + n - 1] * 1LL * inverse(pot[x - 1])) % MOD;
			printf("%d\n", r);
		}
		continue;
	} else {
		licz = (x * 1LL * inverse(d)) % MOD + n - 1;
		mian = (x * 1LL * inverse(d)) % MOD - 1;
		if (licz >= MOD) printf("0\n"); else {
			r = (pot[licz] * 1LL * inverse(pot[mian])) % MOD;
			r = (r * 1LL * poteguj(d, n)) % MOD;
			printf("%d\n", r);
		}
	}
}
}


Measured memory_bytes: 4736
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int n = in.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = in.nextInt();
		System.out.println(solve(a));
		in.close();
	}

	private static int solve(int[] a) {
		int r = 0;
		for (int i = 0; i < a.length; i++)
			for (; a[i] % 2 == 0; a[i] /= 2)
				r++;
		return r;
	}
}

Measured memory_bytes: 33760
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <algorithm>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long> vl;

#define ten(n) (1e##n)
#define COUT cout <<
#define SPACE_COUT << " "  <<
#define COMMA_COUT << ", " <<
#define ENDL << endl;

int
main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long x, y;
    cin >> x >> y;
    ll absx = abs(x);
    ll absy = abs(y);
    ll total = 0;
    if (x == 0) {
      total = absy + (y < 0 ? 1 : 0);
    } else if (absy >= absx) {
      total = absy - absx;
      if (x < 0)
	total += 1;
      if (y < 0)
	total += 1;
    } else if (absy < absx) {
      total = absx - absy;
      if (y > 0)
	total += 1;
      if (x > 0)
	total += 1;
    }    
    cout << total << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define Rep(i,n,m) for(int i = (int)(n);i < (int)(m);i++)
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl 

int main()
{
    int N;
    cin >> N;
    int count = 0;
    int g = 0;
    Rep(i,1,N+1)
    {
        g = 0;
        Rep(j,1,N+1)
        {
            if(i % j == 0)
            {
                g++;
            }
        }
        if(g == 8 && i % 2 == 1)
        {
            count++;
        }
    }
    cout << count << endl;

}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

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

const long long INF = 1LL << 60;

#define rep(i, e) for(int i = 0; i < e; i++)
#define repp(i, s, e) for(int i = s; i < e; i++)
#define N_Max 100
#define Card_Max 36
#define p(a) printf("%d\n", a);
#define ll long long
#define MAX 100005
#define NIL -1

int main() {
    int n;
    double ans = 0;
    cin >> n;
    if(n % 2 == 1) {
        ans = (double)(n / 2 + 1) / n;
    } else {
        ans = (double)(n / 2) / n;
    }
    printf("%.10lf\n", ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pb push_back
#define ub upper_bound
#define lb upper_bound
#define mp make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define ve vector
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
 
typedef long long ll;
const ll INF = LLONG_MAX - 100;
const ll mod = 1e9 + 7;
const int MAX_N = 2e5 + 5;
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
vector<ll> prime;
 
int fac[MAX_N], inv[MAX_N];
 
template <class T = ll> T in() {T x; cin >> x; return (x);}
void DEBUG(vector<int> a) {for(int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;}
ll GCD(ll a, ll b) {ll c; while (b != 0) {c = a % b; a = b; b = c;}return a;}
ll LCM(ll a, ll b) {return a * b / GCD(a, b);}
ll POW(ll a, ll b, bool usemod = true) {ll c = 1LL; while (b > 0) {if (b & 1LL) {if(!usemod)c*=a;else c = a * c%mod;}if (!usemod) a*=a;else a = a * a%mod; b >>= 1LL;}return c;}
void _nCr() {fac[0] = 1LL; for (int i = 1LL; i < MAX_N; i++) {fac[i] = fac[i - 1LL] * i%mod;}for (int i = 0; i < MAX_N; i++) {inv[i] = POW(fac[i], mod - 2);}}
ll nCr(ll n, ll r) {return (fac[n] * inv[r] % mod)*inv[n - r] % mod;}
void PRI(ll n) {bool a[n + 1LL]; for (int i = 0; i < n + 1LL; i++) {a[i] = 1LL;}for (int i = 2; i < n + 1LL; i++) {if (a[i]) {prime.pb(i); ll b = i; while (b <= n) {a[b] = 0; b += i;}}}}
template <typename T> T chmin(T& a, T b) {if(a>b)a=b;return a;}
template <typename T> T chmax(T& a, T b) {if(a<b)a=b;return b;}

bool solve() {
	int n; cin >> n;
	vp A(n);
	REP (i,n) cin >> A[i].S >> A[i].F;
	sort(ALL(A));
	int cur = 0;
	bool ok = true;
	REP (i,n) {
		// DEBUG({i,cur});
		if (cur+A[i].S > A[i].F) ok = false;
		cur += A[i].S;
	}
	if (ok) cout << "Yes" << endl;
	else cout << "No" << endl;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
}

Measured memory_bytes: 3456
N, M, X = map(int,input().split())
A = [[int(x) for x in input().split()] for _ in range(N)]

INF = float('inf')
ans = INF

for i in range(2**N):
    tmp = [0 for _ in range(M+1)]
    b = bin(i)[2:].zfill(N)
    
    for n in range(N):
        for m in range(M+1):
            tmp[m] += A[n][m] * int(b[N-1-n])

    if min(tmp[1:]) >= X:
        ans = min(ans, tmp[0])

if ans == INF:
    ans = -1
print(ans)

Measured memory_bytes: 68744
#define _USE_MATH_DEFINES
#include <iostream>
#include <complex>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <cmath>
#include <math.h>
#include <numeric>
#include <list>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <set>
#include <memory.h>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <map>
#include <cassert>
#include <time.h>

using namespace std;

typedef complex<double> xy_t;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int , P> PP;
typedef pair<int, string> Ps;
typedef vector<int> vec;
typedef vector<vec> mat;
const int INF= 1 << 30;
const double EPS = 1e-9;
const double PI = 3.1415926535897932384626433832795;

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

int main(){
	double a, b;
	while(cin >> a >> b){
		if(a < 35.50 && b < 71.0){
			cout << "AAA" << endl;
		}else if(a < 37.50 && b < 77.00){
			cout << "AA" << endl;
		}else if(a < 40.00 && b < 83.00){
			cout << "A" << endl;
		}else if(a < 43.00 && b < 89.00){
			cout << "B" << endl;
		}else if(a < 50.00 && b < 105.00){
			cout << "C" << endl;
		}else if(a < 55.00 && b < 116.0){
			cout << "D" << endl;
		}else if(a < 70.0 && b < 148.0){
			cout << "E" << endl;
		}else {
			cout << "NA" << endl;
		}
	}
	return 0;
}
	

Measured memory_bytes: 0