akhauriyash/Code-Regression huggingface dataset:
use proconio::input;
use proconio::marker::Usize1;
use std::collections::BinaryHeap;
use std::cmp::Reverse;
fn main() {
    input! {
        n: usize,
        es: [(Usize1, Usize1, usize); n-1],
        q: usize, k: Usize1,
        qs: [(Usize1, Usize1); q]
    };
    let mut edges: Vec<Vec<(usize, usize)>> = vec![Vec::new(); n];
    for (a,b,c) in es {
        edges[a].push((b,c));
        edges[b].push((a,c));
    }
    let inf = std::usize::MAX;
    let mut d = vec![inf; n];
    let mut heap = BinaryHeap::new();
    d[k] = 0;
    heap.push(Reverse((0, k)));
    while  !heap.is_empty() {
        let (dist, i) = heap.pop().unwrap().0;
        if d[i] < dist {
            continue;
        } else {
        for &(j, w) in &edges[i] {
            if d[j] > d[i] + w {
                d[j] = d[i] + w;
                heap.push(Reverse((d[j], j)));
            } else {}
        }}
    }
    for (x,y) in qs {
        println!("{}", d[x]+d[y]);
    }
}

Measured memory_bytes: 16784
from collections import Counter
N = int(input())
a = list(map(int,input().split()))
even = [[0,0]] + sorted([v,k] for k,v in Counter(a[1::2]).items())
odd = [[0,0]] + sorted([v,k] for k,v in Counter(a[0::2]).items())

if even[-1][1] != odd[-1][1]:
    print(N - even[-1][0] - odd[-1][0])
else:
    print(min(N - even[-1][0] - odd[-2][0], N - even[-2][0] - odd[-1][0]))


Measured memory_bytes: 22132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 998244353;
const ll INF = mod * mod;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)

int main()
{
    int N; cin >> N;
    bool flag = false;
    for (int i = 1; i < 10; i++) {
        if (N % i == 0 && N / i < 10) flag = true;
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
} 

Measured memory_bytes: 256
from collections import deque

def bfs(s):
    q = deque()
    q.append([s, 0])
    while q:
        x, y = q.popleft()
        for g in G[x]:
            if color[g[1]] == -1:
                color[g[1]] = y + 1
                y += 1
                y %= k
                q.append([g[0], y])
    return

n = int(input())
G = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append([b, i])
    G[b].append([a, i])
k = 0
for g in G:
    k = max(k, len(g))
color = [-1] * (n - 1)
bfs(0)
print(k)
for i in color:
    print(i)

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

#define F(i,a,b) for(int i=a;i<b;i++)

using namespace std;

int n,x;

int main()
{
	cin>>n>>x;
	int m[n+5];
	F(i,0,n)scanf("%d",&m[i]);
	
	int ans=0;
	F(i,0,n)x-=m[i];
	ans+=n;
	sort(m,m+n);
	
	ans+=x/m[0];
	
	cout<<ans;	
	return 0;
}


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


int main() {
  string s,t;
  cin >> s >> t;
  
  int slen=s.size();
  int tlen=t.size();
  
  int ans=tlen;
  for(int i=0; i<=slen-tlen; i++){
    int diff=0;
    for(int j=0; j<tlen; j++){
      diff += s[i+j]!=t[j];
    }
    ans = min(ans,diff);
  }
  cout << ans << endl;
}

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

int N, M;
vector<vector<int>> G;
vector<vector<ll>> lpMemo, rpMemo;
vector<unordered_map<int, int>> id;

int subtreeCount(int, int);

// [0, pi)
ll leftProduct(int u, int pi) {
  if (lpMemo[u][pi] != -1) return lpMemo[u][pi];

  return lpMemo[u][pi] =
             (subtreeCount(G[u][pi - 1], u) + 1) * leftProduct(u, pi - 1) % M;
}

// [pi, G[u].size())
ll rightProduct(int u, int pi) {
  if (rpMemo[u][pi] != -1) return rpMemo[u][pi];

  return rpMemo[u][pi] =
             (subtreeCount(G[u][pi], u) + 1) * rightProduct(u, pi + 1) % M;
}

int subtreeCount(int u, int p) {
  if (p == -1) return leftProduct(u, G[u].size());

  return leftProduct(u, id[u][p]) * rightProduct(u, id[u][p] + 1) % M;
}

int main() {
  cin >> N >> M;
  G.resize(N);
  id.resize(N);
  lpMemo.resize(N), rpMemo.resize(N);

  auto addEdge = [&](int u, int v) {
    id[u][v] = G[u].size();
    G[u].push_back(v);
  };

  rep(i, N - 1) {
    int x, y;
    cin >> x >> y;
    x--, y--;

    addEdge(x, y);
    addEdge(y, x);
  }

  rep(i, N) {
    lpMemo[i].resize(G[i].size() + 1, -1);
    rpMemo[i].resize(G[i].size() + 1, -1);
    lpMemo[i][0] = 1;
    rpMemo[i][G[i].size()] = 1;
  }

  rep(i, N) cout << subtreeCount(i, -1) << endl;

  return 0;
}


Measured memory_bytes: 40576
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back

int main(){
    ll n;
    cin>>n;
    vector<ll> a(n);
    ll i,j,ans = 0;
    for(i=0;i<n;i++){
        cin>>a[i];
        ans = ans^a[i];
    }
    for(i=0;i<n;i++)
        cout<<(a[i]^ans)<<" ";
}

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

ll N;
string S;

int main(void){
    cin >> N >> S;
    if(N%2 == 1){
        cout << "No" << endl;
        return 0;
    }
    bool flag = true;
    rep(i,N/2){
        if(S[i] !=S[i+N/2])flag = false;
    }
    if(flag)cout << "Yes" <<endl;
    else cout << "No" <<endl;
    
}




Measured memory_bytes: 256
def solve(prime, pay)
  turi = pay - prime
  result = {100 => 0, 500 => 0, 1000 => 0}
  if turi >= 1000
    add = turi / 1000
    result[1000] += add
    turi -= add * 1000
  end
  if turi >= 500
    add = turi / 500
    result[500] += add
    turi -= add * 500
  end
  if turi >= 100
    add = turi / 100
    result[100] += add
    turi -= add * 100
  end
  result
end

def main
  STDIN.each_line{|line|
    prime, pay = line.split(" ").map{|n| n.to_i}
    if prime == 0 && pay == 0
      break
    end
    result = solve prime, pay
    puts "#{result[100]} #{result[500]} #{result[1000]}"
  }
end

main

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

int main() {
  int n;
  cin >> n;
  n %= 10;
  if(n == 0 || n == 1 || n == 6 || n == 8){
    cout << "pon" << endl;
  }
  else if(n == 3){
    cout << "bon" << endl;
  }
  else cout << "hon" << endl;
}

Measured memory_bytes: 3596
#include <stdio.h>
#include <math.h>

int sosuufi(int n){
  int i;
  int flag=1;
  for(i=2;i<=(int)sqrt(n);i++){
    if(n%i==0){
      flag=0;
    }
  }
  return flag;
}

void sosuu(int*A){
  int i;
  int k=0;
  for(i=6;i<=55555;i++){
    if(i%5==1 && sosuufi(i)==1){
      A[k]=i;
      k++;
    }
    if(k>55){
      break;
    }
  }
}

int main(){
  int n;
  scanf("%d",&n);
  int A[55];
  sosuu(A);
  int i;
  for(i=0;i<n;i++){
    printf("%d ",A[i]);
  }
  return 0;
}


Measured memory_bytes: 128
import itertools
N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))

n = [i+1 for i in range(N)]

a = 0
b = 0
i = 0
for x in itertools.permutations(n):
    if list(x) == P:
        a = i
    if list(x) == Q:
        b = i
    i += 1

print(abs(a - b))

Measured memory_bytes: 9204
// By Shreehari Bodas

#include <bits/stdc++.h>

using namespace std;

int main(){
	
	int N,W; cin>>N>>W;
	int w[N],v[N];

	int sum=0;

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

	long long int dp[sum+1]; // values go from 0 to sum; stores min. weight for a given value;
	dp[0]=0;
	for(int i=1;i<=sum;i++) dp[i]=INT_MAX;
		
	for(int i=0;i<N;i++){
		for(int value=sum-v[i];value>=0;value--){
			dp[value+v[i]]=min(dp[value+v[i]],dp[value]+w[i]);
		}
	}

	int max_val=0;
	for(int i=0;i<sum+1;i++){
		if(dp[i]<=W) max_val=i;
	}

	cout<<max_val<<endl;

	return 0;
} 

Measured memory_bytes: 1152
#include <cstdio>
#include <string>
#include <iostream>
#include <cstring>

using namespace std;

int fie[40][40];
int num[40][40];
int n,m,k,d;

int main(void){
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		scanf("%d",&m);
		m--;
		scanf("%d",&k);
		k--;
		scanf("%d",&d);
		if(n==1){
			printf("0\n");
			continue;
		}
		memset(fie,-1,sizeof(fie));
		memset(num,-1,sizeof(num));
		for(int i=0;i<n;i++)num[0][i]=i;
		for(int i=0;i<d;i++){
			for(int j=0;j<n;j++)num[i+1][j]=num[i][j];
			string str;
			cin >> str;
			for(int j=0;j<n-1;j++){
				fie[i][j]=str[j]-'0';
				if(fie[i][j]==1){
					swap(num[i+1][j],num[i+1][j+1]);
				}
			}
		}
		if(num[d][k]==m){
			printf("0\n");
		}else{
			int sw=num[d][k];
			bool flag=false;
			for(int i=0;i<d;i++){
				if(flag)continue;
				for(int j=0;j<n;j++){
					if(num[i][j]==m && num[i][j+1]==sw && num[i+1][j]==m && num[i+1][j+1]==sw){
						flag=true;
						printf("%d %d\n",i+1,j+1);
					}
					if(num[i][j]==sw && num[i][j+1]==m && num[i+1][j]==sw && num[i+1][j+1]==m){
						flag=true;
						printf("%d %d\n",i+1,j+1);
					}
				}
			}
			if(!flag){
				printf("1\n");
			}
		}
	}
	return 0;
}

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

using namespace std;

int const M = 1e9;
int main()
{
    int n;  cin >> n;
    vector <int> v(n), dp(n+15, 1e9);
    for (int &x: v)
        cin >> x;
    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j <= i + 2; j++)
        {
            if (j < n)
                dp[j] = min(dp[j], dp[i] + abs(v[i] - v[j]));
        }
    }
    cout << dp[n-1] << "\n";
    
}

Measured memory_bytes: 1024
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[] a = new int[n];
        int sum = 0;
        int b = 0;
        for(int i = 0; i < n; i++){
            a[i] = scan.nextInt();
            sum += a[i];
        }
        for(int i = 0; i < n; i++){
            if(a[i] >= sum / (4 * m) && sum % (4 * m) == 0){
                b++;
            }else if(a[i] > sum / (4 * m)){
                b++;
            }
        }
        if(b >= m){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 23764
/*input
999
*/
#include<bits/stdc++.h>
#define int        long long
#define MOD        1000000007
#define MAX        100005
#define pb         push_back
#define mp         make_pair
#define pii        pair<int,int>
#define mii        map<int,int>
#define vi         vector<int>
#define ff         first
#define ss         second
#define T          int t;cin>>t;while(t--)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define umi        unordered_map<int,int>
#define maxheap    priority_queue<int>
#define minheap    priority_queue<int,vector<int>,greater<int> >
#define inp(n)     for(int i=0;i<n;i++)
#define N          2000005
#define lb(v,val)  (lower_bound(v.begin(),v.end(),val)-v.begin())
#define ub(v,val)  (upper_bound(v.begin(),v.end(),val)-v.begin())
using namespace std;
using namespace std::chrono;

bool pal(string s){
    int n = s.length();
    for(int i=0,j=n-1;i<j;i++,j--){
        if(s[i] != s[j]) return false;
    }
    return true;
}

signed main(){
    double n;
    cin >> n;
    n/=3.0;
    n = n*n*n;
    cout << fixed << setprecision(10) << n << '\n';
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mp make_pair
#define fi fisrt
#define se second

using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f3f3f3f;
int cnt;
int prim[N];
int vis[N];
void init()
{
	for (int i=2;i<N;i++)
	{
		if (!vis[i]) 
		{
			prim[++cnt]=i;
//			printf("prim[%lld]=%lld\n",cnt,i);
		}
		for (int j=1;j<=cnt && i*prim[j]<N;j++)
		{
			vis[i*prim[j]]=1;
			if (i%prim[j]==0) break;
		}
	}
}
int n;
int num[N],a[N];
int GcD;
bool flag=1;
void solve(int x)
{
	if (!vis[x])
	{
		num[x]++;
		return;
	}
	for (int i=1;i<=cnt;i++)
	{
		if (x%prim[i]==0) 
		{
			num[prim[i]]++;
			while (x%prim[i]==0) x/=prim[i];
			solve(x);
			break;
		}
	}
}
void otpt()
{
	if (flag==1) cout<<"pairwise coprime"<<endl;
	else if (GcD==1) cout<<"setwise coprime"<<endl;
	else cout<<"not coprime"<<endl;
}
signed main()
{
	init();
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	GcD=a[1];
	for (int i=1;i<=n;i++) GcD=__gcd(GcD,a[i]);
	for (int i=1;i<=n;i++) solve(a[i]);
	for (int i=2;i<N;i++)
		if (num[i]>1) flag=0;
	otpt();
}


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

int main(void) {
    int N,B;
    int64_t sum = 0;
    int remain;
    cin >> N;
    vector<int> A(N+1);
    for(int i=0;i<N+1;i++) {
        cin >> A[i];
    }

    for(int i=0;i<N;i++) {
        cin >> B;
        if(A[i] < B) {
            if(A[i+1] < (B-A[i])) {
//printf("double A[%d]:%d A[%d]:%d B:%d sum:%ld\n",i+1,A[i+1],i,A[i],B, sum);
                sum += A[i+1];
                A[i+1] = 0;
            } else {
//printf("plus   A[%d]:%d A[%d]:%d B:%d sum:%ld\n",i+1,A[i+1],i,A[i],B, sum);
                sum += (B-A[i]);
                A[i+1] -= (B-A[i]);
            }
            sum += A[i];
        } else {
// printf("single A[%d]:%d A[%d]:%d B:%d sum:%ld\n",i+1,A[i+1],i,A[i],B, sum);
            sum += B;
        }
    }

    cout << sum << "\n";
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<long long, long long>
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

vector<int> graph[100005];
vector<int> sorted;
vector<int> depth(100005);
vector<int> depths;

void dfs(int i) {
  for(auto e: graph[i]) {
    dfs(e);
  }
  sorted.push_back(i);
}

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

  int n; cin >> n;
  rep(i, n-1) {
    int a; cin >> a;
    graph[a].push_back(i+2);
  }
  dfs(1);

  for(auto e: sorted) {
    for(auto f: graph[e]) {
      depths.push_back(depth[f]);
    }
    int si = depths.size();
    sort(depths.rbegin(), depths.rend());
    int ma = 0;
    for(int i=0; i<si; i++) {
      ma = max(ma, depths[i]+i+1);
    }
    depth[e] = ma;
    //debug(e); debugln(depth[e]);
    depths.clear();
  }
  cout << depth[1] << endl;
}

Measured memory_bytes: 11512
#include <stdio.h>
int main(){
 int a[3],b[3],i;
  scanf("%d %d %d",&a[0],&a[1],&a[2]);
  b[0]=0;
  b[1]=0;
  b[2]=0;
  for(i=0;i<3;i++)
    if(a[i]==5)b[0]++;else if(a[i]==7)b[1]++;else b[2]++;
  if (b[0]==2&&b[1]==1) printf("YES"); else printf("NO");
  
  return 0;
  
}


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

using namespace std;

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

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

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

template<class T>
ostream &operator<<(ostream &os, const vector <T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair <T, U> &p) {
    return os << "(" << p.first << " " << p.second << ")";
}

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

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld EPS = 1e-9;


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

    ll N, M, L;
    cin >> N >> M >> L;
    vi K(N);
    REP(i, N) {
        cin >> K[i];
        --K[i];
    }
    sort(all(K));
    // debug(K);

    vll S(M+1);
    REP(i, M) {
        cin >> S[i+1];
        S[i+1] += S[i];
    }
    // debug(S);

    vvll dp(N, vll(N, LINF));
    dp[0][0] = 0;
    REP(i, N-1) {
        REP(j, N-1) {
            if (dp[i][j] == INF) continue;
            int m = max(i, j);
            chmin(dp[m+1][j], dp[i][j] + (S[K[m+1]+1] - S[K[i]]) / L);
            chmin(dp[i][m+1], dp[i][j] + (S[K[m+1]+1] - S[K[j]]) / L);
        }
        // REP(k, N) {
        //     debug(dp[k]);
        // }
        // cerr << endl;
    }

    REP(i, N-1) {
        if (chmin(dp[N-1][N-1], dp[i][N-1] + (S[K[N-1]+1] - S[K[i]]) / L)) {
            // debug(i);
            // debug(dp[N-1][N-1]);
        }
    }
    // REP(j, N) {
    //     chmin(dp[N][N], dp[N][j] + (S[K[j]+1] - (j ? S[K[j-1]] : 0)) / L);
    // }
    // REP(i, N) {
    //     debug(dp[i]);
    // }
    // cerr << endl;


    cout << dp[N-1][N-1] << endl;

    return 0;
}



Measured memory_bytes: 35100
#include<iostream>
#include<string>
using namespace std;
int main(){
  string s,t,u;
  getline(cin,s);
  t = s;
  u = s;
  for(;;){
    string::size_type pos = s.find("apple");
    if(pos == string::npos) break;
    s[pos] = 'p';s[pos+1] = 'e';s[pos+2] = 'a';s[pos+3] = 'c';s[pos+4] = 'h';
    u[pos] = 'p';u[pos+1] = 'e';u[pos+2] = 'a';u[pos+3] = 'c';u[pos+4] = 'h';
  }
  for(;;){
    string::size_type pos = t.find("peach");
    if(pos == string::npos) break;
    t[pos] = 'a';t[pos+1] = 'p';t[pos+2] = 'p';t[pos+3] = 'l';t[pos+4] = 'e';
    u[pos] = 'a';u[pos+1] = 'p';u[pos+2] = 'p';u[pos+3] = 'l';u[pos+4] = 'e';
  }
  cout <<u<<endl;
  return 0;
}

Measured memory_bytes: 1180
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N,M;

void solve() {
    cin >> N >> M;
    vector<vector<int>> g(N + 1);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> parents(N+1, -1);
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int point = q.front(); q.pop();
        for (int x : g[point]) {
            if (parents[x] != -1) continue;
            parents[x] = point;
            q.push(x);
        }
    }
    cout << "Yes" << endl;
    for (int i = 2; i <= N; ++i) {
        cout << parents[i] << endl;
    }
}

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


Measured memory_bytes: 9960
n,m,x,y=map(int,input().split())
x1=list(map(int,input().split()))
y1=list(map(int,input().split()))
if min(y1)-max(x1)>=1 and max(x1)<y and min(y1)>x:
    print('No War')
else:
    print('War')

Measured memory_bytes: 3060
n,T=map(int, input().split())
m=-1
for i in range(n):
  c,t=map(int, input().split())
  if t<=T:
    if m==-1:
      m=c
    else:
      m=min(m,c)
if m==-1:
  print('TLE')
else:
  print(m)


Measured memory_bytes: 2940
#include<stdio.h>

int main(){

int M,T,P,R;

while(1){
scanf("%d%d%d%d",&M,&T,&P,&R);
if(M==0&&T==0&&P==0&&R==0)break;

int n[51][11]={};int n2[51][11]={};

int m,t,p,j;
for(int i=0;i<R;i++)
{
scanf("%d%d%d%d",&m,&t,&p,&j);
if(j==0){n[t][p]+=m;n2[t][p]=1;}
else{n[t][p]+=20;}
}
for(int i=1;i<=T;i++)
for(int k=1;k<=P;k++)
	if(n2[i][k]==0){n[i][k]=0;}


int N[51][3]={};
for(int i=1;i<=T;i++)
for(int k=1;k<=P;k++)
{
N[i][0]+=n[i][k];
N[i][1]+=n2[i][k];
N[i][2]=i;
}

for(int i=1;i<=T;i++)
for(int k=T;k>i;k--)
if(N[k][1]>N[k-1][1]){
int t=N[k][1];N[k][1]=N[k-1][1];N[k-1][1]=t;
int t2=N[k][0];N[k][0]=N[k-1][0];N[k-1][0]=t2;
int t3=N[k][2];N[k][2]=N[k-1][2];N[k-1][2]=t3;
}
for(int i=1;i<=T;i++)
for(int k=T;k>i;k--)
	if(N[k][1]==N[k-1][1]&&N[k][0]<N[k-1][0]){
		int t=N[k][1];N[k][1]=N[k-1][1];N[k-1][1]=t;
int t2=N[k][0];N[k][0]=N[k-1][0];N[k-1][0]=t2;
int t3=N[k][2];N[k][2]=N[k-1][2];N[k-1][2]=t3;
	}


for(int i=1;i<=T;i++)
for(int k=T;k>i;k--)
	if(N[k][1]==N[k-1][1]&&N[k][0]==N[k-1][0]&&N[k][2]>N[k-1][2]){
		int t3=N[k][2];N[k][2]=N[k-1][2];N[k-1][2]=t3;
	}


for(int i=1;i<=T;i++)
{if(i>1){if(N[i][1]==N[i-1][1]&&N[i][0]==N[i-1][0])printf("=");
else printf(",");}

printf("%d",N[i][2]);
}
printf("\n");
}
return 0;
}

Measured memory_bytes: 1036
N,Q=map(int,input().split())
S="#"+input()+"#"
accum=[0]
for i in range(1,N+1):
	if (S[i]=="A" and S[i+1]=="C") or (S[i-1]=="A" and S[i]=="C"):
		accum.append(accum[i-1]+1)
	else:
		accum.append(accum[i-1])
for i in range(Q):
	l,r=map(int,input().split())
	print((accum[r]//2)-((accum[l-1]+1)//2))

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

using namespace std;

int main()
{
	int R[200000];
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>R[i];
	int maxv=-1000000000;
	int minv=R[0];
	for(int i=1;i<n;i++)
	{
		maxv=max(maxv,R[i]-minv);
		minv=min(minv,R[i]);
	}
	cout<<maxv<<endl;
}


Measured memory_bytes: 3884
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int a, b;
	cin >> a >> b;
	
	cout << (a + b + 1) / 2 << endl;
	
	return 0;
}


Measured memory_bytes: 256
x, n = map(int, input().split())

if x == 0:
    print(x)
    exit()

p = list(map(int, input().split()))
p.sort()

large = 0
for i in range(101):
    if not x + i in p:
        large = x + i
        break

small = 0
for i in range(101):
    if not x - i in p:
        small = x - i
        break

if abs(x - large) == abs(x - small):
    print(small)
elif abs(x - large) < abs(x - small):
    print(large)
else:
    print(small)

Measured memory_bytes: 9212
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ll                  long long int
#define ull                 unsigned long long int
#define ld                  long double
#define fi                  first
#define se                  second
#define pb                  push_back
#define pbb                 pop_back
#define mp                  make_pair
#define pii     	        pair<int,int>
#define all(x)              x.begin(), x.end()
#define uniq(x)             x.erase(unique(x.begin(),x.end()),x.end())
#define mem(array, value)   memset(array, value, sizeof(array))
#define lcm(a,b)            (abs(a)/gcd(a,b))*abs(b)
#define PI      	        2*acos(0.0)
#define INF     	        1e9
#define EPS     	        1e-8
#define line                cout << "\n==========\n"
#define fastRead 	        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> orderedSet; 

const int N = 1e5+9;
int ara[N][3];
int dp[N][3];
int n;

int call(int idx, int pre)
{
    if (idx >= n){
        return 0;
    }
    if (dp[idx][pre] != -1){
        return dp[idx][pre];
    }
    int res = 0;
    for (int i = 0; i<3; i++){
        if (i != pre){
            res = max(res, call(idx+1, i) + ara[idx][i]);
        }
    } 
    return dp[idx][pre] = res;
}

int main ()
{
    #ifdef Lollipop
    //freopen ("input.txt", "r", stdin);
    //freopen ("output.txt", "w", stdout);
    #endif
    mem(dp, -1);
    cin >> n;
    for (int i = 0; i<n; i++){
        for (int j = 0; j<3; j++){
            cin >> ara[i][j];
        }
    }
    cout << max({call(1, 0) + ara[0][0], call(1, 1) + ara[0][1], call(1, 2) + ara[0][2]}) << endl;
    return 0;
}





Measured memory_bytes: 8832
#include<bits/stdc++.h>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define ll long long
using namespace std;
const int N=105;
int n,x,y,ans,md;
int v[N];
vector<int>e[N];
ll ans2;
void dfs2(int x,int y,int d){
	int s=0;
	for(int i:e[x])if(y!=i)
		++s,dfs2(i,x,d+1);
	md=max(md,d);
	v[d]=max(v[d],s);
}
void dfs(int x,int y){
	md=0;
	dfs2(x,0,0);
	ll tot=1;
	fo(i,0,md-1)tot*=v[i],v[i]=0;
	if(md<ans)ans=md,ans2=tot;
	if(md==ans)ans2=min(ans2,tot);
	for(int i:e[x])if(y!=i){
		md=0;
		dfs2(x,i,0);
		dfs2(i,x,0);
		ll tot=2;
		fo(j,0,md-1)tot*=v[j],v[j]=0;
		if(md<ans)ans=md,ans2=tot;
		if(md==ans)ans2=min(ans2,tot);	
		dfs(i,x);
	}
}
int main(){
	cin>>n;
	fo(i,2,n)cin>>x>>y,e[x].push_back(y),e[y].push_back(x);
	ans=n+1;
	dfs(1,0);
	printf("%d %lld\n",ans+1,ans2);
}

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

#define ll long long

using namespace std;

int n;
int Y[109] ={};
int M[109] ={};
int D[109] ={};

int main(){

    scanf("%d",&n);

    for(int i=0;i<n;i++){
        scanf("%d %d %d",&Y[i],&M[i],&D[i]);
    }

    for(int i=0;i<n;i++){
        int ans = 0;
        for(int j = Y[i]+1;j< 1000 ; j++){
            if(j%3 == 0){
                ans += 200;
            }else{
                ans += 195;
            }
        }

        if(Y[i]%3 == 0){
            ans += (10 - M[i]) * 20;
        }else{
            for(int j=M[i]+1;j<=10;j++){
                if(j%2){
                    ans += 20;
                }else{
                    ans += 19;
                }
            }
        }

        if(M[i]%2 || Y[i]%3 == 0){
            ans += 21-D[i];
        }else{
            ans += 20-D[i];
        }
        printf("%d\n",ans);
    }

}


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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ll          long long
#define pb          push_back
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define rs(v,n)     v.resize(n)
#define hell        1000000007
#define peak        9123372036854775807
#define pii         acos(-1)
#define clr(a,x)    memset(a,x,sizeof(a))
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class x,class y> x sum(x a,y b){return a+b;}
template<class x,class y> x mul(x a,y b){return a*b;}
template<class x,class y> x sub(x a,y b){return a-b;}
template<class x,class y> x divi(x a,y b){return a/b;}

template<class x,class y>
istream &operator>>(istream &in,pair<x,y> &p) 
{ 
    in>>p.F>>p.S;
    return in;
}
template<class x>
istream &operator>>(istream &in,vector<x> &v) 
{
    for(auto& i:v)
        in>>i;
    return in;
}
template<class x,class y>
ostream &operator<<(ostream &out,pair<x,y> &p) 
{ 
    out<<"("<<p.F<<","<<p.S<<") ";
    return out; 
}
template<class x>
ostream &operator<<(ostream &out,vector<x> &v) 
{ 
    out<<v.size()<<endl;
    for(auto i:v)
        out<<i<<" ";
    out<<endl;
    return out; 
}
#define N  1000005

int main()
{
    ios;
    ll tt=1;
    // cin>>tt;
    while(tt--)
    {
    	ll i,j,k,l,m,n;
    	cin>>n;
    	vector<pair<ll,ll>> v;
    	for(i=0;i<n;i++)
    	{
    		cin>>l>>m;
    		v.pb({m,l});
    	}
    	sort(all(v));
    	ll d=0;
    	ll t=1;
    	for(i=0;i<n;i++)
    	{
    		
    		// cout<<d<<" "<<v[i].F<<" "<<v[i].S.F<<" "<<v[i].S.S<<endl;
    		d+=v[i].S;
    		if(d>v[i].F) t=0;
    	}
    	if(t)
    		cout<<"Yes";
    	else
    		cout<<"No";
    }
    return 0;
}

Measured memory_bytes: 6384
import math
n = int(input())
li = list()
for _ in range(n):
    li.append(''.join(sorted(input())))
li.sort()

ans = 0
i = 0
while i < n:
    cnt = 1
    c = li[i]
    while i < n - 1 and li[i] == li[i + 1]:
        cnt += 1
        i += 1
    i += 1
    if cnt > 1:
        ans += math.factorial(cnt) // (math.factorial(cnt - 2) * math.factorial(2))
print(ans)

Measured memory_bytes: 65752
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
int main()
{
    ll x;
    scanf("%lld",&x);
    if(x>=30)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}


Measured memory_bytes: 3756
# -*- coding: utf-8 -*-
a = int(input())
b = list(map(int,input().split()))
from collections import defaultdict
d = defaultdict(int)
for i in b:
    d[i]+=1
ret = 0
for k,v in d.items():
    if v>=k:
        ret+=(v-k)
    else:
        ret+=v
print(ret)

Measured memory_bytes: 18168
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		MyScanner sc = new MyScanner(System.in);
		String n = sc.next();
		int l = n.length();
		if(l==1) {
			System.out.println(n);
		} else {
			char ch = n.charAt(0);
			int a = Character.getNumericValue(ch);
			int ans = Math.max(digitsum(n), (a-1)+(l-1)*9);
//			System.out.println(digitsum(n));
//			System.out.println((a-1)+(l-1)*9);
			System.out.println(ans);
		}
	}
	
	static int digitsum(String n) {
		int ret = 0;
		for(int i=0; i<n.length(); i++) {
			ret += Character.getNumericValue(n.charAt(i));
		}
		return ret;
	}

	static class MyScanner
	{
		BufferedReader br;
		StringTokenizer st;
		public MyScanner(InputStream s)
		{
			br=new BufferedReader(new InputStreamReader(s));
		}
		public String nextLine() throws IOException
		{
			return br.readLine();
		}
		public String next() throws IOException
		{
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
			
		}
		public double nextDouble() throws IOException
		{
			return Double.parseDouble(next());
		}
		public boolean ready() throws IOException
		{
			return br.ready();
		}
		public long nextLong() throws IOException
		{
			return Long.parseLong(next());
		}
	}
}

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

int main(){
long X, A, B; cin >> X;
for(A=0; A<=1000; A++){ 
for(B=-1000; B<=1000; B++){ 
if(A*A*A*A*A-B*B*B*B*B==X){ cout << A << " " << B << "\n"; return 0; }
}}
}

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){

	int h;
	int hh;
	int w;
	int ww;
	string i;
	vector<string> lines;

	cin >> h >> w;
	for ( int i = 0; i < h; ++i )
	{
		string s;
		cin >> s;
		lines.push_back(s);
	}

	for (ww = w + 2; ww > 0; ww--)
	{
		cout << "#";
	}
	cout << endl;
	for ( int i = 0; i < h; ++i ) {
		cout << "#" << lines[i] << "#" << endl;
	}
	for (ww = w + 2; ww > 0; ww--)
	{
		cout << "#";
	}
	cout << endl;

	
	return 0;
}

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

using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
template <typename T>
constexpr T INF = numeric_limits<T>::has_infinity ? numeric_limits<T>::infinity() : numeric_limits<T>::max() / 2;

#define REP(i, stop) FOR(i, 0, stop)
#define FOR(i, start, stop) for (int i = start, i##_len = stop; i < i##_len; ++i)
#define ALL(v) (v).begin(), (v).end()

template<typename T>
istream& operator>>(istream& in, vector<T>& a) { for (T& x : a) in >> x; }

void LOG(int x) { cerr << x << "\n"; }
void LOG(vector<int>& a) { for (int x : a) cerr << x << " "; cerr << "\n"; }

int ceil(int a, int b) { return (a - 1) / b + 1; }

class UnionFind {
private:
  vector<int> par;
  int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
  }
public:
  UnionFind(int size) {
    par.resize(size);
    REP(i, size) par[i] = i;
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    par[x] = y;
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

struct InitCpp { InitCpp() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
} } initCpp;

signed main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(m), b(m);
  REP(i, m) cin >> a[i] >> b[i];
  int cnt = 0;
  REP(i, m) {
    auto uf = UnionFind(n);
    REP(j, m) {
      if (i != j) uf.unite(a[j] - 1, b[j] - 1);
    }
    REP(j, n) {
      if (!uf.same(0, j)) {
        cnt += 1;
        break;
      }
    }
  }
  cout << cnt << endl;
}


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


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

def main():
	n,k=map(int,input().split())
	x=list(map(int,input().split()))

	ans=10**18

	for i in range(n):
		try:
			l=x[i]
			r=x[i+k-1]
			if r<0:
				ans=min(ans,-l)
			elif l>0:
				ans=min(ans,r)
			else:
				ans=min(ans,r-l+min(-l,r))
		except:
			pass
	print(ans)



if __name__ == "__main__":
	main()


Measured memory_bytes: 12488
// Author : Mohamed Sameh
#include <bits/stdc++.h>
typedef long long ll ;
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SZ(a) (int)a.size()
#define Flush fflush(stdout);
using namespace std ;
int main()
{
    int h ,n ;
    cin >> h >> n ;
    int sum =0;
    for (int i =0 ; i < n ;i++)
    {
        int x ;
        cin >> x ;
        sum += x ;
    }
    if (sum >= h )
        cout <<"Yes\n";
    else
        cout <<"No\n";


}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
    int W , H ;
    while(1){
        cin >> H >> W;
        if ( H == 0 && W == 0 ) break;
        
        for (int i = 0; i < H; i++ ){
            for(int j = 0; j < W; j++ ){
                cout << '#';       
            }
            cout << endl;
        }
        cout << endl;
    }
    
    return 0;
}

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

int main(){
  int X,Y,Z;
  vector<int>vec(3);
  
  for(int i=0; i<3 ;i++){
    cin >> vec.at(i);}
    
  swap( vec.at(0),vec.at(1) );
    
  swap( vec.at(0),vec.at(2) );
    
  cout << vec.at(0) << " " << vec.at(1) << " " << vec.at(2) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {

    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    long long sum = 0;
    rep(i,N) {
        cin >> A[i];
        sum += A[i];
    }

    sort(A.begin(), A.end());
    
    vector<long long> divisor;
    for (long long i = 1; i * i <= sum; i++) {
        if (sum % i == 0) {
            divisor.push_back(i);
            if (i != sum / i) divisor.push_back(sum / i);
        }
    }
    
    sort(divisor.begin(), divisor.end(), greater<long long>());
    long long D = divisor.size();
    rep(i,D) {
        long long x = divisor[i];
        vector<long long> plus, minus;
        rep(j,N) {
            long long p = A[j] % x;
            if (p <= (x - p)) plus.push_back(p);
            else minus.push_back(x - p);
        }
        sort(plus.begin(), plus.end());
        sort(minus.begin(), minus.end());
        deque<long long> deq_plus, deq_minus;
        rep(j,plus.size()) deq_plus.push_back(plus[j]);
        rep(j,minus.size()) deq_minus.push_back(minus[j]);
        long long count = 0;
        while (!deq_plus.empty() || !deq_minus.empty()) {
            if (deq_plus.empty()) {
                long long& mb = deq_minus.back(); deq_minus.pop_back();
                deq_plus.push_back(x - mb);
            } else if (deq_minus.empty()) {
                long long& pb = deq_plus.back(); deq_plus.pop_back();
                deq_minus.push_back(x - pb);
            }
            long long& p = deq_plus.front(); deq_plus.pop_front();
            long long& m = deq_minus.front(); deq_minus.pop_front();
            if (p == m) count += p;
            else if (p > m) {
                count += m;
                p -= m;
                deq_plus.push_front(p);
            } else {
                count += p;
                m -= p;
                deq_minus.push_front(m);
            }
        }
        if (count <= K) {
            cout << x << endl;
            return 0;
        }
    }

    return 0;
}

Measured memory_bytes: 256
require 'matrix'
n, m, l = gets.chomp.split(' ').map(&:to_i)
a = []
n.times do
  a << gets.chomp.split(' ').map(&:to_i)
end
b = []
m.times do
  b <<  gets.chomp.split(' ').map(&:to_i)
end
c = Matrix.rows(a) * Matrix.rows(b)
c.to_a.each do |row|
  print row.join(' '), "\n"
end

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


signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
 
    ll n;
    cin>>n;
    ll ans=0;
    if(n<10){
        ans = n;
    }
    else if(n<100){
        ans=9;
    }
    else if(n<=999){
        ans += n-99 + 9;
    }
    else if(n<10000){
        ans = 909;
    }
    else if(n<=99999){
        ans = n-9090;
    }
    else ans = 90909;
    cout<<ans<<endl;
    
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    from fractions import gcd
    from functools import reduce
    return reduce(gcd, A)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


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

int main() {
  int64_t n, min, max;
  cin >> n >> min >> max;
  int64_t begin = (n - 1) * min + max;
  int64_t end   = (n - 1) * max + min;
  int64_t ans   = end - begin + 1;
  cout << (ans < 0 ? 0 : ans) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
    string s;
  	cin >> s;
  	for(int i = 0 ; i < 3 ; i++){
     	if(s[i] == '9')
          cout << 1;
      	else if(s[i] == '1')
          cout << 9;
      	else
          cout << s[i];
    }
 	return 0; 
}

Measured memory_bytes: 256
<?php

class Scanner
{
    private $arr = [];
    private $count = 0;
    private $pointer = 0;

    public function next()
    {
        if ($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(' ', $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        ++$this->pointer;

        return $result;
    }

    public function hasNext()
    {
        return $this->pointer < $this->count;
    }

    public function nextInt()
    {
        return (int) $this->next();
    }

    public function nextDouble()
    {
        return (float) $this->next();
    }
}

$sc = new Scanner();
$x = $sc->nextInt();
$y = $sc->nextInt();
$sum = 0;
$answer = 'No';

for($i=0;$i<$x+1;$i++){
    $sum = $i*2 + ($x-$i) * 4;
    if($sum == $y){
        $answer = 'Yes';
        break;
    }
}

echo $answer.PHP_EOL;

Measured memory_bytes: 16204
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class Main {
    public static void trace(int[] a, int n) {

        for (int i = 0; i < n; i++) {
            if (i > 0)
                System.out.print(" ");
            System.out.printf("%d", a[i]);
        }
        System.out.print("\n");
    }

    public static void sort(int[] data, int n) {
        int tmp, j;
        for (int i = 1; i < n; i++) {
            tmp = data[i];
            j = i - 1;
            while (j >= 0 && data[j] > tmp) {
                data[j + 1] = data[j];
                j--;
            }
            data[j + 1] = tmp;
            trace(data, n);

        }
    }

    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n;
        int[] data;
        String[] input_data;
        try {
            n = Integer.parseInt(br.readLine());
            data = new int[n];

            input_data = br.readLine().split(" ");
            for (int i = 0; i < input_data.length; i++)
                data[i] = Integer.parseInt(input_data[i]);

            trace(data, n);
            sort(data, n);

        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}


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

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> p(n);

    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        p.at(i) = make_pair(a, i);
    }

    sort(p.begin(), p.end());

    for(int i = 0; i < n; i++){
        cout << p.at(i).second + 1;
        if(i != n-1) cout << " ";
    }

    cout << endl;

}

Measured memory_bytes: 1664
import collections


def modinv(n, p):
    """
    逆元のmod pを求める
    """
    if n >= p:
        raise ValueError('p must be larger than n')
    return pow(n, p-2, p)


def prime_sieve(n):
    """
    n以下の素数を昇順に列挙する
    エラトステネスの篩 計算量O(Nlog(log(N)))
    """
    is_prime = [True for i in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return [i for i in range(2, n+1) if is_prime[i]]


def prime_factorization(it):
    """
    数値の素因数分解をリストで返すイテレータ
    エラトステネスの篩を応用する 計算量O(A+Nlog(log(N)))
    """
    n = max(it)
    factor = [1 for i in range(n+1)]
    factor[0] = 0
    factor[1] = 1
    for i in range(2, n+1):
        if factor[i] == 1:
            for j in range(i, n+1, i):
                factor[j] = i
    for a in it:
        if a < 2:
            yield list()
        else:
            prime_factors = list()
            while a != factor[a]:
                prime_factors.append(factor[a])
                a //= factor[a]
            prime_factors.append(factor[a])
            yield list(sorted(prime_factors))


def lcm(x, p=-1):
    """
    配列xに対する最小公倍数 LCM(x_1, x_2, ..., x_n) を求める
    p > 0のときはLCM mod pを返す
    """
    max_prime_counts = dict()
    for prime in prime_sieve(max(x)):
        max_prime_counts[prime] = 0
    pfs = prime_factorization(x)
    for pf in pfs:
        prime_count = collections.Counter(pf)
        for prime in prime_count.keys():
            max_prime_counts[prime] = max(max_prime_counts[prime], prime_count[prime])
    lcm_value = 1
    for prime, factor in max_prime_counts.items():
        if p > 0:
            lcm_value *= pow(prime, factor, p)
            lcm_value %= p
        else:
            lcm_value *= pow(prime, factor)
    return lcm_value


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, MOD=1000000007):
    bsum = 0
    for i in range(N):
        bsum += modinv(A[i], MOD)
        bsum %= MOD
    bsum *= lcm(A, p=MOD)
    bsum %= MOD
    return bsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Measured memory_bytes: 24768
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ld INF = (ld)10000000000000;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
int n, m;
int x[1 << 17];

int ans[1 << 17];

priority_queue<int, vector<int>, greater<int>>q;
vector<P> vr;

int main() {
	cin >> n >> m;
	rep(i, m) {
		cin >> x[i];
	}
	ans[1] = n - m;
	rep(i, m - 1) {
		if (x[i + 1] - x[i]-1 > 0)q.push(x[i + 1] - x[i] - 1);
	}
	//if (x[0] > 1)q.push(x[0] - 1);
	if (n - x[m - 1] > 0)q.push(n - x[m - 1]);
	Rep1(i, 2, n) {
		ans[i] = ans[i - 1] - q.size();
		while (!q.empty() && q.top() < i)q.pop();
		//cout << i << " " << ans[i] << endl;
	}
	rep1(i, n) {
		vr.push_back({ ans[i],i });
	}
	sort(vr.begin(), vr.end());
	int q; cin >> q;
	rep(aa, q) {
		int l; cin >> l;
		int id = lower_bound(vr.begin(), vr.end(), P{ l+1,-1 }) - vr.begin();
		if (id == 0)cout << -1 << endl;
		else {
			id--;
			int out = n - id;
			cout << out << endl;
		}
	}
	//stop
	return 0;
}




Measured memory_bytes: 4648
while(n = gets.chomp) != '0 0'
  a, b = n.split(' ').map(&:to_i)
  a.times do |x|
    _t = ''
    s = (x % 2).zero? ? '#.' : '.#'
    b.times { |y| _t += (y % 2).zero? ? s[0] : s[1] }
    puts _t
  end
  puts
end

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

#ifdef DEBUG
    #include "debug.h"
    #define dump(...)                                                              \
        DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
                << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
                << endl                                                            \
                << "    ",                                                         \
            dump_func(__VA_ARGS__)
#else
    #define dump(...)
#endif


// http://beet-aizu.hatenablog.com/entry/2018/04/08/145516
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

//////////////////

#define int long long
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
#define ALL(v) (v).begin(), (v).end()
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

//*
#define mod 1000000007 /*/
#define mod 998244353 //*/

typedef pair<int, int> P;
#define INF (1LL<<60)




void solve(){
    int X, N;
    cin >> X >> N;
    set<int> p;
    rep(i,N){
        int t; cin >> t;
        p.insert(t);
    }
    for(int d = 0; d<=100; d++){
        for(int f = -1; f<=1; f+=2){
            if(p.find(X+d*f) == p.end()){
                cout << X+d*f << endl;
                return;
            }
        }
    }
}


signed main(){
    cout << fixed << setprecision(18);
    cerr << fixed << setprecision(18);
    solve();
}


Measured memory_bytes: 3636
/*

*/
#include<iostream>
#include<iomanip>
#include<ios>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)
#define MAX_N 10000

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;
const ll MOD = ll(1e9+7);

int main(){
  int a;cin>>a;
  cout<<int(a+pow(a, 2)+pow(a, 3))<<endl;
  // system("read -n 1 -s -p \"Press any key to continue...\"");
}


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

string s,t,u;
int a,b;


int main()
{  
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>s>>t;
    cin>>a>>b;
    cin>>u;
    if(u==s)a-=1;
    else b-=1;
    cout<<a<<" "<<b<<"\n";
}

Measured memory_bytes: 256