akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
using namespace std;
 
#define ff                  first
#define ss                  second
#define endl                "\n"
#define loop(i,s,e)         for(int i=s;i<e;i++)
#define int                 long long
#define vi                  vector<int> 
#define S(v)                sort(v.begin(),v.end())
#define RS(v)               sort(v.rbegin(),v.rend())
#define R(v)                reverse(v.begin(),v.end())
#define mxpq(T)             priority_queue <T>
#define mnpq(T)             priority_queue<T,vector<T>,greater<T>>
#define prv(v)              for(auto &x : v)cout << x << " ";
#define piirv(v)            for(auto &x : v)cout << x.ff << " " << x.ss << endl;
#define prvv(v)             for(auto &x : v)for(auto &y : x.ss)cout << y << " ";
#define mp                  make_pair
#define pii                 pair<int,int>
#define mset(a,f)           memset(a , f , sizeof(a))
#define pb                  push_back
#define inf                 INT_MAX
#define INF                 LLONG_MAX
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
 
const int N = 2e6 + 6;
const int M = 998244353;
int A[N];
int dp[N];
int n , m;

inline int mul(int a, int b) { return (a * b) % M; };
inline int add(int a, int b)
{
      int res = a + b;
      if ( res < 0 ) res += M;
      if ( res >= M) res -= M;
      return res;
}

void solve()
{
	int n , k;
	cin >> n >> k;
	vector<pii> vec(k);
	loop(i,0,k)cin >> vec[i].ff >> vec[i].ss;
	S(vec);

	dp[0] = 0; dp[1] = 1;

	loop(i,2,n+1)
	{
		loop(j,0,k)
		{
			int l = max( i - vec[j].ss , 1ll);
			int r = max( i - vec[j].ff , 0ll);

			dp[i] = add(dp[i] , add(dp[r] , -dp[l-1]));
		}
		dp[i] = add(dp[i] , dp[i-1]);
	}

	cout << (dp[n] - dp[n-1] + M)%M;
}			
 
int32_t main()
{
 
cout<<fixed<<setprecision(16);
 
ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
 	
 
 	int t = 1;
 	// cin >> t;
 	while(t--)solve();
  
}

Measured memory_bytes: 5168
use std::cmp::*;
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();

    // n // m == n % m
    // (n - n % m ) / m == n % m
    // n - n % m == m * (n % m)
    // n == (m + 1) * (n % m)

    let mut i = 1;
    let mut ans = 0;
    while i * i <= n {
        if n % i == 0 {
            if i > 1 && i * (n % (i - 1)) == n {
                ans += i - 1;
            }
            if n / i != i {
                if n / i > 1 && (n / i) * (n % (n / i - 1)) == n {
                    ans += n / i - 1;
                }
            }
        }
        i += 1;
    }
    println!("{}", ans);
}


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

#define LL long long
typedef pair<int, int> pii;

template< typename T > inline void read(T &x)
{
    static char _c;
    static bool _f;

    x = 0;
    _f = 0;
    _c = getchar();

    while(_c < '0' || '9' < _c) {if(_c == '-') _f = true; _c = getchar();}
    while('0' <= _c && _c <= '9') {x = (x << 1) + (x << 3) + (_c & 15); _c = getchar();}
    if(_f) x = -x;
}

template < typename T > inline void Min(T &x, T y) {if(y < x) x = y;}
template < typename T > inline void Max(T &x, T y) {if(x < y) x = y;}


#define lowbit(x) ((x) & -(x))
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
#define ls id<<1
#define rs id<<1|1
#define MID(l,r) ((l)+(((r)-(l))>>1))
#define fi first
#define se second
#define mk make_pair
#define pb push_back

const int INF = 0x3f3f3f3f;
const int MOD = (int) 998244353;
const int maxn = (int) 2e5 + 20;
const int maxm = (int) 1000000 + 20;
const double pi = (double) acos(-1.0);
const double eps = (double) 1e-8;

inline int sig(double x) {return x < -eps ? -1 : eps < x;}
LL fp(LL a, LL n, LL m = MOD) {LL res = 1; for(; n; n >>= 1, a = a * a % m) if(n & 1) res = res * a % m; return res;}

int n;
string s[2];

void work()
{
    cin >>n;
    cin >>s[0] >>s[1];

    for(int i = 0; i < n * 2; i++) cout <<s[i & 1][i >> 1];
}

int main()
{
#ifdef yukihana0416
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // yukihana0416
//    get_prime();
    int tc = 1;
//    read(tc);
    for(int ca = 1; ca <= tc; ca++)
    {
//        printf("Case #%d: ", ca);
        work();
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX 100000

int Partition(int [], int, int);
void Quicksort(int [], int, int);

int q;

int main(void){

  int A[MAX+1];

  int i, p, n;

  scanf("%d",&n);

  for(i=1;i<=n;i++)
    scanf("%d",&A[i]);

  p = 1;

  Quicksort(A, p, n);


  for(i=1;i< n;i++){
    if(i==q)
    printf("[%d] ",A[i]);

    else
      printf("%d ",A[i]);
  }

  printf("%d\n",A[i]);

  return 0;
}


int Partition(int A[], int p, int r){

  int i, j, x;
  int tmp;

  x = A[r];
  i = p - 1;

  for(j = p;j<r;j++){
    if(A[j] <= x){
      i = i + 1;
      tmp = A[j];
      A[j] = A[i];
      A[i] = tmp;
    }
  }
  
  tmp = A[i+1];
  A[i+1] = A[r];
  A[r] = tmp;

  return i+1;
}


void Quicksort(int A[], int p, int r){


  //if(p < r){
    q = Partition(A, p, r);
    //Quicksort(A, p, q-1);
    //Quicksort(A, q+1, r);
    //}
}

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

ll ans = 1000000000;

void search1(ll tate, ll yoko) {
  for (ll i = 1; i < yoko; i++) {
    vector<ll> S(3);
    S[0] = tate*i;
    if (tate % 2 == 0) {
      S[1] = tate*(yoko-i)/2;
      S[2] = tate*(yoko-i)/2;
    }
    else {
      S[1] = tate/2*(yoko-i);
      S[2] = (tate+1)/2*(yoko-i);
    }
    sort(S.begin(), S.end());
    if (S[2]-S[0] < ans) ans = S[2]-S[0];
  }
}

void search2(ll tate, ll yoko) {
  vector<ll> S(3);
  S[0] = yoko*(tate/3);
  S[1] = yoko*((tate+1)/3);
  S[2] = yoko*((tate+2)/3);
  if (S[2]-S[0] < ans) ans = S[2]-S[0];
}

int main() {
  ll H, W;
  cin >> H >> W;
  if (H % 3 == 0 || W % 3 == 0) ans = 0;
  else {
    search1(H, W);
    search1(W, H);
    search2(H, W);
    search2(W, H);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
const int inf = 1000000001;
const ll INF = 1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };


int main() {
	double x, a, b;
	cin >> x >> a >> b;
	if (abs(x - a) > abs(x - b)) {
		cout << "B" << endl;
	}
	else {
		cout << "A" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Combination:
    def __init__(self, n, mod):

        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, n + 1):
            g1.append((g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod//i)) % mod)
            g2.append((g2[-1] * inverse[-1]) % mod)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD


M = 1000003
m = Mod(M)
C = Combination(M-1, M)


def slv(x, d, n):
    if d == 0:
        return m.pow(x, n)

    xd = m.div(x, d)
    if n > M - xd:
        return 0

    return m.mul(m.mul(C.g1[xd+n-1], C.g2[xd-1]), m.pow(d, n))


def main():
    Q = read_int()
    for _ in range(Q):
        x, d, n = read_int_n()
        print(slv(x, d, n))


if __name__ == '__main__':
    main()


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

public class Main {
    public static void main(String[] args) {
        //コード
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        String t = scanner.next();
        int a = Integer.parseInt(scanner.next());
        int b = Integer.parseInt(scanner.next());
        String u = scanner.next();

        if (s.equals(u)) {
            a--;
        } else {
            b--;
        }

        System.out.println(a + " " + b +" ");
    }
}

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

int main() {
  int A,B,C;
  cin >> A >> B >> C;

  bool ans= false;
  for(int i=0; i<B; i++){
    if( A*i%B==C ){
      ans= true;
      break;
    }
  }

  if(ans){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
	string s;
	cin>>s;
	size_t h=0;
	size_t r=s.length()-1;
	if (r==0){
		cout<<0<<endl;
		return 0;
	}
	int aw=0;
	while (h<r){
		if (s[h]==s[r]){
			h++;
			r--;
		}else{
			if (s[h]=='x' && s[r]!='x'){
				h++;
				aw++;
			}else if (s[h]!='x' && s[r]=='x'){
				r--;
				aw++;
			}else{
				cout<<-1<<endl;
				return 0;
			}
		}
	}
	cout<<aw<<endl;
	return 0;
}

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

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

const double EPS = 1e-9;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

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

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

int main(void){
    ll H,W; cin >> H >> W;
    ll ans = 0;
    if(H==1 || W==1) ans = 1;
    else if(H%2 == 0 && W%2 == 0) ans = H*W/2;
    else if(W%2 == 0 && H%2 == 1) ans = H*(W/2);
    else if(H%2 == 0 && W%2 == 1) ans = W*(H/2);
    else ans = W*((H-1)/2) + (W+1)/2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

int main() {
    int h, w;
    while (cin >> h >> w) {
        if (h == 0) return 0;
        string r[100], s;
        int x[200], y[200];
        for (int i = 0; i < h; i++) {
            cin >> r[i];
            for (int j = 0; j < w; j++) {
                if (char(r[i][j]) != '_') {
                    x[int(r[i][j])] = i;
                    y[int(r[i][j])] = j;
                }
            }
        }
        cin >> s;
        
        int ans = x[int(s[0])] + y[int(s[0])] + 1;
        for (int i = 0; i < s.size() - 1; i++) {
            ans += abs(x[int(s[i + 1])] - x[int(s[i])]) + abs(y[int(s[i + 1])] - y[int(s[i])]) + 1;
        }
        cout << ans << endl;
    }
    
}


Measured memory_bytes: 3160
def main():
    n = int(input())
    
    a = list(map(int,input().split()))
    a = [0] + a
    
    count = 0
    for i in range(1,n+1):
        if i%2==1 and a[i]%2==1:
            count+=1
    print(count)
    
if __name__=='__main__':
    main()


Measured memory_bytes: 8996
import java.util.*;
import java.io.*;
public class Main  {
    public static void main(String args[]) {
      FastScanner fs=new FastScanner();    
      PrintWriter out=new PrintWriter(System.out);
        int x=fs.nextInt();
        out.println(x==1?0:1);
        out.flush();
        out.close();
    }
	static void ruffleSort(int[] a) {
 		Random random=new Random();
		int n=a.length;
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n), temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
}
        class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		
		String next() {
			while (!st.hasMoreTokens())
				try {
				st=new StringTokenizer(br.readLine());
				}
				catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		String nextLine() {
		    String str="";
		    try {
		        str=br.readLine();
		    }
		    catch (IOException e) {
		        e.printStackTrace(); 
		    }
		    return str;
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		double nextDouble() {
		    return Double.parseDouble(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
	}

Measured memory_bytes: 32996
import sys
readline = sys.stdin.readline

def main():
    N = int(readline())
    A = list(map(int, readline().rstrip().split()))
    Ai = [a-i-1 for i, a in enumerate((A))]
    Ai.sort()
    if N % 2 == 1:
        b = Ai[N//2]
    else:
        b = (Ai[N//2-1] + Ai[N//2]) / 2

    print(int(sum([abs(a-b) for a in Ai])))


if __name__ == '__main__':
    main()

Measured memory_bytes: 25284
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << "\n";
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << " ";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return 0
#define br break
#define con continue
#define lcm(n, m) (n * m / gcd(n, m))
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define repill(i, m, n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define repll(i, n) repill(i, 0, n)
#define revi(i, m, n) for(int i=(int)(m);i>(int)(n);i--)
#define rev(i, n) revi(i, 0, n)
#define revill(i, m, n) for(ll i=(ll)(m);i>(ll)(n);i--)
#define revll(i, n) revill(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define all(n) (n.begin(), n.end())
#define sp(n) cout << fixed << setprecision(n)
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数 __builtin_popcount bitの個数

int main() {
  int N;
  ci(N);
  rep(i, 15){
    rep(j, 25){
      if(7 * i + 4 * j == N){
        co("Yes");
        rt;
      }
    }
  }
  co("No");
}

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

using namespace std;

template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
void warshall_floyd(Matrix< T > &g, T INF) {
  for(int k = 0; k < g.size(); k++) {
    for(int i = 0; i < g.size(); i++) {
      for(int j = 0; j < g.size(); j++) {
        if(g[i][k] == INF || g[k][j] == INF) continue;
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
}

int main() {
  int V, E;
  scanf("%d %d", &V, &E);
  Matrix< int > mat(V, vector< int >(V, INT_MAX));
  for(int i = 0; i < V; i++) mat[i][i] = 0;
  for(int i = 0; i < E; i++) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    mat[x][y] = z;
  }
  warshall_floyd(mat, INT_MAX);
  for(int i = 0; i < V; i++) {
    if(mat[i][i] < 0) {
      puts("NEGATIVE CYCLE");
      return 0;
    }
  }
  for(int i = 0; i < V; i++) {
    for(int j = 0; j < V; j++) {
      if(j > 0) putchar(' ');
      if(mat[i][j] == INT_MAX) printf("INF");
      else printf("%d", mat[i][j]);
    }
    putchar('\n');
  }
}



Measured memory_bytes: 3320
#include<iostream>
#include<algorithm>
#include<functional>
#include <string>
#include<iomanip>
#include<cstdio>
#include<math.h>
#include<stack>
#include<queue>
#include<cstring>
#include<vector>
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EREP(i,n) for(int i=(n-1);i>=0;--i)
#define D(n,retu) REP(i,n){cin>>retu[i];}
#define mod 1000000007
#define MIN -93193111451418101
#define INF 931931114518101
using namespace std;
typedef long long int ll;
template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}
#define MAX_NUM 50
long long comb[MAX_NUM + 1][MAX_NUM + 1];

static void calc_comb()
{
	for (uint32_t i = 0; i <= MAX_NUM; i++) {
		for (uint32_t j = 0; j <= i; j++) {
			if ((j == 0) || (i == j)) {
				comb[i][j] = 1;
			}
			else {
				comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
			}
		}
	}
}

//------------------変数-----------------------//
ll n, m, a, b;
typedef pair<ll, ll> P;
vector<vector<ll>> way(2001), money(2001);
ll maxa = 0, moto = 0;
ll v[11451] = {};
queue <ll>q;
ll bitmax = 0;
//-------------------関数----------------------//

int main() {
	cin >> n >> a >> b; double hoge = a;
	calc_comb();
	REP(i, n) {
		cin >> v[i];
	}
	sort(v, v + n);
	double heikin = 0;
	bool onaji = true;
	ll mae = v[n - 1];
	ll saigo = v[n - a];
	for (ll i = n - 1; i >= n - a; i--)
	{
		if (v[i] != mae) { onaji = false; }
		heikin += v[i];
	}
	heikin /= hoge;
	ll cnt = 0;
	ll goukei = 0;
	if (onaji == false) {
		ll wei = 0;
		REP(i, n) {
			if (v[i] == saigo) { cnt++; if (i > n - a - 1) { wei++; } }
		}
		cout << fixed << setprecision(7) << heikin << endl;
		cout<<  comb[cnt][wei] << endl;
	}
	else {
		for (ll i = n - 1; i >= 0; i--)
		{
			if (v[i] == mae) { cnt++; }
		}
		for (int i = a; i <= b; i++)
		{
			goukei += comb[cnt][i];
		}
		cout << fixed << setprecision(7) << heikin << endl;
		cout << goukei << endl;
	}
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;

struct UnionFind
{
  vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

  UnionFind(int N) : par(N)
  { //最初は全てが根であるとして初期化
    for (int i = 0; i < N; i++)
      par[i] = i;
  }

  int root(int x)
  { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
    if (par[x] == x)
      return x;
    return par[x] = root(par[x]);
  }

  void unite(int x, int y)
  { // xとyの木を併合
    int rx = root(x); //xの根をrx
    int ry = root(y); //yの根をry
    if (rx == ry)
      return;     //xとyの根が同じ(=同じ木にある)時はそのまま
    par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
  }

  bool same(int x, int y)
  { // 2つのデータx, yが属する木が同じならtrueを返す
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
};

int main()
{
  int N,M;
  cin >> N >> M;
  vector<int> p(N);
  REP(n,N) cin >> p[n];
  UnionFind tree(N);
  REP(m,M){
    int x,y;
    cin >> x >> y;
    x--, y--;
    tree.unite(x,y);
  }
  int ans = 0;
  REP(n,N){
    if(tree.same(n,p[n]-1)) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)

struct INIT{
    INIT(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);
        cout << fixed << setprecision(13);
    }
}INIT;

int m;
LL digcnt, digsum;
LL d, c;
int main(){
    cin >> m;
    REP(i, m){
        cin >> d >> c;
        digcnt += c;
        digsum += d * c;
    }
    cout << (digcnt - 1LL) + ((digsum - 1) / 9LL) << endl;
}

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

#define For(i, n) for(int i = 0; i < (n); i ++)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Cin(T, x) T x; cin >> x
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cout(x) cout << (x) << "\n"
#define Couts(xs) for(const auto &e : xs) cout << e << " "; cout << "\n"
#define Vec2(T, vs, n, m) vector<vector<T>> vs(n, vector<T>(m))
#define Cusum(T, n, xs, sxs) vector<T> sxs(n+1); For(i, n) sxs[i+1] = sxs[i] + xs[i]
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))

using namespace std;
using ll = long long;

int main(void){
    Cins(int, 3, a);
    Cin(int, k);
    DeSort(a);
    Cout(a[0] * (1 << k) + a[1] + a[2]);
    //Cout(() ? "Yes" : "No");
    //Cout(() ? "YES" : "NO");
}

Measured memory_bytes: 256
/*
 * 競技プログラミング用テンプレート
 * by yuma140902
 * 2020/06/01
 * ver 0.3.1
 */
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
typedef tuple<int, int> ii;
typedef tuple<int, int, int> iii;
const int INF = 900000;
const ll INFL = 9000000;

#define vi vector<int>
#define vii vector<vector<int> >
#define vi_def(n) vector<int>((n))
#define vii_def(n,m) vector<vector<int> >((n), vector<int>((m)))
#define vi_def_dflt(n, def) vector<int>((n), (def))
#define vii_def_dflt(n, m, def) vector<vector<int> >((n), vector<int>((m), (def)))

#define rep(i, n) for(int i=0; i < (n); ++i)
#define per(i, n) for(int i=(n)-1; i >= 0; --i)
#define range(i, begin, end) for(int i=(begin); i < (end); ++i)

#define ALL(vec) vec.begin(), vec.end()

#ifdef DBG_FLAG
#define pdbg(msg) cout << (msg)
#define dbg if(true)
#else
#define pdbg(msg) ;
#define dbg if(false)
#endif



int N;
vi X;

int calcTotalCost(int p){
  int cost = 0;
  rep(i, N){
    int tmp = X[i] - p;
    cost += tmp*tmp;
  }
  return cost;
}

int main(){
  cin >> N;
  X = vi_def(N);
  rep(i, N){
    cin >> X[i];
  }

  int sum = accumulate(ALL(X), 0);
  float avg = (float)sum / X.size();
  int ideal1 = (int)floorf(avg);
  int ideal2 = (int)ceilf(avg);
  int cost1 = calcTotalCost(ideal1);
  int cost2 = calcTotalCost(ideal2);
  int ans = min(cost1, cost2);

  dbg{
    printf("sum: %d, avg: %f\n", sum, avg);
    printf("ideal: [%d, %d]\n", ideal1, ideal2);
    printf("cost: [%d, %d]\n", cost1, cost2);
    printf("ans: %d\n", ans);
  }

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

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(long long int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

int main(){

    long long int n,a,b;
    cin>>n>>a>>b;
    long long int tmp = n/(a+b);

    long long int result=tmp*a;
    result+=min(a,(n%(a+b)));
    cout<<result<<endl;
    return 0;
}


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

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

int main()
{
  int T;
  while (cin >> T) {
    for (int t = 0; t < T; ++t) {
      vector<string> puyo(12);
      for (int i = 0; i < 12; ++i)
	cin >> puyo[i];

      int ans = 0;
      for ( ; ; ) {
	bool update = false;
	vector<vector<int> > visited(puyo.size(), vector<int>(puyo[0].size(), 0));
	for (unsigned int i = 0; i < puyo.size(); ++i) {
	  for (unsigned int j = 0; j < puyo[0].size(); ++j) {
	    if (puyo[i][j] != '.' && puyo[i][j] != 'O' && !visited[i][j]) {
	      int cnt = 0;
	      queue<pair<int, int> > que;
	      que.push(pair<int, int>(i, j));
	      while (!que.empty()) {
		const pair<int, int> p = que.front();
		que.pop();

		++cnt;
		visited[p.first][p.second] = 1;
		for (int d = 0; d < 4; ++d) {
		  int ii = p.first + dy[d];
		  int jj = p.second + dx[d];
		  if (ii < 0 || ii >= puyo.size() || jj < 0 || jj >= puyo[0].size() || puyo[ii][jj] != puyo[i][j] || visited[ii][jj])
		      continue;
		  que.push(pair<int, int>(ii, jj));
		}
	      }
	      if (cnt >= 4) {
		update = true;
		char color = puyo[i][j];
		que.push(pair<int, int>(i, j));
		vector<vector<int> > deleted(puyo.size(), vector<int>(puyo[0].size(), 0));
		while (!que.empty()) {
		  const pair<int, int> p = que.front();
		  que.pop();

		  puyo[p.first][p.second] = '.';
		  deleted[p.first][p.second] = 1;
		  for (int d = 0; d < 4; ++d) {
		    int ii = p.first + dy[d];
		    int jj = p.second + dx[d];
		    if (ii < 0 || ii >= puyo.size() || jj < 0 || jj >= puyo[0].size() || deleted[ii][jj])
		      continue;
		    
		    if (puyo[ii][jj] == color) {
		      que.push(pair<int, int>(ii, jj));
		    } else if (puyo[ii][jj] == 'O')
		      puyo[ii][jj] = '.';
		  }
		}
	      }
	    }
	  }
	}

	if (!update)
	  break;

	++ans;
	for (int i = puyo.size()-1; i >= 0; --i) {
	  for (unsigned int j = 0; j < puyo[0].size(); ++j) {
	    if (puyo[i][j] != '.') {
	      int ii = i + 1;
	      while (ii < puyo.size() && puyo[ii][j] == '.')
		++ii;
	      swap(puyo[i][j], puyo[ii-1][j]);
	    }
	  }
	}
      }
      cout << ans << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include <stdio.h>

int main(){
	int n, x;
	int i, j, k;
	int res = 0;
	
	while(1) {
		scanf("%d %d", &n, &x);
		if((n == 0) && (x == 0)) break;
		
		for(i=1; i<=n; i++) {
			for(j=i+1; j<=n; j++) {
				for(k=j+1; k<=n; k++) {
					if(i + j + k == x) res++;
				}
			}
		}
		printf("%d\n", res);
		res = 0;
	}
	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>
#include <chrono>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
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;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;
const double EPS = 1e-9;

const int MAX = 1e5 + 10;
int N;
vector<int> a;

int main() {
    scanf("%d", &N);
    int pre = -1;
    for (int i = 0; i < N; ++i) {
        int buf; scanf("%d", &buf);
        if (buf != pre) {
            a.emplace_back(buf);
            pre = buf;
        }
    }
    N = a.size();
    int ans = 1;
    bool up = false, start = true;
    for (int i = 1; i < N; ++i) {
        if (start) {
            up = a[i - 1] < a[i];
            start = false;
        } else {
            if (up ^ a[i - 1] < a[i]) {
                ++ans;
                start = true;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 892
sx,sy,tx,ty = [int(_) for _ in input().split()]

#スタート地点を{0,0}にする
tx = tx - sx
ty = ty - sy


if tx != 0 and ty != 0:
    aV = ["U","R","D","L"]
    d1 = ty
    d2 = tx
    if ty < 0 and 0 < tx :
        aV = ["R","D","L","U"]
        d1 = tx
        d2 = -ty
    if ty < 0 and tx < 0:
        aV = ["D","L","U","R"]
        d1 = -ty
        d2 = -tx
    if 0 < ty and tx < 0:
        aV = ["L","U","R","D"]
        d1 = -tx
        d2 = ty
    print( aV[0]*d1 + aV[1]*d2 + aV[2]*d1 + aV[3]*(d2+1)
        + aV[0]*(d1+1) + aV[1]*(d2+1) + aV[2] + aV[1] + aV[2]*(d1+1) + aV[3] * (d2+1) + aV[0])
else:
    if 0 < ty and tx == 0:
        aV = ["U","R","D","L"]
        d1 = ty
        d2 = tx
    if ty == 0 and 0 < tx :
        aV = ["R","D","L","D"]
        d1 = tx
        d2 = ty
    if ty < 0 and tx == 0 :
        aV = ["D","L","D","R"]
        d1 = ty
        d2 = tx
    if ty == 0 and tx < 0 :
        aV = ["L","D","R","D"]
        d1 = tx
        d2 = ty
    print( aV[0]*d1 + aV[1] + aV[2] * d1 + aV[3] * 2 + aV[0] * d1 + aV[1] + aV[0] + aV[1] * 2 + aV[2] * (d1+2) + aV[3] * 2 + aV[0])


Measured memory_bytes: 3188
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
    	
		Scanner sc = new Scanner(System.in);
		// 整数の入力　りんご
		int A = sc.nextInt();
		// 整数の入力　りんご　はんぱ
		int P = sc.nextInt();
		
		int all = A * 3 + P;
		
		int ans = all / 2;
		

		System.out.println(ans);

   		sc.close();
        return ;

    }
    
}



Measured memory_bytes: 21844
n, m = map(int, raw_input().split())
edges = [list(map(int, raw_input().split())) for _ in xrange(m)]

adjacent = [[] for _ in xrange(n)]
for a, b in edges:
    adjacent[a-1].append(b)
    adjacent[b-1].append(a)

check = [False]*n
check[0] = True
count = 0

def DFS(cn):
    global count
    if all(check):
        count += 1
        return 0
    for nn in adjacent[cn-1]:
        if check[nn-1] == True:
            continue
        else:
            check[nn-1] = True
            DFS(nn)
            check[nn-1] = False
    return 0

if __name__ == '__main__':
    DFS(1)
    print count

Measured memory_bytes: 2696
n = gets.to_i
arr = gets.chomp.split.map(&:to_f).sort
max = 0
arr.each_cons(2){|d, c|
    arr2 = arr.dup
    arr2.delete d
    arr2.delete c
    v = (arr2[-1] + arr2[-2]) / (c - d)
    max = v if max < v
}
puts max


Measured memory_bytes: 14760
import java.util.Scanner;
 
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String S=sc.next();
    String T=sc.next();
    int X=T.length();
    String Z=T.substring(0,X-1);
    if(S.equals(Z)) {
    	System.out.println("Yes");
    }else {
    	System.out.println("No");
    }
  }
}

Measured memory_bytes: 35648
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fr(i,n) for(int i=0;i<n;i++)
#define Fr(i,n) for(int i=0;i++<n;)
#define ifr(i,n) for(int i=n-1;i>=0;i--)

const ll MOD=998244353;
ll n,a[2010];

ll ad(ll x,ll y){
  return (x+y)%MOD;
}

ll mlt(ll x,ll y){
  return (x*y)%MOD;
}

ll pwr(ll x,ll y){
  ll pw[32]={},w=1;
  pw[0]=x;
  fr(i,31) pw[i+1]=mlt(pw[i],pw[i]);
  fr(i,32){
    w=mlt(w,1+(y%2)*(pw[i]-1));
    y/=2;
  }
  return w;
}

ll iv[2010]={};
ll inv(ll x){
  if(iv[x]<1) iv[x]=pwr(x,MOD-2);
  return iv[x];
}

ll nC[2010]={1};
ll comb(ll r){
  if(nC[r]==0) nC[r]=mlt(comb(r-1),mlt(n-r+1,inv(r)));
  return nC[r];
}

int main(){
  n=0;
  ll R=0,r=0,b=0;
  char c;
  for(;cin>>c;){
    a[n]=c-'0';
    if(a[n]<1) R++;
    if(a[n]<2) R++;
    n++;
  }
  ll dp[2010][2010]={};
  dp[0][0]=1;
  fr(i,n){
    if(a[i]<1) r+=2;
    else if(a[i]<2){r++;b++;}
    else b+=2;
    fr(j,n+1){
      ll k=i-j;
      if(k<0) break;
      if(r-j>0) dp[i+1][j+1]=ad(dp[i+1][j+1],dp[i][j]);
      if(b-k>0) dp[i+1][j]=ad(dp[i+1][j],dp[i][j]);
    }
  }
  ll ans=0;
  fr(j,n+1) if(R>=j && n+j>=R) ans=ad(ans,mlt(dp[n][j],comb(R-j)));
  cout<<ans<<endl;
}

Measured memory_bytes: 31872
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

int main(){
    ll k;
    cin >> k;
    vector<ll> ans;
    if(k < 50){
        ans.resize(2);
        if(k % 2 == 0){
            ll s = 1 + k / 2;
            ans.at(0) = s;
            ans.at(1) = s;
        }else{
            ll s = 1 + (k + 1) / 2;
            ans.at(0) = s - 2;
            ans.at(1) = s + 1;
        }
    }else{
        ans.resize(50);
        ll k2;
        if(k % 50 == 0){
            k2 = k;
        }else{
            k2 = k + (50 - k % 50);
        }
        ll s = 49 + k2 / 50;
        for(int i = 0; i < ans.size(); ++i){
            ans.at(i) = s;
        }
        for(; k2 > k; --k2){
            ll max_idx = max_element(ans.begin(), ans.end()) - ans.begin();
            for(int i = 0; i < ans.size(); ++i){
                if(i == max_idx){
                    ans.at(i) -= 50;
                }else{
                    ans.at(i) += 1;
                }
            }
        }
    }

    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); ++i){
        cout << ans.at(i);
        if(i < ans.size() - 1){
            cout << ' ';
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 888
#include <stdio.h>
#include <ctype.h>

int main(int argc, char **argv){
	int c;
	char s[2] = {};
	int x,cnt;

	for(;;){
		// Input & CountUp
		x = cnt = 0;
		for(;;){
			c = getchar();
			// EOL/EOF Check
			if( c == EOF || c == '\n' ){
				break;
			}
			// Number Check
			if( !isdigit(c) ){
				continue;
			}
			// Convert & CountUp
			s[0] = (char)c;
			x += atoi(s);
			cnt++;
		}
		// Finish Check
		if( x == 0 && cnt == 1 ){
			break;
		}
		// Output
		printf("%d\n",x);
	}

	return 0;
}

Measured memory_bytes: 524
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

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

int main(int argc, char **argv)
{
    int N;
    cin >> N;
    int u[N - 1], v[N - 1];
    ll w[N - 1];
    REP(i, N -1) cin >> u[i] >> v[i] >> w[i];

    map<int, ll> tree[N];
    REP(i, N - 1) {
        tree[u[i] - 1].insert(make_pair(v[i] - 1, w[i]));
        tree[v[i] - 1].insert(make_pair(u[i] - 1, w[i]));
    }

    int color[N];
    REP(i, N) color[i] = -1;
    color[0] = 0;

    deque< pair<int, pair<int, ll> > > dq;
    for (auto itr = tree[0].begin(); itr != tree[0].end(); ++itr) {
        dq.push_back(make_pair(0, make_pair(itr->first, itr->second)));
    }

    while (dq.size() != 0) {
        pair<int, pair<int, ll>> v = dq.front();
        dq.pop_front();
        if (color[v.second.first] == -1) {
            if (v.second.second % 2 == 0) color[v.second.first] = color[v.first];
            else color[v.second.first] = 1 - color[v.first];
            for (auto itr = tree[v.second.first].begin(); itr != tree[v.second.first].end(); ++itr) {
                dq.push_back(make_pair(v.second.first, make_pair(itr->first, itr->second)));
            }
        }
    }
    REP(i, N) cout << color[i] << endl;
    return 0;
}


Measured memory_bytes: 19584
import java.math.*

fun main(args: Array<String>) {
    val N = readInputLine().toInt()
    val S = readInputLine()
    
    var ans = 0
    
    for (i in 0 until N) {
        val tmp = zAlgorithm(S.substring(i..N - 1))
        ans = tmp.foldIndexed(ans) { index, acc, len -> 
            if (index == 0 || len == 0) acc
            else Math.max(acc, Math.min(len, index))
        }
        
    }
    
    println(ans)
}

fun readInputLine(): String {
    return readLine()!!
}

fun zAlgorithm(s: String): IntArray {
    val ret = IntArray(s.length)
    
    ret[0] = s.length
    
    var i = 1
    var j = 0
    
    while (i < s.length) {
        while (i + j < s.length && s[j] == s[i + j]) {
            j++
        }
        ret[i] = j
        if (j == 0) {
            i++
            continue
        }
        var k = 1
        while (i + k < s.length && k + ret[k] < j) {
            ret[i + k] = ret[k]
            k++
        }
        i += k
        j -= k
    }
    
    return ret
}


Measured memory_bytes: 104112
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase

/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=998244353;
const llint big=2.19e18+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	llint i,n,B,ans=0;cin>>n;
	vector<llint>A(n);
	for(i=1;i<=n;i++){cin>>A[i-1];A[i-1]-=i;}
	SO(A);
	B=A[n/2];
	for(i=0;i<n;i++){ans+=abs(B-A[i]);}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
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; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> t(n+1, 0), x(n+1, 0), y(n+1, 0);
    REP(i, 1, n+1) {
        cin >> t[i] >> x[i] >> y[i];
    }

    vector<int> v(n+1);
    iota(v.begin(), v.end(), 0);
    sort(v.begin(), v.end(), [&](int i, int j) {return t[i] < t[j];});

    bool ok = true;
    rep(i, n) {
        int c = abs(x[v[i]] - x[v[i+1]]) + abs(y[v[i]] - y[v[i+1]]);
        int dt = t[v[i+1]] - t[v[i]];
        if (c <= dt && c % 2 == dt % 2) continue;
        else ok = false;
    }

    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 1792
def BubbleSort(C,n):
	for i in range(n):
		for j in range(i+1,n)[::-1]:
			if C[j][1] < C[j-1][1]:
				C[j],C[j-1] = C[j-1],C[j]
	return C

def SelectionSort(C,n):
	for i in range(n):
		minj = i
		for j in range(i,n):
			if C[j][1] < C[minj][1]:
				minj = j
		C[i],C[minj] = C[minj],C[i]
	return C

def stable(C):
	new = []
	for i in range(1,10):
		Ci = [cc for cc in C if cc[1]==str(i)]
		new += Ci
	return new

n = int(input())
C = input().split()
x,y,z = C[:],C[:],C[:]
bubble = BubbleSort(x,n)
selection = SelectionSort(y,n)
sta = stable(z)

print(' '.join(bubble))
print({True:'Stable',False:'Not stable'}[sta==bubble])
print(' '.join(selection))
print({True:'Stable',False:'Not stable'}[sta==selection])

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

using namespace std;
int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  int flag=1;
  while(true){
    if(flag%2!=0){
      c=c-b;
    }
    else
      a=a-d;
    
    if(c<=0){
      cout<<"Yes";
      return 0;
    }
    else if(a<=0){
      cout<<"No";
      return 0;
    }
    flag+=1;
  }
  return 0;
  }

Measured memory_bytes: 3636
import java.util.*;

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

        boolean isEvenA = false;
        boolean isEvenB = false;
        boolean isEvenC = false;

        int count = 0;

        if(a % 2 == 0){
            isEvenA = true;
            count++;
        }

        if(b % 2 == 0){
            isEvenB = true;
            count++;
        }

        if(c % 2 == 0){
            isEvenC = true;
            count++;
        }


        int ans = 0;

        switch (count){
            case 0:
                break;
            case 1:
                if(! isEvenA){
                    a++;
                }
                if(! isEvenB){
                    b++;
                }
                if(! isEvenC){
                    c++;
                }

                ans += 1;
                break;
            case 2:
                if(isEvenA){
                    a++;
                }
                if(isEvenB){
                    b++;
                }
                if(isEvenC){
                    c++;
                }

                ans += 1;
                break;
            case 3:
                break;
        }


        List<Integer> list = Arrays.asList(a, b, c);
        Collections.sort(list);


        System.out.println((((list.get(2) * 2) - (list.get(0) + list.get(1))) / 2) + ans);
    }
}


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

using namespace std;
typedef long long int lli;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef pair <lli,lli> pii;
#define all(vec) vec.begin(),vec.end()
#define ff first
#define ss second
#define inf 4e18
#define MOD 1000000007
#define push_back emplace_back
#define pb push_back
#define for1(low,high,k) for(int i=low;i<high;i+=k)
#define for2(low,high,k) for(int j=low;j<high;j+=k)
#define rev(high,low,k) for(int i=high;i>=low;i-=k) 

int main(){
	fast;
	lli k,a,b;
	cin>>k>>a>>b;
	if (a%k==0 || b%k==0) cout<<"OK"<<endl;
	else{
	a=a/k;
	b=b/k;
	if (b>a) cout<<"OK"<<endl;
	else cout<<"NG"<<endl;
}	
}

Measured memory_bytes: 3652
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<string>
#include <iomanip>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
typedef long long ll;
//#define INF 1000000000000 //10^12:極めて大きい値,∞
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)

int main(){
    int H,M;
    while(1){
        cin >> H >> M;
        if(H==0&&M==0) break;
        REP(i,H){
            REP(j,M){
                if(i==0||j==0||i==H-1||j==M-1) cout << '#';
                else cout << '.';
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3048
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ld = long double;
using p = pair<int, int>;
using Graph = vector<vector<int>>;
#define rep(i,n)  for(int i = 0; i < n ; i++)
int dx[4]{ -1,0,1,0 };
int dy[4]{ 0,1,0,-1 };
 
int main()
{
	int N, M;
	cin >> N >> M;
	vector<int> Item(N);
	double all = 0;
	rep(i, N)
	{
		cin >> Item[i];
		all += Item[i];
	}
	sort(Item.begin(), Item.end());
	reverse(Item.begin(), Item.end());
    double th = (all / (double)(4 * M));
	if (Item[M - 1] < th)
	{
		cout << "No" << endl;
	}
	else
	{
		cout << "Yes" << endl;
	}
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
public static void main(String[] args) {
		
		Scanner keyboard = new Scanner(System.in); 
		
		int A= keyboard.nextInt();
		int B= keyboard.nextInt();
		int C= keyboard.nextInt();
		int D= keyboard.nextInt();
		
		String ans = "No";
		int countT = 0;
		int countA = 0;
		
		while(A>0) {
			A -= D;
			countT++;
		}
		while(C>0) {
			C -= B;
			countA++;
		}
		
		if(countT >= countA) {
			ans = "Yes";
		}
		
		
		System.out.println(ans);
		keyboard.close();	
		
	}
}


Measured memory_bytes: 35700