akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <queue>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=1e3;
int fx[8][2]={1,0,0,1,-1,0,0,-1,1,-1,-1,1,1,1,-1,-1};
int vis[55][55];
char mp[55][55];
int h,w;
int main()
{
    scanf("%d %d",&h,&w);
    for(int i=0; i<h; i++)
        scanf("%s",mp[i]);
    for(int i=0; i<h; i++)
    {
        for(int j=0;j<w;j++)
        {
            if(mp[i][j]=='.')
            {
                int sum=0;
                for(int k=0;k<8;k++)
                {
                    int x=i+fx[k][0];
                    int y=j+fx[k][1];
                    if(x<0||x>=h||y<0||y>=w)
                        continue;
                    if(mp[x][y]=='#')
                        sum++;
                }
                mp[i][j]=sum+'0';
            }
        }
    }
    for(int i=0;i<h;i++)
            printf("%s\n",mp[i]);
    return 0;
}
/*
4 8

*/


Measured memory_bytes: 256
n = gets.to_i
sp = (1..n).map{ |i| gets.split(" ").push(i) }
i = 0
rankings = sp.sort_by { |x| [x[1].to_i, i += 1]}.reverse.sort_by {|x| [x[0], i += 1] }
rankings.transpose[2].each{ |e| puts e }

Measured memory_bytes: 1788
import std.stdio, std.algorithm, std.range, std.conv, std.string, std.math;
import core.stdc.stdio;
// foreach, foreach_reverse, writeln

void main() {
	int n;
	scanf("%d", &n);
	int[] a = new int[n];
	int[] b = new int[n];

	bool same = true;
	foreach (i; 0..n) {
		scanf("%d%d", &a[i], &b[i]);
		if (a[i] != b[i]) same = false;
	}
	if (same) {
		writeln(0);
		return;
	}
	long ans = 0;
	int[] x;
	foreach (i; 0..n) {
		if (a[i] <= b[i]) {
			ans += b[i];
		} else {
			x ~= b[i];
		}
	}
	x.sort;
	foreach (i; 1..x.length) {
		ans += x[i];
	}
	writeln(ans);
}



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

string s;

int main(void){
	cin >> s;
	lli n = s.size();
	if(s.size() == 26){
		if(s == "zyxwvutsrqponmlkjihgfedcba") cout << -1 << endl;
		else{
			string b = s;
			next_permutation(s.begin(), s.end());
			rep(i, 26){
				if(s[i] == b[i]) cout << s[i];
				else{
					cout << s[i] << endl;
					return 0;
				}
			}
		}

		return 0;
	}

	vector<bool> used(26);
	rep(i, n) used[s[i]-'a'] = true;
	rep(i, 26){
		if(used[i] == false){
			cout << s+char('a'+i) << endl;
			return 0;
		}
	}
	cout << "error" << endl;
	return 0;
}


Measured memory_bytes: 3540
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vpi = vector<pii>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpl = vector<pll>;
using vs = vector<string>;

ll mod = static_cast<ll>(1e9+7);

ll modpow(ll num, ll jou)
{
    ll res = 1;
    while(jou>0)
    {
        if(jou & 1) res = res * num % mod;
        num = num * num % mod;
        jou >>= 1;
    }
    return res;
}

int main()
{
    int n;
    int k;
    cin >> n >> k;
    ll sun = 0;
    vi memo(k+1, 0);
    for(int i=k; i>0; i--)
    {
        int sh = k / i;
        ll m = modpow(sh, n);
        for(int j=2; j<=sh; j++)
        {
            m -= memo.at(i*j);
            if(m<0)
            {
                m = m % mod + mod;
            }
        }
        memo.at(i) = m;
        // cout << i << ", " << sh << ", " << m << ", " << m*i << endl;
        sun += m*i;
        sun %= mod;
    }
    cout << sun << endl;
    return 0;
}


Measured memory_bytes: 3572
N, K = map(int, input().split())
X = list(map(int, input().split()))
ans = 10**9

for i in range(N-K+1):
    if X[i] >= 0:
        ans = min(ans, X[K+i-1])
    elif X[K+i-1] <= 0:
        ans = min(ans, -X[i])
    else:
        ans = min(ans, 2*X[K+i-1]-X[i], X[K+i-1]-2*X[i])
print(ans)


Measured memory_bytes: 20340
N, K = map(int, input().split())
h = list(map(int, input().split()))
rps = ['r', 's', 'p']
T = input()
ans = 0
for i in range(3):
    for j in range(K):
        o = True
        for k in range(j, N, K):
            if o and (rps[i]+T[k] == 'rs' or rps[i]+T[k] == 'sp' or rps[i]+T[k] == 'pr'):
                ans += h[i]
                o = False
            else:
                o = True
print(ans)


Measured memory_bytes: 73944
#include <bits/stdc++.h>
#define int         long long int
#define pb          push_back
#define endl        "\n"
#define hell        1000000007
#define INF         1000000000000000000
int mod  =              998244353;
using namespace std;
int dp[400000+10];
  void solve()
  {
    int n,k;
    cin>>n>>k;
    vector<pair<int,int>>v;
    for(int i=0;i<k;i++)
    {
      int a,b;
      cin>>a>>b;
      v.push_back({a,b});
    }
    sort(v.begin(),v.end());
    for(int i=0;i<400000+10;i++)
      dp[i]=0;
    dp[n]=1;
   int subsum=0;
    for(int i=n-1;i>=1;i--)
    {
      for(auto it:v)
      {
        subsum=(subsum%mod+dp[it.first+i]%mod)%mod;

        subsum=(mod+subsum%mod-(dp[it.second+i+1]%mod))%mod;
      }
      dp[i]=subsum;
    }
    cout<<dp[1];

  }
  
  

 
  signed main()
  {
    ios::sync_with_stdio(false);
      cin.tie(0);
      cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
 
        solve();

return 0;
  }

Measured memory_bytes: 6776
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

ll n;
vl a;

int main(){
	cin>>n;
	a=vl(n);
	ll sum=0,N=n*(n+1)/2;
	for(int i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	if(sum%N!=0) cout<<"NO"<<endl;
	else{
		ll t=sum/N,cnt=0;
		for(int i=0;i<n;i++){
			ll A=a[i]-(i?a[i-1]:a[n-1])-t;
			if(A>0) cnt=inf;
			else cnt+=-A/n;
		}
		if(cnt==t) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

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

int main(void){
    int i,ex1,ex2,ex3,ex4,a,b;
    int dice[7],dice2[7];
    int command;

    for(i = 1;i <= 6;i++){
        scanf("%d",&dice[i]);
    }

    for(i = 1;i <= 6;i++){
        scanf("%d",&dice2[i]);
    }

    for(i = 0;i < 1000000;i++){
            command = rand() % 4;
            if(command == 0){
                ex1 = dice[1];
                ex2 = dice[2];
                ex3 = dice[5];
                ex4 = dice[6];
                dice[1] = ex3;
                dice[2] = ex1;
                dice[5] = ex4;
                dice[6] = ex2;
            }else if(command == 1){
                ex1 = dice[1];
                ex2 = dice[2];
                ex3 = dice[5];
                ex4 = dice[6];
                dice[1] = ex2;
                dice[2] = ex4;
                dice[5] = ex1;
                dice[6] = ex3;
            }else if(command == 2){
                ex1 = dice[1];
                ex2 = dice[3];
                ex3 = dice[4];
                ex4 = dice[6];
                dice[1] = ex3;
                dice[3] = ex1;
                dice[4] = ex4;
                dice[6] = ex2;
            }else if(command == 3){
                ex1 = dice[1];
                ex2 = dice[3];
                ex3 = dice[4];
                ex4 = dice[6];
                dice[1] = ex2;
                dice[3] = ex4;
                dice[4] = ex1;
                dice[6] = ex3;
            }
            for(a = 1;a <= 6;a++)
                if(dice[a] != dice2[a])
                    break;
            if(a == 7){
                printf("Yes\n");return 0;
            }
    }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 580
n, shoki, correct = map(int, input().split())
b = list()
for i in range(correct):
    b.append(int(input()))
a = [shoki]*n
a = [i-correct for i in a]
for i in b:
    a[i-1] += 1
for i in range(n):
    if a[i] <= 0:
        print("No")
    else:
        print("Yes")

Measured memory_bytes: 11920
using System;
using System.Collections.Generic;

namespace test
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			string inputA;
			List<string> resultList = new List<string> ();

			while ((inputA = Console.ReadLine()) != null) {
				string[] Aset = inputA.Split (' ');
				string[] Bset = Console.ReadLine ().Split (' ');
				int hit = 0;
				int brow = 0;
				for (int i=0; i<4; i++) {
					for (int j=0; j<4; j++) {
						if (Aset [i] == Bset [j]) {
							if (i == j) {
								hit++;
							} else {
								brow++;
							}
							break;
						}
					}
				}

				string result = string.Format ("{0} {1}", hit, brow);
				resultList.Add (result);
			}

			foreach (string s in resultList) {
				Console.WriteLine (s);
			}



		}


	}
}

Measured memory_bytes: 5672
import sys
input = sys.stdin.readline
mod=10**6+3
n_max=mod
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
for i in range(int(input())):
  x,d,n=map(int,input().split())
  if d==0:
    print(pow(x,n,mod))
  else:
    s=(x*pow(d,mod-2,mod)-1)%mod
    if s+n>=mod:
      print(0)
    else:
      g=(x*pow(d,mod-2,mod)+n-1)%mod
      print(((pow(d,n,mod))*F[g]*FI[s])%mod)


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

int main(){
    string str;
    getline(cin, str);
    int i;
    for(i=0; i<str.size(); i++){
        if(str[i]>='a'&&str[i]<='z') str[i]+='A'-'a';
        else if(str[i]>='A'&&str[i]<='Z') str[i]+='a'-'A';
    }
    cout<< str<<endl;
    return 0;
}


Measured memory_bytes: 3152
def nibun_right(a, x, lo=0, hi=None):
 if lo < 0:
  raise ValueError('lo must be non-negative')
 if hi is None:
  hi = len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
N,D,A=map(int,input().split())
lst=[0]*N
for i in range(N):
 lst[i]=list(map(int,input().split()))
lst.sort()
DMG=[0]*N
ans=0
for i in range(N):
 if i!=0:
  DMG[i]+=DMG[i-1]
 renji=nibun_right(lst,lst[i][0]+2*D)
 Z=max(int((lst[i][1]-1)/A)+1-DMG[i],0)
 DMG[i]+=Z
 if renji!=N:
  DMG[renji]-=Z
 ans+=Z
print(ans)

Measured memory_bytes: 72912
#include <cstdio>
#include <vector>

using namespace std;

int main() {

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

    vector<int> a_vec(n);

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

    int target = 1;
    int broken = 0;
    int ng = 1;

    for (int i=0; i < n; i++) {
        if (a_vec[i] == target) {
            target++;
            ng = 0;
        } else {
            broken++;
        }
    }

    if (ng) {
        printf("-1");
    } else {
        printf("%d", broken);
    }

}


Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main ()
{
    long long int a;
    cin>>a;
    if(a<=9)
        cout<<a-0<<endl;
    else if(a<=99)
        cout<<9<<endl;
    else if(a<=999)
    {
        cout<<((a-100)+10)<<endl;
    }
    else if(a<=9999)
    {
        cout<<909<<endl;
    }
    else if(a<=99999)
    {
        cout<<((a-10000)+910)<<endl;
    }
    else if(a<=999999)
    {
        cout<<90909<<endl;
    }
}


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

int op(int a, int b) {
	return max(a, b);
}
int e() {
	return -1;
}

int main() {
	int n, q; cin >> n >> q;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];
	segtree<int, op, e> st(a);
	for (int i = 0; i < q; ++i) {
		int t, x, y; cin >> t >> x >> y;
		if (t == 1) st.set(x-1, y);
		else if (t == 2) cout << st.prod(x-1, y) << "\n";
		else cout << st.max_right(x-1, [&y](int z) {return z < y;}) + 1 << "\n";
	}
	return 0;
}

Measured memory_bytes: 6132
#include <stdio.h>
int main(void){
   int a,b;
   scanf("%d %d",&a,&b);
   if(a>b)
      printf("a > b\n");
   else if(a<b)
      printf("a < b\n");
   else if(a==b)
      printf("a == b\n");
return 0;
}

Measured memory_bytes: 580
#include<stdio.h>
int main(void)
{
    long int x,i,j,p,a = 0,flag = 0;
    scanf("%ld",&x);
    i = x;
    while(1)
    {
        flag = 0;
        for(j = 2 ; j < i ; j++)
        {
            if(i % j == 0)
            {
                flag = 1;
            }
        }
        if(flag == 0)
        {
            p = i;
            break;
        }
        i++;
    }
    printf("%ld\n",p);
    return 0;
}

Measured memory_bytes: 1696
import java.util.Scanner;

public class Main {

	private static Scanner sc;

	public static void main(String[] args){
		sc = new Scanner(System.in);
		String line = sc.nextLine();
		for(int i=0;i<line.length();i++){
			if(Character.isLowerCase(line.charAt(i))){
				System.out.print(Character.toUpperCase(line.charAt(i)));
			}else System.out.print(Character.toLowerCase(line.charAt(i)));
		}
		System.out.println();
	}
}

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

int main(){
    string s; cin >> s;
    int ans=0;
    int n = s.size();
    for(int i=0; i<n-1; i++){
        if(s[i]!=s[i+1]) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3764
n,m,k = map(int,input().split())
mod = 998244353
def comb(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]*finv[k]%mod*finv[n-k]%mod
fac = [0]*(n+1)
finv = [0]*(n+1)
fac[0] = finv[0] = 1
for i in range(1,n+1):
    fac[i] = fac[i-1]*i%mod
    finv[i] = pow(fac[i],mod-2,mod)

ans = 0
for i in range(k+1):
    ans = (ans + m*comb(n-1,i)%mod*pow(m-1,n-1-i,mod)%mod)%mod
print(ans)

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

const ll MX = 1e18;

int main() {
  int n;
  cin >> n;
  ll ans = 1;
  bool ng = false;
  rep(i,n) {
    ll a;
    cin >> a;
    if (a == 0) {
      cout << 0 << endl;
      return 0;
    }
    if (ng || (MX+1)/ans < a || ans*a > MX) {
      ng = true;
    }
    ans *= a;
  }
  if (ng) cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}

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

int main () {
  string id1, id2;
  cin >> id1 >> id2;
  
  int flag = 0;
  
  for (int i = 0; i < id1.size(); i++) {
    if (id1.at(i) != id2.at(i))
      flag++;
  }
  if (flag == 0)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

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

using namespace std;

#define int long long
#define pii pair<int, int>
#define pb push_back
int const N = 2e5 + 10;
vector<int> a[N];
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    for(int i = 2; i <= n; i++){
        int x; cin >> x;
        a[x].pb(i);
    }
    for(int i = 1; i <= n; i++) cout << a[i].size() << "\n";

    return 0;
}



Measured memory_bytes: 14460
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
using namespace std;
typedef long long ll;
#define rep(i,a,n)	for(int i=a;i<n;i++)
#define rrep(i,a,n) for(int i=(a-1);i>=n;i--)
 
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
ll lcm(ll a,ll b){
	ll g=gcd(a,b);
	return a/g*b;
}
 
ll digitsum(ll a){
	ll x=0;
	while(a>0){
		x+=a%10;
		a/=10;
	}
	return x;
}
int main(){
	ll n;
	cin>>n;
	cout<<"ABC"<<n<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define max 100

int selectionSort(int*,int);


int main(){
    int n,num[max];
    int count;

    scanf("%d",&n);

    for(int i = 0;i < n;i++)scanf("%d",&num[i]);

    count = selectionSort(num,n);

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

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

    return 0;
}

int selectionSort(int *num,int n){
    int minj,tmp;
    int count = 0;
    int flag;

    for(int i = 0;i < n;i++){
        minj = i;
        flag = 0;
        for(int j = i;j < n;j++){
            if(num[j] < num[minj]){
                minj = j;
                flag = 1;
            }
        }
        if(flag == 1){
            tmp = num[minj];
            num[minj] = num[i];
            num[i] = tmp;
            count++;
        }
    }

    return count;
}


Measured memory_bytes: 2136
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,w,i,j,k,ma,u,v,ans=0;
  cin>>h>>w;
  vector<string> s(h);
  vector<int> dh={-1,0,1,0},dw={0,-1,0,1};
  for(i=0;i<h;i++) cin>>s.at(i);
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      if(s[i][j]=='#') continue;
      vector<vector<int>> cnt(h,vector<int>(w,-1));
      queue<pair<int,int>> q;
      cnt[i][j]=0;
      ma=0;
      q.push(make_pair(i,j));
      while(!q.empty()){
        u=q.front().first;
        v=q.front().second;
        q.pop();
        for(k=0;k<4;k++){
          if(0<=u+dh[k]&&u+dh[k]<h&&0<=v+dw[k]&&v+dw[k]<w&&s[u+dh[k]][v+dw[k]]=='.'&&cnt[u+dh[k]][v+dw[k]]==-1){
            cnt[u+dh[k]][v+dw[k]]=cnt[u][v]+1;
            ma=max(ma,cnt[u+dh[k]][v+dw[k]]);
            q.push(make_pair(u+dh[k],v+dw[k]));
          }
        }
      }
      ans=max(ans,ma);
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3572
n = int(input())
a, b = map(int, input().split())
p = list(map(int, input().split()))


cnt = [0, 0, 0]

for pi in p:
    if pi <= a:
        cnt[0] += 1
    elif pi <= b:
        cnt[1] += 1
    else:
        cnt[2] += 1

print(min(cnt))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 100100100100;


ll combination(ll n, ll r){
    if(n < r) return 0;
    if(r == 0||r == n) return 1;
    else if(r == 1) return n;
    return (combination(n - 1, r - 1) + combination(n - 1, r));
}

bool checkKaibun(string str){
    string checkStr = str;
    reverse(checkStr.begin(), checkStr.end());
    if(str == checkStr) return true;
    else return false;
}

int keta(ll num){
    int digits = 0;
    while(num > 0){
        num /= 10;
        digits++;
    }
    return digits;
}


int main(){
    int X, Y, Z;
    cin >> X >> Y >> Z;
    cout << Z << " " << X << " " << Y << endl;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
a=[input() for _ in range(n)]
b=[input() for _ in range(m)]

flag=False
cnt=0
for a_i in range(n-m+1):
    for a_j in range(n-m+1):
        for b_i in range(m):
            if a[a_i+b_i][a_j:a_j+m]==b[b_i]:
                cnt+=1
        if cnt==m:
            flag=True
            break
        cnt=0
print('Yes' if flag else 'No')


Measured memory_bytes: 3064
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

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

int main(void) {
    int X;
    cin >> X;

    int ans = 1;
    for (int i = 2; i < 100; i++) {
        int a = i * i;
        while (a * i <= X) {
            a *= i;
        }
        if (a <= X) {
            chmax(ans, a);
        }
    }

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


Measured memory_bytes: 256
def s():
 n=int(input())+1
 e=[input().split()for _  in[0]*~-n]
 p=[int(e[0][0])]+list(int(x[1])for x in e)
 m=[[0]*n for _ in[0]*n]
 for i in range(n):
  for r in range(n-i-1):
   c=r+i+1
   for j in range(r+1,c):
    x=m[r][j]+m[j][c]+p[r]*p[j]*p[c]
    if 1>m[r][c]or m[r][c]>x:m[r][c]=x
 print(m[r][c])
s()


Measured memory_bytes: 5720
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect


from math import factorial
# 組み合わせ
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

def main():
    num = int(input())
    data = [input() for i in range(num)]
    for i in range(num):
        data[i] = list(data[i])
        data[i].sort()
        data[i] = ''.join(data[i])
    data.sort()

    kari = 1
    pre = ''
    ans = 0
    # print(data)
    for i in range(num):
        if pre == data[i]:
            kari += 1
        else:
            if kari > 1:
                ans += combinations_count(kari, 2)
            kari = 1
            pre = data[i]

    if kari > 1:
        ans += combinations_count(kari, 2)
    print(ans)




if __name__ == '__main__':
    main()


Measured memory_bytes: 80088
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int second = scanner.nextInt();
		
		int hour = second / 3600;
		second -= hour * 3600;
		int minute = second / 60;
		second -= minute * 60;
		System.out.println(hour + ":" + minute + ":" + second);
	}	
}

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

public class Main {

	private static final int[] NUMBER = { 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 };

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			int m = scanner.nextInt();
			scanner.nextLine();
			int[] a = new int[m];
			int[] num = new int[m];
			for (int i = 0; i < m; i++) {
				a[i] = scanner.nextInt();
				num[i] = num(a[i]);
			}
			scanner.nextLine();
			Arrays.sort(a);
			Arrays.sort(num);
			int digit = dp(n, num);
			int remain = n;
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < digit; i++) {
				for (int j = m - 1; j >= 0; j--) {
					if (dp(remain - num(a[j]), num) == dp(remain, num) - 1) {
						sb.append(a[j]);
						remain -= num(a[j]);
						break;
					}
				}
			}
			System.out.println(sb.toString());
		}
	}

	/**
	 * @param k 数字
	 * @return 数字を並べるのに必要なマッチ棒の数
	 */
	private static int num(int k) {
		return NUMBER[k];
	}

	/**
	 * @param n   マッチ棒の総数
	 * @param num 数字を並べるのに必要なマッチ棒の数一覧
	 * @return 並べられる最大桁数
	 */
	private static int dp(int n, int[] num) {
		if (0 == n) {
			return 0;
		}
		int min = num[0];
		if (n % min == 0) {
			return n / min;
		} else {
			for (int number : num) {
				if (n >= number) {
					int next = dp(n - number, num);
					if (next >= 0) {
						return next + 1;
					}
				}
			}
		}
		return -1;
	}
}

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

using namespace std;

void dfs(vector< vector<int> > &g, vector<int> &res, int v, int d=0, int p=-1) {
    res[v] = d;
    for(auto u: g[v]) {
        if(u == p) continue;
        dfs(g, res, u, d+1, v);
    }
}

vector<int> calcDistance(vector< vector<int> > &g, int s) {
    vector<int> res(g.size());
    dfs(g, res, s);
    return res;
}

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

    vector<int> distacneF = calcDistance(g, 0);
    vector<int> distacneS = calcDistance(g, N-1);

    int cntF = 0;
    for(int i=0; i<N; i++) {
        if(distacneF[i] <= distacneS[i]) {
            cntF++;
        }
    }

    if(cntF > N - cntF) {
        cout << "Fennec" << endl;
    } else {
        cout << "Snuke" << endl;
    }
    return 0;
}


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

using namespace std;

typedef long long int lli;

int main(){
    lli n, A = 0;
    cin >> n;
    while(n > 0){
        A += n % 10;
        n /= 10;
    }
    if(A == 1)
        cout << 10 << endl;
    else
        cout << A << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
  
int main(){
  int n,x,sum=0; cin>>n>>x;
  vector<int>vec(n);
  for(int i=0;i<n;i++){
    int m; cin>>m;
    sum+=m;
    vec[i]=m;
  }
  sort(vec.begin(),vec.end());
  cout<<n+(x-sum)/vec[0]<<endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10**9+7
ans = 0
cmb = [0]*N
x = [0]*N
cmb[K-1] = 1
def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod
for i in range(1,N-K+1):
    x[i] = Pow(i, mod-2)
    
for i in range(K, N):
    cmb[i] = cmb[i-1]*i%mod*x[i-K+1]%mod
for i in range(N):
    fac = cmb[i] - cmb[N-i-1]
    num = fac*a[i]%mod
    ans += num
    ans = ans%(10**9+7)
print(ans)

Measured memory_bytes: 14416
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <iomanip>
using namespace std;
typedef long long ll;

const ll MOD = 1e9+7;
ll dpab[25000001]; //abのときのどんぐりの最大量
ll dpba[25000001]; //baのときのどんぐりの最大量
ll a[3];
ll b[3];

int main()
{
	int n;
	ll ans=0;
	cin>>n;
	for(int i=0;i<3;i++)
		cin>>a[i];
	for(int i=0;i<3;i++)
		cin>>b[i];
	//init dp
	for(int i=0;i<5000*5000+1;i++)
	{
		dpab[i]=i;
		dpba[i]=i;
	}

	//start dp
	for(int i=0;i<3;i++)
	{
		for(int j=a[i];j<25000001;j++)
			dpab[j]=max(dpab[j],dpab[j-a[i]]+b[i]);
	}
	for(int i=0;i<3;i++)
	{
		for(int j=b[i];j<25000001;j++)
			dpba[j]=max(dpba[j],dpba[j-b[i]]+a[i]);
	}
	ans=max(dpab[n],dpba[n]);
	ans=max(ans,dpba[dpab[n]]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 390912
s = int(input())
a = [0 for _ in range(1000000)]
a[0] = s
for i in range(1, len(a)):
    if a[i - 1] % 2 == 0:
        a[i] = a[i - 1] // 2
    else:
        a[i] = 3 * a[i - 1] + 1
    if a[i] in a[:i]:
        print(i + 1)
        break


Measured memory_bytes: 10904
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod

int main(){
	ll a,b;
	cin>>a>>b;
	if(a<=b){
		cout<<"Impossible\n"<<flush;
		return 0;
	}
	vector<ll> ids;
	for(int i=0;i<a+b;i++){
		if(ids.size()==0){
			ids.push_back(i);
			continue;
		}
		cout<<"? "<<ids.back()<<" "<<i<<"\n"<<flush;
		char res; cin>>res;
		if(res=='Y')ids.push_back(i);
		else ids.pop_back();
	}
	vector<bool> ans;
	for(int i=0;i<a+b;i++){
		cout<<"? "<<ids.back()<<" "<<i<<"\n"<<flush;
		char res; cin>>res;
		ans.push_back(res=='Y');
	}
	cout<<"! ";
	rep(i,a+b)cout<<ans[i];
	cout<<"\n"<<flush;
}


Measured memory_bytes: 724
//
// Created by Myabu on 2020/01/25.
//

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <numeric>
#include <iomanip>

using namespace std;


int main(void){
    int N;
    int T,A;
    cin>>N>>T>>A;
    vector<double> H(N);

    for (int i = 0; i < N; ++i) {
        cin>>H[i];
        H[i] = T-H[i]*0.006;
    }

//    sort(H.begin(), H.end());

    double sa = 1000;
    int ans = -1;
    for (int i = 0; i < N; ++i) {
        if (abs(A - H[i]) < sa) {
            sa = abs(A - H[i]);
            ans = i + 1;
        }
    }

    cout<<ans<<endl;



    return 0;
}

Measured memory_bytes: 504
import copy

n = int(input())

ary_list = []
def f(ary, max_num):
    if len(ary) == n:
        ary_list.append(ary)
        return
    for i in range(max_num + 2):
        next_ary = copy.copy(ary)
        next_ary.append(i)
        f(next_ary, max_num + (1 if i == max_num + 1 else 0))

f([], -1)

str_list = []
for i in range(len(ary_list)):
    for j in range(n):
        ary_list[i][j] = chr(97 + ary_list[i][j])
    str_list.append("".join(ary_list[i]))

str_list = sorted(str_list)

for s in str_list:
    print(s)


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

typedef long long LL;
const int M=1005;
const int INF=1e9+5;

struct Node
{
	int a,b,c;
	void read()
	{
		scanf("%d%d%d",&a,&b,&c);
	}
}r[M],c[M];

int x[M*3],y[M*3];
int nx,ny;
int findx(int v)
{
	return lower_bound(x,x+nx,v)-x;
}
int findy(int v)
{
	return lower_bound(y,y+ny,v)-y;
}

int vis[M*3][M*3];
int block[M*3][M*3][4];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
//         L R U D

LL ans;

int qx[M*M*9];
int qy[M*M*9];

void bfs(int xx,int yy)
{
	int t=0;
	qx[t]=xx; qy[t]=yy; t++;
	vis[xx][yy]=1;
	for(int ii=0;ii<t;ii++)
	{
		xx=qx[ii]; yy=qy[ii];
		ans+=1LL*(x[xx+1]-x[xx])*(y[yy+1]-y[yy]);
		for(int i=0;i<4;i++)
		{
			if(block[xx][yy][i]) continue;
			int x=xx+dx[i],y=yy+dy[i];
			if(x<=0||nx-1<=x||y<=0||ny-1<=y)
			{
				ans=-1;
				return;
			}
			if(vis[x][y]) continue;
			vis[x][y]=1;
			qx[t]=x; qy[t]=y; t++;
		}
	}
}

int main()
{
	//freopen("F.in","r",stdin);
	int n,m; scanf("%d%d",&n,&m);
	nx=ny=0;
	for(int i=0;i<n;i++)
	{
		r[i].read();
		x[nx++]=r[i].a;
		x[nx++]=r[i].b;
		y[ny++]=r[i].c;
	}
	for(int i=0;i<m;i++)
	{
		c[i].read();
		x[nx++]=c[i].a;
		y[ny++]=c[i].b;
		y[ny++]=c[i].c;
	}
	x[nx++]=-INF; x[nx++]=INF;
	y[ny++]=-INF; y[ny++]=INF;
	sort(x,x+nx); nx=unique(x,x+nx)-x;
	sort(y,y+ny); ny=unique(y,y+ny)-y;
	// cout<<nx<<" "<<ny<<endl;
	// for(int i=0;i<nx;i++)
	// 	cout<<x[i]<<" ";
	// cout<<endl;
	// for(int i=0;i<ny;i++)
	// 	cout<<y[i]<<" ";
	// cout<<endl;
	for(int i=0;i<n;i++)
	{
		int p=findy(r[i].c);
		//cout<<p<<" "<<findx(r[i].a)<<" "<<findx(r[i].b)<<endl;
		for(int j=findx(r[i].a);j<findx(r[i].b);j++)
			block[j][p-1][1]=block[j][p][0]=1;
	}
	for(int i=0;i<m;i++)
	{
		int p=findx(c[i].a);
		for(int j=findy(c[i].b);j<findy(c[i].c);j++)
			block[p-1][j][3]=block[p][j][2]=1;
	}
	bfs(findx(0)-1,findy(0)-1);
	if(ans==-1) printf("INF\n");
	else printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 230800
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using data=pair<int,int>;
#define rep(i,N) for(i=0;i<N;i++)
#define rep1(i,N) for(i=1;i<N;i++)
#define mod 1000000007

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}
 
ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll euclidean_gcd(ll a, ll b) {
  if(a<b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)){a=b;b=r;}
  return b;
}

int main(){
  ll i,N,a,b,cnt=0;
  cin>>N;
  vector<vector<ll>> v(N);
  vector<ll> ans(N,0),c(N,0);
  rep(i,N-1){
    cin>>a>>b;
    a--;b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  rep(i,N)cin>>c[i];
  sort(c.begin(),c.end(),greater<ll>());
  queue<int> que;
  que.push(0);
  ans[0]=c[cnt++];
  while(cnt<N){
    a=que.front();que.pop();
    for(i=0;i<v[a].size();i++){
      if(ans[v[a][i]]==0){
        que.push(v[a][i]);
        ans[v[a][i]]=c[cnt++];
      }
    }
  }
  cnt=-1*c[0];
  rep(i,N)cnt+=c[i];
  cout<<cnt<<endl;
  rep(i,N){
    cout <<ans[i]<<" ";
  }
  return 0;
}

Measured memory_bytes: 1152
//(・ω・)
#include <stdio.h>
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, atoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip> //setprecision
#include <limits>
#include <sstream> //istringstream
#include <stdlib.h>
#include <list>
#include <iterator>//std::advance()
#include <ctime>
#include <functional>
#include <cassert>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<long long> a(3*n);
    for(int i=0; i<3*n; i++) cin >> a[i];
    sort(a.begin(),a.end(),greater<long long>());
    long long ans=0;
    for(int i=0; i<n; i++){
        ans+=a[i*2+1];
    }
    cout << ans << endl;
}



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

int main(){
	int N, K;
	cin >> N >> K;
	vector<int> sticks;
	int length = 0;
	for(int i = 0; i < N; i++){
		int input;
		cin >> input;
		sticks.push_back(input);
	}
	sort(sticks.begin(), sticks.end());
	for(int i = N - 1; i > N - K - 1; i--){
		length += sticks[i];
	}
	cout << length << endl;
}

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

string rotate(string s)
{
    string s_rot = ""; 
    s_rot += s[s.size()-1];
    for (int i=0; i<s.size()-1; i++)
        s_rot += s[i];
    return s_rot;
}

int main() 
{
    string s1;
    string s2;
    cin >> s1 >> s2;
    bool y = false;
    for (int i=0; i<s1.size(); i++)
    {
        string s3 = rotate(s2);
        if (s1 == s3)
        {
            y = true;
            break;
        }
        s2 = s3;
    }
    cout << (y?"Yes":"No");
    return 0;
}

Measured memory_bytes: 256
n = int(input())
import math
sqrt_n = math.floor(math.sqrt(n))

seisu_tuple = []
for a in range(1,sqrt_n+1):
    if n/a == math.floor(n/a):  # 整数判定
        seisu_tuple.append((a,n/a))
bunkai_list_sum = [sum(x) for x in seisu_tuple]
min_tuple = seisu_tuple[bunkai_list_sum.index(min(bunkai_list_sum))]
print(int(sum(min_tuple) - 2))

Measured memory_bytes: 40796
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main()
{
  string s;
  cin >> s;

  for (int bit = 0; bit < (1 << 3); ++bit)
  {
    int sum = s[0] - '0';
    string ans = "";
    ans += s[0];
    for (int i = 0; i < 3; ++i)
    {
      if (bit & (1 << i))
      {
        sum += s[i + 1] - '0';
        ans += '+';
        ans += s[i + 1];
      }
      else
      {
        sum -= s[i + 1] - '0';
        ans += '-';
        ans += s[i + 1];
      }
    }
    if (sum == 7)
    {
      ans += "=7";
      cout << ans << endl;
      return 0;
    }
  }

  return 0;
}


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





int main() {

  int A,B,C;
  cin>>A>>B>>C;
  
  if (C>=A and C<=B){
    cout<<"Yes"<<endl;
  }
  
  else {
    cout<<"No"<<endl;
  }
  
    
  
  
}













Measured memory_bytes: 256
N,A,B,C = map(int,input().split())
l =[int(input()) for _ in range(N)]

INF = 10**9

def dfs(cur,a,b,c):
    if cur == N:
        return abs(a-A)+abs(b-B)+abs(c-C) - 30 if min(a,b,c)>0 else INF
    ret0 = dfs(cur+1, a, b, c)
    ret1 = dfs(cur+1, a + l[cur], b, c) + 10
    ret2 = dfs(cur+1, a , b + l[cur], c) + 10
    ret3 = dfs(cur+1, a , b, c + l[cur]) + 10
    return min(ret0, ret1, ret2, ret3)
print(dfs(0,0,0,0))

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

using namespace std;

#define sp << " " <<
#define mod 1000000007

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

/*long long dice()
{
    uniform_int_distribution<long long> uid(l,r);//specify l and r.
    return uid(rng) ;
}*/

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

    return 0;
}
*/

#define ll long long

struct Line {
  mutable ll k, m, p;
  bool operator<(const Line& o) const { return k < o.k; }
  bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
  // (for doubles, use inf = 1/.0, div(a,b) = a/b)
  const ll inf = LLONG_MAX;
  ll div(ll a, ll b) { // floored division
    return a / b - ((a ^ b) < 0 && a % b); }
  bool isect(iterator x, iterator y) {
    if (y == end()) { x->p = inf; return false; }
    if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
    else x->p = div(y->m - x->m, x->k - y->k);
    return x->p >= y->p;
  }
  void add(ll k, ll m) {
    auto z = insert({k, m, 0}), y = z++, x = y;
    while (isect(y, z)) z = erase(z);
    if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
    while ((y = x) != begin() && (--x)->p >= y->p)
      isect(x, erase(y));
  }
  ll query(ll x) {
    assert(!empty());
    auto l = *lower_bound(x);
    return l.k * x + l.m;
  }
}o;

int main()
{
 ll n,c;
 cin >> n >> c;
 ll h[n],dp[n];
 for(int i=0;i<n;i++)
 cin >> h[i];
 dp[0]=0;
 o.add((2*h[0]),-(h[0]*h[0]));
 for(int i=1;i<n;i++)
 {
 ll t=o.query(h[i]);
 t-=h[i]*h[i];
 t-=c;
 dp[i]=t;
 o.add((2*h[i]),(-h[i]*h[i]+dp[i]));
 }
 cout << -dp[n-1];
 return 0;
}


Measured memory_bytes: 15872
N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
ans = 0
l = [1] + [2] * (len(A)-1)
k = 0
for i in range(N-1):
  l[k] -= 1
  ans += A[k]
  if l[k] == 0:
    k += 1
print(ans)

Measured memory_bytes: 105136
local function getgcd(x, y)
  while(0 < x and 0 < y) do
    if(x < y) then y = y % x else x = x % y end
  end
  return math.max(x, y)
end

local t = io.read("*n")

for i = 1, t do
  local a, b, c, d = io.read("*n", "*n", "*n", "*n")
  if(a < b) then print("No")
  elseif(d < b) then print("No")
  elseif(b <= c) then print("Yes")
  elseif(d % b == 0) then
    if(a % b <= c) then print("Yes") else print("No") end
  else
    local gcd = getgcd(b, d)
    if(a % gcd + (b - gcd) <= c) then print("Yes") else print("No") end
  end
end


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;

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

vector<double> l,a,b;

double dfs(int k, vector<int> v) {
	if(k==0) {
		double res = 0;
		rep(ri, v.size()) {
			int i = v[ri];
			for(int rj=ri+1; rj<v.size(); rj++) {
				int j = v[rj];
				double dist = (l[i]-l[j])*(l[i]-l[j]) + (a[i]-a[j])*(a[i]-a[j]) + (b[i]-b[j])*(b[i]-b[j]);
				res += dist;
			}
		}
		return res;
	}

	double res = 0.0;
	if(v.size()>0) {
		for(int i=v[v.size()-1]+1; i<l.size(); i++) {
			vector<int> v2 = v;
			v2.push_back(i);
			res = max(res, dfs(k-1, v2));
		}
	}
	else {
		for(int i=0; i<l.size(); i++) {
			vector<int> v2;
			v2.push_back(i);
			res = max(res, dfs(k-1, v2));
		}
	}
	return res;
}

int main() {
	int n,m;
	cin >> n >> m;
	l.resize(n);
	a.resize(n);
	b.resize(n);
	rep(i,n) {
		cin >> l[i] >> a[i] >> b[i];
	}
	if(m == 1) {
		cout << 0 << endl;
	} else {
		cout << fixed << setprecision(8) << dfs(m, vector<int>()) << endl;
	}
	return 0;
}

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

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

    int n;
    cin>>n;
    vector<int> a(n+1);
    vector<int> b(n+1);
    int i=1,j=1;
    int cnt=0,sum=0;
    while(i<=n)
    {
        cin >> a[i];
        i++;
    }
    vector<int>ans;
    int p=0;
    for(i=n; i>0; --i)
    {
        j=2;
        sum=0;
        while((i*j)<=n)
        {
            sum^=b[i*j];
            j++;
        }
        b[i]=sum^a[i];
        if(b[i])
            ans.push_back(i);
    }
    cout<<ans.size()<<endl;
    i=0;
    while(i<ans.size())
    {
        cout<<ans[i]<<' ';
        i++;
    }
    return 0;
}


Measured memory_bytes: 3192
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<iomanip>
using namespace std;
typedef long long ll;
const int maxn = 300005;
const int inf = 1000000007;

int n,a[maxn];

int dfs(int x,int y){
    if(x==y)return a[x];
    int mid = (x+y)>>1;
    int ansx=dfs(x,mid);
    int ansy=dfs(mid+1,y);
    if(ansx==ansy)return ansx;
    return abs(ansx-ansy);
}

int main() {
  //  freopen("in.cpp","r",stdin);
    cin>>n;
    for(int i=0;i<(1<<n);i++)cin>>a[i];
    cout<<dfs(0,(1<<n)-1)<<endl;
    return 0;
}


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

int main()
{ int A,B,C,N;
 int count = 0;
 
 cin>>A>>B>>C>>N;
 for(int a = 0; a <= A ; a++)
 {for(int b = 0; b <= B ; b++)
 {for(int c = 0; c <=C ; c++)
 {if( 500*a + 100*b + 50*c == N){count++;}}}}
 cout<<count<<endl;
return 0;}
  

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

int main() {
  ll h, w;
  cin >> h >> w;
  ll ans = 1e10;
  for (ll i = 1; i < h; ++i) {
    ll l = min(w*i, w/2*(h-i)), r = max(w*i, (w+1)/2*(h-i));
    ans = min(ans, r-l);
  }
  for (ll i = 1; i < w; ++i) {
    ll l = min(h*i, h/2*(w-i)), r = max(h*i, (h+1)/2*(w-i));
    ans = min(ans, r-l);
  }
  ans = min(ans, min(1LL, h%3) * w);
  ans = min(ans, min(1LL, w%3) * h);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{
    static List<Integer> nList = new ArrayList<>();
    static List<Integer> rankList = new ArrayList<>();

    static int[] p;
    static int[] rank;

    public static void main(String args[]){


        Scanner scanner = new Scanner(System.in);

        int n = Integer.parseInt(scanner.next());
        int q = Integer.parseInt(scanner.next());

        p = new int[n];
        rank = new int[n];

        int query;
        int x;
        int y;



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

        for(int i = 0; i < q; i++){
           query = Integer.parseInt(scanner.next());
           x = Integer.parseInt(scanner.next());
           y = Integer.parseInt(scanner.next());

           if(query == 0){
               union(x, y);
           }else {
               same(x, y);
           }

        }



    }


    static public void link(int x, int y){
        if(rank[x] > rank[y]){
            p[y] = x;
        }else {
            p[x] = y;
        }
        if(rank[x] == rank[y]){
            rank[y] = rank[y] + 1;
        }
    }

    static public int findSet(int x){
        if(x != p[x]){
            p[x] = findSet(p[x]);
        }
        return p[x];
    }

    static public void union(int x, int y){
        link(findSet(x), findSet(y));
            }

    static public void same(int x, int y){
        if(findSet(x) == findSet(y)){
            System.out.println(1);
        }else {
            System.out.println(0);
        }
    }


}



Measured memory_bytes: 71836
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 整数の入
		long k = sc.nextLong();
		long a = sc.nextLong();
		long b = sc.nextLong();

		if(b<=a+2){
			//愚直パタン
			
			System.out.println(k+1);

		}else{
			//交換パターン
			long remain =k-a+1;
			long doDouble = remain/2;
			long result = doDouble*(b-a) + (remain%2) + a;

			// System.out.println(doDouble * (b - a));
			// System.out.println(remain % 2);
			System.out.println(result);
		}

	}
}


Measured memory_bytes: 22996
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		ans = 0
		for sp in range(len(t)):
			if len(t) - sp <= ans:
				break
			for L in range(ans,len(t)-sp+1):
				if t[sp:sp+L] in s:
					ans = L
				else:
					break
		print ans
	except:
		break

Measured memory_bytes: 4472
import sys
input = sys.stdin.readline
N, L = map(int, input().split())
a = list(map(int, input().split()))
s = -1
for i in range(N - 1):
  if a[i] + a[i + 1] >= L:
    s = i
    break
if s == -1:
  print("Impossible")
  exit(0)
res = [s]
for i in range(s - 1, -1, -1):
  res.append(i)
for i in range(s + 1, N - 1):
  res.append(i)
res.reverse()
print("Possible")
for r in res: print(r + 1)

Measured memory_bytes: 60804
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c;
    cin >> a >> b >> c;
    if(b - a == c - b) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<complex>
#include<cstdio>
using namespace std ;
typedef vector<int> vi ;
typedef vector<vi> vvi ;
typedef vector<string> vs ;
typedef pair<int, int> pii; 
typedef long long ll ;

#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define rep(i,a) loop(i,0,a)
#define all(a) (a).begin(),(a).end()


int main(void){
	string num;
	getline(cin,num);
	int n = atoi(&num[0]);
	while(n--){
		string s;
		getline(cin,s);
		rep(i,s.size()){
			if(s[i]=='H'&&s[i+1]=='o'&&s[i+2]=='s'&&s[i+3]=='h'&&s[i+4]=='i'&&s[i+5]=='n'&&s[i+6]=='o'){
				s[i+6]='a';
			}
			if(s[i]=='\n'){cout<<endl;n--;break;cout<<"test"<<n<<endl;}
			}
		cout<<s<<endl;
	}
}

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

#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
#define ANS(ans) cout << (ans) << endl;
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
typedef vector<int> VI;
typedef pair<int, int> P;

// repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, n) for (long long i = 0; i < (n); ++i)

int main() {
  int n, m;
  cin >> n >> m;
  int penalty = 0;
  int success = 0;

  VI v(n + 1, 0);
  REP(i, m) {
    int q;
    string status;
    cin >> q >> status;

    if(v[q]!=-1){
      if(status == "WA"){
        v[q]++;
      }
      if(status == "AC"){
        success++;
        penalty += v[q];
        v[q] = -1;
      }
    }
  }

  cout << success << " " << penalty << endl;
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#define REP(i, a, n) for(int i = a; i < n; i++)
using namespace std;


int N;
vector<int> A;
vector< pair<int, int> > B;

int main(void) {
  cin >> N;
  REP(i, 0, N) {
    int a;
    cin >> a;
    A.push_back(a);
    B.push_back(pair<int, int>(a, i));
  }

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

  long c = 0;
  REP(i, 0, N) {
    c += abs(B[i].second - i) % 2;
  }
  c /= 2;

  cout << c << endl;

  return 0;
}


Measured memory_bytes: 1780
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21

def main():
    n, m = getlist()
    numbers = [-1 for i in range(n)]
    for query in range(m):
        a, b = getlist()
        if numbers[a-1] != b and numbers[a-1] != -1:
            print(-1)
            return
        else:
            numbers[a-1] = b
    if n == 1 and numbers[0] <= 0:
        print(0)
        return

    if numbers[0] == 0:
        print(-1)
        return

    elif numbers[0] == -1:
        numbers[0] = 1

    for i, num in enumerate(numbers):
        if num == -1:
            numbers[i] = 0

    print("".join(list(map(str, numbers))))


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Measured memory_bytes: 38384