akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
typedef long long ll;

int main(){
    ll n,m;
    cin >> n >> m;  // n: 4 m:1
    ll ai;
    double s=0.;
    int A[n];
    for (ll i=0;i<n;i++){  // i 3
        cin >> ai;  // ai 1
        A[i] = ai;  // A: [5,4,2,1]
        s += ai;  // 12.0
    }
    ll cnt=0;
    double needed=s/(4*m);  // needed: 3.0
    for (ll i=0;i<n;i++){  // i: 3
        if (A[i] >= needed) cnt++;  // 2
    }
    if (cnt >= m) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

int main(){
    ll n,m;
    cin>>n>>m;
    ll acnum=0;
    vector<bool> ac(n,false);
    vector<ll> wanum(n,0);
    rep(i,m){
        ll p;
        string r;
        cin>>p>>r;
        p--;
        if(r=="AC"&&!ac[p]){
            ac[p]=true;
            acnum++;
        }
        if(r=="WA"&&!ac[p]){
            wanum[p]++;
        }
    }
    ll re=0;
    rep(i,n){
        if(ac[i])re+=wanum[i];
    }
    cout<<acnum<<" "<<re<<endl;
}


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

using namespace std;
#define int long long
const int p=998244353;
const int maxn=3e3+5;
int dp[maxn][maxn];
int po(int a,int b)
{
    if(b==0) return 1;
    if(b==1) return a;
    if(b%2==0)
    {
        int u=po(a,b/2);
        return (u*u)%p;
    }
    if(b%2==1)
    {
        int u=po(a,b-1);
        return (a*u)%p;
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    dp[a][b]=1;
    for(int i=a;i<=c;++i)
    {
        for(int j=b;j<=d;++j)
        {
            if(i==a)
            {
                dp[i][j]=po(a,j-b);
                continue;
            }
            if(j==b)
            {
                dp[i][j]=po(b,i-a);
                continue;
            }
            dp[i][j]=dp[i-1][j]*j+dp[i][j-1]*i-dp[i-1][j-1]*(i-1)*(j-1);
            dp[i][j]%=p;
        }
    }
    cout<<(dp[c][d]+p)%p;
    return 0;
}


Measured memory_bytes: 74080
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }
    
    int count = 0;
    for (int i = 0; i < a.length; i++) {
      if (a[i] == i + 1 && i == a.length - 1) {
        int swap = a[i];
        a[i] = a[i - 1];
        a[i - 1] = swap;
        count++;
      }
      if (a[i] == i + 1) {
        int swap = a[i];
        a[i] = a[i + 1];
        a[i + 1] = swap;
        count++;
      }
    }
    System.out.println(count);
  }
}


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

#define int long long

const int INF = 1e15;

int dp[55555];
int c[22];

int n, m;

signed main() {
  cin >> n >> m;
  for (int i = 0; i <= m; i++) {
    cin >> c[i];
  }

  fill(dp, dp+n+5, INF);
  dp[0] = 0;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j < m; j++) {
      if (i - c[j] >= 0) {
        dp[i] = min(dp[i], dp[i-c[j]] + 1);
      }
    }
  }

  cout << dp[n] << endl;

  return 0;
}


Measured memory_bytes: 3480
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

#define PI 3.14159265358979323

int main(int argc, char* argv[]) {
	char op;
	int a, b;


	while(1){
		cin >> a >> op >> b;
		if(op == '?') break;

		switch(op)
		{
			case '+': cout << a + b << endl; break;
			case '-': cout << a - b << endl; break;
			case '*': cout << a * b << endl; break;
			case '/': cout << a / b << endl; break;
		}
	}

	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
cin>>a>>b;
if((a==1 || a==2) && (b==1 || b==2))
    cout<<'3'<<endl;
else if((a==1 || a==3) && (b==1 || b==3))
cout<<'2'<<endl;
    else if((a==2 || a==3) && (b==2 || b==3))
    cout<<'1'<<endl;

return 0;}


Measured memory_bytes: 3600
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  vector<int> A(N);
  for(int i=0;i<N;++i) cin>>A[i];
  sort(A.begin(), A.end());
  cout<<A[N-1]-A[0]<<endl;
}



Measured memory_bytes: 3536
#include "bits/stdc++.h"
using namespace std;

const string number={'2','3','4','5','6','7','8','9'};
const string moji={'i','x','c','m'};

void hantei(string MCXI,int *digit){
  // for(int i=4;i>0;--i)cout << MCXI[i] <<endl;
  for(int i=MCXI.size();i>1;--i){//?°?????????????????????????????????????????????\??§?????????
    if(MCXI[i-1]==moji[0]){
      digit[0]=1;
      for(int j=0;j<number.size();++j){
        if(MCXI[i-2]==number[j]){
          digit[0]=j+2;
          --i;
          break;
        }
      }
    }else if(MCXI[i-1]==moji[1]){
      digit[1]=1;
      for(int j=0;j<number.size();++j){
        if(MCXI[i-2]==number[j]){
            digit[1]=j+2;
            --i;
            break;
          }
        }
      }else if(MCXI[i-1]==moji[2]){
        digit[2]=1;
        for(int j=0;j<number.size();++j){
          if(MCXI[i-2]==number[j]){
            digit[2]=j+2;
            --i;
            break;
          }
        }
      }else if(MCXI[i-1]==moji[3]){
      digit[3]=1;
      for(int j=0;j<number.size();++j){
        if(MCXI[i-2]==number[j]){
          digit[3]=j+2;
          --i;
          break;
        }
      }
    }
  }
  if(MCXI[0]==moji[0])digit[0]=1;
  else if(MCXI[0]==moji[1])digit[1]=1;
  else if(MCXI[0]==moji[2])digit[2]=1;
  else if(MCXI[0]==moji[3])digit[3]=1;
}

string answer(int *digit1,int *digit2){
  string ans;
  int ans_digit[4]={(digit1[0]+digit2[0])%10,
                (digit1[1]+digit2[1]+(digit1[0]+digit2[0])/10)%10,
                (digit1[2]+digit2[2]+(digit1[1]+digit2[1]+(digit1[0]+digit2[0])/10)/10)%10,
                digit1[3]+digit2[3]+(digit1[2]+digit2[2]+(digit1[1]+digit2[1]+(digit1[0]+digit2[0])/10)/10)/10};
  // for(int i=4;i>0;--i)cout << ans_digit[i-1] <<endl;
    for(int i=4;i>0;--i){
      if(ans_digit[i-1]==1)ans.push_back(moji[i-1]);
      else if(ans_digit[i-1]>1){
        ans.push_back(number[ans_digit[i-1]-2]);
        ans.push_back(moji[i-1]);
        }
      }
    return ans;
}

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

  int n;
  string MCXI1,MCXI2;

  cin >> n;
  while(n){
    int digit1[4]={0};
    int digit2[4]={0};
    cin >> MCXI1 >>MCXI2;
    hantei(MCXI1,digit1);
    hantei(MCXI2,digit2);
    // for(int i=4;i>0;--i)cout << digit1[i-1] << " " << digit2[i-1] <<endl;
    cout << answer(digit1,digit2) << endl;
    n--;
  }
  return 0;
}

Measured memory_bytes: 3036
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int H,A;
    cin >> H >> A;
    int ans;
    if(H%A==0){
        ans=H/A;
    }else{
        ans=H/A+1;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int N,ans=0,res=0;
    cin>>N;
    int A[N];
    for ( int i = 0; i<N; i++){
        cin>>A[i];
    }
    for ( int i=0;i<N;i++){
        if (A[i]%2==0){
            ans++;
            if (A[i]%3==0 || A[i]%5==0){
                res++;
            }
        }
        }
    if (ans==res){
        cout<<"APPROVED"<<endl;
    }
    else {
        cout<<"DENIED"<<endl;
    }
}

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

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> v(n);
  for (int i = 0; i < n; i++) cin >> v[i];
  int res = 0;
  /*操作を全探索*/
  for (int l = 0; l <= min(n, k); l++) {
    for (int r = 0; l + r <= min(n, k); r++) {
      vector<int> h;
      for (int i = 0; i < l; i++) h.emplace_back(v[i]);
      for (int i = 0; i < r; i++) h.emplace_back(v[n-i-1]);
      sort(h.begin(), h.end());
      int tmp = accumulate(h.begin(), h.end(), 0);
      for (int i = 0; i < min(k - l - r, (int)h.size()); i++) {
        if (h[i] < 0) tmp -= h[i];
      }
      res = max(res, tmp);
    }
  }
  cout << res << endl;
  return 0;
}

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

typedef int64_t Int;
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << '\n'; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) std::cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << '\n';
}

void solve() {
    Int x, y;
    cin >> x >> y;
    Int res = INF;
    if (x <= y) {
        res = min(res, y - x);
    }
    if (-x <= y) {
        res = min(res, 1 + y - (-x));
    }
    if (x <= -y) {
        res = min(res, 1 + (-y) - x);
    }
    if (-x <= -y) {
        res = min(res, 2 + (-y) - (-x));
    }
    print(res);
}

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


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

int main(){
    int N, K, X, Y;
    cin >> N;
    cin >> K;
    cin >> X;
    cin >> Y;
    if(N <= K){
        cout << X * N << endl;
    }else{
        cout << X * K + Y * (N - K) << endl;
    }
    return 0;
}

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

int main()
{
   int a,b;
   cin >> a >> b;
  int ans = a * b;
  if(ans % 2 == 0){
      cout << "Even" << endl;
  }else {
      cout <<"Odd" << endl;
  }
}


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

#define ALL(a) begin(a),end(a)
#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v) {
  for (T& x: v) s >> x;
  return s;
}
inline void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}
inline void YES(bool f){cout<<(f?"YES":"NO")<<endl;}

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

    string s; cin >> s;

    int A_pos = s.find('A');
    int Z_pos = s.rfind('Z');
    string AxxxZ = s.substr(A_pos, Z_pos - A_pos + 1);
    cout << AxxxZ.length() << endl;
}


Measured memory_bytes: 788
MOD = 10**9 + 7
def solve(n, a, p=60):
    res, m = 0, 1
    for i in range(p):
        y = sum(x & m for x in a) // m
        res += y * (n-y) * m
        m *= 2
    return res % MOD

n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))

Measured memory_bytes: 42212
#include <bits/stdc++.h>
#if ONLINE_JUDGE
    #define DEBUG false
#else
    #define DEBUG true
#endif
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
#define REP(i, k, n) for (int i = (int)(k); i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define rep1(i, n) REP(i, 1, n)
#define rREP(i, k, n) for (int i = (int)(n)-1; i >= k; i--)
#define rrep(i, n) rREP(i, 0, n)
#define forlist(i, vec) for(auto &&i : vec)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define REV(x) reverse(all(x))
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define LOWitr(x, n) lower_bound(all(x), n)
#define UPRitr(x, n) upper_bound(all(x), n)
#define cii(x) int x;cin >> x
#define cill(x) LL x;cin >> x
#define cis(x) string x;cin >> x
#define co(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define truecheck assert
#define dump(x) cerr << #x << ": " << (x) << endl
using namespace std;
typedef long long LL;
typedef long long int64;
typedef std::vector<int> VI;
typedef std::vector<VI> VVI;
typedef std::vector<LL> VL;
typedef std::vector<VL> VVL;
typedef std::vector<std::string> VS;
typedef std::pair<int, int> PII;
typedef std::pair<LL, LL> PLL;
typedef std::queue<int> QI;
typedef std::priority_queue<int> PQI;
template<class T,class U>inline bool chmax(T &a, const U &b){if (a<b){a=b;return true;}return false;}
template<class T,class U>inline bool chmin(T &a, const U &b){if (b<a){a=b;return true;}return false;}
template<class T,class U>inline void vcinpb(T &v, U n){rep(i, n){typename T::value_type a;cin >> a;v.pb(a);}}
template<class T>inline void dumpv(T &v){
    if(!DEBUG)return;cout<<"{";rep(i,v.size()){cout<<v[i]<<(i!=v.size()-1)?",":"}";}cout<<endl;
}

const int INF = 1e9, MOD = 1e9 + 7;
const LL LLINF = 1e16;
// M_PI 3.1415...

int main() {
    fastcin();
    cout << fixed << setprecision(10);
    cill(x);
    for (LL i = -200; i < 200; i++){
        for (LL j = -200; j < 200; j++){
            if(i*i*i*i*i-j*j*j*j*j==x){
                cout << i << " " << j << endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
using namespace std;
using ll=long long;
const ll MOD=100000007;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=b-1;i>=a;i--)
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline constexpr int intpow(ll a,ll b){
    if(b==0) return 1;
    ll ans=intpow(a,b/2);
    return ans*ans%MOD*(b&1?a:1)%MOD;
}
inline constexpr int modf(ll n){
    ll ans=1;
    rep(i,0,n) {ans=ans*(n-i)%MOD;}
    return ans;
}
inline long double median(vector<ll> v){
    ll size=v.size();
    sort(v.begin(),v.end());
    if (size % 2 == 1) return v[(size - 1) / 2];
    else return (v[(size / 2) - 1] + v[size / 2]) / 2;
}


int main(){
    ll n;
    cin>>n;
    string a,b;
    cin>>a>>b;
    ll l=a.size();
    rep(i,0,l){
        if(a[i]==b[0]){
            bool f=0;
            rep(j,1,l-i){
                if(a[i+j]!=b[j]){
                    f=1;
                    break;
                }
            }
            if(!f) {
                cout<<l+i;
                return 0;
            }
        }
    }
    cout<<2*l;
}






Measured memory_bytes: 256
char buf[1<<20];
sz;
main()
{
	read(0,buf,1<<20);
	for(;buf[sz++]>='0';);
	int A=0;
	for(;;)
	{
		char k=buf[sz++];
		if(k<'0')break;
		A=A*10+k-'0';
	}
	int ans=1;
	char s=0,t=0;
	for(;buf[sz]>='0';)
	{
		int B=0;
		for(;;)
		{
			char k=buf[sz++];
			if(k<'0')break;
			B=B*10+k-'0';
		}
		if(A>B)s=1;
		else if(A<B)t=1;
		if(s&&t)s=t=0,++ans;
		A=B;
	}
	printf("%d\n",ans);
}


Measured memory_bytes: 1152
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
#include<math.h>
#include<bitset>
#include<random>
 
using namespace std;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
 
#define shosu setprecision(17)
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<char,P> Q;
//ll longinf=1ll<<60;
int inf=1<<29;
ll longinf=(1ll<<60);

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

vector<ll> ans;
int n;

void dfs(ll k){
    if(k>n) return;
    else{
    ans.push_back(k);
    dfs(10*k+3);
    dfs(10*k+5);
    dfs(10*k+7);
    }
}

bool is753(ll k){
    int ret=0;
    while(k>0){
        int aa=k%10;
        if(aa==3) ret|=1;
        if(aa==5) ret|=2;
        if(aa==7) ret|=4;
        k/=10;
    }
    return ret==7;
}

int main(){
    cin>>n;
    dfs(0);
    int a=ans.size();
    int cnt=0;
    rep0(i,a){
        if(is753(ans[i])){
            cnt++;
           // cout<<ans[i]<<endl;
        }
    }
    cout<<cnt<<endl;
    return 0;
}


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

int main(){
	int n, ans;
	cin >> n;
	vector<int> au(n), ad(n);
	rep(i, n){
		cin >> au.at(i);
	}
	rep(i, n){
		cin >> ad.at(i);
	}
	
	ans = 0;
	rep(i, n){
		int temp = 0;
		rep(j, n){
			if(j < i){
				temp += au.at(j);
			}else if(j == i){
				temp += au.at(j);
				temp += ad.at(j);
			}else{
				temp += ad.at(j);
			}
		}
		ans = max(temp, ans);
	}
	
	
	cout << ans << endl;
	
	return 0;
}

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

const int MOD = 1e+9+7;

int main(){
    int n, k;
    cin >> n >> k;
    ll ans = 0;
    for(ll i = k; i <= n+1; i++){
        ans = (ans + i*(n-i+1) + 1) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3584
use std::io;
use std::cmp;


fn main() {
    let s = read_one::<String>()
        .chars()
        .collect::<Vec<char>>();

    let red = s.iter().filter(|&c| *c == '0').count();
    let blue = s.iter().filter(|&c| *c == '1').count();

    println!("{}", cmp::min(red, blue) * 2);
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define MOD 1000000007
#define MOD2 1000000009
#define endl "\n"
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vll std::vector<int>

int main()
{   
    IOS;
        #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
        #endif


   ll a, b, c, k;
   cin >> a >> b >> c >> k;

   if(k <= a) {
    cout << k;
    return 0;
   }

   ll tot = 0;
   if(k > a && k <= a + b) {             // 1 4 2 6   
    cout << a;
    return 0;
   }
   tot += a;
   k = k - a;
   k = k - b;

   if(k > 0)
   tot += (k * -1);

   cout << tot;

   


        
        
    


return 0;
}

Measured memory_bytes: 3640
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
static const int MAX = 101;
static const int INFTY = (1 << 30);
int V;
vector< pair<int, int> > G[MAX], G2[MAX];

void dijkstra(int r, int t, int type) {
    std::priority_queue<std::pair<int, int> > pq;
    bool visited[V];
    int d[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
        d[i] = INFTY;
    }
    d[r] = 0;
    pq.push({0, r}); //dist from target * -1, current node
    visited[r] = true;
    if (type == 0) {
        while ( !pq.empty() ) {
            pair<int, int> f = pq.top(); pq.pop();
            int current = f.second;
            visited[current] = true;

            if (d[current] < f.first * (-1)) continue;

            for (unsigned long i = 0; i < G[current].size(); i++) {
                int target = G[current][i].first;
                if (visited[target]) continue;
                if (d[target] > d[current] + G[current][i].second) {
                    d[target] = d[current] + G[current][i].second;
                    pq.push({d[target] * (-1), target});
                }
            }
        }
    }

    else if (type == 1) {
        while ( !pq.empty() ) {
            pair<int, int> f = pq.top(); pq.pop();
            int current = f.second;
            visited[current] = true;

            if (d[current] < f.first * (-1)) continue;

            for (unsigned long i = 0; i < G2[current].size(); i++) {
                int target = G2[current][i].first;
                if (visited[target]) continue;
                if (d[target] > d[current] + G2[current][i].second) {
                    d[target] = d[current] + G2[current][i].second;
                    pq.push({d[target] * (-1), target});
                }
            }
        }
    }

    printf("%d\n", d[t]);

}

int main()
{
    int E, source, target, dist, cost, type, m;
    for (; ;) {
        std::scanf("%d %d", &E, &V);
        if (E == 0 && V == 0) break;
        for (int i = 0; i < E; i++) {
            std::scanf("%d %d %d %d", &source, &target, &dist, &cost);
            source--; target--;
            G[source].push_back({target, dist});
            G[target].push_back({source, dist});
            G2[target].push_back({source, cost});
            G2[source].push_back({target, cost});
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &source, &target, &type);
            source--; target--;
            dijkstra(source, target, type);
        }
        for (int i = 0; i < V; i++) { G[i].clear(); G2[i].clear(); }
    }
    return 0;
}



Measured memory_bytes: 2876
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

class Node
{
public:
  int location;
  int p,l,r;
  Node(){}
};

class Point
{
public:
  int id,x,y;
  Point(){}
  Point(int id, int x,int y): id(id),x(x),y(y){}
  bool operator < ( const Point &p ) const
  {
    return id < p.id;
  }

  void print()
  {
    printf("%d\n", id);
  }
};
static const int MAX = 1000000;
static const int NIL = -1;

int N;
Point P[MAX];
Node T[MAX];
int np;

bool lessX(const Point &p1,const Point &p2){return p1.x < p2.x;}
bool lessY(const Point &p1,const Point &p2){return p1.y < p2.y;}

int makeKDTree(int l,int r,int depth)
{
  if( !(l<r)) return NIL;
  int mid=(l+r)/2;
  int t= np++;
  if(depth % 2 ==0)
    {
      sort(P+l,P+r,lessX);
    }
  else
    {
      sort(P+l,P+r,lessY);
    }
  T[t].location = mid;
  T[t].l = makeKDTree(l,mid,depth+1);
  T[t].r = makeKDTree(mid+1,r,depth+1);
  return t;
}

void find(int v,int sx, int tx, int sy,int ty, int depth, vector<Point> &ans)
{
  int x=P[T[v].location].x;
  int y=P[T[v].location].y;
  if( sx <= x && x<= tx && sy <= y && y <= ty)
    {
      ans.push_back(P[T[v].location]);
    }
  if(depth % 2 ==0)
    {
      if(T[v].l != NIL)
	{
	  if(sx<=x) find(T[v].l,sx,tx,sy,ty,depth+1,ans);
	}
      if(T[v].r != NIL)
	{
	  if(x<=tx) find(T[v].r,sx,tx,sy,ty,depth+1,ans);
	}
    }
  else
    {
      if(T[v].l != NIL)
	{
	  if(sy<=y) find(T[v].l,sx,tx,sy,ty,depth+1,ans);
	}
      if(T[v].r != NIL)
	{
	  if(y<=ty) find(T[v].r,sx,tx,sy,ty,depth+1,ans);
	}
    }
}
      
int main()
{
  int x,y;
  scanf("%d",&N);
  for(int i=0;i<N;i++)
    {
      scanf("%d %d",&x,&y);
      P[i]=Point(i,x,y);
      T[i].l=T[i].r = T[i].p=NIL;
    }
  np=0;
  
  int root=makeKDTree(0,N,0);
  int q;
  scanf("%d",&q);
  int sx,tx,sy,ty;
  vector<Point> ans;
  for(int i=0;i<q;i++)
    {
      scanf("%d %d %d %d",&sx,&tx,&sy,&ty);
      ans.clear();
      find(root,sx,tx,sy,ty,0,ans);
      sort(ans.begin(),ans.end());
      for(int j=0;j< ans.size();j++)
	{
	  ans[j].print();
	}
      printf("\n");
    }
  return 0;
}

Measured memory_bytes: 15960
#include <stdio.h>
 
int main(void)
{
	char s[300000];
	int a,z,i=0;
	scanf("%s",s);
	for(i = 0;s[i] != 'A';i++){}
	a = i + 1;
	for(i = 200001;s[i] != 'Z';i--){}
	z = i + 1;
	printf("%d\n",z-a+1);
	return 0;
}

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << "\n";
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define endl "\n"
// gcj print用
#define Case(x) printf("Case #%d: ", x);

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<int>>> vvvl;
typedef vector<PI> vpi;
typedef vector<vector<PI>> vvpi;
typedef vector<vector<vector<PI>>> vvvpi;
typedef vector<PLL> vpl;
typedef vector<vector<PLL>> vvpl;
typedef vector<vector<vector<PLL>>> vvvpl;

int POWINT(int x, int n) {
  int ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

ll POWLL(ll x, int n) {
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

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

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vi A(N);
  rep(i, 0, N) {
    cin >> A[i];
  }
  sort(All(A));

  if (N == 1) {
    cout << 0 << endl;
  } else {
    cout << A[N-1] - A[0] << endl;
  }

  return 0;
};


Measured memory_bytes: 256
function main(input) {
    const args = input.split("\n");
    const N = parseInt(args[0],10);
    const nums = args.slice(1,N+1);
    const isValid = nums.every(n=>{
        var ns = n.split(" ");
        var t = parseInt(ns[0]),
            x = parseInt(ns[1]),
            y = parseInt(ns[2])
        var sum = x + y;
        return t >= sum && t % 2 == sum % 2
    })
    if(isValid){
        console.log("Yes");
    }else{
        console.log("No");
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

public class Main {

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

		int tcase = 0;
		while(true){
			int price = Integer.parseInt(br.readLine());
			if(price == 0){
				break;
			}
			
			if(tcase != 0){
				System.out.println();
			}
			String[] tmpArray = br.readLine().split(" ");

			int c10 = Integer.parseInt(tmpArray[0]);
			int c50 = Integer.parseInt(tmpArray[1]);
			int c100 = Integer.parseInt(tmpArray[2]);
			int c500 = Integer.parseInt(tmpArray[3]);

			//?´???´?????????
			int minimumCoins = Integer.MAX_VALUE;
			int res10 = 0, res50 = 0, res100 = 0, res500 = 0;
			for(int i = 0; i <= c10; i++){
				for(int j = 0; j <= c50; j++){
					for(int k = 0; k <= c100 ; k++ ){
						for(int l = 0; l <= c500; l++){
							if(i*10 + j*50 + k*100 + l*500 >= price){
								int numOfCoins = i + j + k + l;
								Change change = new Change(i*10 + j*50 + k*100 + l*500 - price);
//								System.out.println(i*10 + j*50 + k*100 + l*500 - price);
								if(change.isAvailable(i, j, k, l)){
//									System.out.println("Available");
									minimumCoins = Math.min(minimumCoins, (c10+c50+c100+c500) - numOfCoins + change.numOfCoins());
//									System.out.println("coins "+ ((c10+c50+c100+c500) - numOfCoins + change.numOfCoins()));
									res10 = i; res50 = j; res100 = k; res500 = l;
								}
 							}
						}
					}
				}
			}

			if(res10 != 0)System.out.println("10 "+res10);
			if(res50 != 0)System.out.println("50 "+res50);
			if(res100 != 0)System.out.println("100 "+res100);
			if(res500 != 0)System.out.println("500 "+res500);
			
			tcase++;
		}
	}

}

class Change {
	int c10, c50, c100, c500;

	public Change(int p){
		c500 = p/500;
		p %= 500;
		c100 = p/100;
		p %= 100;
		c50 = p/50;
		p %= 50;
		c10 = p/10;
	}

	int numOfCoins(){
//		System.out.println("change coins "+ (c10 + c50 + c100 + c500));
		return c10 + c50 + c100 + c500;
	}

	boolean isAvailable(int c10, int c50, int c100, int c500){
//		if((this.c10 == 0 || this.c10 != c10) && (this.c50 == 0 || this.c50 != c50) && 
//				(this.c100 == 0 || this.c100 != c100) && (this.c500 == 0 || this.c500 != c500)){
		if(this.c10*c10 == 0 && this.c50*c50 == 0 && this.c100*c100 == 0 && this.c500*c500 == 0){
			return true;
		}
		else {
			return false;
		}
	}
}

Measured memory_bytes: 60480
#include <stdio.h>
#include <string.h>

#define min(X, Y) ((X)<(Y)?(X):(Y))
#define max(X, Y) ((X)>(Y)?(X):(Y))
#define f(X, Y) (((X)-(Y))*((X)-(Y)))
int dp[20001][256], C[16];

int main(void)
{
    int n, m;
    while (scanf("%d%d", &n, &m), n) {
        int i, *prev, *curr, res;
        for(i=0;i<m;++i) scanf("%d", C+i);
        memset(dp, -1, sizeof(dp));
        dp[0][128]=0;
        for(i=0;i<n;++i) {
            int x, j, k;
            scanf("%d", &x);
            prev=dp[i], curr=dp[i+1];
            for(j=0;j<256;++j) if (prev[j]>=0) {
                for(k=0;k<m;++k) {
                    int t=min(255, max(0, j+C[k]));
                    int y=prev[j]+f(x, t);
                    curr[t]=curr[t]<0 ? y : min(curr[t], y);
                }
            }
        }
        res=1<<30;
        for(i=0;i<256;++i) if (curr[i]>=0) res=min(res, curr[i]);
        printf("%d\n", res);
    }
    return 0;
}

Measured memory_bytes: 20608
# itne me hi thakk gaye?
from collections import defaultdict
n = int(input())
mp = defaultdict(int)
arr = list(map(int, input().split()))
cur_sum = 0
for i in arr:
    cur_sum += i
    mp[i] += 1
for i in range(int(input())):
    a, b = map(int, input().split())
    fra = mp[a]
    cur_sum -= a*fra
    mp[a] -= fra
    mp[b] += fra
    cur_sum += b*fra
    print(cur_sum)

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

int main(){
    int n,y;
    cin >> n >> y;
    y /= 1000;
    int a,b,c;
    c = y%5;
    int z = y/5;
    b = z%2;
    a = z/2;
    for(int i=0; i<=a; i++){
        for(int j=0; j<=(b+(a-i)*2); j++){
            if(10*i+5*j+n-i-j == y){
                cout << i << ' ' << j << ' ' << n-i-j << endl;
                return 0;
            }
        }
    }
    cout << -1 << ' ' << -1 << ' ' << -1 << endl;

    return 0;
}


Measured memory_bytes: 256
/*The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

//PRABHJOT SINGH A.K.A. PRABHI
//~~~~~conquizztador~~~~~


#include<bits/stdc++.h>
using namespace std;
using lli = long long int;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
const int MOD = 1000000007;
const int MOD1 = 998244353;
const int maxn = 100010;
const int lim = (int)1e9;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n = 0, res = 0; lli c = 0ll, k = 0ll;
	cin >> n >> c >> k;
	vector<lli> t(n);
	for (auto &i : t)
		cin >> i;
	sort(t.begin(), t.end());
	for (int i = 0; i < n;)
	{
		++res; int j = i + 1, ct = 1;
		while (ct < c && j < n && t[j] <= t[i] + k)
		{
			++j; ++ct;
		}
		i = j;
	}
	cout << res << endl;
}

Measured memory_bytes: 3936
from collections import deque


S = deque(input())
Q = int(input())
is_reversed = False

for _ in range(Q):
    Query = input().split()
    if Query[0] == "1":
        is_reversed = not is_reversed
    else:
        F, C = int(Query[1]), Query[2]
        if is_reversed:
            F = 3 - F
        if F == 1:
                S.appendleft(C)
        else:
                S.append(C)

if is_reversed:
    S.reverse()
print("".join(S))


Measured memory_bytes: 103156
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
#======================================================#
def main():
    n = II()
    s = IS()
    cnt_b = 0
    cnt_w = s.count('.')
    cnt = cnt_w
    for si in s:
        if si == '#':
            cnt_b += 1
        else:
            cnt_w -= 1
        cnt = min(cnt, cnt_b+cnt_w)
    print(cnt)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3500
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<iostream>
using namespace std;
long long int lcm(long long int a,long long int b){
  long long int n;
  n=a*b/__gcd(a,b);
  return n;
}
using ll =long long int;
#define ci(a) cin>>a
#define co(a) cout<<a<<endl
#define gcd(a,b) __gcd(a,b)
#define vec vector<ll>
#define For(i,a,b) for(ll i=a;i<b;i++)
#define rFor(i,a,b) for(ll i=a;i>b;i--)
#define wFor(i,a,b) for(ll i=a;i<b;i+=2)
#define wrFor(i,a,b) for(ll i=a;i>b;i-=2)
#define sort(a,b) sort(a.begin(),b.end())
#define reverse(a,b) reverse(a.begin(),b.end())
//gcd 最大公約数
//lcm 最小公倍数
//double 少数（変数）
//string 文字列（変数）
//sqrt 平方根
//ceil 天井関数
//floor 床関数
//abs 絶対値
//pow 累乗
//cbrt  立方根
//hypot 平方和の平方根
//(string-'0') 文字列を数字に変換
//vector<vector<int>> data(a,vector<int>(b)) a×b行列
//for(int i=0;i<a;i++)
//for(int j=0;j<b;j++)
//cin>>data.at(i).at(j)  a×b行列の入力
//floor(log10(a)+1) aの10進法での桁数
//ceil(log10(a)) aの10進法での桁数

int main() {
  double a;
  ci(a);
  double b=0;
  For(i,0,a)
    if(i%2==0)
      b++;
  co(b/a);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define mt make_tuple
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector <long long int>
#define pii pair <int,int>
#define pll pair <long long int, long long int>
#define vpii vector< pair<int,int> >
#define vpll vector < pair <long long int,long long int> >
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int inf = 1e9 + 5;
const ll inf64 = 1e18 + 5;

bool chk(int arr[], int n, int mid, int k)
{
	ll res = 0;
	for(int i = 0; i < n; i++) 
	res += (arr[i] - 1) / mid;
	return (res <= k);
}
int main()
{
	boost;
	int n, k, i;
	cin >> n >> k;
	int arr[n];
	fo(i, 0, n)
	cin >> arr[i];
	
	int f = 1, l = inf, mid, ans = inf;
	while(f <= l) {
		mid = (f + l) / 2;
		if(chk(arr, n, mid, k)) {
			ans = min(ans, mid);
			l = mid - 1;
		}
		else
		f = mid + 1;
	}
	cout << ans;
}


Measured memory_bytes: 4336
using System;

namespace TaskA
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var t = Console.ReadLine();
            if (t[0..^1] == s)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 25896
S = input()
ans = "NO"
if S[:7] == "keyence" or S[-7:] == "keyence":
  ans = "YES"
else:
  w = "keyence"
  for i in range(len(S)):
    if w[i] == S[i]: continue
    break
  if w[i:] == S[-len(w[i:]):]: ans = "YES"
print(ans)

Measured memory_bytes: 3060
/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll k;
ll dp[5][2][100000];
vector<ll>v;
ll digit_dp(vector<ll>v,ll cnt,ll tight,ll pos){
	///cout<<cnt<<" "<<tight<<" "<<pos<<endl;
    ll i;
    ll res=0;
    if(pos>=v.size()&&cnt==k)
    return 1;
    else if(pos>=v.size()&&cnt!=k)
    return 0;
    else if(cnt>k)
    return 0;
    if(dp[cnt][tight][pos]!=-1)
    return dp[cnt][tight][pos];
    ll chuto;
    if(tight==1||pos==0)
    chuto=v[pos];
    else
    chuto=9;
    ///cout<<chuto<<endl;
    if(pos==0){
    	for(i=0;i<=chuto;i++){
    		if(i==chuto){
    			if(i!=0)
                res+=(digit_dp(v,cnt+1,1,pos+1));
                else
                res+=(digit_dp(v,cnt,1,pos+1));
			}
			else{
				 if(i!=0)
                 res+=(digit_dp(v,cnt+1,0,pos+1));
                 else
                 res+=(digit_dp(v,cnt,0,pos+1));
			}
		}
		return dp[cnt][tight][pos]=res;
	}
	else{
      for(i=0;i<=chuto;i++){
          if(tight==1&&i==chuto){
              if(i!=0)
              res+=(digit_dp(v,cnt+1,1,pos+1));
              else
              res+=(digit_dp(v,cnt,1,pos+1));
         }
          else{
              if(i!=0)
               res+=(digit_dp(v,cnt+1,0,pos+1));
              else
               res+=(digit_dp(v,cnt,0,pos+1));
          }
     }
     return dp[cnt][tight][pos]=res;
   }
}
int main()
{
    ios_base::sync_with_stdio(false);
    string s;
    ll n,i,j,l;
    for(i=0;i<=4;i++){
        for(j=0;j<=1;j++){
            for(l=0;l<=1000;l++)
            dp[i][j][l]=-1;
        }
    }
    cin>>s>>k;
    ll sz=s.size();
    for(i=0;i<sz;i++)
    v.push_back(s[i]-'0');
    cout<<digit_dp(v,0,0,0);
    return 0;
}


Measured memory_bytes: 4480
#include <iostream>

using namespace std;
int main() {
    int H,W,K;
    cin >> H >> W >> K;
    char S[10][1000];
    for (int i=0; i<H; i++)
        for (int j=0; j<W; j++) cin >> S[i][j];

    int answer = 10000;
    
    int Hpow = 1 << (H-1);
    for (int i=0; i<Hpow; i++) {
        int table[10][1000];
        for (int x=0; x<10; x++)
            for (int y=0; y<1000; y++) table[x][y] = 0;
        
        int tmp = i;
        int group = 0;
        //cerr << "#" << endl;
        for (int ite=0; ite<H; ite++) {
            for (int j=0; j<W; j++) {
                if (S[ite][j] == '1') table[group][j]++;
            }
            if (tmp % 2) group++;
            //cerr << tmp % 2;
            tmp /= 2;
        }
        //cerr << "G:" << group << endl;
        //for (int x=0; x<H; x++) {for (int y=0; y<W; y++) cerr << table[x][y]; cerr << endl;}

        {
        bool fail = false;
        for (int j=0; j<W; j++) {
            for (int h=0; h<10; h++) {
                if (table[h][j] > K) {
                    fail = true;
                }
            }
        }
        if (fail) continue;
        }
        
        int all[10];
        int answer_i = 0;
        for (int h=0; h<10; h++) {
            all[h] = table[h][0];
        }
        for (int j=1; j<W; j++) {
            bool fail = false;
            for (int h=0; h<10; h++) {
                all[h] += table[h][j];
                if (all[h] > K) fail = true;
            }
            if (fail) {
                answer_i++;
                for (int h=0; h<10; h++) {
                    all[h] = table[h][j];
                }
            }
        }
        //cerr << answer_i << endl;
        answer = min(answer, answer_i + group);
    }
    cout << answer << endl;
    return 0;
}



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

// 型名の省略
typedef unsigned int uint;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> P;
typedef pair<lint, lint> Plint;
 
const int MOD = 1e9+7;
const int INF = 1<<18;
const lint INFLINT = 1LL<<60;
const double PI=acos(-1.0);
 
// cinとcoutの高速化
#define endl "\n"
struct cinacc{cinacc(){cin.tie(0);ios::sync_with_stdio(false);}}cinaccc;
struct coutacc{coutacc(){cout.setf(ios::fixed);cout.precision(12);}}coutaccc;
 
// 繰り返し
#define rep(i,n) for(lint i=0;i<(lint)(n);i++)
#define reps(i,n) for(lint i=0;i<=(lint)(n);i++)
#define rrep(i,n) for(lint i=(lint)(n)-1;i>0;i--)
#define rreps(i,n) for(lint i=(lint)(n)-1;i>=0;i--)

#define pb push_back

#define ALL(s) (s.begin(), s.end())
#define SZ(s) (s.size())

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

// Union-Find-Tree
class UnionFind {
	vector<int> par;
	UnionFind(int n):par(n){rep(i,n)par[i]=i;}
	int root(int x){if(par[x]==x)return x;return par[x]=root(par[x]);}
	void unite(int x,int y){int rx=root(x);int ry=root(y);if(rx==ry)return;par[rx]=ry;}
	bool same(int x,int y){return root(x)==root(y);}
};

// Final Weapon!
// #define int lint

#define MAX_V 100000

struct edge { int to; int cost; };
int V, d[MAX_V];
vector<edge> G[MAX_V];
vector<int> ans(MAX_V);

void dijkstra(int n, int s) {
    rep(i, n) d[i] = INF;
    d[s] = 0;
    
    queue<P> que;
    que.push(P(s, 0));
    
    while(!que.empty()) {
        P p = que.front();
        que.pop();
        int nv = p.first;
        if(d[nv] < p.second) continue;
        for(auto e : G[nv]) {
            if(d[e.to] > d[nv] + e.cost) {
                ans[e.to] = nv;
                d[e.to] = d[nv] + e.cost;
                que.push(P(e.to, d[e.to]));
            }
        }
    }
}

int main() {
    int n, m, a, b;
    cin >> n >> m;
    rep(i, m) {
        cin >> a >> b;
        a--; b--;
        G[a].pb(edge{b, 1});
        G[b].pb(edge{a, 1});
    }
    
    dijkstra(n, 0);
    for(int i = 1; i < n; i++) {
        if(d[i] == INF) {
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    for(int i = 1; i < n; i++) cout << ans[i] + 1 << endl;
    
    return 0;
}


Measured memory_bytes: 12964
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <climits>
#include <map>
using namespace std;

#define max_N 100005
#define mod 1000000007

int n, a[max_N], s, pre, post;
bool vis[max_N];
int inv[max_N], f[max_N], invf[max_N];

inline int C(int n, int m) {
    if ( n < m ) return 0;
    return 1ll * f[n] * invf[m] % mod * invf[n - m] % mod;
}

int main(){
    scanf("%d", &n);
    for ( int i = 1; i <= n + 1; ++i ) cin >> a[i];
    for ( int i = 1; i <= n + 1; ++i ) {
        if ( vis[a[i]] ) s = a[i];
        vis[a[i]] = 1;
    }
    
    for ( int i = 1; i <= n + 1 && a[i] != s; ++i ) ++pre;
    for ( int i = n + 1; i > 0 && a[i] != s; --i ) ++post;
    
    f[0] = invf[0] = 1;
    inv[1] = f[1] = invf[1] = 1;
    
    for ( int i = 2; i <= post + pre || i <= n + 1; ++i ) {
        inv[i] = mod - 1ll * (mod / i) * inv[mod % i] % mod;
        f[i] = 1ll * f[i - 1] * i % mod;
        invf[i] = 1ll * invf[i - 1] * inv[i] % mod;
    }
    
    for ( int i = 1; i <= n + 1; ++i ){
        int ans = (C(n + 1, i) - C(pre + post, i - 1) + mod) % mod;
        printf("%d\n",ans);
    }
    
    return 0;
}

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

int main(){
    string S;
    cin >> S;
    
    string ans;
    for (int i=0; i < S.length(); i++){
        if (S[i] == ','){
            ans += " ";
        }
        else ans += S[i];

    }
    cout << ans;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<string>
typedef long long LL;
using namespace std; 
int main()
{
	int N,Q;
	scanf("%d %d",&N,&Q);
	for(int i=0;i<Q;i++)
	{
		int len=0;
		int v,w;
		scanf("%d %d",&v,&w);
		if(N!=1)
		{
			v--;
			w--;
			int flag=0;
			while(v>0)
			{
				while(w>v)
				{
					int ga=w/N;
					if(w%N==0)
						ga--;
					w=ga;
				}
				if(w==v)
				{
					flag=w;
					break;
				}
				int fa=v/N;
				if(v%N==0)
					fa--;
				v=fa;
				
			}
			printf("%d\n",flag+1); 
		}
		else
			printf("%d\n",v);
	}
	return 0;
 } 
 	

Measured memory_bytes: 1152
# coding: utf-8
import sys


def main(argv=sys.argv):

    max_range, min_digit_sum, max_digit_sum = map(int, input().split(' '))

    ok_sum = 0
    for i in range(1, max_range + 1):
        digit_sum = sum(map(int, list(str(i))))
        if min_digit_sum <= digit_sum <= max_digit_sum:
            ok_sum += i

    print(ok_sum)

    return 0


if __name__ == '__main__':
    sys.exit(main())


Measured memory_bytes: 2940
#include <bits/stdc++.h> 
using namespace std; 
int n,m,u,v;
void dfs(int node, vector<int> adj[], int dp[], bool vis[]) 
{ 
    vis[node] = true; 
    for (int i = 0; i < adj[node].size(); i++) { 
        if (!vis[adj[node][i]]) 
            dfs(adj[node][i], adj, dp, vis); 
        dp[node] = max(dp[node], 1 + dp[adj[node][i]]); 
    } 
} 
int findLongestPath(vector<int> adj[], int n) 
{ 
    int dp[n + 1]; 
    memset(dp, 0, sizeof dp); 
    bool vis[n + 1]; 
    memset(vis, false, sizeof vis); 
    for (int i = 1; i <= n; i++) { 
        if (!vis[i]) 
            dfs(i, adj, dp, vis); 
    } 
    int ans = 0; 
    for (int i = 1; i <= n; i++) { 
        ans = max(ans, dp[i]); 
    } 
    return ans; 
} 
int main() 
{ 
    cin>>n>>m;
    vector<int> adj[n + 1]; 
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        adj[u].push_back(v);
    }
  
    cout << findLongestPath(adj, n); 
} 

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

int main()
{
    int a,b,k;
    cin >> a >> b >> k;
    int count = 1;
    set<int> ans;
    for(int i = a; i < a+k && i <= b; i++){
        ans.insert(i);
    }
    int num;
    if(b-k+1 < a){
        num = a;
    }else{
        num = b-k+1;
    }
    for(int i = num; i <= b; i++){
        ans.insert(i);
    }
    for(auto itr = ans.begin(); itr != ans.end(); itr++){
        cout << *itr << endl;
    }
}

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

int main(){
  int x,y;
  while(1){
    cin >> x >> y;
    if (x == 0 and y == 0){
      break;
    }
    if (x <= y){
      cout << x << " " << y << endl;
    }
    if (x > y){
      cout << y << " " << x << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3068
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    int x = sc.nextInt();
    int count = 0;
    for(int i = 0; i <= a; i++){
      for(int j = 0; j <= b; j++){
        int k = (x - 500 * i - 100 * j) / 50;
        if(k <= c && k >= 0){
          count++;
        }
      }
    }
    System.out.println(count);
  }
}

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

#define DEBUG(x) cerr << #x << ": " << x << endl;
#define ll long long

struct pos {
    int x;
    int y;
} typedef p;

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

    vector<p> stu(n+1);
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;

        stu[i].x = x;
        stu[i].y = y;
    }

    vector<p> check(m+1);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;

        check[i].x = x;
        check[i].y = y;
    }

    for (int i = 1; i <= n; i++) {
        int minDst = 1e9;
        int minCheck = 0;
        for (int j = 1; j <= m; j++) {
            int dif = abs(stu[i].x - check[j].x) + abs(stu[i].y - check[j].y);
            if (dif < minDst) {
                minDst = dif;
                minCheck = j;
            }
        }
        cout << minCheck << endl;
    }

    return 0;
}

Measured memory_bytes: 256
N = int(input())
p_ls = list(map(int, input().split(' ')))
cnt = 0

for i in range(len(p_ls) - 1):
    min_idx = i
    for j in range(i + 1, len(p_ls)):
        if p_ls[min_idx] > p_ls[j]:
            min_idx = j
    if min_idx != i:
        p_ls[min_idx], p_ls[i] = p_ls[i], p_ls[min_idx]
        cnt += 1
if cnt > 1:
    print('NO')
else:
    print('YES')

Measured memory_bytes: 9100