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

int main(int argc, char const *argv[])
{
    int N;
    cin >> N;
    vector<int> X(N);

    for (int i = 0; i < N; i++)
    {
        cin >> X.at(i);
    }
    int sum = 0;
    for (int i = 0; i < N; i++)
    {
        sum += X.at(i);
    }
    int a = sum / N;
    int b = a + 1;
    int p = 0;
    int q = 0;
    for (int i = 0; i < N; i++)
    {
        p += ((X.at(i) - a) * (X.at(i) - a));
        q += ((X.at(i) - b) * (X.at(i) - b));
    }
    cout << ((p < q) ? p : q) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
#define fast                                                                   \
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define ll long long
#define f(i, n) for (int i = 0; i < n; i++)
#define fo(i,a,n) for (i = a; i <= n; i++)
#define F first
#define S second
#define pii pair<int,int>
#define sz size()
#define all(v) v.begin(),v.end()
#define pb push_back
#define pf push_front    
#define PB pop_back
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<int>
#define mp make_pair
#define mod 1000000007
typedef unsigned long long ull;
const int N = 200005;
const int MOD = 998244353 ;




void solve(){
    int h, cnt = 1, sum = 0;
    cin>>h;
    while(cnt <= h){
        sum += cnt;
        cnt *= 2;
    }
    cout<<sum;
}

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


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

using namespace std;

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

int n;
vec<ll> a;

ll ret(ll p) {if (p < 0) return - p; else return p;}

int main(void)
{
	cin >> n;
	a.resize(n);
	ll sum = 0;
	rep(i, n) {
		cin >> a[i];
		sum += a[i];
	}
	ll s = 0;
	ll min = ret(sum - 2 * a[0]);
	rep(i, n - 1) {
		s += a[i];
		if (ret(sum - 2 * s) < min) min = ret(sum - 2 * s);
	}
	cout << min << endl;
	return 0;

}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <string.h>
#include <stack>
#include <set>

const int maxN = 1e5 + 9;

using namespace std;
typedef long long ll;

int n, arr[maxN], m;

map<int, int> mp;

//1, -2, 4, -8, 16, -32
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    
    ll sm = 0;
    
    int md = 0;
    
    for(int i = n - 1; i >= 0; i--){
        mp[md]++;
        md = (md + m - arr[i] % m) % m;
        sm += mp[md];
    }
    
    cout << sm << '\n';
    
}


Measured memory_bytes: 3584
# include <iostream>
# include <cstdio>
# include <algorithm>
# include <queue>
# include <vector>
# include <cstring>

using namespace std;

int A[100][100];
int B[100][100];
int dp[100][100][20000];
const int mid = 10000;
int H,W;
int main(void){
    // freopen("aaa.in","r",stdin);
    scanf("%d%d",&H,&W);
    for (int i=1;i<=H;i++)
        for (int j=1;j<=W;j++)
            scanf("%d",&A[i][j]);
    for (int i=1;i<=H;i++)
        for (int j=1;j<=W;j++)
            scanf("%d",&B[i][j]);
    dp[1][1][mid+A[1][1]-B[1][1]] = 1;
    dp[1][1][mid+B[1][1]-A[1][1]] = 1;
    for (int i=1;i<=H;i++)
        for (int j=1;j<=W;j++)
            for (int k=mid-6400;k<=mid+6400;k++){
                int cha = A[i][j]-B[i][j];
                dp[i][j][k]|=dp[i-1][j][k-cha];
                dp[i][j][k]|=dp[i-1][j][k+cha];
                dp[i][j][k]|=dp[i][j-1][k+cha];
                dp[i][j][k]|=dp[i][j-1][k-cha];     
            }
    int ans = 0;
    for (int i=0;i<=6400;i++)
    if (dp[H][W][mid+i]||dp[H][W][mid-i]) {ans = i;break;}
    printf("%d\n",ans);        
    return 0;
}



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

const int maxn = 1e5+10;
const long long M = 1e9+7;
typedef long long ll;

int n, a, b, c, powa[maxn], powb[maxn], inv[maxn], Cn[maxn<<1];
long long ans;

int main() {
	scanf("%d%d%d%d", &n, &a, &b, &c);
	inv[1] = 1;
	for (int i = 2; i < maxn; ++i) {
		inv[i] = (M-(M/i)*inv[M%i]%M)%M;
	}
	powa[0] = powb[0] = 1;
	for (int i = 1; i <= n; ++i) {
		powa[i] = (ll)powa[i-1]*a%M*inv[a+b]%M;
		powb[i] = (ll)powb[i-1]*b%M*inv[a+b]%M;
	}
	Cn[n-1] = 1;
	for (int i = n; i < 2*n; ++i) {
		Cn[i] = (ll)Cn[i-1]*i%M*inv[i-n+1]%M;
	}
	for (int i = n; i < 2*n; ++i) {
		ans = (ans+(ll)i*Cn[i-1]%M*(((ll)powa[n]*powb[i-n]+(ll)powb[n]*powa[i-n])%M))%M;
	}
	ans = ans*100%M*inv[100-c]%M;
	printf("%lld\n", ans);
}


Measured memory_bytes: 1920
#include<iostream>
#include<vector>
#include<string>
#include<cstdio>

using namespace std;
using T = int;

struct WeightedUnionFind {
    vector<int> parent;
    vector<T> weight;
    vector<int> myrank;
    //親は小さい
    WeightedUnionFind(int n) : parent(n,-1), weight(n,0), myrank(n,0) { }
    bool Find(int x, int y){
        return find_root(x) == find_root(y); 
    }
    int find_root(int x){
        if(parent[x] < 0){
            return x;
        }else{
            int pare = find_root(parent[x]);
            weight[x] += weight[parent[x]];
            return parent[x] = pare;
        }
    }
    T Weight(int x){
        find_root(x);
        return weight[x];
    }
    //x <= y 
    bool Union(int x, int y, int w){
        w += Weight(x);
        w -= Weight(y);
        x = find_root(x); y = find_root(y);

        if(x != y){
            if(myrank[y] < myrank[x]){
                swap(x,y); w = -w;
            }
            parent[x] += parent[y]; parent[y] = x;
            weight[y] = w;
            if(myrank[x] == myrank[y]) myrank[x]++;
            return true;
        }else{
            return false;
        }
    }
    int size(int x){
        return -parent[find_root(x)];
    }
    T diff(int x, int y){
        return Weight(x) - Weight(y);
    }
};

int main() {
    int N, M;
    int a, b, d;
    //string str;
    char str;
    for(;;){
        cin >> N >> M;
        
        if (N==0) break;
        WeightedUnionFind wuf(N);
        for(int i=0; i< M ;i++){
            cin >> str;
            if(str=='!'){
                cin >> a >> b >> d;
                a--;b--;
                wuf.Union(a,b,d);
            }else{
                cin >> a >> b;
                a--;b--;
                if(wuf.Find(a,b)){
                    cout << wuf.diff(b,a) << "\n";
                }else{
                    cout << "UNKNOWN" << "\n";
                }
            }
        }
    }
    return 0;
}



Measured memory_bytes: 4880
/*
このコード、と～おれ!
Be accepted!
  ∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
　　　　　　　　　　(¸.·´ (¸.·'* ☆
*/

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printfin(a) printf(a ? "possible\n" : "inposible\n")
#define all(x) (x).begin(), (x).end()
using ll = long long;

//マクロとかここまで

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>

using namespace std;

int main() {
	
	int a, b, c;
	scanf("%d%d%d", &a,&b,&c);
	printyn(max(a,max(b,c)) == a + b + c - max(a, max(b,c)));
	return 0;
}
	    

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

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

    cout << 100 << " " << 100 << "\n";
	
	int cnt = b-1;
	rep(i, 50) {
		rep(j, 100) {
			if(i%2 == 0 && j%2 == 0 && cnt > 0) {
                cout << '#';
                cnt--;
            }
			else {
                cout << '.';
            }
		}
		cout << "\n";
	}

	cnt = a-1;
	rep(i, 50) {
		rep(j, 100) {
			if(i%2 == 1 && j%2 == 0 && cnt > 0) {
                cout << '.';
                cnt--;
            }
			else {
                cout << '#';
            } 
		}
		cout << "\n";
	}

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i, n) for (ll i = 0; i < (n); i++)
#define fori(i, b, e) for (ll i = (b); i < (e); i++)
#define forr(i, b, e) for (ll i = (b); i >= (e); i--)
#define allele(v) v.begin(), v.end()
#define fi first
#define se second
#define Mat vector<vector<ll>>
#define Arr vector<ll>

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, x;
    cin >> n >> x;
    int cur = 0, z;
    forn(i, n)
    {
        cin >> z;
        cur += z;
        if (cur > x)
            return cout << (i + 1), 0;
    }
    cout << (n + 1);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>

using ll = long long;

int main() {
    int X;
    std::cin >> X;
    if (X == 3 || X == 5 || X == 7) {
        std::cout << "YES" << std::endl;
    }
    else {
        std::cout << "NO" << std::endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <unordered_map>
#include <queue>
#include <set>

using namespace std;

#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;


int main(){
    int n;
    cin >> n;
    string s;
    vector<int> memory(5, 0);
    rep(i, n) {
        cin >> s;
        switch(s[0]){
            case 'M':
                memory[0]++;
                break;
            case 'A':
                memory[1]++;
                break;
            case 'R':
                memory[2]++;
                break;
            case 'C':
                memory[3]++;
                break;
            case 'H':
                memory[4]++;
                break;
            default:
                break;
         }
    }
    long long answer = 0, count;
    rep(i, 1 << 5){
        if (__builtin_popcount(i) == 3){
            count = 1;
            rep(j, 5) {
                if (i & (1 << j)) count *= memory[j];
            }
            answer += count;
        }
    }
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <unordered_map>
#include <set>
#include <fstream>
#include <cstring>
#include <climits>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;

#define ll long long
#define mod 1000000007

double dp[301][301][301];

double solve_ite(int* a, int n, int one, int two, int three) {

	for (int i = 0; i <= three; i++) {
		for (int j = 0; j <= two + three; j++) {
			for (int k = 0; k <= one + two + three; k++) {
				if (i != 0 or j != 0 or k != 0) {
					dp[i][j][k] = n / (double)(i + j + k);
				}
				if (k > 0) {
					dp[i][j][k] += k / (double)(i + j + k) * dp[i][j][k - 1];
				}
				if (j > 0) {
					dp[i][j][k] += j / (double)(i + j + k) * dp[i][j - 1][k + 1];
				}
				if (i > 0) {
					dp[i][j][k] += i / (double)(i + j + k) * dp[i - 1][j + 1][k];
				}
			}
		}
	}
	return dp[three][two][one];
}

int main() {
  
	int n;
	cin >> n;
	int a[n];
	int one = 0, two = 0, three = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		if (a[i] == 1)
			one++;
		if (a[i] == 2)
			two++;
		if (a[i] == 3)
			three++;
	}
	for (int i = 0; i < 301; ++i)
		for (int j = 0; j < 301; ++j)
			for (int k = 0; k < 301; ++k)
				dp[i][j][k] = 0;
	cout << setprecision(14) << solve_ite(a, n, one, two, three);

	return 0;
}

Measured memory_bytes: 213248
#include<stdio.h>
#include<string.h>
#include<math.h>

#define N 1000000007

int main(void) {
	int n;
	long long k;
	int a[2001] = { 0 };
	int count =  0 ;
	long long ans = 0;

	scanf("%d %lld", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < n ; i++) {
		for (int j = i + 1; j < n; j++) {
			if (a[i] > a[j]) ans++;
		}
		for (int j = 0; j < n; j++) {
			if (a[i] > a[j])count++;
		}
	}
	//printf("ans=%lld\n", ans);
	ans = ans * k % N;
	//printf("ans=%lld\n", ans);
	ans = (ans + (k * (k - 1) / 2%N) * count) % N;
	printf("%lld", ans);
	return 0;
}


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

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define MIN(a,b) ((a)>(b)? (b): (a))
#define MAX(a,b) ((a)<(b)? (b): (a))

const long long INF = 1LL << 60;
typedef unsigned long long ll;
const long long MOD = 1000000000 + 7;

int main(){
    int x;
    cin >> x;
    if(x < 1200) cout << "ABC" << endl;
    else cout << "ARC" << endl;
    return 0;
}

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

int main() {
  int N, K;
  int R, S, P;
  string T;
  int i, j;
  int count = 0;
  cin >> N >> K;
  cin >> R >> S >> P;
  cin >> T;
  for (i = 0; i < K; i++) {
    for (j = i; j < T.size(); j+= K) {
      if (T[j] == 'r')
        count += P;
      else if (T[j] == 's')
        count += R;
      else
        count += S;
      if (j < T.size() - K)
        if (T[j] == T[j+K])
          j += K;
    }
  }
  cout << count << endl;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
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;}

ll N, K;
ll A[510];

int main(){
    cin >> N >> K;
    ll sum = 0;
    for(ll i = 0; i < N; i++){
        cin >> A[i];
        sum += A[i];
    }
    vector<ll> div;
    for(ll j = 1; j * j <= sum; j++){
        if(sum % j == 0){
            div.push_back(j);
            div.push_back(sum / j);
        }
    }
    sort(div.begin(), div.end());
    ll ans = 1;
    for(auto u : div){
        vector<ll> d;
        ll g = 0;
        for(ll i = 0; i < N; i++){
            ll tmp = (((A[i] - 1) / u) + 1) * u - A[i];
            d.push_back(tmp);
            g += tmp;
        }
        sort(d.begin(), d.end());
        ll f = g / u;
        ll cnt = 0;
        for(ll i = 0; i < N - f; i++){
            cnt += d[i];
        }
        if(cnt <= K) ans = u;
    }
    cout << ans << endl;
    return 0;
}

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

#define pb push_back
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    string s; cin >> s;
    int c = count(all(s), 'A');
    if (c == 3 || c == 0) cout << "No\n";
    else cout << "Yes\n";
}

Measured memory_bytes: 256
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define MOD 1000000007

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
signed main() {
  ios::sync_with_stdio(false);
  int n;
  string s;
  cin >> n >> s;
  long long alphabet[26] = {};
  REP(i, n) {
      alphabet[s[i] - 'a']++;
  }
  long long ans = 1;
  REP(i, 26) {
      ans *= alphabet[i]+1;
      ans %= MOD;
  }
  cout << ans - 1 << endl;
  return 0;
}


Measured memory_bytes: 512
#include <iostream>

using namespace std;

int main() {
  int nbr;

  cin >> nbr;
  cout << nbr << ":";
  for (int i = 2; i*i <= nbr; i++) {
    while(nbr%i == 0) {
      cout << " " << i;
      nbr/=i;
    }
  }
  
  if (nbr!=1)
    cout << " " << nbr;
  cout << endl;
}


Measured memory_bytes: 3104
#include <iostream>
#include <cstdio>
#include <math.h>

using namespace std;

typedef long long int ll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
const int MOD = 1000000007;
const int INF = INT_MAX;



int main(int argc, char const *argv[])
{
    int n;
    cin >> n;

    int a[4] = {10};
    for (int i=0; i < 4; i++){
        a[i] = n%10;
        n /= 10;
    }


    int flag = 0;
    if (a[1] == a[2]){
        if (a[0] == a[1]){
            flag = 1;
        }
        else if (a[2] == a[3]){
            flag = 1;
        }
    }

    if (flag == 0){
        cout << "No" << endl;
    }
    else {
        cout <<  "Yes" << endl;
    }

    return 0;
}




//              g++ -std=c++1z  

Measured memory_bytes: 256
import java.util.*; 
import static java.util.Arrays.*;
public class Main {

	/**
	 * @param args
	 */
	static Scanner sc = new Scanner(System.in);
	static int array[] = new int[10];	
	static int i=0;
	
	public static void main(String[] args) {

		
		read();
		solve();
		
		
	}
	
	
	static boolean read(){

		while(sc.hasNextInt()){
			array[i] = sc.nextInt();
			i++;
		}
				
		return true;
	}
	
	
	static void solve(){
		sort(array);
		
		
		for(int i=array.length-1; i>=array.length-3; i--){
			System.out.println(array[i]);
		}
	}
	
	

}

Measured memory_bytes: 12000
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
using namespace std;

double average(double a, double b) { return (a + b) / 2.0; }

int main() {
    int n;
    cin >> n;
    vector<double> v;
    double temp;
    rep(i, n) {
        cin >> temp;
        v.push_back(temp);
    }

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

    double ans = v[0];
    rep(i, n) { ans = average(ans, v[i]); }

    cout << fixed << setprecision(15) << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
	vector<int> A(3);
	for (int i = 0; i < 3; i++)
		cin >> A[i];

	sort(A.begin(), A.end());
	cout << (A[2] - A[1]) + (A[1] - A[0]) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

struct P {
    bool operator<(const P& p) const {
        return b > p.b;
    }
    int a, b;
};

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

    int n, h;
    cin >> n >> h;

    vector<P> p(n);
    int m = 0;
    for (int i = 0; i < n; i++) {
        cin >> p[i].a >> p[i].b;
        if (p[i].a > m) m = p[i].a;
    }
    sort(p.begin(), p.end());

    int k = 0;
    for (int i = 0; i < n; i++) {
        h -= max(p[i].b, m);
        k++;
        if (h <= 0) break;
    }

    if (h > 0) {
        k += (h + m - 1) / m;
    }

    cout << k << endl;

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
stack<int> s;
signed main(void){
	ios::sync_with_stdio(false);
	int x;
	while(cin>>x){
		if(x)
			s.push(x);
		else{
			cout<<s.top()<<endl;
			s.pop();
		}
	}
}

Measured memory_bytes: 1200
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int>a(n);
    int m = -1;
    int z = -1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        m = max(m, a[i]);
    }
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == m) {
            count++;
        }
        else {
            z = max(z, a[i]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (count == 1) {
            if (a[i] == m) {
                cout << z << endl;
            }
            else {
                cout << m << endl;
            }
        }
        else {
            cout << m << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 2432
#include<cstdio>
using namespace std;
int N,A[200005],a[200005],l=1,r=200000,mid;
bool check(int n)
{
	int re=-1;
	for(int i=1;i<=N*2-1;i++)
	if(A[i]>=n)
	a[i]=1;
	else
	a[i]=0;
	for(int i=1;i<=N-1;i++)
	{
		if(a[N+i]==a[N+i-1])
		{
			re=a[N+i];
			break;
		}
		if(a[N-i]==a[N-i+1])
		{
			re=a[N-i];
			break;
		}
	}
	if(re!=-1)
	return re;
	else
	return a[1];
}
int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N*2-1;i++)
	scanf("%d",&A[i]);
	while(l+1<r)
	{
		mid=(l+r)/2;
		if(check(mid))
		l=mid;
		else
		r=mid;
	}
	printf("%d",l);
	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
using namespace std;
const ll mod=1e9+7;
ll x[110],y[110];
main(){
  char f[110],f2[110];
  bool p=true,q=true;
  string s,t;
  cin>>s>>t;
  ll ssl=s.length();
  rep(i,0,ssl){
    ll tmp=s[i]-'a';
    if(x[tmp]>=1&&f[tmp]!=t[i]){p=false;break;}
    else {x[tmp]++;f[tmp]=t[i];}
    //cout<<tmp<<endl;
  }
  rep(i,0,ssl){
    ll tmp=t[i]-'a';
    if(y[tmp]>=1&&f2[tmp]!=s[i]){p=false;break;}
    else {y[tmp]++;f2[tmp]=s[i];}
   // cout<<tmp<<endl;
  }
  if(p&&q)cout<<"Yes";
  else cout<<"No";
}

Measured memory_bytes: 776
import java.util.*;

public class Main{
    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);

		String s = sc.next();
		long k = sc.nextLong();

        long count = 1;
        long in = 0;
        long head = 0;
        long tail = 0;
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i) == s.charAt(i - 1)) count++;
            else{
                if(head == 0) head = count;
                else in += count / 2;
                count = 1;
            }
        }
        if(head == 0) head = count;
        else tail = count;

        // System.out.println("head " + head);
        // System.out.println("in " + in);
        // System.out.println("tail " + tail);

        if(tail == 0) System.out.println(s.length() * k / 2);
        else if(s.charAt(0) == s.charAt(s.length() - 1)) System.out.println(in * k + (head + tail) / 2 * (k - 1) + head / 2 + tail / 2);
        else System.out.println(in * k + head / 2 * k + tail / 2 * k);

    }

}


Measured memory_bytes: 21972
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
#define REP(i,n) for(int i=0;i<n;i++)
typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
    int K, N;
    string S;
    cin >> N >> S >> K;
    string ans(N, 'a');
    for(int i = 0; i < N; i++){
        if(S[i] == S[K-1]){
            ans.at(i) = S[K-1];
        }else{
            ans.at(i) = '*';
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define vi vector<int>
#define vl vector<ll>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define lop(i,a,b) for(ll i=a;i<b;i++)
#define endl "\n"
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
using namespace std;

void func(){
    ll n,tot=0;
	cin>>n;
	for(int i=1;i<n;i++)tot+=(n-1)/i;
	cout<<tot<<endl;
}

int main(){
    fastio;
    int t=1;
    //cin>>t;
    while(t--){
        func();
    }
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

int main(){
    int N;cin>>N;
    vector<vector<ll>> a(2,vector<ll>(N));
    REP(i, N){
        cin >> a[0][i];
        a[1][i]=-a[0][i];
    }
    
    REP(k,2) {
        vector<pair<int,int>> ans;
        REP(_,2*N){
            auto M=max_element(All(a[k]));
            bool ok=true;
            if(k==0) REP(i,N-1) if(a[0][i]>a[0][i+1]){
                ok=false;
                a[0][i+1]+=*M;
                ans.push_back({M-a[0].begin(),i+1});
                break;
            }
            if(k==1) for(int i=N-1;i>0;--i) if(a[1][i-1]<a[1][i]){
                ok=false;
                a[1][i-1]+=*M;
                ans.push_back({M-a[1].begin(),i-1});
                break;
            }
            if(ok){
                cout<<ans.size()<<endl;
                for(auto e:ans) cout<<e.first+1<<" "<<e.second+1<<endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
n,m,x = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
l = 0
(0..x).each do |i|
  if a.include?(i)
    l += 1
  end
end
r = 0
(x..n).each do |i|
  if a.include?(i)
    r += 1
  end
end
puts r >= l ? l : r

Measured memory_bytes: 1788
#include "bits/stdc++.h"
using namespace std;
typedef long long int lint;
typedef pair<lint, lint> plint;
typedef pair<double long, double long> pld;
#define Alint(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1ll << (n))
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
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; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first - r.first, l.second - r.second); }
const lint MOD = 998244353, INF = 1e18;

struct edge { lint to, cap, rev; };

vector<edge> Graph[20000];
int level[20000];
int iter[20000];
void add_edge(lint from, lint to, lint cap) {
	Graph[from].push_back({ to, cap, SZ(Graph[to]) });
	Graph[to].push_back({ from, 0, SZ(Graph[from]) - 1 });
}
void bfs(lint s) {
	memset(level, -1, sizeof(level));
	queue<lint> que;
	que.push(s);
	level[s] = 0;
	while (!que.empty()) {
		lint v = que.front(); que.pop();
		REP(i, SZ(Graph[v])) {
			edge& e = Graph[v][i];
			if (e.cap > 0 && level[e.to] < 0) {
				level[e.to] = level[v] + 1;
				que.push(e.to);
			}
		}
	}
}

lint dfs(lint v, lint t, lint f) {
	if (v == t) return f;
	for (int& i = iter[v]; i < SZ(Graph[v]); i++) {
		edge& e = Graph[v][i];
		if (e.cap > 0 && level[v] < level[e.to]) {
			lint d = dfs(e.to, t, min(f, e.cap));
			if (d > 0) {
				e.cap -= d;
				Graph[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

lint max_flow(lint s, lint t) {
	lint flow = 0;
	for (;;) {
		bfs(s);
		if (level[t] < 0) return flow;
		memset(iter, 0, sizeof(iter));
		lint f;
		while ((f = dfs(s, t, INF)) > 0) {
			flow += f;
		}
	}
}


lint H, W;
char c;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(false);
	lint N = 500;
	plint st, ed;
	cin >> H >> W;
	REP(i, H) {
		REP(j, W) {
			cin >> c;
			lint xi = 1 + j, yi = 1 + W + i;
			if (c == 'o') {
				add_edge(xi, yi, 1);
				add_edge(yi, xi, 1);
			}
			else if (c == 'S') {
				add_edge(0, xi, INF);
				add_edge(0, yi, INF);
			}
			else if (c == 'T') {
				add_edge(xi, 1 + W + H, INF);
				add_edge(yi, 1 + W + H, INF);
			}
		}
	}
	lint ans = max_flow(0, 1 + W + H);
	if (ans >= 300) cout << -1 << endl;
	else cout << ans << endl;
}


Measured memory_bytes: 2176
# -*- coding: utf-8 -*-
import heapq

N, M = map(int, input().split())
MAX = float("inf")

nodes = [[] for i in range(N+1)]

for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    nodes[u].append(v)

S, T = map(int, input().split())
S -= 1
T -= 1

# init
d = [
    [MAX for i in range(N)],
    [MAX for i in range(N)],
    [MAX for i in range(N)],
]
d[0][S] = 0
queue = []
heapq.heappush(queue, [0, 0, S])

while queue:
    p, m, n = heapq.heappop(queue)
    if m == 0 and n == T:
        print(int(p/3))
        quit()
    for to in nodes[n]:
        if d[(m+1) % 3][to] > d[m][n] + 1:
            d[(m+1) % 3][to] = d[m][n] + 1
            heapq.heappush(queue, [
                d[(m+1) % 3][to],
                (m+1) % 3,
                to
            ])

print(-1)


Measured memory_bytes: 30056
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,k,r,s,p,res=0;
    string t;
    cin>>n>>k>>r>>s>>p>>t;
    for(ll qc=0;qc<k;qc++){
        vector<ll> v;
        v.push_back(-1);
        for(ll j=qc;j<n;j+=k)
        if(t[j]=='r')
        v.push_back(0);
        else if(t[j]=='p')
        v.push_back(1);
        else
        v.push_back(2);
        ll m=v.size();
        ll dp[m][3];
        dp[0][0]=dp[0][1]=dp[0][2]=0;
        for(ll i=1;i<m;i++){
            dp[i][0]=max(dp[i-1][1],dp[i-1][2]);
            dp[i][1]=max(dp[i-1][0],dp[i-1][2]);
            dp[i][2]=max(dp[i-1][0],dp[i-1][1]);
            if(v[i]==0)
            dp[i][1]+=p;
            else if(v[i]==1)
            dp[i][2]+=s;
            else
            dp[i][0]+=r;
        }
        res+=max(dp[m-1][0],max(dp[m-1][1],dp[m-1][2]));
    }
    cout<<res;
}

Measured memory_bytes: 3572
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AtCoder solver = new AtCoder();
        solver.solve(1, in, out);
        out.close();
    }

    static class AtCoder {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int rate = in.nextInt();

            if (rate < 1200) {
                out.println("ABC");
            } else {
                out.println("ARC");
            }
        }

    }
}



Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
int main(){
  int q;
  int z,p,x;
  deque<int> d={};
  cin>>q;
  for(int i=0;i<q;i++){
    cin>>z;
    if(z==1){
      cin>>p;
      cout<<d[p]<<endl;
    }
    else{
      if(z==2){
	cin>>p;
	if(p){
	  d.pop_back();
	}
	else{
	  d.pop_front();
	}
      }
      else{
	cin>>p>>x;
	if(p){
	  d.push_back(x);
	}
	else{
	  d.push_front(x);
	}
      }
    }
  }
  return 0;
}



Measured memory_bytes: 4680
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
using namespace std;
  
int main () {
  int n, t;
  cin >> n >> t;
  vector<pair<int,int>> p;
  rep(i,n) { 
    int a, b;
    cin >> a >> b;
    p.push_back(make_pair(a,b));
  }
  sort(p.begin(),p.end());
  int ans = 0;
  rep(i,n) {
    if(p.at(i).second <= t) {
      ans = p.at(i).first;
      break;
    }
  }
  if(ans == 0)
    cout << "TLE";
  else 
    cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define rrep(i, a, b) for (int i = (a); i < (b); ++i)
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using tl = tuple<ll, ll, ll>;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) {if (a > b) { a = b; return true; } return false; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    string s, t; cin>>s>>t;
    ll n = sz(s);
    ll m = sz(t);
    ll ans = LINF;
    rep(i, n - m + 1) {
        ll cnt = 0;
        rep(j, m) {
            if (s[i + j] != t[j]) cnt++;
        }
        chmin(ans, cnt);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3652
#include <iostream>
#include <climits>
#include <set>
#include <string>
#include <algorithm>
#include <vector>
#define MAX 1000000007


using namespace std;
#define ll long long
#define dbg if(0)
#define ISRANGE(val,lo,hi) ((lo<=val)&&(val<hi))
/*
変数宣言 
作詞 Ry0um4
唄 任意のユーザー
歌詞：
お前がコードを貼り付ける前に 言っておきたい事がある
かなり厳しい話もするが 俺の本音を聴いておけ
初期化より先に計算してはいけない
初期化より先に計算してはいけない
まとめて定義するな いつも=0にしろ
出来る範囲で 構わないから
忘れてくれるな 文脈も読めないマシンに
未初期化変数を0にできる はずなどないってことを
マシンにはマシンしか できないこともあるけど
それ以外は全部 黙ってお前が書いてこい

(飽きたので省略)
*/


int main(){
    ll ans=0,n;//ここ
    cin >>n;
    if (n<3)ans=0;
    else{
        for(ll i=1;i*i<=n;i++){
            if(n%i==0){
                if(n%(n/i-1)==n/(n/i-1)){
                    ans+=(n/i-1);
                }
            }
        }
    }

    cout <<ans<<endl;

    return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <limits>
template <typename T>
constexpr T INF() { return std::numeric_limits<T>::max() / 16; }
template <typename T, typename V = T>
class LiChaoTree
{
    static std::size_t SZ(const std::size_t n)
    {
        std::size_t ans = 1;
        for (; ans < n; ans <<= 1) {}
        return ans;
    }

public:
    template <typename InIt>
    LiChaoTree(const InIt first, const InIt last)
        : size(std::distance(first, last)), half(SZ(size)), x(size), seg(half << 1, Line{0, 0, true}) { std::copy(first, last, x.begin()); }
    void add(const T a, const T b, const std::size_t lind, const std::size_t rind)
    {
        const Line line{a, b, false};
        for (std::size_t L = lind + half, R = rind + half, sz = 1, left = lind, right = rind; L < R; L >>= 1, R >>= 1, sz <<= 1) {
            if (L & 1) { addLine(line, L++, left, left + sz), left += sz; }
            if (R & 1) { right -= sz, addLine(line, --R, right, right + sz); }
        }
    }
    V query(std::size_t ind) const
    {
        V ans = INF<V>();
        const T X = x[ind];
        for (ind += half; ind > 0; ind >>= 1) { ans = seg[ind].null ? ans : std::min(ans, seg[ind].val(X)); }
        return ans;
    }

private:
    struct Line
    {
        T a, b;
        bool null = true;
        T val(const T x) const { return a * x + b; }
    };

    void addLine(Line l, const std::size_t ind, const std::size_t L, const std::size_t R)
    {
        const std::size_t M = (L + R) / 2;
        if (seg[ind].null) { return (void)(seg[ind] = l); }
        const T lx = x[L], rx = x[R - 1], mx = x[M];
        const bool lunder = l.val(lx) < seg[ind].val(lx), munder = l.val(mx) < seg[ind].val(mx), runder = l.val(rx) < seg[ind].val(rx);
        if (lunder and runder) { return (void)(seg[ind] = l); }
        if (not lunder and not runder) { return; }
        if (munder) { std::swap(seg[ind], l); }
        return lunder != munder ? addLine(l, ind << 1, L, M) : addLine(l, ind << 1 | 1, M, R);
    }

    std::size_t size, half;
    std::vector<T> x;
    std::vector<Line> seg;
};
using ll = long long;
int main()
{
    std::size_t N;
    ll C;
    std::cin >> N >> C;
    std::vector<ll> h(N), dp(N);
    for (std::size_t i = 0; i < N; i++) { std::cin >> h[i]; }
    LiChaoTree<ll> cht(h.begin(), h.end());
    cht.add(-2 * h[0], dp[0] + h[0] * h[0], 0, N);
    for (std::size_t i = 0; i < N; i++) {
        dp[i] = cht.query(i) + h[i] * h[i] + C;
        cht.add(-2 * h[i], dp[i] + h[i] * h[i], 0, N);
    }
    std::cout << dp[N - 1] << std::endl;
    return 0;
}


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

// int/long:		-2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)
// while (getline(cin, S)) {}

// cout <<fixed <<setprecision(10)

// priority_queue<int> q;
// priority_queue<int, vector<int>, less<int>> q; // Default: vector, less
// priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> q;

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

//
// Notes
//
// When specified less than N, try full scan.
// RE: empty vector
// Check Qs
// long/int
// xor -> count each bit
// Check values
// 	1,000,000 -> Loop
// 	100,000	-> vector(int:400KB, long:800KB) 

#define	INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define	MOD 1000000007

#define	Rep0(i, n)	for (int i=0; i<n; i++)
#define	Rep1(i, n)	for (int i=1; i<=n; i++)
#define Sort(P)	sort(P.begin(), P.end())
#define Rev(P)	reverse(P.begin(), P.end())

int	main() {
	int N, M;
	cin >>N >>M;
	vector<vector<int>> P(N+1);
	vector<vector<int>> L;
	Rep0(i, M) {
		int P1, P2;
		cin >>P1 >>P2;
		L.push_back({P1, P2});
		P.at(P1).push_back(P2);
		P.at(P2).push_back(P1);
	}
	vector<bool> PP(N+1, false);
	vector<int> Chain;
	vector<int> Q;
	Chain.push_back(1);
	PP.at(1)=true;
	Q.push_back(P.at(1).at(0));
	if (P.at(1).size()>1)
		Q.push_back(P.at(1).at(1));
	while (!Q.empty()) {
		Rev(Chain);
		int QQ=Q.back();
		while (!PP.at(QQ)) {
			Chain.push_back(QQ); 
			PP.at(QQ)=true;
			Rep0(i, P.at(QQ).size()) {
				int NP=P.at(QQ).at(i);
				if (!PP.at(NP)) {
					QQ=NP;
					break;
				}
			}
			/*
			if (PP.at(QQ)) // If not found, break
				break;
			*/
		}
		Q.pop_back();
	}
	cout <<Chain.size() <<endl;
	Rep0(i, Chain.size()) {
		if (0!=i)
			cout <<' ';
		cout <<Chain.at(i);
	}
	cout <<endl;
	return 0;
}



Measured memory_bytes: 13232
a,b,c=map(int,input().split())
if a==b and b==c and a%2==0:
    print(-1)
else:
    ans=0
    while a%2==0 and b%2==0 and c%2==0:
        tmp=a
        tmp2=b
        a=(b+c)//2
        b=(c+tmp)//2
        c=(tmp+tmp2)//2
        ans+=1
    print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 200003;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const double pi = acos(-1.0);
const double EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

template<typename T>
struct Fast_Foulier_Transform{
    Fast_Foulier_Transform() = default;

    vector<complex<double>> to_complex(vector<T> a){
        vector<complex<double>> ret(sz(a));
        rep(i, sz(a)) ret[i] = complex<double>(a[i], 0.0);
        return ret;
    }

    vector<T> to_T(vector<complex<double>> a){
        vector<T> ret(sz(a), 0);
        rep(i, sz(a)) ret[i] = a[i].real()+0.1;
        //rep(i, sz(a)) ret[i] = a[i].real();
        return ret;
    }

    void fft(vector<complex<double>> &a, int n, bool inverse = false){
        assert((n&(n-1)) == 0);
        a.resize(n);
        rep(i, n){
            int j = 0;
            for(int k = 0; k < __builtin_ctz(n); k++){
                if(i&(1<<k)) j |= 1<<(__builtin_ctz(n)-1-k);
            }
            if(i < j) swap(a[i], a[j]);
        }
        for(int k = 1; k < n; k *= 2){
            rep(i, k){
                complex<double> w = polar(1.0, ((inverse? 1.0 : -1.0)*pi*i)/k);
                for(int j = 0; j < n; j += 2*k){
                    complex<double> s = a[j+i], t = a[j+k+i]*w;
                    a[j+i] = s+t, a[j+k+i] = s-t;
                }
            }
        }
        if(inverse) rep(i, n) a[i] /= n;
    }

    vector<T> convolve(vector<T> a, vector<T> b){
        int n = 1<<(32-__builtin_clz(sz(a)+sz(b)-2));
        vector<complex<double>> A = to_complex(a), B = to_complex(b), C(n);
        fft(A, n), fft(B, n);
        rep(i, n) C[i] = A[i]*B[i];
        fft(C, n, true);
        vector<T> c = to_T(C);
        c.resize(sz(a)+sz(b)-1);
        return c;
    }
};

int main(){
    int N;
    cin >> N;
    int log2[MOD];
    ll now = 1;
    rep(i, MOD-1){
        log2[now] = i;
        now *= 2, now %= MOD;
    }
    vector<ll> a(MOD-1, 0), b(2*MOD-3, 0);
    rep(i, N){
        int A; cin >> A;
        if(A != 0) a[log2[A]]++, b[2*log2[A]]++;
    }
    Fast_Foulier_Transform<ll> fft;
    vector<ll> c = fft.convolve(a, a);
    ll ans = 0;
    rep(i, 2*MOD-3){
        ans += (c[i]-b[i])*now;
        now *= 2, now %= MOD;
    }
    cout << ans/2 << endl;
}

Measured memory_bytes: 50656
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <string>
using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

int N, M;
string line;
vector<string> field;

const int MAX_V = 11000;
const int INF = 1000000009;
int V;
struct edge { int to, cap, cost, rev; };
vector<edge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V];
int preve[MAX_V];

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

void add_edge(int from, int to, int cap, int cost) {
	edge e1 = { to, cap, cost, G[to].size() };
	edge e2 = { from, 0, -cost, G[from].size() };
	G[from].push_back(e1);
	G[to].push_back(e2);
}

void bellman_ford(int s) {
	fill(dist, dist+V, INF);
	dist[s] = 0;
	bool update = true;
	while(update) {
		update = false;
		rep(v,V) {
			if(dist[v] == INF) continue;
			rep(i,G[v].size()) {
				edge& e = G[v][i];
				if(e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
					dist[e.to] = dist[v] + e.cost;
					prevv[e.to] = v;
					preve[e.to] = i;
					update = true;
				}
			}
		}
	}
}

int min_cost_flow(int s, int t, int f) {
	int res = 0;
	while(f > 0) {
		bellman_ford(s);
		if(dist[t] == INF) return -1;

		int d = f;
		for(int v=t; v!=s; v=prevv[v]) {
			d = min(d, G[prevv[v]][preve[v]].cap);
		}

		res += d * dist[t];
		f -= d;
		for(int v=t; v!=s; v=prevv[v]) {
			edge& e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
	}
	return res;
}

void solve() {
	V = N * M + 2;
	int s = V - 2;
	int t = V - 1;
	rep(v,V) G[v].clear();

	rep(y,M) {
		rep(x,N) {
			if(field[y][x] == '&') {
				add_edge(y*N+x, t, 1, 0);
			}
			rep(k,4) {
				int xx = x + dx[k];
				int yy = y + dy[k];
				if(xx >= 0 && yy >= 0 && xx < N && yy < M) {
					if(field[y][x] == '.' && field[yy][xx] == '#') {
						add_edge(y*N+x, yy*N+xx, 1, 1);
					} else {
						add_edge(y*N+x, yy*N+xx, 1, 0);
					}
				}
			}
		}
	}

	rep(y,M) {
		if(field[y][0] == '#') {
			add_edge(s, y*N+0, 1, 1); 
		} else {
			add_edge(s, y*N+0, 1, 0); 
		}

		if(field[y][N-1] == '#') {
			add_edge(s, y*N+N-1, 1, 1); 
		} else {
			add_edge(s, y*N+N-1, 1, 0); 			
		}
	}

	repa(x,1,N-2) {
		if(field[0][x] == '#') {
			add_edge(s, 0*N+x, 1, 1);
		} else {
			add_edge(s, 0*N+x, 1, 0);
		}

		if(field[M-1][x] == '#') {
			add_edge(s, (M-1)*N+x, 1, 1);
		} else {
			add_edge(s, (M-1)*N+x, 1, 0);			
		}
	}
	
	int res = min_cost_flow(s, t, 1);
	cout << res << endl;
}

int main() {
	while(scanf("%d%d", &N, &M), N|M) {
		field.clear();
		rep(i,M) {
			cin >> line;
			field.push_back(line);
		}
		solve();
	}
}

Measured memory_bytes: 2856
#include <stdio.h>
#include <math.h>

int IsPrime(int);

int main() {
	int total, n, i, j, flag = 0,count = 0;

	scanf("%d", &total);

	for (i = 0; i < total; i++) {
		scanf("%d", &n);

		if (IsPrime(n) == 1) count++;
	
	}

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

	return 0;
}

int IsPrime(int n) {
	int root,i;

	if (n == 2 || n == 3) return 1;

	if (n % 2 == 0) return 0;

	root = (int)sqrt(n);

	for (i = 3; i <= root; i += 2) {
		if (n % i == 0) return 0;
	}

	return 1;
	
}


Measured memory_bytes: 2068
import sys
A, B = [int(x) for x in input().split()]
 
cnt = 1
N = A
 
if B==1:
  print(0)
  sys.exit()
 
for i in range(0, B):
  if N >= B:
    print(cnt)
    break
  else:
    cnt+=1
    N+=(A-1)

Measured memory_bytes: 3060
#include<stdio.h>
#include<stdlib.h>

#define MAX 100
#define INF 99999999

#define white 0
#define gray 1
#define black 2

struct q{
  
  int data[MAX];
  int head,tail,front,rear;
  
};

typedef struct q queue;

queue q;

int n;
int d[MAX];
int g[MAX][MAX];
int color[MAX];

void push(int x){

  if(q.tail >= n) return;
  
  q.data[q.tail] = x;
  q.tail++;
  
}

int pop(){
  int x;

  if(q.head == q.tail) return INF;

  x = q.data[q.head];
  q.head++;

  return x;
  
}


void bfs(s){
  int i,v,u;

  for(i=0;i<n;i++){
    
    d[i] = INF;
    
  }

  d[s] = 0;
  color[s] = gray;
  q.head = q.tail = 0;
  push(s);

  while(q.tail < n){
    u = pop();
    if(u == INF) break;
    for(v=0;v<n;v++){
      if(g[u][v] == 0) continue;
      if(color[v] == white){
	d[v] = d[u] + 1;
	color[v] = gray;
	push(v);
      }
    }
    color[u] = black;
  }
  
}

void print(int n, int d[]){

  int i;
  
  for(i=0;i<n;i++){
    if(d[i] == INF)printf("%d %d\n",i+1,-1);
    else printf("%d %d\n",i+1,d[i]);
  }

}
 

int main(){
  int i,j,u,k,v;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d %d",&u,&k);
    for(j=0;j<k;j++){
      scanf("%d",&v);
      g[u-1][v-1] = 1;
    }
  }  
  
  bfs(0);

  print(n,d);
  
  return 0;
  
}



Measured memory_bytes: 2044
# -*- coding: utf-8 -*-
# 整数の入力
ind = 0
sd = input()
t = input()
len_t = len(t)
len_sd = len(sd)
matched = False

while (len_sd - len_t - ind) >= 0:
    # S'からTと同じ長さの文字列を後方から順番に切り出す
    partOfSd = sd[len_sd - ind - len_t:len_sd - ind]
    #print ('ind:' + partOfSd)
    # 切り出した文字列PoSdに対して１文字ずつループしてTと比較する
    matched = False
    if len(partOfSd) < len_t:
        break
    else:
        ind_posd = 0
    
    while ind_posd < len_t:
        if partOfSd[ind_posd] == t[ind_posd] or partOfSd[ind_posd] == '?':
            # match
            matched = True
            ind_posd += 1
        else:
            matched = False
            break
    if matched:
        # 全部一致した場合
        # PoSdをTで置き換えて、残りの？をaに置き換える
        slist = list(sd)
        ind_t = 0
        while ind_t < len_t:
            slist[len_sd - ind - len_t] = t[ind_t]
            ind -= 1
            ind_t += 1
        sd = "".join(slist)
        print (sd.replace('?', 'a'))
        break
    else:
        ind += 1
        
if not matched:
    print ('UNRESTORABLE')

# 一致しなかった場合、Sdを一文字ずらして繰り返す


Measured memory_bytes: 3064
def canbuy(n):
    if n%7==0 or n%4==0:
        return 'Yes'
    else:
        if n<4:
            return 'No'
        else:
            if canbuy(n-7)=='Yes':
                return 'Yes'
            else:
                if canbuy(n-4)=='Yes':
                    return 'Yes'
                else:
                    return 'No'

n=int(input())
print(canbuy(n))

Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    for(int i = 0; i < 10; i++){
        int temp = 10 * b + i;
        if(int(temp * 0.08) == a){
            cout << temp;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
count = 0
j = 2

for i in range(n):
    tmp = int(input())
    limit = tmp ** 0.5
    r = round(limit)


    if r > 2:
        for j in range(2, r+1):
            if tmp%j == 0:
                count += 1
                break
    else:
        if tmp == 4:
            count += 1
        if tmp == 6:
            count += 1

print(n-count)


Measured memory_bytes: 5700