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

struct Node {
  int key;
  Node *prev,*next;
};

Node *nil;

void init() {
  nil = (Node *)malloc(sizeof(Node));
  nil->prev = nil;
  nil->next = nil;
}

void insert(int key) {
  Node *x = (Node *)malloc(sizeof(Node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

Node* listSearch(int key) {
  Node *cur = nil->next;
  while(cur != nil && cur->key != key) {
    cur = cur->next;
  }
  return cur;
}

void deleteNode(Node *t) {
  if(t == nil) return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void deleteFirst() {
  deleteNode(nil->next);
}

void deleteLast() {
  deleteNode(nil->prev);
}

void deleteKey(int key) {
  deleteNode(listSearch(key));
}

void printList() {
  Node *cur = nil->next;
  int isf = 0;
  while(1) {
    if(cur == nil) break;
    if(isf++ > 0) printf(" "); 
    printf("%d",cur->key);
    cur = cur->next;
  }
  printf("\n");
}


int main() {
  int n,key;
  cin >> n;
  char com[20];
  init();

  for(int i = 0; i < n; i++) {
    scanf("%s%d",com,&key);
    if(com[0] == 'i') {
      insert(key);
    }else {
      if(strlen(com) > 6) {
        if(com[6] == 'F') deleteFirst();
        else if(com[6] == 'L') deleteLast();
      }else {
        deleteKey(key);
      }
    }
  }

  printList();

}


Measured memory_bytes: 34468
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using P = pair<int, int>;
const long long INF = 100000000000;
typedef long long ll;
typedef vector<vector<ll>> Matrix;
Matrix dist; // グラフの距離を格納した2次元配列（隣接行列）
             // d[u][v]は辺e=(u,v)のコスト（辺が存在しない場合はINF、ただしd[i][i]=0）

//ワーシャルフロイド法
void warshall_floyd(int n){                                 // nは頂点数
  for (int i = 0; i < n; i++)     // 経由する頂点
    for (int j = 0; j < n; j++)   // 開始頂点
      for (int k = 0; k < n; k++) // 終端
        dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
}

int main() {
  int h, w;
  cin >> h >> w;
  ll ans = 0;
  dist = Matrix(10, vector<ll>(10));
  rep(i,10){
    rep(j,10){
      cin >> dist[i][j];
    }
  }
  warshall_floyd(10);
  rep(i,h){
    rep(j,w){
      int num;
      cin >> num;
      if(num == 1 || num == -1) continue;
      ans += dist[num][1];
    }
  }
  cout << ans << endl;
}

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

int main(void){

    int h, w, n;
    cin >> h >> w >> n;
    int m = max(h, w);
    int s = min(h, w);
    int cnt = 0, sum = 0;
    for (int i = 0; i < s;i++){
        sum = m * i;
        if(sum<n)
            cnt++;
        else
            break;
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair

using namespace std;
int n,m;
char ara[500][500];
int vis[500][500];

typedef pair<int,int> pp;

int fx[]={1,-1,0,0};
int fy[]={0,0,1,-1};

bool issafe(int x,int y){
    return ( x>0 && x<=n && y>0 && y<=m   );
}

void bfs(int s1,int s2){
    queue<pair<pp,int> >myq;
    myq.push(mp(mp(s1,s2),1));
    vis[s1][s2]=1;
    while(!myq.empty()){
        int x=myq.front().xx.xx;
        int y=myq.front().xx.yy;
        int d=myq.front().yy;
        myq.pop();
        for(int i=0;i<4;i++){
            int p=x+fx[i];
            int q=y+fy[i];
            if(issafe(p,q)){
                if(ara[p][q]!='#' && vis[p][q]==0){
                    vis[p][q]=vis[x][y]+1;
                    myq.push(mp(mp(p,q),vis[p][q]));
                }
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    int pr1,pr2,s3,s4;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ara[i][j];
            if(ara[i][j]=='%'){
                pr1=i,pr2=j;
            }
            if(ara[i][j]=='@'){
                s3=i;
                s4=j;
            }
        }
    }

    bfs(pr1,pr2);
    int val=vis[s3][s4];
    bool flag=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ara[i][j]=='$'){
                if(vis[i][j]<=val){
                    flag=1;
                }
            }
        }
    }
    if(flag)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

Measured memory_bytes: 3676
#import random,time

H=int(input())
#P=[i for i in range(2**(H-1))]
#random.shuffle(P)
P=list(map(lambda x:int(x)-1,input().split()))
mod=10**9+7
inv=pow(2,mod-2,mod)

L=2**(H-1)

base_t=[1 for i in range(1+1<<H)]
base_t[0]=0
for i in range(2,1+1<<H):
    base_t[i]=i*base_t[i>>1]
    base_t[i]%=mod

base_s=[(i*pow(base_t[i]**2,mod-2,mod))%mod for i in range(1+1<<H)]

ans=0
def solve(i):
    global ans
    if i>=L:
        i-=L
        val=(base_t[i+L]*base_t[P[i]+L])%mod
        val2=pow(val,2,mod)
        id=P[i]+L
        res=[[(P[i]+L)>>(H-1-j),val,val2] for j in range(H)]
        return res
    L1=solve(2*i)
    L2=solve(2*i+1)
    Li,ttt=merge(L1,L2)
    ttt=(ttt*(base_s[i]-base_s[i>>1]))%mod
    ans=(ans+ttt)%mod
    return Li

def merge(L1,L2):
    res=[]
    L1.append([10**18,0])
    L2.append([10**18,0])
    L1=L1[::-1]
    L2=L2[::-1]
    ttt=0
    if L1[-1][0]<=L2[-1][0]:
        res.append(L1.pop())
    else:
        res.append(L2.pop())
    while L1 and L2:
        if L1[-1][0]<=L2[-1][0]:
            if res and res[-1][0]==L1[-1][0]:
                res[-1][1]+=L1[-1][1]
                res[-1][1]%=mod
                res[-1][2]+=L1[-1][2]
                res[-1][2]%=mod
                L1.pop()
            else:
                j,val,val2=res[-1]
                tmp=(base_s[j]-base_s[j>>1]) %mod
                c=val**2 %mod
                c=(c-val2)%mod
                tmp =(tmp*c) %mod
                ttt=(ttt+tmp)%mod
                res.append(L1.pop())
        else:
            if res and res[-1][0]==L2[-1][0]:
                res[-1][1]+=L2[-1][1]
                res[-1][1]%=mod
                res[-1][2]+=L2[-1][2]
                res[-1][2]%=mod
                L2.pop()
            else:
                j,val,val2=res[-1]
                tmp=(base_s[j]-base_s[j>>1]) %mod
                c=val**2 %mod
                c=(c-val2)%mod
                tmp =(tmp*c) %mod
                ttt=(ttt+tmp)%mod
                res.append(L2.pop())
    res.pop()
    return res,ttt

solve(1)

print(ans*inv %mod)


Measured memory_bytes: 234960
s=input()
t=input()
l=len(s)
m=len(t)
L=[]
for i in range(l-m+1):
    if all([s[i+j]=='?' or s[i+j]==t[j] for j in range(m)]):
        L.append(i)
if L:
    k=max(L)
    print((s[:k]+t+s[k+m:]).replace('?','a'))
else:
    print('UNRESTORABLE')

Measured memory_bytes: 3064
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N;
    static int[] b;

    private static void init() {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        b = new int[N - 1];
        for(int i = 0; i < N - 1; i++) {
            b[i] = scanner.nextInt();
        }
        scanner.close();
    }


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

        ArrayList<Integer> l = new ArrayList<>();
        l.add(b[0]);
        l.add(b[N - 2]);

        int min = Integer.MAX_VALUE;
        for(int i = 1; i < N - 1; i++) {
            min = Math.min(b[i], b[i - 1]);
            l.add(min);
        }

        int ans = 0;
        for(int i: l) {
            ans += i;
        }
        System.out.println(ans);
    }
}


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

using namespace std;

using LL = unsigned long long;

const double EPS = 1e-12;

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

	double sum = 0;
	LL mult = 1;

	for(int i = 0; i < N; ++i) {
		LL x; cin >> x;

		if (x == 0) {
			cout << 0 << '\n';
			return 0;
		}

		sum += log10(x);
		mult *= x;

	}

	//cout << fixed << setprecision(10) << sum << '\n';

	if (sum <= 18.00000000 && mult <= (LL) 1e18)
		cout << mult << '\n';
	else cout << -1 << '\n'; 

	return 0;	
}

Measured memory_bytes: 3952
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <random>
#include <chrono>

using namespace std;
using namespace __gnu_pbds;

#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;
//typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	
	int n;
	cin >> n;
	
	vector<ll> v(n + 1);
	
	for(int i = 1; i <= n; i++)
		cin >> v[i];
	
	vector<ll> L(n + 5), R(n + 5);
	
	for(int i = 1; i <= n; i++)
		L[i] = __gcd(L[i - 1], v[i]);
	
	for(int i = n; i >= 1; i--)
		R[i] = __gcd(R[i + 1], v[i]);
	
	ll ans = L[n];
	
	for(int i = 1; i <= n; i++)
		ans = max(ans, __gcd(L[i - 1], R[i + 1]));
	
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <list>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)

int main(){
    while(1){
        int m,f,r;
        cin >> m >> f >> r;
        if(m==-1 && f==-1 && r==-1) return 0;
        if(m==-1 || f==-1) cout << 'F' << endl;
        else if(m+f>=80) cout << 'A' << endl;
        else if(m+f>=65) cout << 'B' << endl;
        else if(m+f>=50) cout << 'C' << endl;
        else if(m+f>=30 && r>=50) cout << 'C' << endl;
        else if(m+f>=30) cout << 'D' << endl;
        else cout << 'F' << endl;
    }
}


Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,num=0;
    cin>>n;
    for(int i=3;i<=55555;i++)
    {
        int flag=0;
        for(int j=2;j<=sqrt(i);j++)
        {
            if(i%j==0)
                flag=1;
        }
        int t=i-3;
        if(flag==0&&(t%3==0||t%5==0||t%15==0))
        {
            printf("%d ",i );
            num++;
        }
       if(num==n)
            return 0;
    }
    return 0;
}


Measured memory_bytes: 256
import math

n, h = map(int, input().split())
k = [tuple(map(int, input().split())) for i in range(n)]
k.sort(reverse=True)
mm = k[0][0]


def main():
    c = 0
    count = 0
    for a, b in sorted(k, reverse=True, key=lambda x:(x[1],x[0])):
        if b < mm:
            break
        count += 1
        c += b
        if h <= c:
            print(count)
            return
    print(count + math.ceil((h - c) / mm))


main()


Measured memory_bytes: 25500
import Control.Applicative
import Control.Monad
import Data.List
import Data.Char
strToInt s = (read :: String -> Int) s
strToInteger s = (read :: String -> Integer) s
strToDouble s = (read :: String -> Double) s

main :: IO ()
main = do
    -- スペース区切り整数の入力
    [x, a, b] <- map strToInt . words <$> getLine
    -- 出力
    putStrLn $ if abs (x-a) < abs (x-b) then "A" else "B"


Measured memory_bytes: 508
import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.Scanner;
 
public class Main {
 
	public static final MyScanner in = new MyScanner();
 
	public static void main(String[] args) {
 
		int K = in.nextInt();


		int i = 0;
		long answer = 0; 

		for(long all=1;i<K;) {
			Optional<Long> next = isRunRun(all);
			if(next.isPresent()) {
				all = next.get();
			} else {
				i++;
				answer = all;
				all++;
			}
		}

		System.out.println(answer);
	}

	public static Optional<Long> isRunRun(long n) {
		boolean flg = false;
		char[] arr = Long.toString(n).toCharArray();
		for(int i=0;i<arr.length-1;i++) {
			if (flg || Math.abs(arr[i] - arr[i+1]) > 1) { 
				flg = true;
				long x = (long)Math.pow(10, arr.length-2-i);
				long nn = (long)(n / x);
				return Optional.of((nn+1)*x);
			}
		}
		return Optional.empty();
	}

	public static class MyScanner {
		Scanner sc = new Scanner(System.in);
		String next() { return sc.next();}
		int nextInt() { return Integer.valueOf(sc.next());}
		long nextLong() { return Long.valueOf(sc.next()); }
	}
}

Measured memory_bytes: 44092
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cfloat>
#define curr(P, i) P[(i) % P.size()]
#define next(P, i) P[(i+1) % P.size()]
#define prev(P, i) P[(i+P.size()-1) % P.size()]

using namespace std;
 
double EPS = 1e-10;
 
double add(double a, double b){
  if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0;
  return a+b;
}
 
struct point{
  double x, y;
  point(){}
  point(double x,double y) : x(x) , y(y){}

  point operator + (point p){
    return point(add(x,p.x), add(y,p.y));
  }
 
  point operator - (point p){
    return point(add(x,-p.x), add(y,-p.y));
  }
 
  point operator * (double d){
    return point(x*d,y*d);
  }
};

double dot(point a, point b){return (a.x * b.x + a.y * b.y);}
 
double cross(point a, point b){return (a.x * b.y - a.y * b.x);}

int contain(vector<point>pol,point p){
  bool in=false;
  for(int i=0;i<pol.size();i++){
    point a=curr(pol,i)-p,b=next(pol,i)-p;
    if(a.y>b.y)swap(a,b);
    if(a.y<=0 && 0<b.y && cross(a,b)<0)in=!in;
    if(cross(a,b)==0 && dot(a,b)<=0)return 2;
  }
  return in?1:0;
}


int main(void){
  int n;
  point k,s,in;
  vector<point>p; 

  cin >> n;
  while(n--){
    p.clear();
    for(int i=0;i<3;i++){
      cin >> in.x >> in.y;
      p.push_back(in);
    }     

    cin >> k.x >> k.y >> s.x >> s.y;

    if(contain(p,k)!=contain(p,s))cout << "OK" << endl;
    else cout << "NG" << endl;
     
  }
 
  return 0;
}

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

struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};


int main() {
    ll n,m;
    cin >> n >> m;
    UnionFind uf(n);
    vector<ll>a(m),b(m);
    rep(i,m) {
        cin >> a[i] >> b[i];
        a[i]--;b[i]--;
    }
    vector<ll>ans(m);
    ans[m-1] = n*(n-1)/2;
    for(int i = m-1;i>0;i--) {
        if(uf.same(a[i],b[i])) {
            ans[i-1] = ans[i];
        } else {
            ll size_a = uf.size(a[i]);
            ll size_b = uf.size(b[i]);
            ans[i-1] = ans[i] - size_a*size_b;
        }
        uf.unite(a[i],b[i]);
    }
    
    rep(i,m) cout << ans[i] << endl;
}





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

typedef struct Node {
  vector<int> child;
  long long int x;
  bool used;
}Node;

Node T[200000];

void solve(long long int x,int i){
  if(T[i].used==true) return;
  T[i].used=true;T[i].x+=x;
  for(int k=0;k<T[i].child.size();k++){
    solve(T[i].x,T[i].child[k]);
  }return;
}

int main(){
  int N,Q,a,b;
  cin >> N >> Q;
  for(int i=0;i<N;i++){
    T[i].x=0;
    T[i].used=false;
  }
  for(int i=0;i<N-1;i++){
    cin >> a >> b;a--;b--;
    T[a].child.push_back(b);
    T[b].child.push_back(a);    
  }
  
  int p;long long int y;
  for(int i=0;i<Q;i++){
    cin >> p >> y;
    T[--p].x += y;
  }
  
  solve(0,0);
  
  for(int i=0;i<N;i++){
    if(i)cout << " ";
    cout << T[i].x;
  }cout << endl;
  
  return 0;
}

Measured memory_bytes: 22656
from collections import defaultdict
n, W = map(int, input().split())
d = defaultdict(int)
d[0] = 0
for i in range(n):
    w, v = map(int, input().split())
    for j, k in list(d.items()):
        if W >= j + w:
            d[j + w] = max(d[j + w], k + v)
print(max(d.values()))

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

int main() {
	int n; cin >> n;
	map<int, int>a;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int tmp; cin >> tmp;
		a[tmp]++;
		if (a[tmp] > 1)cnt++;
	}
	int ans = a.size();
	cout << (a.size() % 2 == 0 ? ans - 1 : ans) << endl;

	return 0;
}

Measured memory_bytes: 4992
// IO library
#include <cstdio>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>

// container library
#include <deque>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>

// namespace
using namespace std;

// typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;

// container
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); i++)
#define SORT(c) sort((c).begin(), (c).end())
#define GSORT(c) sort((c).begin(), (c).end(), greater<decltype((c).front())>())
#define SZ(x) ((int)(x).size())
#define MEMSET(c, v) memset((c), v, sizeof(c))

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

// constant
// const ll MOD = 1e9 + 7;
// const int INF = 1e9;
// const ll INF = 1e15;
// const int dx[4] = {0, -1, 1, 0};
// const int dy[4] = {-1, 0, 0, 1};
// const int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
// const int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

// debug
#define test(x) cout << #x << " = " << x << endl

// answer output
#define Yes(c) cout << ((c) ? "Yes" : "No") << endl;
#define YES(c) cout << ((c) ? "YES" : "NO") << endl;
#define possible(c) cout << ((c) ? "possible" : "impossible") << endl;
#define POSSIBLE(c) cout << ((c) ? "POSSIBLE" : "INPOSSIBLE") << endl;


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


int main() {
  int N, a;
  cin >> N;
  VI vec(100003, 0);

  REP(i, N) {
    cin >> a;
    if (a > 0) {
      vec[a - 1]++;
    } else {
      vec[0]++;
    }

    vec[a + 2]--;
  }

  int sum = 0;

  REP(i, 100001) {
    sum += vec[i];
    vec[i] = sum;
  }

  int maxid = 0;

  NREP(i, 100000) {
    if (vec[i] >= vec[maxid]) {
      maxid = i;
    }
  }

  cout << vec[maxid] << endl;
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
const int n_max=1e6+10;
int dp[n_max][2];

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

  string s;
  cin >> s;
  int n = s.size();

  for(int i=n-1;i>=0;i--){
    int cn = s[i]-'0';
    if(i==n-1){
      dp[i][0] = cn;
      dp[i][1] = 10-cn;
    }
    else {
      dp[i][0] = dp[i+1][0] + cn;
      dp[i][0] = min(dp[i][0],dp[i+1][1]+cn+1);

      dp[i][1] = dp[i+1][0] + (10-cn);
      dp[i][1] = min(dp[i][1], dp[i+1][1] + (10-(cn+1)));
    }
  }

  cout << min(dp[0][1]+1,dp[0][0]) << endl;
  return 0;
    

}


Measured memory_bytes: 9116
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
 
using namespace std;
 
int main(){
    double R;
    cin >> R;
 
    cout << 2*R*3.1415 << endl;
    
    return 0;
}

Measured memory_bytes: 3784
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int h, w, n;
    cin >> h >> w >> n;
    int count = 0;
    int area = 0;
    if(w >= h){
        while(area < n){
            count += 1;
            area += w;
            
        }
    }else{
        while(area < n){
            count += 1;
            area += h;
        }
    }
    cout << count;
}


Measured memory_bytes: 256
import java.util.*

private fun readInts() = readLine()!!.split(" ").map { it.toInt() }
private fun readLongs() = readLine()!!.split(" ").map { it.toLong() }
private fun <K, V> Map<out K, V>.toMutableMap(): MutableMap<K, V> = LinkedHashMap(this)
private fun <K, V> mutableMapOf(): MutableMap<K, V> = LinkedHashMap()
private fun <K, V> mutableMapOf(vararg pairs: Pair<K, V>) = pairs.toMap().toMutableMap()

fun main(args: Array<String>) {
    val S = readLine()!!.asSequence()

    val black = S.count { it == '0' }
    val white = S.count { it == '1' }
    val diff = Math.abs(black - white)

    println(2 * (Math.max(black, white) - diff))
}

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

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

using namespace std;
using lint=long long;

int main(){
	lint n,m,vote,p; scanf("%lld%lld%lld%lld",&n,&m,&vote,&p);
	vector<lint> a(n);
	rep(i,n) scanf("%lld",&a[i]);

	sort(a.begin(),a.end(),greater<int>());

	int lo=0,hi=n;
	while(hi-lo>1){
		int mi=(lo+hi)/2;

		lint tar=a[mi]+m,k=m*vote;
		k-=m*(n-mi);
		k-=m*(p-1);
		if(k<=0){
			if(tar>=a[p-1]) lo=mi;
			else            hi=mi;
			continue;
		}

		bool ok=true;
		for(int i=p-1;i<mi;i++){
			if(a[i]>tar) ok=false;
			k-=min(tar-a[i],m);
		}
		if(ok && k<=0) lo=mi;
		else           hi=mi;
	}

	printf("%d\n",hi);

	return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
 int main(void){
int A,B,C;
scanf("%d",&A);
scanf("%d",&B);
scanf("%d",&C);
if (A==B){
printf("%d\n",C);
}
if(A==C){
  printf("%d\n",B);
}
if(B==C){
printf("%d\n",A);
}
return 0;
 }

Measured memory_bytes: 128
N = int(input())

ans = 0
if N > 3:
    ans += N-1

for i in range(2, int(N**0.5)+1):
    if N%i == 0:
        a = i-1
        if N//a == N%a:
            ans += a
        a = N//i-1
        if N//a == N%a:
            ans += a

print(ans)

Measured memory_bytes: 9352
/***********************************************************
	When you are inspired by passion 
	and you want to live for the current moment

	When your every thought and action
	has the power to become the story of your future

	When difficulties stand to demolish your Glory
	Just remember that Life is a 'Golden adverse Story'

	Withstand it to acheive your passion and dreams
	more amazingly more easily.

	Why then? When writing the story of your Life
	You want to Let someone else hold your pen

					huzaifa242©

***********************************************************/
#include "bits/stdc++.h"
using namespace std;
#define int int32_t
#define MAX 100005
#define x first 
#define y second

int seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l = 0, int r = numeric_limits <int>::max())
{return uniform_int_distribution<int> (l, r)(rng);}

template <typename T, typename G>
ostream& operator << (ostream& out, const pair <T, G> &a) 
{return out << "( " << a.x << ", " << a.y << ")";}

template <typename T>
ostream& operator << (ostream& out, const vector <T> &a) 
{out << "[ "; for(const auto &i: a) out << i << ", "; return out << "]" << endl;}

template <typename T>
ostream& operator << (ostream& out, const set <T> &a) 
{out << "{ "; for(const auto &i: a) out << i << ", "; return out << "}" << endl;}

template <typename T, typename G>
ostream& operator << (ostream& out, const map <T, G> &a) 
{out << "< "; for(const auto &i: a) out << i << ", "; return out << ">" << endl;}

template <typename T, size_t N>
typename enable_if<!is_same <typename remove_cv <T>::type, char>::value,
ostream&>::type operator << (ostream& out, T (&a)[N])
{out << "[ "; for(const auto &i: a) out << i << ", "; return out << "]" << endl;}

void debug_out(){cerr << endl;} 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{cerr << (H) << ' '; debug_out(T...);}
 
#ifdef LOCAL
#define debug(...) cerr << '#' << #__VA_ARGS__ << ":\n", debug_out(__VA_ARGS__)
#else
#define debug(...) 24
#endif

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int a, b, c, k, t = 0;
	cin >> a >> b >> c >> k;
	while (a >= b) {
		b *= 2;
		t++;
	}
	while (b >= c) {
		c *= 2;
		t++;
	}
	if (t <= k) 
		cout << "Yes\n";
	else
		cout << "No\n"; 
	return 0;
}


Measured memory_bytes: 3652
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T> using vec = std::vector<T>;
using namespace std;
using namespace boost::multiprecision;

int main() {
  cpp_int X, Y, answer = 0;
  cin >> X >> Y;
  for (; X <= Y; X <<= 1, answer++) {
  }
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 3688
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
using namespace std;
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[10000001];
//char str[1010][1010];
//vector<pair<int,int> > pc[100001];
//int ABS(int a){return max(a,-a);}
//long long num[100000];
int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	cout<<a[n-1]-a[0]<<endl;
	return 0;
}

Measured memory_bytes: 256
S = input()
N = len(S)
ans = "Yes"
for i in range( (N - 3) // 2 + 1):
    if S[i] != S[N - 1 - i]:
        ans = "No"
        break

for i in range((N - 1) // 4 + 1):
    if S[i] != S[(N - 3) // 2 - i]:
        ans = "No"
        break

print(ans)


Measured memory_bytes: 3060
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
 
public class Main {
	
	public static void main(String[] args) throws IOException {
		final Scanner sc = new Scanner(System.in);
		
		
		final String str = sc.next();
		System.out.println(str.substring(0, 4) + " " + str.substring(4));
	}
 
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;
 
		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}	
 
		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}
 
		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}
 
		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public void close() throws IOException {
			br.close();
		}
	}
}

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

int main() {
  
  int N;
  cin >> N;
  
  vector<int> vec(N);
  for (int i=0; i<N; i++) cin >> vec.at(i);
  
  int s=0;
  for (int i=0; i<100; i++) {
    for (int j=0; j<N; j++) {
      if (vec.at(j)==i+1) {
        s++;
        break;
      }
    }
  }
  
  cout << s << endl;
}

Measured memory_bytes: 256
import itertools
from collections import defaultdict
import collections
import math
import sys
sys.setrecursionlimit(200000)
mod = 1000000007

a, b, h, m = map(int, input().split())

subh = 30 * h
subh += 0.5 * m
subm = 6 * m

kakudo = min(abs(subh - subm), 360 - abs(subh - subm))
ans = a ** 2 + b ** 2 - ((2 * a * b) * (math.cos(math.radians(kakudo))))
print(math.sqrt(ans))

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

int main(){
    int A, B, M;
    cin >> A >> B >> M;
    int a[A];
    int b[B];

    for(int i=0; i<A; i++){
        cin >> a[i];
    }

    for(int i=0; i<B; i++){
        cin >> b[i];
    }

    int x[M];
    int y[M];
    int c[M];
    
    for(int i=0; i<M; i++){
        cin >> x[i] >> y[i] >> c[i];
    }

    int min_cost = *min_element(a, a+A) + *min_element(b, b+B);
    for(int i=0; i<M; i++){
        int xi = x[i];
        int yi = y[i];
        int ci = c[i];

        int cost = a[xi-1] + b[yi-1] - ci;
        if(min_cost > cost){
            min_cost = cost;
        }
    }

    cout << min_cost << endl;
    return 0;
}

Measured memory_bytes: 5508
import java.util.Scanner;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int v = Integer.valueOf(sc.next());
        int h = Integer.valueOf(sc.next());
        System.out.println(v*h + " " + 2*(v+h));
        sc.close();
    }
}

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

int main() {
  int n,t;
  cin>>n>>t;
  int ans=1e9+7;
  for(int i=0;i<n;i++){
    int c,t1;
    cin>>c>>t1;
    if(t1<=t) ans=min(ans,c);

  }
if(ans==1e9+7) cout<<"TLE"<<endl;
else cout<<ans<<endl;
  }


Measured memory_bytes: 256
n;main(r,i) {
scanf("%d",&n);r=n;
for(i=2;i*i<=n;i++)if(n%i==0)for(r=1LL*r*(i-1)/i;n%i==0;n/=i);
if(n!=1)r=1LL*r*(n-1)/n;
n=!printf("%d\n",r);
}

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

namespace Atcoder
{
    class Atcoderrrrrrr
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Console.ReadLine().Replace(",", " "));
        }
    }
}

Measured memory_bytes: 13140
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))



def solve():
    n, m, q = rl()
    Q = []
    for i in range(q):
        Q.append(rl())

    ways = [[i] for i in range(1, m + 1)]
    for i in range(n - 1):
        new_ways = []
        for way in ways:
            new_way = list(way)
            for j in range(way[-1], m + 1):
                new_ways.append(new_way + [j])
        ways = new_ways

    best = 0
    for way in ways:
        tot = 0
        for a, b, c, d in Q:
            if way[b - 1] - way[a - 1] == c:
                tot += d
        best = max(best, tot)

    print (best)







mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()


Measured memory_bytes: 113484
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;

int N;
VV<int> G;
V<int> ans;
V<int> par;
V<int> abovemax;

using P = pair<int,int>;
map<P,int> memo;

int f(int v,int x){	//<=x
	if(v>x) return 0;
	if(memo.count(P(v,x))) return memo[P(v,x)];
	int res = 1;
	for(int u:G[v]) if(u!=par[v]) res += f(u,x);
	return memo[P(v,x)] = res;
}

void dfs1(int v,int p){
	par[v] = p;
	if(p!=-1) abovemax[v] = max(abovemax[p],p);
	for(int u:G[v]) if(u!=p) dfs1(u,v);
}
void dfs(int v,int p){
	if(p!=-1){
		int sv = 1;
		for(int u:G[v]) if(u!=par[v]) sv += f(u,abovemax[v]);
		int sp = f(v,abovemax[p]);
		ans[v] = ans[p] + (sv - sp);
	}
	for(int u:G[v]) if(u!=p) dfs(u,v);
}

int main(){
	cin>>N;
	G.resize(N);
	par.resize(N);
	ans.resize(N);
	abovemax.resize(N);
	rep(i,N-1){
		int x,y;
		cin>>x>>y;
		x--,y--;
		G[x].pb(y);
		G[y].pb(x);
	}
	dfs1(0,-1);
	dfs(0,-1);
	rep1(i,N-1) cout<<ans[i]<<" ";
	cout<<endl;
}

Measured memory_bytes: 49280
h, w = map(int, input().split())
area = [[0 for _ in range(w)] for _ in range(h)]
canvas = [[0 for _ in range(w)] for _ in range(h)]

black = 0
for i in range(h):
    for j, x in enumerate(list(input())):
        if x == '#':
            area[i][j] = 1
            black += 1

def check(canvas, area, i, j):
    if area[i][j] != 1:
        canvas[i][j] = 1
        return canvas
    if j+1 < w:
        if area[i][j+1] == 1:
            canvas[i][j] = 2
            canvas[i][j+1] = 2
    if i+1 < h:
        if area[i+1][j] == 1:
            canvas[i][j] = 2
            canvas[i+1][j] = 2
    return canvas


black_painted = 0
for i in range(h):
    for j in range(w):
        canvas = check(canvas, area, i, j)
        if canvas[i][j] == 2:
            black_painted += 1


print('Yes') if black == black_painted else print('No')

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;

int main(){

	double t, x;
	cin >> t >> x;

	cout << t/x<< endl;

	return 0;
}

Measured memory_bytes: 888
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.math;



void main() {
    int input;
    immutable limitList = 200000;
    bool[] listNumbers = new bool[](limitList);
    int[] listPrimeNumbers;

    listNumbers.fill(true);
    foreach (i; 2..limitList.to!double.sqrt.to!int) {
        if (listNumbers[i]) {
            for (int j = i*2; j < limitList; j += i) listNumbers[j] = false;
        }
    }

    foreach (i; 2..listNumbers.length) {
        if (listNumbers[i]) {
            listPrimeNumbers ~= i.to!int;
        }
    }

    while ((input = readln.chomp.to!int) != 0) {
        ulong sum = 0;

        foreach (i; 0..listPrimeNumbers.length) {
            if (i == input) break;
            sum += listPrimeNumbers[i];
        }

        writeln(sum);
    }
}

Measured memory_bytes: 1236
#!/usr/bin/env python3


def solv(n, h):
    hh = 10**9+1
    for hi in reversed(h):
        if hh >= hi:
            hh = hi
        elif hh != hi-1:
            return 'No'
    return 'Yes'


if __name__ == '__main__':

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

    ans = solv(N, H)

    print(ans)


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

int main() {
    vector<vector<int>> c(3, vector<int> (3, 0));
    for (long long i=0; i<3; i++) {
        for (long long j=0; j<3; j++) {
            cin >> c.at(i).at(j);
        }
    }
    vector <int> df(9);
    df.at(0) = c.at(0).at(0)-c.at(0).at(1);
    df.at(1) = c.at(0).at(1)-c.at(0).at(2);
    df.at(2) = c.at(0).at(2)-c.at(0).at(0);
    df.at(3) = c.at(1).at(0)-c.at(1).at(1);
    df.at(4) = c.at(1).at(1)-c.at(1).at(2);
    df.at(5) = c.at(1).at(2)-c.at(1).at(0);
    df.at(6) = c.at(2).at(0)-c.at(2).at(1);
    df.at(7) = c.at(2).at(1)-c.at(2).at(2);
    df.at(8) = c.at(2).at(2)-c.at(2).at(0);
    if (df.at(0)==df.at(3) && df.at(0)==df.at(6) && df.at(1)==df.at(4) && df.at(1)==df.at(7) && df.at(2)==df.at(5) && df.at(2)==df.at(8)) {
        cout << "Yes";
    }
    else cout << "No";
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x << ": " << x << "\n"
#define PRINTALL(V)    \
  for (auto v : (V)) { \
    cerr << v << " ";  \
  }                    \
  cerr << "\n";
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
using namespace std;
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> using vec = std::vector<T>;
template <class T> void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  string s;
  cin >> s;
  print(s.substr(0, 1) + to_string(s.size() - 2) + s.substr((int)s.size() - 1, 1));
}

Measured memory_bytes: 256
fun main(args:Array<String>){
    val(r,g,b,n)= readLine()!!.split(" ").map{
        it.toInt()
    }
    var ans=0
    for(i in 0..n){
        for(j in 0..n){
            if(i*r+j*g>n)continue
            if((n-i*r-j*g)%b==0) ans++
        }
    }
    println(ans)
}


Measured memory_bytes: 37920
sx,sy,tx,ty = map(int,input().split())

dx = tx - sx
dy = ty - sy

ans = ""
for i in range(dy):
  ans += "U"
for i in range(dx):
  ans += "R"
for i in range(dy):
  ans += "D"
for i in range(dx):
  ans += "L"
#二週目  
ans += "L"
for i in range(dy+1):
  ans += "U"       
for i in range(dx+1):
  ans += "R"
ans += "D"
ans += "R"
for i in range(dy+1):
  ans += "D"
for i in range(dx+1):
  ans += "L"
ans += "U"   
print(ans) 

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  cout << fixed << setprecision(12);
  string s; cin>>s;
  for (char c: s) cout<<"x";
  

  return 0;
}


Measured memory_bytes: 256
n, m = list(map(int, input().split()))
if n % 2 == 0 and m > 1:
    ans = list(range(1, m*2+1))
    s = (len(ans)//2)//2
    for i in range(len(ans)//2):
        if i < s:
            print(ans[i], ans[-1-i]+1)
        else:
            print(ans[i], ans[-1-i])
else:
    ans = list(range(1, m*2+1))
    for i in range(len(ans)//2):
        print(ans[i], ans[-1-i])


Measured memory_bytes: 70684
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
#define REP(i, n) for (Int i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (Int i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) begin(obj), end(obj)
#define RALL(obj) rbegin(obj), rend(obj)
#define fi first
#define se second
using ii = pair<Int, Int>;
template <class T> inline bool chmax(T& a, const T& b) {
    if (a >= b) return false;
    a = b;
    return true;
}
template <class T> inline bool chmin(T& a, const T& b) {
    if (a <= b) return false;
    a = b;
    return true;
}
struct SetupIO {
    SetupIO() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }
} setup_io;

template <class T> std::ostream& print(std::ostream& out, T const& val) { return (out << val << " "); }
template <class T1, class T2> std::ostream& print(std::ostream& out, std::pair<T1, T2> const& val) {
    return (out << "{" << val.first << " " << val.second << "} ");
}
template <template <class, class...> class TT, class... Args>
std::ostream& operator<<(std::ostream& out, TT<Args...> const& cont) {
    for (auto&& elem : cont) print(out, elem);
    return out;
}

void dump_func() { cerr << endl; }
template <class Head, class... Tail> void dump_func(Head&& h, Tail&&... t) {
    cerr << h << (sizeof...(Tail) == 0 ? "" : ", "), dump_func(forward<Tail>(t)...);
}
#ifdef _MY_DEBUG
#define dump(...)                                                                                                    \
    cerr << "/* " << #__VA_ARGS__ << " [" << __LINE__ << ":" << __FUNCTION__ << "]" << endl, dump_func(__VA_ARGS__), \
        cerr << "*/\n\n";
#else
#define dump(...)
#endif

/**
 *    author:  knshnb
 *    created: Sun Nov 24 11:43:50 JST 2019
 **/

template <class T, class S> vector<T> make_vec(size_t n, S x) { return vector<T>(n, x); }
template <class T, class... Ts> auto make_vec(size_t n, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(n, make_vec<T>(ts...));
}

signed main() {
    Int H, W, K;
    cin >> H >> W >> K;
    vector<string> t(H);
    REP(i, H) cin >> t[i];
    vector<Int> cnt(H);
    REP(i, H) cnt[i] = count(ALL(t[i]), '#');
    auto ans = make_vec<Int>(H, W, -1);
    Int idx = 0;
    REP(i, H) {
        if (cnt[i] == 0) {
            if (i) ans[i] = ans[i - 1];
            continue;
        }
        REP(j, W) {
            ans[i][j] = idx;
            if (t[i][j] == '#') idx++;
        }
        for (Int j = W - 1; j >= 0; j--) {
            if (t[i][j] == '#') break;
            ans[i][j] = idx - 1;
        }
    }
    Int i0 = -1;
    REP(i, H) {
        if (cnt[i]) {
            i0 = i;
            break;
        }
    }
    REP(i, i0) ans[i] = ans[i0];
    REP(i, H) {
        REP(j, W) { cout << ans[i][j] + 1 << " "; }
        cout << endl;
    }
}


Measured memory_bytes: 1664
//long long -> ll
//http://web.mit.edu/~ecprice/acm/acm08/notebook.html#file12
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include<bits/stdc++.h>
typedef long long ll;
#define x first
#define y second
#define all(aaa) (aaa).begin(),(aaa).end()
#define REP(i,sss,eee) for(long long i=sss;i<=eee;++i)
#define pb push_back
#define pii pair<long long,long long>
#define vi vector<long long>
#define speed ios_base::sync_with_stdio(0);cin.tie(0);
#define N 1000000007
using namespace __gnu_pbds;
using namespace std;
template <class T>
T MAX(T a, T b){return ((a>b)?a:b);}
template <class T>
T MIN(T a, T b){return ((a<b)?a:b);}
template <class T>
T MOD(T a){return ((a>=0)?a:(-1*a));}
template <class T>
void SWAP(T &a,T &b){T temp=a;a=b;b=temp;}
typedef tree<
long long,
null_type,
less<long long>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
long long ex(long long a, long long b){
	if(b==0||a==1){return 1;}
	if(a==0||b==1){return a;}
	long long tmp=ex(a,(b/2));
	if(b%2){return ((((tmp*tmp)%N)*a)%N);}
	else{return ((tmp*tmp)%N);}
}
long long inv(long long k){
	if(k==1){return 1;}
	else{return ex(k,N-2);}
}
/*****************default********************/
std::vector<std::vector<long long>> g;
std::vector<long long> topo;
std::vector<bool> vis;
long long dfs(long long seed)
{
	vis[seed]=1;
	for(auto it:g[seed])
	{
		if(!vis[it])
		{
			dfs(it);
		}
	}
	topo.pb(seed);
	return 0;
}
long long solve()
{
	long long n;cin>>n;
	g.resize(n);
	std::vector<long long> dp(n),black(n);
	vis.resize(n,0);
	REP(i,0,n-2)
	{
		long long a,b;cin>>a>>b;--a;--b;
		g[a].pb(b);g[b].pb(a);
	}
	dfs(0);
	vis.clear();vis.resize(n,0);
	for(auto it:topo)
	{
		long long ans=1,ans1=1;
		vis[it]=1;
		for(auto pp:g[it])
		{
			if(vis[pp])
			{
				ans=(ans*dp[pp])%N;
				ans1=((ans1*(dp[pp]-black[pp]))%N);
			}
		}
		dp[it]=((((ans+ans1)%N)+N)%N);
		black[it]=((((ans1)%N)+N)%N);
	}
	cout<<dp[0]<<"\n";
}
signed main(){
	long long tt=1;
	//cin>>tt;
	while(tt--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 12664
while True:
    n = int(input())
    if n == 0:
        break
    emp = [0] * 4001
    used = set()
    for i in range(n):
        e, p, q = map(int, input().split())
        emp[e] += p * q
        if 1000000 <= emp[e] and e not in used:
            print(e)
            used.add(e)
    if len(used) == 0:
        print("NA")
    

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

typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); i++)

struct query
{
    ll l, r;
};
ll Q;
vector<query> queries;

bool is_prime(ll n)
{
    if (n < 2)
    {
        return false;
    }
    ll i = 2;
    while (i * i <= n)
    {
        if (n % i == 0)
        {
            return false;
        }
        i++;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    ll right = INT64_MIN;
    ll left = INT64_MAX;
    cin >> Q;
    queries.resize(Q);
    rep(i, queries.size())
    {
        cin >> queries[i].l >> queries[i].r;
        left = min(left, queries[i].l);
        right = max(right, queries[i].r);
    }
    vector<ll> dp((right - left) / 2 + 1);
    for (ll i = left; i <= right; i += 2)
    {
        ll j = (i - left) / 2;
        if (j != 0)
        {
            dp[j] = dp[j - 1];
        }
        if (is_prime(i) && is_prime((i + 1) / 2))
        {
            dp[j]++;
        }
    }
    for (query query : queries)
    {
        ll ans = 0;
        ans += dp[(query.r - left) / 2];
        if (query.l != left)
        {
            ans -= dp[(query.l - left) / 2 - 1];
        }
        printf("%d\n", ans);
    }
}


Measured memory_bytes: 2560
inp = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n')
N = inp.shift() * 1
a = 0
i = 0
while(a < N) {
    i++
    a += i
}
m = a - N
for(j=1; j<=i; j++) {
    if (m != j) {
      console.log(j)
    }
}

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

int main(){
  int h,w,i;
  cin >> h >> w;
  string S;
  for(i=0;i<h;i++){
    cin >> S;
    cout << S << endl;
    cout << S << endl;
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

#define M 18

#define POS(i,j) ((i)*M+(j))

void run(void){
  int n;
  scanf("%d",&n);
  int *x=(int *)malloc(sizeof(int)*n);
  int i;
  for(i=0;i<n;i++) scanf("%d",x+i);
  int l;
  scanf("%d",&l);
  int *dp=(int *)malloc(sizeof(int)*n*M);
  int r=0;
  for(i=0;i<n;i++){
    while(r<n && x[r]-x[i]<=l) r++;
    dp[POS(i,0)]=r-1;
  }
  for(i=0;dp[POS(0,i)]<n-1;i++){
    int j;
    for(j=0;j<n;j++){
      dp[POS(j,i+1)]=dp[POS(dp[POS(j,i)],i)];
    }
  }
  int q;
  scanf("%d",&q);
  while(q--){
    int a,b;
    scanf("%d%d",&a,&b);
    a--;
    b--;
    if(a>b){
      int c=a;
      a=b;
      b=c;
    }
    int ans=0;
    int now=a;
    while(now<b){
      int i=0;
      while(dp[POS(now,i)]<b) i++;
      if(i==0){
	ans++;
	break;
      }
      i--;
      ans+=(1<<i);
      now=dp[POS(now,i)];
    }
    printf("%d\n",ans);
  }
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 8192