akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef tuple<ll,int,int> iii;
priority_queue<iii, vector<iii>, greater<iii> > pq;
int h,w,k;
int a[1000005];
ll d[1000005][5];
int X1,Y1,X2,Y2;
inline int nxt(int u, int dir){
    if (dir == 0){
        if (u < w) return -1;
        else return u-w;
    }
    if (dir == 1){
        if (u%w == w-1) return -1;
        else return u+1;
    }
    if (dir == 2){
        if (u+w >= h*w) return -1;
        else return u+w;
    }
    if (dir == 3){
        if (u%w == 0) return -1;
        else return u-1;
    }
}
int main(){
    scanf("%d%d%d",&h,&w,&k);
    scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
    X1 --, X2 --, Y1 --, Y2 --;
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            char x;
            scanf(" %c",&x);
            a[i*w+j] = (x=='@');
        }
    }
    int s = X1*w + Y1;
    int t = X2*w + Y2;
    memset(d,-1,sizeof(d));
    d[s][4] = 0;
    pq.push({0,s,4});
    while(pq.size()){
        ll D;
        int u, dir;
        tie(D,u,dir) = pq.top(); pq.pop();
        //printf("point <%d,%d>, dir = %d, D = %lld\n",u/w,u%w,dir,D);
        if (dir == 4){
            for (int i = 0; i <= 3; i++){
                if (d[u][i] == -1 || d[u][i] > D){
                    d[u][i] = D;
                    pq.push({D,u,i});
                }
            }
            continue;
        }
        int nD = ((D-1+k)/k) * k;
        if (d[u][4] == -1 || d[u][4] > nD){
            d[u][4] = nD;
            pq.push({nD,u,4});
        }
        int NEW = nxt(u,dir);
        if (NEW == -1 || a[NEW] == 1) continue;
       // printf("<%d,%d> %d -> <%d,%d>\n",u/w,u%w,dir,NEW/w,NEW%w);
        if (d[NEW][dir] == -1 || d[NEW][dir] > D+1){
            d[NEW][dir] = D+1;
            pq.push({D+1,NEW,dir});
        }
    }
    if (d[t][4] == -1) printf("-1\n");
    else printf("%lld",d[t][4]/k);





}


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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  int N, M;
  cin >> N >> M;
  set<int> s1, s2;
  REP(i,M){
	int a, b;
	cin >> a >> b;
	if(a > b) swap(a, b);
	if(a == 1)
	  s2.insert(b);
	else if(b == N)
	  s1.insert(a);
  }

  bool ok = false;
  for(int x: s1)
	ok = ok || s2.count(x);
  cout << (ok? "POSSIBLE": "IMPOSSIBLE") << endl;

  return 0;
}


Measured memory_bytes: 9600
s = input()
tmp = 1
l = []
ans = [0 for i in range(len(s))]
for i in range(1, len(s)):
    if s[i] == s[i-1]:
        tmp += 1
    else:
        l.append(tmp)
        tmp = 1
l.append(tmp)
lsum = 0
for i in range(len(l)):
    if i % 2 == 0:
        lsum += l[i]
        ans[lsum] += l[i]//2
        ans[lsum-1] += l[i]//2 + l[i]%2
    else:
        ans[lsum] += l[i]//2 + l[i]%2
        ans[lsum-1] += l[i]//2
        lsum += l[i]
print(" ".join(map(str, ans)))

Measured memory_bytes: 11260
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char c[] = str.toCharArray();
        if (c.length %2 != 0) {
            System.out.println("No");
            return;
        }
        for (int i = 0; i < c.length; i++) {
            if (i % 2 == 0) {
                if (c[i] != 'h') {
                    System.out.println("No");
                    return;
                }
            } else {
                if (c[i] != 'i') {
                    System.out.println("No");
                    return;
                }
            }
        }
        System.out.println("Yes");
    }
}


Measured memory_bytes: 22868
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    string s;
    cin>>s;
    int n=s.size();
    cout<<s[0]<<n-2<<s[n-1];
}

Measured memory_bytes: 3576
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g


an = []

for i in range(5):
    an.append(int(input()))

k = int(input())

flag = False
if (an[-1]-an[0] > k):
        flag = True

if flag:
    print(":(")
else:
    print("Yay!")


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>
#include <string>

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

using namespace std;


long long int layer_num[51];
long long int p_num[51];
long long int b_num[51];

long long int depth(int L, long long int remain)
{
    if(L==0) {
        return 1;
    }
    if(remain==0) {
        return 0;
    } else if(remain==1) {
        return 0;
    } else if(1<remain && remain<=layer_num[L-1]+1) {
        return depth(L-1, remain-1);
    } else if(remain==layer_num[L-1]+2) {
        return depth(L-1, remain-2) + 1;
    } else if(layer_num[L-1]+2<remain && remain<=layer_num[L-1]*2+2) {
        return depth(L-1, layer_num[L-1]) + 1 + depth(L-1, remain-2-layer_num[L-1]);
    } else if(remain==layer_num[L-1]*2+3) {
        return depth(L-1, layer_num[L-1])*2 + 1;
    } else {
        cout << "error!" <<endl;
    }
    return 0;
}


int main()
{
    int N;
    long long int X;
    scanf("%d %lld", &N, &X);
    layer_num[0] = 1;
    p_num[0] = 1;
    b_num[0] = 0;
    FOR(i, 1, N+1) {
        layer_num[i] = layer_num[i-1]*2 + 3;
        //p_num[i] = p_num[i-1]*2 + 1;
        //b_num[i] = b_num[i-1]*2 + 2;
        //cout << layer_num[i] << endl;
        //cout << p_num[i] << endl;
        //cout << b_num[i] << endl;
    }
    cout << depth(N, X) << endl;


    return 0;
}


Measured memory_bytes: 256
class Dice():

    def __init__(self):
        self.number = [i for i in range(6)]
        self.work = [i for i in range(6)]
        self.order = 'NNNNWNNNWNNNENNNENNNWNNN'

    def setNumber(self, n0, n1, n2, n3, n4, n5):
        self.number[0] = n0
        self.number[1] = n1
        self.number[2] = n2
        self.number[3] = n3
        self.number[4] = n4
        self.number[5] = n5

    def roll(self, loc):
        for i in range(6):
            self.work[i] = self.number[i]

        if loc == 'E':
            self.setNumber(self.work[3], self.work[1], self.work[0], self.work[5], self.work[4], self.work[2])
        elif loc == 'N':
            self.setNumber(self.work[1], self.work[5], self.work[2], self.work[3], self.work[0], self.work[4])
        elif loc == 'S':
            self.setNumber(self.work[4], self.work[0], self.work[2], self.work[3], self.work[5], self.work[1])
        elif loc == 'W':
            self.setNumber(self.work[2], self.work[1], self.work[5], self.work[0], self.work[4], self.work[3])

    def equals(self, another):

        ret = False;

        for i in range(len(self.order)):
            self.roll(self.order[i])
            FLG = True
            for k in range(6):
                if self.number[k] != another.number[k]:
                    FLG = False
                    break
            if FLG == True:
                return True

        return ret


diceA = Dice()
diceB = Dice()

table = list(map(int, input().split()))
diceA.setNumber(table[0], table[1], table[2], table[3], table[4], table[5])

table = list(map(int, input().split()))
diceB.setNumber(table[0], table[1], table[2], table[3], table[4], table[5])

if diceA.equals(diceB):
    print("Yes")
else:
    print("No")



Measured memory_bytes: 5624
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
mod=10**9+7

a,b,c,d=MI()

l=a+b
r=c+d

if l>r:
    print("Left")
elif r>l:
    print("Right")
else:
    print("Balanced")




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

using namespace std;

int main() {
    vector<int> H, W;
    int i = 0, n, m;
    
    while(1) {
        cin >> n >> m;
        H.push_back(n);
        W.push_back(m);
        
        if(H[i] == 0 && W[i] == 0) break;
        
        i++;
    }
    
    for(i = 0; H.size(); i++) {
        if(i != 0) cout << endl;
        if(H[i] == 0 && W[i] == 0) break;
        
        for(int x = 0; x < H[i]; x++) {
            for(int y = 0; y < W[i]; y++) {
                if((x % 2 == 0 && y % 2 == 0) || (x % 2 == 1 && y % 2 == 1)) cout << "#";
                else cout << ".";
                
                if(y == W[i]-1) cout << endl;
            }
        }
    }
    
    
}

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

int main(){
    int n; //整数の個数
    cin >> n;

    vector<ll>  inte(n); //整数の値
    for(int i=0; i<n; i++) cin >> inte[i];

    vector<ll> left(n+1),right(n+1); //要素数0~i-1までの最大公約数 要素数i~n-1までの最大公約数
    ll ans = 0;

    for(int i=1; i<n; i++) left[i+1] = __gcd(left[i],inte[i-1]);
    for(int i=n-1; i>0; i--)  right[i] = __gcd(right[i+1],inte[i]);

    /* i番目の数字を除いた最大公約数の最大値を求める */
    for(int i=1; i<n+1; i++){
        ans = max(ans,__gcd(left[i],right[i]));
    }

    cout << ans << endl;
}

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

int add(int num) {
    int result;
    if(num<=0) return 0;
    if(num<10) return num;
    result=num;
    result=0;
    while(num!=0) {
        result+=num%10;
        num=num/10;
	}
    return result;
}

int main()
{
	int a,b,n,f=0;
	cin >> n >> a >> b;
	for (int i=1;i<=n;i++)
	{
		if(add(i)<=b && add(i)>=a)
			f+=i;
	}
	cout << f;
	return 0; 
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        System.out.println(a[n - 1] - a[0]);
    }
}

Measured memory_bytes: 20692
#include<iostream>
#include<math.h>

using namespace std;

int intersection(double xa,double ya,double ra,double xb,double yb,double rb)
{
	double d=sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
	if(ra+rb<d)
	{
		return 0;
	}
	else if(ra+d<rb)
	{
		return -2;
	}
	else if(rb+d<ra)
	{
		return 2;
	}
	else{
		return 1;
	}
}

int main(void)
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		double xa,ya,ra,xb,yb,rb;
		cin>>xa>>ya>>ra>>xb>>yb>>rb;
		cout<<intersection(xa,ya,ra,xb,yb,rb)<<endl;
	}
}

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

using namespace std;

#define endl '\n'

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

  string s, t;
  cin >> s >> t;

  int n = s.length(), m = t.length();
  int lcs[n + 1][m + 1];
  for (int i = 0; i <= n; i++) lcs[i][0] = 0;
  for (int i = 1; i <= m; i++) lcs[0][i] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (s[i - 1] == t[j - 1]) lcs[i][j] = lcs[i - 1][j - 1] + 1;
      else lcs[i][j] = max(lcs[i][j - 1], lcs[i - 1][j]);
    }
  }
  int i = n, j = m;
  string ans = "";
  while (i >= 1 && j >= 1) {
    if (s[i - 1] == t[j - 1]) {
        ans += s[i - 1];
        i--; j--;
    }
    else if (lcs[i - 1][j] > lcs[i][j - 1]) i--;
    else j--;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;

	return 0;
}


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

#include <iostream>
using namespace std;

uint64_t CulcAttackNum(uint64_t hp) {
  if (hp == 0) {
    return 0;
  } else {
    return 1 + 2 * CulcAttackNum(static_cast<uint64_t>(hp / 2));
  }
}

int main() {
  uint64_t h;
  cin >> h;
  cout << CulcAttackNum(h) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int a,b,c,i;
  int count=0;

  scanf("%d %d %d",&a,&b,&c);
  for(i=a;i<=b;i++){
    if(c%i==0){
      count++;
    }
  }

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

  return 0;
}

Measured memory_bytes: 596
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void calc(Vec2 p, Vec2 a, Vec2 b) {
    auto ab = b - a;
    auto ap = p - a;

    auto e = ab.normalized;
    // ベクトル ap のベクトル ab への正射影ベクトル ax を求める
    auto ax = ap.dot(e) * e;
    auto x = a + ax;
    writefln("%.8f %.8f", x.x, x.y);
}

void main() {
    auto xs = readints();
    auto p1 = Vec2(xs[0], xs[1]);
    auto p2 = Vec2(xs[2], xs[3]);

    int q = readint();
    for (int i = 0; i < q; i++) {
        auto xy = readints();
        auto p = Vec2(xy[0], xy[1]);
        calc(p, p1, p2);
    }
}

struct Vec2 {
    immutable double x;
    immutable double y;

    this(double x, double y) {
        this.x = x;
        this.y = y;
    }

    Vec2 opAdd(Vec2 other) {
        return Vec2(this.x + other.x, this.y + other.y);
    }

    Vec2 opSub(Vec2 other) {
        return Vec2(this.x - other.x, this.y - other.y);
    }

    Vec2 opMul(double d) {
        return Vec2(this.x * d, this.y * d);
    }

    double dot(Vec2 other) {
        return this.x * other.x + this.y * other.y;
    }

    double cross(Vec2 other) {
        return this.x * other.y - other.x * this.y;
    }

    double mag() {
        return sqrt(magSq());
    }

    double magSq() {
        return this.x * this.x + this.y * this.y;
    }

    Vec2 normalized() {
        auto m = mag();
        if (m != 0 && m != 1)
            return Vec2(this.x / m, this.y / m);
        return this;
    }

    static double distance(Vec2 a, Vec2 b) {
        return (a - b).mag();
    }
}



Measured memory_bytes: 2560
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = [0]
b = [0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])

ans = 0
j = M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K-a[i]:
        j -= 1
    ans = max(ans,i+j)
print(ans)

Measured memory_bytes: 47552
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll=long long;
using ld=long double;
//#define int long long
#define _CRT_SECURE_NO_WARNINGS
#define rep(i, n) for (int i = 0; i < n; i++)
#define _GLIBCXX_DEBUG
#define ALL(x) (x).begin(), (x).end()
const int MOD = 1e9 + 7;
const int INF = 1e18 + 9;
constexpr long double pi = 3.141592653589793238462643383279;
int fact(int i) {
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
int keta(int n) {
    if (n == 0) return 1;
    int count = 0;
    while (n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
int ketasum(int n) {
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
char toSmall(char c) { // 大文字を小文字へ
    return (c + 0x20);
}
char toLarge(char c) { // 小文字を大文字へ
    return (c - 0x20);
}
float myPower(int a, int n) { // aのn乗の計算
    float x = 1;
    while (n > 0) { // 全てのbitが捨てられるまで
        if (n & 1) { // 一番右のbitが１のとき
            x *= a;
        }
        a *= a;
        n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
    }
    return x;
}
bool is_prime(const unsigned n) {
    switch (n) {
    case 0: // fall-through
    case 1: return false;
    case 2: // fall-through
    case 3: return true;
    } // n > 3 が保証された

    if (n % 2 == 0 || n % 3 == 0) return false;
    // n は 2 と 3 のいずれの倍数でもないことが保証された
    // これより n は (6の倍数)-1 か (6の倍数)+1 である
    // 6の倍数前後の数を使って試し割りをする
    for (unsigned i = 5; i * i <= n; i += 6) {
        if (n % i == 0) return false; // (6の倍数)-1
        if (n % (i + 2) == 0) return false; // (6の倍数)+1
    }

    return true;
}
int n, d, x, sum;
int main(void){
    cin >> n >> d >> x;
    vector<int> vec(n);
    rep(i, n) {
        cin >> vec[i];
        (d%vec[i]!=0?sum += d / vec[i]:sum+=d/vec[i]-1);
    }
    cout << sum + n + x << endl;
    return 0;
}

Measured memory_bytes: 3608
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <thread>
#include <tuple>
#include <limits>

using namespace std;

constexpr int mod = 1000000007;

int main() {
  int n;
  scanf("%d", &n);
  vector<int> a(n);
  int starter = 0;
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  long long gcnt = 1;
  map<int, int> freq;
  for (int i = 0; i < n; i++) {
    if (a[i] == 0) {
      starter++;
    } else {
      int& val = freq[a[i] - 1];
      gcnt *= val;
      gcnt %= mod;
      val--;
    }
    freq[a[i]]++;
  }
  long long ans = 0;
  if (starter > 3) {
    ans = 0;
  } else if (starter == 3) {
    ans = gcnt * 6 % mod;
  } else if (starter == 2) {
    ans = gcnt * 6 % mod;
  } else if (starter == 1) {
    ans = gcnt * 3 % mod;
  } else {
    ans = 0;
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 5376
n = int(input())
G = [[int(i) for i in input().split()] for i in range(n)]

S = set([])
for i,row in enumerate(G):
    for j,col in enumerate(row):
        if col != -1:
            k = tuple(sorted([i,j]))
            S.add(k + (col, ))

rank = {}
p = {}

def makeSet(x):
    p[x] = x
    rank[x] = 0

def link(x, y):
    if  rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
    if  rank[x] == rank[y]:
        rank[y] += 1

def union(x, y):
    link(findSet(x), findSet(y))
    
def findSet(x):
    if  x != p[x]:
        p[x] = findSet(p[x])
    return p[x]
    
def isSameSet(x, y):
    return findSet(x) == findSet(y)

def kruskal(G, n, S):
    ret = 0
    for x in range(n):
        makeSet(x)
    while len(S) != 0:
        u, v, c = min(S, key=lambda x: x[2])
        S = S - set([(u,v,c)])
        if not isSameSet(u, v):
            union(u, v)
            ret += c
    return ret
print(kruskal(G, n, S))

Measured memory_bytes: 8516
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    s = str(readline().rstrip().decode('utf-8'))
    ls = [0] * len(s)
    n = len(s)
    for i in range(1, n):
        if s[i] == "L" and s[i-1] == "R":
            rc = 0
            for j in range(i-1, -1, -1):
                if s[j] == "R":
                    rc += 1
                else:
                    break
            lc = 0
            for j in range(i, n):
                if s[j] == "L":
                    lc += 1
                else:
                    break
            ls[i-1] = (rc + lc) // 2
            ls[i] = (rc + lc) // 2
            if (rc + lc) % 2 != 0:
                if max(rc, lc) % 2 != 0:
                    if rc > lc:
                        ls[i-1] += 1
                    else:
                        ls[i] += 1
                else:
                    if rc > lc:
                        ls[i] += 1
                    else:
                        ls[i-1] += 1
    print(*ls)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 49724
#include <iostream>

using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    
    constexpr int INF = (1 << 29);
    
    int d[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            d[i][j] = INF * (i != j);
        }
    }
    
    int a[M], b[M], c[M];
    for (int i = 0; i < M; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        d[a[i]][b[i]] = d[b[i]][a[i]] = c[i];
    }

    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    
    int cnt = 0;
    for (int i = 0; i < M; i++) {
        if (d[a[i]][b[i]] != c[i]) ++cnt;
    }
    cout << cnt << endl;
    
    return 0;
}


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

int main()
{
    ll n, tmp = 0, cnt = 1;
    cin >> n;
    vector<ll> a(n), ok(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (i == 0)
            continue;

        if (a[i-1] < a[i])
        {
            if (tmp == -1) {
                tmp = 0;
                cnt++;
            } else {
                tmp = 1;
            }
        }
        if (a[i-1] > a[i])
        {
            if (tmp == 1) {
                tmp = 0;
                cnt++;
            } else {
                tmp = -1;
            }
        }
    }

    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 4776
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, A, B = LI()

    ans = min(A * N , B)
    print(ans)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 10116
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    X = [None] * M
    bsum = 0
    for i in range(M):
        B, C = map(int, input().split())
        X[i] = (C, B)
        bsum += B
    bsum = min(bsum, N)
    X.sort(reverse=True)
    idx = 0
    Z = [0] * bsum
    for C, B in X:
        i = idx
        while i < bsum and i-idx < B:
            Z[i] = C
            i += 1
        idx = min(idx+B, bsum)
    cumsumA = [0] * (N+1)
    cumsumZ = [0] * (bsum+1)
    for i in range(N):
        cumsumA[i+1] = cumsumA[i] + A[i]
    for i in range(bsum):
        cumsumZ[i+1] = cumsumZ[i] + Z[i]
    ans = 0
    for i in range(bsum+1):
        tmp = cumsumA[-1] - cumsumA[i] + cumsumZ[i]
        ans = max(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()


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

int main() {
	int n, x;
	cin >> n;
	
	for ( int i = 1; i <= n; i++) {
		x = i;
		if ( x % 3 == 0 ) {
			cout << " " << i;
		} else {
			while( x ) {
				if ( x % 10 == 3 ) {
					cout << " " << i;
					break;
				}
				x /= 10; //????
			}
		}
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
using P=pair<int,int>;
const int val=1000000;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main(void){
  int h,w;
  int ans=0;
  cin>>h>>w;
  char a[h][w];
  int num[h][w];
  queue<P> que;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>a[i][j];
      if(a[i][j]=='#'){
        que.push(P(i,j));
        num[i][j]=0;
      }else{
        num[i][j]=val;
      }
    }
  }
  while(que.size()){
    P p=que.front();
    que.pop();
    for(int i=0;i<4;i++){
      int nx=p.first+dx[i],ny=p.second+dy[i];
      if(0<=nx && nx<h && 0<=ny && ny<w && num[nx][ny]==val){
        num[nx][ny]=num[p.first][p.second]+1;
        que.push(P(nx,ny));
        ans=max(ans,num[nx][ny]);
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 16428
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A, B, M;
    cin >> A >> B >> M;
    vector<ll> freezes(A);
    for (int i = 0; i < A; i++)
    {
        cin >> freezes.at(i);
    }
    vector<ll> ranges(B);
    for (int i = 0; i < B; i++)
    {
        cin >> ranges.at(i);
    }
    ll answer = 1e12;
    for (int i = 0; i < M; i++)
    {
        ll X, Y, C;
        cin >> X >> Y >> C;
        answer = min(answer, freezes.at(X - 1) + ranges.at(Y - 1) - C);
    }
    sort(freezes.begin(), freezes.end());
    sort(ranges.begin(), ranges.end());
    answer = min(answer, freezes.at(0) + ranges.at(0));
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 1792
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = [11, 31, 41, 61, 71, 101, 131, 151, 181, 191, 211, 241, 251, 271, 281, 311, 331, 401, 421, 431, 461, 491, 521, 541, 571, 601, 631, 641, 661, 691, 701, 751, 761, 811, 821, 881, 911, 941, 971, 991, 1021, 1031, 1051, 1061, 1091, 1151, 1171, 1181, 1201, 1231, 1291, 1301, 1321, 1361, 1381, 1451, 1471, 1481, 1511, 1531, 1571, 1601, 1621, 1721, 1741, 1801, 1811, 1831, 1861, 1871, 1901, 1931, 1951, 2011, 2081, 2111, 2131, 2141, 2161, 2221, 2251, 2281, 2311, 2341, 2351, 2371, 2381, 2411, 2441, 2521, 2531, 2551, 2591, 2621, 2671, 2711, 2731, 2741, 2791, 2801, 2851, 2861, 2971, 3001, 3011, 3041, 3061, 3121, 3181, 3191, 3221, 3251, 3271, 3301, 3331, 3361, 3371, 3391, 3461, 3491, 3511, 3541, 3571, 3581, 3631, 3671, 3691, 3701, 3761, 3821, 3851, 3881, 3911, 3931, 4001, 4021, 4051, 4091, 4111, 4201, 4211, 4231, 4241, 4261, 4271, 4391, 4421, 4441, 4451, 4481, 4561, 4591, 4621, 4651, 4691, 4721, 4751, 4801, 4831, 4861, 4871, 4931, 4951, 5011, 5021, 5051, 5081, 5101, 5171, 5231, 5261, 5281, 5351, 5381, 5431, 5441, 5471, 5501, 5521, 5531, 5581, 5591, 5641, 5651, 5701, 5711, 5741, 5791, 5801, 5821, 5851, 5861, 5881, 5981, 6011, 6091, 6101, 6121, 6131, 6151, 6211, 6221, 6271, 6301, 6311, 6361, 6421, 6451, 6481, 6491, 6521, 6551, 6571, 6581, 6661, 6691, 6701, 6761, 6781, 6791, 6841, 6871, 6911, 6961, 6971, 6991, 7001, 7121, 7151, 7211, 7321, 7331, 7351, 7411, 7451, 7481, 7541, 7561, 7591, 7621, 7681, 7691, 7741, 7841, 7901, 7951, 8011, 8081, 8101, 8111, 8161, 8171, 8191, 8221, 8231, 8291, 8311, 8431, 8461, 8501, 8521, 8581, 8641, 8681, 8731, 8741, 8761, 8821, 8831, 8861, 8941, 8951, 8971, 9001, 9011, 9041, 9091, 9151, 9161, 9181, 9221, 9241, 9281, 9311, 9341, 9371, 9391, 9421, 9431, 9461, 9491, 9511, 9521, 9551, 9601, 9631, 9661, 9721, 9781, 9791, 9811, 9851, 9871, 9901, 9931, 9941, 10061, 10091, 10111, 10141, 10151, 10181, 10211, 10271, 10301, 10321, 10331, 10391, 10501, 10531, 10601, 10631, 10651, 10691, 10711, 10771, 10781, 10831, 10861, 10891, 11071, 11131, 11161, 11171, 11251, 11261, 11311, 11321, 11351, 11411, 11471, 11491, 11551, 11621, 11681, 11701, 11731, 11801, 11821, 11831, 11941, 11971, 11981, 12011, 12041, 12071, \
12101, 12161, 12211, 12241, 12251, 12281, 12301, 12391, 12401, 12421, 12451, 12491, 12511, 12541, 12601, 12611, 12641, 12671, 12721, 12781, 12791, 12821, 12841, 12911]
    print(*a[:n])

if __name__ == '__main__':
    main()

Measured memory_bytes: 3444
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,k;
	cin>>n>>k;
	vector<int> a(n);
	rep(i,n) cin>>a[i];
	sort(begin(a),end(a));
	auto solve=[&](int x){
		vector<vector<bool>> dp(n+1,vector<bool>(k,false));
		dp[0][0]=true;
		rep(j,n)rep(l,k){
			dp[j+1][l]=dp[j+1][l]|dp[j][l];
			if(j==x) continue;
			if(l-a[j]>=0) dp[j+1][l]=dp[j+1][l]|dp[j][l-a[j]];
		}
		FOR(j,max(0,k-a[x]),k) if(dp[n][j]) return false;
		return true;
	};
	int ok=-1,ng=n,mid;
	while(ng-ok>1){
		mid=(ok+ng)/2;
		if(solve(mid)) ok=mid;
		else ng=mid;
	}
	cout<<ok+1<<endl;
}

Measured memory_bytes: 5636
#include <iostream>
#include <cassert>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

long long int INF = 3e18;
double Pi = 3.1415926535897932384626;

vector<ll> G[500005];
vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop

int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←


#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(15)<<x<<endl;
#define pu(x) cout<<x;
#define re(i,n) for(i=0;i<n;i++);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define deba(x) cout<< #x << " = " << x <<endl


long long int mod = 1000000007;
ll rui(ll number1,ll number2){
    //abcのbed乗を計算する
    if(number2 == 0){return 1;}
    else{
        ll number3 = rui(number1,number2/2);
        number3 *= number3;
        number3 %= mod;
        if(number2 % 2 == 1){number3 *= number1; number3 %= mod;}
        return number3;
    }
}
ll gcd(ll number1,ll number2){
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}

ll n,m,num,sum,ans,a,b,c,d,e,f,g,h,i,j,k,l,w,ok,ng,res,q;
ll x[500005],y[500005],z[500005];
ll dp[105][6][6][6];
char s[500005];

int main(){
    cin >> n;
	for(i=0;i<4;i++){
		for(j=0;j<4;j++){
			for(k=0;k<4;k++){
				dp[3][i][j][k] = 1;
			}
		}
	}
	dp[3][0][2][3] = dp[3][0][3][2] = dp[3][2][0][3] = 0;
	for(i=4;i<=n;i++){
		for(j=0;j<4;j++){
			for(k=0;k<4;k++){
				for(l=0;l<4;l++){
					dp[i][k][l][0] += dp[i-1][j][k][l];
					dp[i][k][l][1] += dp[i-1][j][k][l];
					if(k != 0 || l != 3)dp[i][k][l][2] += dp[i-1][j][k][l];
					if((k != 0 || l != 2) && (k != 2 || l != 0) && (j != 0 || k != 2) && (j != 0 || l != 2))dp[i][k][l][3] += dp[i-1][j][k][l];
					for(a=0;a<4;a++){
						dp[i][k][l][a] %= mod;
					}
				}
			}
		}
	}

	ans = 0;
	for(i=0;i<4;i++){
		for(j=0;j<4;j++){
			for(k=0;k<4;k++){
				ans += dp[n][i][j][k];
				//p(dp[n][i][j]);
				ans %= mod;
			}
		}
	}
	p(ans);
	return 0;
}

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

int main() {
	string S,T;
	cin >> S >> T;

	if(S.size()+1==T.size() && S==T.substr(0,S.size()))
		cout << "Yes";
	else
		cout << "No";
	cout << endl;	
}

Measured memory_bytes: 3568
#include <iostream>
#include <cmath>
#include <sstream>
using namespace std;

string inc(string str, int c)
{
    for (int i = 0; i < str.size(); ++i) {
        if (str[i] < 'a' || 'z' < str[i])
            continue;
        int tmp = (str[i] - 'a' + c)%26;
        str[i] = 'a' + tmp;
    }
    return str;
}

int main(void)
{
    bool flag;
    string str;
    while (getline(cin, str)) {

    for (int i = 0; i < 26; ++i) {
        flag = false;
        string tmp;
        stringstream ss;
        ss << str;
        while (!ss.eof()) {
            ss >> tmp;
            tmp = inc(tmp, i);
            flag += tmp == "this";
            flag += tmp == "that";
            flag += tmp == "the";
            flag += tmp == "this.";
            flag += tmp == "that.";
            if (flag)
                break;
        }
        if (flag) {
            cout << inc(str, i) << endl;
            break;
        }
    }
    }
    return 0;
}






Measured memory_bytes: 3172
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
typedef long long llong;
using namespace std;

int main(){
	int n,wl;
	cin>>n>>wl;
	
	vector<int> w(n),v(n);
	REP(i,n) cin>>w[i]>>v[i];
	
	vector<vector<llong> > dp(wl+1,vector<llong>(n+1,0));//重さi(0~wl)における最大価値量dp[i][j].
	for(int i=1;i<=wl;++i){
		for(int j=1;j<=n;++j){
			if(w[j-1]<=i) dp[i][j]=max(dp[i][j-1],dp[i-w[j-1]][j-1]+v[j-1]);
			else dp[i][j]=dp[i][j-1];
		}
	}
	
	cout<<dp[wl][n]<<endl;
	return 0;
}//解答参考.

Measured memory_bytes: 82304
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    ll n; cin >> n;
    vector <ll> cnt(n+1, 0);
    for(ll x=1; x<100; x++){
        for(ll y=1; y<100; y++) {
            for(ll z=1; z<100; z++) {
                ll num = x*x + y*y + z*z + x*y + y*z + z*x;
                if (num > n){
                    continue;
                }
                cnt[num]++;
            }
        }
    }
    for(ll nu=1; nu<n+1; nu++){
        cout << cnt[nu] << endl;
    }
    return 0;
}

Measured memory_bytes: 3592
use proconio::input;

#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars, Usize1};
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::ops::*;

#[derive(Clone, Debug, Default)]
struct Struct;




//#[proconio::fastout]
fn main() {
    input! {
        n:usize,
        m:usize,
        v:[(Usize1,Usize1);m],
    }
    let mut e = vec![Vec::new();n];
    for (a,b) in &v {
        e[*a].push(*b);
        e[*b].push(*a);
    }

    let mut room_mark:Vec<Option<usize>> = vec![None;n];

    let mut q = VecDeque::new();
    q.push_back(0);
    room_mark[0] = Some(0);

    while let Some(r) = q.pop_front() {
        for next_room in &e[r] {
            if room_mark[*next_room] == None {
                q.push_back(*next_room);
                room_mark[*next_room] = Some(r);
            }
        }
    }

    for i in 1..n {
        if room_mark[i] == None {
            println!("No");
            return;
        }
    }
    println!("Yes");
    for i in 1..n {
        println!("{}", room_mark[i].unwrap()+1 );
    }

}


Measured memory_bytes: 18076
#include<stdio.h>
long long int arr[3]={2, 1};
int main() {
    int n;
    scanf("%d", &n);
    for(int i=2;i<=n;i++) {
        arr[i%3]=arr[(i-1)%3]+arr[(i-2)%3];
    }
    printf("%lld", arr[n%3]);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,n,m) for(int i=n;i<=(int)(m);i++)
#define RFOR(i,n,m) for(int i=(int)(n);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
typedef long long ll;
const int INF = 1e9;
const int MOD = 998244353;
const ll LINF = 1e18;
const double PI=3.14159265358979323846;
using namespace std;
vector<int> dx={1,0,-1,0};
vector<int> dy={0,1,0,-1};
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

ll ext_gxd(ll a,ll b,ll &x,ll &y) {
    if(b==0) {
        x=1;
        y=0;
        return a;
    }
    ll q = a/b;
    ll g = ext_gxd(b,a-q*b,x,y);
    ll z = x-q*y;
    x=y;
    y=z;
    return g;
}

ll modinv(ll a, ll m) {
    ll x,y;
    ext_gxd(a,m,x,y);
    x%=m;
    if(x<0) x+=m;
    return x;
}

vector<ll> kaijou() {
    vector<ll> vec(1000010,1);
    rep(i,1000000) vec[i+1]=(vec[i]*(i+1))%MOD;
    return vec;
}

vector<ll> kai;
ll comb(int x,int y) {
    if(x<y || y<0)  return 0;
    return kai[x]*modinv(kai[x-y]*kai[y],MOD)%MOD;
}


int main() {
    kai=kaijou();
    ll n,a,b,k;
    cin>>n>>a>>b>>k;
    ll x,y;
    ll g=ext_gxd(a,b,x,y);
    if(k%g!=0) {
        cout<<0<<endl;
        return 0;
    }
    x*=k/g;
    y*=k/g;
    ll l=ceil(max((double)-g*x/b,(double)-g*(n-y)/a));
    ll r=floor(min((double)g*(n-x)/b,(double)g*y/a));
    //cout<<x<<" "<<y<<" "<<g<<" "<<l<<" "<<r<<endl;
    
    ll ans=0;
    for(ll K=l; K<=r; K++) {
        ll X=x+K*b/g;
        ll Y=y-K*a/g;
       ans+=comb(n,X)*comb(n,Y)%MOD;
       ans%=MOD;
    }
    cout<<ans<<endl;
}


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


int main(){
    ll n ;
    cin >> n ;
    vector<int> A(n) ;
    rep(i,n) cin >> A.at(i) ;
    int ans = 0 ;
    rep(i,n){
        ans = ans ^ A.at(i) ;
        //cout << ans << endl;
    }
    rep(i,n){
        int tem = ans ^ A.at(i) ;
        cout << tem << endl ;
    }
}

 


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

int main(){
	int x,Max;x=Max=0;
	int n;string s;cin>>n>>s;
	for(char c:s){
		if(c=='I')x++;
		else x--;
		Max=max(Max,x);
	}
	cout<<Max<<endl;
}


Measured memory_bytes: 256
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x):
        self.setdefault(x,0)
        self[x] += 1

N,M = mint()
ship = [set() for _ in range(N+1)]
for _ in range(M):
    a,b = mint()
    ship[a].add(b)
    ship[b].add(a)
ans = False
for a in ship[1]:
    if N in ship[a]:
        ans = True
        break
judge(ans,['POSSIBLE','IMPOSSIBLE'])

Measured memory_bytes: 158904
#include <iostream>
#define N 200000

using namespace std;


int main() {
	int n;
	bool inf = true;
	long r[N], max;
	long sup[N];

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

	sup[n-2] = r[n-1];
	for(int i = n-3; i >= 0; --i) {
		if(r[i+1] > sup[i+1]) {
			sup[i] = r[i+1];
		} else {
			sup[i] = sup[i+1];
		}
	}

	for(int i = 0; i < n-1; ++i) {
		if(inf) {
			inf = false;
			max = sup[i] - r[i];
			continue;
		}

		if(sup[i] - r[i] > max) {
			max = sup[i] - r[i];
		}
	}

	cout << max << endl;

	return 0;
}

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

Measured memory_bytes: 3288
#include <cstdio>
#define FOR(i, l, r) for(int i = l; i <= r; ++i)
using namespace std;

const int N = 210;
int a[N], b[N], used[N], mat[N], m[N][N];
int n, ans;

bool find(int x)
{
    FOR(i, 1, n) if (m[x][i] && !used[i])
    {
        used[i] = 1;
        if (!mat[i] || find(mat[i]))
        {
            mat[i] = x;
            return 1;
        }
    }
    return 0;
}

int main()
{
    scanf("%d", &n);
    FOR(i, 1, 2 * n) scanf("%d%d", &a[i], &b[i]);
    FOR(i, 1, n) FOR(j, 1, n) if (a[i] < a[n + j] && b[i] < b[n + j]) m[i][j] = 1;
    FOR(i, 1, n)
    {
        FOR(j, 1, n) used[j] = 0;
        if (find(i)) ++ans;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int n, A[50];

int solve(int i, int m) {
  if (m == 0) return 1;
  if (i >= n) return 0;
  int res = solve(i + 1, m) || solve(i + 1, m - A[i]);
  return res;
}

int main()
{
  int q, M, i;

  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &A[i]);
  scanf("%d", &q);
  for (i = 0; i < q; i++) {
    scanf("%d", &M);
    if(solve(0, M)) printf("yes\n");
    else printf("no\n");
  }
  return 0;
}


Measured memory_bytes: 2692
n = int(input())
a = list(map(int, input().split()))

point = 1
nums = []
for i in range(len(a)):
    if a[i] == point:
        point += 1
        nums.append(a[i])

if not nums:
    print('-1')
else:
    print(len(a) - len(nums))

Measured memory_bytes: 24744
#include<bits/stdc++.h>
#define REP(i,n) for(auto i=0; i<(n); i++)
#define REP2(i,x,n) for(long long i=x; i<(n); i++)
#define D(x) for_each((x).begin(),(x).end(),[](auto&& x){cout<<x<<" ";});
#define eb emplace_back
using LL=long long;
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
	int N, A, B;
	cin >> N >> A >> B;
	vector<int> vc( N );
	for( auto &x : vc )
	{
		cin >> x;
	}
	int count{};
	REP2( i, 0, N )
	{
		if( vc[i] >= A && vc[i] < B )
		{
			continue;
		}
		count++;
	}
	cout << count << endl;
	return 0;
}

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

int main() {
	int N, K;
	std::string S;

	std::cin >> N >> S >> K;

	for(int i = 0; i < N; ++i) {
		if(S[i] != S[K - 1]) {
			S[i] = '*';
		}
	}
	std::cout << S << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int A, B;
    cin >> A >> B;
    
    if((A+B)%2==0){
        cout << (A+B)/2 << endl;
        return 0;
    }else{
        cout << "IMPOSSIBLE" << endl;
    } 
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
const double pi = 3.141592653589793;
typedef unsigned long long ull;
typedef long double ldouble;
const ll INF = 1e18;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
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; }
typedef pair<int, int> P;
typedef pair<ll, ll> PL;

// コンパイル方法
// g++ lazy_segment/___.cpp -std=c++17 -I .
// ./a.out

typedef modint998244353 mint;

const mint inv9 = mint(1) / 9;

struct S
{
    mint x, w;
    S(mint x = 0, mint w = 1) : x(x), w(w) {}
};

S op(S a, S b)
{
    return S(a.x * b.w + b.x, a.w * b.w);
}
S e() { return S(); }

S mapping(int f, S a)
{
    if (f == 0)
        return a;
    return S((a.w - 1) * inv9 * f, a.w);
}

int composition(int f, int g)
{
    if (f == 0)
        return g;
    else
        return f;
}

int id() { return 0; }

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

    lazy_segtree<S, op, e, int, mapping, composition, id> t(n);
    rep(i, n) t.set(i, S(1, 10));
    rep(qi, q)
    {
        int l, r, d;
        cin >> l >> r >> d;
        l--;
        t.apply(l, r, d);
        S ans = t.prod(0, n);
        cout << ans.x.val() << endl;
    }
    return 0;
}

Measured memory_bytes: 9896
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = NI()
    a = LI()

    ans = 0
    for i in range(N):
        if i % 2 == 0 and a[i] % 2 == 1:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int path[5];

int main() {
    //cout.precision(10);
    for(int i = 1; i <= 3; i++) {
        int a, b;
        cin >> a >> b;
        path[a]++;
        path[b]++;
    }
    int one = 0;
    int two = 0;
    for(int i = 1; i <= 4; i++) {
        if(path[i] == 1) one++;
        if(path[i] == 2) two++;
    }
    if((one == 2) && (two == 2)) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[105];
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    sort(a,a+n,cmp);
    if(n&1)
        a[n]=0;
    int ans=0;
    for(int i=0;i<n;i+=2)
        ans+=a[i]-a[i+1];
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256