akhauriyash/Code-Regression huggingface dataset:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
import sys
n,m = ma()
ckp = []
st = []

for i in range(n):
    st.append(lma())
for i in range(m):
    ckp.append(lma())
for a,b in st:
    tmp=10**15
    ans=0
    for i  in range(m):
        c,d=ckp[i]
        if tmp>abs(a-c)+abs(b-d):
            tmp=abs(a-c)+abs(b-d)
            ans=i+1
    print(ans)


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

int main() {
  int n, a, b;
  cin >> n >> a >> b;
  int ans = min(a*n, b);
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3564
def main():
    c = [ [ int(x) for x in input().split() ] for _ in range(3) ]

    for a1 in range(101):
        for a2 in range(101):
            for a3 in range(101):
                b1 = c[0][0] - a1
                b2 = c[0][1] - a1
                b3 = c[0][2] - a1
                a = [a1, a2, a3]
                b = [b1, b2, b3]
                flag = True
                for i in range(3):
                    for j in range(3):
                        if c[i][j] != a[i] + b[j]:
                            flag = False
                if flag:
                    print("Yes")
                    return
    print("No")

main()


Measured memory_bytes: 42332
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        int[] inpt = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
        while(inpt.Sum()>0) {
            Console.WriteLine(GetAns(inpt[1], inpt[0]));
            inpt = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
        }
    }

    private int GetAns(int h, int w) {
        bool[,] map = new bool[h, w];
        for (int i = 0; i < h; i++) {
            bool[] inpt = Reader.ReadLine().Split(' ').Select(a => a[0] != '0').ToArray();
            for (int j = 0; j < w; j++) {
                map[i, j] = inpt[j];
            }
        }
        int ans = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if(map[i,j]) {
                    CountIsl(i, j, map);
                    ans++;
                }
            }
        }
        return ans;
    }

    private void CountIsl(int h, int w, bool[,] map)
    {
        map[h, w] = false;

        for (int i = Math.Max(0, h - 1); i <= Math.Min(map.GetLength(0) - 1, h + 1); i++) {
            for (int j = Math.Max(0, w - 1); j <= Math.Min(map.GetLength(1) - 1, w + 1);j++) {
                if(!map[i, j]) {
                    continue;
                }
                CountIsl(i, j, map);
            }
        }
    }

    public class Reader
    {
        static StringReader sr;
        public static bool IsDebug = false;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (sr == null)
                {
                    sr = new StringReader(InputText.Trim());
                }
                return sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
        private static string InputText = @"


1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0


";
    }

    public static void Main(string[] args)
    {
#if DEBUG
        Reader.IsDebug = true;
#endif
        Program prg = new Program();
        prg.Proc();
    }
}


Measured memory_bytes: 10076
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n = int(input())
a = [int(x) for x in input().split()]

# 1~aの最大値までの数の最小の素因数を前処理で求める(O(max_aloglog(max_a)))
def smallest_prime_factors(a):
    max_a = max(a)
    smallest_prime_factors = [int(x) for x in range(max_a + 1)]
    for i in range(2, max_a + 1):
        if smallest_prime_factors[i] == i:
            for j in range(i, max_a + 1, i):
                if smallest_prime_factors[j] == j:
                    smallest_prime_factors[j] = i
        else:
            continue
    return smallest_prime_factors

smallest_prime_factors = smallest_prime_factors(a)

# nを素因数分解(O(log(n)))
def prime_factorize(n):
    prime_factors = []
    if n == 1:
        return prime_factors
    while n != smallest_prime_factors[n]:
        prime_factors.append(smallest_prime_factors[n])
        n //= smallest_prime_factors[n]
    prime_factors.append(n)
    return prime_factors

prime_factors = set()

flag = 1

for i in a:
    prime_factorize_i = set(prime_factorize(i))
    for j in prime_factorize_i:
        if j in prime_factors:
            flag = 0
            break
        else:
            prime_factors.add(j)

if flag:
    print('pairwise coprime')
    sys.exit()

import math
from functools import reduce

def gcd(*numbers):
    return abs(reduce(math.gcd, numbers))

if gcd(*a) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Measured memory_bytes: 236324
a, b = map(int, input().split())

def prime_factorize(n):
    a = set({1})
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a
print(len(prime_factorize(a) & prime_factorize(b)))

Measured memory_bytes: 9096
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
using static System.Console;

namespace atcorder2
{
    class Program
    {
        public static long Read()
        {
            return long.Parse(ReadLine());
        }

        public static long[] Reads()
        {
            return ReadLine().Split().Select(long.Parse).ToArray();
        }


        public static long gcd(long x,long y)
        {
            if (y < x) gcd(y, x);
            while (y != 0)
            {
                var z = x % y;
                x = y;
                y = z;
            }
            return x;
        }

        public static long C(long n,long k)
        {
            long x=1;
            for (long i = 1; i <=k; i++)
            {
                x *= n - i + 1;
                x /= i;
            }
            return x;
        }
        static void Main(string[] args)
        {
            var sw = new StreamWriter(OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var q = Reads();
            var n = q[0];
            var p = q[1];
            var a = Reads();
            var c = 0;
            for (int i = 0; i < a.Length; i++)
            {
                if (a[i] % 2 == 1) c++;
            }
            var o = c;
            var e = a.Length - o;
            long x1 = 0;
            long x2 = 0;
            long y = (long)Math.Pow(2,e);
            
            for (int i = 1; i <= o; i += 2)
            {
                x1 += C(o, i);
            }
            for (int i = 2; i <= o; i += 2)
            {
                x2 += C(o, i);
            }

            WriteLine(p%2==1?x1*y: (long)Math.Pow(2, o)*y-x1*y);
            


            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 19260
#include <bits/stdc++.h>
using namespace std;
const double pi=2*acos(0.0);
double inff=1.0/0.0;
#define ll           long long int
#define inf          1000000000000000008
#define MOD          1000000007
#define pb           push_back
#define sz(x)        (int)x.size()
#define mp           make_pair
#define lbd          lower_bound
#define ubd          upper_bound
#define ipair        pair<ll,ll> 
#define all(v)       v.begin(),v.end()
#define watch(x)     cout<<(#x)<<" is "<<(x)<<endl;
#define rep(a,b,c)   for(a=(int)b;a<(int)c;a++)
#define rep2(a,b,c)  for(a=(int)b;a<(int)c;a+=2)  
#define bac(a,b,c)   for(a=(int)b;a>=(int)c;a--)
#define se           second
#define f            first
#define ios          ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
#define mem(a,val)   memset(a,val,sizeof a)
#define endl         "\n"
#define mxn          200001
#define vi           vector<ll>
#define vii          vector<ipair> 
#define si           set<ll> 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
/*Variables Start*/
ll x,y,n,i,z,j,k,w,u,q,m,t;
ll v[53];
/*Variables End*/
void solve()
{
 	cin>>n;
 	rep(i,1,n+1)
 	{
 		cin>>v[i];
 		if(v[i]!=i) x++;
 	}
 	if(x<=2)
 	{
 		cout<<"YES"<<endl;
 	}
 	else cout<<"NO"<<endl;
}
int main() 
{ 
  int TESTS=1;
  ios;  
  while(TESTS--)
  {
    solve();
  }  
}

Measured memory_bytes: 256
import java.util.*;
class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int[] a = new int[4];
	for(int i = 0; i<4; i++) {
	    a[i] = sc.nextInt();
	}
	Arrays.sort(a);
	int[] b = {1, 4, 7, 9};
	for(int i = 0; i<4; i++) {
	    if(a[i]!=b[i]) {
		System.out.println("NO");
		return;
	    }
	}
	System.out.println("YES");
    }
}

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

int main()
{
	string a; cin >> a;
	int rs = 0 , CPos; 
	for (int i  = 0 ; i < a.length() ; i ++)
	{
		if (a[i] == 'C')
		{
			rs ++;
			CPos = i;
			break;
		}
	}
	for (int i  = CPos ; i < a.length() ; i ++)
	{
		if (a[i] == 'F')
		{
			rs ++;
			break;
		}
	}
	if (rs == 2)
	{
		cout << "Yes";
	}
	else
	{
		cout << "No";
	}
	return 0;
}

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

const long long INF = 1000000000;

typedef long long ll;

#define writeln(n) cout<<n<<"\n";

typedef pair<int, int> P;
typedef pair<string, int> Psi;


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

	int n,k;cin>>n>>k;

	int ct=0;
	for(int i=0; i<n; i++){
		int tmp;cin>>tmp;
		if(tmp>=k)ct++;
	}
	writeln(ct);

}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define __ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi acos(-1)
using namespace std;

ll mod = 1e9+7;

int main ()
{
__

int m,d,rem,div,ans=0;

cin >> m >> d;

for(int i=1;i<=m;i++)
{
for(int j=1;j<=d;j++)
{
rem = j%10;
div = j/10;

if(rem>=2 && div >=2 && rem*div==i) ans++;

}

}

cout << ans << '\n';

return 0;
}



Measured memory_bytes: 256
def factorize(n):
    b,e = 2,0
    fct = []
    while b*b <= n:
        while n%b==0:
            n//=b
            e+=1
        if e>0:
            fct.append((b,e))
        b+=1
        e=0
    if n!=1:
        fct.append((n,1))
    return fct
    
N,M = list(map(int,input().split()))
 

if M==1:
    print(1)
else:
    pl = factorize(M)
    
    max_coef=max([p[1] for p in pl])
    
    
    if max_coef==0:
        print(N)
    else:
    
        comb_list = [1]
        c = 1
        mod = 10**9+7
        for i in range(max_coef):
            c *= N+i
            c *= pow(i+1,mod-2,mod)
            c %= mod
            comb_list.append(c)
    
        ans = 1
    
        for p in pl:
            ans*=comb_list[p[1]]
            ans %= mod
    
        print(ans)

Measured memory_bytes: 38512
import sys


def main():
    n = int(sys.stdin.readline().strip())
    h = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    cur_height = float('inf')
    cont_count = 0
    ans = 0
    for i in range(n):
        if h[i] <= cur_height:
            cont_count += 1
            ans = max(ans, cont_count)
        else:
            cont_count = 1
        cur_height = h[i]
    print(ans-1)


main()


Measured memory_bytes: 59296
#include <stdio.h>
int kouyakusuu(int a,int b){
int tmp,r;
if(a<b){
tmp=a;
a=b;
b=tmp;
}
r=a%b;
while(r!=0){
a=b;
b=r;
r=a%b;
}
return b;
}
int main(void)
{
int K,a=1,b=1,c=1,d,wa=0;
scanf("%d",&K);
for(a=1;a<=K;a++){
for(b=1;b<=K;b++){
for(c=1;c<=K;c++){
d=kouyakusuu(kouyakusuu(a,b),c);
wa=wa+d;
}
}
}

printf("%d",wa);
return 0;
}

Measured memory_bytes: 1704
#include <bits/stdc++.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
 
 
int main(int argc, char** argv){
	int k,n,fir{0},nex,max{0},store;
	cin >> k >> n >> fir;
	store = fir;
	n--;
	while(n--){
		cin >> nex;
		if(nex - fir > max){
			max = nex - fir;
		}
		fir = nex;
	}
	if(k-(nex - store) > max){
		max = k-(nex - store);
	}
	cout << k - max;
	return 0;
}

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

int main() {
	long long a, b, c, k;
	cin >> a >> b >> c >> k;
	long long ans = (b + c) - (a + c);

	if (k % 2 == 1) cout << ans << endl;
	else cout << -1 * ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define INF 0x3f3f3f3f
#define MOD 1000000007

using namespace std;
typedef long long ll;

mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

template <class T> class FenwickTree {
  int limit;
  vector<T> arr;

  T lowbit(T x) { return x & (-x); }

public:
  FenwickTree(int limit) {
    this->limit = limit;
    arr = vector<T>(limit + 1);
  }

  void update(int idx, T delta) {
    for (; idx <= limit; idx += lowbit(idx))
      arr[idx] += delta;
  }

  T query(int idx) {
    T ans = 0;
    for (; idx > 0; idx -= lowbit(idx))
      ans += arr[idx];
    return ans;
  }
};

class Solution {
public:
  void solve() {
    int n, q;
    read(n), read(q);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
      read(a[i]);
    vector<pair<int, int>> queries;
    for (int i = 0; i < q; ++i) {
      int l, r;
      read(l), read(r);
      queries.emplace_back(l, r);
    }
    vector<int> order(q);
    for (int i = 0; i < q; ++i)
      order[i] = i;
    sort(order.begin(), order.end(),
         [&](int i, int j) { return queries[i].second < queries[j].second; });
    vector<int> ans(q);
    vector<int> pos(n + 1);
    int last = 0;
    FenwickTree<int> ft(n);
    for (int i = 0; i < q; ++i) {
      int k = order[i];
      int l = queries[k].first, r = queries[k].second;
      for (int j = last + 1; j <= r; ++j) {
        if (pos[a[j]] != 0)
          ft.update(pos[a[j]], -1);
        ft.update(j, 1);
        pos[a[j]] = j;
      }
      ans[k] = ft.query(r) - ft.query(l - 1);
      last = r;
    }
    for (int i : ans)
      printf("%d\n", i);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  Solution solution = Solution();
  solution.solve();
}

Measured memory_bytes: 17400
n = int(input())
a = list(map(int, input().split()))

n1 = 0
n2 = 0
n4 = 0
for i in range(0, n):
    if a[i] % 4 == 0:
        n4 += 1
    elif a[i] % 2 == 0:
        n2 += 1
    else:
        n1 += 1

if (n2 == 0 and n4 + 1 >= n1) or (n4 >= n1):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 14252
import java.util.Arrays;
import java.util.Scanner;

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

	public void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] lis = new int[(int) 1e5 + 1];
		for (int i = 0; i < n; ++i) {
			int x = sc.nextInt();
			++lis[x];
		}
		int[] c2 = new int[m];
		int[] c1 = new int[m];
		for (int i = 0; i < lis.length; ++i) {
			c2[i % m] += lis[i] / 2 * 2;
			c1[i % m] += lis[i] % 2;
		}
		for (int i = 0; i <= m / 2; ++i) {
			int j = (m - i) % m;
			if (i == j) {
				c2[i] += c1[i] / 2 * 2;
				c1[i] %= 2;
				continue;
			}
			int tmp = Math.min(c1[i], c1[j]);
			c1[i] -= tmp;
			c1[j] -= tmp;
			if (c1[i] > c1[j]) {
				tmp = c1[i];
				c1[i] = c1[j];
				c1[j] = tmp;
				tmp = c2[i];
				c2[i] = c2[j];
				c2[j] = tmp;
			}
			tmp = Math.min(c2[i], c1[j] / 2 * 2);
			c1[j] -= tmp;
			c2[i] -= tmp;
		}
		int ans = 0;
		for (int v : c1) {
			ans += v;
		}
		if ((n - ans) % 2 == 1) {
			throw new AssertionError();
		}
		System.out.println((n - ans) / 2);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}


Measured memory_bytes: 52124
#include<bits/stdc++.h>
#include<cmath>
#include<cstring>
#include<climits>
#define int long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define asc(a,n) sort(a,a+n);
#define dsc(a,n) sort(a,a+n,comp);
#define fo(i,x,y) for(int i=x;i<y;i++)
#define inarr(x) int n; cin>>n; int x[n]; fo(i,0,n){cin>>x[i];}
#define test int t; cin>>t; while(t--)
using namespace std;

int basic(){freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);return 0;}
bool comp(int a,int b){return a>b;}



int32_t main()
{ //basic(); 
  fast; 
  int n; int m; cin>>n>>m; int h[n+1]; int a[n+1]={0};
  fo(i,1,n+1)
  {
    cin>>h[i];
  } int x,y;
  fo(i,0,m)
  {
    cin>>x>>y;
    if(h[x]>=h[y]){a[y]=-1; }
    if(h[y]>=h[x]){a[x]=-1;}
  } 
  int cnt=0;
  fo(i,1,n+1)
  {
    if(a[i]==0){cnt++;}
  }
  cout<<cnt;
  
  

  
  return 0;
}






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

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

// chmax, chmin
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;
}

void solve(long long N, long long K, std::vector<long long> H) {
    sort(H.rbegin(), H.rend());
    long long ans = 0;
    for(int i = K ; i < N ; i++){
        ans += H[i];
    }
    cout << ans << endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long K;
  scanf("%lld", &K);
  std::vector<long long> H(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &H[i]);
  }
  solve(N, K, std::move(H));
  return 0;
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
int main(){
  bool f1 = false,f2=false;
  string s;
  cin >> s;
  string sp1 = s.substr(0,2);
  string sp2 = s.substr(2);
  int nsp1=stoi(sp1);
  int nsp2=stoi(sp2);
  if(nsp1 < 13 && nsp2 <= 99 && nsp1 > 0) f1 = true;
  if(nsp1 <= 99 && nsp2 < 13 && nsp2 > 0) f2 = true;

  if(f1&f2){
    cout << "AMBIGUOUS" << endl;
  }else if(f2){
    cout << "YYMM" << endl;
  }else if(f1) {
    cout << "MMYY" << endl;
  }else{
    cout << "NA" << endl;
  }
}
  


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int N = 3001;

ll a[N],n,s,dp[N][3];

void add(ll &a, ll b){
	a += b;
	if(a >= MOD) a -= MOD;
	else if(a < 0) a += MOD;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> s;
	for(int i=0;i<n;i++) cin >> a[i];
	
	for(int i=0;i<n;i++){
		for(int j=1;j<=s;j++) add(dp[j][2], -dp[j][1]);
		for(int j=s-a[i];j>0;j--){
			int x = j+a[i];
			add(dp[x][0], dp[j][2]);
			add(dp[x][1], dp[j][1]);
			add(dp[x][2], dp[j][2]);
		}
		add(dp[a[i]][0], (i+1) * (n-i));
		add(dp[a[i]][1], i+1);
		add(dp[a[i]][2], (i+1) * (n-i));
	}
	cout << dp[s][0] << endl;
	return 0;
}



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

int main() {

    int k, x;
    cin >> k >> x;

    for(int i=x-k+1; i<=k+x-1; ++i){
        cout << i << " ";
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>


using namespace std;
int N, M;
vector<int>p;
vector<bool>s;


int main()
{


	cin >> N;
	cin >> M;

	p = vector<int>(M);
	s = vector<bool>(M);

	auto acp = vector<int>(N + 1,0);

	for (int i = 0; i <  M; i++) {
		cin >> p[i];

		string tmp;
		cin >> tmp;

		s[i] = !tmp.compare("AC");
	}

	int ac_count = 0;
	int p_count = 0;

	for (int i = 0; i < M; i++) {
		if (acp[p[i]] < 0) { continue; }

		if (!s[i]) {
			acp[p[i]]++;
		}
		else {
			ac_count++;
			p_count += acp[p[i]];
			acp[p[i]] = -1;
		}
	}

	

	cout << ac_count << " " << p_count << endl;

	return 0;
}



Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include<vector>
#include<map>
#include <algorithm>

using namespace std;

unsigned int getPow2(unsigned int num) { //i以上で最小の2のべき乗数を返す
    int i = 0;
    while(1) {
        num >>= 1;
        if(num <= 0) break;
        i++;
    }
    return 1 << i+1;
}

int main(int, char**) {
    unsigned int N, A;
    map<unsigned int, unsigned int> A_map; //値,個数
    vector<unsigned int> A_vector;
    unsigned int max_odd_index = 0, max_even_index = 0;
    int num_pow2 = 0;
    cin >> N;
    A_vector.reserve(N);
    for(int i = 0; i< N ; i++) {
        cin >> A;
        A_map[A]++;
        A_vector.push_back(A);
    }
    sort(A_vector.begin(), A_vector.end(), greater<int>());
    //ペア探し
    for(int i = 0; i < N; i++) {
        if(A_map[A_vector[i]]==0) continue;
        A_map[A_vector[i]]--;
        if (A_map[getPow2(A_vector[i])-A_vector[i]]!=0) {
            A_map[getPow2(A_vector[i])-A_vector[i]]--;
            num_pow2++;
        }
    }
    cout << num_pow2 << endl;
    return 0;
}

Measured memory_bytes: 19712
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

void shuffle(char card[], int h) {
	for (int i = 0; i < h; i++) {
		char tmp = card[0];
		for (int j = 1; j < strlen(card); j++) {
			card[j-1] = card[j];
		}
		card[strlen(card)-1] = tmp;
	}
}

int main() {
	while (1) {
		char card[201];
		scanf("%s", card);
		if (strcmp(card, "-") == 0) {
			break;
		}

		int m;
		scanf("%d", &m);

		for (int i = 0; i < m; i++) {
			int h;
			scanf("%d", &h);
			shuffle(card, h);
		}

		printf("%s\n", card);
	}

	return 0;
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<S<<endl
#define PB push_back
using namespace std;


int main(){
	int n;
	map<pair<int,int>,int> mp;
	mp[{0,1}]=mp[{1,2}]=mp[{2,3}]=mp[{3,0}]=1;//clock-wise
	while(cin>>n,n){
		int m;
		int nextx,nexty,nowx,nowy,nextm,nowm=5;
		vector<int> d[51],muki[51],rmuki;
		int mu[51];
		cin>>m;
		cin>>nowx>>nowy;
		REP(i,0,m-1){
			cin>>nextx>>nexty;
			if(nextx-nowx>0)		mu[i]=0;//right
			else if(nexty-nowy<0)	mu[i]=1;//down
			else if(nextx-nowx<0)	mu[i]=2;//left;
			else if(nexty-nowy>0)	mu[i]=3;//up

			d[0].PB(abs(nextx-nowx+nexty-nowy));
			if(i) muki[0].PB(mp[{mu[i-1],mu[i]}]);
			nowx=nextx;
			nowy=nexty;
		}
		for(int i=m-2;i>0;i--){
			rmuki.PB(mp[{mu[i],mu[i-1]}]);
		}
		REP(j,1,n+1){
			cin>>m;
			cin>>nowx>>nowy;
			REP(i,0,m-1){
				cin>>nextx>>nexty;

				if(nextx-nowx>0)		nextm=0;//right
				else if(nexty-nowy<0)	nextm=1;//down
				else if(nextx-nowx<0)	nextm=2;//left;
				else if(nexty-nowy>0)	nextm=3;//up

				d[j].PB(abs(nextx-nowx+nexty-nowy));
				if(i) muki[j].PB(mp[{nowm,nextm}]);

				nowm=nextm;
				nowx=nextx;
				nowy=nexty;

			}
		}
		REP(i,1,n+1){
			if(d[0]==d[i]&&muki[0]==muki[i]){
				p(i);
				continue;
			}

			if(rmuki==muki[i]){
				bool flag=true;
				REP(j,0,m-1){
					if(d[0][j]!=d[i][m-j-2]){
						flag=false;
						break;
					}
				}
				if(flag) p(i);
			}

		}

		p("+++++");
	}


	return 0;
}

Measured memory_bytes: 3084
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define MP(x, y) make_pair(x, y)
#define Pair pair<int, int> 
//#define int long long 
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M;
Pair P[MAXN];
main() {
	N = read(); M = read();
	for(int i = 1; i <= M; i++) {
		int x = read(), y = read();
		P[i] = MP(y, x);
	}
	int ans = 0, last = -1;
	sort(P + 1, P + M + 1);
	for(int i = 1; i <= M;) {
		int j = i + 1;
		while(j <= M && P[i].first == P[j].first) j++;
		if(P[j - 1].second >= last) 
			ans++, last = P[j - 1].first;
		i = j;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
//#define int long long  
int main(){
    int N;
    int a[114514];
    int num[3]={};
    cin >> N;
    REP(i,N){
        cin >> a[i];
        if(a[i]%2==1){a[i]=0;num[0]++;}
        else if((a[i]/2)%2==1){a[i]=1;num[1]++;}
        else{a[i]=2;num[2]++;}
    }
    //num[2]+=2;
    //cout << num[0] << num[1] << num[2] << endl;
    if((num[2]-num[0]>=0 && num[1]!=0)||(num[2]-num[0]>=-1 && num[1]==0)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

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

int main() {
   ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);
   ll a, b, c, k;
   cin >> a >> b >> c >> k;
   while (b <= a) {
      b *= 2;
      k--;
   }
   while (c <= b) {
      c *= 2;
      k--;
   }
   cout << (k >= 0 ? "Yes" : "No") << '\n';
   return 0;
}

Measured memory_bytes: 3604
#include<iostream>
#include<cmath>
#define M 100000007
using namespace std;

int comb[1100][1100];

int main(){
  int r,c,a1,b1,a2,b2;

  for(int i=0;i<=1000;i++){
    for(int j=0;j<=1000;j++)comb[i][j] = 0;
    comb[i][0] = comb[i][i] = 1;
  }

  for(int i=1;i<=1000;i++){
    for(int j=1;j<i;j++){
      comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % M;
    }
  }
  
  cin >> r >> c >> a1 >> b1 >> a2 >> b2;
  
  int path = r+c+1, num = 0;
  int a = abs(a1-a2), b = abs(b1-b2);
  if(path>a+b){
    path = a+b;
    num = comb[a+b][a];
  }else if(path == a+b){
    num += comb[a+b][a];
    num %= M;
  }

  if(path>r-a+b){
    path = r-a+b;
    num = comb[r-a+b][r-a];
  }else if(path == r-a+b){
    num += comb[r-a+b][r-a];
    num %= M;
  }

  if(path>a+c-b){
    path = a+c-b;
    num = comb[a+c-b][a];
  }else if(path == a+c-b){
    num += comb[a+c-b][a];
    num %= M;
  }

  if(path>r-a+c-b){
    path = r-a+c-b;
    num = comb[r-a+c-b][r-a];
  }else if(path == r-a+c-b){
    num += comb[r-a+c-b][r-a];
    num %= M;
  }

  cout << num % M << endl;
}

Measured memory_bytes: 5464
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <iterator>
#include <bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define tenll(x) ((ll)1e##x)

int disp[10][7] = {
	{ 1, 1, 1, 0, 1, 1, 1 },
	{ 0, 0, 1, 0, 0, 1, 0 },
	{ 1, 0, 1, 1, 1, 0, 1 },
	{ 1, 0, 1, 1, 0, 1, 1 },
	{ 0, 1, 1, 1, 0, 1, 0 },
	{ 1, 1, 0, 1, 0, 1, 1 },
	{ 1, 1, 0, 1, 1, 1, 1 },
	{ 1, 0, 1, 0, 0, 1, 0 },
	{ 1, 1, 1, 1, 1, 1, 1 },
	{ 1, 1, 1, 1, 0, 1, 1 }
};

bool enable[14][7];
int sum[14][10];

const int DS[] = {-1 , 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

vector<int> solve_all_upper(){
	vector<int> ret(60);
	FOR(y, 10000) for (int m = 1; m <= 12; m++) {

		int s = 0;
		s += sum[0][y / 1000];
		s += sum[1][y / 100 % 10];
		s += sum[2][y / 10 % 10];
		s += sum[3][y % 10];
		s += sum[4][m / 10];
		s += sum[5][m % 10];

		int md = DS[m];
		if (m == 2 && (y % 400 == 0 || (y % 100 != 0 && y % 4 == 0))) md++;
		for(int d = 1; d <= md; d++) {
			int t = s;
			t += sum[6][d / 10];
			t += sum[7][d % 10];
			ret[t]++;
		}
	}
	return ret;
}

vector<int> solve_all_lower(){
	vector<int> ret(50);
	FOR(a, 24) FOR(b, 60) FOR(c, 60){
		int s = 0;
		s += sum[8][a / 10];
		s += sum[9][a % 10];
		s += sum[10][b / 10];
		s += sum[11][b % 10];
		s += sum[12][c / 10];
		s += sum[13][c % 10];
		ret[s]++;
	}
	return ret;
}

int main(){
	int n; cin >> n;
	int k; cin >> k;
	memset(enable, 1, sizeof(enable));
	FOR(i, k){
		int a, b; cin >> a >> b;
		enable[a][b] = false;
	}
	FOR(i, 14) FOR(j, 10) FOR(k, 7){
		if (enable[i][k] && disp[j][k]) sum[i][j]++;
	}

	vector<int> all_upper = solve_all_upper();
	vector<int> all_lower = solve_all_lower();

	vector<ll> v(110);
	ll ans = 0;
	FOR(i, 60) FOR(j, 50){
		v[i + j] += ll(all_upper[i]) * all_lower[j];
	}

	cout << v[n] << endl;
}

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

#define all(v) v.begin(), v.end()
#define V vector
#define P pair
typedef long long ll;
const int INT_INF = 1e9;
const ll INF = 1LL << 30;

int main() {
    ll h; cin >> h;

    ll ans = 1;
    for(int i = 1; h > 1 ; i++){
        h /= 2;
        ans += pow(2, i);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
using System;

public class Hello
{
    public static void Main()
    {
        var x = int.Parse(Console.ReadLine().Trim());
        var res = 0L;
        for (int i = 1; i <= 32; i++)
            for (int j = 2; j <= 10; j++)
            {
                var w = (long)Math.Pow(i, j);
                if (w <= x) res =(long) Math.Max(res, w);
            }
        Console.WriteLine(res);
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

typedef long long ll;

#define f first
#define s second

ll n, m, v[100002], sum[100002];

ll larger (ll x) {
  ll nr = 0;
  for (ll i = 1; i <= n; i++) {
    ll st = i, dr = n, poz = 0;
    while (st <= dr) {
      ll mij = (st + dr) / 2;
      if (v[i] + v[mij] > x) {
        st = mij + 1;
        poz = mij;
      }
      else
        dr = mij - 1;
    }
    if (poz > 0)
      nr += 1 + (poz - i) * 2;
  }
  return nr;
}


int main()
{
  cin >> n >> m;
  for (ll i = 1; i <= n; i++)
    cin >> v[i];
  sort(v + 1, v + n + 1);
  reverse(v + 1, v + n + 1);
  for (ll i = 1; i <= n;i++)
    sum[i] = sum[i - 1] + v[i];
  ll st = 1, dr = 2e5, ans;
  while (st <= dr) {
    ll mij = (st + dr) / 2;
    if (larger(mij) < m) {
      dr = mij - 1;
      ans = mij;
    }
    else {
      st = mij + 1;
    }
  }
  ll nr = 0;
  ll hatz = 0;
  for (ll i = 1; i <= n; i++) {
    ll st = i, dr = n, poz = 0;
    while (st <= dr) {
      ll mij = (st + dr) / 2;
      if (v[i] + v[mij] > ans) {
        st = mij + 1;
        poz = mij;
      }
      else
        dr = mij - 1;
    }
    if (poz > 0) {
      nr += 1 + (poz - i) * 2;
      hatz += (sum[poz] - sum[i]) * 2 + v[i] * 2 + 2 * v[i] * (poz - i);
    }
  }
  cout << (m - nr) * ans + hatz << "\n";
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long double LD; 
typedef long long ll; 
#define int ll 
#define ff(i,a,b) for (int i = a; i < b; i++) 
#define bf(i,a,b) for (int i = a; i >= b; i--) 
#define all(v) v.begin(),v.end() 
#define show(a) for(auto xyz:a)cout<<xyz<<" ";cout<<endl;
#define F first 
#define S second
#define pb push_back
#define mp make_pair
#define lb lower_bound   
#define ub upper_bound
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define one cout<<"-1"<<endl
#define pi 3.141592653589793238
#define intmx INT_MAX 
#define intmi INT_MIN
const int MOD=1e9+7;
int mod(int x){
    return ((x%MOD + MOD)%MOD);
}
int add(int a,int b){
    return mod(mod(a)+mod(b));
}
int mul(int a,int b){
    return mod(mod(a)*mod(b));
}
void solve(){
   int n;
   cin>>n;
   if(n>=30)
   yes;
   else
   no;
}
signed main() {
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

Measured memory_bytes: 3676
package main

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

//Util
func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func maxInt(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func minInt(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func absInt(a int) int {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

//Main
var sc = bufio.NewScanner(os.Stdin)
var a, b, n int

func main() {
	sc.Split(bufio.ScanWords)
	a, b, n = nextInt(), nextInt(), nextInt()
	x := minInt(b-1, n)
	//fmt.Println(x)
	fmt.Println(int(a*x/b) - a*int(x/b))
}


Measured memory_bytes: 1756
#include <bits/stdc++.h>
using namespace std;
using Int = long long int;
template<typename T> void swap(T *t1, T *t2){ T* tmp=t1; t1=t2; t2=tmp;}
Int tmp = 0;
double tmpd = 0.0;


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

    Int p, q, r;
    cin >> p >> q >> r;
    Int min = 1000000;
    min = p+q < p+r ? p+q : p+r;
    min = q+r < min ? q+r : min;
    cout << min << endl;

    return 0;
}

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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>
#define Graph vector<vector<int>>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

const string YES = "Yes";
const string NO = "No";

void func(long long A, long long B, long long C, long long D){

}

int main(){

    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    long long D;
    scanf("%lld",&D);
    

    ll countT=0;
    ll countA=0;

    while(A>0){
        A-=D;
        countT++;

    }

    while(C>0){
        C-=B;
        countA++;

    }

    if(countT>=countA){
        cout << "Yes" << endl;
    }

    else{
        cout << "No" << endl;
    }
    return 0;
}


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

using namespace std;

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

	#ifdef LOCAL
	assert(freopen("input.txt", "r", stdin));
	#endif

	int n;
	cin >> n;
	vector<int> b(n);
	for (auto &t : b) {
		cin >> t;
		t--;
	}	
	vector<int> ans;
	while (!b.empty()) {
		/*cerr << "-" << endl;
		for (auto t : b) cerr << t;
		cerr << endl;*/
		int pos = -1;
		for (int i = 0; i < (int)b.size(); i++) {
			if (i == b[i]) {
				pos = i;
				//break;	
			}
		}
		if (pos == -1) {
			cout << -1;
			exit(0);
		} else {
			ans.push_back(pos);
			b.erase(b.begin() + pos);
		}
	}	
	reverse(ans.begin(), ans.end());
	for (auto t : ans) {
		cout << t + 1 << '\n';
	}
}



Measured memory_bytes: 896
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

def main():
    n=int(input())
    ans=int(input())
    for _ in range(n-1):
        t=int(input())
        ans=t*ans//gcd(t,ans)
    print(ans)
main()

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> ac(n), pena(n);
  rep(i,m) {
    int p;
    string s;
    cin >> p >> s;
    --p;
    if (ac[p]) continue;
    if (s == "AC") {
      ac[p] = 1;
    } else {
      pena[p]++;
    }
  }
  int AC = 0, PENA = 0;
  rep(i,n) {
    AC += ac[i];
    if (ac[i]) PENA += pena[i];
  }
  printf("%d %d\n", AC, PENA);
  return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
int main(void){
    int r,g,b,num;
    scanf("%d %d %d",&r,&g,&b);
    num=r*100+g*10+b;
    if(num%4==0){
        printf("YES\n");
    }else{
        printf("NO\n");
    }
    return 0;
}


Measured memory_bytes: 128
# -*- coding: utf-8 -*-
# A

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

x = float(input())
if x > 0:
    print(0)
else:
    print(1)





Measured memory_bytes: 65124
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

void dfs(int v, int p, Graph& g, vector<bool>& visited, vector<int>& ans) {
  visited[v] = true;
  if (v > 0)
    ans[v] += ans[p];

  for (auto nv : g[v])
    if (!visited[nv])
      dfs(nv, v, g, visited, ans);
}

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

  Graph g(n);
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  vector<int> ans(n);
  for (int i = 0; i < q; ++i) {
    int p, x;
    cin >> p >> x;
    --p;
    ans[p] += x;
  }

  vector<bool> visited(n);
  dfs(0, -1, g, visited, ans);

  for (int i = 0; i < n; ++i) {
    if (i != 0)
      cout << " ";
    cout << ans[i];
  }
  cout << endl;
}

Measured memory_bytes: 29824
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <climits> // FOO_MAX, FOO_MIN
#include <cmath> 
#include <cstdlib> // abs(int)
#include <numeric>
#include <iomanip>

using namespace std;

#define roundup(n,d) ( ((n) + ((d)-1)) / (d) )
#define assign_max(into, compared) (into = max((into), (compared)))
#define assign_min(into, compared) (into = min((into), (compared)))
#define rep(i,n) for(long long i = 0;i < n;++i)
#define FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr);
#define fix(n) fixed << setprecision(n)

#define PI 3.14159265358979323846;

using ll = long long;
using ull = unsigned long long;
using vll = vector<long long>;


int main(void){
    FAST_IO
    
    ll h,a;
    cin >> h >> a;
    cout << roundup(h,a) << endl;
    
    return 0;
}

Measured memory_bytes: 3156
# pdf解法（隣接行列でグラフを管理して、DFSで連結判定する）
def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    for i in range(N):
        # xに繋がっている頂点をたどっていく
        if graph[x][i]:
            dfs(i)


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

edge = []
graph = [[False]*N for _ in range(N)]   # 隣接行列
visited = [False]*N

for i in range(M):
    a, b = map(int, input().split())
    edge.append((a, b))
    graph[a-1][b-1] = True
    graph[b-1][a-1] = True

ans = 0
for i, e in enumerate(edge):
    # 辺を取り除く
    graph[e[0]-1][e[1]-1] = False
    graph[e[1]-1][e[0]-1] = False

    # 初期化（全ての頂点を未訪問にする）
    for j in range(N):
        visited[j] = False

    # 任意の１つの頂点からDFS
    dfs(0)

    # 連結判定（訪問していない頂点がある＝非連結）
    bridge = False
    for j in range(N):
        if not visited[j]:
            bridge = True
    if bridge:
        ans += 1

    # 取り除いた辺を戻す
    graph[e[0]-1][e[1]-1] = True
    graph[e[1]-1][e[0]-1] = True

print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <math.h>
#include <string>
using namespace std;
          

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string a , b , c;
    cin >> a >> b >> c;
    char i = 'a';
    reverse( a.begin() , a.end() );
    reverse( b.begin() , b.end() );
    reverse( c.begin() , c.end() );
    while ( a.length() >= 0 && b.length() >= 0 && c.length() >= 0 ) {
        if ( i == 'a' ) {
            if ( a.length() == 0 ) {
                cout << "A\n";
                break;
            } else {
                i = a[a.length() - 1];
                a.pop_back();
            }
        } else if ( i == 'b' ) {
            if ( b.length() == 0 ) {
                cout << "B\n";
                break;
            } else {
                i = b[b.length() - 1];
                b.pop_back();
            }
        } else {
            if ( c.length() == 0 ) {
                cout << "C\n";
                break;
            } else {
                i = c[c.length() - 1];
                c.pop_back();
            }
        }
    }
}

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

using namespace std;

int main() {
  size_t N;
  cin >> N;
  multiset<int, greater<int>> s(greater<int>{});
  auto num = pow(2, N);
  for (size_t i = 0; i < num; ++i) {
    int S;
    cin >> S;
    s.emplace(S);
  }
  vector<int> done;
  done.reserve(num);

  vector<int> adding;
  adding.reserve(num / 2);

  auto it = s.begin();
  adding.emplace_back(*it);
  s.erase(it);

  while (!s.empty()) {
    for (int val : adding) {
      done.emplace_back(val);
    }
    adding.clear();
    sort(done.rbegin(), done.rend());
    for (int val : done) {
      auto it = s.upper_bound(val);
      if (it == s.end()) {
        cout << "No" << endl;
        return 0;
      }
      adding.emplace_back(*it);
      s.erase(it);
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 13568
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=100005;
template<typename T>
void read(T &x){
	x=0;int f=1; char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    x*=f;
}
ll d[N];
struct Edg{
	int nxt,poi;
}e[N<<1];
int size[N],first[N],l=0,n,deep[N];
vector<pii>G;
map<ll,int>id;
void addedge(int u,int v){
	G.push_back(make_pair(u,v));
	l++;
	e[l].nxt=first[u];
	e[l].poi=v;
	first[u]=l;
}
void dfs(int u,int f){
	for (int p=first[u];p;p=e[p].nxt){
		int v=e[p].poi;
		if (v==f) continue;
		deep[v]=deep[u]+1; 
		dfs(v,u);
	}
}
int main(){
	read(n);
	for (int i=1;i<=n;i++) read(d[i]),id[d[i]]=i,size[i]=1;
	sort(d+1,d+1+n);
	for (int i=n;i>1;i--){
		int u=id[d[i]];
		int tmp=n-2*size[u];
		if (tmp<=0){printf("-1\n"); return 0;}
		ll t=d[i]-tmp;
		if (id[t]==0){printf("-1\n"); return 0;}
		int fa=id[t];
		addedge(fa,u); 
		size[fa]+=size[u];
	}
	dfs(id[d[1]],id[d[1]]);
	ll sum=0;
	for (int i=1;i<=n;i++) sum+=deep[i];
	if (sum!=d[1]){printf("-1\n"); return 0;}
	for (int i=0;i<G.size();i++){
		printf("%d %d\n",G[i].first,G[i].second);
	}
	return 0;
}

Measured memory_bytes: 13688
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i = 0; i < int(n); ++i)
#define sz(x) ((int) (x).size())
typedef long double ld;
typedef long long ll;
typedef long long i64;

const int M = 100100;

int n;
ll a[M];
vector<int> g[M];
vector<ll> x[M];
int deg[M];
int q[M], qs = 0, qf = 0;
bool u[M];
set<pair<int, int>> s;

void yes() {
    cout << "YES\n";
    exit(0);
}

void no() {
    cout << "NO\n";
    exit(0);
}

void read() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

bool was(int x, int y) {
    return s.count({min(x, y), max(x, y)});
}

void add(int x, int y) {
    s.emplace(min(x, y), max(x, y));
}

void kill() {
    for (int i = 0; i < n; ++i)
        deg[i] = g[i].size();
    
    for (int i = 0; i < n; ++i)
        if (deg[i] == 1) {
            u[i] = true;
            x[i].push_back(a[i]);
            q[qf++] = i;
        }

    while (qs < qf) {
        int v = q[qs++];
        auto &cur = x[v];

        ll sum = 0;
        for (ll x : cur)
            sum += x;

        ll need = sum - a[v];

        //cerr << "v = " << v + 1 << ", need = " << need << endl;
        //for (int x : cur)
            //cerr << x << " ";
        //cerr << endl;

        sort(cur.begin(), cur.end());

        ll mn = 0, mx;
        if (2 * cur.back() <= sum) {
            mx = sum / 2;
        } else {
            mx = sum - cur.back();
        }

        if (need < mn || need > mx)
            no();

        int cnt = 0;
        for (int to : g[v])
            if (!was(v, to)) {
                add(v, to);
                ++cnt;
                deg[to]--;
                x[to].push_back(sum - 2 * need);
                if (deg[to] == 1) {
                    u[to] = true;
                    q[qf++] = to;
                }
            }
        if (qs == n && sum - 2 * need != 0)
            no();
        //if (cnt == 0 && sum != 2 * need)
            //no();
        assert(cnt <= 1);
    }

    yes();
}

int main() {
#ifdef LOCAL
    assert(freopen("c.in", "r", stdin));
#endif
    ios_base::sync_with_stdio(false);

    read();
    kill();

}



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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = 1e9+7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; } template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	string s;
	cin >> s;
	
	string x[]={"YYMM", "MMYY", "AMBIGUOUS", "NA"}; 
	
	int p1=stoi(s.substr(0,2));
	int p2=stoi(s.substr(2,2));
	
	bool b1=true, b2=true;
	if(p1 <1 || p1>12) b1=false;
	if(p2 <1 || p2>12) b2=false;
	
	if(!b1 && b2) cout<<x[0]<<endl;
	else if(b1 && !b2) cout<<x[1]<<endl;
	else if(b1 && b2) cout<< x[2]<<endl;
	else cout<<x[3]<<endl;;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[1000010];
int main () {
    int n,k;
    cin>>k>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int mi = 2e9;
    //mi = min(k-a[n-1]+a[0],mi);
    for(int i=0;i<n;i++){
        if(i==0)
            mi = min(mi,a[n-1]-a[0]);
        else
            mi = min(mi,k-a[i]+a[i-1]);


    }
    cout<<mi;
}

Measured memory_bytes: 1024
object Main extends App {
  @scala.annotation.tailrec
  def loop(v: Double, vs: Seq[Double]): Double = {
    vs match {
      case Seq() => v
      case head::tail => loop((v + head) / 2, tail)
    }
  }
  val sc = new java.util.Scanner(System.in)
  val v::vs = List.fill(sc.nextInt())(sc.nextDouble()).sorted
  println(loop(v, vs))
}

Measured memory_bytes: 27288
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
vector<int> g[100005];
int vis[100005], dp[100005];
void dfs(int u) {
  vis[u] = 1;
  for (int v : g[u]) {
    if (!vis[v])
      dfs(v);
    dp[u] = max(dp[u], dp[v] + 1);
  }
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[i])
      dfs(i);
  }
  cout << *max_element(dp + 1, dp + n + 1) << endl;
}


Measured memory_bytes: 8576
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <regex>
#include <stack>
#include <queue>
#include <vector>
#define MAX_N 100
#define INF 10000000

using namespace std;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

long n,a,b;
string s;

void solve(){
	int n = 0;
	for (int i = 0; i < 6; i++) {
		if (s[i] == '1') n++;
	}
	cout << n << endl;
}

int main() {
	cin >> s;
	solve();
	return 0;
}

Measured memory_bytes: 256