akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
#define Yes "Yes"
#define No "No"
#define YES "YES"
#define NO "NO"
typedef long long ll;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

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

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/

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

    string s;
    cin >> s;
    int N = s.size();
    //終わりが奇数長
    if(s.front() == s.back()){
        //最初が奇数長
        if(N & 1){
            cout << "Second" << endl;
        }
        else{
            cout << "First" << endl;
        }
    }
    else{
        if(N & 1)cout << "First" << endl;
        else cout << "Second" << endl;
    }
}

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


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

  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> x(n);
  rep(i,n){
    x[i] = s[i] -'0';
  }
  int cnt=0;
  rep(i,n){
    if(x[i]) cnt++;
  }
  // cout <<"cnt "<< cnt << endl;

  if(cnt==1){
    rep(i,n){
      if(x[i]) cout << 0 << endl;
      else if(x[n-1]==1 || i==n-1){
        cout << 2 << endl;
      }
      else{
        cout << 1 << endl;
      }
    }
    return 0;
  }
  else if(cnt==0){
    rep(i,n){
      cout << 1 << endl;
    }
    return 0;
  }
  vector<int> modp(n),modn(n);
  ll sump,sumn;
  sumn = sump = 0;
  ll vp,vn;
  vp=vn=1;
  rep(i,n){
    modp[n-1-i]=vp;
    modn[n-1-i]=vn;
    // cout << vp <<" " << vn <<  " " << sump <<" " << sumn << endl;
    vp = vp<<1;
    vn = vn<<1;
    vp%=(cnt+1);
    vn%=(cnt-1);

    if(x[n-1-i]){
      sump += modp[n-1-i];
      sump %= (cnt+1);
      sumn += modn[n-1-i];
      sumn %= (cnt-1);
    }


  }
  // cout << sump << " " << sumn << endl;
  rep(i,n){
    ll v = 0;
    if(x[i]==0){
      v = sump + modp[i];
      v%=cnt+1;
    }
    else{
      v = sumn - modn[i];
      if(v<0)v+=cnt-1;
    }
    // cout << "v " << v << endl;
    ll res = 1;
    while(v>0){
      ll pcnt = __builtin_popcount(v);
      v = v%pcnt;
      res++;
    }
    cout << res << endl;
  }
  
  return 0;
    

}


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

int main() {
	int a,b,c,k;
	string ans = "No";
	cin >> a >> b >> c;
	cin >> k;
	for (int i = 0; i <= k; i++) {
		int B, C;
		B = b * pow(2, i);
		C = c * pow(2, (k - i));
		if (a < B && B < C) {
			ans = "Yes";
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4104
(* O(|xs|) *)
let list_count f = List.fold_left (fun n x -> if f x then n + 1 else n) 0

(* O(n * m) *)
let solve n m c bs as_s =
  list_count
    (fun a_s -> c + List.fold_left2 (fun sum a b -> sum + a * b) 0 a_s bs > 0)
    as_s

let read_ints () = read_line () |> Str.split (Str.regexp " ") |> List.map int_of_string

(* O(n) *)
let rec fold_btw f a i n = if i >= n then a else fold_btw f (f a i) (i + 1) n
let fold_int f a n = fold_btw f a 0 n

let _ =
  match read_ints () with
  | [n; m; c] ->
    let bs = read_ints () in
    fold_int
      (fun acc _ -> read_ints () :: acc)
      []
      n |> solve n m c bs |> string_of_int |> print_endline
  | _ -> ()

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main(){
    int N,L;
    string ans;
    cin >> N >> L;
    vector<string> s(N);
    for(int i=0;i<N;i++){
        cin >> s[i];
    }
    sort(s.begin(),s.end());
    for(int i=0;i<N;i++){
        ans+= s[i];
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int h,w;
  cin>>h>>w;
  for(int i=0;i<w+2;i++){
    cout<<'#';
  }
  cout<<endl;
  for(int i=0;i<h;i++){
    string s;
    cin>>s;
    cout<<'#'<<s<<'#'<<endl;

  }
  for(int i=0;i<w+2;i++){
    cout<<'#';
  }


}

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

using namespace std;
using ull = unsigned long long;

ull solve(ull a, ull b){
	if(a == b){ return 1; }
	const ull c = a ^ b;
	const int s = 63 - __builtin_clzll(c);
	const ull m = (1ull << s) - 1;
	const ull x = solve(a & m, m);
	const ull ya = (a | m) - a + 1;
	const ull yb =
		(b & m) ? (1ull << (64 - __builtin_clzll(b & m))) : 1;
	const ull y = min(m + 1, ya + yb);
	const ull ans = x + y;
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	ull a, b;
	cin >> a >> b;
	const ull answer = solve(a, b);
	cout << answer << endl;
	return 0;
}



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

int main() {
    long long N, A[4], i;
    scanf("%lld %lld %lld %lld", &A[0], &A[1], &A[2], &A[3]);
    for (i = 0; i < 3; ++i) A[i + 1] = min(A[i + 1], A[i] * 2);
    scanf("%lld", &N);
    printf("%lld\n", N / 2 * A[3] + N % 2 * A[2]);
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

    int main(){

        int x, a, b, disA, disB;
        scanf("%d %d %d", &x, &a, &b);
        disA = x - a;
        if(disA<0)
            disA = (-1)*disA;

        disB = x - b;
        if(disB<0)
            disB = (-1)*disB;
        if(disA<=disB)
            printf("A");
        else
            printf("B");
        return 0;
        }


Measured memory_bytes: 128
#include<stdio.h>
#include<algorithm>
using namespace std;
long long a[200010];
int t[200010];
int main()
{
    int n;
    long long ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    sort(a,a+n);
    t[n-1]=1;int j=n-1;
    for(int i=1;i<n;i++)
    {
    	if(t[j]==2)j--;
    	ans+=a[j];t[j]++;
    	
	}
	printf("%lld ",ans);
    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int>> vpii;
typedef pair<int, int> pii;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(a) (a).begin(), (a).end()
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

int main(){
	ll a, b; scanf("%lld%lld", &a, &b);
	printf("%lld\n", a*b/__gcd(a, b));
}


Measured memory_bytes: 256
words = lambda t : list(map(t, input().split()))
x,y = words(int)

ans = 0
if x == 3:
    ans += 100000
if y == 3:
    ans += 100000
if x == 2:
    ans += 200000
if y == 2:
    ans += 200000
if x == 1:
    ans += 300000
if y == 1:
    ans += 300000
if x == 1 and y == 1:
    ans += 400000
print(ans)


Measured memory_bytes: 38256
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using boost::irange;
typedef long long ll;
const ll mod = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i: irange(0, N))
        cin >> A[i];

    sort(A.begin(), A.end());
    ll ans = 1;
    int cnt = 0;
    int hikae = -1;
    for (int i = N - 1; i >= 0; i--) {
        if (hikae == -1) {
            hikae = A[i];
        } else if (hikae == A[i]) {
            ans *= A[i];
            hikae = -1;
            cnt++;
            if (cnt == 2) {
                cout << ans << endl;
                exit(0);
            }
        } else {
            hikae = A[i];
        }
    }
    cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 640
import java.util.*;
import java.lang.*;
public class Main {
        public static void main (String[]args){
            Scanner scanner = new Scanner(System.in);
            long n = scanner.nextLong();
            long a =scanner.nextLong();
            long b =scanner.nextLong();
            long totalPlaced=n/(a+b);
            long remainder=n%(a+b);
            long totalA=0;
            if(remainder>a){
                totalA+=a;
            }else{
                totalA+=remainder;
            }
            totalA+=(totalPlaced*a);
            System.out.println(totalA);

    }
}





Measured memory_bytes: 25556
#include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
     
    int main() {
        string S, T;
        cin >> S >> T;
      
        int ans = T.size();
     
        for (int start = 0; start <= S.size() - T.size(); start++)
        {
            int diff = 0;
            for (int i = 0; i < T.size(); i++)
            {
                if (T[i] != S[start + i]) {
                    diff++;
                }
            }
            ans = min(ans, diff);
        }
     
        cout << ans << endl;
    }

Measured memory_bytes: 3592
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

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

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

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

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)
	N := getInt()
	m := make(map[int]int)
	for i := 0; i < N; i++ {
		a := getInt()
		if a >= 3200 {
			m[8]++
		} else {
			m[a/400]++
		}
	}

	// out(m)
	if m[8] != 0 {
		if len(m) == 1 {
			out(1, m[8])
		} else {
			out(len(m)-1, len(m)-1+m[8])
		}
	} else {
		out(len(m), len(m))
	}
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
const int N = 2e5+1;
ll a[N];
ll pre[N];
ll ans = 1e18;
ll sum(int l,int r)		{	return pre[r] - pre[l-1];	}
int main()
{
	pre[0]=0ll;
	int n,i,j,k,l,r,pos;
	scanf("%d",&n);
	for(i=1;i<=n;++i)	scanf("%lld",&a[i]);
	for(i=1;i<=n;++i)	pre[i] = pre[i-1] + a[i];
	for(i=2;i<=n;++i)
	{
		l=1;r=i-1;pos=l;
		while(l<=r) 
		{
			int mid=(l+r)/2;
			if(2*pre[mid]>pre[i]) 	r=mid-1;
			else 					
			{
				pos=mid;
				l=mid+1;
			}
		}
		int lower_bound=pos;
		l=i+1;r=n-1;pos=l;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(2*sum(i+1,mid)>sum(i+1,n)) r=mid-1;
			else 							
			{
				pos=mid;
				l=mid+1;
			}
		}
		int upper_bound=pos;
		for(j=lower_bound-5;j<=lower_bound+5;j++)
		{
			for(k=upper_bound-5;k<=upper_bound+5;k++)
			{
				if(j>0&&j<i&&k>i&&k<n)
				{
					ll a = pre[j];
					ll b = sum(j+1,i);
					ll c = sum(i+1,k);
					ll d = sum(k+1,n);
					ll mn = min(min(a,b),min(c,d));
					ll mx = max(max(a,b),max(c,d));
					ans=min(ans,mx-mn);
				}
			}
		}
	}	
	printf("%lld",ans);
}


Measured memory_bytes: 6916
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif

#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define bp __builtin_popcount
#define debug(x) cerr << #x << " = " << x << endl;

const int MOD = 1e9 + 7;
const int INF = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>void print(T t){for(auto &it : t)cout<<it<<" ";}
inline int powerexp(int a, int b, int m){ int res = 1;while(b){if(b&1)res = res * a % m;a = a * a % m,b >>= 1;}return res % m;}
inline int modinv(int a){ return powerexp(a,MOD-2,MOD);}
inline int lcm(int a, int b){ int g = __gcd(a,b);return a/g*b;}
inline int add(int x, int y){ x += y; if (x >= MOD) x -=  MOD; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % MOD;}
inline int sub(int x, int y){ x -= y; if (x<0) x += MOD; return x ;}

//-------------------< start here >-------------------------// 
const int N = 1e5 + 11;
int cnt[N];
bool isRed[N];
int n, m;

void solve(){
	 cin >> n >> m;
	 for(int i = 1; i <=n; i++){
		 cnt[i] = 1;
		 isRed[i] = (i == 1); 
	  }
	 for(int i = 0; i < m; i++){
		 int x, y;
		 cin >> x >> y;
		 if (isRed[x]) isRed[y] = 1;
		 if (cnt[x] == 1) isRed[x] = 0;
		 cnt[x]--;
		 cnt[y]++;
	 }
	 int ret = 0;
	 for(int i = 1; i <= n; i++){
	   ret += isRed[i];	 
	}
	cout << ret << endl;
}

//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
   IOS;
   solve();
   //find();
   #ifdef LOCAL_DEFINE
   cerr << "time elapsed " << (double)clock()/CLOCKS_PER_SEC << endl;
   #endif
}


Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;
const int M = 100;

int main(){
	int n;
	while(cin >> n && n){
		int num[N+1];
		fill(num, num + N + 1, 0);
		for(int i=0;i<M;i++){
			char c;
			cin >> c;
			num[i%n]++;
			if(c == 'S'){
				num[n] += num[i%n];
				num[i%n] = 0; 
			}else if(c == 'L'){
				num[i%n] += num[n];
				num[n] = 0;
			}
		}
		sort(num, num + n);
		for(int i=0;i<=n;i++){
			if(i) cout << " ";
			cout << num[i];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1184
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<cstdint>
#include<bits/stdc++.h>
#include<queue>
#include<set>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for(int i = n-1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define INF bit(60)
#define pb push_back
#define mod 1000000007

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using namespace std;
using uif=uint_fast64_t;
using ll=long long int;

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


#define FACSIZE 2002

ll invfac[FACSIZE];
ll fac[FACSIZE];

ll mod_pow(ll ,ll );
ll mod_add(ll ,ll );
ll mod_mul(ll ,ll );
ll mod_div(ll ,ll );
void make_fact(ll );
void make_invfact(ll );

ll node[100001];

void init(){
  rep(i,100001) node[i]=i;
}

ll root(ll idx){
  if( node[idx]==idx ) return idx;
  else return node[idx]=root( node[idx] );
}

void unite(ll x,ll y){
  auto rx=root(x);
  auto ry=root(y);
  node[ry] = rx;
}

bool same(ll x,ll y){
  return root(x)==root(y);
}

int main(void){

  ll n,m;
  cin>>n>>m;

  vector<ll> x(m);
  vector<ll> y(m);
  vector<ll> z(m);

  init();

  rep(i,m) cin>>x[i]>>y[i]>>z[i];

  rep(i,m) unite( x[i],y[i] );

  set<ll> se;

  rep1(i,n){
    auto r=root(node[i]);
    //cout << r << endl;
    se.insert( r );
  }

  cout << se.size() << endl;

  return 0;

}

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 t*t %mod;
  } 
  else{
    ll t=mod_pow(x,r/2)%mod;
    ll k= t*t %mod;
    return k*x%mod;
  } 
}
ll mod_add(ll a,ll b){
  return (a+b)%mod;
}

ll mod_mul(ll a,ll b){
  return (a*b)%mod;
}

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

void make_fact(ll n){
  fac[0]=1;
  rep(i,n){
    fac[i+1]=mod_mul(fac[i],i+1);
  }  
}

void make_invfact(ll n){
  invfac[n]= mod_pow( fac[n] ,mod-2);
  for(int i=n-1;i>=0;i--){
    invfac[i]=mod_mul(invfac[i+1],i+1);
  }

}


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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef map<ll,ll>::iterator itll;
typedef long double ld;
typedef map<ll,ll> mapll;

#define con continue
#define pb push_back
#define fi first
#define se second
#define fr front()
#define INF 1000000000000000000
#define all(vl) vl.begin(),vl.end()
#define m_p make_pair 
#define sz(a) sizeof(a)
#define forn(mp,it) for(it = mp.begin();it!=mp.end();it++)
#define FOR(i,a,n) for(int i=a;i<n;i++) 
#define FORE(i,a,n) FOR(i,a,n+1)
#define Endl endl
#define eNdl endl
#define enDl endl
#define endL endl

int main()
{
	ll n,k;
	cin>>k>>n;
	vector<ll> vl(n);
	FOR(i,0,n)cin>>vl[i];
	vector<ll> dist;
	FOR(i,0,n)
	{
		if(i == 0)
		{
			dist.push_back(vl[0]+k-vl[n-1]);continue;
		}
		dist.push_back(vl[i]-vl[i-1]);
	 } 
	sort(all(dist));
	ll he = 0;
	FOR(i,0,dist.size()-1)
	{
		he+=dist[i];
	 } 
	cout<<he<<Endl;
	return 0;
} 


Measured memory_bytes: 6912
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

N=get_nsp.map(&:to_i)
K=gets.to_i
L=N.size
D=K>L ? K : L
dp=Array.new(L+1){Array.new(2){Array.new(D+1){0}}}

dp[0][0][0]=1
L.times do|i|
  2.times do|j|
    D.times do|k|
      lim=(j==1 ? 10 : N[i]+1)
      lim.times do|d|
        dp[i+1][j==1||d<N[i] ? 1 : 0][k+(d.zero? ? 0 : 1)]+=dp[i][j][k]
      end
    end
  end
end
puts dp[L][0][K]+dp[L][1][K]

Measured memory_bytes: 2684
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;
// vector<vector<int>> data(3, vector<int>(4));

priority_queue<ll> que, que1, que2;

int main(){	
	long long N;
	scanf("%lld",&N);
	que1.push(3);
	que1.push(5);
	que1.push(7);
	que.push(3);
	que.push(5);
	que.push(7);
	rep(i, 8) {
		while(!que1.empty()) {
			ll q = que1.top();
			que1.pop();
			que.push(q*10+3);
			que.push(q*10+5);
			que.push(q*10+7);
			que2.push(q*10+3);
			que2.push(q*10+5);
			que2.push(q*10+7);
		}
		while(!que2.empty()) {
			que1.push(que2.top());
			que2.pop();
		}
	}
	ll res = 0;
	while(!que.empty()) {
		ll q = que.top();
		ll s = 0, f = 0, t = 0; 
		while(q != 0) {
			if (q%10 == 3) t++;
			if (q%10 == 5) f++;
			if (q%10 == 7) s++;
			q /= 10;
		}
		if (t >= 1 && f >= 1 && s >= 1 && que.top() <= N) res++;
		que.pop();
	}
	cout << res << endl;
	return 0;
}



Measured memory_bytes: 1072
import math

def comb(n,r):
  return math.factorial(n)//(math.factorial(n-r) * math.factorial(r))

s=int(input())

sm=1

if s<3:
  print("0")
else:
  for i in range(2,(s//3)+1):
    a=s-(i*3)
    #print(i,",",a)
    sm+=comb(i+a-1,i-1)
    #print(sm)
  print(sm%((10**9)+7))

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

struct Dice {
    std::vector<int> dice;  // {top, front, right, bottom, back, left};
    std::vector<int> NORTH, EAST, WEST, SOUTH, LEFT, RIGHT;
    Dice(): 
        dice{1, 2, 3, 6, 5, 4},
        NORTH{1, 3, 2, 4, 0, 5},
        EAST{5, 1, 0, 2, 4, 3},
        WEST{2, 1, 3, 5, 4, 0},
        SOUTH{4, 0, 2, 1, 3, 5},
        LEFT{0, 5, 1, 3, 2, 4},
        RIGHT{0, 2, 4, 3, 5, 1}
    {}
    int kurukuru(char op) {
        std::vector<int> p;
        if (op == 'N') {
            p = NORTH;
        } else if (op == 'E') {
            p = EAST;
        } else if (op == 'W') {
            p = WEST;
        } else if (op == 'S') {
            p = SOUTH;
        } else if (op == 'L') {
            p = LEFT;
        } else if (op == 'R') {
            p = RIGHT;
        }

        std::vector<int> tmp(6);
        for (int i=0; i<6; ++i)
            tmp[i] = dice[p[i]];

        dice = std::move(tmp);

        return dice[0];
    }
};

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

    if (n == 0)
        return 1;

    Dice d;
    int res=1;
    for (int i=0; i<n; ++i) {
        char buf[16];
        scanf("%s", buf);
        res += d.kurukuru(buf[0]);
    }

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

int main() {
    while (true)
        if (testcase_ends()) break;

    return 0;
}

Measured memory_bytes: 3216
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = 10 ** 20


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n,k=LI()
ans=0
if k==0:
    print(n*n)
    exit()
for b in range(k+1,n+1):
    ans+=(n+1)//b*(b-k)+max(0,(n+1)%b-k)

print(ans)

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

int main(){
	int n,cnt=0,ans=0;
	cin>>n;
	int a[205];
	for(int j=0; j<n; j++) cin>>a[j];

	while(1==1){
		for(int i=0; i<n; i++){
			if(a[i] % 2 ==0){
				cnt++;
				a[i] = a[i] / 2;
			}
		}
		if(cnt==n){
			ans++;
			cnt=0;
		}else{
			cout<<ans<<endl;
			return 0;
		}
	}
}


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

typedef long long ll;

#define REP(i, N) for (int i = 0; i < (int)(N); i++)

// chmax, chmin
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using P = pair<int,int>;

int main() {
    int H,W,D;
    cin >> H >> W >> D;
    
    map<int,P> m;
    REP(x,H)REP(y,W){
        int a;
        cin >> a;
        m[a] = make_pair(x,y);
    }
    int Q;
    cin >> Q;
    
    vector<ll> d(90010,0);
    for ( int i = D; i < 90010; ++i){
        P pb = m[i-D], p = m[i];
        int xb = pb.first, yb = pb.second, x = p.first, y = p.second;
        d[i] = d[i-D] + abs(x-xb) + abs(y-yb);
    }
    
    REP(i,Q){
        int l,r;
        cin >> l >> r;
        ll cost = d[r] - d[l];
        cout << cost << endl;
    }
    
    return 0;
}

Measured memory_bytes: 9580
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    ll n;
    cin >> n;
    vector <ll> arr(n);
    vector <ll> sarr;
    for (int z=0;z<n;z++){
        cin >> arr[z];
    }
    sarr = arr;
    sort(sarr.begin(),sarr.end());
    ll c = 0;
    for (int z=0;z<n;z++){
        if (sarr[z] != arr[z]){
            c++;
        }
    }
    if (c <= 2){
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;     
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    long long t,x,ans=0,cnt=0,mi=1e9+7;
    cin>>t;
    while(t--){
        cin>>x;
        if(x<0) {
            x*=-1;
            cnt++;
        }
        mi=min(mi,x);
        ans+=x;
    }
    if(cnt&1) ans-=2*mi;
    cout<<ans;
}

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

template<class T> inline T gcd(T a,T b)//NOTES:gcd( 
  {if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}

template<class T> inline T lcm(T a,T b)//NOTES:lcm( 
  {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));} 

int main(){
	long long a, b, c, d;
	cin>>a>>b>>c>>d;
	long l = lcm(c, d);
	a--;
	long res = (b - b / c - b / d + b / l) - (a - a / c - a / d + a / l);	
	cout<<res<<endl;
	return 0;
}

// 10 40 6 8

// 5 1


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

int main(){
    int N;
    cin >> N;
    ll ans = 0;
    ll A[N], B[N];
    rep(i, N){
        cin >> A[i] >> B[i];
        ans -= B[i];
        A[i] += B[i];
    }
    sort(A, A+N, greater<ll>());
    for(int i = 0; i < N; i += 2){
        ans += A[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
s = list(input())
s.reverse()
ans = 0
for i in range(len(s)):
  if len(s)%2 == 1:
    ans += 1
    del s[0]
  else:
 
    if s[:len(s)//2] == s[len(s)//2:]:
      if ans != 0:
        print(len(s))
        break
      else:
        ans += 1
        del s[0]
    else:
      ans += 1
      del s[0]

Measured memory_bytes: 3060
<?php
$input = input();
$trump = trump();

for($i = 0; $i < $input ; $i++){
    list($mark,$num) = exinput();
    $trump[$mark][$num] = "check";
}

foreach($trump as $key => $value){
    for($j = 1; $j <= 13; $j++){
        if(! isset($trump[$key][$j])){
            printf("%s %d%s", $key, $j, PHP_EOL);
        }
    }
}

function input(){
    return trim(fgets(STDIN));
}

function exinput(){
    return explode(" ", trim(fgets(STDIN)));
}

function trump(){
    return array(
        "S" => array_fill(1, 13, null),
        "H" => array_fill(1, 13, null),
        "C" => array_fill(1, 13, null),
        "D" => array_fill(1, 13, null),
        );
}

Measured memory_bytes: 15488
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	int h,w;
	cin>>h>>w;
	vector<string> a(h);
	queue<Pi> que;
	vector<vector<int>> dist(h,vector<int>(w,INF));
	vector<int> dx={1,-1,0,0},dy={0,0,1,-1};
	rep(i,h){
		cin>>a[i];
		rep(j,w){
			if(a[i][j]=='#'){
				que.push(Pi(i,j));
				dist[i][j]=0;
			}
		}
	}
	int ans=0;
	while(!que.empty()){
		auto now=que.front();
		que.pop();
		rep(i,4){
			int nx=now.fi+dx[i],ny=now.se+dy[i];
			if(0<=nx && nx<h && 0<=ny && ny<w){
				if(dist[nx][ny]==INF){
					dist[nx][ny]=dist[now.fi][now.se]+1;
					chmax(ans,dist[nx][ny]);
					que.push(Pi(nx,ny));
				}
			}
		}
	}
	cout<<ans<<endl;
}

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

using namespace std;

const long long MOD = 1000000007LL;
long long GCD(long long a, long long b){return b == 0 ? a : GCD(b, a % b);}

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

    int n, x;
    cin >> n >> x;
    long long cur = 0;
    long long t = 0;
    for(long long i = 0; i < n; ++i){
        long long j; cin >> j;
        if(cur <= x){
            t++;
        }
        cur += j;
    }

    if(cur <= x) t++;

    cout << t;

    return 0;
}


Measured memory_bytes: 256
class Binary_Indexed_Tree:
 
    def __init__(self,n):
        self.size=n
        self.graph=[0]*(n+1)
 
    def partially_sum(self,i):
        res=0
        while i>0:
            res+=self.graph[i]
            i-=i&-i
        return res
 
    def add_element(self,i,x):
        while self.size>=i:
            self.graph[i]+=x
            i+=i&-i
    
    def ret_sum(self,l,r):
        return self.partially_sum(r)-self.partially_sum(l)
    
n,q = map(int,input().split())
a = list(map(int,input().split()))
bit = Binary_Indexed_Tree(n)

for i,x in enumerate(a):
    bit.add_element(i+1,x)
    
for i in range(q):
    t, L, R = map(int,input().split())
    if t == 0:
        bit.add_element(L+1,R)
    else:
        ans = bit.ret_sum(L,R)
        print(ans)

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

#define M 1000003
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ return key % M ;}
int h2(int key){ return 1 + (key % (M - 1)); }

int find(char str[]){
    long long key,i,h;
    key = getKey(str);
    for(i = 0;;i++){
        h = (h1(key) + i * h2(key)) % M;
        if(strcmp(H[h],str) == 0) return 1;
        else if (strlen(H[h])== 0) return 0;
    }
    return 0;
}

int insert(char str[]){
    long long key,i,h;
    key = getKey(str);
    for(i = 0;;i++){
        h = (h1(key) + i * h2(key)) % M;
        if(strcmp(H[h],str) == 0) return 1;
        else if(strlen(H[h])== 0){
            strcpy(H[h],str);
            return 0;
        }
    }
    return 0;
}

int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
    	scanf("%s %s", com, str);
    	
    	if ( com[0] == 'i' ){
    	    insert(str);
    	} else {
    	    if (find(str)){
    		printf("yes\n");
    	    } else {
    		printf("no\n");
    	    }
    	}
    }

    return 0;
}


Measured memory_bytes: 16812
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

s = ns()
k = ni()
cnt = 1
li = []
prev = '@'
for c in s:
    if c == '@':
        cnt = 1
        prev = c
        continue
    elif prev == c:
        cnt += 1
    else:
        li.append(cnt)
        cnt = 1
        prev = c
else:
    li.append(cnt)
li = li[1:]

ans_ele = 0
ans = 0
if len(set(s)) == 1:
    ans = len(s) * k // 2
elif s[0] == s[-1] and (li[0] + li[-1]) % 2 == 0:
#elif s[0] == s[-1] and li[0] == 1 and li[-1] == 1 :
    for e in li:
        if e >= 2:
            ans_ele += e // 2
    ans = ans_ele * k + k - 1
else:
    for e in li:
        if e >= 2:
            ans_ele += e // 2
    ans = ans_ele * k
print(ans)

""" same
1 ~ 1 :  + (k - 1)
2 ~ 1 : X
1 ~ 2 : X
2 ~ 2 : X
 and len(li) != 1
"""

Measured memory_bytes: 38420
n = int(input())
A = list(map(int, input().split()))
M = max(A)
m = min(A)

if M-m >= 2:
    print('No')
elif M-m == 0:
    # alone
    if M == n-1:
        print('Yes')
    elif M*2 <= n:
        print('Yes')
    else:
        print('No')
else:
    c = M
    x = 0
    for a in A:
        if a == m:
            x += 1
    if x < c and (c-x)*2 <= (n-x):
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 83780
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define DIV 1000000007

ll modPow(ll a, ll n, ll p) {
  if (n == 1) return a % p;
  if (n % 2 == 1) return (a * modPow(a, n-1, p)) % p;
  ll t = modPow(a, n/2, p);
  return (t * t) % p;
}

int main() {
  ll n, a, b;
  cin >> n >> a >> b;
  //a, b本を含む取り方
  ll all_bqs = modPow(2, n, DIV) - 1;
  ll removeA = 1, removeB = 1;
  for (int i = 0; i < a; i++) removeA = (removeA * (i+1)) % DIV;
  for (int j = 0; j < b; j++) removeB = (removeB * (j+1)) % DIV;
  removeA = modPow(removeA, DIV-2, DIV);
  removeB = modPow(removeB, DIV-2, DIV);
  for (int i = 0; i < a; i++) removeA = (removeA * (n-i)) % DIV;
  for (int j = 0; j < b; j++) removeB = (removeB * (n-j)) % DIV;

  ll bqs = (all_bqs + 2 * DIV - removeA - removeB) % DIV;
  cout << bqs << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(x,n) for(int x = 0; x < n; x++)
#define ALL(a) (a).begin(), (a).end()
using namespace std;

int main() {
  string S; cin >> S;
  int n = 0, s = 0, e = 0, w = 0;
  for(int x = 0; x <(int) S.size(); x++)
    if(S[x] == 'N')
      n = 1;
    else if(S[x] == 'S')
      s = 1;
    else if(S[x] == 'E')
      e = 1;
    else
      w = 1;
    cout << (n == s && w == e ? "Yes" : "No") << '\n';
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#define rep(i, n) for (int i=0; i<n; i++)
#define ll long long
using namespace std;

int main() {
  int a,b,c,d; cin>>a>>b>>c>>d;
  bool ok=false;
  while (1) {
    c-=b;
    if (c<=0) {
      ok=true;
      break;
    }
    a-=d;
    if (a<=0) {
      ok=false;
      break;
    }
  }
  if (ok) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


Measured memory_bytes: 3624
{-# LANGUAGE BangPatterns #-}
import Data.Char (isSpace)
import Data.Int (Int64)
import Data.List (unfoldr)
import qualified Data.Vector.Unboxed as U
import qualified Data.ByteString.Char8 as BS
import Control.Monad (replicateM)

main = do
  [n,maxW] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  items <- replicateM n $ do
    [w,v] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    return (w, fromIntegral v :: Int64)
  print $ solve maxW items U.! maxW

solve :: Int -> [(Int, Int64)] -> U.Vector Int64
solve !maxW [] = U.replicate (maxW + 1) 0
solve !maxW ((!w,!v):xs)
  = let a = solve maxW xs
    in U.generate (maxW + 1)
       $ \i -> if w <= i
               then max (a U.! i) (a U.! (i - w) + v)
               else a U.! i


Measured memory_bytes: 81916
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin >> n >> k;
    int l[n];
    for(int i=0;i<n;i++){
        cin >> l[i];
    }
    sort(l,l+n);
    reverse(l,l+n);
    int ans=0;
    for(int i=0;i<k;i++){
        ans = ans + l[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#define ll int64_t
#define REP(i, n) for (ll i=0; i<n; i++)
using namespace std;

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

    ll A, B, C;
    cin >> A >> B >> C;
    ll ans = 0;

    if (A % 2 == 0 || B % 2 == 0 || C % 2 == 0) {
        ans = 0;
    } else {
        vector<ll> e = {A, B, C};
        sort(e.begin(), e.end());
        ans = e[0] * e[1];
    }

    cout << ans << "\n";
}

Measured memory_bytes: 256
s = input()
q = int(input())

rvs = False
front = []
back = []
for i in range(q):
    op = input().split()
    if op[0] == "1":
        rvs = rvs ^ 1
    else:
        if op[1] == "1":
            if rvs:
                back.append(op[2])
            else:
                front.append(op[2])
        else:
            if rvs:
                front.append(op[2])
            else:
                back.append(op[2])

if rvs:
    for c in reversed(back):
        print(c, end='')
    for c in reversed(s):
        print(c, end='')
    for c in front:
        print(c, end='')
else:
    for c in reversed(front):
        print(c, end='')
    print(s, end='')
    for c in back:
        print(c, end='')

print()

Measured memory_bytes: 6472
#include<iostream>
#include<vector>
#include<bitset>
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>
#include<list>
#include<queue>
#include<map>
#include<numeric>
#include<set>
#include<iterator>
using namespace std;
#define rep(i,x) for(int i=0;i<x;i++)
#define re(i,x,y) for(int i=x;i<y;i++)
int INF=1e9;
const long long mod=1e9+7;
typedef long long ll;
int main(){
    int n;
    set<int>a,b;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        a.insert(x);
    }
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        b.insert(x);
    }
    vector<int>c;
    set_intersection(a.begin(),a.end(),b.begin(),b.end(),back_inserter(c));
    for(int i=0;i<c.size();i++)cout<<c[i]<<endl;
    return 0;
}


Measured memory_bytes: 21944
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MOD=1000000007;

int main(){
  int i,j,cnt=0;
  int n;
  cin>>n;
  for(i=0;i<n;i++){
    if(i*(i+1)/2<=n && n<(i+1)*(i+2)/2)break;
  }
  int m=i;
  int d=n-m*(m+1)/2;
  int a[m+1];
  for(i=1;i<=m;i++)a[i]=i;
  for(i=0;i<d;i++)a[m-i]++;
  for(i=1;i<=m;i++)cout<<a[i]<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


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

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 2e6+5;

int to[maxn][26];
int hv[maxn][26];
int NOW = 1;

void add(string x) {
    int at = 0;
    vector<int> me(26);
    for (char c : x) me[c-'a'] ++ ;
    for (int i = 0; i<SZ(x); ++i) {
        for (int j = 0; j<26; ++j) hv[at][j] += me[j] != 0;
//        if (i == SZ(x)) break;
        int c = x[i] - 'a';
        me[c]--;
        if (to[at][c] != -1) {
            at = to[at][c];
        }else{
            to[at][c] = NOW;
            at = NOW++;
        }
    }
}

ll gt(string x) {
    int at = 0;
    for (int i = 0; i<SZ(x)-1; ++i) {
        if (to[at][x[i]-'a'] == -1) return 0;
        at = to[at][x[i]-'a'];
    }
    return hv[at][x.back()-'a'];
}

signed main(){
    IOS();
    int n; cin>>n;
    memset(to, -1, sizeof to);
    vector<string> v;
    for (int i = 0; i<n; ++i) {
        string s; cin>>s;
        reverse(ALL(s));
        v.pb(s);
    }
    sort(ALL(v), [&](string a, string b){return SZ(a) > SZ(b);});
    ll re = 0;
    for (string s : v) {
        bug(s);
        re += gt(s);
        add(s);
    }
    bug(NOW);
    cout<<re<<endl;
}


Measured memory_bytes: 309696
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int INF = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<ll> v;
    ll sum = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        scanf("%d", &a);
        sum += a;
        v.emplace_back(sum);
    }
    ll ans = numeric_limits<ll>::max();
    for (int i = 0; i < n-1; ++i) {
        ans = min(ans, abs(sum-2*v[i]));
    }
    cout << ans << "\n";
    return 0;
}


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

constexpr int mod = 1000000007;
class mint {
public:
    ll x;
    constexpr mint(long long x=0) : x((x % mod + mod) % mod) {}
    constexpr mint operator-() const { 
      return mint(-x);
    }
    constexpr mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    constexpr mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    constexpr mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    constexpr mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    constexpr mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    constexpr mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    constexpr mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    constexpr mint inv() const {
        return pow(mod-2);
    }
    constexpr mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    constexpr mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
    friend ostream& operator<<(ostream& os, const mint& a){
        os << a.x;
        return os;
    }
};

int main() {

    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n){
        cin >> a[i];
    }

    ll cnt1 = 0;   //1回目
    ll cnt2 = 0;   //その他
    rep(i, n){
        rep(j, n){
            if(a[i] > a[j]){
                cnt2++;
            }
            if(i < j && a[i] > a[j]){
                cnt1++;
            }
        }
    }
    mint ans(cnt1*k);
    ans += cnt2 * ((k * (k-1) / 2) % mod);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

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

  cout << a << " " << b << " " << c << endl;
  return 0;
}

Measured memory_bytes: 3632
from operator import mul
from itertools import starmap
 
n, m, l = map(int, input().split())
a, b = ([tuple(map(int, input().split())) for _ in range(k)] for k in (n, m))
for line in ([sum(starmap(mul, zip(ai, bj))) for bj in zip(*b)] for ai in a):
    print(*line)

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

int main(int argc, const char * argv[]) {
    long long n, m, ans;
    
    cin >> n >> m;
    
    if (n>=m) {
        ans = m/2;
    }else{
        if(m>=2*n){
            ans = n + (m-2*n)/4;
        }else{
            ans = m/2;
        }
    }
    
    
    
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

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

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(int argc, char const* argv[])
{
	int n;
	cin >> n;
	if (n < 1000) {
		cout << "ABC" << endl;
	}
	else {
		cout << "ABD" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
from collections import Counter

n = int(input())
a = list(map(int, input().split()))

ac = Counter(a)
sm = 0
for v in ac.values():
    if v > 1:
        sm += v * (v - 1) // 2
for v in a:
    print(sm - ac[v] * (ac[v] - 1) // 2 + (ac[v] - 1) * (ac[v] - 2) // 2)


Measured memory_bytes: 109856