akhauriyash/Code-Regression huggingface dataset:
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>

using namespace std;

#define int long long 

int n;
vector<int> a;
vector<int> b;

signed main() {
  cin >> n;
  a.resize(n);
  b.resize(n);

  int rest_sum = 0;
  int lack_sum = 0;
  int lack_cnt = 0;

  vector<int> rests;

  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    int lack = max(0LL, b[i] - a[i]);
    int rest = max(0LL, a[i] - b[i]);
    lack_sum += lack;
    rest_sum += rest;
    if (rest > 0) {
      rests.push_back(rest);
    }
    if (lack > 0) {
      lack_cnt++;
    }
  }

  if (lack_sum > rest_sum) {
    cout << -1 << endl;
    return 0;
  }

  if (lack_sum == 0) {
    cout << 0 << endl;
    return 0;
  }

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

  for (int i = 1; i < rests.size(); i++) {
    rests[i] += rests[i - 1];
  }

  if (rests.size() == 1) {
    cout << lack_cnt + 1 << endl;
    return 0;
  }

  int l = 0, r = rests.size();
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (rests[m] >= lack_sum) {
      r = m;
    } else {
      l = m;
    }
  }

  cout << lack_cnt + r + 1 << endl;

  return 0;
}


Measured memory_bytes: 2428
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  int n; cin >> n;
  map<string, int> mp;
  for(int i = 0; i < n; i++) {
    string s; cin >> s;
    sort(ALL(s));
    mp[s]++;
  }

  lint ans = 0;
  for(auto x : mp) {
    lint val = x.second;
    ans += val * (val - 1) / 2;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 11136
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

import math
import decimal

ctx = decimal.Context(prec=5, rounding=decimal.ROUND_CEILING)

for i in range(int(input())):
    a, b, c, d = map(int, input().split())

    if a < b:
        print('No')
        continue

    if b > d:
        print('No')
        continue

    if c >= b:
        print('Yes')
        continue

    g = gcd(b, d)
    r = a % g
    # FYI: https://stackoverflow.com/questions/2795946/getting-ceil-of-decimal-in-python
    _max = (int(((decimal.Decimal(b, context=ctx) - decimal.Decimal(r, context=ctx)) / decimal.Decimal(g, context=ctx)).to_integral_exact(context=ctx)) * g) + r - g

    # math.ceilは精度不足でエラーになる: https://cocoinit23.com/math-floor-ceil-error/
    #_max = ((math.ceil((b - r) / g)) * g) + r - g

    # OK: (a + b - 1) // b: https://nariagari-igakusei.com/cpp-division-round-up/
    #_max = ((b - r + g - 1)//g) * g + r - g
    if c < _max:
        print('No')
    else:
        print('Yes')


Measured memory_bytes: 79548
a = int(input())
b = int(input())
c = int(input())
X = int(input())


count = 0
for x in range(a+1):
	for y in range(b+1):
		for z in range(c+1):
			count += 1 if( X == (500 * x + 100 * y + 50 * z)) else +0
#			print((500 * x + 100 * y + 50 * z))
#			print(x)
#			print(y)
#			print(z)
print(count)

Measured memory_bytes: 3060
import java.util.Scanner;
import java.io.*;
import java.util.Arrays;


public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		/*long sum = 1;
		for(int i = 0; i < k; i++) {
			sum*= (long)a[i];
		}
		long pre = sum;
		
		for(int i = k; i < n; i++) {
			sum = sum * (long)a[i] / (long)a[i - k];
			//System.out.println(sum + " " + pre);
			if(sum > pre) {
				System.out.println("Yes");
			}else {
				System.out.println("No");
			}
			pre = sum;
		}*/
		for(int i = k; i < n; i++) {
			if(a[i] > a[i - k]) {
				System.out.println("Yes");
			}else {
				System.out.println("No");
			}
		}
	}
	
}


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

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

int main()
{
    long long int a, b, c, d;
    long long int canc, cand;
    long long int canlcm;
    long long int lcm;

    cin >> a >> b >> c >> d;

    lcm = c*d/gcd(c, d);

    canc = (b/c - a/c);
    if (a%c == 0) {
        canc++;
    }

    cand = (b/d - a/d);
    if (a%d == 0) {
        cand++;
    }

    canlcm = (b/lcm - a/lcm);
    if (a%lcm == 0) {
        canlcm++;
    }

    cout <<(b-a)+1-((canc+cand)-canlcm) << endl;
}


Measured memory_bytes: 256
#pypy
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

#累積和
for _ in range(K):
    B = [0]*N
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1, i+A[i])
        B[l] += 1
        if r+1 < N: B[r+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    B,A = A,B
    if min(A) == N:
        break
print(*A)


Measured memory_bytes: 151304
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    long long A;
    long long ans;
    double B;
    long long tA;
    int tB;
    scanf("%lld", &A);
    scanf("%lf", &B);
    tA = (long long)(A / 100);
    tB = (int)(100 * B);
    if (100 * B - tB > 0.5)
    {
        ++tB;
    }
    ans = tA * tB + (long long)(((A - tA * 100) * tB) / 100);
    printf("%lld", ans);
    return 0;
}

Measured memory_bytes: 1748
def DP_D() :
    N, W = map(int, input().split())
    w = []
    v = []
    for i in range(N) :
        wi, vi = map(int, input().split())
        w.append(wi)
        v.append(vi)

    dp = [[0]*(W+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(W+1) :
            if j >= w[i-1] :
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]]+v[i-1])
            dp[i][j] = max(dp[i][j], dp[i-1][j])

    return max(dp[N])

print(DP_D())


Measured memory_bytes: 118768
s = input()

stack = []

ans = 0

for s_i in s:
  if len(stack) == 0:
    stack.append(s_i)
    continue
  if (s_i == "0" and stack[-1] == "1") or (s_i == "1" and stack[-1] == "0"):
    stack.pop()
    ans += 2
  else:
    stack.append(s_i)
print(ans)
  

Measured memory_bytes: 3956
//A-Task_Scheduling_Problem
#include <bits/stdc++.h>
using namespace std;

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

  if(a<c) swap(a,c);
  if(a<b) swap(a,b);
  if(b<c) swap(b,c);
  a=a-b;
  b=b-c;
  cout<<a+b<<endl;
  return 0;
}


Measured memory_bytes: 256
/*
  AUTHOR:SOURABH
  CREATED:13:09:20
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<ll , null_type, less< ll >, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define W while
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x) for(i=x;i>=0;i--)
#define fit(it,s) for(it=s.begin();it!=s.end();it++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define mod 1000000007
#define MAXN 10000001
#define M 32

using namespace std;
using namespace __gnu_pbds;

ll modex(ll x,ll y)
{
    x=x%mod;
    ll r=1;
    while(y>0)
    {
        if(y%2==1)
            r=(r*x)%mod;
        y/=2;
        x=(x*x)%mod;
    }
    return r;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //freopen("input.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    ll t,s,i,j;
    t=1;
    //cin>>t;
    W(t--)
    {
        cin>>s;
        vll dp(s+1);
        fs(i,3,s+1)
        {
            dp[i]=1;
            for(j=3;j<i;j++)
            dp[i]=(dp[i]+dp[i-j])%mod;
        }
        cout<<dp[s];
    }
}











Measured memory_bytes: 3592
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }



const int MAX = 210000;;

int N;
int A[MAX], B[MAX], C[MAX];

int main() {
    while (cin >> N) {
        for (int i = 0; i < N; ++i) cin >> A[i];
        for (int i = 0; i < N; ++i) cin >> B[i];
        for (int i = 0; i < N; ++i) cin >> C[i];
        
        sort(A, A+N);
        sort(B, B+N);
        sort(C, C+N);
        long long res = 0;
        for (int i = 0; i < N; ++i) {
            long long a = lower_bound(A, A+N, B[i]) - A;
            long long c = upper_bound(C, C+N, B[i]) - C;
            res += a * (N - c);
        }
        cout << res << endl;
    }
}




Measured memory_bytes: 1408
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,a,ans=0;
    cin>>n>>x;
    int d[n+1];
    d[0]=0;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        d[i+1]=d[i]+a;
    }
    for(int i=0;i<=n;i++)
    {
        if(d[i]<=x)
        ans++;
        else
        break;
    }
    cout<<ans<<"\n";
}

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

int A[100005];
int B[100005];
int C[100005];
int dp[100005][3];

int main() {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &A[i], &B[i], &C[i]);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == 0) {
				if (j == 0) dp[i][j] = A[i];
				else if (j == 1) dp[i][j] = B[i];
				else dp[i][j] = C[i];
			} else {
				for (int k = 0; k < 3; k++) {
					if (j == k) continue;

					if (j == 0) dp[i][j] = max(dp[i][j], dp[i-1][k] + A[i]);
					else if (j == 1) dp[i][j] = max(dp[i][j], dp[i-1][k] + B[i]);
					else dp[i][j] = max(dp[i][j], dp[i-1][k] + C[i]);
				}
			}
		}
	}
	int result = 0;
	result = max({result, dp[n-1][0], dp[n-1][1],dp[n-1][2]});
	printf("%d\n", result);
}

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

main() {
    string S; cin >> S; bool can =true;
    int count=0;
    rep(i,S.size()){
        if(i==0){if(S[i]!='A'){can=false; break;}}
        else if(i>=2&&S.size()-2>=i&&S[i]=='C')count++;
        else if(S[i]==toupper(S[i])) {can =false; break;}
    }
    if(count!=1)can = false;
    if(can) cout << "AC" << endl;
    else cout << "WA" << endl;

    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.println((int)Math.pow(Integer.parseInt(br.readLine()), 3));
	}
}

Measured memory_bytes: 17024
////////////////////////////////////////////////////////////////////
// This source code is for Visual Studio
////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <stack>
#include <functional>
#include <iomanip>
#include <string>
#include <cstring>
#include <deque>
#include <math.h>
#include <assert.h>

#define	numberof(a)	(sizeof(a) / sizeof(a[0]))
#define	INF		UINT64_MAX
#define Rep(i,n) for(int i = 0; i < (n); ++i )

using namespace std;

typedef vector< vector<int> > MAT;
typedef pair<int, int> PINT;
typedef long long ll;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int32_t s32;
typedef int64_t s64;

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int main()
{
	ll A = 0;
	ll B = 0;
	ll C = 0;
	ll ans = 0;

	cin >> A >> B >> C;
	ll max_val = max( A, max(B, C) );

	if ( A % 2 == B % 2 && B % 2 == C % 2 ) {
		ans = (max_val - A) / 2 + (max_val - B) / 2 + (max_val - C) / 2;
	}
	else {
		if (A % 2 == B % 2 && B % 2 != C % 2) {
			A++;
			B++;
		}
		else if (A % 2 == C % 2 && C % 2 != B % 2) {
			A++;
			C++;
		}
		else if (B % 2 == C % 2 && C % 2 != A % 2) {
			B++;
			C++;
		}
		max_val = max(A, max(B, C));
		ans = (max_val - A) / 2 + (max_val - B) / 2 + (max_val - C) / 2 + 1;
	}

	cout << ans << endl;

	return 0;
}


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

int main() {
    long long N,K;
    cin >> N >> K;
    long long ans = 1;
    for(int i = 0; i < N; i++) {
        if(ans <= K) {
            ans *= 2;
        }
        else {
            ans += K;
        }
    }
    cout << ans << endl;
} 



Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
#define rep(i,x) for(int i = 0; i < x; i++)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> ivec;
const ll N = 1e9+7;

int main(){
    int n; cin >> n;
    int p[n];
    rep(i,n) cin >> p[i];
    int ans =  0;
    rep(i,n){
        bool ok = false;
        if(i > 0 && i < n-1){
            if(p[i] < p[i-1] && p[i] > p[i+1]) ok = true;
            else if(p[i] > p[i-1] && p[i] < p[i+1]) ok = true;
        }
        if(ok) ans++;

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

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

vector<int>getbin(long n){
  vector<int>ret;
  for(int i=0; i<45; i++){
    ret.push_back(n%2);
    n/=2;
  }
  return ret;
}

int main(){
  long a, b;
  cin >> a >> b;
  long l=b-a+1;
  vector<int>bita=getbin(a);
  long p=1, ret=0;
  for(int i=0; i<45; i++){
    long cnt1=0, q=l/(2*p), r=l%(2*p);
    cnt1+=q*p;
    if(bita[i]==1)cnt1+=min(p-(a%p)+max(0L, r-(2*p-(a%p))), r);
    else cnt1+=r-min(p-(a%p)+max(0L, r-(2*p-(a%p))), r);
    ret+=p*(cnt1%2);
    p*=2;
  }
  cout << ret;
  return 0;
}

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

class Solve {
private:
	using vi = std::vector<int>;
	using vvi = std::vector<vi>;
	using i3 = std::array<int, 3>;

public:
	bool is_last_query{};
	Solve()
	{
		int N, M, L, K, A, H;
		scanf("%d%d%d%d%d%d", &N, &M, &L, &K, &A, &H);
		if (N == 0)
		{
			is_last_query = true;
			return;
		}

		std::vector<bool> hospital_exists(N);
		for (int i{}; i < L; i++)
		{
			int hos;
			scanf("%d", &hos);
			hospital_exists[hos] = true;
		}

		std::vector<std::list<std::pair<int, int>>> graph(N);
		for (int i{}; i < K; i++)
		{
			int X, Y, T;
			scanf("%d%d%d", &X, &Y, &T);
			graph[X].push_back({Y, T});
			graph[Y].push_back({X, T});
		}
		
		vvi distance(N, vi(M + 1, 1 << 30));
		std::fill(distance[A].begin(), distance[A].end(), 0);

		std::priority_queue<i3, std::vector<i3>, std::greater<i3>> dij;
		dij.push({0, A, M});
		while (!dij.empty())
		{
			i3 now{dij.top()};
			dij.pop();
			if (now[0] > distance[now[1]][now[2]]) continue;
			if (now[1] == H) break;
			for (auto& e: graph[now[1]])
			{
				if (now[2] < e.second) continue;
				if (now[0] + e.second >= distance[e.first][now[2] - e.second]) continue;
				distance[e.first][now[2] - e.second] = now[0] + e.second;
				dij.push({now[0] + e.second, e.first, now[2] - e.second});
			}
			if (hospital_exists[now[1]] && now[2] < M)
			{
				if (now[0] + 1 >= distance[now[1]][now[2] + 1]) continue;
				distance[now[1]][now[2] + 1] = now[0] + 1;
				dij.push({now[0] + 1, now[1], now[2] + 1});
			}
		}
		int ans{*std::min_element(distance[H].begin(), distance[H].end())};
		if (ans == (1 << 30)) puts("Help!");
		else printf("%d\n", ans);
	}
};

int main()
{
	while (!Solve().is_last_query);

	return 0;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

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

const double PI=acos(-1.0);

int main()
{   
    double a, b, h, m;
    cin >> a >> b >> h >> m;
    double th = (60*h+m)/720*2*PI;
    double tm = 2*PI*m/60;
    double ans = a*a + b*b - 2*a*b*cos(th-tm);
    ans = sqrt(ans);
    printf("%.10f\n", ans);

    return 0;
}


Measured memory_bytes: 4228
C=[]

C.append(list(map(int, input().split())))
C.append(list(map(int, input().split())))
C.append(list(map(int, input().split())))


#print(max(max(C[0],C[0],C[0])))

res=False

for a1 in range(0,min(C[0])+1):
        b1=C[0][0] - a1
        b2=C[0][1] - a1
        b3=C[0][2] - a1

        if C[1][0] - b1 == C[1][1] - b2 == C[1][2] - b3:
                if C[2][0] - b1 == C[2][1] - b2 == C[2][2] - b3:
                        res=True
                        break

if res:
        print("Yes")
else:
        print("No")

Measured memory_bytes: 3064
from collections import defaultdict
import sys
input = lambda: sys.stdin.readline().rstrip()

M = 998244353
B = pow(10, 18, M)
N = int(input())

def geometric_mod(a, r, m, n):
  x = a
  for i in range(n):
    yield x
    x = (x*r)%m

BB = list(geometric_mod(1, B, M, N+2))

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
      sum_g[g[i]] = (sum_g[g[i]] + BB[i]) % M
      sum_g[0]  = (sum_g[0] - BB[i]) % M

  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = (ret + sx*sy*sz) % M
  return ret


edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Measured memory_bytes: 77432
n=int(input())
mod = 10 ** 9 + 7

def powmod(x, n, mod):

    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K*x)%mod
        x = (x*x) % mod
        n = n // 2

    return (K * x) % mod

sol = powmod(10,n,mod) - 2 * powmod(9,n,mod) + powmod(8,n,mod)
sol = sol % mod
print(sol)


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

typedef long long ll;

int main(){
    int N;cin>>N;
    vector<int> A(N),B(N),C(N);
    for(int i = 0 ;i < N ;i++){
        cin >> A[i];
    }
    for(int i = 0 ;i < N ;i++){
        cin >> B[i];
    }
    for(int i = 0 ;i < N ;i++){
        cin >> C[i];
    }
    sort(A.begin(),A.end());
    sort(C.begin(),C.end());

    ll res = 0;
    for(int i = 0; i < N ; i++){
        ll top = lower_bound(A.begin(),A.end(),B[i]) - A.begin();
        ll bottom  = C.end() - upper_bound(C.begin(),C.end(),B[i]);
        res += top*bottom;
    }

    cout << res << endl;
    return 0;
}

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

#define int long long
using pii = pair<int, int>;
const int MOD = 1e9 + 7;
const int INF = 1 << 29;
const int N = 1e5 + 10;

struct IOsetup{
  IOsetup(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
   cout << fixed << setprecision(20);
  }
}IO;

map<int, int> factor(int n){
  map<int, int> ret;
  for (int i = 2; i * i <= n; i++){
    if (n % i == 0){
      int cnt = 0;
      while (n % i == 0){
        n /= i;
        cnt++;
      }
      ret[i] = cnt;
    }
  }
  if (n > 1) ret[n]++;
  return ret;
}

int add(int a, int b){
  a += b;
  if (a > MOD) a -= MOD;
  return a;
}

int modmul(int a, int b){
  return (a * 1ll * b) % MOD;
}

int powermod(int a, int b, int m = MOD){
  int res = 1ll;
  while (b){
    if (b & 1) res = res * a % m;
    a = a * a % m, b >>= 1;
  }
  return res;
}

int modinv(int a){
  return powermod(a, MOD - 2);
}

int32_t main(){
  map<int, int> p;
  int n;
  cin >> n;
  int ret = 0;
  for (int i = 0; i < n; i++){
    int x;
    cin >> x;
    ret = add(ret, modinv(x));
    auto f = factor(x);
    for (auto &it : f)
      p[it.first] = max(p[it.first], it.second);
  }
  for (auto &it : p)
    ret = modmul(ret, powermod(it.first, it.second));
  ret %= MOD;
  cout << ret << endl;
}

Measured memory_bytes: 896
#include<cstdio>
#include<cstring>
#include<sys/time.h>

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

using namespace std;

typedef long long ll;

ll gettime(){
	struct timeval tv;
	gettimeofday(&tv,NULL);
	return 1000000LL*tv.tv_sec+tv.tv_usec;
}

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

int h,w,B[9][9];

int x2,y2,x3,y3; // 2, 3 それぞれの出発点

int bfs(int x,int y,int tar){
	int d[9][9];
	memset(d,-1,sizeof d);
	d[y][x]=0;
	int Q[81],head=0,tail=0; Q[tail++]=y*w+x;
	while(head<tail){
		int i=Q[head]/w,j=Q[head]%w; head++;
		rep(k,4){
			int yy=i+dy[k],xx=j+dx[k];
			if(0<=yy && yy<h && 0<=xx && xx<w && d[yy][xx]==-1){
				if(B[yy][xx]==tar) return d[i][j]+1;
				if(B[yy][xx]== 0 ) Q[tail++]=yy*w+xx, d[yy][xx]=d[i][j]+1;
			}
		}
	}
	return 777;
}

ll t0;

int ans;
void dfs(int x,int y,int now){
	int hstar=bfs(x,y,2)+bfs(x3,y3,3);
	if(ans<now+1+hstar) return;

	if(ans==777){ // 0.5 秒の間に一つも解が見つからなければ解なし
		ll t1=gettime();
		if(t1-t0>500000){ ans=0; return; }
	}

	// これまでのパスと接したら最適解でないので探索打ち切り
	int cnt=0;
	rep(k,4){
		int xx=x+dx[k],yy=y+dy[k];
		if(0<=xx && xx<w && 0<=yy && yy<h && B[yy][xx]==7) cnt++;
	}
	if(cnt>=2) return;

	rep(k,4){
		int xx=x+dx[k],yy=y+dy[k];
		if(0<=xx && xx<w && 0<=yy && yy<h){
			if(B[yy][xx]==2){
				ans=now+1+bfs(x3,y3,3);
				return;
			}
			else if(B[yy][xx]==0){
				B[yy][xx]=7;
				dfs(xx,yy,now+1);
				B[yy][xx]=0;
			}
		}
	}
}

int main(){
	while(scanf("%d%d",&h,&w),h){
		rep(i,h) rep(j,w) scanf("%d",B[i]+j);

		rep(i,h) rep(j,w) {
			if(B[i][j]==2) x2=j, y2=i;
			if(B[i][j]==3) x3=j, y3=i;
		}
		B[y2][x2]=7; // 訪問済みのマーク

		t0=gettime();
		ans=777;
		dfs(x2,y2,0);
		printf("%d\n",ans<777?ans:0);
	}

	return 0;
}

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

int main(){
int n;
  cin>>n;
  int a=n%10;
  if(a==2 ||a==4 ||a==5 ||a==7 ||a==9){
cout<<"hon"<<endl;}
    else if(a==1||a==0||a==6||a==8){
cout<<"pon"<<endl;}
      else if(a==3){
cout<<"bon"<<endl;}
}

Measured memory_bytes: 3588
@n = gets.chomp.to_i
@output = []

def insert_edge_odd i, n
	opposite_num = n - i
	1.upto(n) do |j|
		@output << "#{i} #{j}" if (i < j && j != opposite_num && i != n)
	end
end

def insert_edge_even i, n
	opposite_num = n + 1 - i
	1.upto(n) do |j|
		@output << "#{i} #{j}" if (i < j && j != opposite_num)
	end
end

if @n.odd?
	1.upto(@n) do |i|
		insert_edge_odd i, @n
	end
else
	1.upto(@n) do |i|
		insert_edge_even i, @n
	end
end

# ------------------------------------------------

print @output.size
print "\n"
@output.each_with_index do |x, idx|
	print x
	print "\n" unless idx == @output.size - 1 
end


Measured memory_bytes: 2172
import java.util.Scanner;

public class Main {
  
  	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		boolean ans = true;
		int N = sc.nextInt();
		
		for(int i=0;i<N;i++){
			int a = sc.nextInt();
			if((a % 2 == 0) && ((a % 3 != 0) && (a % 5 != 0))){
				ans = false;
				break;
			}
		}
		
		if(ans){
			System.out.println("APPROVED");
		}
		else{
			System.out.println("DENIED");
		}
	}
	
}

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

int main() {
  ll n; cin>>n;
  vector<ll> v(n);
  rep(i,n){cin>>v[i];}
  
  ll c=1;
  ll i=0;
  while(i<n-1){
    if(v[i]<v[i+1]){
      while(i<n-1){
        if(v[i]>v[i+1]){c++; i++; break;}
        i++;
      }
    }
    else if(v[i]>v[i+1]){
      while(i<n-1){
        if(v[i]<v[i+1]){c++; i++; break;}
        i++;
      }
    }
    else  if(v[i]==v[i+1]){i++;}
  }
  cout<<c;
} 

Measured memory_bytes: 1024
class Point
  attr_reader :x, :y

  def initialize(x, y)
    @x=x
    @y=y
  end
end

# 1次関数(2点標準形)
def linear(p1, p2)
  lambda { |p| (p2.y-p1.y)*(p.x-p1.x)-(p2.x-p1.x)*(p.y-p1.y) }
end

# 包含判定
def inner?(p, poly)

  temp=poly+[poly[0]]

  a=linear(temp[0], temp[1]).call(p)
  1.upto(temp.size-2) do |i|
    b=a
    a=linear(temp[i], temp[i+1]).call(p)
    if (a*b<0)
      return false
    end
  end
  true
end

gets.to_i.times do

  ps = gets.split.map(&:to_f)

  p1=Point.new(ps[0], ps[1])
  p2=Point.new(ps[2], ps[3])
  p3=Point.new(ps[4], ps[5])
  poly=[p1, p2, p3]

  pa=Point.new(ps[6], ps[7]) # altair
  pv=Point.new(ps[8], ps[9]) # vega

  if inner?(pv, poly)
    unless inner?(pa, poly)
      puts :OK
      next
    end
  else
    if inner?(pa, poly)
      puts :OK
      next
    end
  end

  puts :NG

end

Measured memory_bytes: 6168
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll linf = 1e18;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

int N;
int A[1 << 18 + 1];
int mx1[1 << 18], mx2[1 << 18];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for(int i = 0; i < (1 << N); ++i){
        cin >> A[i];
        mx1[i] = 1 << 18; 
        mx2[i] = 1 << 18; 
    }
    mx1[0] = 0;

    int ans = 0;

    auto update = [](int idx, int v){
        if(A[idx] > A[mx1[v]]) mx2[v] = mx1[v], mx1[v] = idx;
        else if(idx != mx1[v] && A[idx] > A[mx2[v]]) mx2[v] = idx;
    };

    for(int i = 1; i < (1 << N); ++i){
        mx1[i] = i;
        for(int j = 0; j < N; ++j){
            if(i >> j & 1){
                int to = i ^ 1 << j;
                update(mx1[to], i);
                update(mx2[to], i);
            }
        }
        chmax(ans, A[mx1[i]] + A[mx2[i]]);
        cout << ans << endl;
    }
    return 0;
}

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

int main(void){
  string a,b,c;
  cin>>a>>b>>c;
  transform(a.begin(), a.end(), a.begin(), ::toupper);
  transform(b.begin(), b.end(), b.begin(), ::toupper);
  transform(c.begin(), c.end(), c.begin(), ::toupper);
  cout<<a[0]<<b[0]<<c[0]<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>

using namespace std;

int main()
{
    string S;
    cin >> S;
    
    string ans= "";

    for (int i = 0; i < S.length(); i++) {
        ans = ans + "x";
    }
    cout << ans << endl;
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,a,ans[234567];
int main(){
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>a;
        ans[a-1]++;
    }
    for(int i=0;i<n;i++)cout<<ans[i]<<endl;
}


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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    ll N, K;
    cin >> N >> K;
    ll p[N];
    long double sum=0, mx;

    for(ll i = 0; i < N; ++i) cin >> p[i];

    //まずK番目まで合計
    for(ll i = 0; i < K; ++i) sum += (p[i] + 1.0) / 2;
    mx=sum;
    
    //以降差分のみ計算
    for(ll i = K; i < N; ++i){
        sum += (p[i] + 1.0) / 2;
        sum -= (p[i-K] + 1.0) / 2;
        mx = max(mx,sum);
    }

    cout << fixed << setprecision(10) << mx << endl;
}

Measured memory_bytes: 1792
//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <iomanip>
#include <stack>
#include <bitset>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

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

ll sum[1001000];
ll cnt = 0;
ll maxv = 0;
  
int
main(void){  
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  ll n, m;
  cin >> n >> m;
  REP(i, m){
    ll l, r;
    cin >> l >> r;
    l--; r--;
    sum[l]++;
    sum[r+1]--;
  }
  REP(i, n){
    sum[i+1] += sum[i];
    //maxv = max(maxv, sum[i+1]);
  }
  /*
  if(maxv != m){
    cout << 0 << endl;
    return 0;
  }
  */
  REP(i, n+1){
    if(sum[i] == m) cnt++;
  }
  
  cout << cnt << endl;
  
  return 0;
}


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

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}

vector< vector<int> >
gridbfs(vector<string> &st,int sy,int sx,char wall){
  int h=st.size(),w=st.front().size();
  vector<vector<int> > dp(h,vector<int>(w,h*w));
  using P = pair<int, int>;
  deque<P> qu;

  dp[sy][sx]=0;
  qu.emplace_back(sy,sx);

  auto in=[&](int y,int x){return 0<=y&&y<h&&0<=x&&x<w;};

  while(!qu.empty()){
    int y,x;
    tie(y,x)=qu.front();qu.pop_front();

    for(int dy=-1;dy<=1;dy++){
      for(int dx=-1;dx<=1;dx++){
        if(abs(dy)+abs(dx)!=1) continue;
        int ny=y+dy,nx=x+dx;
        if(!in(ny,nx)||st[ny][nx]==wall) continue;
        if(dp[ny][nx]<=dp[y][x]+0) continue;
        dp[ny][nx]=dp[y][x]+0;
        qu.emplace_front(ny,nx);
      }
    }

    for(int dy=-2;dy<=2;dy++){
      for(int dx=-2;dx<=2;dx++){
        int ny=y+dy,nx=x+dx;
        if(!in(ny,nx)||st[ny][nx]==wall) continue;
        if(dp[ny][nx]<=dp[y][x]+1) continue;
        dp[ny][nx]=dp[y][x]+1;
        qu.emplace_back(ny,nx);
      }
    }
  }

  return dp;
}

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int h,w;
  cin>>h>>w;

  int cy,cx;
  cin>>cy>>cx;
  cy--;cx--;

  int dy,dx;
  cin>>dy>>dx;
  dy--;dx--;

  auto st=read<string>(h);
  auto ds=gridbfs(st,cy,cx,'#');
  cout<<(ds[dy][dx]==h*w?-1:ds[dy][dx])<<newl;
  return 0;
}


Measured memory_bytes: 8652
n = int(input())
a = list(map(int, input().split()))
a.sort()
dic = {}
for i in range(n):
    if not a[i] in dic:
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1
op = 0
for key in dic:
    if dic[key] > 1:
        op += dic[key]-1
op = op+1 if op%2==1 else op
print(n-op)

Measured memory_bytes: 62124
#include<bits/stdc++.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険
#define count cout                                      // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define ednl endl                                       // endl誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r) for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k) for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r) for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k) for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

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 (b<a) { a=b; return 1; } return 0; }

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

ll hex2dec(string s){
    ll res = 0;
    rep(i,0,2){
        ll tmp;
        if(s[i] >= 'A' && s[i] <= 'F'){
            tmp = s[i] - 'A' + 10;
        }else{
            tmp = s[i] - '0';
        }
        res += tmp*pow(16,i);
    }
    return res;
}

int main(){
    string a,b;cin>>a>>b;
  	if(a == b) cout << "=" << ednl;
    else{
        ll c = hex2dec(a), d = hex2dec(b);
      	cout << ( c< d ? "<" : ">") << ednl;
    }
}


Measured memory_bytes: 256
#include <stdio.h>

int a,d,n;

int isPrime[1000000];

int solve(){
	int i,c=0;
	for(i=0;c<n;i++){
		if(isPrime[a+d*i])c++;
	}
	i--;
	return a+d*i;
}

int main(void){
	int i,j;
	for(i=2;i<1000000;i++) isPrime[i]=1;
	for(i=0;i<1000000;i++){
		if(isPrime[i]){
			for(j=2;i*j<1000000;j++){
				isPrime[i*j]=0;
			}
		}
	}

	while(scanf("%d %d %d",&a,&d,&n),a|d|n){
		printf("%d\n",solve());
	}

	return 0;
}

Measured memory_bytes: 4504
#include <iostream>
#include <string>
#define ll long long
using namespace std;
int main(){
    ll score=0, x=1, h=1, n;
    int y, b=1;
    string a;
    cin >> a;
    cin >> n;
    y=a.size()-1;
    for(int i=1; i<=y; i++){
        if(a[i]==a[i-1]){
            h++;
        }
    }
    if(h==y+1){
        cout << h*n/2 << endl;
    }
    else{
        for(int i=1; i<=y; i++){
            if(a[i]==a[i-1]){
                b++;
            }
            else{
                score+=b/2;
                b=1;
            }
        }
        score+=b/2;
        while(a[x]==a[x-1]){
            x++;
        }
        if(x%2==1 && a[y]==a[0]){
            x++;
            while(a[y]==a[y-1]){
                y--;
                x++;
            }
            if(x%2==0){
                x=1;
            }
            else{
                x=0;
            }
        }
        else{
            x=0;
        }
        score*=n;
        score+=x*(n-1);
        cout << score << endl;
    }
    return 0;
}   

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

box=[0]*n
ans=[]
for i in range(n,0,-1):
    sum_=0
    for j in range(1,n+1):
        if j*i>n:
            break
        sum_+=box[j*i-1]
    if sum_%2!=a[i-1]:
        box[i-1]=1
        ans.append(i)

print(len(ans))
print(' '.join(list(map(str,ans))))

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

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

int ask(string s) {
    printf("? %s\n", s.c_str());
    fflush(stdout);
    int res;
    scanf("%d", &res);
    return res;
}

void answer(string s) {
    printf("! %s\n", s.c_str());
    exit(0);
}

const int maxl = 128;
string subs[64];
int len;

// solve [l, r)
string dfs(int l, int r) {
    if (r - l == 1) {
        return subs[l];
    }
    int m = (l + r) / 2;
    string A = dfs(l, m);
    string B = dfs(m, r);
    int ap = 0, bp = 0;
    string cur;

    while (ap < A.size() || bp < B.size()) {
        if (ap < A.size()) {
            string cand = cur + A[ap] + B.substr(bp);
            if (ask(cand) == len - cand.size()) {
                cur.pb(A[ap++]);
                continue;
            }
        }
        cur.pb(B[bp++]);
    }
    return cur;
}

int main() {
    string kinds;
    for (char c = 'a'; c <= 'z'; ++c) kinds.pb(c);
    for (char c = 'A'; c <= 'Z'; ++c) kinds.pb(c);
    for (char c = '0'; c <= '9'; ++c) kinds.pb(c);

    int sz = SZ(kinds);
    V<int> freq(sz);

    rep(i, SZ(kinds)) {
        string t(maxl, kinds[i]);
        int r = ask(t);
        freq[i] = maxl - r;
        len += freq[i];
        subs[i] = string(freq[i], kinds[i]);
    }

    string ans = dfs(0, sz);
    answer(ans);

    return 0;
}

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

int Prime(int num);

int main(){
  int n;
  int ans=0;
  cin>>n;
  for(int i=0,a;i<n;i++){
    cin>>a;
    ans+=Prime(a);
  }
  cout<<ans<<endl;
}

int Prime(int num){
  if(num==2)return 1;
  if(num%2==0)return 0;
  for(int i=3;i<=sqrt(num);i+=2){
    if(num%i==0)return 0;
  }
  return 1;
}

Measured memory_bytes: 1160
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int ans = 0;
    int n = sc.nextInt();
    int[] l = new int[n];
    for (int cnt = 0; cnt < n; cnt++) {
      l[cnt] = sc.nextInt();
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < i; j++) {
        for (int k = 0; k < j; k++) {
            if (l[i] != l[j] && l[j] != l[k] && l[k] != l[i]) {
              if (l[i] < (l[j] + l[k]) && l[j] < (l[i] + l[k]) && l[k] < (l[i] + l[j])) {
                ans++;
            }
          }
        }
      }
    }
    System.out.println(ans);
    sc.close();
  }
}


Measured memory_bytes: 36956
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long gcd(long long a, long long b);
long long lcm(long long a, long long b);

int main()
{
	long long a, b, c, d;
	cin >> a >> b >> c >> d;
	a--;

	long long ansb = b;
	long long ansa = a;

	ansb -= b / c;
	ansb -= b / d;
	ansb += b / lcm(c, d);
	ansa -= a / c;
	ansa -= a / d;
	ansa += a / lcm(c, d);

	cout << ansb - ansa << endl;

	return 0;
}

long long gcd(long long a, long long b)
{
	if (a < b) {
		long long t = a;
		a = b;
		b = t;
	}

	long long r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}

	return b;
}

long long lcm(long long a, long long b)
{
	return a * b / gcd(a, b);
}

Measured memory_bytes: 256
from collections import deque

def bfs():
    # すべての点を初期化
    wpCnt = [[int(10**10)] * m for i in range(n)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    sx = Cm-1
    sy = Cn-1

    que = deque([])
    que.append((sy, sx))
    wpCnt[sy][sx] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and wpCnt[nx][ny] > wpCnt[p[0]][p[1]]:
                # 移動できるならキューに入れ、優先的に処理
                wpCnt[nx][ny] = wpCnt[p[0]][p[1]]
                que.appendleft((nx, ny))

        # ワープ方向をループ
        for i in range(-2,3):
            for j in range(-2,3):
                # ワープした後の点を (nxw, nyw) とする
                nxw = p[0] + i
                nyw = p[1] + j

                # ワープが可能かの判定
                if 0 <= nxw < n and 0 <= nyw < m and maze[nxw][nyw] != "#" and 0 <= p[1] < m and 0 <= p[0] < n and wpCnt[nxw][nyw] > wpCnt[p[0]][p[1]] + 1 :
                    # ワープできるならキューに入れる
                    # print(nyw,nxw, p[0],p[1], i,j)
                    wpCnt[nxw][nyw] = wpCnt[p[0]][p[1]] + 1
                    que.append((nxw, nyw))
    return wpCnt

n, m = map(int, input().split())
Cn,Cm = map(int, input().split())
Dn,Dm = map(int, input().split())
maze = [list(input()) for _ in range(n)]

ans = bfs()

# print(ans)
if ans[Dn-1][Dm-1] == 10**10:
    print(-1)
else:
    print(ans[Dn-1][Dm-1])

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

#define sysp system("pause")

typedef long long ll;

int a,b,n;

int main(){
	cin>>n;
	int sli[n];
	for(int i=0;i<n;i++){
		cin>>sli[i];
	}
	int mem=sli[0];
	for(int i=0;i<n-1;){
		if(sli[i]==sli[i+1]){
			a++;
			i+=2;
		}else{
			i++;
		}
	}
	cout<<a<<endl;
	sysp;
} 

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

int main(){
  string S;
  int K;
  cin >> S >> K;
  vector<long long> L;
  long long l = 0;
  for(size_t i = 0; i+1 < S.length(); ++i){
    if(S[i] == S[i+1]) ++l;
    else{
      L.push_back(l);
      l = 0;
    }
  }
  L.push_back(l);
  size_t ll = S.length();
  if(L[0]+1 == ll){
    cout << (ll*K)/2 << endl;
    return 0;
  }
  // for(auto l : L)
  //   cerr << l << " ";
  // cerr << endl;
  long long ans = 0;
  for(size_t i = 1; i+1 < L.size(); ++i){
    ans += (L[i]+1)/2;
  }
  ans *= K;
  // cerr << ans << endl;
  if(S[0] == S.back()){
    ans += (L[0]+1)/2;
    ans += (L.back()+1)/2;
    // cerr << ans << endl;

    S += S;
    while(ll < S.length()){
      if(S[ll] == S[ll-1]) ++l, ++ll;
      else break;
    }
    // L.push_back(l);
    //cerr << l << endl;
    ans += (l+1)/2*(K-1);
  }else{
    ans += ((L[0]+1)/2 + (L.back()+1)/2)*K;
  }
  cout << ans << endl;
}


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

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0;i < n;i++) {
		cin >> a[i];
	}
	int ans = 0;
	for (int i = 0;i < n;i++) {
		while (a[i] % 2 == 0) {
			a[i] /= 2;
			ans++;
		}
	}
	cout << ans << endl;

	return 0;
}

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

int main(){
   
   int N,T;
   cin >> N >> T;
   int data[N];
   ll ans = T;
   for(int i=0;i<N;i++) cin >> data[i];
    
   for(int i=0;i<N-1;i++){
       ans += (min(data[i]+T,data[i+1]) - data[i]);
   }
   cout << ans << endl;
}

Measured memory_bytes: 4320
N, M = map(int, input().split())

A = []
B = []
C = []
for i in range(M):
    a, b, c = map(int, input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)

INF = 10**9
# dist is minimal distance between node i and node j
dist = [[INF if i != j else 0 for i in range(N)] for j in range(N)]

# calculate minimal distance of all nodes combination
for i in range(M):
    dist[A[i]][B[i]] = min(dist[A[i]][B[i]], C[i])
    dist[B[i]][A[i]] = min(dist[B[i]][A[i]], C[i])

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = M
for i in range(M):
    # isShortest = False
    for j in range(N):
        if dist[j][A[i]] + C[i] == dist[j][B[i]]:
            ans = ans - 1
            break

print(ans)


Measured memory_bytes: 3428
#include <stdio.h>
int main(void){
	int N,num[101]={0},i,j,cnt=0,mini,temp;
	scanf("%d",&N);
	for(i=0;i<N;i++){
		scanf("%d",&num[i]);
	}
	for(i=0;i<N;i++){
		mini=i;
		for(j=i;j<N;j++){
			if(num[j]<num[mini]){
				mini=j;
			}
		}
		if(num[i]>num[mini]){
			temp=num[i];
			num[i]=num[mini];
			num[mini]=temp;
			cnt++;
		}
	}
	for(i=0;i<N;i++){
		printf("%d",num[i]);
		if(i!=N-1) printf(" ");
	}
	printf("\n%d\n",cnt);
	return 0;
}



Measured memory_bytes: 2736
n=int(input())

latest_dic = {}
array   = []
answers = []

for i in range(n):
    c = int(input())
    array.append(c)

for i,c in enumerate(array):
    if i==0:
        answers.append(1)
        latest_dic[c] = 1
    else:
        cnt = answers[i-1]
        if (c in latest_dic) and (c!=array[i-1]):
            cnt += latest_dic[c]
            answers.append(cnt)
        else:
            answers.append(cnt)
        latest_dic[c]=cnt

print(answers[n-1]%(10**9 +7))


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

int main() { long N; cin >> N; vector<long> a(N);
for(int i = 0; i < N; i++) cin >> a.at(i);

int cnt = 0;

for(int i = 0; i < N; i++){
  while(a.at(i) % 2 == 0){
    a.at(i) = a.at(i) / 2;
    cnt++;
  }
}





cout << cnt << endl;
  return 0;
 
}


Measured memory_bytes: 384