akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

const ll MOD = 1000000007;

ll mod_add(ll a, ll b){
    return ((a % MOD) + (b % MOD)) % MOD;
}
 
ll mod_mul(ll a, ll b){
    return ((a % MOD) * (b % MOD)) % MOD;
}

ll mod_pow(ll x, ll r){
    if (r == 0) return 1;

    else if (r == 1) return x % MOD;

    else if (r % 2 == 0){
        ll t = mod_pow(x, r/2) % MOD;
        return mod_mul(t, t);
    }

    else{
        ll t = mod_pow(x, r/2) % MOD;
        ll k = mod_mul(t, t);
        return (k % MOD) * (x % MOD);
    }
}

ll mod_div(ll a, ll b){
    return mod_mul(a, mod_pow(b, MOD - 2));
}

ll calc_subcomb(ll num, ll k){
    ll ret;
    ll over = 1;
    ll under = 1;
    for (ll i = num; i > num-k; --i){
        over = mod_mul(over, i);
    }
    for(ll i = 1; i <= k; ++i){
        under = mod_mul(under, i);
    }

    ret = mod_div(over, under);
    return ret;
}

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

    ll n, a, b;
    cin >> n >> a >> b;

    ll all = mod_pow(2, n) - 1;

    ll sub_a = calc_subcomb(n, a);
    ll sub_b = calc_subcomb(n, b);

    cout << ((all + MOD - sub_a)%MOD + MOD - sub_b) % MOD << endl;



    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <set>
#include <sstream>
#include <bitset>
#include <string>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define all(x) (x).begin(),(x).end()
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)

int main() {
    ll ans = 0;
    ll N; cin >> N;
    // cout << sqrt(N) << endl;
    // cout << int(sqrt(N)) << endl;
    reps(i,int(sqrt(N))){
      if(N%i==0){
        if(N/i == 1) ans += N/i-1;
        else{
          if(N%(N/i-1)!=0 && i<(N/i-1)) ans += N/i-1;
        } 
      }
    }

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


Measured memory_bytes: 256
import collections
import bisect
n= int(input())
a=list(map(int, input().split()))
c=collections.Counter(a)
ans=0
des=sorted(a,reverse=True)
# asc=sorted(a)

for i in des:
    if c[i]>0:
        bi=format(i, 'b')
        x=2**len(bi)-i
        c[i]-=1
        if c[x]>0:
            c[x]-=1
            ans+=1
print(ans)

Measured memory_bytes: 33296
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

struct Edge {
  ll t, c, m;

  bool operator < (const Edge& e) const {
    return m > e.m;
  }
};

vector<Edge> G[55];

vector<vector<ll>> dp(55, vector<ll>(2505, INF));

void dijkstra(ll s) {
  repr(i, s) dp[0][s] = 0;
  priority_queue<pair<Edge, ll>> pq;
  pq.push({{0, 0, 0}, s});
  while (!pq.empty()) {
    ll v = pq.top().first.t, resc = pq.top().second;
    pq.pop();
    for (Edge e: G[v]) {
      ll nxtc = resc - e.c;
      if (nxtc < 0) continue;
      chmin(nxtc, 2500LL);
      if (chmin(dp[e.t][nxtc], dp[v][resc] + e.m)) {
        pq.push({e, nxtc});
        repr(i, nxtc - 1) {
          if (!chmin(dp[e.t][i], dp[v][resc] + e.m)) break;
        }
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(25);

  ll n, m, s;
  cin >> n >> m >> s;
  chmin(s, 2500LL);
  rep(i, m) {
    ll u, v, a, b;
    cin >> u >> v >> a >> b;
    u--, v--;
    G[u].push_back({v, a, b});
    G[v].push_back({u, a, b});
  }
  rep(i, n) {
    ll c, d;
    cin >> c >> d;
    G[i].push_back({i, -c, d});
  }
  dijkstra(s);
  FOR(i, 1, n) cout << dp[i][0] << '\n';







  
  return 0;
}

Measured memory_bytes: 20796
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

import numpy as np

n = int(readline())
ab = np.array(read().split(), np.int64)
a = ab[::2]
b = ab[1::2]

a.sort()
b.sort()

if n % 2:
    idx = (n + 1) // 2 - 1
    mn = a[idx]
    mx = b[idx]
    ans = mx - mn + 1

else:
    i1, i2 = n // 2 - 1, n // 2
    a *= 2
    b *= 2
    mn = (a[i1] + a[i2]) // 2
    mx = (b[i1] + b[i2]) // 2
    ans = mx - mn + 1

print(ans)


Measured memory_bytes: 53056
#include <bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
#define pb push_back
#define sort(x) sort((x).begin(), (x).end())
using ll = long long;
const int INF = 1e9+7;
const int EPS = -1e6;
inline void fastio() {ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);}
const int maxn = 100000+5;


int main(){
    //freopen("input.txt", "r", stdin);
    fastio();

    int N, ans;
    cin>>N;
    for(int i = 0; i < N; ++i){
        int x; cin>>x;
        if(i == 0) ans = x;
        else ans = __gcd(ans, x);
    }
    cout<<ans<<endl;
    return 0;
}


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


int main(){
   string str,str_r;
   int cnt = 0;
   while(cin >> str){
      str_r = str;
      reverse(str_r.begin(),str_r.end());
      if(str == str_r) cnt++;
   }
   cout << cnt << endl;
   return 0;
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
//#define bint int1024_t
#define ld long double
#define vect vector<ll>
#define unmap unordered_map
#define pb push_back
#define F first
#define pll pair<ll,ll>
#define S second
#define pi 3.1415926536
#define mod int(1e9+7)
#define mp make_pair
//ios_base::sync_with_stdio(false);cin.tie(NULL);
#define testcases ll t; cin>>t; while(t--)

using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

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

    ll n,q,ans = 0;
    cin>>n;

    unmap<ll,ll> m;
    while(n--)
    {
        ll x;
        cin>>x;
        ans+=x;
        m[x]++;
    }
    cin>>q;
    while(q--)
    {
        ll x,y;
        cin>>x>>y;
        ans += (y-x)*m[x];
        m[y]+=m[x];
        m[x]=0;
        cout<<ans<<"\n";
    }

    return 0;
}


Measured memory_bytes: 7024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll>P;

class BF{
    public:
    ll N;
    ll INF;
    vector<vector<P> >path;
    vector<vector<ll> >rev;
    vector<ll>dist;
    vector<ll>flg;
    BF(ll n, ll inf){
        N = n + 1;
        INF = inf;
        path = vector<vector<P> >(N);
        rev = vector<vector<ll> >(N);
        dist = vector<ll>(N, INF);
        flg = vector<ll>(N, 1);
    }
    void add(ll a, ll b, ll c){
        path[a].push_back(P(b, c));
        rev[b].push_back(a);
    }
    // loopがあったらtrue(目標ノードに到達できないところでloopする可能性あり)
    // 無関係なノードはadjust()で消しておくと良い
    bool make(ll s){
        dist[s] = 0;
        for(ll i = 0; i < N; i++){
            for(ll v = 0; v < N; v++){
                if(dist[v] == INF)continue;
                for(ll k = 0; k < path[v].size(); k++){
                    ll to = path[v][k].first;
                    ll w = path[v][k].second;
                    if(dist[to] > dist[v] + w){
                        dist[to] = dist[v] + w;
                        if(i == N - 1 && flg[to])return true;
                    }
                }
            }
        }
        return false;
    }
    // 目標ノードに到達できないノードのフラグを0にする
    void adjust(ll t){
        flg = vector<ll>(N, 0);
        queue<ll>Q;
        flg[t] = 1;
        Q.push(t);
        while(!Q.empty()){
            ll q = Q.front();
            Q.pop();
            for(ll i = 0; i < rev[q].size(); i++){
                ll j = rev[q][i];
                if(flg[j])continue;
                flg[j] = 1;
                Q.push(j);
            }
        }
    }
    ll get(ll t){
        return dist[t];
    }
};

int main(){

    ll N, M;
    cin >> N >> M;
    BF bf(N + 1, 1e16);
    for(ll i = 0; i < M; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        bf.add(a, b, -c);
    }
    bf.adjust(N);
    if(bf.make(1))cout << "inf" << endl;
    else cout << -bf.get(N) << endl;

    return 0;
}


Measured memory_bytes: 384
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N;
    cin >> N;

    int ans = 0;
    REP(i, N) {
        int idx = i + 1;
        int a; cin >> a;
        if ((idx & 1) && (a & 1)) ans++;
    }

    print(ans);
    
}


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

int H,W,g[50][50],cntp;
const int x[4]={0,0,1,-1};
const int y[4]={1,-1,0,0};
char s[50][50];
queue<pair<int,int>>q;

int main()
{
    cin>>H>>W;
    for(int i=0;i!=H;++i){
        for(int j=0;j!=W;++j){
            cin>>s[i][j];
            if(s[i][j]=='.')++cntp;
            g[i][j]=0xe869120;
        }
    }
    q.push(make_pair(0,0));
    g[0][0]=1;
    while(!q.empty()){
        for(int i=0;i!=4;++i){
            if(q.front().first+x[i]!=-1&&q.front().first+x[i]!=H&&q.front().second+y[i]!=-1&&q.front().second+y[i]!=W&&g[q.front().first+x[i]][q.front().second+y[i]]==0xe869120&&s[q.front().first+x[i]][q.front().second+y[i]]=='.'){
                g[q.front().first+x[i]][q.front().second+y[i]]=g[q.front().first][q.front().second]+1;
                q.push(make_pair(q.front().first+x[i],q.front().second+y[i]));
            }
        }
        q.pop();
    }
    if(g[H-1][W-1]==0xe869120)cout<<-1<<endl;
    else cout<<cntp-g[H-1][W-1]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include <stdio.h>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<array>
#include<vector>
#include<set>
#include <utility>
#include <map>
using namespace std;

int main(){
  int n; cin >>n;
  int h[200];
  for(int i=0;i<n;i++)
  cin >>h[i];
  int cnt=1;

  for(int i=1;i<n;i++){
    int a=h[i];
    int f=0;
    for(int j=0;j<i;j++){
      if(h[j]>a) {f=1; break;}
    }
    if(f==0) cnt++;
  }
   cout<<cnt<<endl;
  }


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

int main(){
  int A,B;
  cin>>A>>B;
  if(A==B){
    cout<<"Draw"<<endl;
  }
  else if(A==1){
    cout<<"Alice"<<endl;
  }
  else if(A<B){
    cout<<"Bob"<<endl;
  }
  else if(B==1){
    cout<<"Bob"<<endl;
  }
  else if(A>B){
    cout<<"Alice"<<endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, k, n) for(int i = (k); i < (int)(n); i++)
using namespace std;
int main(){
    string N;
    cin >> N;
    bool t, f;
    t = (N[0] == N[1] && N[0] == N[2]);
    f = (N[1] == N[2] && N[1] == N[3]);
    if(t || f)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll;
template<class T>using vv = vector<vector<T>>; template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T>bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T>bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

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

    if (N < 3) {
        write("No");
        return 0;
    }

    int bcnt = 0, i = 0, msb = -1;
    for (int i = 0; i < 31; ++i) {
        if (N >> i & 1) {
            bcnt++;
            msb = i;
        }
    }
    if (bcnt == 1) {
        write("No");
        return 0;
    }

    write("Yes");
    vector<pair<int, int>> edge;
    edge.emplace_back(1, 2);
    edge.emplace_back(2, 3);
    edge.emplace_back(3, N + 1);
    edge.emplace_back(N + 1, N + 2);
    edge.emplace_back(N + 2, N + 3);

    for (int i = 4; i < N; i += 2) {
        edge.emplace_back(i, i + 1);
        edge.emplace_back(i + 1, N + 1);
        edge.emplace_back(N + 1, N + i);
        edge.emplace_back(N + i, N + i + 1);
    }

    if (N % 2 == 0) {
        int n = (N ^ (1 << msb)) + 1;
        edge.emplace_back(N, N + (1 << msb));
        edge.emplace_back(n, N + N);
    }

    for (auto& e : edge) {
        cout << e.first << " " << e.second << endl;
    }
}

Measured memory_bytes: 4464
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		City[] cities = new City[n];
		for (int i = 0; i < n; i++) {
			cities[i] = new City(i, sc.nextInt(), sc.nextInt());
		}
		Arrays.sort(cities, new Comparator<City>() {
		public int compare(City c1, City c2) {
			return c1.x - c2.x;
        }
		});
		Road[] roads = new Road[(n - 1) * 2];
		for (int i = 0; i < n - 1; i++) {
			roads[i] = new Road(cities[i].id, cities[i + 1].id, cities[i + 1].x - cities[i].x);
		}
		Arrays.sort(cities, new Comparator<City>() {
		public int compare(City c1, City c2) {
			return c1.y - c2.y;
        }
		});
		for (int i = 0; i < n - 1; i++) {
			roads[n - 1 + i] = new Road(cities[i].id, cities[i + 1].id, cities[i + 1].y - cities[i].y);
		}
		Arrays.sort(roads, new Comparator<Road>() {
		public int compare(Road r1, Road r2) {
			return r1.cost - r2.cost;
        }
		});
		Tree t = new Tree(n);
		long sum = 0;
		for (Road r : roads) {
			if (t.find(r.src) != t.find(r.dst)) {
				sum += r.cost;
				t.unite(r.src, r.dst);
			}
		}
		System.out.println(sum);
	}
	
	static class Tree {
		int size;
		int[] parent;
		int[] rank;
		
		public Tree(int size) {
			this.size = size;
			parent = new int[size];
			rank = new int[size];
			for (int i = 0; i < size; i++) {
				parent[i] = i;
				rank[i] = 0;
			}
		}
		
		public int find(int idx) {
			if (parent[idx] == idx) {
				return idx;
			} else {
				parent[idx] = find(parent[idx]);
				return parent[idx];
			}
		}
		
		public void unite(int idx1, int idx2) {
			int p1 = find(idx1);
			int p2 = find(idx2);
			if (p1 == p2) {
				return;
			}
			if (rank[p1] < rank[p2]) {
				parent[p1] = p2;
			} else {
				parent[p2] = p1;
				if (rank[p1] == rank[p2]) {
					rank[p1]++;
				}
			}
		}
	}
			
	
	static class City {
		int id;
		int x;
		int y;
		
		public City(int id, int x, int y) {
			this.id = id;
			this.x = x;
			this.y = y;
		}
	}
	
	static class Road {
		int src;
		int dst;
		int cost;
		
		public Road(int src, int dst, int cost) {
			this.src = src;
			this.dst = dst;
			this.cost = cost;
		}
	}
}


Measured memory_bytes: 98668
#include <iostream>
#include<stdio.h>
using namespace std;
 
 int main(){
     int a, b;
     cin >> a >> b;
     if(a > b){
         cout << "a > b" << endl;
     }else if(a < b){
         cout << "a < b" << endl;
     }else{
         cout << "a == b" << endl;
     }
return 0 ;
 }


Measured memory_bytes: 3048
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
//#include<unordered_map>//イテレータあるけど順序保持しないmap
//#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
#include<valarray>//なんとなく追加
//メモ：表示桁数を大きくする　　cout << fixed << setprecision(20) << cm << endl;
using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define PI acos(-1.0)
#define answer(ans) cout<<ans<<endl;
#define input(N) cin >> N ;

signed main() {
int N,ans=0,sig=1;
cin >> N;
vector<int> a(N);
REP(i,N) cin >> a[i];

REP(i,N){
if(a[i]==sig){
    sig +=1;
}
else{
    ans +=1;
}
}
if(sig == 1){
    cout << "-1" << endl;
    return 0;
}
answer(ans);

return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define debug(x) cerr<<#x<<": "<<x<<endl;
#define MOD 1000000007ULL;
#define rep(i,n) for(int i=0;i<n;i++)


int main() {
	int N;
  	cin>>N;
  	set<string> S;
  
  	rep(i,N){
      	string s;
      	cin>>s;
     	S.insert(s); 
    }
  
  	cout<<S.size()<<endl;
  
  	
  	
  
  
}

Measured memory_bytes: 19124
#pragma GCC optimize "trapv" 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define rep(i,a,n)     for(int i=a;i<n;i++)
#define rep3(n)        for(int i=0;i<n;i++)
#define inarr(arr,n)   rep(i,a,n)cin>>arr[i]
#define ll             long long int
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define eb             emplace_back
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define pres(a,x)      a.find(x)!=a.end()
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define IOS            ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ret            return 0
#define pi             3.1415926536
#define hell           1000000007
#define narak          998244353
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
const int inf1=1e9;
const ll inf2=1e18;
const int N=100000;
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
int dirs[4][2] ={{1,0},{-1,0},{0,1},{0,-1}};
int a[25][25];
ll  dp[25][(1<<22)];
ll zeno(int i,int mask,int n){
    if(i==n)return 1;
    if(dp[i][mask]!=-1)return dp[i][mask];
    dp[i][mask]=0;
    for(int j=0;j<n;j++){
        if(a[i][j] && ((mask&(1<<j))==0))dp[i][mask]=(dp[i][mask]+zeno(i+1,mask|(1<<j),n))%hell;
    }
    return dp[i][mask];
}
int solve(){
   mem1(dp); 
   int n;cin>>n;         
   for(int i=0;i<n;i++){
       for(int j=0;j<n;j++)cin>>a[i][j];
   }         
   cout<<zeno(0,0,n)<<endl;
 ret;
}
int main(){
    IOS;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef cat
    cat();
    #endif
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
    ret;
}
 

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

int main () {
    bool possible = false;
    int n;
    cin >> n;
    for (int i=1; i <=9; i++) {
        if (n%i == 0){
            int q = n/i;
            if (q < 10) {
                possible = true;
            }
        }
    }

    if (possible) {
        cout << "Yes";
    } else {
        cout << "No";
    }
     return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 60;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

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

    int n; cin >> n;
    using Edge = tuple<ll, int, int>;
    vector<Edge> edges;
    vector<vll> A(n, vll(n));
    rep(i, n){
        rep(j, n){
            ll c; cin >> c;
            A[i][j] = c;
            if(i == j) continue;
            edges.emplace_back(Edge(c, i, j));
        }
    }

    sort(_all(edges));
    ll res = 0;
    vector<vll> B(n, vll(n, inf)); rep(i, n) B[i][i] = 0;
    for(auto& e : edges){
        ll c; int a, b; tie(c, a, b) = e;
        ll min_d = inf;
        rep(k, n){
            chmin(min_d, B[a][k] + B[k][b]);
        }
        B[a][b] = B[b][a] = c;
        if(min_d < c) {
            res = -1;
            break;
        }
        if(min_d == c){
            continue;
        }
        res += c;
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 3196
import functools as F,fractions as f;n,k,*a=map(int,open(0).read().split());
P="POSSIBLE"

if max(a)<k:
    print("IM"+P)
else:
    if k%F.reduce(f.gcd,a)!=0:
        print("IM"+P)
    else:
        print(P)

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

int main(){
  ull a,b;
  cin>>a>>b;
  if(abs(a-b)<=1){
     cout<<a+b<<endl;
  }
  else{
     cout<<max(a,b)+max(a-1,b-1)<<endl;
  }

  return 0;
}


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

char s[200010];

int main(){
	scanf("%s",s);
  	int len=strlen(s);
    int sum=0;
    for(int i=0;i<len;i++) sum+=s[i]-'0';
    if(sum%9==0){
        puts("Yes");
    } else{
        puts("No");
    }
}


Measured memory_bytes: 3904
h,w=map(int,input().split());a=[input()for i in range(h)]
def che(i,j):
  global h,w,a
  if i==0:
    if a[i+1][j]=="#":return
  elif i==h-1:
    if a[i-1][j]=="#":return
  else:
    if a[i-1][j]=="#"or a[i+1][j]=="#":return
  print("No");exit()
for i in range(h):
  s=a[i]
  if s[:2]=="#.":che(i,0)
  if s[-2:]==".#":che(i,w-1)
  for j in range(w-2):
    if s[j]+s[j+1]+s[j+2]==".#.":che(i,j+1)
print("Yes")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
// define
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (((a)%mod) * ((b)%mod)) % mod
#define rollcall cout << "I'm Sucu." << endl;
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define fi first
#define se second
// debug
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
  os << "(" << p.first << "," << p.second << ")";return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  for (auto it = v.begin();it != v.end();++it){
    if(it != v.begin())os << " ";os << *it;
  }return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &mp){
  for(auto x: mp)os << "(" << x.first << "," << x.second << ")" << endl;
  return os;
}
template<typename T, int SIZE>
int array_length(const T (&)[SIZE]){return SIZE;}
template<typename T, int N>
void PRINTF(const T (&a)[N], int s = N, int t = -1, bool f = true){
	if(t == -1){rep(i,s){if(i)cout << " ";cout << a[i];}}
	else repi(i,s,t){if(i!=s)cout << " ";cout << a[i];}
	if(f)cout << "\n";
}
template<typename T, int N1, int N2>
void PRINTF(const T (&a)[N1][N2], int h = N1, int w = N2){
	rep(i,h){rep(j,w){cout << a[i][j] << " \n"[j==w-1];}}
}
string substr(const string &str, int S1, int S2 = -1){
  if(S2 == -1)return str.substr(S1);
  return str.substr(S1, S2-S1);
}
// typedef
typedef complex<double> Point;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;
// int sum = accumulate(a, a+n, 0LL);
// int mx = max_element(a, a+n);
// int mn = min_element(a, a+n);
// int cnt = count(a, a+n, k);

int a[200000];
int solve(string str){
  int n = str.size();
  rep(i,n){
    int cnt = 0;
    if(str[i] == 'A')cnt++;
    if(str[i] == 'T')cnt++;
    if(str[i] == 'G')cnt++;
    if(str[i] == 'C')cnt++;
    if(cnt == 0)return 0;
  }
  return n;
}
signed main(){
  string str;cin >> str;
  int n = str.size(), ans = 0;
  rep(i,n)rep(j,n){
    if(i > j)continue;
    ans = max(ans, solve(substr(str, i, j+1)));
  }
  cout << ans << endl;
  return 0;
}





Measured memory_bytes: 256
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

count_A = Counter(A)
# print(count_A)

gusu = 0
for a in count_A:
    if count_A[a] % 2 == 0:
        gusu += 1
print(len(count_A) - gusu % 2)

Measured memory_bytes: 62124
package main

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

func main() {
	sc := NewScanner()
	_, K := sc.NextInt(), sc.NextInt()
	S := []byte(sc.Next())

	S[K-1] = bytes.ToLower([]byte{S[K-1]})[0]

	fmt.Println(string(S))

}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *Scanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *Scanner) NextFloat() float64 {
	v, _ := strconv.ParseFloat(s.Next(), 64)
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, int(v))
			start = s.p + 1
		}
	}

	return result
}
func (s *Scanner) NextInt64Array() []int64 {
	s.pre()
	start := s.p
	result := []int64{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 64)
			result = append(result, v)
			start = s.p + 1
		}
	}
	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


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

using namespace std;

int main()
{
   
    int q;
    scanf("%d",&q);
    int i;
    long long a,b,res=0;
    char c;
    for(i=0;i<q;i++)
    {
        scanf("%lld%c%c%lld",&a,&c,&c,&b);
        //printf("%lld %c %lld ",a,c,b);
        if(c=='(') res+=b;
        else res-=b;
        //printf("%lld\n",res);
        if(!res) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

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


int main() {

	int n; cin >> n;
	int a[100]; for (int i = 0; i < n; i++) cin >> a[i];
	int ans = 0;

	bool flag = true;
	while (flag) {
		flag = false;
		for (int i = n - 1; i > 0; i--) {
			if (a[i - 1] > a[i]) {
				swap(a[i - 1], a[i]);
				ans++;
				flag = true;
			}
		}
	}

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

	cout << ans << endl;

	return 0;
}






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

using namespace std;

int main() {
  string s; cin >> s;
  int n = (int) s.size();
  int cur = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'g') {
      cur++;
    } else {
      cur--;
    }   
  }
  int suf = cur;
  int ans = 0;  
  for (int i = n - 1; i >= 0; i--) {
    if (cur < 0) {
      assert(false);
    }
    suf = min(suf, cur);
    if (s[i] == 'g') {
      if (suf - 2 >= 0) {
//        cerr << "-> " << i << endl;        
        s[i] = 'p';
        suf -= 2;  
        cur -= 2;
        ans++;
      }
    }
    if (s[i] == 'g') {
      cur--;                    
    } else {
      cur++; 
    }
  }
  cout << ans << endl;
  return 0;
}

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

#define INF 2147483647;
int *D;
int n = 1;


void initRMQ(int n_) {
    while (n < n_) {
        n *= 2;
    }
    D = new int[2 * n - 1];  
    for (int i = 0; i <= 2 * n - 1; ++i) {
        D[i] = INF;
    }
}

void update(int k, int a) {
    k += n - 1;
    D[k] = a;
    while (k > 0) {
        k = (k - 1) / 2;
        D[k] = D[k*2+1] < D[k*2+2] ? D[k*2+1] : D[k*2+2];        
    }
}

int query(int a, int b, int k, int l, int r) {

    if (r <= a || b <= l) {
        return INF;
    }
    if (a <= l && r <= b) {
        return D[k];
    }
    return min(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
}

int findMin(int a, int b) {
    return query(a, b + 1, 0, 0, n);
}

int main() {
    int size;
    int q;
    int x, y;
    int operation;
    cin >> size >> q;
    initRMQ(size);
    for (int i = 0; i < q; ++i) {
        cin >> operation >> x >> y;
        if (operation == 0) {
            update(x, y);
        } else {
            cout << findMin(x, y) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 4112
def main():
    n, a, b, c, d = map(int, raw_input().split())
    s = '#' + raw_input().strip() + '...'
    f = 0
    for i in xrange(b, d):
        if s[i] == '#' and s[i+1] == '#':
            print 'No'
            return
        if s[i] == '.' and s[i+1] == '.' and s[i+2] == '.':
            f = 1
    for i in xrange(a, c):
        if s[i] == '#' and s[i+1] == '#':
            print 'No'
            return
    if c > d:
        if s[b-1] == '.' and s[b+1] == '.':
            f = 1
        if not f:
            print 'No'
            return
    print 'Yes'
main()


Measured memory_bytes: 3180
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <numeric>
#include <bitset>

using namespace std;
using ll = long long;
using ld = long double;
const ll mod =  1000000007;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define all(x) (x).begin(),(x).end()

ll power(ll base, ll exponent){ if(exponent % 2){ return power(base, exponent - 1) * base % mod; }else if(exponent){ ll root_ans = power(base, exponent / 2); return root_ans * root_ans % mod; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
struct combination{ vector<ll> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

int bsearch(const vector<ll>& a, ll x){
  int lft = 0;
  int rgt = a.size();
  while (rgt - lft > 1) {
    int mid = (lft + rgt) / 2;
    if(a[mid] < x) {
      lft = mid;
    }
    else {
      rgt = mid;
    }
  }
  return lft;
}
vector<vector<int>> to;
vector<ll> fact, inv;
ll K;

ll dfs(int c, int from) {
  ll ans = 0;
  if(from == -1) {
    ans = fact[K-1] % mod * inv[K-1-to[c].size()] % mod;
  }
  else {
    ans = fact[K-2] % mod * inv[K-2-to[c].size()+1] % mod;
  }
    if(K < to[c].size()) {
      return 0;
    }
  for(const auto i: to[c]) {
    if(i==from) continue;
    ans *= dfs(i, c);
    ans %= mod;
  }
  return ans;
}
signed main() {
  ios::sync_with_stdio(false);
  ll n;
  cin >> n >> K;
  to = vector<vector<int>>(n);
  REP(i, n-1) {
    int a, b;
    cin >> a >> b;
    a--;b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  fact = vector<ll>(K+1);
  inv = vector<ll>(K+1);
  fact[0] = 1;
  inv[0] = 1;
  REP(i, K) {
    fact[i+1] = fact[i] * (i+1) % mod;
    inv[i+1] = inverse(fact[i+1]);
  }
  for(const auto & tmp : to) {
    if(K < tmp.size() + 1) {
      cout << 0 << endl;
      return 0;
    }
  }
  ll ans =  K * dfs(0, -1) % mod;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 10368
x, y = map(int, input().split())

if 0 <= x <= y or x <= y <= 0:
    print(y - x)
elif x <= 0 <= y:
    if x == 0 or y == 0:
        print(abs(x + y))
    else:
        print(abs(y + x) + 1)
elif 0 <= y <= x or y <= x <= 0:
    if x == 0 or y == 0:
        print(abs(x - y) + 1)
    else:
        print(abs(x - y) + 2)
else:
    print(abs(x + y) + 1)

Measured memory_bytes: 3064
import itertools
N = int(input())
s = []
def str_sort(x, s = False):
    y = sorted(x, reverse = s)
    return ''.join(y)

for i in range(N):
    si = str_sort(input())
    s.append(si)
s.sort()

ans = 0
gr = itertools.groupby(s)
for key, group in gr:
    n = len(list(group))

    ans += n*(n-1)//2

print(ans)


Measured memory_bytes: 62552
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
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 int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int n, h, w;
    cin >> n >> h >> w;
    cout << (n-h+1) * (n-w+1) << endl;
}


Measured memory_bytes: 256
A,B,C,X,Y = map(int,input().split())
ans = A*X+B*Y
for i in range(1,max(X,Y)+1):
    a = A*(X-i) if X-i>0 else 0
    b = B*(Y-i) if Y-i>0 else 0
    tmp = a+b+C*i*2
    ans = min(ans,tmp)
print(ans)


Measured memory_bytes: 39408
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
 
int main() {
    int N; cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++) cin >> A[i];

    vector<int> divs;
    for(int i=1; i*i<=N; i++) {
        if(N % i == 0) {
            divs.emplace_back(i);
            divs.emplace_back(N / i);
        }
    }

    int ans = -1;
    for(auto d : divs) {
        bool ok = true;
        for(int i=0; i<d; i++) {
            for(int j=i; j<N; j+=d) {
                ok &= (A[i] == A[j]);
            }
        }
        if(ok) ans = max(ans, N / d);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3616
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use num_traits::clamp;
use ordered_float::OrderedFloat;
use proconio::{input, marker::*, fastout};
use superslice::*;

fn main() {
    input! {
        n: usize, s: Chars
    }

    let mut low = 0;
    let mut high = n/2 + 1;
    'outer: while high > low + 1 {
        let mid = (low + high) / 2;
        for i in 0..n-mid {
            for j in i+mid..=n-mid {
                if s[i..i+mid] == s[j..j+mid] {
                    low = mid;
                    continue 'outer;
                }
            }
        }
        high = mid;
    }
    println!("{}", low);
}


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

int main() {
    string s;
    cin >> s;
    int ans=700;
    rep(i, s.size()) {
        if(s[i]=='o') ans += 100;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
N, M = gets.split.map(&:to_i)
connects = Array.new(M) { gets.split.map(&:to_i) }
connects += connects.map { |e1,e2| [e2,e1] }

now = 1
visited = [now] # point

stack = [visited]
ans = []

until stack.empty? do
  visited = stack.shift
  remain = N - visited.size
  now = visited[-1]
  1.upto(N) do |i|
    next if i == now
    if connects.include? [now,i]
      unless visited.include? i
        new_visited = visited + [i]
        stack << new_visited
        ans << new_visited if new_visited.size == N
        # p new_visited
      end
    end
  end
end

# p '-----------------------'
p ans.size


Measured memory_bytes: 15204
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
  ll N;
  cin >> N;
  for (ll l = 1; l <= 3500; l ++) {
    for (ll k = 1; k <= 3500; k ++) {
      ll p = 4 * l * k - N * l - N * k;
      ll q = N * k * l;
      if (p > 0 && q % p == 0) {
        cout << l << ' ' << k << ' ' << q / p << endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 3596
// 2011/04/03 Tazoe

#include <iostream>
#include <string>
using namespace std;

int main()
{
	while(true){
		string str;
		cin >> str;
		if(cin.eof())
			break;

		for(int i=0; i<str.size(); i++){
			if(str[i]=='@'){
				i++;
				int n = str[i]-'0';
				i++;
				for(int j=0; j<n; j++)
					cout << str[i];
			}
			else{
				cout << str[i];
			}
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 0
N = input()
A = sorted(map(int, raw_input().split()))
B = sorted(map(int, raw_input().split()))
C = sorted(map(int, raw_input().split()))

TB = [0]*len(B)
a = 0
for b in range(len(B)):
    while a<len(A) and A[a]<B[b]:
        a += 1
    TB[b] = a
TC = [0]*len(C)
b = 0
s = 0
for c in range(len(C)):
    while b<len(B) and B[b]<C[c]:
        s += TB[b]
        b += 1
    TC[c] = s
print sum(TC)


Measured memory_bytes: 21664
#include<stdio.h>
#include<string.h>
int d;
int q;

typedef struct {
  char name[100];
  int t;
}Process;

Process Q[10000000];
int n;
int head=0, tail=0;


void enqueue(Process x){
  Q[head]=x;
  head++;
}

Process dequeue(){
  tail++;
  return Q[tail-1];
}

int main(void){
  int i,j;
  int count;
  int time=0;
  Process x;
  scanf("%d %d", &n, &q);
  
  for ( i = 0; i < n; i++){
    scanf("%s", x.name);
    scanf("%d", &x.t);
    enqueue(x);
  }
  
  while(1){
    x=dequeue();
    if(x.t<=q){
      time+=x.t;
      printf("%s %d\n", x.name, time);
    }
    else{
      x.t-=q;
      time+=q;
      enqueue(x);
    }
    if(head-tail==0)break;
  }
  return 0;
}

Measured memory_bytes: 21072
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define ll long long
 
//const int INF = 1e8;
typedef pair<int,int>P;
int dx[4] = {1,0,-1,0};int dy[4] = {0,1,0,-1};
queue<P> que;

int main(){
  int n;cin >> n;
  int l;cin >> l;
  int sum = 0;
  if(l>= 0){
    for(int i = 1;i<n;i++){
      sum += l + i;
    }
  }else if(l< 0 and l+n-1>0){
    for(int i = 0;i<n;i++){
      sum += l + i;
    }
  }else{
    for(int i = 0;i<n-1;i++){
      sum += l +i;
    }
  }
  cout << sum << endl;
} 

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

using namespace std;

pair<string, int> a[100];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
	string s;
	cin >> s;
	int ans = 0, pos = -1;
	for (int i = 0; i < n; i++) {
		if (a[i].first == s) {
			pos = i; break;
		}
	}
	for (int i = pos + 1; i < n; i++) ans += a[i].second;
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 256
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
  ww,vv=map(int,input().split())
  w.append(ww)
  v.append(vv)
dp=[[0]*(W+1) for i in range(N+1)]

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

print(dp[-1][-1])


Measured memory_bytes: 147280
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

struct fruit{
    double r;
    string name;
    fruit(){}
    ~fruit(){}
    fruit(double a, string b): r(a), name(b) {}
    bool operator < (const fruit& o) const {
        return r == o.r ? name < o.name : r > o.r;
    }
};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    while(true){
        cin >> N;
        if(N == 0) break;
        fruit fr[50];
        for(int i = 0; i < N; i++){
            string l;
            int p, a, b, c, d, e, f, s, m;
            cin >> l >> p >> a >> b >> c >> d >> e >> f >> s >> m;
            fr[i].name = l;
            fr[i].r = (double)(m * f * s - p) / (a + b + c + (d + e) * m);
        }
        sort(fr, fr + N);
        for(int i = 0; i < N; i++){
            cout << fr[i].name << endl;
        }
        cout << "#" << endl;
    }
    return 0;
}

Measured memory_bytes: 1224
#include <stdio.h>

int main(){
  int x,y,tem,mod;

  scanf("%d%d",&x,&y);
  if(y>x){
    tem = x;
    x = y;
    y = tem;
  }

  while(1){
    mod = x % y;
    if(mod == 0) break;
    x = y;
    y = mod;
  }

  printf("%d\n",y);
  return 0;
}



Measured memory_bytes: 2144
#include<iostream>

const int N = 10;
int b[N],m,n;

void erace(){
	for(int i=0; i<N; i++)
		b[i] = 0;
}

void show(){
	for(int i=0; i<N; i++){
		if(b[i]==0)
			std::cout << '-';
		else
			for(int n=0; n<b[i]; n++)
				std::cout << '*';
		std::cout << std::endl;
	}
}

int main(){
	while(true){
		std::cin >> n;
		if(!n)
			return 0;
		erace();
		for(int i=0; i<n; i++){
			std::cin >> m;
			b[m]++;
		}
		show();
	}
	return 0;
}

Measured memory_bytes: 0
n=int(input())
a=map(lambda x: int(x)//400,input().split())
b=set()
c=0
for v in a:
  if v>=8:
    c+=1
  else:
    b.add(v)
if len(b)==0:
  print('1 '+str(c))
else:
  print(str(len(b))+' '+str(len(b)+c))


Measured memory_bytes: 2940
N,M,Q = map(int,input().split())
plane = [[0]*N for _ in range(N)]
for i in range(M):
    l,r = map(int,input().split())
    plane[l-1][r-1] += 1
acc = [[0]*(N+1) for _ in range(N)]

for i in range(N):
    for j in range(N):
        acc[i][j+1] = acc[i][j]+plane[i][j]

for i in range(Q):
    p,q = map(int,input().split())
    tmp = 0
    for j in range(p,q+1):
        tmp += acc[j-1][q]-acc[j-1][p-1]
    print(tmp)

Measured memory_bytes: 55384