akhauriyash/Code-Regression huggingface dataset:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, accumulate
import itertools
import heapq
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

def factorization(n):
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret

def main():
    N = I()
    v = defaultdict(int)

    for i in range(1, N+1):
        fac = factorization(i)
        for f in fac:
            v[f] += 1

    ans = 1
    for c in v.values():
        ans *= (c + 1)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 44888
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;

/* --------------------------------------------------- */

int main() {
    int a, b, k;
    cin >> a >> b >> k;
    rep(i, k) {
        if(i % 2 == 0) {
            a /= 2;
            b += a;
        } else {
            b /= 2;
            a += b;
        }
    }
    cout << a << " " << b << endl;
    return 0;
}

Measured memory_bytes: 3624
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    M = na[1]
    lrd_list = []
    for i in range(M):
        na = list(map(int, input().split()))
        lrd_list.append((na[0], na[1], na[2]))

    l_list = [None for i in range(N+1)]
    r_list = [None for i in range(N+1)]
    for lrd in lrd_list:
        l = lrd[0]
        r = lrd[1]
        if l_list[l] is None:
            l_list[l] = [lrd]
        else:
            l_list[l].append(lrd)
        if r_list[r] is None:
            r_list[r] = [lrd]
        else:
            r_list[r].append(lrd)

    positions = [None for i in range(N+1)]
    consistent = True
    i = 1
    while consistent and i <= N:
        s = []
        p = 0
        positions[i] = p
        s.append(i)
        while consistent and 0 < len(s):
            j = s.pop()
            p = positions[j]
            if not l_list[j] is None:
                for lrd in l_list[j]:
                    l, r, d = lrd
                    if positions[r] is None:
                        positions[r] = p + d
                        s.append(r)
                    elif positions[r] != p + d:
                        consistent = False
                        break
                if not consistent:
                    break
            if not r_list[j] is None:
                for lrd in r_list[j]:
                    l, r, d = lrd
                    if positions[l] is None:
                        positions[l] = p - d
                        s.append(l)
                    elif positions[l] != p - d:
                        consistent = False
                        break
        while consistent and i <= N and (not positions[i] is None):
            i += 1


    print('Yes' if consistent else 'No')


if __name__ == '__main__':
    main()



Measured memory_bytes: 58456
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,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n=I()
    lis=[LI() for i in range(n)]
    for i in range(n-2):
        if lis[i][0]==lis[i][1] and lis[i+1][0]==lis[i+1][1] and lis[i+2][0]==lis[i+2][1]:
            print("Yes")
            exit()
    print("No")

        
        
        
        



        
        
        
        
        
    
if __name__=="__main__":
    main()



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

int main() {
    int a, b, n;
    bool even = false;
    cin >> a >> b;

    n = a * b;

    if (n % 2 == 0) {
        even = true;
    }

    if (even)
    {
        cout << "Even" << endl;
    }

    if (!even)
    {
        cout << "Odd" << endl;
    }
    
}


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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    int N;
    cin >> N;
    bool o = N % 2 == 1;

    vector<pll> v;
    if (o)
        N--;
    //! 1-N,2-N-1をペアにする
    FOR(i, N + 1, 1)
    {
        FOR(j, N + 1, i + 1)
        {
            if (i + j == N + 1)
                continue;
            v.push_back(pll(i, j));
        }
    }

    if (o)
    {
        REP(i, N)
        {
            v.push_back(pll(i + 1, N + 1));
        }
    }
    cout << v.size() << endl;
    REP(i, v.size())
    {
        cout << v[i].first << " " << v[i].second << endl;
    }
    return 0;
}

Measured memory_bytes: 512
n=int(input())
a=[[0 for _ in range(9)] for _ in range(9)]

for i in range(1,n+1):
  x=int(str(i)[0])
  y=int(str(i)[-1])
  if x!=0 and y!=0:
    a[x-1][y-1]+=1
  
ans=0
  
for i in range(9):
  for j in range(9):
    if i!=j:
      
      ans+=a[i][j]*a[j][i]
      
    else:
      ans+=(a[i][i]*a[i][i])
      
print(ans)

Measured memory_bytes: 92016
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define mod 1000000007

int main(){
  string s; cin>>s;
  string bef="";
  ll p=0,ans=0;
  for(;;ans++){
      string cur=""; cur+=s[p]; p++;
      for(;p<s.size()&&cur==bef;p++)cur+=s[p];
      if(bef==cur)break;
      if(p==s.size()){
	  ans++;
	  break;
      }
      bef=cur; //cout<<cur<<" ";
  }
  cout<<ans<<endl;
  return 0;
}


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

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

const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;

#define rep(i, a, b) for(ll (i) = (a); (i) < (b);++i)

bool pairCompare(const Po& firstElof, const Po& secondElof) {
    return firstElof.second < secondElof.second;
}

int main()
{
  ll N, M;
  cin >> N >> M;
  ll P[M], Y[M];
  rep(i,0,M)cin >> P[i] >> Y[i];

  vector<Po> pairs;
  rep(i,0,M)pairs.push_back(make_pair(make_pair(P[i], Y[i]), i));
  sort(pairs.begin(), pairs.end());

  pairs[0].first.second = 1;
  ll a = 1;
  rep(i,1,M) {
    if (pairs[i].first.first == pairs[i-1].first.first) {
      a++;
      pairs[i].first.second = a;
    }else{
      a = 1;
      pairs[i].first.second = a;
    }
  }

  sort(pairs.begin(), pairs.end(), pairCompare);
  rep(i,0,M) {
    printf("%06d%06d\n", pairs[i].first.first, pairs[i].first.second);
  }
  return 0;
}


Measured memory_bytes: 7540
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

ll dp[3030][3030];

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

  dp[1][1]=1;
  for(int i=1;i<n;i++){
    ll sdp[n+1]={},tdp[n+1]={};
    for(int j=1;j<=i;j++){
      if(s[i-1]=='>'){
        sdp[j]=(sdp[j]+dp[i][j])%MOD;
      }else{
        tdp[j+1]=(tdp[j+1]+dp[i][j])%MOD;
      }
    }

    for(int j=1;j<=i;j++) tdp[j+1]=(tdp[j+1]+tdp[j])%MOD;
    for(int j=i+1;j>1;j--) sdp[j-1]=(sdp[j-1]+sdp[j])%MOD;
    
    for(int j=1;j<=i+1;j++) dp[i+1][j]=(sdp[j]+tdp[j])%MOD;
  }

  ll ans=0;
  for(int i=1;i<=n;i++) ans=(ans+dp[n][i])%MOD;
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 70400
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int arr[n];
	int sum=0;
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	sort(arr,arr+n);
	for(int i=0;i<n-1;i++)
		sum += (arr[i+1]-arr[i]);
	cout<<sum<<endl;
	return 0;
}

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

import static java.lang.Integer.parseInt;

/**
 * Alphametic - Accepted
 */
public class Main {

	static int[] nums;
	static boolean[] used;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		words = br.readLine().split(" ");

		nums = new int[9];
		used = new boolean[10];

		for (int i = 0; i < words.length; i++) {
			nums[i] = parseInt(words[i]);
			if (nums[i] != -1) used[nums[i]] = true;
		}

		System.out.println(solve(0));
	}

	static int solve(int idx) {

		if (idx == nums.length) {
			int a = nums[3] * 100 + (nums[1] + nums[4]) * 10 + nums[0] + nums[2] + nums[5];
			int b = nums[6] * 100 + nums[7] * 10 + nums[8];
			if (a == b) return 1;
			else return 0;
		}

		//
		int ret = 0;

		if (nums[idx] == -1) {
			for (int k = 1; k <= 9; k++) {
				if (!used[k]) {
					nums[idx] = k;
					used[k] = true;
					ret += solve(idx + 1);
					nums[idx] = -1;
					used[k] = false;
				}
			}
		} else {
			ret = solve(idx + 1);
		}

		return ret;
	}
}

Measured memory_bytes: 25532
#[allow(unused_macros)]
macro_rules! input {
    ( $($t:ty),* ) => {{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s);
        let mut splits = s.trim().split_whitespace();
        ($( { splits.next().unwrap().parse::<$t>().unwrap() },)*)
    }}
}

#[allow(unused_must_use)]
#[allow(unused_variables)]
fn solve() {
    let (l, r) = input!(usize, usize);
    let mut count = 0;
    let mut set = std::collections::HashSet::with_capacity(2019);

    for i in l..(r+1) {
        let mut inner_count = 0;
        for j in (i+1)..(r+1) {
            set.insert((i * j) % 2019);
            if inner_count == 2019 {
                break;
            }
            inner_count += 1;
        }
        if count == 2019 {
            break;
        }
        count += 1;
    }

    println!("{}", set.iter().min().unwrap());
}

fn main() {
    solve();
}


Measured memory_bytes: 4352
#include <stdio.h>
int xg,yg,c,sc,ans,block[101][101],w,h;
int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int idou(int x,int y)
{
    if(x == xg&&y == yg)
    {
        ans = 1;
        return 0;
    }
    if(sc == 0)return 0;
    block[x][y] = 0;
    for(int i = 0; i < 4; i++)
    {
        if(block[x + dx[i]][y + dy[i]] == sc)idou(x + dx[i],y + dy[i]);
    }
    return 0;
}
int main()
{
    while(1)
    {
        int xs,ys,n,d,x,y;
        ans = 0;
        for(int i = 0; i < w; i++)
        {
            for(int j = 0; j < h; j++)
            {
                block[i][j] = 0;
            }
        }
        scanf("%d%d",&w,&h);
        if(w == 0&&h == 0)break;
        scanf("%d%d",&ys,&xs);
        scanf("%d%d",&yg,&xg);
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d%d%d",&c,&d,&y,&x);
            if(d == 1)
            {
                for(int i = 0; i < 2; i++)
                {
                    for(int j = 0; j < 4; j++)
                    {
                        block[x + j][y + i] = c;
                    }
                }
            }
            if(d == 0)
            {
                for(int i = 0; i < 2; i++)
                {
                    for(int j = 0; j < 4; j++)
                    {
                        block[x + i][y + j] = c;
                    }
                }
            }
        }
        sc = block[xs][ys];
        //block[xg][yg] = 9;
        /*for(int i = 0; i < w; i++)
        {
            for(int j = 0; j < h; j++)
            {
                printf("%d",block[i][j]);
            }
            printf("\n");
        }*/
        idou(xs,ys);
        if(ans == 1)printf("OK\n");
        else printf("NG\n");
    }
    return 0;
}

Measured memory_bytes: 1052
N, M = map(int,input().split())
alist = list()
for _ in range(M):
    alist.append(int(input()))


li = {}
li[0] = 1

for i in range(1,N+1):
    if len(alist)>=1 and i ==  alist[0]:
        li[i] = 0
        alist.pop(0)
    else:
        if i == 1:
            li[i] = 1
        else:
            li[i] = ((li[i-1] + li[i-2])%(10**9+7))
print(li[N]%(10**9+7))

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

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

using ll = long long;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
  ll N;
  cin >> N;
  vector<ll> v(N+1LL);
  for(ll i = 0LL; i < N; i++) {
    cin >> v[i+1LL];
  }
  vector<ll> ans(N+1,0LL);
  for(ll i = N; i>=1; i--) {
    ll t = N/i;
    ll s = 0LL;
    for(ll j = 2LL; j <= t;j++) {
      s+=ans[j*i];
    }
    ans[i]=(s+v[i])%2LL;
  }
  ll cnt = 0LL;
  for(ll i = 1LL; i <= N; i++) {
    cnt += ans[i];
  }
  cout<<cnt<<endl;
  for(ll i = 1LL; i <=N; i++) {
    if(ans[i]==1LL)cout<<i<<" ";
  }
  cout<<endl;
}

Measured memory_bytes: 3968
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1e18;

int main(){
    int n;
    cin>>n;
    vector<int> e[n];
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        --a,--b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    int c[n];
    memset(c,-1,sizeof(c));
    queue<int> q[2][2];
    int t=0;
    q[0][t].push(0);
    q[1][t].push(n-1);
    while(q[0][t].size()||q[1][t].size()){
        for(int i=0;i<2;i++){
            while(q[i][t].size()){
                int k=q[i][t].front();
                q[i][t].pop();
                for(int l:e[k]){
                    if(c[l]==-1){
                        c[l]=i;
                        q[i][t^1].push(l);
                    }
                }
            }
        }
        t^=1;
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        if(c[i]==0)cnt++;
    }
    if(cnt>n-cnt)cout<<"Fennec"<<endl;
    else cout<<"Snuke"<<endl;
}


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

int main(){
	int a,b,c,sum;
	cin>>a>>b>>c;
	for(int i=1;i<=1e6;i++){
		sum+=a*i;
		if((b*i+c)%a==0){
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
	return 0;
} 

Measured memory_bytes: 3604
#include<bits/stdc++.h>
#define maxn 510
using namespace std;
int n,m;
char red[maxn][maxn],blue[maxn][maxn];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i+=2)
        for(int j=1;j<=m;j++)
            red[i][j]='#';
    for(int i=2;i<=n;i+=2)
        for(int j=1;j<=m;j++)
            red[i][j]='.';
    for(int i=2;i<=n;i+=2)
        for(int j=1;j<=m;j++)
            blue[i][j]='#';
    for(int i=1;i<=n;i+=2)
        for(int j=1;j<=m;j++)
            blue[i][j]='.';
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char cur;
            cin>>cur;
            if(cur=='#')  red[i][j]='#',blue[i][j]='#';
        }
    }
    for(int i=1;i<=n;i++)
        red[i][1]='#',blue[i][1]='.';
    for(int i=1;i<=n;i++)
        red[i][m]='.',blue[i][m]='#';
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++)
          	putchar(red[i][j]);
        putchar('\n');
    }
    putchar('\n');
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
          	putchar(blue[i][j]);
        putchar('\n');
    }
    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
using p = pair<int,int>;
static const long long INF = 1000000007;

int main(){
    int a,b;
    cin >> a >> b;
    rep(i,max(a,b)){
        cout << min(a,b);
    }
    cout << endl;

}

Measured memory_bytes: 3548
import math
X = int(input())
list1 = []

for i in range(2,X+1):
  for j in range(2,int((X + 1)/2)):
    a = math.log10(i)/math.log10(j)
    if a.is_integer():
      list1.append(i)
if list1 == []:
  print(1)
else:
  print(max(list1))


Measured memory_bytes: 9284
#define DBG 0 //submit 0
#define ll long long
#if DBG
    #include <algorithm>
    #include <array>
    #include <ctime>
    #include <cstdlib>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <iostream>
    #include <cmath>
    #include <queue>
    #include <numeric>
#else
    #include <bits/stdc++.h>
#endif
 
using namespace std;
 
 
int main(){
    //int a[100005],b[100005],c[100005];
    //bool flag=false,d[100005];
    ll a,b,r,x,tmp,n,ans=1;
    //char s[105],t[105],u;
   
    cin >> a >> b;
    //for(int i=0;i<n;i++) cin >> s[i];
    //for(int i=0;i<n;i++) cin >> t[i];

    x = a * b;
 
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }

    
    ans = x/b;
    
    //cout << (!flag ? "Yes" : "No");
    cout << ans;
    //cout << s;
    //printf("%.10f",ans_d);
    cout << endl;
}


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

int main(){
  int n;
  cin >> n;
  vector<int> ans(n+1);
  for(int x = 1; x <= 100; x++){
    for(int y = 1; y <= 100; y++){
      for(int z = 1; z <= 100; z++){
        int s = x*x + y*y + z*z;
        s += x*y + x*z + y*z;
        if(s > n){
          continue;
        }
        ans[s]++;
      }
    }
  }
  for(int i = 1; i <= n; i++){
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 3564
#include<bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007
#define Vi vector<int>
#define Vl vector<long long>
#define pb(a) push_back(a)

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=10000000000000000001;
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct edge{int to,cost;};
struct pos{
	int x,y,cost;
};
int f[102]={};

int main() {

	int x,n;
	cin>>x>>n;

	rep(i,n){
		int p;
		cin>>p;
		f[p]=1;
	}
	int mi=x,ans=0;
	for(int i=1; i<102; i++){
		if(f[i]==0&&mi>abs(x-i)){
			mi=abs(x-i);
			ans=i;
		}
	}
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 3636
#pragma GCC opimize (3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int n;
	int p[105];
	cin >> n;
	for(int i = 1; i <= n; ++i) 
		cin >> p[i];
	int ans = 0x3f3f3f3f;
	for(int i = 1; i <= 100; ++i) {
		int tmp = 0;
		for(int j = 1; j <= n; ++j)
			tmp += (p[j] - i) * (p[j] - i);
		ans = min(tmp, ans);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <float.h>
#include <inttypes.h>
#include <limits.h>
#include <signal.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#ifdef __cplusplus
#include <bits/stdc++.h>
#endif
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define getchar getchar_unlocked
#define putchar putchar_unlocked
int32_t nextint(void){ char c=getchar(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar(); bool s=false; if(c=='-'){s=true;c=getchar();} uint32_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar(); } return s?-x:x; }
int64_t nextlong(void){ char c=getchar(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar(); int s=0; if(c=='-'){s=1;c=getchar();} uint64_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar(); } return s?-x:x; }
uint32_t nextstr(char *s){ char c=getchar(); while(c==' '||c=='\n') c=getchar(); uint32_t len=0; while(c!=' '&&c!='\n'){ *s++=c; len++; c=getchar(); } *s='\0'; return len; }

int edge[300000][2];

int qmem[600000];

int *e[300000];
int el[300000];

int d[300000];
int a[1000000][2];
int s=0;

void push(int x, int y){
	int c=s++, p=(c-1)/2;
	while(c>0 && x<a[p][0]){
		a[c][0]=a[p][0];
		a[c][1]=a[p][1];
		c=p, p=(c-1)/2;
	}
	a[c][0]=x;
	a[c][1]=y;
}
int pop(int *t){
	int td=a[0][0];
	*t=a[0][1];
	s--;
	int x=a[s][0], y=a[s][1];
	int p=0, c=p*2+1;
	while(c<s && a[c=(c+1<s&&a[c+1][0]<a[c][0])?c+1:c][0]<x){
		a[p][0]=a[c][0];
		a[p][1]=a[c][1];
		p=c, c=p*2+1;
	}
	a[p][0]=x;
	a[p][1]=y;
	return td;
}

void dike(int x){
	push(0,x);
	d[x]=0;
	while(s){
		int p;
		if(pop(&p)>d[p]) continue;
		for(int i=0; i<el[p]; i++){
			int to=e[p][i];
			long now=d[p]+1;
			if(now<d[to]){
				d[to]=now;
				push(now,to);
			}
		}
	}
}

int main(void){
	int n=nextint();
	int m=nextint();
	for(int i=0; i<m; i++){
		int A=nextint()-1;
		int B=nextint()-1;
		edge[i*3+0][0]=A*3+0; edge[i*3+0][1]=B*3+1; el[A*3+0]++;
		edge[i*3+1][0]=A*3+1; edge[i*3+1][1]=B*3+2; el[A*3+1]++;
		edge[i*3+2][0]=A*3+2; edge[i*3+2][1]=B*3+0; el[A*3+2]++;
	}
	int ne=0;
	for(int i=0; i<n*3; i++){
		e[i]=&qmem[ne];
		ne+=el[i];
		el[i]=0;
	}
	for(int i=0; i<m*3; i++){
		int A=edge[i][0];
		int B=edge[i][1];
		e[A][el[A]++]=B;
	}
	int s=(nextint()-1)*3;
	int t=(nextint()-1)*3;
	for(int i=0; i<n*3; i++){
		d[i]=INT_MAX;
	}
	dike(s);
	printf("%d\n", d[t]==INT_MAX?-1:d[t]/3);
}


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

int n,m,q;
ll point[51][4];
ll s=0;

ll score(const vector<int> &A){
  ll ans=0;
  for(int i=0;i<q;i++){
    if(A[point[i][1]]-A[point[i][0]]==point[i][2]){
      ans+=point[i][3];
    }
  }
  return ans;
}

void dfs(vector<int> &A){
  if(A.size()==n){
    s=max(score(A),s);
    return;
  }
  int p;
  if(A.size()==0){
    p=1;
  }
  else{
    p=A.back();
  }
  for(int v=p;v<=m;v++){
    A.push_back(v);
    dfs(A);
    A.pop_back();
  }
}

int main(){
  cin>>n>>m>>q;
  for(int i=0;i<q;i++){
    cin>>point[i][0]>>point[i][1]>>point[i][2]>>point[i][3];
    point[i][0]--;
    point[i][1]--;
  }
  vector<int> A;
  dfs(A);
  cout<<s<<endl;
}

Measured memory_bytes: 3632
#include<iostream>
using namespace std;
int main(){
	int x,a,b;
	cin>>x>>a>>b;
	if(a-b >= 0){
		cout<<"delicious"<<endl;
	}
	else if(b-a <= x){
		cout<<"safe"<<endl;
	}
	else{
		cout<<"dangerous"<<endl;
	}
	
	return 0;
}

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

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
int n,x,y,a[2002][2002],val[2002];
void solve(){
    cin>>n>>x>>y;
    rep(i,1,n+1){
        rep(j,1,n+1){
            a[i][j]=abs(i-j);
        }
    }
    a[x][y]=1;
    a[y][x]=1;
    rep(i,1,n+1){
        rep(j,1,n+1){
            a[i][j]=min(a[i][j],a[i][x]+1+a[y][j]);
            a[i][j]=min(a[i][j],a[i][y]+1+a[x][j]);
        }
    }
    rep(i,1,n+1){
        rep(j,1,n+1){
            val[a[i][j]]++;
        }
    }
    rep(i,1,n) cout<<val[i]/2<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 15872
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def resolve():
    n, m = map(int, input().split())
    first_ac_dic = {}
    wa_count_dic = {}
    wa_num = 0
    for i in range(m):
        p, s = input().split()
        p = int(p)

        if s == "AC":
            if p in first_ac_dic:
                pass
            else:
                first_ac_dic[p] = i
                wa_num += wa_count_dic.get(p, 0)
        else:
            wa_count_dic[p] = wa_count_dic.get(p, 0) + 1

    ans_ac = len(first_ac_dic)

    print(ans_ac, wa_num)


if __name__ == "__main__":
    resolve()



Measured memory_bytes: 56408
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    string ans="";
    ll n,k;cin>>n>>k;
    while(n>0){
        ans.push_back('0'+n%k);
        n/=k;
    }
    cout<<ans.size()<<endl;
    return 0;
}


Measured memory_bytes: 256
N,K=map(int,input().split())
H=[int(input()) for i in range(N)]
H.sort()
ans=0
for i in range(N-K+1):
  if(i==0):
    ans=H[i+K-1]-H[i]
  else:
    ans=min(ans,H[i+K-1]-H[i])
print(ans)

Measured memory_bytes: 7384
def main():
    N, K = map(int, input().split())
    S = input()
    ans = 0
    prev_c = "_"
    for c in S:
        if prev_c == c:
            ans += 1
        prev_c = c
    k = N-1-ans
    ans += min(K*2, k)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <utility>
#include <cstdlib>
using namespace std;
typedef long long int lli;
const lli mod = 1e9 +7;
const lli inf = 1e18;
typedef pair<lli, lli> pll;

//euclid
lli gcd(lli a, lli b){
    if(a%b==0) return b;
    return gcd(b,a%b);
}

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

lli solve_(lli a, lli d){
    return a/d;
}
lli solve(lli a, lli b, lli d){
    return b/d - (a-1)/d;
}

int main(){
    lli a,b,c,d;
    cin >> a >> b >> c >> d;
    cout << b-a+1 -(solve(a, b, c) +solve(a, b, d) -solve(a, b, lcm(c, d))) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
      long long a,b,c,z;
     scanf("%lld%lld%lld",&a,&b,&c);
    if(a==0)
    {
        z=(b/c)+1;
    }
    else
    {
        z=(b/c)-(a-1)/c;
    }
    printf("%lld",z);

}


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

int main(){
    string s;
    cin >> s;
    if(s == "SUN"){
        cout << 7;
    }else if(s == "MON"){
        cout << 6;
    }else if(s == "TUE"){
        cout << 5;
    }else if(s == "WED"){
        cout << 4;
    }else if(s == "THU"){
        cout << 3;
    }else if(s == "FRI"){
        cout << 2;
    }else if(s == "SAT"){
        cout << 1;
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>

int main(){
  int X,Y,Z,K;
  std::cin >> X >> Y >> Z >> K;

  std::vector<long long int> X_arr(X), Y_arr(Y), Z_arr(Z), XY_arr, XYZ_arr;
  for(int i = 0; i < X; i++) std::cin >> X_arr[i];
  for(int i = 0; i < Y; i++) std::cin >> Y_arr[i];
  for(int i = 0; i < Z; i++) std::cin >> Z_arr[i];

  for(int i = 0; i < X; i++){
    for(int j = 0; j < Y; j++){
      XY_arr.push_back(X_arr[i]+Y_arr[j]);
    }
  }
  std::sort(XY_arr.begin(), XY_arr.end(), std::greater<long long int>());
  XY_arr.resize(K);
  for(int i = 0; i < K; i++){
    for(int j = 0; j < Z; j++){
      XYZ_arr.push_back(XY_arr[i]+Z_arr[j]);
    }
  }
  std::sort(XYZ_arr.begin(), XYZ_arr.end(), std::greater<long long int>());
  for(int i = 0; i < K; i++) std::cout << XYZ_arr[i] << std::endl;

  return 0;
}



Measured memory_bytes: 43240
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int a[MAXN];
int main() {
	int n, power = 1; read(n);
	while (power < n) power <<= 1;
	if (n == power) {
		puts("No");
		return 0;
	}
	puts("Yes");
	power >>= 1;
	if (n % 4 == 0) {
		for (int i = 1; i <= n - 1; i++)
			a[i] = i;
		swap(a[power - 1], a[n ^ power]);
		for (int i = 1; i <= n - 2; i++)
			printf("%d %d\n", a[i], a[i + 1]);
		printf("%d %d\n", a[n - 1], n + a[1]);
		for (int i = 1; i <= n - 2; i++)
			printf("%d %d\n", n + a[i], n + a[i + 1]);
		printf("%d %d\n", n, power);
		printf("%d %d\n", 2 * n, n ^ power);
	}
	if (n % 4 == 1) {
		for (int i = 2; i <= n - 1; i++)
			printf("%d %d\n", i, i + 1);
		printf("%d %d\n", n, n + 2);
		for (int i = 2; i <= n - 1; i++)
			printf("%d %d\n", n + i, n + i + 1);
		printf("%d %d\n", 1, 2);
		printf("%d %d\n", n + 1, 3);
	}
	if (n % 4 == 2) {
		for (int i = 2; i <= n - 1; i++)
			a[i] = i;
		swap(a[power - 1], a[n ^ power]);
		if ((n ^ power) == 2 && n != 6) swap(a[power - 2], a[3]);
		for (int i = 2; i <= n - 2; i++)
			printf("%d %d\n", a[i], a[i + 1]);
		printf("%d %d\n", a[n - 1], n + a[2]);
		for (int i = 2; i <= n - 2; i++)
			printf("%d %d\n", n + a[i], n + a[i + 1]);
		printf("%d %d\n", n, power);
		printf("%d %d\n", 2 * n, n ^ power);
		printf("%d %d\n", 1, 2);
		printf("%d %d\n", 1 + n, 3);
	}
	if (n % 4 == 3) {
		for (int i = 1; i <= 2 * n - 1; i++)
			printf("%d %d\n", i, i + 1);
	}
	return 0;
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,string> P;
typedef long long int lld;
#define INF (1<<20)

int main(){
  int n;
  cin >> n;
  vector<P> product;
  map<string,int> count;
  for(int i=0;i<n;i++){
    string name; int num;
    cin >> name >> num;
    if(count[name] == 0) product.push_back(P(name.size(),name));
    count[name] += num;
  }
  sort(product.begin(),product.end());
  for(int i=0;i<product.size();i++){
    cout << product[i].second << " " << count[product[i].second] << endl;
  }
}

Measured memory_bytes: 1232
/*
    BFS(bread-first search，幅優先探索)を用いる
    アリ本pp.87以降にグラフの解説がある
*/
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cmath>
using namespace std;

#define repeat(i, n) for (int i = 0; i < (n); i++)
#include<queue>

const int INF = 1001001001;
// vector<int>の配列
// なんでこんなことしてるの...？
vector<int> to[100005];

int main(void)
{
    // 部屋数N、通路数M
    int N, M;
    cin >> N >> M;

    repeat(i, M){
        // 互いに通行可能な部屋a-b
        int a, b;
        cin >> a >> b;
        // 配列格納用にデクリメント処理
        a--;
        b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }

    queue<int> q;
    vector<int> dist(N, INF);   // 無限大で初期化
    vector<int> pre(N, -1); // -1で初期化
    dist[0] = 0;
    q.push(0);
    while (!q.empty())
    {
        int v = q.front();  // 先頭要素の確認
        q.pop();    // 取り出し(上のと一緒くたにできないの...?)
        // 拡張for文(だっけ？)
        for (int u : to[v])
        {
            // 既に距離が算出されていれば以降の処理を省く
            if (dist[u] != INF)
            {
                continue;
            }
            // 繋がっている部屋のゴールまでの距離+1がゴールまでの距離
            dist[u] = dist[v] + 1;
            // 道しるべの部屋番号を記録
            pre[u] = v;
            // キューに自身を格納(幅優先探索の処理、これに基づいて子を展開する)
            q.push(u);
        }
    }

    puts("Yes");
    repeat(i, N){
        if (i == 0){
            continue;
        }
        int ans = pre[i];
        printf("%d\n", ans+1);
    }

    return 0;
}

Measured memory_bytes: 10724
#include <iostream>
#include <bits/stdc++.h>
#include <stdio.h>

typedef long long ll;
using namespace std;



bool isPrime(int n){
    if(n < 2){
        return 0;
    }
    if(n%2 == 0){
        return n==2;
    }
    for(int i=3;i*i<=n;i++){
        if(n%i == 0) return 0;
    }
    return 1;
}

void allPoss(int indx,int n,vector<int> v,vector<vector<int>> &vv){
    if(indx == n) {
        vv.push_back(v);
        return;
    }
    v.push_back(indx);
    allPoss(indx+1,n,v,vv);
    v.pop_back();
    allPoss(indx+1,n,v,vv);
}

int main() {
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<char>> g(n,vector<char>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)cin>>g[i][j];
    }
    vector<vector<int>> vn;
    vector<vector<int>> vm;
    vector<int> v;
    allPoss(0,n,v,vn);
    v.clear();
    allPoss(0,m,v,vm);
    int f = 0;
    for(int i=0;i<vn.size();i++){
        for(int j=0;j<vm.size();j++){
            vector<vector<char>> gg(n,vector<char>(m));
            for(int ii=0;ii<n;ii++){
                for(int ji=0;ji<m;ji++)gg[ii][ji]=g[ii][ji];
            }
            for(int r=0;r<vn[i].size();r++){
                for(int h=0;h<m;h++)gg[vn[i][r]][h] = '.';

            }
            for(int c=0;c<vm[j].size();c++){
                for(int h=0;h<n;h++)gg[h][vm[j][c]] = '.';

            }
            int l =0;
            for(int ii=0;ii<n;ii++){
                for(int ji=0;ji<m;ji++){
                    if(gg[ii][ji] == '#') l++;
                }
            }
            if(l == k)f++;
        }
    }
    cout<<f<<endl;
    return 0;
}


Measured memory_bytes: 3648
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define FOR(i, m, n) for(ll i = m; i < (n); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vii = vector<vi>;
using pii = pair<int, int>; 
using vl = vector<ll>;
using vll = vector<vl>;
using pll = pair<ll, ll>;

const ll INF = 10e9;

int main() {
    ll n, m;
    cin >> n >> m;
    vl c(m);
    rep(i, m){
        cin >> c[i];
    }
    //dp[i][v]:=左からi種類までのコインでv円払うときのコインの最小枚数
    vll dp(m+10, vl(n+10));
    rep(i, m+1){
        dp[i][0] = 0;
    }
    rep(i, n+1){
        dp[0][i] = INF;
    }
    rep(i, m){
        FOR(j, 1, n+1){
            if(j >= c[i]){
                dp[i+1][j] = min(dp[i+1][j-c[i]]+1, dp[i][j]);
            }
            else dp[i+1][j] = dp[i][j];
        }
    }
    cout << dp[m][n] << endl;
}


Measured memory_bytes: 15048
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repe(i,n) for (int i = 0; i <= (n); ++i)
#define repe1(i,n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define eb(k,v) emplace_back(k,v)
#define ct(res) cout << res << "\n";
#define vi vector<int>
#define vl vector<ll>
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1e9;
const ll MOD = 1000000007;
const double pi = 3.141592653589;
using Graph = vector<vector<int>>;
ll gcd(ll a, ll b) {return (a%b) ? gcd(b, a%b) : b;}
ll modPow(ll x, ll n) {
    if(n==0) return 1;
    ll res = modPow(x*x%MOD, n/2);
    if(n&1) res=res*x%MOD;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while(true) {
        int n,x; cin>>n>>x;
        if (n==x && n==0) {
            return 0;
        }
        int cnt = 0;
        for(int i=1; i<=n; ++i) {
            for (int j=i; j<=n; ++j) {
                for (int k=j; k<=n; ++k) {
                    if (i==j || j==k || i==k) continue;
                    if (i+j+k==x) {
                        cnt++;
                    }
                }
            }
        }
        ct(cnt);
    }
}


Measured memory_bytes: 3208
n = int(input())
a = list(map(int, input().split()))
q = int(input())
BC = []
B = 0
C = 1
for i in range(q):
   BC.append(list(map(int, input().split())))

cnt = [0] * (10**5 + 1)
S = sum(a)

for _a in a:
    cnt[_a] += 1

for bc in BC:
    bCount = cnt[bc[B]]
    cnt[bc[B]] = 0
    cnt[bc[C]] += bCount
    S += (bc[C] - bc[B])*bCount
    print(S)



Measured memory_bytes: 31980
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

//find_by_order gives kth-largest element
//order_of_key gives the number of items in the set that are strictly smaller!!

// OT.find_by_order(k-1)
// 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define db4(x, y, z, w) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << "," << #w << "=" << w << endl
#define ll long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define X first
#define Y second
#define sz(x) (int)((x).size())
#define pii pair<int,int>
#define MOD (ll)(998244353)
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
typedef vector<int> vi;
#define inf (ll)(1e18)
#define double long double
#define int long long
 
int32_t main() {
	
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> v(n);
    rep(i,n) cin >> v[i];

    vector<int> arr(n);
    arr[n-1] = 0;
    int mx = 0;
    repD(i,n-2,0) {
    	if(v[i] >= v[i+1])
    		arr[i] = arr[i+1] + 1;
    	else
    		arr[i] = 0;
    	mx = max(mx, arr[i]);
    }
    cout << mx << '\n';
}

// Mistakes
// j or k --> i
// read question again

Measured memory_bytes: 1792
// IOI 2021
#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 998244353;
 
////////////////////////////////////////////////////////////////////
 
const int N = 1e5 + 5;

int A[N], B[N], P[N], c;
bool C[N];

int GetPar(int v) { return P[v] == v ? v : P[v] = GetPar(P[v]); }
bool Merge(int v, int u) {
	v = GetPar(v), u = GetPar(u);
	if (v == u) return false;
	P[v] = u;
	c--;
	return true;
}

int main() {
 
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	int n; cin >> n; c = n;
	ll m ; cin >> m;
	int q; cin >> q;
	for (int i = 0; i < n; i++) P[i] = i;
	for (int i = 0; i < q; i++) {
		cin >> A[i] >> B[i] >> C[i];
		if (!C[i]) Merge(A[i], B[i]);
		if (m == n - 1 && C[i]) die("No");
	}
	if (m == n - 1) die("Yes");
	for (int i = 0; i < q; i++) if (C[i] && GetPar(A[i]) == GetPar(B[i])) die("No");
	int k = n - c;
	cout << (m <= k + 1LL * c * (c - 1) / 2 ? "Yes" : "No") << endl;

	return 0;
}


Measured memory_bytes: 4888
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define LIMIT 1000000007 //10^9+7
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define all(v) (v).begin(), (v).end()

int main(){
  int N;cin>>N;
  int bits = 0;
  vector<int> A(N);

  rep(i,N){
    int x;cin>>x;
    A[i] = x;
    bits ^= x;
  }

  rep(i,N){
    cout<<(A[i]^bits)<<" ";
  }
  cout<<endl;
}


Measured memory_bytes: 3900
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct Point{
	double x,y;
}p[N],rt;
double R;
double sqr(double x) {return x*x;}
double dis(Point x,Point y) {return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
bool incircle(Point x) {return dis(rt,x)<=R;}
Point solve(double a,double p,double c,double d,double e,double f) {
	double y=(f*a-c*d)/(p*d-e*a);
	double x=(f*p-c*e)/(a*e-p*d);
	return {x,y};
}
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%lf%lf",&p[i].x,&p[i].y);
	}
	R=0;
	for(int i=1;i<=n;i++) {
		if(incircle(p[i])) continue;
		rt=p[i];
		R=0;
		for(int j=1;j<i;j++) {
			if(incircle(p[j])) continue;
			rt.x=(p[i].x+p[j].x)/2;
			rt.y=(p[i].y+p[j].y)/2;
			R=dis(rt,p[i]);
			for(int k=1;k<j;k++) {
				if(incircle(p[k])) continue;
				rt=solve(
					p[i].x-p[j].x,p[i].y-p[j].y,(sqr(p[j].x)+sqr(p[j].y)-sqr(p[i].x)-sqr(p[i].y))/2,
					p[i].x-p[k].x,p[i].y-p[k].y,(sqr(p[k].x)+sqr(p[k].y)-sqr(p[i].x)-sqr(p[i].y))/2);
				R=dis(rt,p[i]);
			}
		}
	}
	printf("%.12f\n",R);
	return 0;
}

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

typedef long long ll;
int main(void){
    int n,w;
    cin >> n >> w;
    vector<pair<ll,ll>>a(n);
    ll max_val = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i].first >> a[i].second;
        max_val += a[i].second;
    }
    vector<vector<ll>> dp(2,vector<ll>(max_val + 1,INT_MAX));
    
    dp[0][0] = 0,dp[1][0] = 0;
    for(int i = 0; i < n; i++){
        int currRow = i & 1;
        for(int j = 0; j <= max_val; j++){
            if(a[i].second <= j){
                dp[currRow][j] = min(dp[currRow ^ 1][j],a[i].first + dp[currRow ^ 1][j - a[i].second]);
            }else
                dp[currRow][j] = min(dp[currRow ^ 1][j],dp[currRow][j]);
        }
    }
    int last_row = (n - 1) & 1;
    for(int i = max_val; i >= 0; i--){
        if(dp[last_row][i] <= w){
            cout << i << endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 2560
#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;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = (ll)a;i < (ll)b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = (ll)b-1LL;i >= (ll)a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

const ll INF=(1LL<<50);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}



int main(){
  cout<<setprecision(1000);
  ll N,K;
  cin>>N>>K;
  vector<ll> A(N);
  REP(N){
    cin>>A[i];
    --A[i];
  }
  ll cur=0;
  vector<ll> loop(1);
  set<ll> s;
  s.insert(0);
  REP(K){
    cur=A[cur];
    if(s.count(cur)){
      break;
    }
    loop.push_back(cur);
    s.insert(cur);
  }
  ll start=0,llen=0;
  REP(loop.size()){
    if(loop[i]==A[loop.back()]){
      start=i;
      llen=loop.size()-i;
      break;
    }
  }
  if(K<loop.size()){
    cout<<loop[K]+1<<endl;
  }else{
    cout<<loop[(K-start)%llen+start]+1<<endl;
  }
  return 0;
}


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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define REPS(i, m, n) for (int i = (m); i <= (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define rreps(i, x) for (int i = (int)(x); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos(-1.0);
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; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill( (T*)array, (T*)(array+N), val ); }
template <class T1, class T2, class Pred = std::less<T2> >
struct sort_pair_second {
    bool operator()(const std::pair<T1,T2>&left, const std::pair<T1,T2>&right) {
        Pred p;
        return p(left.second, right.second);
    }
};

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

    int a, b, c;
    cin >> a >> b >> c;
    if (a == b && b == c) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
H, W = list(map(int,input().split()))
ans = H*W
h = H
w = W
for i in range(h//3,h//2+1):
    p1 = i*w
    for j in range((h-i)//2-1,(h-i)//2+1):
        p2 = (h-i-j)*W
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
    for j in range(w//2-1,w//2+1):
        p2 = (h-i)*(w-j)
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
h = W
w = H
for i in range(h//3,h//2+1):
    p1 = i*w
    for j in range((h-i)//2-1,(h-i)//2+1):
        p2 = (h-i-j)*H
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
    for j in range(w//2-1,w//2+1):
        p2 = (h-i)*(w-j)
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n;
  cin >> n;
  vl a(n);
  rep(i, n) cin >> a[i];
  ll ans = 1e9;
  for(int i = -100; i <= 100; i++) {
    ll now = 0;
    rep(j, n) now += pow(i - a[j], 2);
    ans = min(ans, now);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int T[10],i,m,n,x,sum;
    for(i=0; i<5; i++)
        scanf("%d",&T[i]);
    x=0;
    n=10;
    for(i=0; i<5; i++)
    {
        m=T[i]-(T[i]/10)*10;
        if(m!=0&&m<n)
        {
            n=m;
            x=i;
        }
    }
    sum=0;
    for(i=0; i<5; i++)
    {
        if(i!=x)
        {
            if(T[i]%10==0)
                sum+=T[i];
            else
                sum+=(T[i]/10)*10+10;
        }
    }
    sum+=T[x];
    printf("%d\n",sum);
    return 0;
}


Measured memory_bytes: 128