akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
    int l, r, d;
    cin >> l >> r >> d;
    
    int ans = 0;
    for (int i = l; i <= r; i++)
        if (i % d == 0)
            ans++;
        
    cout << ans << endl;
    
    return 0;
}


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

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

int main(){
        int n,m;
        cin>>n>>m;
        vector<int>a(m),b(m);
        P p[100000];
        for(int i=0;i<m;i++){
                cin>>a[i]>>b[i];
                p[i]=P(b[i],a[i]);
        }
        sort(p,p+m);
        int ans=1;
        int tmp=p[0].first;
        for(int i=0;i<m;i++){
                if(tmp-1<p[i].second)ans++,tmp=p[i].first;
        }
        cout<<ans<<endl;
        return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;

int main()
{
  int h,w;
  cin>>h>>w;
  vector<string> mat(h);
  REP(i,h)cin>>mat[i];
  vector red(h, string(w, '.'));
  vector blue(h, string(w, '.'));
  REP(i,h) red[i].back() = '#';
  REP(i,h) blue[i].front() = '#';
  FOR(i,1,w) red.front()[i] = '#';
  REP(i,w-1) blue.back()[i] = '#';
  FOR(i,1,h-1)FOR(j,1,w-1) {
    int s = (i+j) / 2;
    if (mat[i][j] == '#') {
      red[i][j] = '#';
      blue[i][j] = '#';
    } else {
      if (s % 2) {
        red[i][j] = '#';
      } else {
        blue[i][j] = '#';
      }
    }
  }
  REP(i,h) cout<<red[i]<<"\n";
  cout<<"\n";
  REP(i,h) cout<<blue[i]<<"\n";

  return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
pair<int,int> P[202020];
int V[202020],L[202020],R[202020];

ll dp[202020];
ll S[202020];
ll mo=1000000007;



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	map<int,int> M;
	cin>>N;
	FOR(i,N) {
		cin>>P[i].first>>P[i].second;
		M[P[i].second]=0;
	}
	sort(P,P+N);
	x=0;
	FORR(r,M) r.second=++x;
	FOR(i,N) {
		V[i]=M[P[i].second];
		R[i]=max(i?R[i-1]:V[i],V[i]);
	}
	for(i=N-1;i>=0;i--) {
		L[i]=min((i==N-1)?V[i]:L[i+1],V[i]);
	}
	
	dp[0]=S[0]=1;
	y=0;
	FOR(i,N) {
		while(y<R[i]) y++,(S[y]=S[y-1]+dp[y])%=mo;
		ll x=mo+S[R[i]]-((L[i]-2>=0)?S[L[i]-2]:0);
		(dp[R[i]]+=x)%=mo;
		(S[R[i]]+=x)%=mo;
	}
	cout<<dp[N]<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 16768
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in= new Scanner(System.in);
		
		int a = in.nextInt();
		int b = in.nextInt();
		
		int m = 0;
		
		if(a<=9 && b<=9) {
			m = a * b;
			System.out.println(m);
		}
		else {
			System.out.println("-1");
		}

	}

}


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

int main()
{
    int b1,b2,b3;
    cin >> b1 >> b2 >> b3;
    int x,y,z;
    cin >> x >> y >> z;
    if(x-b1 != y-b2||y-b2 != z-b3||x-b1 != z-b3){
        cout << "No";
        return 0;
    }
    cin >> x >> y >> z;
    if(x-b1 != y-b2||y-b2 != z-b3||x-b1 != z-b3){
        cout << "No";
        return 0;
    }
    cout << "Yes";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int N;
bool flag=false;
inline long long read(){
	int x=0,f=1;
	char c;
	do{c=getchar();if(c=='-'){f*=-1;}}while(!isdigit(c));
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}
int main(){
	N=read();
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			if(i*j==N){flag=true;}
		}
	}
	if(flag){printf("Yes\n");}
	else{printf("No\n");}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);  
    int t;
    //cin>>t;
    //while(t--)
    {
        int n ;
        cin>>n;
        vector <int> arr(n);
        for(int i = 0;i<n;i++)
        {
            cin>>arr[i];
        }
        set <int> check;
        check.insert(arr.begin(),arr.end());
        if(check.size()==n)
        cout<<"YES\n";
        else{
            cout<<"NO\n";
        }
    }
    return 0;
}

Measured memory_bytes: 13472
N,K=map(int,input().split())
A=list(map(int,input().split()))
import collections
a=collections.Counter(A)
a=sorted(a.items(),key=lambda x:x[1])
k=len(a)
ans=0
i=0
while k>K:
        ans+=a[i][1]
        i+=1
        k-=1
print(ans)

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

#define REP(i, start, count) for(int i=(start); i<(int)(count); ++i)
#define rep(i, count) REP(i, 0, count)
#define ALLOF(c) (c).begin(), (c).end()

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline T gcd(T a, T b)
{
    T r;
    if (a < b)
        swap(a, b);

    while (b > 0)
    {
        r = a % b;
        a = b;
        b = r;
    }

    return a;
}

template <class T>
inline T lcm(T a, T b)
{
    if (a * b == 0)
        return 0;
    return a * b / gcd(a, b);
}

ll A, B, C, D;

int main(void) {
    cin >> A >> B >> C >> D;
    ll CD = C * D;

    ll LCM = lcm(C, D);

    ll Aminus = A - 1;
    ll toA = Aminus - (Aminus / C) - (Aminus / D) + Aminus / LCM;

    ll toB = B - (B / C) - (B / D) + B / LCM;

    cout << toB - toA << endl;
    return 0;
}

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

class mint {
  int value;
  static vector<int> _fact;
  static int extGCD(int a, int &x, int b, int &y) {
    if (b == 0) {
      x = 1, y = 0;
      return a;
    }
    int ret = extGCD(b, y, a % b, x);
    y -= a / b * x;
    return ret;
  }

public:
  static const int MOD = 998244353;
  mint(long long x)
      : value((x % MOD + MOD) % MOD) {}
  mint operator+(mint y) const {
    return mint(value + y.value);
  }
  mint &operator+=(mint a) {
    return *this = *this + a;
  }
  mint operator*(mint y) const {
    return mint(long(value) * y.value);
  }
  mint &operator*=(mint a) {
    return *this = *this * a;
  }
  mint operator-() const {
    return *this * mint(-1);
  }
  mint operator-(mint y) const {
    return *this + (-y);
  }
  mint &operator-=(mint a) {
    return *this = *this - a;
  }
  operator int() const {
    return value;
  }
  static mint pow(mint a, int n) {
    if (n <= 0) {
      return 1;
    }
    else if (n == 1) {
      return a;
    }
    mint half = mint::pow(a, n / 2);
    return n % 2 ? half * half * a : half * half;
  }
  static mint fact(int n) {
    if (size_t(n) < _fact.size()) {
      return _fact[n];
    }
    mint ans = fact(n - 1) * mint(n);
    _fact.push_back(ans);
    return ans;
  }
  mint inv() {
    int x, y;
    extGCD(value, x, MOD, y);
    return mint(x);
  }
  static mint comb(int n, int k) {
    return fact(n) * fact(k).inv() * fact(n - k).inv();
  }
};
vector<int> mint::_fact = {1};

int main() {
  int N, M, K;
  cin >> N >> M >> K;

  mint ans = 0;
  for (int i = 0; i <= K; i++) {
    ans += mint(M) * mint::comb(N - 1, i) * mint::pow(M - 1, N - 1 - i);
  }

  cout << ans << endl;
}


Measured memory_bytes: 10436
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int h = sc.nextInt();
		int w = sc.nextInt();
		for(int i = 0; i < h; i++){
		    String s = sc.next();
		    System.out.println(s);
		    System.out.println(s);
		}
		
		
		// 計算
		//int result = 0;
		
		// 出力
		//System.out.println(result);
	}

	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}


Measured memory_bytes: 24020
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

int n;
ll x[100010],S[100010];

struct mod_fac{
    private:
        vector<ll> f,i_f;
        int n;ll MOD;
    public:
        void init(int n,ll m){
            MOD=m;
            f.resize(n+1,0);
            i_f.resize(n+1,0);
            f[0]=1;
            rep(i,n){
                f[i+1]=f[i]*(i+1)%MOD;
            }
            i_f[n]=power(f[n],MOD-2);
            per(i,n){
                i_f[i]=(i_f[i+1]*(i+1))%MOD;
            }
        }
        ll power(ll a ,ll x){
            if (x==0) return 1;
            if (x==1) return a%MOD;
            if (x==2) return (a*a)%MOD;
            if (x%2==1) return (a*power(power(a,(x-1)/2),2))%MOD;
            return (power(power(a,x/2),2))%MOD;
        }
        ll fac(int x){
            return f[x];
        }
        ll invfac(int x){
            return i_f[x];
        }
        ll comb(int m,int k){
            if (m<0 or k<0) return 0;
            if (m<k) return 0;
            return (((f[m]*i_f[k])%MOD)*i_f[m-k])%MOD;
        }
};

void solve(){
    cin >> n;
    rep(i,n){
        cin >> x[i];
        S[i+1]=S[i]+x[i];
        S[i+1]%=mod;
    }
    mod_fac mo;mo.init(n,mod);
    ll ans=0;
    Rep(t,1,n-1){
        ll T=(ll)t*((ll)t+1ll)%mod;
        ll T_inv=mo.power(T,mod-2);
        ans+=T_inv*(S[n-1]-S[t]-S[n-t-1]+S[0]+2*mod);
        ans%=mod;
    }
    rep(i,n-1){
        ll inv=mo.power(n-i-1,mod-2);
        ans+=(x[n-1]-x[i])*inv;
        ans%=mod;
    }
    cout << ans*mo.fac(n-1)%mod << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(50);
    solve();
}

Measured memory_bytes: 3456
"use strict";
const main = input => {
    const n = parseInt(input[0].split(' ')[0], 10);
    const m = parseInt(input[0].split(' ')[1], 10);
    const c = parseInt(input[0].split(' ')[2], 10);
    const b = input[1].split(' ');
    for(let i=0; i<m; i++) {
        b[i] = parseInt(b[i], 10);
    }
    let sum, ans = 0;
    for(let i=0; i<n; i++) {
        sum=0;
        let a = input[i+2].split(' ');
        for(let k=0; k<m; k++) {
            a[k] = parseInt(a[k], 10);
            sum+=a[k]*b[k];
        }
        if (sum+c>0) {
            ans++;
        }
    }
    console.log(ans);
    
}
main(require("fs").readFileSync("/dev/stdin", "utf8").split('\n'));

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

long long int modPow(long long int a, long long int n){//繰り返し自乗法(a^n mod p)。計算量 O(logN)
    long long int p = pow(10, 9) + 7;//任意のp(素数) modのやつで使える 
    if(n == 0){
        return 1;
    }
    if(n == 1){
        return a % p;
    }
    if (n % 2 == 1){ 
        return (a * modPow(a, n - 1)) % p;
    }      
    long long t = modPow(a, n / 2);
    return (t * t) % p;
}

int main(){
    int n;
    cin >> n;
    vector<char> c(n);
    int redCount = 0;
    int whiteCount = 0;
    
    stack<int> red;//スタック
    queue<int> white;//キュー
    //白の先頭と赤の一番尻を交換したい
    for(int i = 0; i < n; i++){
        cin >> c.at(i);
        if(c.at(i) == 'R'){
            redCount++;
            red.push(i);
            //cout << i << endl;
        }else{
            whiteCount++;
            white.push(i);
        }
    }

    //reverce(red.begin(), red.end());//尻の座標が先頭にある
    int count = 0;
    char tmp;
    for(int i = 0; i < n; i++){
        if(c.at(i) == 'W' && !(red.empty())){// 
            if(i < red.top()){
                c.at(i) = 'R';
                c.at(red.top()) = 'W';
                white.pop();
                red.pop();    
                count++;
            }
        }
        /*for(int j = 0; j < n; j++){
            cout << c.at(j);
        }
        cout << count << endl;*/
    }


    cout << min(redCount, min(whiteCount, count)) << endl;
}

Measured memory_bytes: 4388
R,G,B,N = (int(i) for i in input().split())
P = N//R
ans = 0
count1=0
count2=0
for i in range(P+1):
    left = N - i*R
    Q = left//G
    for j in range(Q+1):
        left1 = left - j*G
        if left1%B == 0:
            ans +=1
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cassert>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
#include <iomanip>
#include <fstream>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define chmax(a,b) (a<b?(a=b,1):0)
#define chmin(a,b) (a>b?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
const int INF = 1<<29;
const double EPS = 1e-8;
const double PI = acos(-1);
typedef long long ll;
typedef pair<int,int> pii;

const int H = 50;
const int W = 50;

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

struct Field {
  char a[H][W];
  int h,w;
  int dist[H][W];
  void input_hw() {
    cin >> h >> w;
  }
  void set_hw(int _h, int _w) {
    h = _h; w = _w;
  }
  void input_field() {
    REP(i,h)REP(j,w)cin>>a[i][j];
  }
  void bfs(int y, int x) {
    memset(dist,-1,sizeof(dist));
    queue<pii> Q;
    Q.push(pii(y,x));
    dist[y][x] = 0;
    while(!Q.empty()) {
      pii p = Q.front(); Q.pop();
      REP(i,4) {
        int yy = p.first + dy[i];
        int xx = p.second + dx[i];
        if (valid(yy,xx,h,w)) {
          if (a[yy][xx] == '#') continue;
          if (dist[yy][xx] == -1) {
            dist[yy][xx] = dist[p.first][p.second] + 1;
            Q.push(pii(yy,xx));
          }
        }
      }
    }
  }
  bool canGo(int y, int x) {
    return dist[y][x] != -1;
  }
} field;

int a[H][W];

int main() {
  int h,w,d,n;
  while(cin >> h >> w >> d >> n) {
    field.set_hw(h,w);
    field.input_field();
    int sy,sx;
    REP(i,h)REP(j,w)if(field.a[i][j] == 'D') sy=i,sx=j;
    field.bfs(sy,sx);
    int r[d+2];
    REP(i,d) {
      cin >> r[i+1];
    }
    r[0] = -1;
    r[d+1] = INF;
    memset(a,0,sizeof(a));
    REP(ii,n) {
      int x,y,s;
      cin >> x >> y >> s;
      REP(i,h) {
        REP(j,w) {
          int dist = max(abs(i-y),abs(j-x));
          if (r[s] < dist && dist <= r[s+1]) {
            a[i][j]++;
          }
        }
      }
    }
    int S = 0;
    REP(i,h)REP(j,w) {
      if (a[i][j] == n && field.a[i][j] != '#') {
        if (field.canGo(i,j)) S |= 1;
        else S |= 2;
      }
    }
    // REP(i,h) {
    //   REP(j,w) cout << a[i][j] << " ";
    //   cout << endl;
    // }
    if (S == 0) puts("Broken");
    else if (S == 1) puts("Yes");
    else if (S == 2) puts("No");
    else puts("Unknown");
  }
}

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

int main() {
    int n, x, cnt=0;
    while (cin >> n >> x) {
        if (n == 0 && x==0) return 0;
        cnt=0;

        for (auto i=1; i<n-1; i++) for(auto j=i+1; j<n; j++) for(auto k=j+1; k<n+1; k++) if (i != j && i != k && j != k) if(i+j+k == x) cnt++;
        cout << cnt << endl;
    }

    return 0;
}


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define trace(it,mp) for(auto it = (mp).begin(); it != (mp).end(); it++)
#define fr(i,n) for(ll i=0;i<n;i++)
#define mod 1000000000
using namespace std;

// covert number to string to_string(x);
ll h(ll a[],ll n)
{
	ll dp[n+1];
	dp[0]=0;
	dp[1]=0;

	for(ll i=2;i<=n;i++)
	{
		if(i==2)
			dp[i]=abs(a[i-1]-a[i-2]);
		else
			dp[i]=min(abs(a[i-1]-a[i-2])+dp[i-1],abs(a[i-1]-a[i-3])+dp[i-2]);
	}

	return dp[n];
}

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

    ll t,a,b,c,x,y,z,n,m,k,ans;
    cin >> n;

    ll arr[n];

    fr(i,n){
    	cin >> arr[i];
    }

    cout << h(arr,n);

    cerr<< '\n' << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n" ;
}

Measured memory_bytes: 5296
S=input()
N=len(S)
As=[0]*N
ABs=[0]*N
ABCs=[0]*N
p=10**9+7

if S[0]=="A":
    As[0]=1

now=1
if S[0]=="?":
    now=3
    As[0]=1
for i in range(1,N):
    s=S[i]
    if s=="A":
        As[i]=(As[i-1]+now)%p
        ABs[i]=ABs[i-1]
        ABCs[i]=ABCs[i-1]
    elif s=="B":
        As[i]=As[i-1]
        ABs[i]=(ABs[i-1]+As[i-1])%p
        ABCs[i]=ABCs[i-1]

    elif s=="C":
        As[i]=As[i-1]
        ABs[i]=ABs[i-1]
        ABCs[i]=(ABCs[i-1]+ABs[i-1])%p

    else:
        
        As[i]=(3*As[i-1]+now)%p
        ABs[i]=(3*ABs[i-1]+As[i-1])%p
        ABCs[i]=(3*ABCs[i-1]+ABs[i-1])%p
        now*=3
        now%=p

print(ABCs[-1])
#print(As)
#print(ABs)
#print(ABCs)

Measured memory_bytes: 76040
#include<bits/stdc++.h>
using namespace std;
long long n, a, b;
int getlen(long long x) {
    int i = 0;
    while (x) {
        x /= 10;
        ++i;
    }
    return i;
}
int main(){
    cin >> n;
    for (long long i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            a = i;
            b = n / i;
        }
    }
    cout << max(getlen(a), getlen(b)) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REPR(i, n) for(int i = (n); i >= 0; i--)
#define FOR(i, m, n) for(int i = (m); i < (n); i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << ": " << x << endl;

using namespace std;
typedef long long ll;

signed main() {
  int a;
  cin >> a;
  cout << a + a * a + a * a * a << endl;
  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 1000007
#define INF63 1061109567
#define INF127 9187201950435737471
#define F first
#define S second
#define ll long long
#define N 100010
#define M 20
#define NM 70000
using namespace std;
int n,m,val[N],tms[M],v=0,ans=0,dp[NM];
bool can[NM]={};
int main(){
	int i,j,x,y,z;
	cin>>n;
	memset(tms,0,sizeof(tms));
	memset(val,0,sizeof(val));
	for(i=1;i<n;i++)
	{
		cin>>x>>y>>z;
		val[x]^=z;
		val[y]^=z;
	}
	for(i=0;i<n;i++)
	{
		tms[val[i]]++;
	}
	ans+=tms[0];
	for(i=1;i<16;i++)
	{
		if(tms[i]%2==1)
		{
			v+=(1<<i);
		}
		ans+=tms[i]/2;
	}
	for(i=0;i<(1<<16);i++)
	{
		x=0;
		for(j=1;j<16;j++)
		{
			if((i&(1<<j))!=0)
			{
				x^=j;
			}
		}
		if(x==0)
		{
			can[i]=true;
		}
	}
	memset(dp,0,sizeof(dp));
	for(i=0;i<(1<<16);i++)
	{
		for(j=i;j!=0;j=i&(j-1))
		{
			if(can[j])
			{
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
	}
	ans+=dp[v];
	cout<<n-ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	k,q = readline() |> split |> parseMap
	d = readline() |> split |> parseMap
	for query in 1:q
		n,x,m = readline() |> split |> parseMap
		c = Int[d[i]%m for i in 1:k]
		zc = Int[0 for i in 1:k]
		if c[1]==0
			zc[1] = 1
		end
		for i in 2:k
			if c[i] == 0
				zc[i] += 1
			end
			c[i] += c[i-1]
			zc[i] += zc[i-1]
		end
		u = div(n-1,k)
		v = (n-1)%k
		os = v==0?div(x%m+u*c[k],m):div(x%m+u*c[k]+c[v],m)
		zs = v==0?u*zc[k]:u*zc[k]+zc[v]
		println(n-1-os-zs)
	end
end

main()

Measured memory_bytes: 177944
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)

int n,m[1001][1001],dp[1001][1001];

int main(){
	while(cin>>n&&n){
		rep(i,n)fill(dp[i],dp[i]+n,0);
		char c;
		rep(i,n)rep(j,n){
			cin>>c;
			m[i][j]=(c=='.')?1:0;
			if(!i||!j)dp[i][j]=m[i][j];
		}
		int ans=0;
		for(int i=1;i<n;i++)for(int j=1;j<n;j++){
			if(m[i][j]){
				dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
				ans=max(ans,dp[i][j]);
			}
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 6812
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use itertools::Itertools;
use proconio::*;
use std::collections::VecDeque;
use std::io::stdin;
use std::str::FromStr;
use text_io::*;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let mut sc = Scanner::new();
    let n = sc.next_usize();
    let mut a = sc.make_vec_line::<usize>(n);
    a.sort();
    a.reverse();

    let mut j = 0;
    let mut ans = 0;
    for i in 0..(n - 1) {
        ans += a[j];

        if i == 0 {
            j += 1;
        } else if i % 2 == 0 {
            j += 1;
        }
    }

    println!("{}", ans);
}

pub struct Scanner {
    buf: VecDeque<String>,
}

impl Scanner {
    pub fn new() -> Self {
        Self {
            buf: VecDeque::new(),
        }
    }

    fn scan_line(&mut self) {
        let mut flag = 0;
        while self.buf.is_empty() {
            let mut s = String::new();
            stdin().read_line(&mut s).unwrap();
            let mut iter = s.split_whitespace().peekable();
            if iter.peek().is_none() {
                if flag >= 5 {
                    panic!("There is no input!");
                }
                flag += 1;
                continue;
            }

            for si in iter {
                self.buf.push_back(si.to_string());
            }
        }
    }

    pub fn next<T: FromStr>(&mut self) -> T {
        self.scan_line();
        self.buf
            .pop_front()
            .unwrap()
            .parse()
            .unwrap_or_else(|_| panic!("Couldn't parse!"))
    }

    pub fn next_usize(&mut self) -> usize {
        self.next()
    }

    pub fn next_isize(&mut self) -> isize {
        self.next()
    }

    pub fn next_chars(&mut self) -> Vec<char> {
        self.next::<String>().chars().collect_vec()
    }

    pub fn next_string(&mut self) -> String {
        self.next()
    }

    pub fn fill_vec_line<T: FromStr>(&mut self, v: &mut Vec<T>) {
        for vi in v {
            *vi = self.next();
        }
    }

    pub fn fill_vec<T: FromStr>(&mut self, v: &mut Vec<Vec<T>>) {
        for vi in v {
            for vii in vi {
                *vii = self.next();
            }
        }
    }

    pub fn make_vec_line<T: FromStr + Default + Clone>(&mut self, i: usize) -> Vec<T> {
        let mut v = vec![Default::default(); i];
        self.fill_vec_line(&mut v);
        v
    }

    pub fn make_vec<T: FromStr + Default + Clone>(&mut self, i: usize, j: usize) -> Vec<Vec<T>> {
        let mut v = vec![vec![Default::default(); j]; i];
        self.fill_vec(&mut v);
        v
    }
}


Measured memory_bytes: 15092
#include <bits/stdc++.h>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

main() {
    int64_t n;
    cin >> n;

    vector<int64_t> a(n);
    for (auto&& aa : a) {
        cin >> aa;
    }

    int64_t b = 0;
    for (auto i : irange(0L, 60L) | reversed) {
        vector<int64_t> idxs;
        for (auto aa : a | indexed()) {
            if ((aa.value() & (1L << i)) > 0) {
                idxs.push_back(aa.index());
            }
        }

        if (idxs.empty()) {
            continue;
        }

        int64_t num = idxs.size();
        if (num % 2 == 1) {
            continue;
        }

        auto aa = a[idxs.front()];
        for (auto idx : idxs) {
            a[idx] ^= aa;
        }

        if ((b & (1L << i)) > 0) {
            continue;
        }

        b ^= aa;
    }

    int64_t c = b;
    for (auto aa : a) {
        c ^= aa;
    }

    cout << b + c << endl;
}

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

int main()
{
	int n, sum = 0, a, b, c = 0;
	cin >> n >> a >> b;
	for (int x=1;x<=n;x++)
	{ 
	 sum = 0;
	 for (int i = x; i > 0;)
	 {
		sum += i % 10;
		i = i / 10;
	 }
	 if (sum >= a && sum <= b)
		 c += x;
	}
	cout << c;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e18;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    char a;
    cin >> a;
    if(a >= 'a' && a <= 'z') {
        cout << "a" << endl;
    }
    else {
        cout << "A" << endl;
    }
}


Measured memory_bytes: 3640
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define SZ(c) int(c.size())
#define pb push_back
#define loop(i,start,n)  for(int i=start;i<n;i++)
#define rloop(i,start,n)  for(int i=start;i>n;i--)

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vs = vector<string>;
const ll inf = 2e9+3;

void solve(){
    int tc=1 ;
    //cin >> tc;
    while(tc--) {
        ll n,m,k,res=0;
        cin >> n >> m >> k;
        vll va(n+1) , vb(m+1);
        ll A=0, B=0;
        loop(i,1,n+1) { cin >> va[i]; va[i] = va[i]+va[i-1]; }
        loop(i,1,m+1) { cin >> vb[i]; vb[i] = vb[i]+vb[i-1]; }
        ll b = m;
        loop(i,0,n+1){
            if(va[i] > k) break;
            while(vb[b] > k-va[i]) b-=1;
            res = max(res,i+b);
        }
        cout << res;
    }
}

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

Measured memory_bytes: 6344
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
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; }

int N, M;
vector<bool> visit;
vector<bool> seen;

void dfs(int v, const vector<vector<int>> &G) {
    if (seen[v]) return;
    visit[v] = true; seen[v] = true;
    for (auto u : G[v]) if (!seen[u]) dfs(u, G);
}

template<typename T>
pair<bool, vector<T>> bellmanford(const vector<vector<pair<int, T>>> &G, int s) {
    const T inf = numeric_limits<T>::max();
    int V = G.size();
    vector<T> dist(V, inf); dist[s] = 0;
    bool negative_cycle = false;
    
    for (int relax = 0; relax <= V; relax++) {
        for (int from = 0; from < V; from++) {
            for (const auto &e : G[from]) {
                int to; T cost; tie(to, cost) = e;
                if (dist[from] == inf) continue;
                if (dist[from] + cost < dist[to]) {
                    dist[to] = dist[from] + cost;
                    if (relax == V && visit[to]) negative_cycle = true;
                }
            }
        }
    }
    return {negative_cycle, dist};
}

signed main() {
    cin >> N >> M;
    vector<vector<pair<int, int>>> G(N);
    vector<vector<int>> H(N);
    seen.resize(N, false);
    visit.resize(N, false);
    for (int i = 0; i < M; i++) {
        int v, u, c; cin >> v >> u >> c; v--; u--;
        G[v].emplace_back(u, -c);
        H[u].emplace_back(v);
    }
    
    dfs(N-1, H);
    
    bool neg; vector<int> dist;
    tie(neg, dist) = bellmanford(G, 0);
    
    int ans = -dist[N-1];
    if (neg) cout << "inf" << endl;
    else cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1152
N,K=input().split()
N,K=int(N),int(K)-1
S=input()

#文字列はイミュータブル
'''
if S[K]=="A":
    S[K]="a"
elif S[K]=="B":
    S[K]="b"
else:
    S[K]="c"

print(S)
'''
Slist=list(S)
if S[K]=="A":
    Slist[K]="a"
elif S[K]=="B":
    Slist[K]="b"
else:
    Slist[K]="c"

print("".join(Slist))


Measured memory_bytes: 3060
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

using ll = long long;

void read();
template<typename First, typename... Rest> void read(First& first, Rest&... rest);
void write();
template<typename First, typename... Rest> void write(First first, Rest... rest);
template<typename T> void write_vec(vector<T>& v, char divider);

int main(){
    int H, W;
    read(H, W);
    vector<string> a(H);
    for(int i = 0; i < H; i++){
        read(a[i]);
    }
    int nH = H;
    int nW = W;
    int i = 0;
    while(i < nH){
        bool f = true;
        for(int j = 0; j < nW; j++){
            if(a[i][j] == '#') f = false;
        }
        if(f){
            for(int k = i; k < nH - 1; k++){
                for(int j = 0; j < nW; j++){
                    a[k][j] = a[k + 1][j];
                }
            }
            nH--;
        }
        else i++;
    }
    int j = 0;
    while(j < nW){
        bool f = true;
        for(int i = 0; i < nH; i++){
            if(a[i][j] == '#') f = false;
        }
        if(f){
            for(int k = j; k < nW - 1; k++){
                for(int i = 0; i < nH; i++){
                    a[i][k] = a[i][k + 1];
                }
            }
            nW--;
        }
        else j++;
    }
    for(int i = 0; i < nH; i++){
        for(int j = 0; j < nW; j++){
            cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

//配列以外の入力を受け取る
void read(){

}
template<typename First, typename... Rest>
void read(First& first, Rest&... rest){
    cin >> first;
    read(rest...);
}
//
//配列以外を出力する
void write(){

}
template<typename First, typename... Rest>
void write(First first, Rest... rest){
    cout << first << " ";
    write(rest...);
}
//
//配列を区切って出力する
template<typename T>
void write_vec(vector<T>& v, char divider){
    for(size_t i = 0; i < v.size(); i++){
        cout << v[i] << divider;
    }
}
//

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;

int main(void)
{
	int n, s;
	int magic[20500];
	
	while (cin >> n >> s, n && s){
		for (int i = 0; i < n; i++){
			scanf("%d", &magic[i]);
		}
		
		int ret = 0;
		for (int i = 0; i < n; i++){
			for (int j = i + 1; j < n; j++){
				if (magic[i] + magic[j] > s) ret++;
			}
		}
		
		cout << ret << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1284
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;
#define fi first
#define se second
const ll INFLL=LLONG_MAX;
const int INF=INT_MAX;
#define eb emplace_back
#define emp emplace
#define mp(a,b) make_pair(a,b)
template<class T> using min_heap=priority_queue<T,vector<T>,greater<T> >;
template<class T>
void sort(vector<T>& v){
	sort(v.begin(),v.end());
}
template <class T, class U>
void sort(vector<T>& v,U func){
	sort(v.begin(),v.end(),func);
}
template <class T>
int lb_index(vector<T>& v,T k){
	return lower_bound(v.begin(),v.end(),k)-v.begin();
}
template <class T>
int ub_index(vector<T>& v,T k){
	return upper_bound(v.begin(),v.end(),k)-v.begin();
}
template<class T>
struct segtree{
private:
	T init;
	int n;
	function<T(T,T)> op;
	vector<T>arr;
	vector<T>st;
	vector<T>lz;
	void build(int lo,int hi,int u){
		if(lo==hi){
			st[u]=arr[lo];
		}
		else{
			int mi=(hi+lo)>>1;
			build(lo,mi,u<<1);
			build(mi+1,hi,u<<1|1);
			st[u]=op(st[u<<1],st[u<<1|1]);
		}
	}
	void apply(T x,int u,int lo,int hi){
// 		st[u]+=x*(hi-lo+1);
 		st[u]+=x;
//		st[u]=x;
// 		st[u]=x*(hi-lo+1);
 		lz[u]+=x;
//		lz[u]=x;
	}
	void push(int u,int lo,int hi){
		if(lz[u]!=init){
			int mi=(lo+hi)>>1;
			apply(lz[u],u<<1,lo,mi);
			apply(lz[u],u<<1|1,mi+1,hi);
			lz[u]=init;
		}
	}
	void modify(int l,int r,T x,int u,int lo,int hi){
		if(r<lo||l>hi||l>r)return;
		if(l<=lo&&r>=hi){
			apply(x,u,lo,hi);
			return;
		}
		push(u,lo,hi);
		int mi=(lo+hi)>>1;
		if(mi>=r){
			modify(l,r,x,u<<1,lo,mi);
		}
		else if(mi<l){
			modify(l,r,x,u<<1|1,mi+1,hi);
		}
		else{
			modify(l,mi,x,u<<1,lo,mi);
			modify(mi+1,r,x,u<<1|1,mi+1,hi);
		}
		st[u]=op(st[u<<1],st[u<<1|1]);
	}
	T query(int l,int r,int u,int lo,int hi){
		if(l>r||l>hi||r<lo)return init;
		if(l<=lo&&r>=hi){
			return st[u];
		}
		push(u,lo,hi);
		int mi=(hi+lo)>>1;
		if(mi>=r){
			return query(l,r,u<<1,lo,mi);
		}
		else if(mi<l){
			return query(l,r,u<<1|1,mi+1,hi);
		}
		else{
			return op(query(l,mi,u<<1,lo,mi),query(mi+1,r,u<<1|1,mi+1,hi));
		}
	}
public:
	segtree(T n,function<T(T,T)> op):n(n),st(n*4),op(op),lz(n*4){
		init=T();
	}
	segtree(vector<T> v,function<T(T,T)> op):n(v.size()),st(v.size()*4),op(op),lz(v.size()*4){
		init=T();
		arr=v;
		build(0,n-1,1);
	}
	T query(int l,int r){
		return query(l,r,1,0,n-1);
	}
	void setinit(T x){
		init=x;
		for(int i=0;i<4*n;i++){
			st[i]=init;
			lz[i]=init;
		}
	}
	void modify(int l,int r,T x){
		modify(l,r,x,1,0,n-1);
	}
};
int main(){
	int n,q;
	cin>>n>>q;
	segtree<int> seg(n,[](int a,int b){
		return min(a,b);
	});
	while(q--){
		int c;
		cin>>c;
		if(c){
			int l,r;
			cin>>l>>r;
			cout<<seg.query(l,r)<<"\n";
		}
		else{
			int l,r,x;
			cin>>l>>r>>x;
			seg.modify(l,r,x);
		}
	}
}




Measured memory_bytes: 5988
def f(num):
   i = 2
   d = dict()
   while i * i <= num:
       if num % i == 0:
           num //= i
           d[i] = d.get(i, 0) + 1
       else:
           i += 1
   
   d[num] = d.get(num, 0) + 1
   return d

n = int(input())
d = f(n)

ans = n
for k in d.keys():
    ans *= (1-(1/k))

print(int(ans))


Measured memory_bytes: 5604
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;

public class Main {
	private static final int INF = (int)1e9;

	static class Pair {
		int first;
		int second;

		public Pair(int first, int second) {
			this.first = first;
			this.second = second;
		}

		@Override
		public int hashCode() {
			return first + second;
		}

		@Override
		public boolean equals(Object other) {
			if (other instanceof Pair) {
				Pair p = (Pair)other;

				return p.first == first && p.second == second;
			}
			return false;
		}
	}

	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		try (Scanner in = new Scanner(System.in)) {
			int n = in.nextInt();
			List<Integer>[] g = new ArrayList[n];
			for (int i = 0; i < n; i++)
				g[i] = new ArrayList<>();

			int m = in.nextInt();
			int r = in.nextInt();
			Map<Pair, Integer> dist = new HashMap<>();
			for (int i = 0; i < m; i++) {
				int f = in.nextInt();
				int t = in.nextInt();
				int w = in.nextInt();

				g[f].add(t);
				dist.put(new Pair(f, t), w);
			}

			dijkstra(g, n, dist, r);
		} catch (Exception ex) {
			throw new RuntimeException(ex);
		}
	}

	public static void dijkstra(List<Integer> g[], int n, Map<Pair, Integer> dist, int s) {
		int[] d = new int[n];
		for (int i = 0; i < n; i++)
			d[i] = INF;

		d[s] = 0;
		PriorityQueue<Pair> pq = new PriorityQueue<>((x, y) -> x.second-y.second);
		pq.add(new Pair(s, 0));

		while (!pq.isEmpty()) {
			Pair p = pq.remove();

			for (int v : g[p.first]) {
				int dd = d[p.first] + dist.get(new Pair(p.first, v));
				if (dd < d[v]) {
					d[v] = dd;
					pq.add(new Pair(v, d[v]));
				}
			}
		}

		for (int i = 0; i < n; i++) {
			if (d[i] == INF)
				System.out.println("INF");
			else
				System.out.println(d[i]);
		}
	}
}

Measured memory_bytes: 367852
#include <bits/stdc++.h>
using namespace std;
 
#define FAST ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
 
#define MAXX 100005
 
#define PI   3.14159265358979323846264338327950

#define PB push_back 
#define F first
#define S second
 
#define ll 	 long long int

#define mod  1000000007





int main()
{
	FAST;
	ll m = 0;
	string s;
	cin >> s;
	for(ll i = 0; i < s.size(); i ++){
		if(s[i] == '+'){
			m ++;
		}
		else{
			m --;
		}
	}
	cout << m;
	return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin >> n;
    int a = n / 15;
    int b = n % 15;
    long long sum = 0;
    for (int i=0; i<a; i++){
        sum += a * 60;
    }
    if (b<1){
        sum += 0;
    }
    else if (b<2){
        sum += 1 + 15 * a;
    }
    else if (b<4){
        sum += 1 + 15 * a;
        sum += 2 + 15 * a;
    }
    else if (b<7){
        sum += 1 + 15 * a;
        sum += 2 + 15 * a;
        sum += 4 + 15 * a;
    }
    else if (b<8){
        sum += 1 + 15 * a;
        sum += 2 + 15 * a;
        sum += 4 + 15 * a;
        sum += 7 + 15 * a;
    }
    else if (b<11){
        sum += 1 + 15 * a;
        sum += 2 + 15 * a;
        sum += 4 + 15 * a;
        sum += 7 + 15 * a;
        sum += 8 + 15 * a;
    }
    else if (b<13){
        sum += 1 + 15 * a;
        sum += 2 + 15 * a;
        sum += 4 + 15 * a;
        sum += 7 + 15 * a;
        sum += 8 + 15 * a;
        sum += 11 + 15 * a;
    }
    else if (b<14){
        sum += 1 + 15 * a;
        sum += 2 + 15 * a;
        sum += 4 + 15 * a;
        sum += 7 + 15 * a;
        sum += 8 + 15 * a;
        sum += 11 + 15 * a;
        sum += 13 + 15 * a;
    }
    else if (b<15){
        sum += 1 + 15 * a;
        sum += 2 + 15 * a;
        sum += 4 + 15 * a;
        sum += 7 + 15 * a;
        sum += 8 + 15 * a;
        sum += 11 + 15 * a;
        sum += 13 + 15 * a;
        sum += 14 + 15 * a;
    }
    cout << sum << endl;
}

Measured memory_bytes: 3672
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>
#include <stack>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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; }

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

vector<ll> c;
vector<ll> d;
vector<vector<ll>> g;
int k;

void dfs(int v, int p=-1) {
  d[v] = c[k++];
  for (ll u : g[v]) {
    if (u == p) { continue; }
    dfs(u,v);
  }
}

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n;
  cin >> n;
  c.resize(n);
  d.resize(n);
  g.resize(n);

  vector<ll> deg(n);
  rep(i,n-1) {
    ll a,b;
    cin >> a >> b;
    --a; --b;
    g[a].push_back(b);
    g[b].push_back(a);
    ++deg[a];
    ++deg[b];
  }

  rep(i,n) {
    cin >> c[i];
  }
  sort(all(c));
  reverse(all(c));

  int maxD = 0;
  int root = 0;
  rep(i,n) {
    if (maxD < deg[i]) {
      maxD = deg[i];
      root = i;
    }
  }

  // printvec(c);

  dfs(root);

  ll m = 0;
  for (int i = 1; i < n; ++i) {
    m += c[i];
  }
  cout << m << endl;
  rep(i,n) {
    cout << d[i];
    if (i < n-1) {
      cout << " ";
    }
  }
  cout << endl;
}


Measured memory_bytes: 1408
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int N;
    string S;
    cin >> N >> S;
    int cnt = 0;

    for(int i = 0; i < N - 2; i++){
        string SS;
        SS.push_back(S[i]);
        SS.push_back(S[i+1]);
        SS.push_back(S[i+2]);
        if(SS == "ABC")cnt++;
    }

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


// 正解

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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
// #define map unordered_map
// #define set unordered_set
#define pll pair<ll, ll>
#define vll vector<ll>
#define mll map<ll, ll>

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

vector<ll> pr3(ll n) {
  vector<ll> ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

map<ll, ll> prime_factor(ll n) {
  map<ll, ll> ret;
  for (ll i = 2; i * i <= n; i++) {
    // for (ll i = 2; i <= pow(num, 0.5); i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

// Prime prime(1000005);
// vll l = prime.v(28); // 2,2,7

int main() {
  // std::cout << std::fixed << std::setprecision(10);

  ll N;
  scanf("%lld", &N);

  mll numbers = prime_factor(N);

  ll ans = 0;

  auto ite = numbers.begin();
  for (; ite != end(numbers); ite++) {
    ll key = (*ite).first;
    ll val = (*ite).second;
    // cout << key << ":" << val << endl;
    // cout << ans << endl;

    ll required = 1;
    for (;;) {
      if (val >= required) {
        ans++;
        val -= required;
      } else {
        break;
      }
      required += 1;
    }
    // cout << "ans:" << ans << endl;
  }

  cout << ans << endl;
}


Measured memory_bytes: 3696
//
//  CPlibrary
//
//  Created by Tanmay Singh on 3/03/2020.
// INDIAN INSTITUTE OF TECHNOLOGY (BHU) , VARANASI
//  Copyright © 2020 Tanmay Singh. All rights reserved.
//#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <climits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
 
#define FAST(); ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl "\n"
#define mod 1000000007
typedef long long int  bigint ;
typedef std::vector< int > vi;
typedef std::vector< long long int > vll;
typedef std::vector< vi > vvi;
 
using namespace std;


int main(){
    FAST() ;
    int N ; cin >> N ;
    int arr[N] ;
    for( int i = 0 ; i < N ; i++ ){
        cin >> arr[i] ;
    }
    sort( arr , arr + N ) ;
    int L = arr[0] , R = arr[N-1] ;
    int ANS = INT_MAX ;
    for( int i = L ; i <= R ; i++ ){
        int ans = 0 ;
        for( int j = 0 ; j < N ; j++ ){
            ans += ( arr[j] - i ) * ( arr[j] - i ) ;
        }
        ANS = min( ANS , ans );
    }
    cout << ANS << endl ;
        
    return 0 ;
}


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

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;
const int maxn = 100005;

inline int read() {
    reg int s = 0, ch;
    while (!isdigit(ch = getchar())) ;
    while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s;
}

int n, fa[maxn];
map < pii, int > Map;
set < int > s[maxn];
queue < pii > q;

inline int find(reg int x) { return (fa[x] == x) ? x : (fa[x] = find(fa[x])); }

inline void init(reg int x, reg int y) {
    s[x].insert(y), s[y].insert(x);
    Map[pii(x, y)]++, Map[pii(y, x)]++;
    if (Map[pii(x, y)] == 2) q.push(pii(x, y)); 
}

inline void solve() {
    while (!q.empty()) {
        reg int x = q.front().first, y = q.front().second; q.pop();
        x = find(x), y = find(y), s[x].erase(y), s[y].erase(x);
        if (s[x].size() < s[y].size()) swap(x, y);
        for (auto it : s[y]) {
            Map[pii(it, y)] = Map[pii(y, it)] = 0,
            s[it].erase(y), s[it].insert(x), s[x].insert(it), 
            Map[pii(it, x)]++, Map[pii(x, it)]++;
            if (Map[pii(it, x)] == 2) q.push(pii(it, x));
        }
        fa[y] = x, s[y].clear();
    }
}

int main() {
    ios::sync_with_stdio(false);
    n = read(); reg int u, v;
    for (reg int i = 1; i <= 2 * n - 2; i++) u = read(), v = read(), init(u, v);
    for (reg int i = 1; i <= n; i++) fa[i] = i;
    solve(); reg int ans = 0;
    for (reg int i = 1; i <= n; i++) ans += fa[i] == i;
    if (ans == 1) puts("YES");
    else puts("NO");
    return 0;
}

Measured memory_bytes: 56192
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e12;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	if (n == 1)return x%MOD;
	ll res = sq(mod_pow(x, n / 2));
	res %= MOD;
	if (n % 2 == 1) {
		res *= x;
		res %= MOD;
	}
	return res;
}
ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

int h, w, d;
P pos[200000];
int q;
ll dis[2000000];

int main() {
	cin >> h >> w >> d;
	rep(i, h) {
		rep(j, w) {
			int num;
			cin >> num;
			pos[num] = P(i, j);
		}
	}
	FOR(i, 1, h*w + 1) {
		dis[i + d] = dis[i]
			+ abs(pos[i + d].first - pos[i].first)
			+ abs(pos[i + d].second - pos[i].second);
	}
	cin >> q;
	rep(i, q) {
		int l, r;
		cin >> l >> r;
		cout << dis[r] - dis[l] << endl;
	}
}

Measured memory_bytes: 5888