akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <cmath>
#include <iomanip>
#include <deque>
#include <queue>
#include <unordered_map>
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
ll intpow(ll N, ll P){
    if(P==0) return 1;
    if(P%2==0){
        ll t = intpow(N, P/2);
        return t*t;
    }
    return N * intpow(N, P-1);
}
ll modpow(ll N, ll P,ll k){
    if(P==0) return 1;
    if(P%2==0){
        ll t = modpow(N, P/2,k)%k;
        return t*t%k;
    }
    return N * modpow(N, P-1,k)%k;
}
ll modkai(ll n,ll m,ll k){//n*(n-1)*(n-2)*...(m+1)%k
    if(n == m)return 1;
    return modkai(n-1,m,k)*n%k;
}
ll mod_cnb(ll n,ll m,ll k){//nCm%k,kは十分大きい素数
  int m_=modkai(m,0,k);
  return modkai(n,n-m,k)*modpow(m_,k-2,k)%k;
}
ll gcd(ll n,ll m){
    ll n_ = max(n,m);
    ll m_ = min(n,m);
    if(n_%m_ == 0)return m_;
    return gcd(m_,n_%m_);
}
ll lcm(ll n,ll m){
    return n*m/gcd(n,m);
}
vector<ll> l;
queue<ll> q;
ll p=3234566667;
void pls(){
    while(!q.empty()){
        ll a=q.front();
        q.pop();
        ll b=a%10;
        if(b==9 && a*10+9<=3234566667){
            l.push_back(a*10+8);
            l.push_back(a*10+9);
            q.push(a*10+8);
            q.push(a*10+9);
            }
        else if(b==0 && a*10+1<=p){
            l.push_back(a*10);
            l.push_back(a*10+1);
            q.push(a*10);
            q.push(a*10+1);
            }
        else if(a*10+b+1<=p){
            rep(i,3){
                l.push_back(a*10+b+i-1);
                q.push(a*10+b+i-1);
                }
            }
    }
}
int main(){
    ll k;cin>>k;
    rep(i,9)q.push(i+1),l.push_back(i+1);
    pls();
    sort(l.begin(),l.end());
    cout<<l[k-1]<<endl;
}

Measured memory_bytes: 1620
#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <queue>

using namespace std;

typedef long long ll;

const int MAXN = 100000+5;

int parent[MAXN];
int marked[MAXN];
int N,Q;

int main()
{
    while(scanf("%d%d", &N, &Q)!=EOF){
        if(N==0 || Q==0) break;
        memset(parent, -1, sizeof(parent));
        memset(marked, 0, sizeof(marked));
        int p;
        for(int i=1;i<N;++i){
            scanf("%d", &p);
            parent[i+1] = p;
        }
        getchar();
        char c;
        ll ans = 0;
        marked[1] = 1;
        for(int i=0;i<Q;++i){
            scanf("%c%d", &c, &p);
            getchar();
            if(c=='M'){
                marked[p] = 1;
            }
            else{
                while(!marked[p]){
                    p = parent[p];
                }
                ans += p;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}


Measured memory_bytes: 3928
#include<bits/stdc++.h>
using namespace std;
//これだとTLE
typedef long long ll;
int N, K;
int a[110];
const ll MOD = 1e9 + 7;
ll A[110];
ll dp[110][100010];

ll rec(int n, int k)
{   
    
    if(k == 0) return 1;
    if(n == 0 || k < 0) return 0;
    if(dp[n][k] != -1) return dp[n][k];
    ll res = rec(n - 1, k) % MOD + rec(n, k - 1) % MOD - rec(n - 1, k - a[n] - 1) + MOD;
    return dp[n][k] = res % MOD;
}

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

    

    memset(dp, -1, sizeof(dp));
    //for(int i = 0; i < 110; i++)
    //for(int j = 0; j < 100010; j++) dp[i][j] = -1;
    memset(A, 0, sizeof(A));

    for(int i = 1; i <= N; i++) 
    {   
        cin >> a[i];
        A[i] += A[i - 1] + a[i];
    }
    if(K == 0 && A[N] == 0)
    {
        cout << 1 << endl;
        return 0;
    }
    cout << rec(N, K) << endl;
}


Measured memory_bytes: 92416
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int a,b;

void gcd(int a,int b,int c){
	if(!b)cout<<a<<" "<<c<<endl;
	else gcd(b,a%b,++c);
}

int main(){
	while(cin>>a>>b){
		if(!a)return 0;
		gcd(max(a,b),min(a,b),0);
	}
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
#include<stdio.h>
#define LL long long 
LL H, W, A, B;
LL mod = 1000000007;
LL mul[200010];
LL dis[200010];
LL ans;
LL fermat(LL x, LL y) {
	//std::cout << y << std::endl;
	if (y == 0) return 1;
	if (y == 1)	return x;
	if (y % 2 == 1) {
		LL F = fermat(x, y / 2);
		F *= F;
		F%=mod;
		return F*x%mod;
	}
	if (y % 2 == 0) {
		LL F = fermat(x, y / 2);
		F *= F;
		return F%mod;
	}
}

int main() {
	scanf("%d%d%d%d", &H,&W,&A,&B);
	mul[1] = 1;
	mul[0] = 1;
	for (LL i = 1; i <= H + W - 2; i++) {
		mul[i] = mul[i - 1] * i%mod;
	}
	dis[H + W - 2] = fermat(mul[H + W - 2], mod - 2);
	for (LL i = H + W - 3; i > 0; i--) {
		dis[i] = dis[i + 1] * (i + 1)% mod;
	}
	dis[0] = 1;
	for (LL i = B; i < W; i++) {
		LL plus = mul[H - A + i - 1] * dis[i];
		plus %= mod;
		plus *= dis[H - A - 1];
		plus %= mod;
		LL plus2 = mul[W + A - i - 2] * dis[A - 1];
		plus2 %= mod;
		plus2 *= dis[W - i - 1];
		plus2 %= mod;
		ans += plus*plus2;
		ans %= mod;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 3328
using System;
using System.Linq;

namespace ConsoleApp2
{
    class Program
    {
        static void Main()
        {
            string input= Console.ReadLine();

            string output = input;

            if (input.Last() =='s')
            {
                output += "es";
            }
            else
            {
                output += "s";
            }
            Console.WriteLine(output);
        }
    }
}


Measured memory_bytes: 26240
#include <iostream>
#include<algorithm>
using namespace std;
 int main()
   {
     string s;
     string t;
     cin>>s>>t;
     int u=0;
     
      for(int i=0;i<s.size();i++)
         {
           if(s[i]!=t[i]){u++;}
         }
         cout<<u<<endl;
   }

Measured memory_bytes: 3868
fun main(args: Array<String>) {
    val (N, K) = readLine()!!.split(" ").map { it.toInt() }
    val x = Array(N) { 0 }
    val y = Array(N) { 0 }
    val c = Array(N) { 'B' }

    fun flip(c: Char): Char = if (c == 'B') 'W' else 'B'

    for (i in x.indices) {
        val (X, Y, C) = readLine()!!.split(" ")
        x[i] = X.toInt()
        y[i] = Y.toInt()
        c[i] = C[0]

        x[i] %= 2 * K
        if (x[i] >= K) {
            x[i] -= K
            c[i] = flip(c[i])
        }

        y[i] %= 2 * K
        if (y[i] >= K) {
            y[i] -= K
            c[i] = flip(c[i])
        }
    }

    val imosB = Array(K + 2) { Array(K + 2) { 0 } }
    val imosW = Array(K + 2) { Array(K + 2) { 0 } }

    for (i in x.indices) {
        if (c[i] == 'B') {
            imosB[y[i] + 1][x[i] + 1]++
        } else {
            imosW[y[i] + 1][x[i] + 1]++
        }
    }

    for (i in 1 until imosB.size) for (j in 1 until imosB[i].size) {
        imosB[i][j] += imosB[i - 1][j] + imosB[i][j - 1] - imosB[i - 1][j - 1]
        imosW[i][j] += imosW[i - 1][j] + imosW[i][j - 1] - imosW[i - 1][j - 1]
    }

    fun calcSum(si: Int, sj: Int, ei: Int, ej: Int, imos: Array<Array<Int>>): Int {
        if (si > ei || sj > ej) return 0
        return imos[ei][ej] - imos[si - 1][ej] - imos[ei][sj - 1] + imos[si - 1][sj - 1]
    }

    var res = 0

    for (si in 1..K) for (sj in 1..K) {
        fun calc(a: Array<Array<Int>>, b: Array<Array<Int>>): Int {
            return calcSum(1, 1, si - 1, sj - 1, a) + calcSum(si, sj, K, K, a) +
                    calcSum(1, sj, si - 1, K, b) + calcSum(si, 1, K, sj - 1, b)
        }
        res = Math.max(res, calc(imosB, imosW))
        res = Math.max(res, calc(imosW, imosB))
    }

    println(res)
}


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

using namespace std;

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

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

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {

	LL n; cin >> n;

	set<LL> used;

	used.insert(n);

	for (int i = 2; i < 1000001; i++) {
		if (n % 2 == 0) {
			n = n / 2;

			if (used.find(n) != used.end()) {
				cout << i << endl;
				return 0;
			}
			else {
				used.insert(n);
			}
		}
		else {
			n = (LL)3 * n + 1;

			if (used.find(n) != used.end()) {
				cout << i << endl;
				return 0;
			}
			else {
				used.insert(n);
			}
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,n) for(int i=1;i<=n;i++)

#define INF 1000000000

int main(){
	while(1){
		int n,m;
		cin>>n>>m;
		
		if(n==0 && m==0)break;
		
		int dp[111][111][2];
		rep(p,2){
		rep(i,111)rep(j,111){
			dp[i][j][p]=INF;
		}
		}
		
		
		rep(i,n){
			int a,b,c,d;
			cin>>a>>b>>c>>d;
			
			dp[a][b][0] = c;
			dp[b][a][0] = c;
			
			dp[a][b][1] = d;
			dp[b][a][1] = d;
		}
		
		for(int p=0;p<2;p++){
		for(int k=1;k<=m;k++){
			for(int i=1;i<=m;i++){
				for(int j=1;j<=m;j++){
					dp[i][j][p] = min(dp[i][j][p], dp[i][k][p]+dp[k][j][p]);
				}
			}
		}
		}
		
		int r;
		cin>>r;
		
		rep(i,r){
			int a,b,c;
			cin>>a>>b>>c;
			printf("%d\n",dp[a][b][c]);
		}
	}
}

Measured memory_bytes: 964
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#define INF 1000000021
#define MOD 1000000007
#define pb push_back
#define sqr(a) (a)*(a)
#define M(a, b) make_pair(a,b)
#define T(a, b, c) make_pair(a, make_pair(b, c))
#define F first
#define S second
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 222222

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const ld pi = 2 * acos(0.0);
template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;}
template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;}
template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int r[N], b[N], g[N];
int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	for(int i = 0; i < n; i ++)
	{
		if(i)
			r[i] = r[i - 1], g[i] = g[i - 1], b[i] = b[i - 1];
		r[i] += (s[i] == 'R');
		g[i] += (s[i] == 'G');
		b[i] += (s[i] =='B');
	}
	ll ans = 0;
	for(int i = 0; i < n; i ++)
	{
		for(int j = i + 2; j < n; j ++)
		{
			if(s[i] == 'R' && s[j] == 'B')
			{
				int q = g[j] - g[i];
				if((j - i) % 2 == 0)
				{
					if(s[i + (j-i)/2] == 'G')
						q --;
				}
				ans += q;
			}
			if(s[i] == 'R' && s[j] == 'G')
			{
				int q = b[j] - b[i];
				if((j - i) % 2 == 0)
				{
					if(s[i + (j-i)/2] == 'B')
						q --;
				}
				ans += q;
			}			
			if(s[i] == 'G' && s[j] == 'B')
			{
				int q = r[j] - r[i];
				if((j - i) % 2 == 0)
				{
					if(s[i + (j-i)/2] == 'R')
						q --;
				}
				ans += q;
			}
			if(s[i] == 'G' && s[j] == 'R')
			{
				int q = b[j] - b[i];
				if((j - i) % 2 == 0)
				{
					if(s[i + (j-i)/2] == 'B')
						q --;
				}
				ans += q;
			}
			if(s[i] == 'B' && s[j] == 'R')
			{
				int q = g[j] - g[i];
				if((j - i) % 2 == 0)
				{
					if(s[i + (j-i)/2] == 'G')
						q --;
				}
				ans += q;
			}
			if(s[i] == 'B' && s[j] == 'G')
			{
				int q = r[j] - r[i];
				if((j - i) % 2 == 0)
				{
					if(s[i + (j-i)/2] == 'R')
						q --;
				}
				ans += q;
			}
		}
	}
	cout << ans;





	





	getchar();
	getchar();
	return 0;
	//ios::sync_with_stdio(false);
	//cin.tie(0);
}

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

void solve(long long N, std::vector<long long> a) {
  sort(a.rbegin(), a.rend());

  long long sum = 0;
  for (int i = 0; i < N; i++) {
    sum += a[2 * i + 1];
  }

  printf("%lld\n", sum);
}

// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You
// use the default template now. You can remove this line by using your custom
// template)
int main() {
  long long N;
  scanf("%lld", &N);
  std::vector<long long> a(3 * N);
  for (int i = 0; i < 3 * N; i++) {
    scanf("%lld", &a[i]);
  }
  solve(N, std::move(a));
  return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>

int main(){
  int N, M, X, A, left=0, right=0;
  scanf("%d %d %d", &N, &M, &X);
  int i;
  for(i=1;i<=M;i++){
    scanf("%d", &A);
    if(A<X) left++;
    else right++;
  }
  int ans = left;
  if(left > right) ans = right;
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 128
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

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

func main() {
	sc.Split(bufio.ScanWords)
	a := nextLine()
	b := nextLine()

	c := strings.Split(a, "")
	d := strings.Split(b, "")

	t := ""
	for i, v := range d {
		t += c[i]
		t += v
	}

	if len(c) > len(d) {
		t += c[len(c)-1]
	}
	fmt.Println(t)
	return
}


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

int main() {
    int a,b;

    cin >> a >> b;

    if ((a + b) % 2 > 0) {
        cout << (a + b) / 2 + 1 << endl;
    }
    else {
        cout << (a + b) / 2  << endl;
    }

 
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int n = sc.nextInt();

//		String[] s = new String[n];
//		int[] p = new int[n];
		Pair[] sp = new Pair[n];
		for (int i = 0; i < n; i++) {
//			s[i] = sc.next();
//			p[i] = sc.nextInt();
			sp[i] = new Pair(sc.next(), sc.nextInt(), i);
		}
		Arrays.sort(sp);
		
		for (Pair e : sp) {
			pr.println(e.i + 1);
		}
	}

	static class Pair implements Comparable<Pair> {
		String a;
		int b;
		int i;

		Pair(String a, int b, int i) {
			this.a = a;
			this.b = b;
			this.i = i;
		}

		@Override
		public int compareTo(Pair o) {
			if (a.equals(o.a)) {
				return Integer.compare(o.b, b);
			}

			return a.compareTo(o.a);
		}

		@Override
		public int hashCode() {
			return Integer.hashCode(b);
		}

		@Override
		public boolean equals(Object obj) {
			Pair o = (Pair) obj;
			return a == o.a && b == o.b;
		}

		@Override
		public String toString() {
			// [xxx, xxxx]
			StringBuilder stmp = new StringBuilder(32);
			stmp.append('[');
			stmp.append(a);
			stmp.append(',');
			stmp.append(' ');
			stmp.append(b);
			stmp.append(']');

			return stmp.toString();
		}
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);
			
		solve();
			
		pr.close();
		sc.close();
	}

	static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
static const int MAX = 100000;
static const int NIL = -1;
using namespace std;


int main() {
    int n,m; cin >> n >> m;
    int tmp1,tmp2;
    string ans = "IMPOSSIBLE";
    vector<pair<bool,bool>> c(n);

    rep(i,m) {
        cin >> tmp1 >> tmp2;
        if(tmp1 == 1) c[tmp2-1].first = true;
        if(tmp2 == n) c[tmp1-1].second = true;
    }

    rep(i,n){
        if(c[i].first && c[i].second) ans = "POSSIBLE";
    }
    cout << ans;

    return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int i=0; i<n; i++)
#define FOR1(i, n) for(int i=1; i<=n; i++)
#define FORI(i, n) for(int i=n-1; i>=0; i--)
template<class T, class U> void umin(T& x, const U& y){ x = min(x, (T)y);}
template<class T, class U> void umax(T& x, const U& y){ x = max(x, (T)y);}
template<class T, class U> void init(vector<T> &v, U x, size_t n) { v=vector<T>(n, (T)x); }
template<class T, class U, typename... W> void init(vector<T> &v, U x, size_t n, W... m) { v=vector<T>(n);  for(auto& a : v) init(a, x, m...); }

vector<vector<vector<ll>>> dp;
vector<vector<int>> vs;
int r, c, k;

int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);

    int T = 1;
//    cin >> T;
    FOR1(tt, T){
        cin >> r >> c >> k;
        init(vs, 0, r+1, c+1);
        FOR(i, k){
            int ri, ci, vi;
            cin >> ri >> ci >> vi;
            vs[ri][ci] = vi;
        }

        init(dp, 0, r+1, c+1, 4);
        dp[r][c][1] = vs[r][c]; //at pos r, c taken t from row r
        for(int rr = r; rr > 0; rr--){
            for(int cc = c; cc > 0; cc--){
                //just go right
                if (cc < c){
                    FOR(i, 4){
                        umax(dp[rr][cc][i], dp[rr][cc+1][i]);
                    }
                }
                //just go down
                if (rr < r){
                    FOR(i, 4){
                        umax(dp[rr][cc][i], dp[rr+1][cc][i]);
                    }
                }
                if (vs[rr][cc]){
                    //take and go right
                    if (cc+1 <= c) {
                        FOR1(i, 3) {
                            umax(dp[rr][cc][i], dp[rr][cc + 1][i]);
                            umax(dp[rr][cc][i], dp[rr][cc + 1][i - 1] + vs[rr][cc]);
                        }
                    }
                    //take and go down
                    if (rr+1 <= r){
                        FOR(i, 4)
                            umax(dp[rr][cc][1], dp[rr+1][cc][i] + vs[rr][cc]);
                    }
                }
            }
        }
        ll sol = 0;
        FOR(i, 4) umax(sol, dp[1][1][i]);
        cout << sol << endl;
    }

    if (argc == 2 && atoi(argv[1]) == 123456789) cout << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}



Measured memory_bytes: 671192
#include <stdio.h>

int main() 
{

    char s[11], t[12];
    int i = 0;
    scanf("%s", s);
    scanf("%s", t);

    while(s[i]){
        if ( s[i] != t[i] ){
            printf("No");
            return 0;
        }
        i++;
    }
    printf("Yes");
    return 0;
}



Measured memory_bytes: 1708
from fractions import gcd
class SegmentTree(object):
    def __init__(self, sequence, function, identity):
        N = len(sequence)
        self.length = (1 << (N - 1)).bit_length()
        self.data = [identity] * (self.length << 1)
        self.function = function
        self.identity = identity
        for i in range(N):
            self.data[i + self.length - 1] = sequence[i]
        for i in range(self.length - 2, -1, -1) :
            self.data[i] = self.function(self.data[(i << 1) + 1], self.data[(i << 1) + 2])

    def update(self, idx, x):
        idx += self.length - 1
        self.data[idx] = x
        while idx:
            idx = (idx - 1) >> 1
            self.data[idx] = self.function(self.data[(idx << 1) + 1], self.data[(idx << 1) + 2])

    def query(self, p, q):
        if q <= p:
            return self.identity
        p += self.length - 1
        q += self.length - 2
        res = self.identity
        while q - p > 1:
            if not p & 1:
                res = self.function(res, self.data[p])
            if q & 1:
                res = self.function(res, self.data[q])
                q -= 1
            p >>= 1
            q = (q - 1) >> 1
        return self.function(res, self.data[p]) if p == q else self.function(self.function(res, self.data[p]), self.data[q])

N, *A = map(int, open(0).read().split())
seg_tree = SegmentTree(A, gcd, 0)
ans = 0
for i in range(N):
    seg_tree.update(i, 0)
    ans = max(ans, seg_tree.query(0, N))
    seg_tree.update(i, A[i])
print(ans)

Measured memory_bytes: 96824
#include <iostream>
#include <vector>
#include <atcoder/dsu>

int main()
{
    int N, Q;
    std::cin >> N >> Q;

    atcoder::dsu forest(N);
    std::vector<int> ans;

    for (int i = 0; i < Q; i++)
    {
        int q, u, v;
        std::cin >> q >> u >> v;
        if (q == 0)
            forest.merge(u, v);
        else
            ans.push_back(forest.same(u, v) ? 1 : 0);
    }

    for (int i = 0; i < ans.size(); i++)
        std::cout << ans[i] << std::endl;
}

Measured memory_bytes: 4424
#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,abm,fma,popcnt,mmx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
const char nl = '\n';
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 186, L = 17;

int n, m;
string grid[N];
int pref[N][N];
short dp[N][N][N][L];

void init() {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + (grid[i-1][j-1] == '#');
    }
  }
  for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) for (int l = 0; l < L; l++) dp[i][j][k][l] = -3;
}

inline bool mono(int b, int t, int l, int r) {
  int area = pref[t+1][r+1] - pref[b][r+1] - pref[t+1][l] + pref[b][l];
  return area == 0 || area == (r-l+1)*(t-b+1);
}

int solve(int b, int t, int l, int k) {
  if (l < 0) return -2;
  if (l >= m) return m-1;
  if (dp[b][t][l][k] != -3) return dp[b][t][l][k];
  if (k == 0) {
    int lb = l, rb = m-1, ans = -1;
    while (lb <= rb) {
      int mid = (lb+rb)/2;
      if (mono(b, t, l, mid)) {
        ans = mid;
        lb = mid+1;
      } else rb = mid-1;
    }
    return dp[b][t][l][k] = ans;
  }
  int ans = solve(b, t, solve(b, t, l, k-1)+1, k-1);
  if (b < t) {
    int lb = b, rb = t-1, bsplit = t-1;
    while (lb <= rb) {
      int mid = (lb+rb)/2;
      ans = max(ans, min(solve(b, mid, l, k-1), solve(mid+1, t, l, k-1)));
      if (solve(b, mid, l, k-1) >= solve(mid+1, t, l, k-1)) {
        bsplit = mid;
        lb = mid+1;
      } else rb = mid-1;
    }
    ans = max(ans, min(solve(b, bsplit, l, k-1), solve(bsplit+1, t, l, k-1)));
    if (bsplit < t-1) {
      bsplit++;
      ans = max(ans, min(solve(b, bsplit, l, k-1), solve(bsplit+1, t, l, k-1)));
      bsplit--;
    }
    if (bsplit > b) {
      bsplit--;
      ans = max(ans, min(solve(b, bsplit, l, k-1), solve(bsplit+1, t, l, k-1)));
    }
  }
  return dp[b][t][l][k] = ans;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> grid[i];
  }
  init();
  for (int k = 0; k < L; k++) {
    if (solve(0, n-1, 0, k) >= m-1) {
      cout << k << nl;
      return 0;
    }
  }
  cout << L << nl;
  return 0;
}



Measured memory_bytes: 214144
#include <iostream>
#include <algorithm>
#include <map>
#include <string>

using namespace std;
 
int main(void){
	
	int N, min, count1, count2;
	
	cin >> N;
	
	int W[N];
	
	for(int i=0; i<N; i++){
		cin >> W[i];
	}
	
	min = 100000000;
	
	for(int i=0; i<N; i++){
		count1 = 0;
		count2 = 0;
		for(int j=0; j<=i; j++){
			count1 += W[j];
		}
		for(int j=i+1; j<N; j++){
			count2 += W[j];
		}
		
		if(count1 > count2){
			if((count1-count2) < min)
				min = count1-count2;
		}else{
			if((count2-count1) < min)
				min = count2-count1;
		}
	}
	
	cout << min;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int N, M;

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

    int p[M];
    string S[M];
    for(int i=0; i<M; i++){
        cin >> p[i] >> S[i];
    }

    int A[N], W[N], fl[N];

    for(int i=0; i<N; i++){
        A[i] = 0;
        W[i] = 0;
    }

    for(int i=0; i<M; i++){
        if(S[i] == "AC"){
            A[p[i]-1] = 1;
        }else if(S[i] == "WA" && A[p[i]-1] == 0){
            W[p[i]-1]++;
        }
    }

    int wsum = 0;
    int asum = 0;
    for(int i=0; i<N; i++){
        asum += A[i];
        if(A[i] == 1) wsum += W[i];
    }

    cout << asum << " " << wsum;

    return 0;
}

Measured memory_bytes: 6912
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
using namespace std;



int main()
{
	int a, b;
	cin >> a >> b;
	int x[1000000];
	for (int i = 0; i < a; i++)
	{
		cin >> x[i];
	}

	vector<int> anss(a - b + 1);
	for (int i = 0; i < a - b + 1; i++)
	{
		if (x[i] >= 0)
		{
			anss.at(i) = abs(x[i + b - 1]);

		}
		else if (x[i + b - 1] <= 0)
		{
			anss.at(i) = abs(x[i]);

		}
		else
		{
			int p = min(abs(x[i]), abs(x[i + b - 1]));
			int q = max(abs(x[i]), abs(x[i + b - 1]));
			anss.at(i) = p * 2 + q;

		}

	}
	sort(anss.begin(), anss.end());
	cout << anss.at(0) << endl;

}

Measured memory_bytes: 2560
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using Pair = pair<int64_t, int64_t>;

// std::cout << std::setprecision(20) << 1.1 << endl;

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

  string s, t;
  cin >> s >> t;
  vector<int32_t> s_array(s.length());
  vector<int32_t> t_array(t.length());
  for (int32_t i = 0; i < static_cast<int32_t>(s.length()); ++i) {
    s_array[i] = static_cast<int32_t>(s.c_str()[i]);
  }
  for (int32_t i = 0; i < static_cast<int32_t>(t.length()); ++i) {
    t_array[i] = static_cast<int32_t>(t.c_str()[i]);
  }
  sort(s_array.begin(), s_array.end());
  sort(t_array.begin(), t_array.end());
  reverse(t_array.begin(), t_array.end());
  bool is_okay = false;
  for (int32_t i = 0; i < max(static_cast<int32_t>(s_array.size()), static_cast<int32_t>(t_array.size())); ++i) {
    if (i >= static_cast<int32_t>(s_array.size())) {
      is_okay = true;
      break;
    } else if (i >= static_cast<int32_t>(t_array.size())) {
      is_okay = false;
      break;
    } else if (s_array[i] < t_array[i]) {
      is_okay = true;
      break;
    } else if (s_array[i] == t_array[i]) {
      // DO NOTHING
    } else {
      is_okay = false;
      break;
    }
  }
  if (is_okay) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif

struct Graph{
    struct Edge{
        int cost, dest;
        Edge(int cost, int dest): cost(cost), dest(dest){ }
        ostream& operator >> (ostream& out){
            return out << '(' << cost << ':' << dest << ')';
        }
    };
    struct Node{
        vector<Edge> edges;
        ll height = 0;
    };
    vector<Node> nodes;
    Graph(int num): nodes(num){ }
    // vector<Edge> edges;
    // Graph(int nn, int en = 10): nodes(nn){
    //     edges.reserve(en);
    // }
    // void addEdge(int from, int dest, ll cost = 1){
    //     nodes[from].outEdges.emplace_back(edges.size());
    //     edges.emplace_back(from, dest, limit);
    // }
    void addEdge(int from, int dest, int cost = 1){
        nodes[from].edges.emplace_back(cost, dest);
    }
    void addEdge2(int from, int dest, int cost = 1){
        addEdge(from, dest, cost);
        addEdge(dest, from, cost);
    }
    void dfs(int idx, ll height, int from = -1){
        nodes[idx].height = height;
        for(auto& e : nodes[idx].edges){
            if(e.dest == from){ continue; }
            dfs(e.dest, height + e.cost, idx);
        }
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    Graph g(n);
    for(int i = 0; i < n - 1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g.addEdge2(a, b, c);
    }
    int q, k;
    cin >> q >> k;
    k--;
    g.dfs(k, 0);
    for(int i = 0; i < q; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        cout << g.nodes[x].height + g.nodes[y].height << '\n';
    }
}


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

#define N 100000

int n;
int p[N];

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

	int ans = 0;
	for( int i = 0; i < n; i++ ) {
		int pp = p[i] - 1;
		if( pp == i ) {
			if( i < n - 1 ) {
				int pp1 = p[i + 1] - 1;
				if( pp1 != i ) {
					swap( p[i], p[i + 1] );
					ans++;
				}
				else if( i > 0 ) {
					int pp2 = p[i - 1] - 1;
					if( pp2 != i ) {
						swap( p[i], p[i - 1] );
						ans++;
					}
				}
			}
			else if( i > 0 ) {
				int pp2 = p[i - 1] - 1;
				if( pp2 != i ) {
					swap( p[i], p[i - 1] );
					ans++;
				}
			}
			
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
struct Card{
    char c,n;
};
void BubbleSort(struct Card *A,int N){
    int i,j;
    struct Card v;
    for(i=0;i<N-1;i++){
        for(j=N-1;j>i;j--){
            if(A[j].n < A[j-1].n){
                v = A[j];
                A[j] = A[j-1];
                A[j-1] = v;
            }
        }
    }
}
void SelectionSort(struct Card *A,int N){
    int i,j,min;
    struct Card v;
    for(i=0;i<N;i++){
        min = i;
        for(j=i;j<N;j++){
            if(A[min].n > A[j].n){
                min = j;
            }
        }
        v = A[min];
        A[min] = A[i];
        A[i] = v;
    }
}
void print(struct Card *A,int N){
    int i;
    for(i=0;i<N;i++){
        if(i>0) printf(" ");
        printf("%c%c",A[i].c,A[i].n);
    }
    printf("\n");
}
int isStable(struct Card *A1,struct Card *A2,int N){
    int i;
    for(i=0;i<N;i++){
        if(A1[i].c != A2[i].c) return 1;
    }
    return 0;
}
int main(void){
    struct Card C1[100],C2[100];
    int N;
    int i;
    
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf(" %c %c",&C1[i].c,&C1[i].n);
        //printf("%c%c\n",C1[i].c,C1[i].n);
        C2[i] = C1[i];
    }
    BubbleSort(C1,N);
    SelectionSort(C2,N);
    
    print(C1,N);
    printf("Stable\n");
    print(C2,N);
    if(isStable(C1,C2,N) == 1){
        printf("Not stable\n");
    }else printf("Stable\n");
    return 0;
}



Measured memory_bytes: 2104
// 线段树区间修改，区间查询

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200010, mod = 998244353;

struct SegmentTree
{
    LL sum, lz;
}tr[N << 2];

LL s[N], ten[N];
int n, q;

void pushup(int p, int l, int r)
{
    int mid = l + r >> 1;
    tr[p].sum = (tr[p << 1].sum * ten[r - mid] % mod + tr[p << 1 | 1].sum) % mod;
}

void build(int p, int l, int r)
{
    if (l == r)
    {
        tr[p].sum = 1;
        return;
    }   

    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);

    pushup(p, l, r);
}

void pushdown(int p, int l, int r)
{
    if (tr[p].lz)
    {
        int mid = l + r >> 1;
        tr[p << 1].sum = s[mid - l + 1] * tr[p].lz % mod;
        tr[p << 1 | 1].sum = s[r - mid] * tr[p].lz % mod;
        tr[p << 1].lz = tr[p].lz;
        tr[p << 1 | 1].lz = tr[p].lz;
        tr[p].lz = 0;
    }
}

void update(int p, int l, int r, int L, int R, int d)
{
    if (L <= l && R >= r)
    {
        tr[p].sum = s[r - l + 1] * d % mod;
        tr[p].lz = d;
        return;
    }

    int mid = l + r >> 1;
    pushdown(p, l, r);

    if (L <= mid) update(p << 1, l, mid, L, R, d);
    if (R > mid) update(p << 1 | 1, mid + 1, r, L, R, d);

    pushup(p, l, r);
}

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

    s[1] = ten[0] = 1, ten[1] = 10;
    for (int i = 2; i <= n; i ++ )
    {
        s[i] = (s[i - 1] + ten[i - 1]) % mod;
        ten[i] = ten[i - 1] * 10 % mod;
    }

    build(1, 1, n);

    while (q --)
    {
        int l, r, d;
        scanf("%d%d%d", &l, &r, &d);
        update(1, 1, n, l, r, d);

        printf("%lld\n", tr[1].sum);
    }

    return 0;
}

Measured memory_bytes: 15076
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=LI()

  a=l[0]
  for x in l[1:]:
    a=a^x

  if a==0:
    return 'Yes'
  return 'No'

# main()
print(main())


Measured memory_bytes: 16616
#include <iostream>
#include <string>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<math.h>
#include<stack>
#include<set>
#include<map>
#define INF 2e9
#define rep(i,n,m) for(int i=n;i<m;i++)

using namespace std;

vector<long long int>Ans;
int main()
{
	int N, m = 0;
	long long int x;
	cin >> N;
	vector<long long int>a(N);
	vector<bool>value_flag(33,0);
	vector<bool>v(33,0);
	rep(i, 0, N) {
		cin >> a[i];
		x = a[i];
		int j = 0;
		while (x) {
			if (x % 2) {
				if (value_flag[j] == false)value_flag[j] = true;
				else value_flag[j] = false;
			}
			x = (x - x % 2) / 2;
			j++;
		}
		m = max(m, j);
	}

	rep(i, 0, N) {
		int j = 0;
		long long int ans = 0;
		vector<bool>v(33, 0);
		rep(k, 0, m)v[k] = value_flag[k];
		while (a[i]) {
			if (a[i] % 2) {
				if (v[j] == false)v[j] = true;
				else v[j] = false;
			}
			a[i] = (a[i] - a[i] % 2) / 2;
			j++;
		}
		rep(k, 0, m)ans += v[k] * (1 << k);
		cout << ans << endl;
	}
}

Measured memory_bytes: 4776
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<=int(b);++i)
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
int INF=numeric_limits<int>::max();
// for(int j=0;j<N;++j) {

int main(void) {
  int n,k;cin>>n>>k;
  int r,s,p;cin>>r>>s>>p;
  string t;cin>>t;
  vector<bool> win(n+10,true);

  ll ans=0;
  rep(i,0,n-1) {
    if(t[i]=='r') {
      ans+=p;
    } else if(t[i]=='s') {
      ans+=r;
    } else {
      ans+=s;
    }
  }
  rep(i,k,n-1) {
    // pr(t[i-k],t[i]);
    if(t[i-k] == t[i] && win[i-k]) {
      win[i] = false;
      if(t[i]=='r') {
        ans-=p;
      } else if(t[i]=='s') {
        ans-=r;
      } else {
        ans-=s;
      }
    }
  }
  pr(ans);
  return 0;
}


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

int result[45];

int fib(int n){
    if(n == 0 || n == 1)return result[n] = 1;
    if(result[n] != -1) return result[n];
    return result[n] = fib(n - 1) + fib(n - 2);
}

int main(){
    int n;
    for(int i = 0;i < 45;++i){
        result[i] = -1;
    }
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}


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

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

  int count = 0;
  if(A%2 == B%2 && A%2 == C%2){
  } else if(A%2 == B%2){
    A += 1;
    B += 1;
    count += 1;
  } else if(A%2 == C%2){
    A += 1;
    C += 1;
    count += 1;
  } else{
    B += 1;
    C += 1;
    count += 1;
  }
  int max1 = max({A,B,C});

  count += (max1-A)/2 + (max1-B)/2 + (max1-C)/2;
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Contest.D
{
	class Program
	{
		public static void Main(string[] args)
		{
			var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
			Console.SetOut(sw);

			Scanner cin = new Scanner();

			int n = cin.nextInt();
			long k = cin.nextLong();
			int[] a = cin.ArrayInt(n);
			long[] visitedTime = Enumerable.Repeat<long>(-1, n).ToArray();

			long t = 0;
			visitedTime[0] = 0;
			int now = 0;
			while (true)
			{
				t++;
				now = a[now] - 1;
				if (visitedTime[now] == -1)
				{
					visitedTime[now] = t;
				}
				else break;
			}
			long p = visitedTime[now];
			int ans;
			if (k <= p) ans = Array.IndexOf(visitedTime, k) + 1;
			else ans = Array.IndexOf(visitedTime, (k - p) % (t - p) + p) + 1;
			Console.WriteLine(ans);

			Console.Out.Flush();
		}
	}

	class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

		public Scanner()
		{
			s = new string[0];
			i = 0;
		}

		public string next()
		{
			if (i < s.Length) return s[i++];
			string st = Console.ReadLine();
			while (st == "") st = Console.ReadLine();
			s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
			if (s.Length == 0) return next();
			i = 0;
			return s[i++];
		}

		public int nextInt()
		{
			return int.Parse(next());
		}

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextInt() + add;
			}
			return Array;
		}

		public long nextLong()
		{
			return long.Parse(next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextLong() + add;
			}
			return Array;
		}

		public double nextDouble()
		{
			return double.Parse(next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextDouble() + add;
			}
			return Array;
		}
	}
}

Measured memory_bytes: 44540
import sys
from collections import Counter, defaultdict, deque
readline = sys.stdin.readline

MOD = 998244353
def calc():
    N, M = map(int, readline().split())
    D = Counter()
    Grid = defaultdict(lambda: -1)
    flag = True
    geta = N
    co = 0
    for _ in range(M):
        a, b, c = map(int, readline().split())
        a -= 1
        b -= 1
        
        if abs(b - a) >= 3:
            if a > b:
                a, b = b, a
            if (a, b) in D:
                if D[(a, b)] != c:
                    flag = False
            else:
                D[(a, b)] = c
                co += 1
        else:
            Grid[a*geta+b] = c
    
    if not flag:
        return 0
        
    for i in range(N-2):
        g = Grid[(i+1)*geta+(i+1)]
        g1 = Grid[i*geta+(i+2)]
        g2 = Grid[(i+2)*geta+i]
        if g1 == -1 or g2 == -1:
            continue
        if g != -1:
            if (g1 == g2) == g:
                return 0
        else:
            Grid[(i+1)*geta+(i+1)] = int(g1 != g2)
    

    
    Edge = [[] for _ in range(N)]
    for i in range(N-1):
        g1 = Grid[(i+1)*geta+i]
        g2 = Grid[i*geta+(i+1)]
        if g1 == -1 or g2 == -1:
            continue
        
        k = int(g1 != g2)
        Edge[i].append((i+1, k))
        Edge[i+1].append((i, k))
    
    Diag = [None]*N
    Q = []
    for i in range(N):
        if Grid[i*geta+i] != -1:
            Diag[i] = Grid[i*geta+i]
            Q.append(i)
    
    
    Q = deque(Q)
    while Q:
        vn = Q.pop()
        for vf, k in Edge[vn]:
            if Diag[vf] is None:
                Diag[vf] = k^Diag[vn]
                Q.appendleft(vf)
            else:
                if Diag[vf] != k^Diag[vn]:
                    return 0
    
    
    jj = set()
    for vn in range(N):
        for vf, k in Edge[vn]:
            if Diag[vn] is None:
                jj.add((min(vn, vf), max(vn, vf)))
    
    co += len(jj)
    co += N - Diag.count(None)
    used = set()
    
    for i in range(N-1):
        if Grid[i*geta + (i+1)] != -1:
            used.add((i, i+1))
        if Grid[(i+1)*geta + i] != -1:
            used.add((i, i+1))
    
    for i in range(N-2):
        if Grid[i*geta + (i+2)] != -1:
            used.add((i, i+2))
        if Grid[(i+2)*geta + i] != -1:
            used.add((i, i+2))
    
    co += len(used)
    return pow(2, N*(N+1)//2 - co, MOD)

print(calc())
                    
            


Measured memory_bytes: 108508
var
    n,cnt_m,cnt_a,cnt_r,cnt_c,cnt_h,ans,i: Int64;
    s: String;
begin
    readln(n);
    for i := 1 to n do
    begin
        readln(s);
        if s[1]='M' then 
        begin
            inc(cnt_m);
        end
        else if s[1]='A' then 
        begin
            inc(cnt_a);
        end
        else if s[1]='R' then 
        begin
            inc(cnt_r);
        end
        else if s[1]='C' then 
        begin
            inc(cnt_c);
        end
        else if s[1]='H' then 
        begin
            inc(cnt_h);
        end;
    end;
    ans:=cnt_m*cnt_a*(cnt_r+cnt_c+cnt_h)+cnt_m*cnt_r*(cnt_c+cnt_h)+
    cnt_m*cnt_c*cnt_h+cnt_a*cnt_r*(cnt_c+cnt_h)+cnt_a*cnt_c*cnt_h+
    cnt_r*cnt_c*cnt_h;
    writeln(ans);
end.

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

int main(){
int N;
int R;
cin>>N>>R;
if(N>=11&&N<=100&&R>=0&&R<=4111)
{
cout<<R<<endl;
}
else if(N<=10&&N>=1&&R>=0&&R<=4111)
{
cout<<R+(100*(10-N))<<endl;
}
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    // task has <deadline,cost> and will be sorted by deadline
    vector<pair<long,long>> tasks(n);
    for(int i=0;i<n;i++){
        long deadline, cost;
        cin >> cost>> deadline;
        tasks[i]=make_pair(deadline,cost);
    }
    sort(tasks.begin(),tasks.end());
    long cum=0;
    for(auto i = tasks.begin();i != tasks.end();i++){
        cum+=i->second;
        //cout << " deadline " << i->first << " cost " << i->second << " cum " << cum << endl;
        if(cum > i->first) {cout << "No" << endl; return 0;}
    }
    cout << "Yes" <<endl;
    return 0;
}

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

int main()
{
  ll p = 2019;
  string s; cin >> s;
  ll n = s.size();

  if (10%p == 0) {
    ll ans = 0;
    rep(i, n) {
      if ((s[i]-'0')%p == 0) ans += i+1;
    }
    cout << ans << endl;
    return 0;
  }

  ll ten = 1;
  vector<ll> c(n+1, 0);
  for (int i=n-1; i>=0; i--) {
    ll t = s[i]-'0';
    ll u = t * ten % p;
    c[i] = (c[i+1]+u) % p;
    ten = (ten*10) % p;
  }
  map<ll, ll> mp;
  mp[0]++;
  ll ans = 0;
  for (int i=n-1; i>=0; i--) {
    ans += mp[c[i]];
    mp[c[i]]++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 5124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define UM unordered_map
#define ALL(a) (a).begin(), (a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll, ll> pii;
const ll INF = 1LL << 58;
const ll MOD = 1000000007;
typedef vector<pii> vpii;
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;
}

signed main()
{
    int A, P;
    cin >> A >> P;
    cout << (A * 3 + P) / 2 << endl;

    // system("pause");
}

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

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

int main() {
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;

	string s;
	cin >> s;
	
	int total_w = 0;
	for(auto &each : s) {
		total_w += each == 'W';
	}

	int ans = 1 << 30;
	int e = 0, w = 0;
	fori(i, 0, n) {
		w += s[i] == 'W';

		ans = min(ans, (i - e) + (n - i - 1 - (total_w - w)));

		e += s[i] == 'E';
	}
	
	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 720
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()

#define pb push_back
#define mp make_pair

#define F first
#define S second

using ll = long long;
using namespace std;

void chmin(ll &a, ll b) { if (a > b) a = b; }
void chmax(ll &a, ll b) { if (a < b) a = b; }

const int mod = 1000000007;
const int INF = 1e+9;

int factoring (int n, int cnt) {
    if (n % 2 != 0 || n == 0) return cnt;
    n /= 2;
    cnt++;
    return factoring(n, cnt);
}

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

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] % 2 != 0 || a[i] == 0) continue;
            int c = factoring(a[i], 0);
            ans += c;
            cerr << a[i] << endl;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
long long gcd(long long a,long long b){return b == 0 ? a : gcd(b, a % b);}
long long lcm(long long a,long long b){return a / gcd(a, b) * b;}
int main(){
    long long a, b;
    scanf("%lld%lld",&a,&b);
    printf("%lld\n",lcm(a, b));
    return 0;
}

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

#define ONLINE_JUDGE
#define ll long long
#define PI 3.14159265359
#define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
#define pb(a) push_back(a)

//////////// Solution /////////////////////////////////
const int MAX = 1e5+1;
int sums[MAX]={};

void solve() {
	int n,q;
	cin >> n >> q;
	string s;
	cin >> s;
	int len = (int)s.length();
	int cnt = 0;
	for (int i = 1; i < len; ++i) {
		if (s[i] == 'C' && s[i-1] == 'A') {
			++cnt;
		}
		sums[i+1] = cnt;
	}

	for (int i = 0; i < q; ++i) {
		int l,r;
		cin >> l >> r;
		cout << sums[r] - sums[l] << '\n';
	}
}	

/////////// End Solution ///////////////////////////////////////

//////// Initialization ////////////////////////////////////

int main() {

	#ifndef ONLINE_JUDGE
	FILE *FIN = freopen("/home/danil/prog/input.txt", "r", stdin);
	clock_t time_start = clock();
	#endif

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	solve();

	#ifndef ONLINE_JUDGE
	fclose(FIN);
	cerr << "\x1b[031m\n-----------------\nTime=" << (ll)((double)(clock()-time_start) / CLOCKS_PER_SEC * 1000) << "ms\n\x1b[0m";
	#endif

	return 0;
}

//////// End Initialization ///////////////////////////////////////

Measured memory_bytes: 1488