akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

int A[1000000], n;

int binarySearch(int key){
	int left = 0;
	int right = n;
	int mid;
	
	while(left < right){
		mid = (left + right) / 2;
		if(key == A[mid]) return 1;
		if(key > A[mid]) left = mid + 1;
		else if (key < A[mid]) right = mid;
	}
	return 0;
	
}

int main(void)
{
	int i, q, k, sum = 0;
	
	scanf("%d", &n);
	for(i = 0; i < n; i++)
	{
		scanf("%d", &A[i]);
	}
	
	scanf("%d", &q);
	for(i = 0; i < q; i++)
	{
		scanf("%d", &k);
		if(binarySearch(k)) sum++;
	}
	printf("%d\n", sum);
	
	return 0;
}




Measured memory_bytes: 2116
N, M = map(int, input().split())

par = list(range(N))
rank = [1]*N
size = [1]*N

def find(x):
  if par[x] == x:
    return x
  else:
    return find(par[x])
  
def unite(x,y):
  x = find(x)
  y = find(y)
  
  if x == y:
    return
  if rank[x]<rank[y]:
    x,y = y,x
  par[y] = x
  size[x] += size[y]
  if rank[x]==rank[y]:
    rank[x]+=1
    
for i in range(M):
  a,b = [int(i)-1 for i in input().split()]
  unite(a,b)
  
print(max(size))

Measured memory_bytes: 20024
#include <iostream>
#include <strings.h>
using namespace std;
int main()
{
        int n, count=0;
        cin>>n;
        string s;
        cin>>s;
        int i;
        for (i=0; i<n; i++)
        {
                if (s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C')
                {
                    count++;
                }
        }
        cout<<count<<endl;
        return 0;
}


Measured memory_bytes: 256
#[test]
fn test_solve() {
    assert_eq!(solve("5 3\n3 1 4\n1 5 9\n2 6 5\n3 5 8\n9 7 9\n"), "56\n");
    assert_eq!(
        solve("5 3\n1 -2 3\n-4 5 -6\n7 -8 -9\n-10 11 -12\n13 -14 15\n"),
        "54\n"
    );
    assert_eq!(solve("10 5\n10 -80 21\n23 8 38\n-94 28 11\n-26 -2 18\n-69 72 79\n-26 -86 -54\n-72 -50 59\n21 65 -32\n40 -94 87\n-62 18 82\n"), "638\n");
    assert_eq!(solve("3 2\n2000000000 -9000000000 4000000000\n7000000000 -5000000000 3000000000\n6000000000 -1000000000 8000000000\n"), "30000000000\n");
}

fn solve(src: &str) -> String {
    let mut sc = Scanner::from_str(src);

    let n: usize = sc.read();
    let m: usize = sc.read();
    let xyz: Vec<(isize, isize, isize)> =
        (0..n).map(|_| (sc.read(), sc.read(), sc.read())).collect();
    let ans: isize = (0..8)
        .map(|s| {
            let sx = 1 - 2 * (s & 1);
            let sy = 1 - 2 * ((s & 2) >> 1);
            let sz = 1 - 2 * ((s & 4) >> 2);
            let mut xyz: Vec<_> = xyz
                .clone()
                .iter()
                .map(|&(x, y, z)| x * sx + y * sy + z * sz)
                .collect();
            xyz.sort_by(|a, b| b.cmp(a));
            xyz.iter().take(m).sum()
        })
        .max()
        .unwrap();
    format!("{}\n", ans)
}
fn main() {
    let mut buf = String::new();
    use std::io::{Read, Write};
    std::io::stdin().read_to_string(&mut buf).unwrap();
    std::io::stdout().write_all(solve(&buf).as_bytes()).unwrap();
}
struct Scanner<'a>(std::str::SplitWhitespace<'a>);
impl<'a> Scanner<'a> {
    fn from_str(src: &str) -> Scanner {
        Scanner(src.split_whitespace())
    }
    fn get(&mut self) -> &str {
        self.0.next().unwrap()
    }
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.get().parse().ok().unwrap()
    }
}


Measured memory_bytes: 4352
// /Code by : Harry_Singh/
#include<bits/stdc++.h>
#define int long long
#define io ios_base::sync_with_stdio(false),cin.tie(nullptr);
#define ipair pair<int,int>
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define F(i,n) for(int i=1;i<=n;i++)
#define mod 1000000007
using namespace std;
#define inf 100000000000000009
#define tr cout<<"\n" 
#define N 205
// directions
int xx[5]={0,0,1,-1};
int yy[5]={1,-1,0,0};
vector<int > G[N],L[N];
 
 
void we_have_choices()
{

   string s;
   cin>>s;
   int mx=0,count=0;
   for(int i=0;i<s.length();i++)
   {
    if(s[i]=='R')count++,mx=max(count,mx);
    else count=0;
   }
   cout<<mx;tr;
}



int32_t main()
{
#ifndef ONLINE_JUDGE
 freopen("input.txt","r",stdin);
 freopen("output.txt","w",stdout);
#endif
    io;
    int t=1;
    while (t--)we_have_choices();
    return 0;
}

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

typedef long long ll;
typedef pair<int,int> P;
typedef map<int,int> M;
typedef vector<int> V;
typedef queue<int> Q;
typedef pair<long,long> PLL;
typedef map<long,long> MLL;
typedef vector<long long> VLL;
typedef vector<pair<int,int>> VP;
typedef vector<vector<int>> VV;
#define INF (int)(1e9+1)
#define MAXX (int)1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define MOD (ll)(1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define PRALL(a) a.begin(),a.end(),greater<pair<int,int>>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
//ceil(a/(double)b)=(a+b-1)/b
//printf("myco\n");//for debug
/*--------------------------------------------*/
int main(){
    int n;cin>>n;
    V a(n);rep(i,n)cin>>a[i];
    V l(n),r(n);
    l[0]=a[0];
    r[n-1]=a[n-1];
    for(int i=1;i<n;i++){
        int w1=l[i-1];
        int w2=a[i];
        l[i]=max(w1,w2);
        int w3=r[n-i];
        int w4=a[n-i-1];
        r[n-i-1]=max(w3,w4);
    }
    cout<<r[1]<<endl;
    rep(i,n-1){
        if(i==0)continue;
        else cout<<max(l[i-1],r[i+1])<<endl;
    }
    cout<<l[n-2]<<endl;
}


Measured memory_bytes: 3968
using System;
using System.Collections.Generic;
using System.Linq;
using static Atcoder;
using System.Threading.Tasks;
using System.ComponentModel;

public class Hello
{
    private const int INF = 1000000000;
    public static void Main()
    {
        string S = Console.ReadLine();
        S = StrReverce(S);
        HashSet<string> ss = new HashSet<string>() { "maerd", "remaerd", "esare", "resare" };
        string ls;
        while (S.Length != 0)
        {
            ls = S.Substring(0, 5);
            if (ss.Contains(ls)) { S = S.Substring(5); continue; }
            ls = S.Substring(0, 6);
            if (ss.Contains(ls)) { S = S.Substring(6); continue; }
            ls = S.Substring(0, 7);
            if (ss.Contains(ls)) { S = S.Substring(7); continue; }
            Console.WriteLine("NO");
            return;
        }
        Console.WriteLine("YES");
    }
}

public class Atcoder
{
    static void Swap<T>(ref T a, ref T b)
    {
        var t = a;
        a = b;
        b = t;
    }
    public static int LCM(int a, int b)
    {
        int c = a * b;
        if (a < b) Swap(ref a, ref b);
        int d = a % b;
        while (d != 0)
        {
            a = b;
            b = d;
            d = a % b;
        }
        return c / b;
    }
    public static string StrReverce(string s)
    {
        return new string(s.Reverse().ToArray());
    }
    public static int IntRead()
    {
        return int.Parse(Console.ReadLine());
    }
    public static bool IsPrime(int n)
    {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        //double sqrtNum = Math.Sqrt(n);
        for (int i = 3; i < n; i += 2)
        {
            if (n % i == 0) return false;
        }
        return true;
    }
    public static string[] SpRead(char c)
    {
        return Console.ReadLine().Split(c);
    }
    public static long[] LSRead()
    {
        return Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
    }
}


Measured memory_bytes: 30316
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define INF ((1LL<<62)-(1LL<<31))


ll iti[90010];
ll cost[90010];
ll h,w,d;
int main(){
	scanf("%lld%lld%lld",&h,&w,&d);
	rep(i,0,h)rep(j,0,w){
		ll t;
		scanf("%lld",&t);
		iti[t]=i*1000+j;
	}

	rep(i,d+1,h*w+1){
		cost[i]=cost[i-d]+llabs(iti[i]/1000-iti[i-d]/1000)+llabs(iti[i]%1000-iti[i-d]%1000);
	}
	
	ll q;
	scanf("%lld",&q);
	while(q--){
		ll l,r;
		scanf("%lld%lld",&l,&r);
		printf("%lld\n",cost[r]-cost[l]);
	}
	return 0;
}

Measured memory_bytes: 2432
#include <cstdio>
#include <iostream>
#include <queue>
#define ROP(i,n) for(int i=0;i<n;i++)
#define ROPP(i,n) for(int i=1;i<=n;i++)
#define INF 999999999
using namespace std;
typedef pair<int,int> P;
int N,M,G,gx[10],gy[10];
char MAP[1005][1005];
int DX[4]={1,0,-1,0},DY[4]={0,1,0,-1},FAR[1005][1005];
int BFS(int u){
  queue<P> que;
  ROPP(i,N){ROPP(j,M) FAR[j][i]=INF;}
  que.push(P(gx[u],gy[u]));
  FAR[gx[u]][gy[u]]=0;
  while(que.size()){
    P p=que.front();que.pop();
    if(p.first==gx[u+1]&&p.second==gy[u+1]) break;
    ROP(i,4){
      int nx=p.first+DX[i],ny=p.second+DY[i];
      if(1<=nx&&nx<=M&&1<=ny&&ny<=N
        &&MAP[nx][ny]!='X'&&FAR[nx][ny]==INF){
        que.push(P(nx,ny));
        FAR[nx][ny]=FAR[p.first][p.second]+1;
      }
    }
  }
  return FAR[gx[u+1]][gy[u+1]];
}
void solve(){
  int res=0;
  ROP(i,G){
    res+=BFS(i);
  }
  printf("%d\n",res);
}
int main(){
  scanf("%d %d %d",&N,&M,&G);
  ROPP(i,N){
    ROP(j,M+1){
      scanf("%c",&MAP[j][i]);
      if(MAP[j][i]=='S') gx[0]=j,gy[0]=i;
      ROPP(k,G) {char l='0'+k;
      if(MAP[j][i]==l) gx[k]=j,gy[k]=i;}
    }
  }
  solve();
  return 0;
}

Measured memory_bytes: 8140
#include  <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 1000000007
//vector<vector<int>> vec(縦, vector<int>(横));
#define REP(i,N) for(int i=0;i<N;i++)
int gcd(int a, int b) {
    if(a>b){
        swap(a,b);
        }
    while(b%a!=0){
        b%=a;
        swap(a,b);
    }
    return a;
}


//cout << setprecision(123)<<ans;
//a=atoi(S.c_str());
//S=to_string(a);
int main(){
  int H,W,K,cou1=0,cou2=0,cou3=1,a=0;
  cin>>H>>W>>K;
  vector<vector<char>>V(H,vector<char>(W));
  vector<int>C(H,0);
  vector<vector<int>>ans(H,vector<int>(W));
  
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>V[i][j];
      if(V[i][j]=='#')C[i]++;
    }
  }
  
  for(int i=H-1;i>=0;i--){
    if(C[i]==0){
      cou1++;
      continue;
    }
    pair<int,int>p;
    p.first=i;
    p.second=-1;
    for(int j=0;j<W;j++){
      if(V[i][j]=='#'){
        cou2++;
        if(cou2==C[i]){
          for(int x=p.first;x<=p.first+cou1;x++){
            for(int y=p.second+1;y<W;y++){
              ans[x][y]=cou3;
            }
          }
          cou3++;
          cou2=0;
          continue;
        }
        for(int x=p.first;x<=p.first+cou1;x++){
          for(int y=p.second+1;y<=j;y++){
            ans[x][y]=cou3;
          }
        }
        cou3++;
        p.second=j;
        
    }//ifの終わり
    }//jの更新
    
    
    
    cou2=0;
    cou1=0;
  } // iの更新
  
  for(int i=0;i<H;i++){
    if(C[i]!=0)break;
    a++;
  }
  
  for(int i=a-1;i>=0;i--){
    for(int j=0;j<W;j++){
      ans[i][j]=ans[i+1][j];
    }
  }
  
  
  
  
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cout<<ans[i][j];
      if(j!=W-1)cout<<' ';
      else cout<<endl;
    }
  }
}


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

int main() {
    int h, w;
    while (true) {
        cin >> h >> w;
        if (h == 0 && w == 0) {
            break;
        }

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (i == 0 || i == h-1) {
                    cout << "#";
                } else if (j == 0 || j == w-1) {
                    cout << "#";
                } else {
                    cout << ".";
                }
                
            }
            cout << endl;
        }
        cout << endl;
    }
}


Measured memory_bytes: 3052
#include<iostream>

using namespace std;

int main(){
    int n, T;
    cin >> n >> T;
    int t[n];
    for(int i=0; i<n; i++){
        cin >> t[i];
    }
    int x = T;
    for(int i=1; i<n; i++){
        if(t[i]>=t[i-1]+T){
            x += T;
        }else{
            x += t[i] - t[i-1];
        }
    }
    cout << x << "\n";
}


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

// typedef
// -----------------------------------------------------------------------------
typedef long long ll;
typedef long double ld;

// container util
// -----------------------------------------------------------------------------
#define ALL(c)  (c).begin(),(c).end()
#define SZ(c) ((ll)(c).size())
#define MAX(c) *max_element(ALL(c))
#define MIN(c) *min_element(ALL(c))
#define SORT(c) sort((c).begin(),(c).end())

// repetition
// -----------------------------------------------------------------------------
#define FOR(i, a, b) for(ll i= (a); i < (ll)(b); ++i)
#define REP(i, n) FOR(i, 0, n)

// constant
// -----------------------------------------------------------------------------
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1.0);

// debug
// -----------------------------------------------------------------------------
#define DUMP(x)  cerr << #x << " = " << (x) << endl


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int L, R, d; cin >> L >> R >> d;
    int ans = R / d - (L - 1) / d;
    cout << ans << "\n"; 
}

Measured memory_bytes: 3648
import math

N = int(input())

def keta(n):
    res = 1
    t = n // 10
    while t > 0:
        t //= 10
        res += 1
    return res

ans = 11
n = int(math.sqrt(N))
for i in range(n):
    a = i + 1
    if N % a == 0:
        b = N / a
    ans = min(ans, max(keta(a), keta(b)))
print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;
LL p = 998244353ll;
LL half = (p+1)/2;

int main(void)
{
  LL n, s;
  cin >> n >> s;
  vector<LL> a(n);
  for(auto &x:a) cin >> x;

  vector<LL> dp(s+1, 0ll);
  dp[0]=1;
  REP(i,n) dp[0] = (dp[0]*2)%p;
  REP(i,n) for(LL j=s-a[i];j>=0;--j) {
    dp[j+a[i]] = (dp[j+a[i]] + dp[j] * half) % p;
  }
  cout << dp[s] << endl;
  return 0;
}


Measured memory_bytes: 3676
import java.io.CharArrayReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        boolean flg = true;
        String nn[] = new String[n];
        String mm[] = new String[m];
        for(int i=0;i<n;i++)nn[i]=sc.next();
        for(int i=0;i<m;i++)mm[i]=sc.next();
        for(int x=0;x<=n-m;x++)for(int y=0;y<=n-m;y++){
            flg = true;
            for (int k = 0; k < m; k++){
                if(!mm[k].equals(nn[y+k].substring(x, x+m))){
                    flg = false;
                    break;
                }
            }
            if(flg){
                System.out.println("Yes");
                System.exit(0);
            }

        }
        System.out.println("No");
    }
}


Measured memory_bytes: 35764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
#define down_queue(x) priority_queue<x>
#define up_queue(x) priority_queue<x, vector<x>, greater<x>>
#define vec(x) vector<x>
#define IINF INT_MAX
#define LLINF LLONG_MAX
ll gcd(ll a,ll b){while(b){ll tmp = a % b;a = b;b = tmp;}return a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
#define rep(x, y) for(int x = 0; x < (y); x++)
#define REP(x, z, y) for(int x = (z); x < (y); x++)
#define all(x) x.begin(), x.end()
#define split_str(str, sp_word) istringstream stream(str); string res; for(int cnt = 0; getline(stream,res,sp_word); cnt++)
#define digit(x) ((int)log10((double)(x)) + 1)
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define out(x) for(auto i : x) cout << i << " "; cout << endl;
#define outln(x) for(auto i : x) cout << i << endl;
#define vec_cpy(to,from) copy(all(to),back_inserter(from))
#define ary_cpy(to,from) memcpy(to, from, sizeof from)
#define MOD 1000000007
#ifdef DEBUG
    #define debug_echo(expr) cout << expr;
#else
    #define debug_echo(expr)
#endif

int main(){
  int a,b,c;cin >> a >> b >> c;
  int gcdi = gcd(a,b);
  debug_echo(gcdi << endl);
  cout << ((a / gcdi) * (b / gcdi)) * c << endl;
  return 0;
}

Measured memory_bytes: 3092
import scala.io.StdIn.{readLine,readInt}

object Main extends App {


  def exec(w:String):Unit =  {
    val len = w.length

    def shuffle(i:Int, cnt:Int):String =
      if(i == 0) (w drop (cnt%len))+(w take (cnt%len)) else { val m = readInt;shuffle(i-1, cnt+m) }

    if(w=="-") return else { val n = readInt;println(shuffle(n,0));exec(readLine) }

  }
  exec(readLine)
}

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


int main(){
    int n,k;
    cin >> n >> k;
    int ans = 1;
    rep(i,n){
        if(2*ans>ans+k) ans+=k;
        else ans*=2;
    }
    cout << ans <<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
int menseki[105][105] = {};
int main() {
	int w, h, n;
	cin >> w >> h >> n;
	int x, y, a;
	for (int i = 0; i < n; i++) {
		cin >> x >> y >> a;
		x--; y--;
		if (a == 1) {
			for (int i = 0; i < h; i++) {
				for (int j = 0; j <= x; j++) {
					menseki[i][j] = 1;
				}
			}
		}
		if (a == 2) {
			for (int i = 0; i < h; i++) {
				for (int j = x+1; j < w; j++) {
					menseki[i][j] = 1;
				}
			}
		}
		if (a == 3) {
			for (int i = 0; i <= y; i++) {
				for (int j = 0; j < w; j++) {
					menseki[i][j] = 1;
				}
			}
		}
		if (a == 4) {
			for (int i = y + 1; i < h; i++) {
				for (int j = 0; j < w; j++) {
					menseki[i][j] = 1;
				}
			}
		}
	}
	ll count = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (menseki[i][j] == 0) {
				count++;
			}
		}
	}
	cout << count << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i <(n) ; ++i)
#define PI 3.14159265
#define pb push_back
#define pr pair<int,int>
using namespace std;
using ll = long long;
// using mod = 1000000000 + 7;
void self_max(int &a,int b){
	a = max(a,b);
}

void self_min(int &a,int b){
	a = min(a,b);
}
int main(){
	int w,h,x,y,r; cin >> w >> h >> x >> y >> r;

	bool check1 = false, check2 = false;
	if(x+r <= w && x-r >= 0){
		check1 = true;
	}
	if(y-r >= 0 && y+r <= h){
		check2 = true;
	}

	if(check2 && check1){
		cout<< "Yes" << endl;
	}else
	 	cout<< "No" << endl;

	return 0;
}



Measured memory_bytes: 3128
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> P;
int main(void){
    int n,a[300000],b=1;
    P p[500];
    queue<int> q;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        p[i]=P(x, i+1);
    }
    fill(a, a+n*n+2, 0);
    sort(p, p+n);
    for(int i=0;i<n;i++){
        int x=p[i].first, y=p[i].second;
        for(int j=1;j<y;j++){
            while(b<x&&a[b]>0)b++;
            if(b==x){
                cout<<"No"<<endl;
                return 0;
            }
            a[b]=y;
        }
        a[x]=y;
    }
    int t=0;
    for(int i=1;i<=n*n;i++){
        if(t<n&&i==p[t].first){
            int s=p[t].second;
            for(int j=s;j<n;j++){
                q.push(s);
            }
            t++;
        }
        if(a[i]==0){
            if(q.empty()){
                cout<<"No"<<endl;
                return 0;
            }
            a[i]=q.front();
            q.pop();
        }
    }
    cout<<"Yes"<<endl;
    for(int i=1;i<=n*n;i++){
        cout<<a[i];
        if(i<n*n)cout<<" ";
    }
    cout<<endl;
}


Measured memory_bytes: 2688
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
P = list(map(float,input().split()))
dp = FILL2(0,N+3,N+3)
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        dp[i+1][j+1] += dp[i][j]*P[i]
        dp[i+1][j] += dp[i][j]*(1-P[i])
print(sum(dp[N][N//2+1:]))


Measured memory_bytes: 271460
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String str = in.next();
		int w = in.nextInt();
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<str.length();i=i+w) {
			sb.append(str.charAt(i));
		}
		System.out.println(sb.toString());
	}
}


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

int main(){
  
  int a,b,k;
  cin >> a >> b >> k;
  
  for(int i=0;i<k&&a<=b;i++){
    cout << a << endl;
    a++;
  }
  for(int i=b-k+1;i<=b;i++){
    if(i>=a) cout << i << endl;
  }
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
#include<cassert>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
const long long inf = 1ll << 61;
typedef pair<int, int> P;
int a[200006];
vector<int>A[200006];
signed main() {
	int n, k; cin >> n >> k;
	rep(i, n)cin >> a[i];
	rep(i, n)A[a[i]].push_back(i);
	int ns = 1;
	int now = a[0];
	int nk = 0;
	while (1) {
		auto x = upper_bound(A[now].begin(), A[now].end(),nk );
		if (x == A[now].end()) {
			ns++;
			nk=A[now][0]+1;
			now = a[nk];
		}
		else {
			nk = *x+1;
			now = a[nk];
		}
		if (nk == n)break;
	}
	k %= ns;
	vector<int>ans;
	ns = 1;
	now = a[0];
	nk = 0;
	while (1) {
		auto x = upper_bound(A[now].begin(), A[now].end(), nk);
		if (x == A[now].end()) {
			if (ns == k)break;
			else ns++;
			nk = A[now][0] + 1;
			now = a[nk];
		}
		else {
			nk = *x + 1;
			now = a[nk];
		}
		if (nk == n)break;
	}
	for (int i = nk; i < n; i++) {
		now = a[i];
		auto x = upper_bound(A[now].begin(), A[now].end(), i);
		if (x == A[now].end()) {
			ans.push_back(now);
		}
		else {
			i = *x;
		}
	}
	rep(i, ans.size()) {
		if (i)cout << ' ';
		cout << ans[i];
	}cout << endl;
}

Measured memory_bytes: 15732
#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define abs(x) (((x)<0)?(-(x)):(x))

using namespace std;

int H,W;
bool B[400][400];
bool checked[400][400];

void func(int i, int j, int *a, int *b){
    if(checked[i][j]==true){ return; }
    checked[i][j]=true;
    if((i+j)%2==0){
        (*a)++;
    }
    else{
        (*b)++;
    }
    if(i-1>=0 && B[i][j] == B[i-1][j]){ func(i-1,j,a,b); }
    if(j-1>=0 && B[i][j] == B[i][j-1]){ func(i,j-1,a,b); }
    if(i+1<H && B[i][j] == B[i+1][j]){ func(i+1,j,a,b); }
    if(j+1<W && B[i][j] == B[i][j+1]){ func(i,j+1,a,b); }
}
int main(){
    long count = 0;
    cin >> H >> W;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            char c; cin >> c;
            if(c=='#'){
                B[i][j] = ((i+j)%2==0);
            }
            if(c=='.'){
                B[i][j] = ((i+j)%2!=0);
            }
            checked[i][j]=false;
        }
    }
    
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(checked[i][j]){ continue; }
            int a=0,b=0;
            func(i,j, &a, &b);
            count += (long)a*(long)b;
        }
    }
    cout << count;
    return 0;
}


Measured memory_bytes: 13056
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		String[] d = new String[k];
		Arrays.setAll(d, i -> sc.next());
		
		int pay = n;
		outer:
		for (; pay < n * 100; pay++) {
			String s = String.valueOf(pay);
			for (int i = 0; i < k; i++) {
				if (s.contains(d[i])) continue outer;
			}
			break;
		}
		
		System.out.println(pay);
			
		sc.close();
	}
}



Measured memory_bytes: 36864
n,k=map(int,input().split())
d=list(input().split())
for i in range(n,100000):
    num=list(str(i))
    num1=0
    for j in range(len(num)):
        if num[j] in d:
            num1=1
            break
    if num1==0:
        print(i)
        break


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

int main() {
    int L;
    cin >> L;
    cout << fixed << setprecision(12);
    double x, y, z;
    //if (L%3 == 0) x = y = z = L/3;
    //else if (L%3 == 1) {
    //	x = z = L/3;
    //	y = (L+2)/3;
    //} else {
    //	x = z = (L+1)/3;
    //	y = L/3;
    //}
    x = y = z = L/(double)3;
    double ans;
    ans = x*y*z;
    cout << ans << endl;
    return 0;
}


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

int main(){
	int x[10000],y[10000];
	int i=0;
	while(1){
		cin >>x[i]>>y[i];
		if(x[i]==0&&y[i]==0) break;
		i++;
	}
	i=0;
	while(1){
		if(x[i]==0&&y[i]==0) break;
		if(x[i]>y[i]) swap(x[i],y[i]);
		cout<<x[i]<<" "<<y[i]<<endl;
		i++;
	}
	return 0;
}

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

int     main() {
        long N, K;
        cin >>N >>K;
        vector<vector<int>> a(N, vector<int> (2, 0));
        for (int i=0; i<N; i++)
                cin >> a.at(i).at(0) >>a.at(i).at(1);
        sort(a.begin(), a.end());
        int j=0;
        long S=0;
        while (S<K) {
                S += a.at(j).at(1);
                j++;
        }
        j--;
        cout <<a.at(j).at(0) <<endl;
        return 0;
};

Measured memory_bytes: 5760
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1e9 + 7;
typedef long long lint;
#define int lint
const int INF = 1e7;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repi(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(), (x).end()
#define pb push_back
int n;
int dfs(string s)
{
    int res = 0;
    if (s == "")
    {
        res += dfs(s + '3');
        res += dfs(s + '5');
        res += dfs(s + '7');
    }
    else if (stoll(s) <= n)
    {
        if (s.find('3') != string::npos && s.find('5') != string::npos && s.find('7') != string::npos)
        {
            res++;
        }
        res += dfs(s + '3');
        res += dfs(s + '5');
        res += dfs(s + '7');
    }
    return res;
}

signed main()
{
    cin >> n;
    cout << dfs("") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <queue>
#include <utility>
#include <string>
using namespace std;
typedef long long ll;
int main(){
  int N,K;
  cin >> N >> K;
  string s;
  cin >> s;

  int score = 0;
  for(int i = 0;i < N - 1;i++)
    if(s[i] == s[i+1])score++;

  int ans = min(score+2*K,N-1);

  cout << ans << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include "bits/stdc++.h"

using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i, a, b) for(ll i=a;i<b;i++)
#define REP(i, a) for(ll i=0;i<a;i++)
#define jkl ll debug = 0;
#define RREP(i, a) for(ll i=a;i>0;i--)
#define rrep(i, a, b) for(ll i=a-1;i>=b;i--)
#define printall(n, array) {for(ll i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
#define mp make_pair
typedef long long ll;
typedef pair<ll, ll> Pi;
typedef pair<ll, Pi> V;
typedef vector<ll> VE;
typedef vector<vector<ll>> VVE;
const ll mod = 1e9 + 7; //10^9+7

int main() {
    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    VE a(x), b(y), c(z);
    REP(i, x) cin >> a[i];
    REP(i, y) cin >> b[i];
    REP(i, z) cin >> c[i];
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
    sort(c.rbegin(), c.rend());
    ll abSize = x * y;
    VE ab(abSize);
    REP(i, x) {
        REP(j, y) {
            ab.push_back(a[i] + b[j]);
        }
    }
    sort(ab.rbegin(), ab.rend());
    ll abcSize = k * z;
    VE abc(abcSize);
    REP(i, k) {
        REP(j, z) {
            abc.push_back(ab[i] + c[j]);
        }
    }
    sort(abc.rbegin(), abc.rend());
    REP(i, k) {
        print(abc[i]);
    }
}

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

using namespace std;

int main()
{
    vector<int> v;

    int a, b, c;
    cin >> a >> b >> c;

    int ans = max({a, b, c});
    int res = (3 * ans) - a - b - c;
    
    if (res % 2 != 0)
        res += 3;

    cout << res / 2 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <ctime>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <sstream>
#pragma comment(linker, "/STACK:256000000")
using namespace std;

#define in(s) freopen(s, "r", stdin)
#define out(s) freopen(s, "w", stdout)
#define forn(i, n) for (int i = 0; i < n; i++)
#define endl '\n'
#define mp make_pair

typedef long long ll;
typedef long double ld;

int main()
{
	//in("input.txt");
	//out("output.txt");
	srand(1373737);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	string a = "", b = "";

	forn(i, n)
		a += to_string(m);
	forn(i, m)
		b += to_string(n);

	cout << min(a, b);

	return 0;
}

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

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define rep(i, n, m) for (int (i) = (n); (i) < (m); ++(i))
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define debugB(x, y) cerr<<#x<<": "<<bitset<y>(x) << endl;
#define line() cerr << "---------------" << endl;

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

bool v(string s) {
   if (s == "Vacant") return true;
   else return false;
}

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

   int left = 0, right = n;
   int mid = (left+right)/2;
   string l, m;
   cout << left << endl;
   cin >> l;
   if (v(l)) return 0;
   cout << mid << endl;
   cin >> m;
   if (v(m)) return 0;

   rep (i, 0, 18) {
      // 矛盾の判定
      int dist = mid - left;
      bool ok;
      if (dist&1) {
         if (l != m) ok = true;
         else ok = false;
      } else {
         if (l == m) ok = true;
         else ok = false;
      }

      if (ok) { // 矛盾無し
         left = mid;
         l = m;
         mid = (left + right) / 2;
         cout << mid << endl;
         cin >> m;
         if (v(m)) return 0;
      } else { // 矛盾有り
         right = mid;
         mid = (left + right) / 2;
         cout << mid << endl;
         cin >> m;
         if (v(m)) return 0;
      }
   }

   return 0;
}

Measured memory_bytes: 852
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
//using System.Text;
//using System.Text.RegularExpressions;
//using System.Globalization;
//using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;
//using pair = Pair<int, int>;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;
    void chmax<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? b : a; }
    void chmin<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? a : b; }

    void solve()
    {
        int N = cin.nextint;
        int K = cin.nextint;
        var A = cin.scanint;
        int id = -1;
        for (int i = 0; i < N; i++)
        {
            if (A[i] == 1) id = i;
        }
        int l = id;
        int r = N - (l + 1);

        int p = l % (K - 1);
        int q = r % (K - 1);


        int sum = l / (K - 1);
        int now = sum * (K - 1);
        now += K;
        int add = 0;
        if (N - now > 0)add = (N - now + K - 2) / (K - 1);
        WriteLine(sum + 1 + add);

    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 16864
#include<stdio.h>
int main(void){
	int a[7],b[7],c[7],i;
	for(i=0;i<7;i++){
		scanf("%d %d",&a[i],&b[i]);
	}
	for(i=0;i<7;i++){
		c[i]=a[i]-b[i];
	}
	for(i=0;i<7;i++){
		printf("%d\n",c[i]);
	}
	return 0;
}


Measured memory_bytes: 2052
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S seconnd
#define int ll
#define PB push_back


int f(int k,int m){
  int res=0;
  int r = m;
  while(r%k==0){
    res++;
    r/=k;
  }
  return res;
}


int mod_inv(int x){
  int res=1,k=x,t=M-2;
  while(t>0){
    if(t&1){
      res*=k;
      res%=M;
    }
    k*=k;
    k%=M;
    t/=2;
  }
  return res;
}


int comb(int n,int k){
  int res=1,t=1;

  rep(i,k){
    res*=(n-i);
    res%=M;
    t*=(i+1);
    t%=M;
  }

  res*=mod_inv(t);
  res%=M;
  
  return res;
}


signed main(){
  int n,m;
  map<int,int> mp;

  cin>>n>>m;
  int mn = sqrt(m)+1;
  FOR(i,2,mn){
    while(m%i==0){
      m/=i;
      mp[i]++;
    }
  }

  if(m!=1) mp[m]++;

  int ans = 1;

  for(auto i=mp.begin();i!=mp.end();i++){
    int a = i->second;
    ans*=comb(a+n-1,a);
    ans%=M;
  }

  cout<<ans<<endl;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int, input().split()))
b=[0]*n
for i in range(n,0,-1):
    count=0
    for j in range(i,n+1,i):
        count+=b[j-1]
    if (count%2)!=a[i-1]:      
        b[i-1]=1
c=[i+1 for i in range(n) if b[i]==1]
if len(c)==0:
    print("0")
else:
    print(len(c))
    print(*c)

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

int main(){
  int A,B,C,D,num;
  cin >> num;
  D = num % 10; num /= 10;
  C = num % 10; num /= 10;
  B = num % 10; num /= 10;
  A = num % 10;

  if(A + B + C + D == 7) cout <<A<<'+'<<B<<'+'<<C<<'+'<<D<<"=7" << endl;
  else if(A + B + C - D == 7) cout <<A<<'+'<<B<<'+'<<C<<'-'<<D<<"=7" << endl;
  else if(A + B - C + D == 7) cout <<A<<'+'<<B<<'-'<<C<<'+'<<D<<"=7" << endl;
  else if(A + B - C - D == 7) cout <<A<<'+'<<B<<'-'<<C<<'-'<<D<<"=7" << endl;
  else if(A - B + C + D == 7) cout <<A<<'-'<<B<<'+'<<C<<'+'<<D<<"=7" << endl;
  else if(A - B + C - D == 7) cout <<A<<'-'<<B<<'+'<<C<<'-'<<D<<"=7" << endl;
  else if(A - B - C + D == 7) cout <<A<<'-'<<B<<'-'<<C<<'+'<<D<<"=7" << endl;
  else if(A - B - C - D == 7) cout <<A<<'-'<<B<<'-'<<C<<'-'<<D<<"=7" << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int pp[300005];
main()
{
	int t,p;
	scanf("%d%d",&t,&p);
	if(t==2)
	{
		if(p==2)
		{
			printf("Yes\n");
			printf("1\n2\n3");
		}
		else
		printf("No");
	}
	else
	{
		if(p<=1 || p>=2*t-1)
		printf("No");
		else
		{
			int cou=0;
			printf("Yes\n");
			if(p==2)
			{
				pp[2*t-1]=1;
				pp[1]=1;
				pp[2]=1;
				pp[4]=1;
				for(int i = 1;i <= 2*t-1 && cou<=t-4;i++)
				{
					if(pp[i]==0)
					{
						pp[i]=1;
						printf("%d\n",i);
						cou++;
					}
				}
				printf("%d\n%d\n%d\n%d\n",2*t-1,1,2,4);
				
				for(int i = 1;i <= 2*t-1;i++)
				{
					if(pp[i]==0)
					printf("%d\n",i);
				}
			}
			else if(p==2*t-2)
			{
				
				pp[2*t-1]=1;
				pp[2]=1;
				pp[2*t-2]=1;
				pp[1]=1;
				for(int i = 1;i <= 2*t-1 && cou<=t-4;i++)
				{
					if(pp[i]==0)
					{
						pp[i]=1;
						printf("%d\n",i);
						cou++;
					}
				}
				printf("%d\n%d\n%d\n%d\n",2,2*t-1,2*t-2,1);
				for(int i = 1;i <= 2*t-1;i++)
				{
					if(pp[i]==0)
					{
						pp[i]=1;
						printf("%d\n",i);
						cou++;
					}
				}
			}
			else
			{
				
				pp[p-1]=1;
				pp[p]=1;
				pp[p+1]=1;
				pp[p-2]=1;
				for(int i = 1;i <= 2*t-1 && cou<=t-4;i++)
				{
					if(pp[i]==0)
					{
						pp[i]=1;
						printf("%d\n",i);
						cou++;
					}
				}
				printf("%d\n%d\n%d\n%d\n",p-1,p,p+1,p-2);
				for(int i = 1;i <= 2*t-1;i++)
				{
					if(pp[i]==0)
					printf("%d\n",i);
				}
			}
		}
	}
	
}
/*
3-3;
   
   1
  111
 
7124356


   1
  111
 
4765

 331
23415
*/

Measured memory_bytes: 2304
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

typedef struct pointindex{
  int val;
  int index,next;
} node;

int cmp(const void *a,const void *b){
  node *p=(node *)a;
  node *q=(node *)b;
  return p->val-q->val;
}

int root(int x,int *u){
  if(x==u[x]) return x;
  u[x]=root(u[x],u);
  return u[x];
}

int same(int x,int y,int *u){
  return root(x,u)==root(y,u);
}

void merge(int x,int y,int *u){
  x=root(x,u);
  y=root(y,u);
  if(x==y) return;
  u[x]=y;
  return;
}

void run(void){
  int n;
  scanf("%d",&n);
  node *sortX=(node *)malloc(sizeof(node)*n);
  node *sortY=(node *)malloc(sizeof(node)*n);
  int i;
  for(i=0;i<n;i++){
    int x,y;
    scanf("%d%d",&x,&y);
    sortX[i].val=x;
    sortY[i].val=y;
    sortX[i].index=sortY[i].index=i;
  }
  qsort(sortX,n,sizeof(node),cmp);
  qsort(sortY,n,sizeof(node),cmp);
  for(i=0;i<n-1;i++){
    sortX[i].val=sortX[i+1].val-sortX[i].val;
    sortX[i].next=sortX[i+1].index;
    sortY[i].val=sortY[i+1].val-sortY[i].val;
    sortY[i].next=sortY[i+1].index;
  }
  qsort(sortX,n-1,sizeof(node),cmp);
  qsort(sortY,n-1,sizeof(node),cmp);
  int *u=(int *)malloc(sizeof(int)*n);
  for(i=0;i<n;i++) u[i]=i;

  int xIndex=0;
  int yIndex=0;
  int64 cost=0;
  int cnt=0;
  while(cnt<n-1){
    if(sortX[xIndex].val<=sortY[yIndex].val){
      int a=sortX[xIndex].index;
      int b=sortX[xIndex].next;
      if(!same(a,b,u)){
	merge(a,b,u);
	cost+=sortX[xIndex].val;
	cnt++;
      }
      xIndex++;
    } else {
      int a=sortY[yIndex].index;
      int b=sortY[yIndex].next;
      if(!same(a,b,u)){
	merge(a,b,u);
	cost+=sortY[yIndex].val;
	cnt++;
      }
      yIndex++;
    }
  }
  printf("%lld\n",cost);
}

int main(void){
  run();
  return 0;
}


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


int binary_search(vector<int> &a, int key) {
    // Meguru type binary search
    int ok = -1;
    int ng = a.size();

    auto is_ok = [&] (int idx) {
        if (a[idx] < key) {
            return true;
        } else {
            return false;
        }
    };

    int mid;
    while (abs(ok - ng) > 1) {
        mid = (ok + ng) / 2;
        if (is_ok(mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}


int main() {
    int N;
    cin >> N;
    vector<int> L(N);
    rep(i, N) cin >> L[i];

    sort(L.begin(), L.end());

    ll ans = 0;
    for (int a = 0; a < N - 2; a++) {
        for (int b = a + 1; b < N - 1; b++) {
            // c < a + b
            int c = binary_search(L, L[a] + L[b]);
            ans += c - b;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3616
import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int X = Integer.parseInt(sc.next());
        int A = Integer.parseInt(sc.next());
        int B = Integer.parseInt(sc.next());
        sc.close();

        int remain = X - A;
        remain %= B;
        out.printf("%d\n", remain);
        out.flush();
    }
}


Measured memory_bytes: 23124
n = int(input())
l = list(map(int,input().split()))
ans = 0

for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            if l[i] != l[j] and l[i] != l[k] and l[j] != l[k]:
                if abs(l[i]-l[j]) < l[k] < l[i] + l[j]:
                    ans += 1
print(ans)

Measured memory_bytes: 9196
n = int(input())
j = [0]*4

for i in range(n):
    s = input()
    if s == 'AC':
        j[0] += 1
    elif s == 'WA':
        j[1] += 1
    elif s == 'TLE':
        j[2] += 1
    else:
        j[3] += 1

print('AC x', j[0])
print('WA x', j[1])
print('TLE x', j[2])
print('RE x', j[3])

Measured memory_bytes: 9216
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

const int dm = 1 << 21;
char dn[dm], * di = dn;
inline void putkotae(int X, int Y) {
	char C[12];
	rep(i, 6) {
		*(C + i) = '0' + Y % 10;
		Y /= 10;
	}
	rep(i, 6) {
		*(C + i + 6) = '0' + X % 10;
		X /= 10;
	}
	for (int i = 11; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}

ll tmp[100001];
void pakuri_sort(int N, ll A[]) {
	const int b = 8;
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}

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


	int N = getint(), M = getint();
	int P[100000], PK[100001] = {};
	ll S[100000];
	rep(i, M) {
		P[i] = getint();
		S[i] = ((ll)i << 32) + getint();
	}
	pakuri_sort(M, S);

	rep(i, M) {
		int j = S[i] >> 32;
		tmp[j] = ++PK[P[j]];
	}
	rep(i, M) putkotae(P[i], tmp[i]);

	fwrite_unlocked(dn, di - dn, 1, stdout);

	Would you please return 0;
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define FOR(i,l,r) for(i=l;i<r;i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define P pair<ll,ll>
#define F first
#define S second
signed main(){
  ll N,i;cin>>N;ll A[N];
  REP(i,N)cin>>A[i];sort(A,A+N);
  if((A[0]==0&&A[N-1]==0)||(N%3==0&&A[0]==A[N/3-1]&&A[N/3]==A[2*N/3-1]&&A[2*N/3]==A[N-1]&&((A[0]^A[N/3])^A[2*N/3])==0))cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>

int search(int s[],int n,int t)
{
  int lef=0,rig=n,mid;

  while(lef<rig){
    mid=(lef+rig)/2;
    if(s[mid]==t) return 1;
    
    if(s[mid]>t){
      rig=mid;
    }else{
      lef=mid+1;
    }
  }
  return 0;
  
}
  

int main(){

  int i,n,s[100001],q,t,count=0,flag;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&s[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&t);
    flag=search(s,n,t);
    if(flag==1){
      count++;
      flag=0;
    }
  }

  printf("%d\n",count);
  
  return 0;
}



Measured memory_bytes: 2108
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
using namespace std;
#define     loop(n,i,a)     for(ll i=a;i<n;i++)
#define     loopR(n,i,a)    for(ll i=n-1;i>=a;i--)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     pii             pair<ll,ll>
#define     vi              vector<int>
#define     vll             vector<ll>
#define		vii 			vector<pair<ll,ll>>
#define     sz(x)           (int)x.size()
#define     pb              push_back
#define     endl            "\n"
#define     Endl            "\n"
#define     f               first
#define     s               second
#define     mem(dp,n)       memset(dp,n,sizeof dp)
#define     test(i)        cout<<i<<endl
int dx[] = {-1 , 1 , 0 , 0 ,-1 ,-1 , 1 , 1 };
int dy[] = { 0 , 0 , 1 ,-1 ,-1 , 1 ,-1 , 1 };
void fast(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int mxN=2e5+5,oo=0x3f3f3f3f,mod=1e9+7;
int n,k;
int arr[mxN][3],dp[mxN][3];
int go(int idx,int pre=0){
    if(idx==n)
        return 0;
    int &ret=dp[idx][pre];
    if(~ret)
        return ret;
    ret=0;
    if(idx==0){
        loop(3,i,0)
            ret=max(go(idx+1,i)+arr[idx][i],ret);
    }
    else{
        loop(3,i,0)
            if(i!=pre)
                ret=max(go(idx+1,i)+arr[idx][i],ret);
    }
    return ret;
}
void solve(){
    cin>>n;
    loop(n,i,0)
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    mem(dp,-1);
    cout<<go(0)<<endl;
}
int main() {
    fast();
    solve();
}

Measured memory_bytes: 10624
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        double r = sc.nextDouble();
        
        double menseki = r * r * 3.141592653589;
        double enshu = 2 * r * 3.141592653589;
        
        System.out.printf("%f %f", menseki, enshu);
    }
}



Measured memory_bytes: 28404
#include<stdio.h>
int abs(int x,int y){
  if(x>y){
    return x-y;
  }else{
    return y-x;
  }
}

int main(){
  int x,a,b;
  scanf("%d %d %d",&x,&a,&b);

  if(abs(b,x)>abs(a,x)){
    printf("A\n");
  }else{
    printf("B\n");
  }


  return 0;

}


Measured memory_bytes: 128