akhauriyash/Code-Regression huggingface dataset:
# frozen_string_literal: true

MOD = 998244353
n = gets.to_i
d = gets.split.map(&:to_i)

unless d[0].zero?
  puts 0
  exit
end
h = Array.new(n) { 0 }
d.each do |i|
  h[i] += 1
end
if h[0] != 1
  puts 0
  exit
end
sum = 1
flag = false
1.upto(n - 1) do |i|
  if h[i].zero? && !flag
    flag = true
    next
  end
  if flag
    unless h[i].zero?
      puts 0
      exit
    end
  else
    sum *= h[i - 1]**h[i]
    sum %= MOD
  end
end

puts sum % MOD


Measured memory_bytes: 9484
#include<iostream>

using namespace std;

typedef long long int lld;

lld n, c, x[100000], v[100000], cw[100001], ccw[100001], mcw[100001], mccw[100001], rst;

int main() {
    cin >> n >> c;
    for(int i = 0; i < n; i++)
        cin >> x[i] >> v[i];
    
    for(int i = 1; i <= n; i++) {
        cw[i] = cw[i-1] + v[i-1];
        ccw[i] = ccw[i-1] + v[n-i];
    }
    for(int i = 1; i <= n; i++) {
        cw[i] -= x[i-1];
        ccw[i] -= c - x[n-i];
    }
    
    for(int i = 1; i <= n; i++) {
        mcw[i] = max(mcw[i-1], cw[i]);
        mccw[i] = max(mccw[i-1], ccw[i]);
        //cout << mcw[i] << ' ' << mccw[i] << endl;
    }
    
    rst = max((lld)0, max(mcw[n], mccw[n]));
    //cout << rst << endl;
    
    for(int i = 1; i <= n; i++) {
        rst = max(rst, mccw[n-i] + cw[i] - x[i-1]);
        //cout << mccw[n-i] + cw[i] - x[i-1] << ' ';
        rst = max(rst, mcw[n-i] + ccw[i] - c + x[n-i]);
        //cout << mcw[n-i] + ccw[i] - c + x[n-i] << endl;
    }
    cout << rst;
    return 0;
}

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

long long mid(long long a, long long b, long long c){
	return a + b + c - max(max(a, b), c) - min(min(a, b), c);
}

int main(){
	int N;
	string S, T;
	cin >> N >> S >> T;
	int ans = N * 2;
	for(int i = 0; i < N; i++){
		string s = S.substr(i, N - i);
		string t = T.substr(0, N - i);
		if(s == t){
			ans = N + i;
			break;
		}
	}
	
	cout << ans << endl;
}

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

using i8  = int8_t;   /* -128 ~ 127 */
using u8  = uint8_t;  /* 0 ~ 255 */
using i16 = int16_t;  /* -32,768 ~ 32,767 */
using u16 = uint16_t; /* 0 ~ 65,535 */
using i32 = int32_t;  /* -2,147,483,648 ~ 2,147,483,647 */
using u32 = uint32_t; /* 0 ~ 4,294,967,295 */
using i64 = int64_t;  /* -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 */
using u64 = uint64_t; /* 0 ~ 18,446,744,073,709,551,615 */
using f32 = float;    /* (-3.4 * 10^38) ~ (3.4 * 10^38) */
using f64 = double;   /* (-1.7 * 10^308) ~ (1.7 * 10^308) */
using f80 = __float80;
template <class T> using Vec = vector<T>;
constexpr i64 INF = 1010000000000000017;
constexpr i64 MOD = 1e9 + 7;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define ALL(v) v.begin(), v.end()
#define YN(a, b, c) ((c)? a : b)
#define GCD(a, b) __gcd(a, b) /* 最大公約数 */
#define LCM(a, b) (i64)(a / (f64)__gcd(a, b) * b) /* 最小公倍数 */

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

void Main() {
    i32 N, K;
    cin >> N >> K;
    Vec<i32> A(N);
    for (i32 i = 0; i < N; i++) cin >> A[i];
    if (K == N) {
        cout << 1 << endl;
        return;
    }
    i32 index = distance(A.begin(), min_element(ALL(A)));
    i32 min_v = 1000001;
    i32 a1 = 0;
    i32 i = 0;
    while (i + K <= index) {
        a1++;
        i += K - 1;
    }
    i += K;
    a1++;
    while (i < N) {
        i += K - 1;
        a1++;
    }
    i32 a2 = 0;
    i = N - 1;
    while (i - K >= index) {
        a2++;
        i -= K - 1;
    }
    i -= K;
    while (i >= 0) {
        i -= K - 1;
        a2++;
    }
    cout << a1 << endl;
}


Measured memory_bytes: 3612
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
#include <string.h>
using namespace std;

int main()
{
  int n = 0;
  scanf("%d", &n);
  vector<double> p(n, 0); 
  for(int i=0; i<n; i++){
    scanf("%lf", &p[i]);
  }
  vector<double> arr((n+1) * n, 0);
  arr[0] = 1 - p[0];
  for(int m=1; m<n+1; m++){
    arr[m] = arr[m-1] * (1 - p[m]);
  }
  arr[n] = p[0];
  for(int m=1; m<n; m++){
    for(int k=1; k<m+2; k++){
      arr[k*n + m] = p[m] * arr[(k-1)*n + m - 1] + (1 - p[m]) * arr[k*n + m - 1];
    }
  }
  //for(int m=0; m<n; m++){
  //  for(int k=0; k<n+1; k++){
  //    printf("%lf ", arr[k*n+m]);
  //  }
  //  printf("\n");
  //}
  double result = 0;
  for (int k=n/2 + 1; k<n+1; k++){
    result += arr[k*n + n - 1];
  }
  printf("%.10lf\n", result);
}


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

typedef long long int ll ;
ll strToInt(string s1,string s2)
{
    string s3 = s1+s2 ;
    ll res = 0 ;
    stringstream ss(s3) ;
    ss >> res ;
    return res ;
}
int main()
{
    string a,b ;
    cin >> a >> b ;
    ll tmp = strToInt(a,b);
    if(int(sqrt(tmp)) == sqrt(tmp))
    {
        cout << "Yes\n";
    }
    else
        cout <<"No\n";

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int a[100009],dp[100009];
int min(int c,int v){
	if(c>=v) return v;
	else return c;
}
int dif(int c,int v){
	if(c>=v) return(c-v);
	else return(v-c);
}
int main() {
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int i=0;i<n;i++) dp[i]=1000000009;
	dp[0]=0;
	for(int i=1;i<n;i++){
		for(int j=i-1;j>=i-k && j>=0;j--){
			dp[i]=min(dp[i],dp[j]+dif(a[i],a[j]));
		}
	}
	printf("%d\n",dp[n-1]);
}


Measured memory_bytes: 896
from bisect import bisect_left


def main():
    N, Q, *I = map(int, open(0).read().split())
    STX, D = I[:3 * N], I[3 * N:]

    E = sorted(zip(*[iter(STX)] * 3), key=lambda x: x[2])

    R = [-1] * Q
    ans = [-1] * Q

    for s, t, x in E:
        l = bisect_left(D, s - x)
        r = bisect_left(D, t - x)
        while l < r:
            if R[l] == -1:
                ans[l] = x
                R[l] = r
                l += 1
            else:
                l = R[l]

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


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

using namespace std;

int main() {
    int H, W, A, B;
    cin >> H >> W >> A >> B;
    int ans_h = -1;
    int ans_w = -1;
    for (int i = 0; i <= H; i++) {
        int sum1 = A * i + (W - A) * (H - i);
        for (int j = 0; j <= W; j++) {
            int sum2 = B * j + (H - B) * (W - j);
            if (sum1 == sum2) {
                ans_h = i;
                ans_w = j;
                break;
            }
        }
        if (ans_h >= 0) {
            break;
        }
    }
    if (ans_h == -1 or ans_w == -1) {
        cout << "No" << endl;
        return 0;
    }
    vector<int> cnt_h(H);
    vector<int> cnt_w(W);
    for (int i = 0; i < H; i++) {
        int max_h = i < ans_h ? A : W - A;
        for (int j = 0; j < W; j++) {
            int max_w = j < ans_w ? B : H - B;
            if (cnt_h.at(i) < max_h and cnt_w.at(j) < max_w) {
                cout << "1";
                cnt_h.at(i)++;
                cnt_w.at(j)++;
            } else {
                cout << "0";
            }
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> P;
double eps=1e-10;

double Sqrt(double x){
  return sqrt(max(0.0,x));
}

struct S{
  P p,q;
  S(P p,P q):p(p),q(q){}
};

struct C{
  P p;
  double r;
  C(P p,double r):p(p),r(r){}
  C(double x,double y,double r):p(P(x,y)),r(r){}
};

vector<P> getCrossPoint(C a,C b){
  vector<P> res;
  P base=b.p-a.p;
  double dist=abs(base);
  if(dist>a.r+b.r+eps)return res;
  if(dist<abs(a.r-b.r)-eps)return res;
  double ca = (a.r*a.r+dist*dist-b.r*b.r) / (2.0*a.r*dist);
  double sa = Sqrt(1.0-ca*ca);
  P fi=a.p+base/dist*a.r*P(ca,sa);
  P se=a.p+base/dist*a.r*P(ca,-sa);
  res.push_back(fi);
  res.push_back(se);
  return res;
}

vector<P> getCrossPoint(C a,S b){
  vector<P> res;
  P base=b.q-b.p;
  P v=a.p-b.p;
  P target=b.p+base*real(v/base);
  double h=abs(a.p-target);
  if(a.r+eps<h)return res;
  
  double w=Sqrt(a.r*a.r-h*h);
  double L=abs(b.p-target)-w;
  double R=abs(b.p-target)+w;
  
  if( -eps<L && L<abs(base)+eps )
    res.push_back(b.p+base/abs(base)*L);

  if( -eps<R && R<abs(base)+eps )
    res.push_back(b.p+base/abs(base)*R);
  
  return res;
}

int n,w;
int px[10],py[10],h[10];
vector<C> vec;

double calc(double r,double t){
  if(r<t)return r;
  return Sqrt( r*r - (r-t)*(r-t) );
}

bool check(P p,double r){
  double a=calc(r,w)-eps;
  double b=100-calc(r,w)+eps;
  if(p.real()<a)return false;
  if(p.real()>b)return false;
  if(p.imag()<a)return false;
  if(p.imag()>b)return false;

  for(int i=0;i<n;i++)
    if( abs(p-vec[i].p) < vec[i].r-eps )return false;

  return true;
}

bool check(vector<P> v,double r){
  for(int i=0;i<(int)v.size();i++)
    if( check(v[i],r) )return true;
  return false;
}

bool check(double r){

  vec.clear();
  for(int i=0;i<n;i++){
    vec.push_back( C( px[i], py[i], calc(r,h[i]) ) );
  }
  
  
  double a=calc(r,w);
  double b=100-calc(r,w);

  P pa=P(a,a),pb=P(b,a),pc=P(b,b),pd=P(a,b);
  if(check(pa,r))return true;
  if(check(pb,r))return true;
  if(check(pc,r))return true;
  if(check(pd,r))return true;

  
  
  for(int i=0;i<n;i++){
    vector<P> tmp1=getCrossPoint(vec[i],S(pa,pb));
    vector<P> tmp2=getCrossPoint(vec[i],S(pb,pc));
    vector<P> tmp3=getCrossPoint(vec[i],S(pc,pd));
    vector<P> tmp4=getCrossPoint(vec[i],S(pd,pa));
    if(check(tmp1,r))return true;
    if(check(tmp2,r))return true;
    if(check(tmp3,r))return true;
    if(check(tmp4,r))return true;
    for(int j=0;j<i;j++){
      vector<P> tmp0=getCrossPoint(vec[i],vec[j]);
      if(check(tmp0,r))return true;
    }
  }
  return false;
}

int main(){
  while(1){
    cin>>n>>w;
    if(n==0&&w==0)break;
    for(int i=0;i<n;i++)cin>>px[i]>>py[i]>>h[i];
    double l=0,r=100000,m;
    for(int i=0;i<100;i++){
      m=(l+r)/2.0;
      if(check(m))l=m;
      else r=m;
    }
    printf("%.8f\n",m);
  }
  return 0;
}

Measured memory_bytes: 1256
#include<stdio.h>
int main(){
  int a,b;
  char op;
  while(1){
    scanf("%d %c %d", &a, &op, &b);
    if(op=='?')break;
    if(op=='+'){
      printf("%d\n",a+b);
    }
    else if(op=='-'){
      printf("%d\n",a-b);
    }
    else if(op=='*'){
      printf("%d\n",a*b);
    }
    else if(op=='/'){
      printf("%d\n",a/b);
    }
  }
  return 0;
}

Measured memory_bytes: 1808
#include <bits/stdc++.h>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
	int n; cin>>n;
	VL a(n); rep(i,n) cin>>a[i]; sort(RALL(a));
	if(n%2){
		ll ans1=0;
		rep(i,n/2-1) ans1+=a[i]*2;
		ans1+=a[n/2-1]+a[n/2];
		for(int i=n/2+1;i<n;i++) ans1-=a[i]*2;
		ll ans2=0;
		rep(i,n/2) ans2+=a[i]*2;
		ans2-=a[n/2]+a[n/2+1];
		for(int i=n/2+2;i<n;i++) ans2-=a[i]*2;
		cout<<max(ans1,ans2)<<endl;
	}else{
		ll ans=0;
		rep(i,n/2-1) ans+=a[i]*2;
		ans+=a[n/2-1]; ans-=a[n/2];
		for(int i=n/2+1;i<n;i++) ans-=a[i]*2;
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 1024
hitBlow :: Eq a => [a] -> [a] -> (Int,Int)
hitBlow nums guess = (hits, blows) where
    hits = length . filter id $ zipWith (==) nums guess
    blows = subtract hits . length . filter (`elem` nums) $ guess

solve :: [[Int]] -> [(Int,Int)]
solve [] = []
solve [_] = []
solve (n:g:xs) = hitBlow n g : solve xs

main = getContents >>= mapM_ (\(h,b) -> putStrLn $ show h ++ " " ++ show b)
    . solve . map (map read . words) . lines

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

int main() {
  int x1, x2, x3, x4, x5;
  cin >> x1 >> x2 >> x3 >> x4 >> x5;

  if (x1 == 0) {
    cout << 1 << endl;
  }
  if (x2 == 0) {
    cout << 2 << endl;
  }
  if (x3 == 0) {
    cout << 3 << endl;
  }
  if (x4 == 0) {
    cout << 4 << endl;
  }
  if (x5 == 0) {
    cout << 5 << endl;
  }
}

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

int main(){
int N;
cin >>N;
vector<int>data(N);
 for (int i=0;i<N;i++){
 cin >>data.at(i);
 }
  vector<int>data1;
   int s=-1;
  for(int i=0;i<N-1;i++){
    int t;
	if(data.at(i)<data.at(i+1)){
      t=i-s-1;
      s=i; 
      data1.push_back(t);  
    }
    
  }
  data1.push_back(N-s-2);
  sort(data1.begin(),data1.end());
  reverse(data1.begin(),data1.end());
  cout <<data1.at(0)<<endl;
}

Measured memory_bytes: 1276
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    s = S()
    k = 2019
    tens = [1 for _ in range(len(s)+1)]
    for i in range(1, len(s)+1):
        tens[i] = tens[i-1] * 10 % k

    mods0toi = [0 for _ in range(len(s))]
    cur = 0
    for i in range(len(s))[::-1]:
        j = len(s) - i - 1
        mods0toi[i] = (cur + int(s[i]) * tens[j]) % k
        cur = mods0toi[i]
    s = collections.Counter(mods0toi)
    ans = 0
    t = s.keys()
    for c in t:
        if c == 0:
            ans += s[c]
        ans += (s[c]) * (s[c] - 1) // 2
    print(ans)

main()



Measured memory_bytes: 25664
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{

    public static final int FIRST_NUMBER = 0;
    public static final int SECOND_NUMBER = 1;

    public static void main(String[] args) {

	Scanner sc = new Scanner(System.in);
	// ?¨??????\?????¨????????????????£?
	int arrayLength = Integer.parseInt(sc.nextLine());
	int loopCount = Integer.parseInt(sc.nextLine());

	// ?????\???????????????
	int[] outputArray = new int[arrayLength + 1];
	for (int i = 0; i < outputArray.length; i++) {
	    outputArray[i] = i;
	}

	// ??\????????????
	List<int[]> inputArrays = new ArrayList<>();

	for (int i = 0; i < loopCount; i++) {
	    String[] queryStr = sc.nextLine().split(",");
	    int[] query = new int[2];
	    query[FIRST_NUMBER] = Integer.parseInt(queryStr[FIRST_NUMBER]);
	    query[SECOND_NUMBER] = Integer.parseInt(queryStr[SECOND_NUMBER]);
	    inputArrays.add(query);
	}

	// lots???draw?????????????????????outputArray???????´???????
	exchangeLine(inputArrays, outputArray);

	// ?????????????????????
	for (int i = 1; i < outputArray.length; i++) {
	    System.out.println(outputArray[i]);
	}

    }

    private static void exchangeLine(List<int[]> inputArrays, int[] outputArray) {

	for (int[] query : inputArrays) {
	    int mediator = 0;

	    mediator = outputArray[query[FIRST_NUMBER]];
	    outputArray[query[FIRST_NUMBER]] = outputArray[query[SECOND_NUMBER]];
	    outputArray[query[SECOND_NUMBER]] = mediator;

	}

    }
}

Measured memory_bytes: 26116
#include <bits/stdc++.h>
#include <math.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
const int mINF = -1001001001;


int main() {
int a,b,c;
cin >> a >> b;
int ans = a*3+b;
ans /= 2;
cout << ans << endl;
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>

#define REP(i,n) for(int i=0;i<n;++i)
#define RREP(i,n) for(int i=n-1;i>=0;--i)
#define FOR(i,m,n) for(int i=m;i<n;++i)
#define RFOR(i,m,n) for(int i=m-1;i>=n;--i)
#define ALL(v) v.begin(),v.end()
#define pb(a) push_back(a)
#define INF 1000000001
#define MOD 1000000007

using namespace std;



int main() {
	int n, ans = 0;
	cin >> n;
	vector<int> v(2*n);
	REP(i, 2*n) {
		cin >> v[i];
	}
	sort(ALL(v));
	for (int i = 0;i < 2 * n;i += 2) {
		ans += v[i];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <iomanip>
#include <string>
#include <math.h>
#include<set>
#include<stdio.h>
#include <bitset>
#include<string.h>
#define ii int64_t
#define PI 3.14
#define lli long long int
#define li long int
#define deb(x) cout<<"\nhi"<<x<<"\n"
#define mod 1000000007
#define f(x,n) for(int x=0;x<n;++x)
#define ff(x,y,z) for(x=y;x<=z;++x)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// while(scanf("%d",&n)!=EOF)




using namespace std;
 

int main()
 
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    string s,t,ans;
    int64_t i,j,x,y;
    int dp[3004][3004];
    memset(dp, 0, sizeof(dp));
    cin>>s>>t;
    
    
    for(i=1;i<=s.length();i++)
        for(j=1;j<=t.length();j++)
        {
            if(s[i-1]==t[j-1])
                dp[i][j] = dp[i-1][j-1]+1;
            else
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
    

    
    i=s.length();j=t.length();
    while(true)
    {

        if(i>0 && j>0&&s[i-1]==t[j-1])
            {ans +=s [i-1];i--;j--;}
        else if(i>0 && dp[i][j] == dp[i-1][j]) i--;
        else if(j>0 && dp[i][j] == dp[i][j-1]) j--;
        else break;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;
    
    
}





Measured memory_bytes: 35584
import std.stdio, std.string, std.algorithm, std.array, std.range, std.conv,
    std.typecons, std.math, std.container, std.format, std.numeric;

long[] parent;
long[][] children;
long[] depth;
long[][] ancestor_table;

void calc_depth(long i, long d)
{
    depth[i] = d;
    foreach (c; children[i])
    {
        calc_depth(c, d + 1);
    }
}

void make_table(long n, long size)
{
    foreach (i; 0 .. size)
    {
        foreach (j; 0 .. n)
        {
            if (i == 0)
            {
                ancestor_table[j][i] = parent[j];
            }
            else
            {
                auto k = ancestor_table[j][i - 1];
                if (k == -1)
                {
                    ancestor_table[j][i] = -1;
                }
                else
                {
                    ancestor_table[j][i] = ancestor_table[k][i - 1];
                }
            }
        }
    }
}

long get_nth_parent(long p, long n)
{
    long i = 0;
    while (n != 0 && p != -1)
    {
        if (n & 1)
        {
            p = ancestor_table[p][i];
        }
        i++;
        n /= 2;
    }
    return p;
}

long lca(long u, long v, long n)
{
    if (depth[u] > depth[v])
    {
        swap(u, v);
    }

    v = get_nth_parent(v, depth[v] - depth[u]);
    assert(depth[u] == depth[v]);
    // long ok = 0;
    // while (get_nth_parent(u, ok) != get_nth_parent(v, ok))
    // {
    //     ok++;
    // }
    // return get_nth_parent(u, ok);

    long ok = depth[v], ng = -1;
    while (abs(ng - ok) > 1)
    {
        long m = (ok + ng) / 2;
        if (get_nth_parent(u, m) == get_nth_parent(v, m))
        {
            ok = m;
        }
        else
        {
            ng = m;
        }
    }

    return get_nth_parent(v, ok);
}

void main(string[] args)
{
    long n;
    readf("%d\n", &n);
    parent = new long[](n);
    children = new long[][](n);

    parent.fill(-1);
    foreach (i; 0 .. n)
    {
        auto cs = readln.strip.split(" ").to!(long[]);
        foreach (c; cs[1 .. $])
        {
            parent[c] = i;
            children[i] ~= c;
        }
    }

    depth = new long[](n);
    calc_depth(0, 0);

    long size = 0;
    for (long i = 1; i < n; i *= 2)
    {
        size++;
    }

    ancestor_table = new long[][](n, size);
    make_table(n, size);

    long q;
    readf("%d\n", &q);
    long u, v;
    foreach (i; 0 .. q)
    {
        readf("%d %d\n", &u, &v);
        long ans = lca(u, v, n);
        writeln(ans);
    }
}



Measured memory_bytes: 42668
package main

import (
	"fmt"
)

// main is...
func main() {
	// IO start
	var n int
	fmt.Scan(&n)

	var listA = make([]int, n)
	var listB = make([]int, n)
	var listC = make([]int, n-1)
	for i := 0; i < n; i++ {
		fmt.Scan(&listA[i])
	}
	for i := 0; i < n; i++ {
		fmt.Scan(&listB[i])
	}
	for i := 0; i < n-1; i++ {
		fmt.Scan(&listC[i])
	}

	ret := 0
	// process start
	ret += listB[listA[0]-1]
	for i := 1; i < n; i++ {
		value := listA[i] - 1
		ret += listB[value]
		if previous := listA[i-1]; previous == value {
			ret += listC[value-1]
		}
	}
	fmt.Print(ret)
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define PRINT(x) cout<<(x)<<endl
#define INF 1000000000000 // 10^12
#define MOD 1000000007 // 10^9+7
#define PB push_back
#define MP make_pair

ll modpow(ll m, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * m % MOD;
        m = m * m % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    ll m, n; cin >> m >> n;
    ll ans = modpow(m, n);
    PRINT(ans);
    return 0;
}


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

int main() {
  string s;
  cin >> s;
  if( s.at(0) != s.at(1) && s.at(1) != s.at(2) && s.at(2) != s.at(0) ){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import sys
#input = sys.stdin.readline

S = list(input())
T = list(input())

alpha2num = lambda c: ord(c) - ord('a') 

alpha = [[] for _ in range(26)]
for i,s in enumerate(S):
    alpha[alpha2num(s)].append(i)

import bisect
tmp = -1
N = len(S)
base = 0
for t in T:
    a = alpha2num(t)
    if len(alpha[a]) == 0:
        print(-1)
        sys.exit()
    else:
        L = len(alpha[a])        
        num = bisect.bisect_right(alpha[a],tmp)
        
        if num == L:
            base += 1
            tmp = alpha[a][0]
        else:
            tmp = alpha[a][num]
ans = N * base + tmp + 1
print(ans)
        
    


Measured memory_bytes: 9056
#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) x=-x,pc('-');
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;

int main(){
int a=read(),b=read();
puts(a<=8&&b<=8?"Yay!":":(");
}

Measured memory_bytes: 256
N=int(input())
X=list(map(int,input().split()))
a=sum(X)//N
b=sum(X)//N+1
ans1=0
ans2=0

for i in range(N):
  ans1+=(X[i]-a)**2
  ans2+=(X[i]-b)**2
print(min(ans1,ans2))

Measured memory_bytes: 3064
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    int tmp;
    vector<int> nums;
    
    cin >> n;
    
    for(int i = 0;i < n;i++) {
        cin >> tmp;
        nums.push_back(tmp);    
    }
    
    for(int i = nums.size() - 1;i >= 0;i--) {
        cout << nums.at(i);
        
        if(i > 0)
            cout << " ";
    }
    
    cout << endl;

    return 0;
}

Measured memory_bytes: 3140
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var table = new Dictionary<int, int>()
            {
                {9, 1},
                {8, 2},
                {7, 3},
                {6, 4},
                {5, 5},
                {4, 6},
                {3, 7},
                {2, 8},
                {1, 9},
                {0, 0},
            };

            var itemList = new List<int>();
            itemList.Add(int.Parse(Console.ReadLine()));
            itemList.Add(int.Parse(Console.ReadLine()));
            itemList.Add(int.Parse(Console.ReadLine()));
            itemList.Add(int.Parse(Console.ReadLine()));
            itemList.Add(int.Parse(Console.ReadLine()));

            // 注文のロスが一番大きいものを最後にする
            itemList = itemList.OrderBy(elem => table[elem % 10]).ToList();

            int elapsedTime = 0;
            for(int index = 0; index < itemList.Count(); index++)
            {
                // 注文→届く時間
                elapsedTime += itemList[index];

                // 最後なら終了
                if (index == itemList.Count() - 1)
                {
                    break;
                }

                // 次の注文までのロス
                elapsedTime += table[itemList[index] % 10];
            }

            Console.WriteLine(elapsedTime.ToString());
        }
    }
}


Measured memory_bytes: 13396
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
#define pi 3.1415926

int a[(int)2e5][11];

int main(){
    string s;
    cin >> s;
    int br=0, br1=0;
    for(int i = 0; i < 3; i++){
        if(s[i] == 'A')
            br++;
        if(s[i] == 'B')
            br1++;
    }
    if(br == 2 || br1 == 2)
        cout << "Yes";
    else    
        cout << "No";
    

}

    

		


Measured memory_bytes: 256
#include <cstdio>
#include <regex.h>
#include <cstring>

int main() {
  int n;
  regex_t regst[2];
  regmatch_t match[3];
  const char *pattern[] = {"^>'(=+)#(=+)~$", "^>\\^(Q=)+~~$"};
  const char *type_label[] = {"A", "B", "NA"};
  int type;
  char snake[201];
  
  scanf("%d", &n);
  for (int x=0; x<n; x++) {
    scanf("%s", snake);
    type = 2;
    for (int i=0; i<2; i++) {
      regcomp(&regst[i], pattern[i], REG_EXTENDED);
    }
    if (!regexec(&regst[0], snake, 3, match, 0)) {
      if (match[1].rm_eo - match[1].rm_so == match[2].rm_eo - match[2].rm_so) {
        type = 0;
      }
    } else if (!regexec(&regst[1], snake, 0, NULL, 0)) {
      type = 1;
    }
    printf("%s\n", type_label[type]);
  }
  return 0;
}

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

int n, w, d; //??????????????°??????????\\??????

int main(){
	while (cin >> n >> w >> d){
		if (n == 0 && w == 0 && d == 0) break;
		vector<int> cakeW, cakeD, cakeS;
		int p, s;
		cakeW.push_back(w);
		cakeD.push_back(d);
		cakeS.push_back(w*d);
		for (int i = 0; i < n;i++){
			cin >> p >> s;
			--p;
			//?§???????????????¢????¨????
			int w1, w2, d1, d2, s1, s2;
			s = s % (2 * cakeW[p] + 2 * cakeD[p]);
			bool j = true;
			while (1){
				if (s < cakeW[p]) break;
				s -= cakeW[p];
				if (s < cakeD[p]){
					j = false;
					break;
				}
				s -= cakeD[p];
				if (s < cakeW[p]) break;
				s -= cakeW[p];
				j = false;
				break;
			}

			if (j){
				w1 = s;
				d1 = cakeD[p];
				w2 = cakeW[p] - s;
				d2 = cakeD[p];
			}
			else{
				w1 = cakeW[p];
				d1 = s;
				w2 = cakeW[p];
				d2 = cakeD[p] - s;
			}
			s1 = w1 * d1;
			s2 = w2 * d2;
			//??????
			if (s1 < s2){
				cakeW.push_back(w1);
				cakeD.push_back(d1);
				cakeS.push_back(s1);
				cakeW.push_back(w2);
				cakeD.push_back(d2);
				cakeS.push_back(s2);
			}
			else{
				cakeW.push_back(w2);
				cakeD.push_back(d2);
				cakeS.push_back(s2);
				cakeW.push_back(w1);
				cakeD.push_back(d1);
				cakeS.push_back(s1);
			}
			cakeW.erase(cakeW.begin() + p);
			cakeD.erase(cakeD.begin() + p);
			cakeS.erase(cakeS.begin() + p);
		}
		sort(cakeS.begin(),cakeS.end());
		for (int i = 0; i < cakeS.size(); i++){
			if (i != 0) cout << " ";
			cout << cakeS[i];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1224
#include <stdio.h>
int main(void){
    #define PI 3.141592653589793
    double r,s,l;
    
    scanf("%lf",&r);
    s=PI*r*r;
    l=2*PI*r;
    printf("%.6f %.6f",s,l);
    
return 0;
    
}



Measured memory_bytes: 2140
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define rep(x, l, r) for(int x = l; x <= r; x++)
#define repd(x, r, l) for(int x = r; x >= l; x--)
#define clr(x, y) memset(x, y, sizeof(x))
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define MAXN 15
#define fi first
#define se second
#define SZ(x) ((int)x.size())
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int INF = 1 << 30;
const int p = 1000000009;
int lowbit(int x){ return x & (-x);}
int fast_power(int a, int b){ int x; for(x = 1; b; b >>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}

int n;
int tree0[MAXN], tree1[MAXN];

void update0(int x){
	for(int i = x; i <= n; i += lowbit(i)) tree0[i]++;
}

void update1(int x){
	for(int i = x; i <= n; i += lowbit(i)) tree1[i]++;
}

int query0(int x){
	int res = 0;
	for(int i = x; i > 0; i -= lowbit(i)) res += tree0[i];
	return res;
}

int query1(int x){
	int res = 0;
	for(int i = x; i > 0; i -= lowbit(i)) res += tree1[i];
	return res;
}

int main(){
	scanf("%d", &n);
	ll a = 0, b = 0;
	rep(i, 1, n){	
		int x;
		scanf("%d", &x);
		a = a * (n - i + 1) + x - 1 - query0(x);
		update0(x);
	}
	rep(i, 1, n){
		int x;
		scanf("%d", &x);
		b = b * (n - i + 1) + x - 1 - query1(x);
		update1(x);
	}
	printf("%lld\n", abs(a - b));
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  int n,k;
  cin >> n >> k;
  int ans = INF;
  for(int bit=0; bit<(1<<n); bit++){
    int sum = 1;
    rep(i,n){
      if(bit&(1<<i)){
        sum*=2;
      }else{
        sum+=k;
      }
    }
    ans = min(ans,sum);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
static const int MAX = 10000;
static const int INFTY = (1<<20);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n;
vector<pair<int, int> > adj[MAX];  // 重み付き有向グラフの隣接リスト表現

void dijkstra() {
  priority_queue<pair<int, int> > PQ;
  int color[MAX];
  int d[MAX];
  for ( int i = 0; i < n; i++ ) {
    d[i] = INFTY;
    color[i] = WHITE;
  }

  d[0] = 0;
  PQ.push(make_pair(0, 0));
  color[0] = GRAY;

  while ( !PQ.empty() ) {
    pair<int, int> f = PQ.top(); PQ.pop();
    int u = f.second;

    color[u] = BLACK;

    // 最小値を取り出し、それが最短でなければ無視
    if ( d[u] < f.first * (-1) ) continue;

    for ( int j = 0; j < adj[u].size(); j++ ) {
      int v = adj[u][j].first;
      if ( color[v] == BLACK ) continue;
      if ( d[v] > d[u] + adj[u][j].second ) {
        d[v] = d[u] + adj[u][j].second;
        // priority_queue はデフォルトで大きい値を優先するため -1 を掛ける
        PQ.push(make_pair(d[v] * (-1), v));
        color[v] = GRAY;
      }
    }
  }

  for ( int i = 0; i < n; i++ )
    cout << i << " " << ( d[i] == INFTY ? -1 : d[i] ) << endl;
}

int main() {
  int k, u, v, c;

  cin >> n;
  for ( int i = 0; i < n; i++ ) {
    cin >> u >> k;
    for ( int j = 0; j < k; j++ ) {
      cin >> v >> c;
      adj[u].push_back(make_pair(v, c));
    }
  }

  dijkstra();

  return 0;
}


Measured memory_bytes: 7996
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    A = input().strip()

    cnt = Counter(A)

    sameCount = 0
    for _, c in cnt.items():
        sameCount += c * (c - 1) // 2

    N = len(A)
    ans = N * (N - 1) // 2 - sameCount + 1
    print(ans)


sol()

Measured memory_bytes: 3916
#include<stdio.h>
int main(){
    int money;
    int fun = 0;
    scanf("%d", &money);
    while(money >= 500){
        money -= 500;
        fun += 1000;
    }
    while(money >= 5){
        money -= 5;
        fun += 5;
    }
    printf("%d", fun);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>

using namespace std;

int main(){
  int k, count = 0;
  cin >> k;
  for(int i=1; i<=k; i++)
    for(int j=i+1; j<=k; j++){
      if((i%2 == 0 && j%2 != 0) || (i%2 != 0 && j%2 == 0))
        count++;
    }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a[200005];
void lt(int x,int y,int z){
	a[x]=a[y]<a[z];
	printf("< %d %d %d\n",y,z,x);
}
void add(int x,int y,int z){
	a[x]=a[y]+a[z];
	printf("+ %d %d %d\n",y,z,x);
}
//zero -> 4
//one -> 3
void Set(int x,int y){
	printf("+ 4 %d %d\n",y,x);
	a[x]=a[y];
}
void addif(int x,int b,int y,int cnt){
	//if b x+=y
	Set(100,3);
	for(int i=1;i<=cnt;++i){
		add(100+i,99+i,99+i);
	}
	Set(161,4);
	add(164,y,3);
	for(int i=cnt;~i;--i){
		add(162,161,100+i);
		lt(163,162,164);
		Set(165,163);
		for(int j=0;j<i;++j)add(165,165,165);
		add(161,161,165);
		add(166,163,b);
		lt(165,3,166);
		for(int j=0;j<i;++j)add(165,165,165);
		add(x,x,165);
		//if a[163] a[161]+=1<<i
		//if b and a[163] a[x]+=1<<i
	}
//	cerr<<a[x]<<' '<<a[b]<<' '<<a[y]<<' '<<cnt<<endl;
}
signed main(){
#ifdef QAQAutoMaton
	freopen("E.out","w",stdout);
#endif
	printf("92201\n");
	a[0]=1;a[1]=0;
	add(3,0,1);
	lt(3,2,3);
	Set(5,3);
	Set(6,0);
	for(int i=1;i<=32;++i){
		int nx=(i<<1)+5;
		add(nx,nx-2,nx-2);
		add(nx+1,nx-1,nx-1);
	}//64 + 6 = 70
	add(71,1,3);
	for(int i=30;~i;--i){
		add(73,72,(i<<1)+5);	
		lt(74,73,71);
//		cerr<<a[72]<<' '<<a[73]<<' '<<a[74]<<endl;
		addif(72,74,(i<<1)+5,i);
		addif(2,74,(i<<1)+6,i+30);
	}
//	cerr<<a[2]<<endl;
	return 0;
}



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

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

	int N;
	cin >> N;
	int X = N;
	int su = 0;
	while (X > 0) {
		su += X % 10;
		X /= 10;
	}
	if (N % su == 0) {
		cout << "Yes";
		return 0;
	}
	cout << "No";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ll long long
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define test int t; cin>>t; while(t--)
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define f0(i,n) for( ll i = 0; i < ( n ); i ++)
#define f1(i,n) for(i = 1; i <= ( n ); i ++)
#define f(i,m,n) for(auto i = ( m ); i <= ( n ); i ++)
#define nl cout<<"\n"
#define  mod 1000000007
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define rall(v) v.rbegin(), v.rend()
#define SZ(x) ((ll)x.size())
#define mem(a, b) memset(a, b, sizeof(a));
#define make_graph(k) int x,y; f0(i,k){cin>>x>>y; adj[x].pb(y); adj[y].pb(x);}
#define dekh cout<<"dekh"

#define o_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define o_setpll tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update>
typedef vector<ll> vl;




/*ll Pow(ll a, ll b, ll m){
    if(b==0)return 1;
    if(b%2==0){
        ll x = a*a;
        x%=m;
        return Pow(x,b/2,m);
    }
    return (a*Pow(a,b-1,m))%m;
}
*/
vector<ll>adj[200005];
 ll vis[200005]={0};

//ll p;ll arr[200005];

void dfs(ll x)
{
    cout<<x;nl;
    vis[x]=1;

    for(auto child : adj[x])
    {   if(!vis[child])
         {
             dfs(child);
         }
    }

}
ll n,W;
ll w[100005] , v[105];
ll dp[105][100005];
ll solve(ll ind, ll sum)
{
 // cout<<ind<<" "<<sum;nl;
    if(ind>=n)return 0;
    if(dp[ind][sum]!=-1)return dp[ind][sum];
    //if(sum>=W)return 0;
  	ll ans;
  if(sum+w[ind]>W) { ans = solve(ind+1, sum);}
  else
  {
     ans = max(solve(ind+1,sum) , solve(ind+1 , sum+w[ind])+v[ind]);
  }
    return dp[ind][sum] =ans;
}




int main()
{
    fast
    cin>>n>>W;
    mem(dp,-1);
    f0(i,n)
    {
        cin>>w[i]>>v[i];
    }
    cout<<solve(0,0);
}





Measured memory_bytes: 90392
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: tuple(map(int,input().split()))
M = int(input())
S = 0
ans = -1
for _ in range(M):
    d, c = inpl()
    S += d * c
    ans += c

while S >= 10:
    c = S % 10
    ans += S//10
    S = S//10 + c
print(ans)


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

A = [0] + A + [0]
sowa = 0
for i in range(N+1):
    sowa += abs(A[i]-A[i+1])
for i in range(1,N+1):
    print(sowa-(abs(A[i]-A[i-1])+abs(A[i+1]-A[i])-abs(A[i+1]-A[i-1])))


Measured memory_bytes: 14048
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(void){
    int MOD = 1000000007;
    int n,k; cin>>n>>k;
    vector <int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int in=0,b=0;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++) if(a[i]>a[j]) in++;
    }
    in=in*k%MOD;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) if(a[i]>a[j]) b++;
    }
    int x = k*(k-1)/2; x%=MOD;
    b = b*x%MOD;
    cout<<(in+b)%MOD;
}

Measured memory_bytes: 256
M = 10 ** 9 + 7
S = input()
A = 0
AB = 0
ABC = 0
X = 1
for c in S:
    if c == 'C':
        ABC = (ABC + AB) % M
    elif c == 'B':
        AB = (AB + A) % M
    elif c == 'A':
        A = (A + X) % M
    elif c == '?':
        ABC = (3 * ABC + AB) % M
        AB = (3 * AB + A) % M
        A = (3 * A + X) % M
        X = (3 * X) % M
print(ABC)

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

using namespace std;

typedef long long LL;

int A[3][1010],f[3][1010];
int N;

int main()
{
	scanf("%d",&N);
	for (int i=1;i<=2;i++)
		for (int j=1;j<=N;j++)scanf("%d",&A[i][j]);
	for (int i=1;i<=2;i++)
		for (int j=1;j<=N;j++)
			f[i][j] = max(f[i-1][j], f[i][j-1]) + A[i][j];
		
	printf("%d\n",f[2][N]);
}

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

int main() {
    int N; cin >> N;
    vector<int> P(N),Q(N);
    for(int i=0; i<N; i++){
        cin >> P.at(i);
    }
    for(int i=0; i<N; i++){
        cin >> Q.at(i);
    }
    vector<int> order(N);
    for(int i=0; i<N; i++){
        order.at(i)=i+1;
    }
    int a,b;
    int now=1;
    do{
        int cntp=1; int cntq=1;
        for(int i=0; i<N; i++){
            if(order.at(i)!=P.at(i)) cntp=0;
            if(order.at(i)!=Q.at(i)) cntq=0;
        }
        if(cntp==1) a=now;
        if(cntq==1) b=now;
        now++;
    }while(next_permutation(order.begin(),order.end()));
    
    cout << abs(a-b) << endl;
}


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

#define count_ones __builtin_popcountl
#define all(a) a.begin(), a.end()
#define gcd(a, b) __gcd(a, b)
#define lca(a, b) a / __gcd(a, b) * b
typedef long long ll;
typedef long long ld;
using namespace std;

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

    ll a, b;
    cin >> a >> b;
    if (a > 9 || b > 9) {
        cout << -1;
        return 0;
    }
    cout << a * b;
    
    return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import Counter
from math import ceil

n = int(readline())
a = list(map(int, readline().split()))
counter = Counter(a).values()
cnt = sum(counter) - len(counter)
print(n - ceil(cnt / 2) * 2)


Measured memory_bytes: 18636
#include<iostream>
#include<string>
using namespace std;
string S; long long a[200000], b[200000], c;
int main() {
	cin >> S; int h = 0;
	for (int i = 0; i < S.size(); i++) { if (S[i] == '(')h++; else h--; a[i + 1] = h; }
	for (int i = 0; i <= S.size(); i++) { b[a[i]]++; }
	for (int i = 0; i <= S.size(); i++)c += b[i] * (b[i] - 1);
	cout << c / 2 - 1 << endl;
	return 0;
}

Measured memory_bytes: 4484
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define INF 1e9
typedef long long ll;
using namespace std;

int main() {
    int n,m; cin >> n >> m;
    char a[50][50], b[50][50];
    rep(i,n){
        rep(j,n){
            cin >> a[i][j];
        }
    }
    rep(i,m){
        rep(j,m){
            cin >> b[i][j];
        }
    }
    rep(i,n-m+1){
        rep(j,n-m+1){
            int count = 0;
            rep(k,m){
                rep(l,m){
                    if(a[i+k][j+l]!=b[k][l]){
                        count += 1;
                    }
                }
            }
            if(count==0){
                cout << "Yes" << endl;
                goto last;
            }
        }

    }
    cout << "No" << endl;
    last: 

    return 0;
}

Measured memory_bytes: 384
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
////
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define allp(x) (x)->begin(), (x)->end()

#define pb push_back


using namespace std;
void dout() { cerr << endl; }
//typedef long long ll;
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

using ll = long long;
//#ifdef __int128
//using hll = __int128;
//#endif
using pii = pair<ll, ll>;
using ld = long double;
using pll = pair<long long, long long>;

template <typename T>
void do_uniq(vector<T> vec){
    sort(all(vec));
    vec.resize(unique(all(vec)) - vec.begin());
}

clock_t timestamp_start = clock();
void time_calc()
{
    cerr << (ld)(clock() - timestamp_start) / CLOCKS_PER_SEC << "\n";
}


#ifdef _getchar_nolock
#else
#define _getchar_nolock getchar_unlocked
#endif

//#define solvsh
//#define multi

#ifdef solvsh
#else

ll mod = 1e9 + 7;

ll add(ll a, ll b){
    return (a + b) % mod;
}
ll mult(ll a, ll b) {
    return (a * b) % mod;
}


const int MAXN = 205;
const int MAXK = 20 + 3;

ll bin_pw(ll base, ll p) {
    if (p == 0)return 1;
    if (p & 1) return mult(base, bin_pw(base, p - 1));
    ll v = bin_pw(base, p >> 1);
    return mult(v, v);
}

ll get_back(ll elem){
    return bin_pw(elem, mod - 2);
}

void solve() {

    int n;
    cin >> n;

    vector<ll>  v;

    for (int i = 0; i < n; ++ i){
        ll curr;
        cin >> curr;
        v.push_back(curr);
    }


    ll summ = 0;
    ll summ_sq = 0;
    for (int i = 0; i < n; ++ i) {
        summ = add(summ, v[i]);
        summ_sq = add(summ_sq, mult(v[i], v[i]));
    }

    ll ans = mult(summ, summ) - summ_sq;
    ans += mod;
    ans %= mod;

    ans = mult(ans, get_back(2));


    cout << ans;
}

#endif

void multisolve() {
    int t;
    cin >> t;

    int i = 1;
    while (t--) {
        solve();
        i++;
    }
}

#define int int
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(20);

#ifndef ONLINE_JUDGE
//    freopen("../input.in", "r", stdin);
#else

#endif
#ifdef multi
//        gen();
    multisolve();
#else
    solve();
//    gen();
#endif

}


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

int main() {
  int b;
  while (cin >> b, b) {
    int t, w;
    for (int i = 1e5; i >= 1; i--) {
      if (i % 2 != 0 && b % i == 0 || i % 2 == 0 && b % i != 0 && 2 * b % i == 0) {
        t = b / i - (i - 1) / 2;
        if (t >= 1) {
          w = i;
          break;
        }
      }
    }
    cout << t << " " << w << endl;
  }
}



Measured memory_bytes: 3080
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;


public class Main {
	
	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception addd) {
					addd.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception addd) {
				addd.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	
	public static FastReader sc = new FastReader();
 
	static long mod = (int) (1e9+7),MAX=(long)(1e18);
	static List<Integer>[] edges;
	public static int[][] parent;
	public static int col = 20;
	public static void main(String[] args) throws IOException{
		long n = sc.nextLong();
		Map<Long,Integer> map = new HashMap<>();
		fac(n,map);
		//out.print(map);
		long ans = 0;
		for(long key : map.keySet()) {
			long num = 1;
			long val = map.get(key);
			int cnt = 0;
			while(val >= 0) {
			     val-=num;
			     ++num;
			   //  out.println(val);
			     if(val >= 0)
				++cnt;
			}
			//out.println(cnt);
			ans+=cnt;
		}
		out.print(ans);
		out.close();
	}
	
    public static void fac(long n, Map<Long, Integer> map) 
    { 
        // Print the number of 2s that divide n 
        while (n%2==0) 
        {   map.put(2L, map.getOrDefault(2L,0)+1);
       // out.print(map);
            n /= 2; 
        } 
  
        // n must be odd at this point.  So we can 
        // skip one element (Note i = i +2) 
        for (long i = 3; i <= Math.sqrt(n); i+= 2) 
        { 
            // While i divides n, print i and divide n 
            while (n%i == 0) 
            { 
            	map.put(i, map.getOrDefault(i,0)+1);
                n /= i; 
            } 
        } 
  
        // This condition is to handle the case whien 
        // n is a prime number greater than 2 
        if (n > 2) 
        	map.put(n, map.getOrDefault(n,0)+1);
    } 
}

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

void read_stack(int n, int orig) {
    int x;
    if (n > 0) {
        cin >> x;
        read_stack(n-1, orig);
        cout << x;
        if (n != orig) {
            cout << " ";
        }
    }
}

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

    read_stack(n, n);
    cout << endl;
}


Measured memory_bytes: 3076
#include<iostream>
#include<cstdio>
#include<string.h>
#define LEN 1000001

using namespace std;

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

P Q[LEN];
int head, tail;

void enqueue(P x) {
  Q[tail] = x;
  tail = (tail+1)%LEN;
}

P dequeue() {
  P x = Q[head];
  head = (head+1)%LEN;
  return x;
}

int min(int a, int b){
  return (a<b)?a:b;
}

int main() {
  P u;
  int elaps = 0, c;
  int q, n, i;
  scanf("%d %d", &n, &q);
  for(i = 0; i < n; i++) {
    scanf("%s %d", Q[i].name, &Q[i].t);
  }
  head = 0;
  tail = n;

  while(head != tail) {
    u = dequeue();
    c = min(q, u.t);
    u.t -=c;
    elaps += c;
    if(u.t > 0) enqueue(u);
    else {
      printf("%s %d\n", u.name, elaps);
    }
  }

  return 0;
}



Measured memory_bytes: 22400