akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const int DIM = 1e5 + 5;

int cnt[DIM], lev[DIM], fth[DIM];
vector<int> edg[DIM]; pair<int, int> lst[DIM];

void dfs( int x, int f, int &cnt1, int &cnt2, int &p, int &q ) {
    lev[x] = lev[f] + 1; fth[x] = f;
    
    if( cnt[x] == 1 ) cnt1 ++;
    else              cnt2 ++;
    
    int val = -cnt[x];
    for( int y : edg[x] ) {
        if( y == f )
            continue;
        
        if( lev[y] == 0 ) {
            cnt[y] = val;
            dfs( y, x, cnt1, cnt2, p, q );
            cnt[x] += cnt[y];
        }
        else
        if( lev[x] > lev[y] )
            p = x, q = y;
    }
    
    return;
}

int solve( int m, int p, int q ) {
    int ans = 0;
    
    for( int i = 1; i <= m; i ++ ) {
        int x, y;
        tie( x, y ) = lst[i];
        
        if( x == p && y == q ) continue;
        if( y == p && x == q ) continue;
        
        if( lev[x] > lev[y] )
            swap( x, y );
        ans += abs( cnt[y] );
    }
    
    return ans;
}

int main( void ) {
    
    int n, m;
    cin >> n >> m;
    
    for( int i = 1; i <= m; i ++ ) {
        int x, y;
        cin >> x >> y;
        
        edg[x].push_back( y );
        edg[y].push_back( x );
        lst[i] = make_pair( x, y );
    }
    
    int cnt1 = 0, cnt2 = 0, p, q;
    cnt[1] = 1; dfs( 1, 0, cnt1, cnt2, p, q );
    
    if( n == m + 1 ) { // tree
        if( cnt1 != cnt2 )
            cout << -1 << endl;
        else
            cout << solve( m, 0, 0 ) << endl;
    }
    else
    if( ( lev[p] - lev[q] ) & 1 ) { // even cycle
        if( cnt1 != cnt2 )
            cout << -1 << endl;
        else {
            vector<int> aux;
            for( int i = p; i != q; i = fth[i] )
                aux.push_back( cnt[i] );
            
            sort( aux.begin(), aux.end() );
            int ans = aux[(aux.size() + 1) / 2 - 1];
            
            for( int i = p; i != q; i = fth[i] )
                cnt[i] -= ans;
            
            ans = abs( ans );
            ans += solve( m, p, q );
            
            cout << ans << endl;
        }
    }
    else { // odd cycle
        if( abs( cnt2 - cnt1 ) & 1 )
            cout << -1 << endl;
        else {
            int ans = ( cnt2 - cnt1 ) / 2;
            
            for( int i = p; i != 0; i = fth[i] )
                cnt[i] += ans;
            for( int i = q; i != 0; i = fth[i] )
                cnt[i] += ans;
            
            ans = abs( ans );
            ans += solve( m, p, q );
            
            cout << ans << endl;
        }
    }
    
    return 0;
}

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

template<typename T> using V = vector< T >;
using Vi = V<int>;

int main(){
    int n,k;
    cin>>n>>k;
    Vi h(n);
    for(int i=0; i<n; i++){
        cin>>h[i];
    }

    int total=0;
    for(int i=0; i<n; i++){
        if(h[i]>=k){
            total++;
        }
    }

    cout<<total<<endl;

    return 0;
}

Measured memory_bytes: 640
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
template<typename V> constexpr typename V::value_type sum(const V &v) { return accumulate(all(v), 0); }
void solve();
main { solve(); return 0; }
// clang-format on

void solve() {
  int n;
  cin >> n;
  rep(i, n) {
    string s;
    cin >> s;
    string t = s;
    sort(all(s)), sort(rall(t));
    int maxi, mini;
    istringstream(t) >> maxi;
    istringstream(s) >> mini;
    cout << maxi - mini << endl;
  }
}

Measured memory_bytes: 3096
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,b,c,cnt=3;
  cin>>a>>b>>c;
  if(a==b&&b==c)
  {
    cout<<"1"<<endl;
    return 0;
  }
  int x=a^b;
  int i=b^c;
  int y=c^a;
  if(x==0)
  {
    cnt--;
  }
  if(i==0)
  {
    cnt--;
  }
  if(y==0)
  {
    cnt--;
  }
  cout<<cnt<<endl;
  return 0;
}


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

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

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)

ll ds(ll a, ll b) {
  if (a > b) {
    swap(a, b);
  }
  if (!a)
    return b;
  else
    return ds(b % a, a);
}

int main() {
  string S;
  cin >> S;
  if(S.length() == 2) {
    cout << S << endl;
    return 0;
  }else{
    swap(S[0], S[2]);
    cout << S << endl;
    return 0;
  }
}


Measured memory_bytes: 256
import java.util.*;
class Main{
	static HashMap<String,Integer> dat;
	static HashMap<String,Integer> memo;
	static String table[][];
	static String k[];
	static int size[];
	static int b;
	static int solve(String a){
		if(memo.containsKey(a))return memo.get(a);
		if(!dat.containsKey(a))return 999999999;
		int ret=dat.get(a);
		for(int i=0;i<b;i++){
			if(k[i].equals(a)){
				int val=0;
				for(int j=0;j<size[i];j++){
					val+=solve(table[i][j]);
				}
				ret=Math.min(ret,val);
				break;
			}
		}
		memo.put(a,ret);
		return ret;
	}
	public static void main(String[] args){
		Scanner s=new Scanner(System.in);
		int a;
		k=new String[100];
		table=new String[100][100];
		size=new int[100];
		dat=new HashMap<String,Integer>();
		memo=new HashMap<String,Integer>();
		while(true){
			a=s.nextInt();
			dat.clear();
			memo.clear();
			if(a==0)System.exit(0);
			for(int i=0;i<a;i++){
				String str=s.next();
				int p=s.nextInt();
				dat.put(str,p);
			}
			b=s.nextInt();
			for(int i=0;i<b;i++){
				k[i]=s.next();
				size[i]=s.nextInt();
				for(int j=0;j<size[i];j++)table[i][j]=s.next();
			}
		//	System.exit(0);
			String m=s.next();
			System.out.println(solve(m));
		}
	}
}

Measured memory_bytes: 0
/***********************
*  Author: xuziyuan    * 
***********************/

#include <bits/stdc++.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++) 
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

int n,a[3],d[10],ans=1e9;
bool vis[10];

void dfs(int pos,int n1,int n2,int n3,int num)
{
	if(n1>0&&n2>0&&n3>0)ans=min(ans,abs(n1-a[0])+abs(n2-a[1])+abs(n3-a[2])+num*10);
	//if(abs(n1-a[0])+abs(n2-a[1])+abs(n3-a[2])+num*10==120) cout<<n1<<' '<<n2<<' '<<n3<<' '<<num<<endl;
	//if(n1==100&&n2==90&&n3==80)cout<<n1<<' '<<n2<<' '<<n3<<' '<<num<<endl;
	if(pos==n) return;
	dfs(pos+1,n1+d[pos],n2,n3,(n1==0 ? num:num+1));
	dfs(pos+1,n1,n2+d[pos],n3,(n2==0 ? num:num+1));
	dfs(pos+1,n1,n2,n3+d[pos],(n3==0 ? num:num+1));
	dfs(pos+1,n1,n2,n3,num);
}

int main()
{
	cin>>n>>a[0]>>a[1]>>a[2];
	rep(i,n) cin>>d[i];
	dfs(0,0,0,0,0);
	cout<<ans<<endl;
	rt0;
}

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

typedef long long ll;

ll inf = 1LL<<60;
int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<ll > > dst(n,vector<ll>(n)),dst2;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dst[i][j] = inf;
        }
        dst[i][i] = 0;
    }
    for(int i=0;i<m;i++){
        int s,t;
        ll d;
        cin >> s >> t >> d;
        dst[s][t] = d;
    }
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dst[i][k]!=inf&&dst[k][j]!=inf)dst[i][j] = min(dst[i][j],dst[i][k]+dst[k][j]);
            }    
        }
    }
    dst2 = dst;
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dst[i][k]!=inf&&dst[k][j]!=inf)dst[i][j] = min(dst[i][j],dst[i][k]+dst[k][j]);
            }    
        }
    }
    bool flag = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(dst[i][j]!=dst2[i][j]){
                flag = 1;
            }
        }
    }
    if(flag){
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }else{
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dst[i][j]==inf){
                    cout << "INF"; 
                }else{
                    cout << dst[i][j];
                }
                if(j!=n-1){
                    cout << " ";
                }
            }
            cout << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3288
from collections import deque

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    A,B = map(int, input().split())
    edge[A - 1].append(B - 1)

ans = []
for sta in range(N):
    prev = [-1] * N
    que = deque([sta])

    while que:
        v = que.popleft()
        for w in edge[v]:
            if w == sta: # 閉路発見
                path = []
                while v != -1:
                    path.append(v+1)
                    v = prev[v]
                if (not ans) or (len(ans) > len(path)):
                    ans = path
                break

            if prev[w] != -1: continue

            prev[w] = v
            que.append(w)

if ans:
    print(len(ans))
    print(*ans, sep='\n')
else:
    print(-1)

Measured memory_bytes: 3700
// C - Repsept
#include <bits/stdc++.h>
using namespace std;

int f(int k){
	for(int r=7%k, i=1; i<=k; ++i, r=(r*10+7)%k) if(r == 0) return i;
	return -1;
}

int main(){
	int k; cin>>k;
	cout<< f(k) <<endl;
}


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#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 all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
struct edge { int to, cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = ~(1<<31);
const int MOD = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1.0);
 
const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

int main()
{
	int n;
	cin >> n;
	int odd = 0,even = 0;
	for(int i = 1; i <= n; i++){
		if(i%2) odd++;
		else even++;
	}
	cout << odd/(double)(odd+even) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<string>
#include<stdexcept>
#include<stdio.h>
#include<queue>
#include<stack>
#include <cmath>
#include<bits/stdc++.h>
#include<math.h>
#define cinf(n,x) for(int i=0;i<n;i++) cin >> x[i];
#define pi pair<int,int> 
using namespace std;
using ll = long long;

int main(){
    int n,m; cin >> n >> m;
    vector<vector<int>> J(m);
    for(int i=0;i<n;i++){
        int a,b;
        cin >> a >> b;
        if(a > m) continue;
        J[m-a].push_back(b);
    }
    ll ans = 0;
    priority_queue<int> PQ;
    for(int i=m-1;i>=0;i--){
        for(auto& b : J[i]) PQ.push(b);
        if(!PQ.empty()){
            ans += PQ.top(); PQ.pop();
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 5504
fun main(args: Array<String>) {
    val (N,L) = readLine()!!.split(" ").map(String::toInt)
    var list: MutableList<String> = mutableListOf()
    for (i in 1..N) {
        list.add(readLine()!!)
    }
    for(l in list.sorted()) {
        print(l)
    }
}

Measured memory_bytes: 37816
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)
ans = A[0]

if N%2 == 0:
  for i in range(1,int(N/2)):
    ans = ans + A[i]*2
if N%2 == 1:
  for i in range(1,int((N-1)/2)):
    ans = ans + A[i]*2
  ans += A[int((N-1)/2)]
print(ans)



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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;
typedef vector<vll> vvll;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};



ll NMAX=2*1e5+10;
ll n,k;
vll a(NMAX);
bool solve(ll l){
  ll sum=0;
  REP(i,n){
    ll d=a[i]/l;
    if(a[i]%l==0)
      d--;

    sum+=d;
  }

  return sum<=k;
}

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

  cin>>n>>k;
  REP(i,n)cin>>a[i];

  ll ml=0;
  REP(i,n)ml=max(ml,a[i]);

  ll ok=ml;
  ll ng=0;
  while(ok-ng>1){
    ll mid=(ok+ng)/2;
    if(solve(mid))
      ok=mid;
    else
      ng=mid;
  }

  cout<<ok<<endl;


}



Measured memory_bytes: 4688
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <utility>
#include <numeric>

using namespace std;

const uint64_t MOD = 1000000000 + 7;

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

	int a, b;
	a = atoi(s.substr(0, 2).c_str());
	b = atoi(s.substr(2, 2).c_str());

	string f;
	if (1 <= a && a <= 12 && 1 <= b && b <= 12)
	{
		f = "AMBIGUOUS";
	}
	else if (!(1 <= a && a <= 12) && 1 <= b && b <= 12)
	{
		f = "YYMM";
	}
	else if (1 <= a && a <= 12 && !(1 <= b && b <= 12))
	{
		f = "MMYY";
	}
	else
	{
		f = "NA";
	}

	cout << f << endl;
}

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

int main() {
	int N, A, B, ans = 0;
	cin >> N >> A >> B;
	for (int i = 1; i <= N; ++i) {
		int a = 0, b = i;
		do {
			a += b % 10;
		} while (b /= 10);
		if (A <= a && B >= a) ans += i;
	}
	cout << ans;
}

Measured memory_bytes: 256
S=input()
S=list(S)
Check2=[]
Key=True

if S[0]!='A':
    Key=False

Check2=S[2:len(S)-1]
if Check2.count('C')!=1:
    Key=False

if Key==True:
    S.remove('A')
    S.remove('C')
    S=''.join(S)
    if str.islower(S)!=True:
        Key=False
    
if Key==True:
    print('AC')
else:
    print('WA')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  int P=700;
  if (S[0]=='o') P=P+100;
  if (S[1]=='o') P=P+100;
  if (S[2]=='o') P=P+100;
  cout << P << endl;
}

Measured memory_bytes: 256
n = int(input())
a = [list(map(int,input().split())) for l in range(3)]
mnpk = 0
fl = 0
for i in range(n):
  b = a[0][i] - 1
  mnpk = mnpk + a[1][b]
  if fl == 1:
    if a[0][i-1] == b:
      mnpk = mnpk + a[2][b-1]
  else:
    fl = 1
 
print(mnpk)

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;


double calDistance(double x1, double y1, double x2, double y2)
{
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main()
{
    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    cout << fixed << setprecision(4) << calDistance(x1, y1, x2, y2) << endl;

    return 0;
}

Measured memory_bytes: 3272
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::f64::consts::*;

#[allow(unused)]
const INF: usize = std::usize::MAX / 4;
#[allow(unused)]
const M: usize = 1000000007;

fn main() {
    input! {
        h1: usize,
        m1: usize,
        h2: usize,
        m2: usize,
        k: usize,
    }
    let t1 = 60 * h1 + m1;
    let t2 = 60 * h2 + m2;
    println!("{}", t2 - k - t1);
}


Measured memory_bytes: 2168
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i=a;i<=b;++i)
#define read(n)  scanf("%d",&n)
#define ll long long
int main()
{
	string str;
	cin>>str;
	f(i,0,str.length())  if(str[i]=='?') str[i]='D';
	cout<<str;
	return 0;
} 

Measured memory_bytes: 3748
#include <bits/stdc++.h>
using namespace std;
int n,m;
bool yes[10];
int dp[10004],ans[10004],sz[10004];
int num[10]={0,2,5,5,4,5,6,3,7,6};
int main(){
	memset (ans,-1,sizeof(ans));
	cin>>n>>m;
	for (int i=0;i<m;i++){
		int a;cin>>a;
		yes[a]=1;
	}
	ans[0]=0;
	for (int i=1;i<=n;i++)
		for (int j=9;j>=1;j--) if (i-num[j]>=0 && yes[j] && ans[i-num[j]]!=-1)
			if (sz[i-num[j]]+1>sz[i]){
				sz[i]=sz[i-num[j]]+1;
				ans[i]=j;
				dp[i]=i-num[j];
			}
	for (int i=n,j=sz[n];j>0;i=dp[i],j--){
		cout<<ans[i];
	}
	return 0;
}

Measured memory_bytes: 384
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
graph=[[] for _ in range(N)]
color=[-1]*N
for _ in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)

def steps(v,col=0):
    color[v]=col
    for nv in graph[v]:
        if color[nv]!=-1:
            if color[nv]==col: return False
            continue
        if not steps(nv,1-col): return False
    return True

flag=True
for v in range(N):
    if color[v]!=-1: continue
    if not steps(v): flag=False

if flag:
    tmp=color.count(0)
    print(tmp*(N-tmp)-M)
else:
    print(N*(N-1)//2-M)

Measured memory_bytes: 39572
#include<iostream>
using namespace std;
#define MAX 100000
typedef long long llong;
int n,k;
llong T[MAX];
int check(llong P){
    int i=0;
    for(int j=0;j<k;j++){
        llong s=0;
        while(s+T[i]<=P){
            s+=T[i];
            i++;
            if(i==n) return n;
        }
    }
    return i;
}
int solve(){
    llong left=0;
    llong right=10000*100000;
    llong mid;
    while(right-left>1){
        mid=(left+right)/2;
        int v=check(mid);
        if(v>=n) right=mid;
        else left=mid;
    }
    return right;
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>T[i];
    llong ans=solve();
    cout<<ans<<endl;
}


Measured memory_bytes: 3876
#include <stdio.h>
#include <algorithm>

using namespace std;
int main() {
	char S[100002];
	scanf("%s", S + 1);

	int len, dp[100001][2][2];
	for (len = 1; S[len] != 0; len++);
	len--;
	if (S[1] == '0') {
		dp[1][0][0] = len;
		dp[1][0][1] = 0;
		dp[1][1][0] = 1;
		dp[1][1][1] = len;
	} else {
		dp[1][0][0] = 1;
		dp[1][0][1] = len;
		dp[1][1][0] = len;
		dp[1][1][1] = 0;
	}
	for (int i = 2; S[i] != 0; i++) {
		if (S[i] == '0'){
			dp[i][0][0] = max(dp[i - 1][0][0], min(dp[i - 1][0][1], len - i + 1));
			dp[i][1][0] = min(dp[i - 1][0][0], i);
			dp[i][0][1] = min(dp[i - 1][1][1], i);
			dp[i][1][1] = max(dp[i - 1][1][1], min(dp[i - 1][1][0], len - i + 1));
		} else {
			dp[i][0][0] = min(dp[i - 1][1][0], i);
			dp[i][1][0] = max(dp[i - 1][1][0], min(dp[i - 1][1][1], len - i + 1));
			dp[i][0][1] = max(dp[i - 1][0][1], min(dp[i - 1][0][0], len - i + 1));
			dp[i][1][1] = min(dp[i - 1][0][1], i);
		}
		int temp1 = max(dp[i][0][0], min(dp[i][1][0], i));
		int temp2 = max(min(dp[i][1][0], i), dp[i][1][0]);
		dp[i][0][0] = temp1;
		dp[i][1][0] = temp2;
		temp1 = max(dp[i][0][1], min(dp[i][1][1], i));
		temp2 = max(min(dp[i][1][1], i), dp[i][1][1]);
		dp[i][0][1] = temp1;
		dp[i][1][1] = temp2;
	}
	printf("%d\n", max(max(dp[len][0][0], dp[len][0][1]), max(dp[len][1][0], dp[len][1][1])));
}

Measured memory_bytes: 1792
N=list(input())
K=int(input())
N=list(map(int,N))
#print(N)
dp=[[[0 for _ in range(4)] for _ in range(len(N))] for _ in range(2)]
for i in range(len(N)):
    num=N[i]
    mayover=0
    if i==0:
        for j in range(10):
            if j<num:
                if j==0:
                    dp[0][i][0]=dp[0][i][0]+1
                else:
                    dp[0][i][1] = dp[0][i][1] + 1
            elif j==num:
                if j==0:
                    dp[1][i][0] = dp[1][i][0] + 1
                else:
                    dp[1][i][1] = dp[1][i][1] + 1
    else:

        for j in range(2):
            if j==0:
                for l in range(4):
                    dp[j][i][l] = dp[j][i][l] + dp[j][i - 1][l]
                    if l != 0:
                        dp[j][i][l] = dp[j][i][l] + 9*dp[j][i - 1][l - 1]
            else:
                if num==0:
                    for l in range(4):
                        dp[j][i][l]=dp[j][i-1][l]
                else:
                    for l in range(4):
                        dp[0][i][l]=dp[0][i][l]+dp[j][i-1][l]
                        if l!=0:
                            dp[0][i][l]=dp[0][i][l]+(num-1)*dp[j][i-1][l-1]
                            dp[1][i][l]=dp[1][i][l]+dp[j][i-1][l-1]

    #print(dp[0][i],dp[1][i])
    #input()
print(dp[0][len(N)-1][K]+dp[1][len(N)-1][K])








Measured memory_bytes: 63164
l =input().split()

a=int(l[0])
b=int(l[1])

# 最大公約数
def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

# 最小公倍数
def lcm(a, b):
  return a*b/gcd(a, b)

print(int(lcm(a,b)))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define inf 100000000000000007
#define MOD 1000000007
#define x first
#define y second
#define ll long long
#define ii pair<ll, ll>
#define vi vector<ll>
#define vii vector<ii>
#define pb push_back
#define ubnd upper_bound
#define lbnd lower_bound
#define mp make_pair
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 2e5 + 5;
ll n, k;

ll A[N], t;

ll check(ll n){
    for(ll i=1; i<=k; i++)
        n-= n%A[i];
    return n;
}

int main()
{
 //   ios
 //  freopen("in.txt", "r", stdin);
   // freopen("out.txt", "w", stdout);
    ll i ,j , ans=0, a,  c, d,b, p=0,z;
    cin>>k;
    for(i=1; i<=k; i++)
        cin>>A[i];
    ll low= 0, high= inf, mid= high;
    ll mn= inf, mx= 0;
    while(low <= high){
        mid= (low+high)/2;
        a= check(mid);
        if( a >= 2)
            high = mid-1;
        else if(a < 2)
            low= mid+1;
        if(a==2)
            mn= min(mn, mid);
    }

    low= 0, high= inf, mid= high;

    while(low <= high){
        mid= (low+high)/2;
        a= check(mid);
        if( a > 2)
            high = mid-1;
        else if(a <= 2)
            low= mid+1;
        if(a==2)
            mx= max(mx, mid);
    }
    if(mx== 0)
        cout<<-1;
    else
         cout<<mn<<" "<<mx;
}

Measured memory_bytes: 1024
n = int(input())
a = list(map(int,input().split()))
flag = 0
cnt = 0
for i in range(n-1):
    if flag == 0:
        if a[i] > a[i+1]:
            flag = -1
        if a[i] < a[i+1]:
            flag = 1
    if flag == 1:
        if a[i] > a[i+1]:
            flag = 0
            cnt += 1
    if flag == -1:
        if a[i] < a[i+1]:
            flag = 0
            cnt += 1
print(cnt+1)

Measured memory_bytes: 14252
x1, y1, x2, y2 = map(int, input().split())

vector = complex(x2 - x1, y2 - y1)
vector *= complex(0, 1)
xy2 = complex(x2, y2)
xy3 = xy2 + vector
vector *= complex(0, 1)
xy4 = xy3 + vector

print(int(xy3.real), int(xy3.imag),int(xy4.real), int(xy4.imag))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
 
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int, int>
#define vi              vector<int>
#define si              set<int>
#define usi             unordered_set<int>
#define mii             map<int, int>
#define umii            unordered_map<int, int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int, vi, greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define endl            '\n'
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(t)            int t; cin>>t; while(t--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void jaiswal_sahil()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
}

const int N = 1e6;
int dp[N];
int n;

int minCost(int i, int *a){

    if(i >= n-1)
        return 0;

    if(dp[i] != -1)
        return dp[i];

    int q1 = inf, q2 = inf;
    if(i+1 < n)
        q1 = abs(a[i] - a[i+1]) + minCost(i+1, a);
        
    if(i+2 < n)
        q2 = abs(a[i] - a[i+2]) + minCost(i+2, a);
    
    return dp[i] = min(q1, q2);

}

int32_t main()
{
    jaiswal_sahil();

    cin>>n;
    int a[n];
    for(int i=0; i<n; i++)
        cin>>a[i];
    
    memset(dp, -1, sizeof(dp));
    int ans = minCost(0, a);
    cout<<ans<<endl;
    return 0;

}

Measured memory_bytes: 13568
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  int n, k;
  cin >> n >> k;
  if((n - 1) * (n - 2) / 2 < k) {
    cout << -1 << endl;
    return 0;
  }

  vector<pair<int ,int >> ans;
  k = (n - 1) * (n - 2) / 2 - k;
  
  for(int i = 1; i < n; i++) {
    ans.emplace_back(0, i);
  }

  int i = 1;
  int j = 2;
  while(k) {
    if(j == n) i++, j = i + 1;
    ans.emplace_back(i, j);
    k--;
    j++;
  }


  cout << ans.size() << endl;
  for(int i = 0; i < ans.size(); i++) cout << ans[i].first + 1 << " " << ans[i].second + 1 << "\n";
  return 0;
}


Measured memory_bytes: 384
def ans():
    NOT_VISITED = -99999
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    visited = [NOT_VISITED for _ in range(N + 1)]

    def dps(graph, start, visited):
        if visited[start] != NOT_VISITED:
            return False
        stuck = [start]
        visited[start] = 0
        while stuck:
            label = stuck.pop()
            for nextnode, distance in graph[label]:
                if visited[nextnode] == NOT_VISITED:
                    stuck.append(nextnode)
                    visited[nextnode] = visited[label] + distance
                elif visited[nextnode] != visited[label] + distance:
                    return True

    for _ in range(M):
        L, R, D = map(int, input().split())
        graph[L].append((R, D))
        graph[R].append((L, -D))

    for i in range(1, N + 1):
        if dps(graph, i, visited):
            return print('No')
    return print('Yes')
# main()
ans()

Measured memory_bytes: 65876
#include <iostream>                                                              
#include <string>                                                                
                                                                                 
using namespace std;                                                             
                                                                                 
int main (void) {                                                                
  string str;                                                                    
  int i;                                                                         
  int count[26] = {};                                                            
  int num = 0;                                                                   
  while (getline(cin,str)) {                                                     
    for (i=0; i<str.length(); i++) {                                             
      if (islower(str[i])) {                                                     
        num = str[i]-'a';                                                        
        count[num]++;                                                            
      }                                                                          
      else if (isupper(str[i])) {                                                
        str[i] = tolower(str[i]);                                                
        num = str[i]-'a';                                                        
        count[num]++;                                                            
      }                                                                          
    }                                                                            
  }                                                                              
    for (i=0; i<26; i++) {                                                       
      cout << char(i+'a') << " : " << count[i] << endl;                          
    }                                                                            
}                           

Measured memory_bytes: 3136
import sys
#input = sys.stdin.readline
from collections import Counter
def inpl(): return list(map(int, input().split()))

N = int(input())
B = inpl()
A = inpl()

ans = 0
for i in range(N):
    ans += min(A[i], B[i])
    A[i] -= min(A[i], B[i])
    ans += min(A[i], B[i+1])
    B[i+1] -= min(A[i], B[i+1])

print(ans)

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

int main(){
    int A ,B,C,K;
    cin>>A>>B>>C>>K;
while(K!=0){
    if(B<=A){
        B*=2;
        K--;
    }
    else{
        break;
    }
}
while(K!=0){
    if(C<=A||C<=B){
        C*=2;
        K--;
    }
    else{
        break;
    }
}
if(C>B&&C>A&&B>A){
    cout<<"Yes"<<endl;
}
else{
    cout<<"No"<<endl;
}
return 0;
}


Measured memory_bytes: 3628
#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

int main(int argc, char const *argv[]) {
    int edge[3];
    int tri[3]={0};//0:right, 1:acute, 2:obtuse
    int total=0;

    while(1){
        for(int i=0;i<3;i++)
            cin >> edge[i];
        sort(edge,edge+3);
        if(edge[2] < edge[0] + edge[1]){
            total++;
            if(pow(edge[2],2) == pow(edge[0],2) + pow(edge[1],2)){
                tri[0]++;
            }else if(pow(edge[2],2) < pow(edge[0],2) + pow(edge[1],2)){
                tri[1]++;
            }else{
                tri[2]++;
            }
        }else{
            break;
        }
    }
    printf("%d %d %d %d\n",total,tri[0],tri[1],tri[2]);
    return 0;
}



Measured memory_bytes: 3256
N,L=map(int,input().split())
a=[int(i) for i in input().split()]
j=-1
for i in range(N-1):
    if a[i]+a[i+1]>=L:
        j=i
        break
if j==-1:
    print("Impossible")
else:
    print("Possible")
    for i in range(j):
        print(i+1)
    for i in range(j+1,N-1)[::-1]:
        print(i+1)
    print(j+1)


Measured memory_bytes: 14180
n = input()
gap =len(n) -1
for i in range(2 ** gap):
  f = ""
  for j in range(gap):
    f += str(n[j])
    if ((i>>j)&1):
      f += "+"
    else:
      f += "-"
  f += n[-1]
  if eval(f) == 7 :
    print(f +"=7")
    break

Measured memory_bytes: 3060
n, m, q = map(int, input().split())
a = []
for _ in range(q):
    a.append(list(map(int, input().split())))

import itertools

List = []
for v in itertools.combinations_with_replacement(range(1, m+1), n):
    List.append(list(v))
    
answer = []
for l in List:
    ans = 0
    for j in a:
        if l[j[1]-1] - l[j[0]-1] == j[2]:
            ans += j[3]
    answer.append(ans)
    
print(max(answer))

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

int main()
{
ll n ;
cin >> n ;
vector<ll> a(n);
bool same=1;
ll mx=0;
rep(i, n){
  cin >> a[i];
  mx=max(mx,a[i]);
}
rep(i,n-1)if(a[i]!=a[i+1])same=0;
if(same){
  if(n==a[0]+1 ||n>=a[0]*2){
    cout << "Yes" << endl;
    return 0;
  }
}
else{
  ll cnt=0;
  rep(i,n){
    if(a[i]==mx-1)cnt++;
    else if(a[i]<mx-1){
      cout << "No" << endl;
      return 0;
    }
  }
  if(n-cnt>=(mx-cnt)*2 && mx-cnt>0){
    cout << "Yes" << endl;
    return 0;
  }
}
cout << "No" << endl;
return 0;
}

Measured memory_bytes: 1024
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner scan = new FastScanner();
		int n = scan.nextInt();

		int ret = 0;
		int before = scan.nextInt();
		int next;
		int tmp = 0;
		for (int i = 0; i < n - 1; i++) {
			next = scan.nextInt();

			if (before >= next) {
				tmp++;
				if (ret < tmp) {
					ret = tmp;
				}
			} else {
				tmp = 0;
			}
			before = next;

		}

		System.out.println(ret);
	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 24568
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define Sort(a) sort(a.begin(), a.end())
const int INF = 1 << 30;
const ll MOD = 1000000007;
int main(void) {
  int n;
  cin >> n;
  for (int i = 1; i < 10; i++) {
    if (n % i != 0) continue;

    int remain = n / i;
    if (remain < 10) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <stdio.h>
#define MAXN 100005
using namespace std;
typedef long long int lo;
int t;
long long int a,b,c,n,cnt;
string s;
string s2;
string th;
int mer[MAXN];
int main()
{
	cin >> s;
	cin >> s2;
	cin >> a; 
	cin >> b;
	cin >> th;
	if (th == s2)
	{
		b--;
	}
	if (th == s)
	{
		a--;
	}
	cout << a << " " << b;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N;
  cin >>N;
  ll d[N];
  rep(i,N) cin >> d[i];
  sort(d, d+N);
  if(d[N/2] == d[N/2-1]){
    cout << 0 << endl;
    return 0;
  }
  ll ans = d[N/2] - d[N/2-1];
  cout << ans << endl;

  return 0;
    

}


Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
#include <deque>
using ll = long long;
using namespace std;

char dir;
int d;

void straight(){
    for (int i = 0; i < d; i++) cout << dir;
}

void UD(int y1, int y2){
    if(y1==y2){
        d = 0;
        return;
    }
    else if(y1>y2) dir = 'D';
    else dir = 'U';
    d = abs(y1-y2);
    return;
}

void RL(int x1, int x2){
    if(x1==x2){
        d = 0;
        return;
    }
    else if(x1>x2) dir = 'L';
    else dir = 'R';
    d = abs(x1-x2);
    return;
}


int main(){
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    UD(sy, ty); straight();
    RL(sx, tx); straight();
    UD(ty, sy); straight();
    RL(tx, sx); straight();
    cout << 'L'; sx-=1; ty+=1;
    UD(sy, ty); straight();
    RL(sx, tx); straight();
    cout << "DR";
    UD(ty, sy); straight();
    RL(tx, sx); straight();
    cout << 'U';
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef vector<ll> vel;
typedef vector<str> ves;
#define REP(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define rep(i, b) REP(i, 0, b)
const ll mod = 1000000007;
const double pi = 3.14159265358979;

ll expo(ll a, ll b){
    ll ex = 1;
    rep(i, b){
        ex *= a;
    }
    return ex;
}

ll fact(ll a){
    ll fc = 1;
    REP(i, 1, a+1){
        fc *= i;
    }
    return fc;
}

int main() {
    ll a, b;
    cin >> a >> b;
    if(a>b) {
        cout << a-1 << endl;
    }
    else {
        cout << a << endl;
    }
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		sc.close();
		long gcd = gcd(a, b);
		long ans = 0;
		double root = Math.sqrt(gcd);
		for (int i = 1; i <= root; i++) {
			if (gcd % i == 0) {
				if (isPrime(i)) {
					ans++;
				}
				if (i != (gcd / i) && isPrime((gcd / i))) {
					ans++;
				}
			}
		}
		System.out.println(ans);
	}

	public static boolean isPrime(long jud) {
		double root = Math.sqrt(jud);
		for (int i = 2; i <= root; i++) {
			if (jud % i == 0) {
				return false;
			}
		}
		return true;
	}

	// 配列要素数が1だと前触れなくバグるので注意！！！REりたくなければ要素数を保証するか例外処理を入れろ！！！
	public static long gcd(final long[] param) {
		final int len = param.length;
		long g = gcd(param[0], param[1]);
		for (int i = 1; i < len - 1; i++) {
			g = gcd(g, param[i + 1]);
		}
		return g;
	}

	public static long gcd(long a, long b) {
		// a > b にする(swap)
		if (a < b) {
			a = a ^ b;
			b = a ^ b;
			a = a ^ b;
		}
		// ユークリッドの互除法
		long r = -1;
		while (r != 0) {
			r = a % b;
			a = b;
			b = r;
		}

		return a; // b には r=0 の値が入るため、a を返す
	}

	public static long lcm(long m, long n) {
		return m * n / gcd(m, n);
	}

	public static long lcm(final long[] param) {
		final int len = param.length;
		long l = lcm(param[0], param[1]);
		for (int i = 1; i < len - 1; i++) {
			l = lcm(l, param[i + 1]);
		}
		return l;
	}

	public static int[] arrayInt(Scanner sc, int n) {
		int[] array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextInt();
		}
		return array;
	}

	public static long[] arrayLong(Scanner sc, int n) {
		long[] array = new long[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextLong();
		}
		return array;
	}

	public static double[] arrayDouble(Scanner sc, int n) {
		double[] array = new double[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextDouble();
		}
		return array;
	}
}


Measured memory_bytes: 23380
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define int long long
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

const int INF = 1000000000;

int n, m;
vector<int> vec[100010];
int d[100010];
int ans[100010];

void bfs() {
	queue<int> que;
	que.push(1);
	while (!que.empty()) {
		int v = que.front(); que.pop();
		for (int i = 0; i < (int)vec[v].size(); i++) {
			if (vec[v][i] != 1 && d[vec[v][i]] == 0) {
				d[vec[v][i]] = d[v] + 1;
				ans[vec[v][i]] = v;
				que.push(vec[v][i]);
			}
		}
	}
}

signed main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	bfs();
	cout << "Yes" << endl;
	for (int i = 2; i <= n; i++)cout << ans[i] << endl;
}

Measured memory_bytes: 13776
#include<bits/stdc++.h>
#define int long long int
#define inf 100000000000
#define hell (int)(1e9+7)

using namespace std;

void solve(){
    int n;
    cin>>n;
    map <int,int> mp;
    vector <int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        mp[a[i]]++;
    }
    int ans=0;
    for(auto &x:mp){
        ans+=(x.second*(x.second-1))/2;
    }
    for(int i=0;i<n;i++){
        int x=mp[a[i]]-1;
        cout<<ans-x<<"\n";
    }

}

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


Measured memory_bytes: 11136
#abc125c

def gcd(a,b):
 while b:
  a,b=b,a%b
 return a

n=int(raw_input())
a=map(int,raw_input().split())
res=0
x=[0]*(n+1)
y=[0]*(n+1)
for i in range(n):
 x[i+1]=gcd(x[i],a[i])
 y[i+1]=gcd(y[i],a[n-i-1])
for i in range(n):
 res=max(gcd(x[i],y[n-i-1]),res)
print res


Measured memory_bytes: 12924
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))
 
using namespace std;
 
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;}
 
const ll INF=1e9+7;
ll n;
vector<ll> to[100010];

vector<ll> dist;

void dfs(ll v,ll d=0,ll p=-1){
    dist[v]=d;
    for(auto x:to[v]){
        if(x==p) continue;
        dfs(x,d+1,v);
    }
    return ;
}

vector<ll> calcdist(ll s){
    dist=vector<ll>(n);
    dfs(s);
    return dist;
}

int main(){
    ll u,v;
    cin >> n >> u >> v;
    u--; v--;
    rep(i,n-1){
        ll a,b;
        cin >> a >> b;
        a--; b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    vector<ll> distU=calcdist(u);
    vector<ll> distV=calcdist(v);
    ll mx=0;
    rep(i,n){
        if(distU[i]<distV[i]){
            mx=max(mx,distV[i]);
        }
    }
    ll ans=mx-1;
    cout << ans << endl;
    return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define lf double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert


using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a, b; cin>>a>>b;
	cout << (b-1+(a-2))/(a-1) << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define alpha_size 26

const int N = 100 + 10;
int d[N];
int a[N];
bool visited[N];

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

    int n, k;
    cin >> n >> k;
    memset(visited, false, sizeof visited);
    for (int i = 0; i < k; i++){
      cin >> d[i];
      for (int j = 0; j < d[i]; j++){
        cin >> a[j];
        visited[a[j]] = true;
      }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++){
      if (!visited[i]){
        cnt++;
      }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3656
package main

import "fmt"

func main() {
	var n int
	fmt.Scanln(&n)

	for a := 0; a <= 20; a++ {
		for b := 0; b <= (n-a*4)/7; b++ {
			if a*4+b*7 == n {
				fmt.Println("Yes")
				return
			}
		}
	}
	fmt.Println("No")
}


Measured memory_bytes: 512
#include <iostream>
    #include <vector>
    using namespace std;
    int main(int argc, char* argv[])
    {
    	int N;
    	cin>>N;
    	int i;
    	int A;
    	vector<int> aa;
    	for (i=0;i<N;i++){
    		cin>>A;
    		aa.push_back(A);
    	}
    	int aMin = 1e10;
    	for (i=-100;i<=100;i++){
    		int x=0;
    		for (int j=0;j<N;j++){
    			x += (aa[j] - i)*(aa[j] - i);
    		}
    		if (aMin>x){
    			aMin = x;
    		}
    	}
    	cout<<aMin<<endl;
    	return 0;
    }

Measured memory_bytes: 256