akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); 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 FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x << ": " << x << "\n"
#define DEBUG2(x, y) cerr << #x << ": " << x << " " << #y << ": " << y << "\n"
#define DEBUG3(x, y, z) cerr << #x << ": " << x << " " << #y << ": " << y << " " << #z << ": " << z << "\n"
#define PRINTALL(V)    \
  for (auto v : (V)) { \
    cerr << v << " ";  \
  }                    \
  cerr << "\n";
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
#define pint pair<int, int>
#define ld long double
using namespace std;
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;
}
template <class T> using vec = std::vector<T>;
template <class T> void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567, INF2 = INF * INF;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int N, X;
  cin >> N >> X;
  int ans = N;
  int a = max(X, N - X);
  int b = min(X, N - X);
  while (1) {
    if (a % b == 0) {
      ans += b * (2 * (a / b) - 1);
      print(ans);
      return 0;
    } else {
      ans += b * 2 * (a / b);
      int tmp = a % b;
      a = b;
      b = tmp;
    }
  }
}

Measured memory_bytes: 256
N, M, L = [int(i) for i in input().split()]

A = []
for n in range(N):
    A.append([int(a) for a in input().split()])
    
B = []
for m in range(M):
    B.append([int(b) for b in input().split()])
    
C = [[0]*L for _ in range(N)]
for n in range(N):
    for l in range(L):
        v = 0
        for m in range(M):
            v += A[n][m] * B[m][l]
        C[n][l] = v
        
for n in range(N):
    print(*C[n])


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

unsigned long long getEdgeResult(unsigned long long N, unsigned long long A, unsigned long long B);

using namespace std;

int main() {
  unsigned long long N, A, B;
  cin >> N >> A >> B;

  unsigned long long result;

  unsigned long long diff = B - A;
  if (diff % 2 == 0) {
    result = min(diff / 2, getEdgeResult(N, A, B));
  } else {
    result = getEdgeResult(N, A, B);
  }

  cout << result << endl;

  return 0;
}

unsigned long long getEdgeResult(unsigned long long N, unsigned long long A, unsigned long long B) {
  // 折り返すまでの時間
  unsigned long long edgeTo1A = A - 1;
  unsigned long long edgeToNB = N - B;

  unsigned long long diffTo1 = (B - edgeTo1A) - 1;
  unsigned long long diffToN = N - (A + edgeToNB);
  return min(min(B - 1, ((diffTo1 % 2 == 0) ? ((diffTo1 / 2) + edgeTo1A) : (diffTo1 / 2 + 1 + edgeTo1A))),
             min(N - A, ((diffToN % 2 == 0) ? (diffToN / 2 + edgeToNB) : (diffToN / 2 + 1 + edgeToNB))));
}




Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("faild to read char") as char)
        .take_while(|c| !c.is_whitespace())
        .collect();
    token
        .parse()
        .ok()
        .expect("faild to parse token")
}

fn main() {
    let n: usize = read();
    let k: usize = read();

    let a: Vec<usize> = (0..n).map(|_| read::<usize>() - 1).collect();

    let mut now = 0;
    let mut whole_num = 0;
    let mut visited: Vec<bool> = (0..n).map(|_| false).collect();

    loop {
        visited[now] = true;
        now = a[now];
        whole_num += 1;

        if visited[now] {
            break;
        }
    }
    let loop_start = now;
    let mut loop_num = 0;

    loop {
        now = a[now];
        loop_num += 1;

        if now == loop_start {
            break;
        }
    }
    let start_num = whole_num - loop_num;

    if k <= start_num {
        now = 0;
        for _ in 0..k {
            now = a[now];
        }
        println!("{}", now + 1);
        return;
    }

    let last_loop = (k - start_num) % loop_num;

    for _ in 0..last_loop {
        now = a[now];
    }
    println!("{}", now + 1);
}


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

int C[25],V[25],N;
int sum=0;

int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++) scanf("%d",&V[i]);
	for(int i=0;i<N;i++) scanf("%d",&C[i]);
	for(int i=0;i<N;i++)
		if(V[i]>C[i]) sum+=V[i]-C[i];
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

N = int(input())
A = [None] * N
for i in range(N):
    A[i] = int(input())

sorted_a = sorted(A)
max_a, max2_a = sorted_a[-1], sorted_a[-2]

for i in range(N):
    if A[i] == max_a:
        print(max2_a)
    else:
        print(max_a)


Measured memory_bytes: 14092
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;

typedef long long LL;
const int maxn=int(1e5)+100;

int n, sum;
int num[maxn*3];
int a[5][maxn];
LL tree[3][maxn*3];
LL cnt[5][maxn*3];
LL ans;
map<int, int> ind;

void read()
{
	scanf("%d", &n);
	for (int i=1; i<=3; ++i)
		for (int j=1; j<=n; ++j)
		{
			scanf("%d", &a[i][j]);
			num[(i-1)*n+j]=a[i][j];
		}
}
void init()
{
	sort(num+1, num+1+3*n);
	sum=1;
	for (int i=2; i<=n*3; ++i)
		if (num[i]!=num[sum]) num[++sum]=num[i];
	for (int i=1; i<=sum; ++i)
		ind[num[i]]=i;
}
void insert(int nid, int cur, LL value)
{
	for (; cur<=sum; cur+=(-cur)&cur) tree[nid][cur]+=value;
}
LL ask(int nid, int cur)
{
	if (cur==0) return 0;
	LL s=0;
	for (; cur; cur-=(-cur)&cur) s+=tree[nid][cur];
	return s;
}
void solve()
{
	ans=0;
	for (int i=1; i<=n; ++i)
		++cnt[1][ind[a[1][i]]];
	for (int i=1; i<=sum; ++i)
		cnt[1][i]+=cnt[1][i-1];
	for (int i=1; i<=n; ++i)
		cnt[2][ind[a[2][i]]]+=cnt[1][ind[a[2][i]]-1];
	for (int i=1; i<=sum; ++i)
		cnt[2][i]+=cnt[2][i-1];
	for (int i=1; i<=n; ++i)
		ans+=cnt[2][ind[a[3][i]]-1];

	printf("%lld\n", ans);
}
int main()
{
	read();
	init();
	solve();
	return 0;
}


Measured memory_bytes: 23680
#include <bits/stdc++.h>
//一括include
using namespace std;
int main()
{
    int count = 0;
    string s;
    cin >> s;
    for (int i = 0; i < s.size();i++){
        if(s[i]=='2'){
        count++;
    }
    }
    cout << count << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  ll ans = 0;
  rep(i, n){
    if(i == 0) ans = k;
    else ans *= k - 1;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define LOOP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define int long long

using namespace std;
const int MOD=1000000007;
const int INF=9000000009;
const double eps=1e-10;

signed main(){
  int n;
  cin>>n;
  vector<int> t(n+1);
  vector<pair<int,int>> p(n+1);

  LOOP(i,1,n+1){
    int x,y;
    cin>>t[i]>>x>>y;
    p[i]=MP(x,y);
  }
  REP(i,n){
    int dif=t[i+1]-t[i];
    int nx=abs(p[i+1].F-p[i].F);
    int ny=abs(p[i+1].S-p[i].S);
    int sum=nx+ny;
    if(sum<=dif&&dif%2==sum%2)continue;
    else {
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;

  return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(25) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 1000000007
#define MAX 5100000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int main(){
  lli A,B,C,D,E,F,N,M,K,L,R,X,Y,Z,H,W,sum=0,num=0,flag=0;string S,T;
  cin >>N >> S >> T;
  rep(i,0,N){NeOut(S[i]);NeOut(T[i]);}
  Out("");
}

Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)){
            while(sc.hasNext()) {
                int m = sc.nextInt();
                int nmin = sc.nextInt();
                int nmax = sc.nextInt();
                if(m+nmax+nmin == 0)break;
                
                int[] p = new int[m+1];
                for(int i=1;i<=m;i++) {
                	 p[i] = sc.nextInt();
                }
                
                
                int gap = 0;
                int n = 0;
                for(int i=nmin;i<=nmax;i++) {
                	if(gap<=p[i]-p[i+1] && n<i) {
                		gap = p[i]-p[i+1];
                		n = i;
                	}
                
                }
                
                System.out.println(n);
            }
        }
    }
}



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

int main(){
    int n, i, q ,a;
    scanf("%d", &n);
    vector<int> vec;
    for(i = 0; i < n; i++){
      scanf("%d", &q);
      
      switch(q){
        case 0:
          scanf("%d", &a);
          vec.push_back(a);
          break;
        case 1:
          scanf("%d", &a);
          printf("%d\n", vec.at(a));
          break;
        case 2:
          vec.pop_back();
          break;
      }
    }
}


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

typedef long long ll;
int main(){
    ll N,K;
    cin>>N>>K;
    vector<ll> H(N);
    for(int i=0;i<N;i++)cin>>H.at(i);
    sort(H.begin(),H.end());
    if(K>=N)cout<<0<<endl;
    else{
        ll ans=0;
        for(int i=0;i<N-K;i++)ans+=H.at(i);
        cout<<ans;
    }
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  int N, K, X, Y;
  cin >> N >> K >> X >> Y;

  if (N <= K){
    cout << X * N << endl;
  }else{
    cout << X * K + Y * (N - K) << endl;
  }
}


Measured memory_bytes: 3576
ss = input()
ans = 1
fir_kuro = 0
fir_siro = 0
counter = 0
for s in ss:
    if counter%2 == 0:
        fir_kuro += 0 if s == '1' else 1
        fir_siro += 0 if s == '0' else 1
    else:
        fir_kuro += 0 if s == '0' else 1
        fir_siro += 0 if s == '1' else 1
    counter += 1
print(min(fir_kuro, fir_siro))


Measured memory_bytes: 3188
import java.math.*;
import java.util.*;
import java.util.function.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long H = sc.nextLong();
    sc.close();

    long cnt = 0;
    long h = H;
    while (h != 1) {
      h /= 2;
      cnt++;
    }
    long ans = 1;
    for (int i = 1; i <= cnt; i++) {
      ans += (long) Math.pow(2, i);
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
using namespace std;

using ll = long long;
using boost::irange;

int main(void){
    
    int M, D;
    cin >> M >> D;

    if (D < 22 || M < 4){
        cout << "0" << endl;
        return 0;
    }

    
    int cnt = 0;
    for(const auto m : irange(2,M+1)){
        for(const auto d : irange(22, D + 1)){
            int d_1 = d % 10;
            int d_10 = d / 10;

            if (d_1 < 2 || d_10 < 2){
                continue;
            }

            if (m == d_1 * d_10){
                cnt++;
            }
        }
    }

    cout << cnt << endl;

    return 0;
}

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

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = Integer.parseInt(scanner.next());
        int x = Integer.parseInt(scanner.next());
        int[] children = new int[N];
        for (int i = 0; i < N; i++) {
            children[i] = Integer.parseInt(scanner.next());
        }
        scanner.nextLine();

        Arrays.sort(children);

        int happyChildren = 0;
        for (int i = 0; i < N; i++) {
            int num = children[i];
            if (i == N - 1 && num == x) {
                happyChildren++;
            } else if (i != N - 1 && x >= num) {
                happyChildren++;
                x -= num;
            }
        }

        System.out.println(happyChildren);
    }
}


Measured memory_bytes: 21716
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#define PI 3.14159265359
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pai;
typedef pair<ll, ll> pal;
const int MOD = 1e9+7;
const ll LLINF = 1e18;


int main(){
	ll k;
	cin >> k;
	int max_n = 50;
	if (k == 0){
		cout << 2 << endl << "0 0" << endl;
	}else if (k == 1){
		cout << 2 << endl << "0 2" << endl;
	}else if (k <= max_n){
		cout << k << endl;
		for (int i = 0; i < k; i++){
			cout << i+1 << " ";
		}
		cout << endl;
	}else{
		ll hoge = k/max_n;
		cout << max_n << endl;
		for (int i = 0; i < k%max_n; i++){
			cout << i+hoge+max_n-k%max_n+1 << " ";
		}
		for (int i = k%max_n; i < max_n; i++){
			cout << i+hoge-k%max_n << " ";
		}
		cout << endl;
	}	
	return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
const int MOD=(int)1e9+7;
using namespace std;
int main(){
    string s;
    cin >>s;
    int ans=0;
    REP(i,4){
        if(s[i]=='+') ans++;
        else ans--;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
const int ddx[4] = {1,1,-1, -1};
const int ddy[4] = {1,-1,-1,1};
//////////////////////////////////

int main() {
    int n, k; cin >> n >> k;
    int cnt = 0;
    for(int i=0; i<n; i++) {
        int h; cin >> h;
        if(h >= k) cnt++;
    }
    cout << cnt << endl;

    return 0;
}

// EOF


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

int n;
int A[50];

int solve(int i,int m) {
  if (m==0) {
    return 1;
  }
  if (i>=n) {
    return 0;
  }
  int res=solve(i+1,m) || solve(i+1,m-A[i]);
  return res;
}
int main() {
  cin>>n;
  for (int i=0; i<n; i++) {
    cin>>A[i];
  }
  int q, M;
  cin>>q;
  for (int i=0; i<q; i++) {
    cin>>M;
    cout<<(solve(0,M)?"yes":"no")<<endl;
  }
  return 0;
}



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

#define long long long int
using namespace std;


#ifdef JUDGE
std::ifstream cin("input.txt");
std::ofstream cout("output.txt");
#else
using std::cin;
using std::cout;
#endif

using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.precision(6);

    string s, t;
    cin >> s >> t;
    t.pop_back();
    cout << (s == t ? "Yes" : "No");
    return 0;


}


Measured memory_bytes: 3592
import numpy as np

N = int(input())
rests = []
evals = []

for n in range(N):
    i = input().split()
    rests.append(i[0])
    evals.append(int(i[1]))

rests = np.array(rests)
evals = np.array(evals)
nums = np.array([i + 1 for i in range(len(rests))])

order_by_name = np.argsort(rests)
rests = rests[order_by_name]
evals = evals[order_by_name]
nums = nums[order_by_name]
names = np.unique(rests)

for name in names:
    loc = np.where(rests == name)[0]
    if len(loc) == 1:
        pass
    else:
        start = loc[0]
        end = loc[-1] + 1
        order_by_eval = np.argsort(- evals[start:end])
        evals[start:end] = evals[start:end][order_by_eval]
        nums[start:end] = nums[start:end][order_by_eval]

for num in nums:
    print(num)

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

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef array<int, 3> tri;
typedef long double ld;

template <class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}

#define int long long


int exp(int a, int n) {
        int res = 1;
        while (n--) res *= a;
        return a;
}


void _main() {
        int x; cin >> x;
        int ans = 1;

        for (int a = 2, n; a <= x; a++) {
                int b = a * a;
                while (b <= x) {
                        if (abs(ans - x) > abs(b - x)) ans = b;
                        b *= a;
                }
        }

        cout << ans;
}



signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}


Measured memory_bytes: 3640
MOD = 10 ** 9 + 7
ONE = '1'.freeze

def nCk(n, k)
  res = 1
  i = k
  j = 1
  while i > 0
    res = res * (n - i + 1)
    res %= MOD
    j *= i
    j %= MOD
    i -= 1
  end
  res *= inv(j)
  res %= MOD
  res
end

def repeated_nCk(n, k)
  # 仕切りのイメージで
  nCk(n + k - 1, n - 1) % MOD
end

def inv(x)
  res = 1
  beki = x
  (MOD - 2).to_s(2).reverse.chars do |digest|
    res = (beki * res) % MOD if digest == ONE
    beki = (beki * beki) % MOD
  end
  res
end

n, blue = gets.split.map(&:to_i)
red = n - blue
ans = []
(1..blue).each do |count|
  ans << nCk(red + 1, count) * repeated_nCk(count, blue - count)
end
ans.each { |a| puts a % MOD }


Measured memory_bytes: 14340
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    X, Y, Z = MI()
    X, Y = Y, X
    X, Z = Z, X

    print(X, Y, Z)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38640
n = int(input())
d = list(map(int,input().split()))

d.sort()

if n % 2 == 0:
    if d[n // 2 - 1] == d[n // 2]:
        print(0)
    else:
        print(d[n // 2] - d[n // 2 - 1])
else:
    print(0)

Measured memory_bytes: 52776
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class disjoint_set{
public:	
	vector<int> p,rank;
	disjoint_set(){};
	disjoint_set(int size){
	p.resize(size,0);rank.resize(size,0);
	for(int i=0;i<size;i++) makeset(i);
	}
	void makeset(int i){
		p[i]=i;rank[i]=0;
	}
	int findroot(int i){
		while(p[i]!=i){
			i=p[i];
		}
		return i;
	}
	int same(int a,int b){
		if(findroot(a)==findroot(b)) cout<<"1"<<endl;
		else cout<<"0"<<endl;
	}
	void unite(int a,int b){
		int a_root=findroot(a);int b_root=findroot(b);
		if(rank[a_root]>rank[b_root]) p[b_root]=a_root;
		else if(rank[a_root]<rank[b_root]) p[a_root]=b_root;
		else {
			p[a_root]=b_root,rank[b_root]+=1;
		}
	}
	
};
int main(){
	int q,n,order,a,b;
	cin>>n>>q;
	disjoint_set s=disjoint_set(n);
	for(int i=0;i<q;i++){
		cin>>order>>a>>b;
		if(order==0) s.unite(a,b);
		else s.same(a,b);
	}
}


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

int main(){
    int n;
    cin >> n;
    vector<int> v(n);
    rep(i,n){
        cin >> v[i];
    }
    sort(v.begin(),v.end());
    int cnt = 0;
    
    for(int i = 0;i < n-1;i++){
        if(v[i] == v[i+1]){
            cnt++;
            break;
        }
    }
    
    if(cnt != 0) cout << "NO";
    else cout << "YES";
    return 0;
}

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

const int MOD = 1e9 + 7;

// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};


const int MAX = 2e5 + 10;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

using mint = Fp<MOD>;


int main(){
    COMinit();

    ll n, k;
    cin >> n >> k;

    mint x = 0;
    REP(l, min(n-1, k)+1){
        x += (mint)(COM(n, l) * COM(n-1, l));
    }
    cout << x << endl;
} 

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

int main()
{
  int n;
  cin >> n;
  
  int a[n+1];
  for(int i = 2; i < n+1; i++){
    cin >> a[i];
  }
  
  int x[n+1] = {0};
  for(int i = 2; i < n+1; i++){
    x[a[i]]++;
  }
  
  for(int i = 1; i < n+1; i++){
    cout << x[i] << endl;
  }
}

Measured memory_bytes: 5148
import sys
input = sys.stdin.readline
 
MOD = 10**9 + 7
def main():
    S = input()
    N = len(S)-1
 
    if S[0] == '?':
        dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
        dp[int(S[0])] = 1
 
    for i in range(1,N):
        dppre = dp
        dp = [0] * 13
 
        if S[i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[(j * 10 + k) % 13 ] += dppre[j]
        else:
            for j in range(13):
                dp[(j * 10 + int(S[i])) % 13 ] += dppre[j]
 
        for j in range(13):
            dp[j] %= MOD
 
    print(dp[5])
if __name__ == '__main__':
    main()

Measured memory_bytes: 42860
N = int(input())
sx = list()
sy = list()
sec=0
for i in range(N):
    si = input().split()
    sx.append(si[0])
    sy.append(int(si[1]))
X = input()
xi = sx.index(X)+1
for i in sy[xi:]:
    sec += i
print(sec)

Measured memory_bytes: 3064
import java.util.*;
import java.io.*;
public class Main {
	static long[] w, v;
	static int n, s;
	static long[][] dp;
	static StringBuilder sb;
	public static long dp(int idx, long remw) {
		if (remw < 0) {
			return -(int) 1e9;
		}
		if (idx == n) {
			return 0;
		}
		if (dp[idx][(int) remw] != -1) {
			return dp[idx][(int) remw];
		}
		long take = v[idx] + dp(idx + 1, remw - w[idx]);
		long leave = dp(idx + 1, remw);
		return dp[idx][(int) remw] = Math.max(take, leave);
	}


	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		n = sc.nextInt();
		s = sc.nextInt();
		v = new long[n];
		w = new long[n];
		for(int i=0; i<n;i++) {
			w[i]= sc.nextInt();
			v[i]= sc.nextInt();
		}
		dp = new long[n + 1][s + 1];
		for (long[] x : dp)
			Arrays.fill(x, -1);

		pw.println(dp(0, s));
		sb = new StringBuilder();

		pw.close();
	}
	static class Scanner {
		BufferedReader br;
		StringTokenizer st;
		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
		public int[] nextIntArr(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(next());
			}
			return arr;
		}
	}
}

Measured memory_bytes: 131072
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,q=map(int,input().split())
    S,T,X=[0]*n,[0]*n,[0]*n
    D=[0]*q
    for i in range(n):
        S[i],T[i],X[i]=map(int,input().split())
    for j in range(q):
        D[j]=int(input())

    E=[]
    E+=[(s-x,1,x) for s,x in zip(S,X)]
    E+=[(t-x,2,x) for t,x in zip(T,X)]
    E+=[(d,3,i) for i,d in enumerate(D)]
    E.sort()
    cnt={x:0 for x in X}
    cnt[INF]=1

    from heapq import heappop,heappush
    Q=[INF]
    ans=[-1]*q
    for a,b,c in E:
        if(b==1):
            heappush(Q,c)
            cnt[c]+=1
        elif(b==2): # 本来はここでqからcを削除したいが、できないためb==3で処理する
            cnt[c]-=1
        else:
            while(cnt[Q[0]]==0): # 本来削除されるべき通行止めをここで消す
                heappop(Q)
            x=Q[0]
            if(x!=INF): ans[c]=x
    print(*ans,sep="\n")
resolve()


Measured memory_bytes: 123480
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include<set>
using namespace std;

int main()
{
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    s.at(k-1) = s.at(k-1)-('A'-'a');
    cout << s << endl;
}


Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
string s;
long long mod=1000000007;
int d;
int dp[2][100009][109];

int main(){
  cin >> s >> d;
  dp[0][0][0]=1;
  int n=s.size();
  for(int i=0;i<n;i++){
    for(int j=0;j<10;j++){
      for(int k=0;k<d;k++){
        dp[1][i+1][(k+j)%d]=(dp[1][i+1][(k+j)%d]+dp[1][i][k])%mod;
        if(j>s[i]-'0')continue;
        else if(j<s[i]-'0')dp[1][i+1][(k+j)%d]=(dp[1][i+1][(k+j)%d]+dp[0][i][k])%mod;
        else dp[0][i+1][(k+j)%d]=(dp[0][i+1][(k+j)%d]+dp[0][i][k])%mod;
      }
    }
  }
  long long k=(dp[0][n][0]+dp[1][n][0])%mod;
  if(k==0){k+=mod;}
  cout << k-1 << endl;
}

Measured memory_bytes: 12544
#include <iostream>
using namespace std;
 
int main() {
	int a, b, c, x, res = 0;
	cin >> a >> b >> c >> x;
 
	for (int i = 0; i <= a; ++i) {
		for (int j = 0; j <= b; ++j ) {
			for (int k = 0; k <= c; ++k) {
				if (500 * i + 100 * j +  50 * k == x) {
					++res;
				}
			}
		}
	}
 
	cout << res << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Linq;

class prog{
	public static void Main(string[] args){
    	string[] input = Console.ReadLine().Split(' ');
      	int N = int.Parse(input[0]);
      	int K = int.Parse(input[1]);
      
      	string[] numst = Console.ReadLine().Split(' ');
      	double[] numsi = new double[numst.Length];
      	for(int i = 0;i < numsi.Length;i ++){
        	numsi[i] = double.Parse(numst[i]);
          	numsi[i] = (numsi[i] + 1) /2;
          	//Console.WriteLine(numsi[i]);
        }
      	//Console.WriteLine("-----------------------------------");
      	double[] sums = new double[N - K + 1];
      	for(int i = 0;i < K;i ++){sums[0] += numsi[i];}
      	//Console.WriteLine(sums[0]);
      	for(int i = 1;i < sums.Length;i ++){
        	sums[i] = sums[i - 1] - numsi[i -1] + numsi[i + K - 1]; 
          	//Console.WriteLine(sums[i]);
        }
      
      	Console.WriteLine(sums.Max());
    }
}

Measured memory_bytes: 33500
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n,k,t,u,v,l;
        n = sc.nextInt();
        k = sc.nextInt();
        t = sc.nextInt();
        u = sc.nextInt();
        v = sc.nextInt();
        l = sc.nextInt();

        int[] d = new int[n+1];
        for (int i = 0; i < n; ++i) d[i] = sc.nextInt();
        d[n] = l;

        int pos = 0, c = 0, nk = 0;
        double tm = 0;

        while (pos < l) {
            // ??????????????????????????´???????????????
            if (pos < d[c]) {
                // ?????????????????£?????????
                if (nk > 0) {
                    nk--;
                    int x = Math.min(l, pos+t*v);
                    tm += (x-pos)/(double)v;
                    pos = x;
                }
                // ?????£??????????????£??????
                else {
                    tm += (d[c]-pos)/(double)u;
                    pos = d[c];
                }
            }
            //  ?????????????????´???????????£??????
            else {
                // ?????????????????£??????????????£??????
                if (d[c] == pos) {
                    int x = Math.min(l, pos+t*v);
                    tm += (x-pos)/(double)v;
                    pos = x;
                    ++c;
                }
                else {
                    if (nk < k) {
                        c++;
                        nk++;
                    }
                    else {
                        int x = Math.min(l, d[c++]+t*v);
                        tm += (x-pos)/(double)v;
                        pos = x;
                    }
                }
            }
        }
        System.out.println(tm);
    }
}

Measured memory_bytes: 26752
import java.util.*;

public class Main {
    private static Scanner scanner;

    public static int[] inputIntArray(int n) {
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            res[i] = scanner.nextInt();
        }

        return res;
    }

    // public static String[] <T> ToStringArray(T[] arr) {
    // String[] res = new String[arr.length];
    // for(int i = 0; i < arr.length; ++i) {
    // res[i] = String.valueOf(arr[i]);
    // }

    // return res;
    // }

    private static List<Integer> asIntergerList(int[] arr) {
        List<Integer> intList = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            intList.add(arr[i]);
        }

        return intList;
    }

    private static int[][] deepCopy(int[][] arr) {
        int[][] res = new int[arr.length][];
        for (int i = 0; i < arr.length; ++i) {
            res[i] = arr[i].clone();
        }

        return res;
    }

    private static String asString(int[][] arr) {
        String str = new String();

        for (int i = 0; i < 2; ++i) {
            str += "" + arr[i][0] + arr[i][1] + arr[i][2] + arr[i][3];
        }

        return str;
    }

    public static void main(String[] args) {
        scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        for (int i = 1; i <= n; ++i) {
            boolean flag = false;

            if (i % 3 == 0) {
                flag = true;
            } else {
                int v = i;
                while (v != 0) {
                    if (v % 10 == 3) {
                        flag = true;
                        break;
                    }

                    v /= 10;
                }
            }
            if (flag) {
                System.out.print(" " + i);
            }
        }
        System.out.println();
    }
}



Measured memory_bytes: 28916
n, k = map(int,input().split())
r,s,p = map(int,input().split())
t = input()
ans = 0
def janken(a):
    global ans
    if "r" == a:
        return p
    if "s" == a:
        return r
    if "p" == a:
        return s

for i in range(k):
    ti = t[i::k]
    odd = []
    even = []
    before = ""
    for j in range(len(ti)):
        if ti[j] == before:
            if j % 2 == 0:
                even.append(ti[j])
            else:
                odd.append(ti[j])
        else:
            if j != 0:
                ans += janken(before)*max(len(odd),len(even))
                even = []
                odd = []
            if j % 2 == 0:
                even.append(ti[j])
            else:
                odd.append(ti[j])
        if j == len(ti)-1:
            ans += janken(ti[j])*max(len(odd),len(even))
        before = ti[j]

print(ans)

Measured memory_bytes: 4212
/**
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⠀⠀⠀⠀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡖⠁⠀⠀⠀⠀⠀⠀⠈⢲⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣼⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣧⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣸⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣇⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣿⣿⡇⠀⢀⣀⣤⣤⣤⣤⣀⡀⠀⢸⣿⣿⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢻⣿⣿⣔⢿⡿⠟⠛⠛⠻⢿⡿⣢⣿⣿⡟⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣀⣤⣶⣾⣿⣿⣿⣷⣤⣀⡀⢀⣀⣤⣾⣿⣿⣿⣷⣶⣤⡀⠀⠀⠀⠀
⠀⠀⢠⣾⣿⡿⠿⠿⠿⣿⣿⣿⣿⡿⠏⠻⢿⣿⣿⣿⣿⠿⠿⠿⢿⣿⣷⡀⠀⠀
⠀⢠⡿⠋⠁⠀⠀⢸⣿⡇⠉⠻⣿⠇⠀⠀⠸⣿⡿⠋⢰⣿⡇⠀⠀⠈⠙⢿⡄⠀
⠀⡿⠁⠀⠀⠀⠀⠘⣿⣷⡀⠀⠰⣿⣶⣶⣿⡎⠀⢀⣾⣿⠇⠀⠀⠀⠀⠈⢿⠀
⠀⡇⠀⠀⠀⠀⠀⠀⠹⣿⣷⣄⠀⣿⣿⣿⣿⠀⣠⣾⣿⠏⠀⠀⠀⠀⠀⠀⢸⠀
⠀⠁⠀⠀⠀⠀⠀⠀⠀⠈⠻⢿⢇⣿⣿⣿⣿⡸⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠈⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⣿⣿⣿⣿⣧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠐⢤⣀⣀⢀⣀⣠⣴⣿⣿⠿⠋⠙⠿⣿⣿⣦⣄⣀⠀⠀⣀⡠⠂⠀⠀⠀
⠀⠀⠀⠀⠀⠈⠉⠛⠛⠛⠛⠉⠀⠀⠀⠀⠀⠈⠉⠛⠛⠛⠛⠋⠁⠀⠀
 *    author:  Daredevil666
 *    institution: IIT Patna
**/
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define nl cout<<"\n";
#define ll long long int
#define REP(i,a,n) for(i=a;i<=n;i++)
#define F(i,a,b) for(i=a;i<b;i++)
#define RF(i,b,a) for(i=b;i>=a;i--)
#define IOS  ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
const ll mod=1e9+7;
const ll MAXN=100200;
ll i,j,mask,test;
int main()
{
IOS
/*#ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
#endif // ONLINE_JUDGE*/
ll n;
cin>>n;
vector<ll> v(n);
F(i,0,n)
{
    cin>>v[i];
}
ll ans=0;
ll sum=v[0];
F(i,1,n)
{
    ans=(ans%mod+(sum%mod)*(v[i]%mod))%mod;
    sum+=v[i];
    if(ans<0)
        ans+=mod;
}
if(ans<0)
    ans+=mod;
cout<<ans;
return 0;
}


Measured memory_bytes: 4756
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	string s;
	cin>>s;
	if(s=="RRR")
		cout<<3;
	else
		if(s=="RRS"||s=="SRR")
			cout<<2;
		else
			if(s=="SSS")
				cout<<0;
			else
				cout<<1;
	return 0;
}

Measured memory_bytes: 3620
N, T = map(int, input().split())
tt = list(map(int, input().split()))
ans = 0

for i in range(N - 1):
  nn = tt[i + 1] - tt[i]
  if nn > T:
    ans += T
  else:
    ans += nn
    
ans += T
print(ans)
    


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

int N;
int A[20];
int x[20][20];
int y[20][20];

int counter(int x) {
    if(x == 0) return 0;
    return counter(x >> 1) + (x & 1);
}

void solve() {
    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> A[i];
        for(int j = 1; j <= A[i]; j++) {
            cin >> x[i][j] >> y[i][j];
        }
    }
    int ans = 0;
    for(int bits = 1; bits < (1 << N); bits++) {
        bool ok = true;
        for(int i = 1; i <= N; i++) {
            if(!(bits & (1 << (i-1)))) continue;
            for(int j = 1; j <= A[i]; j++) {
                if(((bits >> (x[i][j]-1)) & 1) ^ y[i][j]) ok = false;
            }
        }
        if(ok) ans = max(ans, counter(bits));
    }
    cout << ans << endl;
    return;
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#define MAX 1000000
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)
#define Mod 1000000007
#define pii pair<ll,ll>
#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
using namespace __gnu_pbds; 
using namespace std;

typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> new_data_set; 

ll num(ll i,ll j){
	return 500*i+j;
}
class Disjoint_Sets{
public:
	ll* parent;
	ll* size;
	Disjoint_Sets(ll n){
		parent = new ll[n];
		size = new ll[n];
		For(i,0,n) parent[i]=i;
		For(i,0,n) size[i]=1;
	}
	void merge(ll a,ll b){
		ll parent_a = find(a);
		ll parent_b = find(b);
		if(parent_a==parent_b) return;
		if(size[parent_a]<size[parent_b]){
			parent[parent_a] = parent_b;
			size[parent_b] += size[parent_a];
			size[parent_a] = 0;
		}else{
			parent[parent_b] = parent_a;
			size[parent_a] += size[parent_b];
			size[parent_b] = 0;
		}
	}
	ll find(ll a){
		if(parent[a]==a){
			return a;
		}
		parent[a]=find(parent[a]);
		return parent[a];
	}
}; 
int main(){
	ios_base::sync_with_stdio(false);
	ll n,m;cin>>n>>m;
	ll a[n][m];
	For(i,0,n){
		string s;cin>>s;
		For(j,0,m) a[i][j]=(s[j]=='#');
	}
	Disjoint_Sets d(MAX);
	pii dir[4];
	dir[0]=mp(0,1);
	dir[1]=mp(1,0);
	dir[2]=mp(-1,0);
	dir[3]=mp(0,-1);
	For(i,0,n){
		For(j,0,m){
			ll c = a[i][j];
			For(k,0,4){
				pii temp(i+dir[k].fi,j+dir[k].se);
				if(temp.fi>=n || temp.se>=m || temp.fi<0 || temp.se<0) continue;
				ll x = a[i+dir[k].fi][j+dir[k].se];
				if(x!=c) d.merge(num(i,j),num(i+dir[k].fi,j+dir[k].se));
			}
		}
	}

	map<ll,pii> M;
	For(i,0,n){
		For(j,0,m){
			ll c = num(i,j);
			ll x = d.find(c);
			if(M.find(x)==M.end()) {
				if(a[i][j])
					M.insert(mp(x,mp(1,0)));
				else M.insert(mp(x,mp(0,1)));
			}
			else{ 
				if(a[i][j])M[x].fi++;
				else M[x].se++;
			}	
		}
	}
	ll ans=0;
	// cout<<M.size()<<endl;
	for(pair<ll,pii> x:M){
		ans += (x.se.fi*x.se.se);
		// cout<<x.se.fi<<" "<<x.se.se<<endl;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 25728
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int nagai,t;
  nagai = 0;
  t = 0;
  string s;
  cin >> s;
  
  for(int i = 0;i < s.size();i++){
    if(s.at(i) == 'A' || s.at(i) == 'T' || s.at(i) == 'C' || s.at(i) == 'G'){
    t++;
    }
      else{
        if(nagai <= t){
      nagai = t;
        }
        t = 0;
      }
    }
    if(t > nagai){
    nagai = t;
    } 
    cout << nagai << endl;
  }

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

lint a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main() {
    lint k;
    cin >> k;
    cout << a[k-1] << endl;
}

Measured memory_bytes: 256
//#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;
#define S 1000001
#define M 1000000007
#define nl cout<<"\n";
#define er  cout<<"\n***********\n";
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define test lli t;  cin>>t; while(t--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define Y cout<<"YES\n";
#define N cout<<"NO\n";
#define print(x)                 cout<<#x<<": "<<x<<endl;
#define print2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl;
#define print3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define print4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define print5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl;
#define print6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl;

int main()
{
    fast
    // test
    {
        lli n;
        cin>>n;
        map<string,lli> mpp;
        string str;
        for(lli i=0;i<n;i++)
        {
            cin>>str;
            mpp[str]++;
        }
        
        cout<<"AC x "<<mpp["AC"]<<"\n";
        cout<<"WA x "<<mpp["WA"]<<"\n";
        cout<<"TLE x "<<mpp["TLE"]<<"\n";
        cout<<"RE x "<<mpp["RE"]<<"\n";

    }
}
//a+b=a?b+2?(a&b)
//__builtin_popcount(number)
//cout<<fixed<<setprecision(8)<<output<<"\n";




Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < int(n); ++i)
#define REPE(i, a, b) for (int i = (a); i <= int(b); ++i)
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define EB emplace_back
using LL = long long;
using PII = pair<int, int>;
#define F first
#define S second

string s, t;

int p(int x) {
  int i = 0;
  for (char &c : s) {
    if (c != 'x') {
      if (x-- == 0) {
        return i;
      }
    }
    i++;
  }
}

int main() {
  cin >> s;
  for (auto &x : s) if (x != 'x') t += x;
  if (t != string(t.rbegin(), t.rend())) {
    puts("-1");
    return 0;
  }
  if (t.empty()) {
    puts("0");
    return 0;
  }
  int a, b;
  if (SZ(t) % 2 == 0) {
    a = p(SZ(t) / 2 - 1);
    b = p(SZ(t) / 2);
  } else {
    a = b = p(SZ(t) / 2);
  }
  int ans = 0;
  while (a >= 0 || b < SZ(s)) {
    if (a < 0) {
      b++;
      ans++;
    } else if (b >= SZ(s)) {
      a--;
      ans++;
    } else {
      if (s[a] == s[b]) {
        a--, b++;
      } else if (s[a] == 'x') {
        a--;
        ans++;
      } else {
        b++;
        ans++;
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}



Measured memory_bytes: 512
#include <stdio.h>

int selection_sort(int n, int *a)
{
	int i, j, minj, x;
int ans = 0;

	for (i = 0; i < n; i++) {
		minj = i;
		for (j = i; j < n; j++) {
			if (a[j] < a[minj]) minj = j;
		}
		if (i != minj) {
			x = a[i], a[i] = a[minj], a[minj] = x;
ans++;
		}
	}
return ans;
}
int in()
{
	int n = 0, c = getchar_unlocked();
	do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}
int a[102];
int main()
{
	int N, i, k;
	N = in();
	for (i = 0; i < N; i++) a[i] = in();
	k = selection_sort(N, a);
	printf("%d", a[0]);
	for (i = 1; i < N; i++) printf(" %d", a[i]);
	putchar('\n');
	printf("%d\n", k);
	return 0;
}




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

map<int,int> m;
vector<int> v;

int main(){
    int n,ans;
    cin>>n;
    for(register int i=1;i<=n;++i){
        int x;
        cin>>x;
        if(m[x]==0) v.push_back(x);
        ++m[x];
    }
    for(register int i=0;i<v.size();++i) if(m[v[i]]>=v[i]) ans+=m[v[i]]-v[i]; else ans+=m[v[i]];
    cout<<ans<<endl;

}

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

Measured memory_bytes: 640
import math
def num():
    return map(int , input().split())
def nu():
    return int(input())
def li():
    return input().split()
def sli():
    return list(map(str, input().split()))
def lli ():
    return list (map(int, input ().split ()))
def fli():
    return [float(x) for x in input().split()]

a, b = num()
print(a * b)

Measured memory_bytes: 9192
/*************************************************************************
  >         File: A.cc
  >       Author: Yuan Lei
  >         Mail: yuanlei@indeed.com
  > Created Time: Sun 22 Oct 2017 08:59:51 PM JST
*************************************************************************/
#include <vector>
#include <cstdio>
#include <bitset>
#include <utility>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <set>
#include <map>
#include <deque>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <string>
#include <iostream>
#include <algorithm>
#include <functional>

int main() {
  std::ios::sync_with_stdio(0);
  std::string s;
  std::cin >> s;
  s.find("AC") == std::string::npos ? puts("No") : puts("Yes");
  return 0;
}


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

const int MAX_N = 100;
const int MAX_W = 100000;

int N, W;
long w[MAX_N+1];
long v[MAX_N+1];
long dp[MAX_N+1][MAX_W+1];

long rec(int i, int j) {
    // メモを利用
    if (dp[i][j] >= 0) {   
        return dp[i][j];
    }
    long res;
    if (i == N) {
        res = 0;
    } else if (j < w[i]) {
        res = rec(i+1, j);
    } else {
        res = max(rec(i+1, j - w[i]) + v[i], rec(i+1, j));
    }
    return dp[i][j] = res;
}

void solve() {
    memset(dp, -1, sizeof(dp));
    cout << rec(0, W) << endl;
}

int main() {
    cin >> N >> W;
    for(int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }
    solve();
}


Measured memory_bytes: 79104
N = int(input())
A = list(map(int,input().split()))

dp = [[0]*(200) for i in range(N)]#所持金jの時のi日目の最大株
kabu0 = 1000#株をひとつも持ってない状態での所持金最大

dp[0][1000%A[0]] = 1000//A[0]

for i in range(1,N):
    for j in range(0,200,1):
        dp[i][j]=dp[i-1][j]
    dp[i][kabu0%A[i]]=kabu0//A[i]
    for j in range(0,200,1):
        kabu0 = max(kabu0,A[i]*dp[i-1][j]+j)
    

print(kabu0)


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

const int maxn=100005;
const int mdn=1000000007;

inline long long qpow(long long bse,long long ex){
    long long ans=1;
    while(ex){if(ex&1)ans=(ans*bse)%mdn;ex>>=1;bse=(bse*bse)%mdn;}
    return ans;
}

int n;
int a[maxn];
long long fac[maxn],ifac[maxn];
long long pfx[maxn];

int main(){
    fac[0]=1;for(int i=1;i<maxn;i++)fac[i]=(fac[i-1]*i)%mdn;
    ifac[maxn-1]=qpow(fac[maxn-1],mdn-2);for(int i=maxn-1;i>=1;i--)ifac[i-1]=(ifac[i]*i)%mdn;
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){pfx[i]=pfx[i-1]+a[i];pfx[i]%=mdn;}
    long long sum=pfx[n];
    for(int i=2;i<=n;i++){
        long long cinv=(fac[i-1]*ifac[i])%mdn;
        long long cnt=(pfx[n-i+1]+pfx[n]-pfx[i-1]+mdn*3ll)%mdn;
        //cerr<<i<<':'<<cnt<<endl;
        sum+=(cinv*cnt)%mdn;
        sum%=mdn;
    }
    cout<<(sum*fac[n])%mdn;
    return 0;
}

Measured memory_bytes: 2944