akhauriyash/Code-Regression huggingface dataset:
#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 rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

vector<vector<int> > edge(10);

int main() {
  int N, M;
  cin>>N>>M;
  int a, b;
  for(int i=0;i<M;++i) {
    cin>>a>>b;
    a--;
    b--;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  vector<int> node;
  for(int i=0;i<N;++i) node.push_back(i);
  int ans = 0;
  bool can, tmp;
  do {
    if(node[0]!=0) can = false;
    else can = true;
    for(int i=0;i<N-1;++i) {
      tmp = false;
      for(int j=0;j<edge[node[i]].size();++j) {
        if(edge[node[i]][j]==node[i+1]) tmp = true;
      }
      can = min(can, tmp);
    }
    if(can) {
      ans++;
    }
  }while(next_permutation(node.begin(), node.end()));
  cout<<ans<<endl;
}



Measured memory_bytes: 3628
// Copyright 2020 yaito3014
#include "bits/stdc++.h"
using namespace std;

int main() {
  cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false);
  int N;
  cin >> N;
  int n = N / 100 % 10;
  if (N > n * 100 + n * 10 + n)++n;
  cout << (n * 100 + n * 10 + n) << endl;
}


Measured memory_bytes: 256
N = int(input())
A_list = list(map(int, input().split()))
A_dict = {}
res = 0
for a in A_list:
    res += a
    if a in A_dict.keys():
        A_dict[a] += 1
    else:
        A_dict[a] = 1

Q = int(input())
for i in range(Q):
    b,c = map(int, input().split())
    tmp = A_dict[b] if b in A_dict.keys() else 0
    A_dict[b] = 0

    if c in A_dict.keys():
        A_dict[c] += tmp
    else:
        A_dict[c] = tmp

    res += c*tmp - b*tmp
    print(res)

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

#define int long long

#define x first
#define y second
#define pb push_back
#define mp make_pair

#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()

const int M = 1e9 + 7;

int pw(int a, int n) {
    int b = 1;
    while (n > 0) {
        if (n & 1) {
            b = b * a % M;
            n--;
        } else {
            a = a * a % M;
            n /= 2;
        }
    }
    return b;
}

int inv(int x) {
    return pw(x, M - 2);
}

int C(int n, int k) {
    if (k > n) return 0;
    int x = 1;
    for (int i = n; i >= n - k + 1; i--) x = x * i % M;
    for (int i = 1; i <= k; i++) x = x * inv(i) % M;
    return x;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, a, b;
    cin >> n >> a >> b;
    int ans = pw(2, n) - 1;
    if (ans < 0) ans += M;
    ans -= C(n, a);
    if (ans < 0) ans += M;
    ans -= C(n, b);
    if (ans < 0) ans += M;
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rrep(i, n) for(ll i = n - 1; i > -1; i--)
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second
template <class X> void print(X x) { cout << x << endl; }
void print(vl x) {
    for(ll i : x) {
        cout << i << " ";
    }
    cout << endl;
}
const ll INF = (1LL << 61) - 1;
const ll MOD = 1000000007 /*998244353*/;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, h, x, y, z, p, q, n, t, r, k, w, l, ans, i, j, u, v, m;
ll codeforces = 1;
string S, T;
vl A, B;
void input() {
    cin>>x;
}
void solve() {
    if(x>29)print("Yes");
    else print("No");
 }
int main() {
    // cout<<fixed<<setprecision(15);
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    while(codeforces--) {
        solve();
    }
}

Measured memory_bytes: 3652
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        int h;
        int max = 0;
        boolean can = true;
        
        for(int i = 0; i < n; i++){
            h = sc.nextInt();
            if(h <= (max-2)){
                can = false;
                break;
            }else if(h > max){
                max = h;
            }
        }
        
        if(can){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 48748
macro_rules! bind_from_vec {
    ( $($variable:ident),+ = $vector:expr ) => {
        let mut v = $vector.clone().into_iter();
        $(let $variable = v.next().unwrap();)+
    };
}
macro_rules! read_line {
    () => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).unwrap();
        input
    }};
}
pub fn read_to_vec<T: std::str::FromStr>() -> Vec<T> {
    read_line!().split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    bind_from_vec!(bottom, top = read_to_vec::<u64>());
    let mut mem = Vec::new();


    for i in 1..(top.next_power_of_two().trailing_zeros() + 2) {
        let modulo = 1 << i;
        mem.push((
            top / modulo * (modulo / 2)
                + (top % modulo).saturating_sub(modulo / 2 - 1),
            bottom.saturating_sub(1) / modulo * (modulo / 2)
                + (bottom.saturating_sub(1) % modulo).saturating_sub(modulo / 2 - 1)
        ));
    }

    let mut ans = 0;

    for tuple in mem.iter().rev() {
        ans <<= 1;
        ans += (tuple.0 - tuple.1) % 2
    }

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


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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define spa << " " <<
#define MP make_pair
ll MOD = 1e9+7;
//ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a, ll b) { if (a > b) a = b; }
void chmax(ll &a, ll b) { if (a < b) a = b; }
void answer1(bool x){
  if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void answer2(bool x){
  if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void answer3(bool x){
  if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void answer(bool x, ll y, ll z){
  if(x) cout<<y<<endl;else cout<<z<<endl;}   


int main(){
  ll i, j;
  //ll n;
  //cin >> n;
  ll a, b, c;
  cin >> a >> b >> c;
  //string s; cin >> s;
  ll result = 0;
  bool judge = true;
  answer2(c>=a&&c<=a+b);

  /*
  vector<ll> a(n);
  for(i=0;i<n;i++)
    cin >> a[i];
  //for(i=0;<n;i++)
  */





  return 0;
}

Measured memory_bytes: 256
#pragma warning(disable:4996)
#include "bits/stdc++.h"
using namespace std;

//macro
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,a,b) for(int i=(int)(b) - 1;i>=(int)(a);i--)
#define rrep(i,n) RREP(i,0,n)
#define each(i, ctn) for (auto &&i : (ctn))
#define all(a) (a).begin(),(a).end()
#define mp make_pair
#define INF 114514810
#define INFL 1145148100000000000LL
#define EPS (1e-8)
#define MOD 1000000007
#define PI 3.141592653589793
#define equals(a,b)(fabs((a)-(b))<EPS)

//alias
using ll = long long;
using ull = unsigned long long;
using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vs = vector<string>;
using P = pair<ll, ll>;
template<class T> using heap = priority_queue<T>;
template<class T> using minheap = priority_queue<T, vector<T>, greater<T>>;

//func
template<typename A, typename T>void assign2d(A&arr, ll H, ll W, T t) { arr.resize(H);	rep(i, H) arr[i].assign(W, t); }
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { int n = v.size(); rep(i, n)os << v[i] << (i == n - 1 ? "" : " "); return os; }
template <class T = int> inline T in() { T x; cin >> x; return x; }
template<class T> inline void print(const T &x) { cout << x << '\n'; }
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } pre__;

class UnionFind {
private:
	vi a;
public:
	UnionFind(int n) : a(n, -1) {}
	int root(int x) { return a[x] < 0 ? x : (a[x] = root(a[x])); }
	bool same(int x, int y) { return root(x) == root(y); }
	bool same(P& p) { return same(p.first, p.second); }
	bool unite(int x, int y) {
		x = root(x), y = root(y);
		if (x == y) return false;
		if (a[x] > a[y]) swap(x, y);
		a[x] += a[y]; a[y] = x;
		return true;
	}
	bool unite(P& p) { return unite(p.first, p.second); }
	int grupNum() { return count_if(all(a), [](int i) { return i < 0; }); }
	bool isConnected() { return size(0) != a.size(); }
	int size(int x) { return -a[root(x)]; }
};

int main() {
	int N, M;
	cin >> N >> M;
	vi A(M), B(M);
	rep(m, M) {
		A[m] = in(); A[m]--;
		B[m] = in(); B[m]--;
	}

	int ans = 0;
	rep(i, M) {
		UnionFind uf(N);
		rep(j, M) {
			if (i == j)continue;
			uf.unite(A[j], B[j]);
		}
		if (uf.isConnected())ans++;
	}

	print(ans);

	return 0;
}

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

int N;

int check(vector<int> v){
  int num=0;
  bool three=false, five=false, seven=false;
  for(auto it=v.begin();it!=v.end();it++){
    num = num*10+*it;
    if(*it==3) three=true;
    if(*it==5) five=true;
    if(*it==7) seven=true;

  }
  if(three&&five&&seven&&num<=N) {
    //    cout << num << ":" << 1 << endl;                                      
    return 1;
  }
  else {
    //    cout << num << ":" << 0 << endl;                                      
    return 0;
  }
}

int dfs(int depth, vector<int> v, int maxd){
  if(depth==maxd) return check(v);
  else {
    int ret=0;
    v.push_back(3);
    ret +=dfs(depth+1, v, maxd);

    v.pop_back();
    v.push_back(5);
    ret +=dfs(depth+1, v, maxd);

    v.pop_back();
    v.push_back(7);
    ret +=dfs(depth+1, v, maxd);
    return ret;
  }
}

int main()
{
  int res=0;
  cin >> N;

  int num=N;
  int d=0;
  while(num>0){
    num/=10;
    d++;
  }
  if(d<=2) {
    cout << 0 << endl;
    return 0;
  }

  vector<int> vv;
  for(int i=3;i<=d;i++){
    res += dfs(0,vv,i);
  }

  cout << res << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		String s = scan.next();
		int x = 0;
		String[] str = new String[n];
		int[] result = new int[n];
		int max = 0;
		
		for(int i = 0; i < n; i++) {
			str[i] = s.substring(i, i + 1);
			if(str[i].equals("I")) {
				x += 1;
			}else {
				x -= 1;
			}
			result[i] += x;
			if(max < result[i]){
				max = result[i];
			}
		}
		System.out.println(max);
	}

}

Measured memory_bytes: 25556
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
vector<int> v[100010];
int vis[100010];
int sum[100010];
int ans[100010];
int pos=1;
int cnt=0;
void dfs(int x){
	vis[x]=pos;
	cnt++;
	for(int i=0;i<v[x].size();i++){
		if(!vis[v[x][i]]){
			dfs(v[x][i]);
		}
	}
}
int main(){
	cin>>n>>m>>k;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			cnt=0;
			dfs(i);
			sum[pos]=cnt;
			pos++;
		}
	}
	for(int i=1;i<=n;i++){
		ans[i]=sum[vis[i]]-v[i].size()-1;
	}
	for(int i=0;i<k;i++){
		int a,b;
		cin>>a>>b;
		if(vis[a]==vis[b]){
			ans[a]--;
			ans[b]--;
		}
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}

Measured memory_bytes: 7552
#include<bits/stdc++.h>
using namespace std;
int ans=0;
int main() {
	string s;
	cin>>s;
	for(int i=1; i<=s.length()-1; i++) {
		if(s[i]!=s[i-1]) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

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

int main() {
  
  int X=0, A=0;
  
  cin >> X >> A;
  
  if(X < A) {
    
    cout << "0" << endl;
    
  } else if(A <= X) {
    
    cout << "10" << endl;
    
  }
  
  return 0;
  
}

Measured memory_bytes: 256
#include<cstdio>
#define maxn 100005
#define LL long long
int n,m,V,E,cnt[3],col[maxn];
bool vis[maxn],vise[maxn],fg;
LL ans;
struct node { int v,w,i; node *nxt; } edge[maxn*2],*head[maxn],*ncnt;
void addedge(int u,int v,int w,int i)
{
	ncnt++;
	ncnt->v=v,ncnt->w=w,ncnt->nxt=head[u],ncnt->i=i;
	head[u]=ncnt;
}
void dfs(int u)
{
	V++; vis[u]=true;
	cnt[col[u]]++;
	for(node *p=head[u];p;p=p->nxt)
	{
		if(vise[p->i/2]) continue;
		vise[p->i/2]=true,E++;
		int v=p->v;
		if(!vis[v]) { col[v]=(col[u]+p->w+3)%3; dfs(v); }
		else if((col[u]+p->w+3)%3!=col[v]) fg=true;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	ncnt=&edge[0];
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		addedge(x,y,1,i*2); addedge(y,x,-1,i*2+1);
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])
		{
			V=E=cnt[0]=cnt[1]=cnt[2]=fg=0;
			dfs(i);
			if(fg) ans+=1ll*V*V;
			else if(!cnt[0]||!cnt[1]||!cnt[2]) ans+=1ll*E;
			else ans+=1ll*cnt[0]*cnt[1]+1ll*cnt[1]*cnt[2]+1ll*cnt[0]*cnt[2];
		}
	printf("%lld\n",ans);
}

Measured memory_bytes: 9344
//文字列を使うとスマート
#include <iostream>
#include <string>
using namespace std;

int main()
{
	string s;
	int i = 1;
	bool good = true;
	cin >> s;
	while (i<=3)
	{
		if (s[i] == s[i - 1])good = false;
		i++;
	}
	/*
	if (good)cout << "Good";
	else cout << "Bad";
	*/
	//こんな書き方もできた
	cout << (good ? "Good" : "Bad");
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#define INF 1000000
using namespace std;
int main(){
	int i,j,k,l,n,a[60],b[60],c[60];
	int edge[60][60];
	int dist[60][60];
	long long ans=0;
	cin >> n;
	for(i=0;i<n;i++){
		cin >> a[i];
	}
	for(i=0;i<n;i++){
		cin >> b[i];
	}
	for(i=0;i<n;i++){
		if(2*b[i]>=a[i] && a[i]!=b[i]){
			cout << -1 << endl;
			return 0;
		}
	}
	
	for(i=0;i<=50;i++){
		c[i] = 0;
		for(j=0;j<=50;j++){
			dist[i][j] = INF;
			edge[i][j] = 0;
		}
	}
	
	for(i=1;i<=50;i++){
		for(k=1;k<=50;k++){
			j = i%k;
			edge[i][j]++;
		}
	}
	
	for(k=50;k>=1;k--){
		
		for(i=0;i<=50;i++){
			for(j=0;j<=50;j++){
				dist[i][j] = INF;
				if(i==j){
					dist[i][j] = 0;
				}
			}
		}
		
		for(i=1;i<=50;i++){
			j = i%k;
			edge[i][j]--;
		}
		
		for(i=0;i<=50;i++){
			for(j=0;j<=50;j++){
				for(l=0;l<=50;l++){
					if(edge[i][l]!=0 && edge[l][j]!=0){
						dist[i][j] = min(dist[i][j],edge[i][l]+edge[l][j]);
					}
				}
			}
		}
		
		for(i=0;i<n;i++){
			if(dist[a[i]][b[i]]==INF && edge[a[i]][b[i]]==0){
				for(j=1;j<=50;j++){
					l = j%k;
					edge[j][l]++;
				}
				c[k] = 1;
				break;
			}
		}
	}
	
	for(i=1;i<=50;i++){
		if(c[i]){
			ans += pow(2,i);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define FOR(i, N) for (long i = 0; i < (N); i++)

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

    vector<int> A(N);
    FOR(i, N) {
        cin >> A[i];
    }

    long stock = 0;
    long money = 1000;
    for (int i = 0; i < N - 1; i++) {
        if (A[i] < A[i + 1]) {
            stock += ((money - (money % A[i])) / A[i]);
            money = (money % A[i]);
        } else if (A[i] > A[i + 1]) {
            money += stock * A[i];
            stock = 0;
        }
    }

    money += stock * A[N - 1];

    cout << money << endl;

    return 0;
}


Measured memory_bytes: 3640
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
	string a,b;
	cin>>a>>b;
	int c=stoi(a+b);
	for(int i=0;i<1000;i++){
		if(i*i==c){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	
	cout<<"No"<<endl;
	
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
std::vector<std::vector<int>> vec;
std::vector<int> invec;
int x1,x2;
std::vector<int> rvec(std::vector<int> vector){
	return vector;
}
int n=1;
int main(){
	while(1){
		std::cin>>x1>>x2;
		invec.push_back(x1);
		invec.push_back(x2);
		sort(invec.begin(),invec.end());
		if(invec==rvec({0,0})){
			break;
		}else {
			vec.push_back(invec);
			invec.erase(invec.begin(),invec.end());
		}
	}
	for(auto i:vec){
		std::cout<<*i.begin()<<" "<<*(i.end()-1)<<std::endl;
	}
	return 0;
}

Measured memory_bytes: 1324
def main():
    N = int(input())
    CARD = tuple(input().split())

    sort_ = []
    for i in range(1, 10):
        for s in CARD:
            if str(i) in s:
                sort_.append(s)

    sort_ = tuple(sort_)
    bsort = tuple(bubbleSort(list(CARD), N))
    ssort = tuple(selectionSort(list(CARD), N))

    for s in (bsort, ssort):
        print(*s, sep=' ')
        if s == sort_:
            print('Stable')
        else:
            print('Not stable')

def bubbleSort(c, n):
    flag = 1
    while flag:
        flag = 0
        for i in range(1, n):
            if c[i][1] < c[i-1][1]:
                c[i], c[i-1] = c[i-1], c[i]
                flag = 1
    return c

def selectionSort(c, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if c[j][1] < c[minj][1]:
                minj = j
        c[i], c[minj] = c[minj], c[i]
    return c

main()

Measured memory_bytes: 7744
// SPDX-License-Identifier: Apache-2.0
// Copyright (C) 2020 Bjarni Dagur Thor Karason

#include <bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for (__typeof(a) i=(a); i<(b); i++)
#define MP make_pair
#define PB push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define INF 1000000000
#define PI 3.14159265359

int n, m;
int h[100010];
vi adj[100010];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].PB(b);
        adj[b].PB(a);
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        bool good = true;
        for (auto u : adj[i]) {
            if (h[u] >= h[i]) good = false;
        }
        if (good) ans++;
    }
    cout << ans << endl;

    return 0;
}


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

int main(){
    long long n;
    cin >> n;
    long long a[n+1], b[n];
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if ( a[i] <= b[i] ) {
            ans += a[i];
            b[i] -= a[i];
            a[i] = 0;
            if ( a[i+1] >= b[i] ) {
                ans += b[i];
                a[i+1] -= b[i];
                b[i] = 0;
            } else {
                ans += a[i+1];
                b[i] -= a[i+1];
                a[i+1] = 0;
            }
        } else {
            ans += b[i];
            a[i] -= b[i];
            b[i] = 0;
        }

        if ( i == n-1 ) {
            if ( a[n] > b[i] ) {
                ans += b[i];
            } else {
                ans += a[n];
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<stdio.h>

int main(){
  int cards[4][13],num,n,m,i,j;
  char mark;

  for(i=0;i<4;i++)
    for(j=0;j<13;j++)
      cards[i][j]=-1;

  scanf("%d",&n);

  for(i=0;i<n*2;i++){
    scanf("%c",&mark);
    scanf("%d",&num);
    if(mark == 'S')cards[0][num-1]=0;
    else if(mark == 'H')cards[1][num-1]=0;
    else if(mark == 'C')cards[2][num-1]=0;
    else if(mark == 'D')cards[3][num-1]=0;
  }

  for(i=0;i<4;i++)
    for(j=0;j<13;j++){
      if(cards[i][j]==-1){
	if(i==0)printf("S %d\n",j+1);
	else if(i==1)printf("H %d\n",j+1);
	else if(i==2)printf("C %d\n",j+1);
	else if(i==3)printf("D %d\n",j+1);
      }
    }

  return 0;
}

Measured memory_bytes: 1024
N, K, Q = map(int, input().split())
A = [int(i) for i in input().split()]

def solve() :
    if Q == 1 : return 0
        
    ret = float('inf')
    for i in range(N) :
        l = -1
        for j in range(i, max(-1, i - K), -1) :
            if A[j] < A[i] :
                l = j
                break
        r = N      
        for j in range(i, min(N, i + K)) :
            if A[j] < A[i] :
                r = j
                break
                
        if r - l - 1 < K :
            continue
            
        B = A[::]
        B.pop(i)
        
        C = [-1]
        for j in range(N - 1) :
            if B[j] < A[i] :
                C.append(j)
        C.append(N - 1)
        
        D = []
        for j in range(len(C) - 1) :
            if C[j+1] - C[j] >= K :
                D += sorted(B[C[j]+1:C[j+1]])[:C[j+1] - C[j] - K]
        
        if len(D) >= Q - 1 :
            D.sort()
            ret = min(ret, D[Q-2] - A[i])

    return ret
    
print(solve())


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

#define fo1(i, n) for (int i = 0; i < n; i++)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int((x).size())
using ll = long long; using vi = vector<int>; using ii = pair<int,int>;
const int oo = 0x3f3f3f3f; const ll OO = ll(oo)*oo;
#ifndef DEBUG
#define endl '\n'
#define debugf(...)
#define debug(...)
#else
#define debugf(...) printf(__VA_ARGS__)
#define debug(...) __VA_ARGS__
#endif
const int N = 100005;

int C[N];
int PC[N];
int in[N];

vector<ii> g[N];

void dfs(int u, int p) {
    int c = 1;
    for (auto& e : g[u]) {
        // auto [i, v] = e;
        int i, v;
        tie(i, v) = e;
        if (v != p) {
            if (c == PC[u]) c++;
            C[i] = c;
            PC[v] = c;
            c++;
            dfs(v, u);
        }
    }
}

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

    int n;
    cin >> n;

    int k = 0;
    fo1(i, n-1) {
        int u, v;
        cin >> u >> v;
        in[u]++; in[v]++;
        k = max({ k, in[u], in[v] });
        g[u].emplace_back(i, v);
        g[v].emplace_back(i, u);
    }

    dfs(1, 0);

    cout << k << endl;

    fo1(i, n-1)
        cout << C[i] << endl;

    return 0;
}

Measured memory_bytes: 8832
using System;
using System.Linq;

namespace aizu
{
    class OnlineJudge
    {
        static void Main()
        {
            string input;
            while((input = Console.ReadLine()) != "0 0") {
                int[] count = input.Split().Select(p => int.Parse(p)).ToArray();
                Player current, first;
                current = first = new Player { Index = 1 };
                for(int i=0; i < count[0] - 1; ++i) {
                    current.Next = new Player();
                    current.Next.Index = current.Index + 1;
                    current = current.Next;
                }
                current.Next = first;
                while(current != current.Next) {
                    for(int i=0; i < count[1] - 1; ++i) {
                        current = current.Next;
                    }
                    current.Next = current.Next.Next;
                }
                Console.WriteLine(current.Index);
            }
        }
    }
    class Player
    {
        public Player Next { get; set; }
        public int Index { get; set; }
    }
}

Measured memory_bytes: 6000
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	N := readint()
	S := readstr()
	ans := 0
	for i := 0; i < N-2; i++ {
		//fmt.Println(S[i : i+3])
		if S[i:i+3] == "ABC" {
			ans++
		}
	}
	fmt.Println(ans)
}

const (
	iobufsize = 1 * 1024 * 1024 // 1 MB
)

var stdinsc = func() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, iobufsize), iobufsize)
	sc.Split(bufio.ScanWords)
	return sc
}()

func readint() int {
	stdinsc.Scan()
	v, err := strconv.Atoi(stdinsc.Text())
	if err != nil {
		panic(err)
	}
	return v
}

func readstr() string {
	stdinsc.Scan()
	return stdinsc.Text()
}

func pow(x, y int) int {
	if y < 1 {
		return 1
	}
	return x * pow(x, y-1)
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()

const string YES = "Yes";
const string NO = "No";

int main(){
    string s;
    cin >> s;
    if(s.substr(0, 4) == "YAKI"){
        cout << YES << endl;
    }else{
        cout << NO << endl;
    }
    return 0;
}


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

int main(void){
  
 	int r, g, b;
   	cin >> r >> g >> b;
  
    if((r*100+g*10+b)%4 == 0) cout << "YES" << endl;
    else cout <<  "NO" << endl;
      
  	return 0;
}



Measured memory_bytes: 256
// AtCoder Grand Contest 017
// B - Moderate Differences

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;


int N;
ll A, B, C, D;


bool can() {
    for (int k = 0; 2 * k <= N; k++) {
        if ((-(N - 2 * k - 1) * D - k * (D - C) <= A - B && A - B <= -(N - 2 * k - 1) * C + k * (D - C)) ||
                ((N - 2 * k - 1) * C - k * (D - C) <= A - B && A - B <= (N - 2 * k - 1) * D + k * (D - C))) {
            return true;
        }
    }
    return false;
}

int main() {

    cin >> N;
    cin >> A >> B >> C >> D;

    cout << (can() ? "YES" : "NO") << endl;

    return 0;

}





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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

double dp[3000][3000];

void Main() {
    int N;
    cin >> N;
    vector<double> P(N);
    rep(i, N) cin >> P[i];

    dp[0][0] = 1;
    rep(i, N) {
        double p = P[i];
        rrep(j, N - 1, 0) {
            dp[i + 1][j + 1] = dp[i][j] * p + dp[i][j + 1] * (1 - p);
            dp[i + 1][j] = dp[i][j] * (1 - p) + dp[i + 1][j] * p;
        }
    }
    double ans = 0;
    rep(i, N + 1) {
        if (i > N - i) {
            ans += dp[N][i];
        }
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 70528
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using i64 = int64_t;
using f80 = __float80;
static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(i64 i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(i64 i=(start);i>end;--i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef v(i64) vi;
typedef v(vi) vvi;
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;}
template<typename T> ostream &operator<<(ostream &os, const vector< T > &v){
  rep(i,v.size()) os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template<typename T> istream &operator>>(istream &is, vector< T > &v){
  for(T &in : v) is >> in;
  return is;
}

void Main()
{
  i64 A, B;
  cin >> A >> B;
  if((A-B)%2==0){
    cout << (A+B)/2 << "\n";
  }else{
    cout << "IMPOSSIBLE\n";
  }

}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int> >;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define rrep(i,m,n) for(int i = m; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define mp make_pair
#define sum accumulate
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
typedef long long ll;
const int INF = 2000000000;
const ll INF64 = 1000000000000000ll;
const ll MOD = 1000000007LL;
typedef unsigned int uint;
int main(){
    int n,m;
    std::cin >> n>>m;
    if(n==m)std::cout << "Yes" << std::endl;
    else std::cout <<  "No" << std::endl;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <numeric>
#include <algorithm>
#include <utility>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;


int gcd(int a, int b) {
    while (b != 0) {
        auto na = a % b;
        a = b;
        b = na;
    }
    return a;
}


void oneCase() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& el : a) {
        cin >> el;
    }
    sort(a.begin(), a.end());
    cout << accumulate(a.begin() + n - k, a.end(), 0) << "\n";
}


int main() {
    int t = 1;
//    cin >> t;
    while (t--) {
       oneCase();
    }

    return 0;
}

ll fact(ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        res = (res * n) % mod;
        --n;
    }
    return res;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <boost/math/common_factor_rt.hpp>
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
// namespace mp = boost::multiprecision;
// namespace mt = boost::math
// using Bint = mp::cpp_int;
typedef long long ll;
typedef pair<int, int> P;

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

int main() {
    int n;
    cin >> n;
    int h[n];
    bool flag = true, only = true;
    rep(i, n) {
        cin >> h[i];
        if (i == 0)
            h[0]--;
        if (i > 1) {
            if (h[i - 1] > h[i - 2]) {
                h[i - 1]--;
            }
        }
    }
    rep(i, n) {
        if (i > 0) {
            if (h[i] < h[i - 1])
                flag = false;
        }
    }
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


Measured memory_bytes: 640
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws Exception {
		Scanner scan=new Scanner(System.in);
		List<String>list=new ArrayList<String>();
		String st=scan.next();
		for(;;) {
			String str=scan.next();
			if(str.equals("END_OF_TEXT")) {
				break;
			}
			list.add(str.toLowerCase());
		}
		int c=0;
		for(int i=0;i<list.size();i++) {
			String s=list.get(i);
			if(st.equals(s)) {
				c++;
			}
		}
		System.out.println(c);
	}
}


Measured memory_bytes: 26304
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
typedef long long int LL;
LL t[200005];
map<LL,int> m1;
int main(){
	int i,j,k;
	LL a,b,c;
	LL s=0;
	int n;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>a;
		t[i+1]=t[i]+a;
	}
	for(i=0;i<=n;i++){
		s+=m1[t[i]];
		m1[t[i]]++;
	}
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 14336
#include <iostream>
using namespace std;
int main(void){
    int N; cin>>N;
    int k2=0,k4=0;
    int a;
    for(int i=0;i<N;i++){
        cin>>a;
        if(a%4==0){
            k4++;
        }else if(a%2==0){
            k2++;
        }
    }
    if(k4+k2/2>=N/2){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    
}


Measured memory_bytes: 768
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
int n,m,i,j,k,dp[5005][5005],num[5005],ans,l,r,mid,pre[5005];
//vector<int> can[5005];
bool check(int x)
{
	if (x<=0) return 1;
	if (x>n) return 0;
	int i;
	for (i=0;i<m;i++)
	{
		if (dp[n-x][i]&&i+pre[n]-pre[n-x]>=m)
		{
			return 0;
		}
	}
	return 1;
}
int main()
{
	cin>>n>>m;
	for (i=1;i<=n;i++)
	{
		cin>>num[i];
		if (num[i]>=m)
		{
			i--;
			n--;
		}
	}
	/*dp[0][0][0]=1;
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=m;j++) dp[i][j][0]=dp[i-1][j][0];
		for (j=num[i];j<=m;j++)
		{
			dp[i][j][0]=dp[i][j][0]||dp[i-1][j-num[i]][0];
		}
	}
	dp[n+1][0][1]=1;
	for (i=n;i>=1;i--)
	{
		for (j=1;j<=m;j++) dp[i][j][1]=dp[i+1][j][1];
		for (j=num[i];j<=m;j++)
		{
			dp[i][j][1]=dp[i][j][1]||dp[i+1][j-num[i]][1];
		}
		//for (j=1;j<=m;j++) if (dp[i][j][1]) can[i].push_back(j);
	}
	bool ok;
	for (i=1;i<=n;i++)
	{
		ok=0;
		for (j=1;j<=m;j++)
		{
			if (!dp[i-1][j][0]) continue;
			for (k=m-num[i]-j;k<=m-j;k++)
			{
				if (!dp[i+1][k][1]) continue;
				if (j+k<m&&j+k+num[i]>=m)
				{
					ok=1;
					break;
				}
			}
			if (ok) break;
		}
		ans+=!ok;
	}*/
	sort(num+1,num+n+1);
	reverse(num+1,num+n+1);
	for (i=1;i<=n;i++) pre[i]=pre[i-1]+num[i];
	dp[0][0]=1;
	for (i=1;i<=n;i++)
	{
		for (j=0;j<=m;j++) dp[i][j]=dp[i-1][j];
		for (j=num[i];j<=m;j++)
		{
			dp[i][j]=dp[i][j]||dp[i-1][j-num[i]];
		}
	}
	l=-1;r=n+1;
	while (l<r)
	{
		mid=(l+r)/2;
		if (check(mid))
		{
			ans=mid;
			l=mid+1;
		}
		else r=mid;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 98048
from collections import Counter
n = int(input())
ns = list(map(int, input().split()))
c = Counter(ns)
ans = 0

l = [True] * (max(ns)+1)
for i in sorted(set(ns)):
    if l[i]:
        j = i*2
        while j < len(l):
            l[j] = False
            j += i

a = set([key for key, value in c.items() if value == 1])
for i in a:
    if l[i]:
        ans += 1
print(ans)



Measured memory_bytes: 158548
/*
 * atcoder/abc159/c.cpp
 */

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>
#include <cstring>

#define ll long long
#define ld long double
#define Int ll
#define loop(__x, __start, __end) for(Int __x = __start; __x < __end; __x++)
#define loopdown(__x, __start, __end) for(Int __x = __start; __x > __end; __x--)
#define rep(__n) for(Int __x = 0; __x < __n; __x++)
#define span(__a,__x,__y) __a.begin()+__x,__a.begin()+__y
#define span_all(__a) __a.begin(),__a.end()
#define len(__x) (__x.size())
#define last(__x) (__x[__x.size()-1])

using namespace std;

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


struct Point {
  Int x, y;
  Point(Int x, Int y): x(x), y(y) {}
  Point(): x(0), y(0) {}

  Point operator + (Point v) { return Point(x + v.x, y + v.y); }
  Point operator - (Point v) { return Point(x - v.x, y - v.y); }
  bool operator == (const Point &v) const {
    return x == v.x && y == v.y;
  }
  bool operator< (const Point &p1) const {
    return x < p1.x && y < p1.y;
  }
};
ostream & operator << (ostream & out, Point const & v) {
  out << "Point(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Point & v) {
  Int x, y;
  in >> x; in >> y; v.x = x; v.y = y;
  return in;
}

// Geometry

#define EPS 0.000001

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (Vector2 v) { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (Vector2 v) { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (double k) { return Vector2(x * k, y * k); }
  Vector2 operator / (double k) { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 v) { return x * v.x + y * v.y; }
  double cross (Vector2 v) { return x * v.y - y * v.x; }
  
  bool operator < (const Vector2 &v) const {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) const {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) { 
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) { 
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}


vector<Int> slice(vector<Int> &vec, int s, int t) {
  return vector<Int>(vec.begin()+s, vec.begin()+t);
}

vector<Int> trim(vector<Int> &vec, int n) {
  auto init = slice(vec, 0, n);
  auto tail = slice(vec, n+2, vec.size());
  init.insert(init.end(), tail.begin(), tail.end());
  return init;
}


ld L;

void input() {
  cin >> L;
}

void solve() {
  ld x = L / 3.0;
  cout << x * x * x << endl;
}

int main() {
  cout.precision(15);
  input();
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    int N; cin >> N;
    vector<LLONG> As(N); for (auto &Ai : As) cin >> Ai;
    // 一般に x xor y <= x + y
    // よって条件を満たす区間では部分空間も条件を満たす→尺取法
    LLONG ans = 0;
    int r = 0;
    LLONG sum = 0;
    for (int l = 0; l < N; ++l)
    {
        while (r < N && (sum ^ As[r]) == (sum + As[r]))
        {
            sum += As[r];
            ++r;
        }
        ans += r - l;
        if (l == r)
        {
            ++r;
        }
        else
        {
            sum -= As[l];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include<stdio.h>
#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, M[N][N];
int color[N], d[N], f[N], tt;

void dfs_visit(int u){
  int v;
  color[u] = GRAY;
  d[u] = ++tt;
  for(v = 0 ; v < n ; v++){
    if(M[u][v] == 0) continue;
    if(color[v] == WHITE){
      dfs_visit(v);
    }
  }
  color[u] = BLACK;
  f[u] = ++tt;
}

void dfs(){
  int u;
  for(u = 0 ; u < n ; u++) color[u] = WHITE;
  tt = 0;

  for(u = 0 ; u < n ; u++){
    if(color[u] == WHITE) dfs_visit(u);
  }
  for(u = 0 ; u < n ; u++){
    printf("%d %d %d\n",u + 1, d[u], f[u]);
  }
}

int main(){
  int u, v, k, i, j;

  scanf("%d",&n);
  for(i = 0 ; i < n ; i++){
    for(j = 0 ; j < n ; j++) M[i][j] = 0;
  }

  for(i = 0 ; i < n ; i++){
    scanf("%d%d",&u,&k);
    u--;
    for(j = 0 ; j < k ; j++){
      scanf("%d",&v);
      v--;
      M[u][v] = 1;
    }
  }

  dfs();

  return 0;
}

Measured memory_bytes: 632
#define _CRT_SECURE_NO_WARNINGS
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<random>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())




vector<tuple<int, int, int>> s[2][100000];
int N;
int x[100000];
int L, Q;
int ans[100000];
int dist[100000];

int bs;


void solve(int dir) {
	rep(i, N - 1) {
		int nxt = upper_bound(x, x + N, x[i] + L) - 1 - x;
		if (s[dir][i].size() < bs) {
			for (const auto &t : s[dir][i]) {
				int b, j, cost;
				tie(b, j, cost) = t;
				if (nxt >= b) {
					ans[j] = cost + 1;
				}
				else {
					s[dir][nxt].emplace_back(b, j, cost + 1);
				}
			}
		}
		else {
			int c = 1, d = 0;
			dist[i] = 0;
			for (int j = i + 1; j < N; j++) {
				d += x[j] - x[j - 1];
				if (d > L) {
					d = x[j] - x[j - 1];
					c++;
				}
				dist[j] = c;
			}
			for (const auto &t : s[dir][i]) {
				int b, j, cost;
				tie(b, j, cost) = t;
				ans[j] = cost + dist[b];
			}
		}
		{
			vector<tuple<int, int, int>> a;
			s[dir][i].swap(a);
		}
	}
}





int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	rep(i, N)cin >> x[i];
	cin >> L >> Q;
	bs = sqrt(Q);
	rep(i, Q) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		if (a < b) {
			s[0][a].emplace_back(b, i, 0);
		}
		else {
			a = N - a - 1;
			b = N - b - 1;
			s[1][a].emplace_back(b, i, 0);
		}
	}
	solve(0);
	reverse(x, x + N);
	rep(i, N)x[i] *= -1;
	solve(1);
	rep(i, Q)cout << ans[i] << endl;

	return 0;
}

Measured memory_bytes: 9524
#ifndef DEBUG
#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i <= i##_len; ++i)
#define rep3(i, l, r) for (int i = l, i##_len = (r); i < i##_len; ++i)
#define REP3(i, l, r) for (int i = l, i##_len = (r); i <= i##_len; ++i)
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
typedef int64_t Int;
typedef long double Ld;

using namespace std;
template <class T>
using Graph = vector<vector<T>>;

const Ld pi = M_PI;
const Int MOD = 1000000007;
const Int INF = 1LL << 62;

Int Floor(Int a, Int b) {
    return (a - (a % b)) / b;
}

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

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

template <typename T>
inline T Gcd(T a, T b) {
    T c;
    while (b) {
        c = b;
        b = a % b;
        a = c;
    }
    return a;
}

Int Lcm(Int a, Int b) {
    if (a < b) {
        swap(a, b);
    }

    return a / Gcd(a, b) * b;
}

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

    int n, m;
    cin >> n >> m;
    Graph<int> G(n);
    vector<bool> seen(n, false);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;

        G[a].push_back(b);
        G[b].push_back(a);
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (seen[i]) {
            continue;
        }

        int tsize = 1;
        queue<int> que;
        que.push(i);
        seen[i] = true;
        while (!que.empty()) {
            int v = que.front();
            que.pop();

            for (auto nv : G[v]) {
                if (!seen[nv]) {
                    que.push(nv);
                    seen[nv] = true;
                    tsize++;
                }
            }
        }

        chmax(ans, tsize);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 14900
#include <iostream>

using namespace std;

typedef long long ll;

int main(int argc, char *argv[])
{
	int N, B[200];
	int A[200];
	ll ans = 0;

	cin >> N;

	for (int i = 0; i < N - 1; i++) {
		cin >> B[i];
	}
	
	A[N - 1] = B[N - 2];
	A[0] = B[0];
	for (int i = N - 2; i >= 1; i--) {
		if (B[i - 1] <= B[i]) {
			A[i] = B[i - 1];
			A[i - 1] = B[i - 1];
		} else {
			A[i] = B[i];
			A[i - 1] = B[i - 1];
		}
	}

	for (int i = 0; i < N; i++) {
		ans += A[i];
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<string.h>
using namespace std;
#define pb push_back
#define all(v) v. begin(),v. end()
#define  rep(i,n,v) for(i=n;i<v;i++)
#define per(i,n,v) for(i=n;i>v;i--)
#define ff first 
#define ss second 
#define pp pair<ll,ll>
#define ll  long long
#define endl '\n'
void solve()
{
  ll n, a,m=0,b=1, c,k=0, i, j,l=1e9+7;
  string s, r, y;
  cin>>s;
  if(s=="SUN") cout<<7;
  else if(s=="MON") cout<<6;
  else if(s=="TUE") cout<<5;
  else if(s=="WED") cout<<4;
  else if(s=="THU") cout<<3;
  else if(s=="FRI") cout<<2;
  else cout<<1;
}
int main()
{
 ios_base::sync_with_stdio(false);
  cin. tie(0);cout. tie(0);
    ll t=1;
 //  cin>>t;
    while(t--)
    {
      solve();
    }
    return 0;
}

Measured memory_bytes: 3556
#include "iostream"
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <math.h>
#include <cctype>
#include <stack>
#include <vector>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <bitset>
using namespace std;
using ll=long long;
#define MOD  1000000007

int main(int argc, char const *argv[]) {
  int n,k;
  std::cin >> n >> k;
  unsigned long long ans=k;
  if(n==1) std::cout << k << '\n';

  else{
  for(int i=1; i<n; i++){
    ans*=(k-1);
  }
  std::cout << ans << '\n';
}
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
typedef unsigned long long ull;
typedef long double ldouble;
const ll INF=1e18;

vector<int> cost(1000000);
vector<vector<int>> data(1000000);

// 10進数を1桁ずつに分割して、配列にして返す
vector<int> divide(string str){
    vector<int> divide(str.length());
    for(int i = 0; i < str.length(); i++){
        divide.at(i) = str.at(i) - '0';
    }
    return divide;
}

int main(){
    string n;
    cin >> n;
    vector<int> divided = divide(n);
    
    // {0, 1, ..., n-1} の部分集合の全探索
    for (int bit = 0; bit < (1<<3); ++bit)
    {
        /* bit で表される集合の処理を書く */
        bitset<3> tmp(bit);
        int answer = divided.at(0);
        /* bit で表される集合の処理を書く */
        for(int i = 0; i < 3; i++){
            if(tmp.test(i)) {
                answer += divided.at(i+1);
            }
            else {
                answer -= divided.at(i+1);
            }
        }

        if(answer == 7) {
            for(int i = 0; i < 3; i++){
                cout << divided.at(i);
                if(tmp.test(i)) cout << '+';
                else cout << '-';
            }
            cout << divided.at(3) << "=7" << endl;
            break;
        }
    }
}

Measured memory_bytes: 30524
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

int compare(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int main(void)
{
    int N;
    int i;
    int *v;
    double value = 0;

    scanf("%d", &N);
    v = (int *)calloc(N, sizeof(int));

    for (i = 0; i < N; i++)
    {
        scanf("%d", v + i);
    }

    qsort(v, N, sizeof(int), compare);

    value = (double)(v[0]);

    for (i = 1; i < N; i++)
    {
        value = (value + (double)(v[i])) / 2.0;
    }

    printf("%f\n", value);

    free(v);
    return 0;
}

Measured memory_bytes: 128
if __name__ == '__main__':
    H, W = map(int, input().split())
    S = [list(input()) for i in range(H)]

    SS = [[0 for i in range(W+2)] for j in range(H+2)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                # pass
                SS[i+1][j+1] = 1

    answer = S.copy()

    for i in range(H):
        for j in range(W):
            if answer[i][j] ==  '.':
                answer[i][j] = str(SS[i][j] + SS[i+1][j] + SS[i+2][j] + SS[i][j+1] + SS[i+2][j+1] + SS[i][j+2] + SS[i+1][j+2] + SS[i+2][j+2])

    for i in range(H):
        print("".join(answer[i]))


Measured memory_bytes: 3188