akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<time.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
#define INF ((1<<30)-1+(1<<30))
#define INFLL (1LL << 60)
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(n); ++i)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }

long maxbit(long x) {
	x = x & 0xFFFF0000 ? x & 0xFFFF0000 : x;
	x = x & 0xFF00FF00 ? x & 0xFF00FF00 : x;
	x = x & 0xF0F0F0F0 ? x & 0xF0F0F0F0 : x;
	x = x & 0xCCCCCCCC ? x & 0xCCCCCCCC : x;
	x = x & 0xAAAAAAAA ? x & 0xAAAAAAAA : x;
	return x;
}

//セグメントツリー
//Range Minimum Query(RMQ)
//https://www.slideshare.net/iwiwi/ss-3578491
class SegmentTree {
	int leafNum;
	vector<int> tree;
	//戻り値：[a, b]の最小値
	//ノードkとkの区間l, r
	int query(int a, int b, int k, int l, int r) {
		if (r < a || l > b) return INF;			//kが[a,b]外
		if (l >= a && r <= b) return tree[k];	//kが[a,b]内
		int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);		//左側のノードへ
		int vr = query(a, b, k * 2 + 2, (l + r + 1) / 2, r);	//右側のノードへ
		return min(vl, vr);
	}
public:
	SegmentTree(int n) {
		leafNum = maxbit(n * 2 - 1);
		tree.resize(leafNum * 2 - 1, INF);
	}
	void update(int idx, int x) {
		idx += leafNum - 1;
		tree[idx] = x;
		while (idx > 0) {
			idx = (idx - 1) / 2;
			tree[idx] = min(tree[idx * 2 + 1], tree[idx * 2 + 2]);
		}
	}
	int query(int a, int b) {
		return query(a, b, 0, 0, leafNum - 1);
	}
};


int main()
{
	int N, Q; cin >> N >> Q;
	auto st = SegmentTree(N);
	rep(i, Q) {
		int c, x, y; cin >> c >> x >> y;
		if (c) {
			cout << st.query(x, y) << endl;
		}
		else {
			st.update(x, y);
		}
	}
	return 0;
}




Measured memory_bytes: 3812
#[allow(unused_imports)]
use std::{cmp::Reverse, collections::*};

#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[allow(unused_imports)]
use itertools::Itertools;

#[allow(unused_imports)]
use num::Integer;

#[fastout]
pub fn main() {
    input! {
        n: usize, m: usize,
        p: [(Usize1, Usize1); m],
    }
    let mut ids: Vec<_> = (0..n).collect();
    let mut c_ids: Vec<_> = (0..n)
        .map(|i| {
            let mut t = HashSet::new();
            t.insert(i);
            t
        })
        .collect();
    for (a, b) in p {
        if ids[a] != ids[b] {
            let aid = ids[a];
            let bid = ids[b];
            if c_ids[aid].len() < c_ids[bid].len() {
                let is = c_ids[aid].clone();
                is.iter().for_each(|&i| {
                    ids[i] = bid;
                    c_ids[bid].insert(i);
                });
                c_ids[aid].clear();
            } else {
                let is = c_ids[bid].clone();
                is.iter().for_each(|&i| {
                    ids[i] = aid;
                    c_ids[aid].insert(i);
                });
                c_ids[bid].clear();
            }
        }
    }
    let mut count = HashMap::new();
    ids.iter().for_each(|&id| {
        *count.entry(id).or_insert(0) += 1;
    });
    println!("{}", count.values().max().unwrap());
}


Measured memory_bytes: 40800
n, y = map(int, input().split())
A = [-1, -1, -1]
for i in range(n + 1):
    for j in range(n - i + 1):
        if y == 10000 * i + 5000 * j + 1000 * (n - i - j):
            A = [i, j, n - i - j]
            break
    else:
        continue
    break

print('{} {} {}'.format(A[0], A[1], A[2]))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int cnt,i,j,k,l,m,n,flg,xx,yy,t,f,c,x,y,max;
	int dx[9]={0,1,1,1,0,-1,-1,-1,0},dy[9]={-1,-1,0,1,1,1,0,-1,-1};
	char fl[1000][1001],em[2][3],a[]="JOI";
	cin>>m>>n;
	for(i=0;i<m;i++) cin>>fl[i];
	for(i=0;i<2;i++) cin>>em[i];
	cnt=0;
	for(i=0;i<m-1;i++){
		for(j=0;j<n-1;j++){
			if(fl[i][j]==em[0][0]){
				flg=1;
				for(k=2;k<=4;k++){
					xx=j+dx[k]; yy=i+dy[k];
					if(fl[yy][xx]!=em[dy[k]][dx[k]]){
						flg=0;
						break;
					}
				}
				if(flg==1){
//					cout<<1<<' '<<i<<' '<<j<<endl;
					cnt++;
				}
			}
		}
	}
	max=cnt;
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			for(k=0;k<3;k++){
				c=0;
				if(em[0][0]==a[k]&&a[k]!=fl[i][j]&&i<m-1&&j<n-1){
					flg=1;
					for(l=2;l<=4;l++){
						xx=j+dx[l]; yy=i+dy[l];
						if(fl[yy][xx]!=em[dy[l]][dx[l]]){
							flg=0;
							break;
						}
					}
					if(flg==1){
						c++;
					}
				}
				if(em[0][1]==a[k]&&a[k]!=fl[i][j]&&i<m-1&&j!=0){
					flg=1;
					for(l=4;l<=6;l++){
						xx=j+dx[l]; yy=i+dy[l];
						if(fl[yy][xx]!=em[dy[l]][1+dx[l]]){
							flg=0;
							break;
						}
					}
					if(flg==1){
						c++;
					}
				}
				if(em[1][1]==a[k]&&a[k]!=fl[i][j]&&i!=0&&j!=0){
					flg=1;
					for(l=6;l<=8;l++){
						xx=j+dx[l]; yy=i+dy[l];
						if(fl[yy][xx]!=em[1+dy[l]][1+dx[l]]){
							flg=0;
							break;
						}
					}
					if(flg==1){
						c++;
					}
				}
				if(em[1][0]==a[k]&&a[k]!=fl[i][j]&&i!=0&&j<n-1){
					flg=1;
					for(l=0;l<=2;l++){
						xx=j+dx[l]; yy=i+dy[l];
						if(fl[yy][xx]!=em[1+dy[l]][dx[l]]){
							flg=0;
							break;
						}
					}
					if(flg==1){
						c++;
					}
				}
				if(max<cnt+c) max=cnt+c;
			}
		}
	}
	cout<<max<<endl;
	return 0;
}

Measured memory_bytes: 4072
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,l,i;
  cin>>n>>l;
  vector <string> v;
  for(i=0;i<n;i++)
  {
    string s;
    cin>>s;
    v.push_back(s);
  }

  sort(v.begin(),v.end());
  for(i=0;i<n;i++)
    cout<<v[i];
  return 0;
  
}

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

int n, M[MAX][MAX];

void dijkstra()
{
    int minv;
    int d[MAX], color[MAX];

    for (int i = 0; i < n; i++)
    {
        d[i] = INFTY;
        color[i] = WHITE;
    }

    d[0] = 0;
    color[0] = GRAY;
    while(true)
    {
        minv = INFTY;
        int u = -1;
        for (int i = 0; i < n; i++)
        {
            if (color[i] != BLACK && d[i] < minv)
            {
                u = i;
                minv = d[i];
            }
        }
        if (u == -1) break;
        color[u] = BLACK;
        for (int v = 0; v < n; v++)
        {
            if (color[v] != BLACK && M[u][v] != INFTY)
            {
                if (d[v] > d[u] + M[u][v])
                {
                    d[v] = d[u] + M[u][v];
                    color[v] = GRAY;
                }
            }
        }
    }

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

}

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

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

    dijkstra();
    
    return 0;
}


Measured memory_bytes: 3132
#include <iostream>
#include <string>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;

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

  string a, b; cin >> a >> b;
  string ans;
  if(a.size() < b.size()) ans = "LESS";
  else if(a.size() < b.size()) ans = "GREATER";
  else {
    if(a < b) ans = "LESS";
    else if(a > b) ans = "GREATER";
    else ans = "EQUAL";
  }

  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

long solve(long w, long h) {
    if (w % 3 == 0) return 0l;
    long w3 = w / 3l;
    long h1 = h / 2l;
    long h2 = h - h1;

    long a1 = (w - w3) * h2 - w3 * h;
    long a2 = - (w - w3 - 1l) * h1 + (w3 + 1l) * h;
    long a = min(a1, a2);
    return min(h, a);
}

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

  long w, h;
  cin >> w >> h;

  cout << min(solve(w, h), solve(h, w)) << endl;
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;
int main(void){
	int M, N;
	int board[1001];
	int dice[1001];
	int pos;
	int times;
	while(cin >> N >> M, N || M){
		pos = 1;
		times = 0;
		for (int i = 1; i <= N; i++)cin >> board[i];
		for (int i = 1; i <= M; i++)cin >> dice[i];

		while(pos < N){
			times++;
			pos += dice[times];
			if(N <= pos)break;
			pos += board[pos];
		}
		cout << times << endl;
	}
}

Measured memory_bytes: 1164
# 操作回数を入力する
N = int(input())
# 言う数字を入力する
list_A = [int(input()) for _ in range(N)]
# 数字を昇順に並べる
list_A.sort()
# 終了後に残っている数字の数を設定する
ans = 0
# 直前の数字を設定する
num = 0
# ある数字が連続している回数を設定する
count = 0
# 昇順に並んだ各数字Aについて、、
for A in list_A:
    # 数字Aが直前の数字と同じ場合、、
    if A == num:
        # 連続回数を増やす
        count += 1
    # 数字Aが直前の数字と異なる場合、、
    else:
        # 直前の数字の連続回数が奇数の場合、、
        if count % 2 != 0:
            # 終了後に残っている数字の数を増やす
            ans += 1
        # 直前の数字と連続回数を更新する
        num = A
        count = 1        
# 最後の数字について、連続回数が奇数の場合、終了後に残っている数字の数を増やす
if count % 2 != 0:
    ans += 1
# 結果を出力する
print(ans)

Measured memory_bytes: 7388
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long ,long long>pll;

ll gcd(ll a, ll b) {return (!b ? a : gcd(b, a % b));}
ll lcm(ll a, ll b) {return ((a*b)/gcd(a,b));}
bool cmp(int a,int b){return a>b;}

const ll mod = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const ld pi = 3.141592653589793;

long long modpow(long long n, long long k, long long mod)
{
if (k == 0) return 1;
long long r = modpow(n * n % mod, k >> 1, mod);
if (k & 1) r = r * n % mod;
return r;
}

void solve(){
   string s,t;
   cin >> s >> t;
   vector< vector<int> >pos(26);
   for(int i = 0;i<s.size();i++){
    pos[s[i]-'a'].push_back(i+1);
   }
   int now = 0;
   ll ans = 0;
   for(int i = 0;i<t.size();i++){
    if(pos[t[i]-'a'].size()==0) {cout << -1;return;}
    auto p = upper_bound(pos[t[i]-'a'].begin(),pos[t[i]-'a'].end(),now);
    if(p!=pos[t[i]-'a'].end()){
        ans += (*p-now);
        now = *p;
    }
    else{
        p = pos[t[i]-'a'].begin();
        ans += s.size()-now+*p;
        now = *p;
    }
   }
   cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 4156
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>
#include <numeric>

using namespace std;

int main(){

    int N, D;
    cin >> N >> D;

    cout << (int)(ceil((double)N / (2 * D + 1))) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <map>
#include <queue>
#include <numeric>
#include <climits>
#include <functional>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
//using ll = unsigned long long;
//const ll mod = 1000000007;
string al = "abcdefghijklmnopqrstuvwxyz";
//bool less_sec(const pair<int, int>&a, const pair<int, int>&b) {
//	return a.second > b.second;
//}
int n, p;
int arr[51];
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	while (cin >> n >> p, n&&p) {
		int table = p;
		for (int i = 0; i < n; ++i) {
			arr[i] = 0;
		}
		int flag = 0;
		while (true) {
			if (table == 0) {
				if (arr[flag] != 0) {
					table = arr[flag];
					arr[flag] = 0;
				}

			}
			else {
				arr[flag]++;
				table--;
			}
			if (arr[flag] == p) break;
			flag++;
            if(flag == n) flag = 0;
		}
		cout << flag << endl;
	}
	return 0;
}


Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)

void chmax(ll& a, ll b) { a = max(a, b); }
void chmin(ll& a, ll b) { a = min(a, b); }

using P = pair<int, int>;

const int MAX_N = 1e5+5;
const int INF = 1001001001;

vector<int> a, ans;
int dp[MAX_N][3];

ll modnum = 1e9+7;


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

    vector<vector<int>> dp(n, vector<int>(n,0));
    for(int i=n-1; i >= 0; i--) for(int j=n-1; j >= 0; j--) {
        if(s[i] == s[j]) {
            dp[i][j] += 1;
            if(i < n-1 && j < n-1) {
                dp[i][j] += dp[i+1][j+1];
            }
        } else {
            dp[i][j] = 0;
        }
    }

    int ans = 0;
    rep(i, n) rep(j, n) {
        if(dp[i][j] < j-i+1) ans = max(ans, dp[i][j]);
    }

    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 98176
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000005
#define VMAX 10005

int A[MAX], B[MAX];
int C[VMAX+1];

int main(){
  
  //unsigned short *A, *B;

  int n, i, j;

  scanf("%d", &n);

  //A = malloc(sizeof(short)*n+1);
  //B = malloc(sizeof(short)*n+1);

  for(i=1;i<=n;i++){
       scanf("%d",A+i);
       //scanf("%d",&A[i]);
     //printf("%d ",*(A+i));
       // C[i]=0;
  }
  //C[n]=0;

  //printf("\n");
  for(j=1;j<=n;j++){
    C[A[j]]++;
  }
  /*
  for(j=0;j<=n;j++){
    printf("%d ",j);
  }   
  printf("\n");
  
  for(j=0;j<=n;j++){
    printf("%d ",C[j]);
  }   
  printf("\n");
  */
  
  for(i=1;i<=VMAX;i++){
    C[i] += C[i-1];
  }
 
  
  /*

  for(j=0;j<=n;j++){
    printf("%d ",C[j]);
  }
  printf("\n");
  */
    
  for(j=n;j>0;j--){
    B[C[A[j]]]= A[j];
    C[A[j]]--;
  }
    
  for(j=1;j<=n;j++){
    printf("%d",B[j]);
    if(j!=n)printf(" ");
  }
  printf("\n");
  
  return 0;
}



Measured memory_bytes: 17448
def check():
  n = int(input())
  if n <= 9:
    return 'Yes'
  elif n > 81:
    return 'No'
  else:
    for i in range(2, 10):
      if n % i == 0 and n / i <= 9:
        return 'Yes'
    return 'No'

print(check())


Measured memory_bytes: 2940
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

const MODULO: usize = 1_000_000_007;

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let n: usize = scan(tokens);
    let k: usize = scan(tokens);
    let mut e: Vec<Vec<usize>> = vec![Vec::new(); n + 1];
    for _ in 0..n - 1 {
        let a: usize = scan(tokens);
        let b: usize = scan(tokens);
        e[a].push(b);
        e[b].push(a);
    }
    let mut f: Vec<usize> = vec![0; k + 1];
    f[0] = 1;
    for i in 1..k + 1 {
        f[i] = i * f[i - 1] % MODULO;
    }
    fn dfs(i: usize, p: usize, k: usize, e: &Vec<Vec<usize>>, f: &Vec<usize>) -> usize {
        if e[i].len() >= k {
            return 0;
        }
        let mut res = if p == 0 {
            f[k - 1] * inverse(f[(k - 1) - e[i].len()]) % MODULO
        } else {
            f[k - 2] * inverse(f[(k - 2) - (e[i].len() - 1)]) % MODULO
        };
        for &j in &e[i] {
            if j == p {
                continue;
            }
            res = res * dfs(j, i, k, e, f) % MODULO;
        }
        res
    }
    println!("{}", k * dfs(1, 0, k, &e, &f) % MODULO);
}

fn power(mut b: usize, mut e: usize) -> usize {
    let mut a = 1;
    while e != 0 {
        if e & 1 != 0 {
            a = a * b % MODULO;
        }
        b = b * b % MODULO;
        e >>= 1;
    }
    a
}

fn inverse(x: usize) -> usize {
    power(x, MODULO - 2)
}


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

using ll = long long;

int
main(int argc, char** argv) {
    int N;
    std::cin >> N;

    ll ans = 0;
    int minA = 0x7fffffff;
    std::vector<int> A(N);
    int neg = 0;
    for (int i = 0; i < N; i++) {
       std::cin >> A[i];
       ans += std::abs(A[i]);
       if (A[i] < 0) neg++;
       minA = std::min(minA, std::abs(A[i]));
    }

    if ((neg % 2) != 0) {
       ans -= std::abs(minA) * 2;
    }

    std::printf("%lld\n", ans);
    return 0;
}

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

const int N = 100010;

int n, c[N];
int x[N], y[N], deg[N], g[N];
int cnt, head[N];
struct edge {int to, nxt, id;} e[N << 1];

void ins(int u, int v, int id) {
	e[++cnt] = (edge) {v, head[u], id};
	head[u] = cnt;
} 

void dfs(int u, int fa, int col) {
	int now = 0;
	for(int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa) continue;
		++now;
		if(now == col) ++now;
		g[e[i].id] = now;
		dfs(v, u, now);
	}
}

int main() {
	cin >> n;
	for(int i = 1; i < n; ++i) {
		cin >> x[i] >> y[i];
		deg[x[i]]++; deg[y[i]]++;
		ins(x[i], y[i], i), ins(y[i], x[i], i);
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i) 
		if(deg[i] > deg[ans]) ans = i;
	cout << deg[ans] << endl;
	dfs(ans, ans, 0);
	for(int i = 1; i < n; ++i) printf("%d\n", g[i]);
} 

Measured memory_bytes: 6528
/*
	Name:
	Author: xiaruize
	Date:
*/
#pragma GCC optimize(2)
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
using namespace std;
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define ll long long
#define form(i,j,n) for(int i=int(j);i<=int(n);i++)
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define pis pair<int,string>
#define sec second
#define sz(a) int((a).size())

inline int read()
{
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*f;
}

int main()
{
 	ios::sync_with_stdio(false);
	cin.tie(0);
 	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ll n;
	cin>>n;
	ll m=n;
	ll ans=0;
	for(ll i=2;i*i<=m;i++)
	{
		ll cnt=0,k=0;
		while(n%i==0)
		{
			n/=i;
			cnt++;
			if(cnt>k)
			{
				ans++;
				k=cnt;
				cnt=0;
			}
		}
	}
	if(n!=1)
	{
		ans++;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;
typedef priority_queue<int, vector<int>, greater<int>> PQ;

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
// 2項係数を求める
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main(){
    int N, K; cin >> N >> K;
    vector<ll> a(N);
    rep(i,N) cin >> a[i];
    sort(a.begin(), a.end());

    combination c(N+5);

    mint ans = 0;
    rep(i,N){
        mint now = c(i, K-1);
        ans += now*a[i];
    }

    reverse(a.begin(), a.end());

    rep(i,N){
        mint now = c(i, K-1);
        ans -= now*a[i];
    }

    cout << ans.x << endl;
}

Measured memory_bytes: 5528
#include <bits/stdc++.h>
#define int llint
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, a, n) &((x)[a]), &((x)[n])
#define ADD(a, b) ((((a+MOD)%MOD)+((b+MOD)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define PI 3.1415926535897
#define EPS (1e-10)
#define INF INT_MAX
#define INFLL LLONG_MAX
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using MCI = std::map<char, int>;
using VPII = std::vector<PII>;
using namespace std;


int N, M;
string S, T;


int gcd(int a, int b){
	return a%b ? gcd(b, a%b) : b;
}


int lcm(int a, int b){
	return a*b/gcd(a, b);
}


int solve(){
	int n = lcm(N, M);
	int a = n/N;
	int b = n/M;
	int x = lcm(a, b);
	repif(i, 0, i*x < n){
		int y = i*x;
		if(S[y/a] != T[y/b]) return -1;
	}
	return n;
}


signed main(){
	cin >> N >> M;
	cin >> S >> T;

	cout << solve() << endl;

	return 0;
}

Measured memory_bytes: 512
N = int(input())
S = input()


Flag = False

for dp,dq in [[0,0],[0,1],[1,0],[1,1]]:
  D = [dq,dp]
  for v in S:
    #D.append( "S" if p==1 else "W" )
    if v == "o" and D[-1] == 1:
      D.append(D[-2])
    elif v == "o" and D[-1] == 0:
      D.append(1-D[-2])
    elif v == "x" and D[-1] == 1:
      D.append(1-D[-2])
    elif v == "x" and D[-1] == 0:
      D.append(D[-2])
  if ( D[0]==D[-2] and D[1]==D[-1] ):
    Flag = True
    break
if ( Flag ):
  print ( "".join( map(lambda x:"S" if x==1 else "W",D[1:-1]) ) )
else:
  print (-1)

Measured memory_bytes: 55972
n,x=map(int,input().split())
*l, =  map(int, input().split())

d = [0]
count = 0
for i in range(n):
    d.append(d[i]+l[i])
for i in range(n+1):
    if d[i] <= x:
        count += 1
        
print(count)


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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

ll mod = 1000000007;

int main() {

    int N,K;
    Scd2(N,K);

    static vector<vl> dp(N+1,vl(K*2+3,0));
    dp[0][0] = 1;

    int a;
    Rep(i,N){
        Scd(a);
        Rep(j,K+1){
            dp[i+1][j] += dp[i][j];
            dp[i+1][j+a+1] += mod - dp[i][j];
        }
        Repe(j,K+1,1){
            dp[i+1][j] += dp[i+1][j-1];
            dp[i+1][j] %= mod;
        }
    }

    printf ("%lld\n", dp[N][K] );

    return 0;
}



Measured memory_bytes: 159744
package main

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

func main() {
	n := oneInt()
	as := scanNums(n)

	ans := calc(as)

	fmt.Println(ans)
}

func calc(as []int) int64 {
	var minusCount int
	var answer int64

	minAbs := abs(as[0])
	for _, ai := range as {
		if ai < 0 {
			minusCount++
		}
		answer += int64(abs(ai))
		minAbs = min(minAbs, abs(ai))
	}
	if minusCount%2 == 0 {
		return answer
	} else {

		answer += int64(minAbs * -2)
	}
	return answer
}

func oneInt() int {
	var a int
	fmt.Scan(&a)
	return a
}

func nextWord(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func scanNums(n int) (nums []int) {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	for i := 0; i < n; i++ {
		s := nextWord(sc)
		num, _ := strconv.Atoi(s)
		nums = append(nums, num)
	}
	return nums
}

func abs(a int) int {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}


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

int main() {
    string n;
    cin >> n;
    int s = 0;
    for (char c : n) s += c - '0';
    if (s % 9 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3732
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#define rep(i, s, g) for (i = s; i <= g; i++)
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

int main(void)
{
    char c;

    cin >> c;

    cout << (char)(c + 1) << endl;
}

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

namespace AOJ2
{
    class Program
    {
        static void Main()
        {
            var cardNum = int.Parse(Console.ReadLine());
            var cardArray = Enumerable.Range(1, cardNum * 2);
            var comNum = int.Parse(Console.ReadLine());
            for (int i = 0; i < comNum; i++)
            {
                var com = int.Parse(Console.ReadLine());
                if (com == 0)
                {
                    cardArray = cardArray.Take(cardNum).ZipA(cardArray.Skip(cardNum).Take(cardNum), (f, s) => new int[] { f, s })
                        .SelectMany(x => x.Select(y => y)).ToArray();
                }
                else
                {
                    cardArray = cardArray.Skip(com).Take(cardNum * 2 - com).Concat(cardArray.Take(com)).ToArray();
                }
            }
            foreach (var item in cardArray)
            {
                Console.WriteLine(item);
            }
        }

    }
    public static class Util
    {

        public static IEnumerable<TResult> ZipA<TFirst, TSecond, TResult>
    (this IEnumerable<TFirst> first,
    IEnumerable<TSecond> second,
    Func<TFirst, TSecond, TResult> resultSelector)
        {
            if (first == null) throw new ArgumentNullException("first");
            if (second == null) throw new ArgumentNullException("second");
            if (resultSelector == null) throw new ArgumentNullException("resultSelector");
            return ZipIterator(first, second, resultSelector);
        }
        private static IEnumerable<TResult> ZipIterator<TFirst, TSecond, TResult>
    (IEnumerable<TFirst> first,
    IEnumerable<TSecond> second,
    Func<TFirst, TSecond, TResult> resultSelector)
        {
            using (IEnumerator<TFirst> e1 = first.GetEnumerator())
            using (IEnumerator<TSecond> e2 = second.GetEnumerator())
                while (e1.MoveNext() && e2.MoveNext())
                    yield return resultSelector(e1.Current, e2.Current);
        }

    }
}

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

const int mod=1e9+7;
const int inf=-1;
const int sz=2e5;

#define pi acos(-1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define gap ' '
#define lb lower_bound
#define ub upper_bound
#define clr(x) memset(x,0,sizeof(x))
#define all(x) sort(x.begin(),x.end())
#define rall(x) reverse(x.begin(),x.end())
#define dbg puts("finding wrong")
#define case(x,y) printf("Case %lld: %lld\n",++x,y)
#define fastio ios::sync_with_stdio(false);cin.tie(0)


int ar[sz];

int main()
{
  fastio;
  ll t, a, b, c, ans=0, i, n;
  
  string s;
  cin>>s;
  ll mx=0;
  for(i=0; i<s.size(); i++)
  {
      if(s[i]=='R')ans++;
      else ans=0;
      mx=max(mx,ans);
  }
  cout<<mx<<endl;
}


Measured memory_bytes: 3620
# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import scipy as scp

# 入力の受け取り
a,b,c  = map(int,input().split())

ans = 0 if c-(a-b) < 0 else c-(a-b)

print(ans)
# print("{:.10f}".format(ans))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する



Measured memory_bytes: 2940
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <queue>
#include <set>
#include <stdio.h>
#include <climits>
#include <map>
#include <time.h>
#include <random>
//#include "rubo.h"

#define dbl long double
#define pb push_back
#define mp make_pair
#define SQ(x) (x)*(x)
#define ll long long
#define ull unsigned long long
#define vc vector
#define X first
#define Y second
//#define in ll
#define pll pair<ll,ll>
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define loop(xxx, yyy) for(int xxx = 0; xxx < yyy; xxx++)
//#define printf(fmt...) (0)
//#define puts(fmt...) (0)

//#include "rubo.h"

using namespace std;

const int N = 222222;

int n, m;
vc<int> g[N];

vc<char> used(N, false);
vc<int> color(N, -1);

void dfs(int v, int c) {
	used[v] = true;
	color[v] = c;

	for (int to : g[v]) {
		if (!used[to]) {
			dfs(to, 1 - c);
		}
	}
}

int main() {
	scanf("%d%d", &n,&m);
	loop(i, m) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	dfs(0, 0);

	bool bipartite = true;
	loop(v, n) 
		for (int u : g[v]) 
			if (color[v] == color[u])
				bipartite = false;
	
	ll ans;


	if (bipartite) {
		ll c0 = count(all(color), 0);
		ll c1 = count(all(color), 1);
		ans = c0*c1 - m;
	}
	else {
		ans = (n*(n - 1ll)) / 2 - m;
	}

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

	return 0;
}


Measured memory_bytes: 10112
#include<stdio.h>
int main(void)
{
    int N,K,h[100000],b=0;
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++)
    {
        scanf("%d",&h[i]);
        if(K<=h[i]){
            b=b+1;
        }
    }
    printf("%d\n",b);
    return 0;
}

Measured memory_bytes: 512
program caddi2018b
  implicit none
  integer n, h, w, i
  integer, dimension(:), allocatable :: a, b

  read *, n, h, w
  allocate(a(n), b(n))

  do i = 1,n
     read *, a(i), b(i)
  end do

  print '(i0)', count(a.ge.h.and.b.ge.w)
end program caddi2018b


Measured memory_bytes: 256
#include<stdio.h>

#include<stdlib.h>


#include<string.h>


int main(void){





char num_str[1002];


int num;


long sum = 0;


int i;


char tmp;


while (1){


fgets(num_str,sizeof(num_str),stdin);


if(num_str[0] == '0') break;


for(i=0;i<strlen(num_str)-1;i++){


tmp = num_str[i];


num=atoi(&tmp);


sum=sum+num;


}


printf("%ld\n",sum);


sum=0;


memset(num_str,1002,0);


}


return 0;


}

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

int main()
{
  int n , b , B , x ;
  cin >> n ;
  vector<int> A(n);
  vector<int> C(n);
  
  for(int i=0; i<n; i++)
    cin >> A.at(i) ;
  for(int i=0; i<n;i++)
  {
    cin >> B ;
    b += B ;
  }
  for(int i=0 ; i<n; i++)
    cin >> C.at(i) ;
  
  for(int i=0; i<n-1; i++)
  {
    if(A.at(i) + 1 ==A.at(i+1)) 
    {
      x = A.at(i) ;
      b += C.at(x-1) ;
    }
  }
  
  cout << b << endl ;
}


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

#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long



using namespace std;

void file(){
	#ifndef ONLINE_JUDGE
    	freopen("in.txt", "r", stdin);
	#endif
}
int tc;
const int N=5e5+5,M=2e6+5,MOD=1e9+7,OO=1e9;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//file();	
 	
 	deque<char>ans;
 	int n;
 	string a;
 	cin>>n>>a;

 	for(auto c : a)ans.pb(c);
 	int cnt = 0;
 	for(auto c : a){
 		if(c == '(')cnt++;
 		else	cnt--;
 		if(cnt==-1)cnt++,ans.push_front('(');
 	}
 	while(cnt--)ans.pb(')');
 	while(sz(ans))cout<<ans.front(),ans.pop_front();
}		


Measured memory_bytes: 256
MOD = 10**9 + 7


def main():
    S = input()

    dp = [[0] * 13 for _ in range(len(S) + 1)]
    dp[0][0] = 1

    for i, s in enumerate(S):
        c = int(s) if s != '?' else -1

        for j in range(10):
            if c in (-1, j):
                for ki in range(13):
                    dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]

        for j, v in enumerate(dp[i + 1]):
            dp[i + 1][j] = v % MOD

    print(dp[-1][5])


if __name__ == '__main__':
    main()


Measured memory_bytes: 62556
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <iomanip>
#include <stack>
  
using namespace std;

#define pi 3.141592653589793

int StrToInt(string str)
{
	int i, j, num = 0, ans = 0, l = str.length();
	if(str[0] == '-'){
		for(i = l - 1; i >= 1; i--){
			num = str[i] - '0';
			for(j = 0; j < l - 1 - i; j++){
				num = num * 10;
			}
			ans -= num;
		}
	} else {
		for(i = l - 1; i >= 0; i--){
			num = str[i] - '0';
			for(j = 0; j < l - 1 - i; j++){
				num = num * 10;
			}
			ans += num;
		}
	}
	return ans;
}

string IntToStr(int n)
{
	string s = "";
	int i = 0;
	if(n < 0){
		s += '-';
		n = abs(n);
		while(n / (int)pow(10, i) != 0){
			i++;
		}
		for(int j = i - 1; j >= 0; j--){
			s += (n / (int)pow(10, j)) + '0';
			n = n % (int)pow(10, j);
		}
	} else if(n == 0) return "0";
	else{
		while(n / (int)pow(10, i) != 0){
			i++;
		}
		for(int j = i - 1; j >= 0; j--){
			s += (n / (int)pow(10, j)) + '0';
			n = n % (int)pow(10, j);
		}
	}
	return s;
}

string solve(string a[], int n)
{
	int xrange[2] = {-1000000001, 1000000001};
	// xのとりうる範囲
	int is_x_in[2] = {0, 0};
	// 0がtrue→偶数番目にxあり、1がtrue→奇数番目にxあり
	if(a[1] == "x"){
		if(a[2] == "x") return "none";
		else xrange[1] = min(StrToInt(a[2]), xrange[1]);
		is_x_in[1] = 1;
	} else {
		if(a[2] != "x" && StrToInt(a[1]) >= StrToInt(a[2])) return "none";
	}
	for(int i = 2; i < n; i++){
		if(a[i] == "x"){
			if(a[i - 1] == "x" || a[i + 1] == "x") return "none";
			else {
				is_x_in[i % 2] = 1;
				if(i % 2 == 0) xrange[0] = max(max(StrToInt(a[i - 1]), StrToInt(a[i + 1])), xrange[0]);
				else xrange[1] = min(min(StrToInt(a[i - 1]), StrToInt(a[i + 1])), xrange[1]);
			}
		} else if(a[i - 1] == "x" || a[i + 1] == "x") continue;
		else {
			if(i % 2 == 0 && max(StrToInt(a[i - 1]), StrToInt(a[i + 1])) >= StrToInt(a[i])) return "none";
			else if(i % 2 == 1 && min(StrToInt(a[i - 1]), StrToInt(a[i + 1])) <= StrToInt(a[i])) return "none";
		}
	}
	if(a[n] == "x"){
		if(a[n - 1] != "x"){
			if(n % 2 == 0){
				xrange[0] = max(StrToInt(a[n - 1]), xrange[0]);
				is_x_in[0] = 1;
			}
			else{
				xrange[1] = min(StrToInt(a[n - 1]), xrange[1]);
				is_x_in[1] = 1;
			}
		}
	} else {
		if(a[n - 1] != "x"){
			if((n % 2 == 0 && StrToInt(a[n]) <= StrToInt(a[n - 1])) || (n % 2 == 1 && StrToInt(a[n]) >= StrToInt(a[n - 1]))) return "none";
		}
	}
	if(is_x_in[0] ^ is_x_in[1]) return "ambiguous";
	else if(!is_x_in[0] && !is_x_in[1]) return "ambiguous";
	else {
		if(xrange[1] - xrange[0] > 2) return "ambiguous";
		else if(xrange[1] - xrange[0] == 2) return IntToStr(xrange[1] - 1);
		else return "none";
	}
}

int main()
{
	int n;
	while(1){
		cin >> n;
		if(n == 0) break;
		string input[1001];
		for(int i = 1; i < n + 1; i++){
			cin >> input[i];
		}
		cout << solve(input, n) << endl;
	}
	return 0;
}

Measured memory_bytes: 1360
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
co_to_ind = {}
A = []
B = []
for _ in range(n):
    a, b = LI()
    A += [a]
    B += [b]

S = sorted(A)
co_to_ind = {x:i for i, x in enumerate(S)}
X = [0] * (n + 1)
G = [[] for _ in range(n + 1)]

for i in range(n):
    X[co_to_ind[A[i]]] += B[i]

for i in range(n, 0, -1):
    X[i] ^= X[i - 1]

for i in range(m):
    l, r = LI()
    l = bisect_left(S, l)
    r = bisect_left(S, r + 1)
    G[l] += [(r, i)]
    G[r] += [(l, i)]

ans = []
visited = [0] * (n + 1)
def dfs(u):
    visited[u] = 1
    for v, e in G[u]:
        if visited[v]: continue
        dfs(v)
        if X[v]:
            ans.append(e + 1)
            X[u] ^= 1


for i in range(n + 1):
    if visited[i]: continue
    dfs(i)
    if X[i]:
        print(-1)
        exit()


ans.sort()
print(len(ans))
print(*ans)







Measured memory_bytes: 142564
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
long long int lis[2000003];
long long int yakulis[2000003];
long long int gcd(long long int a,long long int b){
    if(!b)return a;
    return gcd(b,a%b);
}
int main(){
    int N;
    cin>>N;
    for(int i=0;i<N;i++)cin>>lis[i];
    sort(lis,lis+N);
    int flg=1;
    for(int i=0;i<N-1;i++){
        if(lis[i]==lis[i+1]&&lis[i]!=1)flg=0;
    }
    for(long long int i=0;i<N;i++){

        for(long long int j=1;j*j<=lis[i];j++){

            if(lis[i]%j==0){
                    //printf("[%lld]noyakusuu[%lld]nituite\n",lis[i],j);
                yakulis[j]++;
                if(j*j!=lis[i])yakulis[lis[i]/j]++;
                if(1<yakulis[j]&&j!=1)flg=0;
                if(1<yakulis[lis[i]/j]&&lis[i]/j!=1)flg=0;
            }
            /*
            if(yakulis[lis[i]]==1)flg=0;
            else{
                int moto=lis[i];
                for(int j=moto;j<1000003;j+=moto){
                    if(yakulis[i]=1)flg=0;
                    yakulis[j]=1;
                }
            }
            */
        }
        if(flg==0)break;
    }
    if(flg==1){
        cout<<"pairwise coprime"<<endl;
        return 0;
    }
    long long int pa=gcd(lis[0],lis[1]);
    for(int i=2;i<N;i++){
        pa=gcd(lis[i],pa);
    }
    if(pa==1)cout<<"setwise coprime"<<endl;
    else cout<<"not coprime"<<endl;
    return 0;
}


Measured memory_bytes: 11580
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, student;
  cin >> N;
  vector<int> vec(N);
  for(int i = 1; i <= N; i++){
    cin >> student;
    vec.at(student-1) = i;
  }
  for(int i = 0; i < N; i++){
    cout << vec.at(i) << " ";
  }
}

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



int main() {
  int N;
  long M;
  M=0;
  cin>>N;
  vector<int> K(N+1);
  for(int i=1;i<N+1;i++){
    K.at(i)=i;
  }
  for(int i=1;i<N+1;i++){
    if(K.at(i)%3==0 || K.at(i)%5==0){
      K.at(i)=0;
    }
  }
  for(int i=1;i<N+1;i++){
    M+=K.at(i);
  }
  cout<<M<<endl;
  

}


Measured memory_bytes: 7212
n, m = map(int, input().split())
cs = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    cs[i][i] = 0
es = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    es.append((a, b, c))
    cs[a][b] = cs[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            cs[i][j] = min(cs[i][j], cs[i][k] + cs[k][j])
res = 0
for a, b, c in es:
    if cs[a][b] != c:
        res += 1
print(res)

Measured memory_bytes: 3440
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
using namespace std;
typedef long long ll;
typedef double db;
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
#define cmax(a,b) (a=(a>b)?a:b)
#define cmin(a,b) (a=(a<b)?a:b)
const int N=1e6+5,mo=1e9+7;
int n,m,K,i,j,k,q1,q2;
ll f[2][2005][2],sum[2005];
int ans;
int main()
{
    scanf("%d %d %d",&n,&m,&K);
    m--;K--;
    q1=0;
    q2=1;
    f[0][0][0]=1;
    fo(i,1,max(n,m)*2)
    {
        fo(j,0,n) sum[j+1]=(sum[j-1+1]+f[q1][j][0]+f[q1][j][1])%mo;
        fo(j,0,n)
        {
            f[q2][j][0]=(sum[j+1]-sum[j-1+1])%mo;
            k=max(0,j-K);
            f[q2][j][1]=(sum[j-1+1]-sum[k-1+1])%mo;
        }
        fo(j,0,n)
            if (j%K==n%K&&(i*K-j)%K==m%K&&i*K-j<=m)
                ans=(ans+f[q2][j][1])%mo;
        q1^=1;q2^=1;
    }
    ans=(ans+mo)%mo;
    printf("%d",ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;
	cin>>n;
	char s[500010];
	for(ll i=0;i<n;i++){
		char now;
		cin>>now;
		s[i]=now;
	}
	set<ll>ch[26];
	for(ll i=0;i<n;i++){
		char now=s[i];
		ch[now-'a'].insert(i);
	}
	ll q;cin>>q;
	for(ll i=0;i<q;i++){
		ll f;
		cin>>f;
		if(f==2){
			ll cnt=0;
			ll l,r;
			cin>>l>>r;
			l--;
			for(ll j=0;j<26;j++){
				auto itr1=ch[j].lower_bound(l);
				auto itr2=ch[j].lower_bound(r);
				if(itr1!=itr2){
					cnt++;
				}
			}
			if(l==r){
				cnt++;
			}
			cout << cnt<<endl;
		}
		if(f==1){
			ll now;char t;
			cin>>now;
			now--;cin>>t;
			ch[s[now]-'a'].erase(now);
			s[now]=t;
			ch[t-'a'].insert(now);
		}
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 27556
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
  long int n;
  int d=0;
  int r;
  char c='a';
  scanf("%ld",&n);
  n=n-1;

  while(1)
  {
    if(n < (long int)pow(26,d+1)) break;
    else n -= (long int)pow(26,d+1);
    d++;
  }

  for(int i=d;i>0;i--)
  {
    c = 'a';
    r = n / (long int)pow(26,i);
    c += r;
    printf("%c",c);
    n = n % (long int)pow(26,i);
  }

  c = 'a';
  c += n;
  printf("%c\n",c);

  return 0;
}

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

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(S: str, T: str):
    if (S == T[:-1]):
        print(YES)
        return 0
    print(NO)
    return 1

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(S, T)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9064
#include <bits/stdc++.h>
#define len(x) (int) (x.size())
using namespace std;
typedef long long ll;

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

    if (2*m >= n) {
        cout << "0" << '\n';
    }
    else {
        cout << n-2*m << '\n';
    }
    
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int p = 0, q = 0, r= 0;
        for(int i = sc.nextInt(); i > 0; i--)
            switch(sc.nextInt() % 4){
                case 0: p++; break;
                case 2: q++; break;
                case 1:
                case 3: r++; break;
                default: break;
            }
        String ans = (p >= r || (p == r-1 && q == 0)) ? "Yes" : "No";
        System.out.println(ans);
    }
}

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

#define int long long

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define REV(i, a) for (int i = (a); i >= 0; --i)
#define CLR(a) memset((a), 0, sizeof(a))
#define DUMP(x) cerr << #x << " = " << (x) << endl;
#define INF (3e15)

using namespace std;

int N;
int A[3 * 100005];

int sum1[100005];
int sum2[100005];

signed main() {
    cin >> N;

    REP(i, N * 3) { cin >> A[i]; }

    priority_queue<int, vector<int>, greater<int> > fque;
    int fsum = 0;
    REP(i, N) {
        fque.push(A[i]);
        fsum += A[i];
    }
    sum1[0] = fsum;

    priority_queue<int> sque;
    int ssum = 0;
    FOR(i, 2 * N, 3 * N) {
        sque.push(A[i]);
        ssum += A[i];
    }
    sum2[N] = ssum;

    int ans = -INF;
    for (int k = N; k <= 2 * N - 1; ++k) {
        fsum += A[k];
        fque.push(A[k]);
        int r = fque.top();
        fque.pop();
        fsum -= r;
        sum1[k - (N - 1)] = fsum;
    }
    for (int k = 2 * N - 1; k >= N; --k) {
        ssum += A[k];
        sque.push(A[k]);
        int r = sque.top();
        sque.pop();
        ssum -= r;
        sum2[k - N] = ssum;
    }
    REP(i, N + 1)
    ans = max(ans, sum1[i] - sum2[i]);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 5876