akhauriyash/Code-Regression huggingface dataset:
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
struct FenwickTree {
    seq: Vec<i64>,
}
#[allow(dead_code)]
impl FenwickTree {
    fn new(n: usize) -> FenwickTree {
        FenwickTree { seq: vec![0; n + 2] }
    }
    fn add(&mut self, index: usize, value: i64) {
        let mut index = (index + 1) as i32;
        while (index as usize) < self.seq.len() {
            self.seq[index as usize] += value;
            index += index & -index;
        }
    }
    // inclusive
    fn sum(&self, index: usize) -> i64 {
        let mut ret = 0;
        let mut index = (index + 1) as i32;
        while index > 0 {
            ret += self.seq[index as usize];
            index -= index & -index;
        }
        ret
    }
}

struct Solver {
    s: Vec<char>,
}

impl Solver {
    fn new() -> Solver {
        Solver { s: read::<String>().chars().collect::<Vec<char>>(), }
    }
    fn solve(&mut self) {
        let s: &Vec<char> = &self.s;
        let n = s.len();
        let mut indexs = vec![vec![]; 200];
        for i in 0..n {
            indexs[s[i] as usize].push(i);
        }
        let odd_cnt = indexs.iter().filter(|vs| vs.len() != 0 && vs.len() % 2 == 1).count();
        if odd_cnt > 1 {
            println!("-1");
            return;
        }
        let mut dests = vec![None; n];
        let mut srcs = vec![None; n];
        let mut ans = 0;
        let mut mid = None;
        for index in indexs.iter() {
            for i in 0..index.len() / 2 {
                let revi = index.len() - i - 1;
                dests[index[i]] = Some(index[revi]);
                srcs[index[revi]] = Some(index[i]);
            }
            if index.len() % 2 == 1 {
                mid = Some(index[index.len() / 2]);
            }
        }   
        let mut starts = FenwickTree::new(n);
        let mut ends = FenwickTree::new(n);
        for pos in 0..n {
            if let Some(src) = srcs[pos] {
                starts.add(src, -1);
                let inner = (ends.sum(pos) - ends.sum(src)) as usize;
                let mut intersect = (pos - src - 1) - inner * 2;
                if let Some(mid) = mid {
                    if mid < src || pos < mid {
                        ans += 2;
                    } else {
                        intersect -= 1;
                    }
                }
                let over = starts.sum(src) as usize;
                let outer = n / 2 - 1 - inner - intersect - over;
                ans += intersect + outer * 2;
                ends.add(src, 1);
            }
            if let Some(_) = dests[pos] {
                starts.add(pos, 1);
            }
        }
        println!("{}", ans / 2);
    }
}

fn main() {
    let mut solver = Solver::new();
    solver.solve();
}

Measured memory_bytes: 22292
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;

int main()
{
    int N, A;
    cin >> N >> A;
    int rem = N % 500;

    if (rem <= A) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

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

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int t;
  while (cin >> t, t) {
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) {
      int s, f;
      cin >> s >> f;
      sum += f - s;
    }
    if (sum >= t) cout << "OK" << endl;
    else cout << t - sum << endl;
  }

  return 0;
}


Measured memory_bytes: 3120
use std::io::Read;

pub fn read_stdin() -> String {
    let mut s = String::new();
    ::std::io::stdin().read_to_string(&mut s).unwrap();
    s
}

pub trait Parse {
    fn to<T>(&mut self) -> T
    where
        T: std::str::FromStr;
}

impl<'a> Parse for std::str::SplitWhitespace<'a> {
    fn to<T>(&mut self) -> T
    where
        T: std::str::FromStr,
    {
        let word = self.next().unwrap();
        word.parse().ok().unwrap()
    }
}

fn main() {
    let source = read_stdin();
    let mut iter = source.split_whitespace();
    let n = iter.to();
    let k = iter.to();
    let mut v: Vec<i32> = (0..n).map(|_| iter.to()).collect();
    v.sort();
    let min = v.windows(k)
        .map(|w| w.last().unwrap() - w[0])
        .min()
        .unwrap();

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

Measured memory_bytes: 6396
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=500000;
char s[maxn+5];
int n;
int a[maxn+5],v[maxn+5];
signed main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	s[0]='>';
	s[n+1]='<';
	for(int i=1;i<=n+1;i++) 
	{
		if(s[i-1]=='>'&&s[i]=='<') v[i]=-1;
		if(s[i-1]=='<'&&s[i]=='>') v[i]=1;
	}
	int flag=0;
	for(int i=1;i<=n+1;i++)
	{
		if(v[i]==-1) flag=1;
		else if(!flag) continue;
		else
		{
			if(v[i]==1) flag=0;
			a[i]=max(a[i],a[i-1]+1);
		} 
	}
	flag=0;
	for(int i=n+1;i>=1;i--)
	{
		if(v[i]==-1) flag=1;
		else if(!flag) continue;
		else
		{
			if(v[i]==1) flag=0;
			a[i]=max(a[i],a[i+1]+1);
		} 		
	}
	int sum=0;
	for(int i=1;i<=n+1;i++) sum+=a[i];
	printf("%lld\n",sum);
	return 0;
}

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

int main() {
  ll n, a, b;
  cin >> n >> a >> b;

  if (a > b) {
    cout << 0 << endl;
    return 0;
  }
  if (a != b && n == 1) {
    cout << 0 << endl;
    return 0;
  }

  ll min = b + a * (n - 1);
  ll max = a + b * (n - 1);
  ll ans = max - min + 1;

  cout << ans << endl;
}


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

#define int long long
#define flash ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) begin(x),end(x)

int mod = 1e9+7;
int inf = 4e18;
const int N = 5e5+5;
vector<vector<int>> adj;
vector<bool> vis;

void dfs(int child)
{
	if(vis[child])
	return;
	vis[child] = true;
	for(auto &it:adj[child])
	dfs(it);
}		
signed main()
{
    flash
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
		int n;
		cin>>n;
		int m;
		cin>>m;
		adj.resize(n+1);
		vis.resize(n+1);
		while(m--)
		{
			int a,b;
			cin>>a>>b;
			adj[a].pb(b);
			adj[b].pb(a);
		}
		int ans = 0;
		for(int i=1;i<=n;++i)
		{
			if(!vis[i])
			{
				++ans;
				dfs(i);
			}
		}
		cout<<ans-1;
    }
    return 0;
}


Measured memory_bytes: 9812
#include <iostream>
using namespace std;
int main()
{
  int n,m,a,b,c;
  while(cin >> n >> m, n){
    m -= n;
    a = m / 1000;
    m %= 1000;
    b = m / 500;
    m %= 500;
    c = m / 100;
    cout << c << " " << b << " " << a << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main(){

    ll N;
    cin >> N;
    ll ans = 0;
    ll hoge[4] = {0, 3, 5, 7};
    for(ll i = 0;;i++){
        ll flg[4] = {};
        ll tmp = 0;
        stack<ll>S;
        for(ll j = i;j;j/=4){
            ll k = j % 4;
            flg[k] = 1;
            S.push(hoge[k]);
        }
        while(!S.empty()){
            ll s = S.top();
            S.pop();
            tmp = tmp * 10 + s;
        }
        if(tmp > N){
            // cout << "*" << i << endl;
            break;
        }
        // cout << tmp;
        // for(ll j = 0; j < 4; j++)cout << ", " << flg[j];
        // cout << endl;
        if(flg[0] == 0 && flg[1] && flg[2] && flg[3])ans++;
    }
    cout << ans << endl;

    return 0;
}

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

int main()
{
	int m, f, r;//中間,期末,再試験

	while (1)
	{
		cin >> m >> f >> r;

		if (m == -1 && f == -1 && r == -1) return 0;
		
		if (m == -1 || f == -1)cout << "F" << "\n";
		else if (m + f >= 80) cout << "A" << "\n";
		else if (m + f >= 65 && m + f < 80) cout << "B" << "\n";
		else if (m + f >= 50 && m + f < 65) cout << "C" << "\n";
		else if (m + f >= 30 && m + f < 50)
		{
			if (r >= 50) cout << "C" << "\n";
			else cout << "D" << "\n";
		}
		else if (m + f < 30)
		{
			cout << "F" << "\n";
		}

	}
}


Measured memory_bytes: 3036
#include <bits/stdc++.h>
 
using namespace std;
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; i++)
 
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
 
const long long INF = 1LL << 60;
 
bool dp[100100];
 
 
int main () {
    int S , W;
    scanf("%d%d",&S,&W);

    if(S <= W)printf("%s\n","unsafe");
    else printf("%s\n","safe");

    return 0;



}

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

#define db(x) cerr << #x ": " << (x) << '\n';

using namespace std;

typedef long long ll;

typedef long double ld;

const int oo = 1e18;

string cad;

int Q;

deque<char> D;

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

    cin >> cad;

    for(int i = 0 ; i < cad.size() ; i++)
    {
        D.push_back(cad[i]);
    }

    cin >> Q;

    bool temp = false;

    for(int i = 1 ; i <= Q ; i++)
    {
        int q;
        cin >> q;
        if(q == 1)
        {
            temp = !temp;
        }
        else if(q == 2)
        {
            int f;
            char c;
            cin >> f >> c;
            bool bb;

            if(f == 1)bb = true;
            else bb = false;

            if(temp != bb)D.push_front(c);
            else D.push_back(c);
        }
    }

    if(!temp)
    {
        while(!D.empty())
        {
            cout << D.front();
            D.pop_front();
        }
    }
    else
    {
        while(!D.empty())
        {
            cout << D.back();
            D.pop_back();
        }
    }

    return 0;
}


Measured memory_bytes: 976
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		
		double sum = 0.0;
		for (int i = 0; i < N; i++) {
			double a = scanner.nextDouble();
			a = 1 / a;
			sum += a;
		}
		System.out.println(1 / sum);
	}
}


Measured memory_bytes: 37752
#include<bits/stdc++.h>
#define pb push_back
#define in insert
#define ff first
#define ss second
#define mp make_pair
#define int long long
#define uint unsigned long long
#define rep(i,x,m) for(int i=x;i<m;i++)
#define repr(i,x,m) for(int i=x;i>=m;i--)
#define MOD 1000000007
#define endl "\n"
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define vi vector<int>
#define vs vector<string>
#define print(v) for(int i=0;i<v.size();i++) cout<<v[i]<<" ";cout<<endl
using namespace std;
#define noob ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

void ram5564()
{
    int n;
    cin>>n;
    int a[n];
    set<int>s;
    rep(i,0,n)
    {cin>>a[i];s.in(a[i]);}
    if(s.size()==n)
        cout<<"YES";
    else
        cout<<"NO";
}

signed main()
{
        noob
        // #ifndef ONLINE_JUDGE
        //  freopen("input.txt","r",stdin);
        //  freopen("output.txt","w",stdout);
        //  #endif   
        
        int t=1;
        //cin>>t;
        while(t--)
        ram5564();
        return 0;
}

Measured memory_bytes: 11264
#include <iomanip>
#include <utility>
#include <algorithm>
#include <type_traits>
#include <set>
#include <string>
#include <iostream>
#include <fstream>
#include <cassert>
#include <memory>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <queue>
#include <vector>
#include <chrono>
#include <random>
#include <forward_list>
#include <iomanip>
#include <functional>
using namespace std;
#define MFOR(i,end) for(size_t i = 0, end_i = (end); i < end_i; ++ i)


int N;
int L[2000];
int main()
{
	std::cin >> N;
	MFOR(i, 2*N) {
		std::cin >> L[i];
	}

	std::sort(L, L + 2*N);
	int sum = 0;
	for (size_t i = 0, end_i = (2*N); i < end_i; i += 2) {
		sum += L[i];
	}
	std::cout << sum;
}

Measured memory_bytes: 888
#include<stdio.h>
#include<stdlib.h>
int n,**array,**timerecord;
//array仕様
//二次元配列　各行のindex[0]は探索済かどうか、それ以外のindexはつながってるかどうかの判断
//timerecod[0]はstart time, timerecord[1]はfinish time
void record(int,int*);

int main(){
  int m,i,j,k,l,time=0;
  scanf("%d",&n);

  timerecord = malloc(sizeof(int*)*2);
  for(i=0;i<2;i++)timerecord[i]=malloc(sizeof(int)*(n+1));
 
  array = malloc(sizeof(int *)*(n+1));
  for(i=0;i<n+1;i++)array[i]=malloc(sizeof(int)*(n+1));
  for(i=0;i<n+1;i++)for(j=0;j<n+1;j++)array[i][j]=0;
  
  k=n;
  while(k--){
    scanf("%d %d",&i,&l);
    while(l--){
      scanf("%d",&m);
      array[i][m]=1;
    }
  }
  
  for(i=1;i<n+1;i++)if(array[i][0]==0)record(i,&time);

  for(i=1;i<n+1;i++)printf("%d %d %d\n",i,timerecord[0][i],timerecord[1][i]);

  for(i=0;i<n+1;i++)free(array[i]);
  free(array);
  for(i=0;i<2;i++)free(timerecord[i]);
  free(timerecord);
  return 0;
}

void record(int k,int *time){
  int i,j;
  array[k][0]=2;
  timerecord[0][k]=++(*time);
  for(i=1;i<n+1;i++){
    if(array[i][0]==0 && array[k][i] == 1){//判別条件　行先が探索済でない　かつ　つながってる場所
      
      for(j=0;j<n+1;j++)array[j][i]=2;
      record(i,time);
    }
  }
  
  timerecord[1][k]=++(*time);
}
  
  


    
  
      
  
  
  



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

int main() {
  long a, b, c, k;
  cin >> a >> b >> c >> k;
  
  if (k <= a) cout << k;
  else if (k > a && k <= a + b) cout << a;
  else cout << a - (k - a - b);
  
  return 0;
}

Measured memory_bytes: 3596
# import numpy as np
#
# N, W = map(int, input().split())
#
# dp = np.zeros(W+1, dtype=np.int64)
#
# for _ in range(N):
#     w, v = map(int, input().split())
#     np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])
#
# print(dp[-1])


import numpy as np

N, W = map(int, input().split())
dp = np.full(N * 1000 + 1, 10 ** 10, dtype=np.int64)
# print(dp)
# print(len(dp))
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
print(((dp <= W) * np.arange(N * 1000 + 1)).max())


Measured memory_bytes: 14904
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k,a[105],aa;
int main(){
	cin>>n>>k;
	while(k--){
		int s,x;
		cin>>s;
		while(s--)cin>>x,a[x]=1;
	}
	for(int i=1;i<=n;i++)if(!a[i])aa++;
	cout<<aa;
}


Measured memory_bytes: 3624
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
A = LI()
for i in range(N):
    A[i] -= i+1
A.sort()

x = A[N//2]
y = A[(N-1)//2]
z = (x+y)//2

print(sum(abs(A[i]-z) for i in range(N)))


Measured memory_bytes: 104448
def divisor(n):
    limit = int(n**0.5 + 1)
    divisors = set()
    for div in range(1, limit):
        if n % div == 0:
            div2 = n//div
            divisors.add(div)
            divisors.add(div2)
    return len(divisors)


n = int(input())
ans = 0

for num in range(105, n+1, 2):
    if divisor(num) == 8:
        ans += 1

print(ans)

Measured memory_bytes: 3060
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		new Main().solve();
	}
	int N;
	int[]s;
	int sum=0;
	void solve(){
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		s=new int[N];
		for(int i=0;i<N;i++){
			s[i]=sc.nextInt();
			sum+=s[i];
		}
		Arrays.sort(s);
		for(int i=0;i<N;i++){
			if(sum%10!=0){
				System.out.println(sum);
				return;
			}
			else if(s[i]%10!=0){
				sum-=s[i];
			}
		}
		System.out.println(0);
	}
}


Measured memory_bytes: 21972
#include <iostream>
#include <vector>
#define LMAX 100005
#define pb push_back

using namespace std;

vector<int>g[LMAX];
int rdp[LMAX];
int n, m;
int gi[LMAX];
int x, y;
int ans;

void dp(int k)
{
    rdp[k] = 0;
    if (!g[k].size())
    {
        return ;
    }
    int m = 0;
    for (int i=0; i<g[k].size(); ++i)
    {
        if (rdp[g[k][i]] == -1)
        {
            dp(g[k][i]);
        }
        m = max(m, rdp[g[k][i]]+1);
    }
    rdp[k] += m;
    ans = max(rdp[k], ans);
}

int main()
{
    cin>>n>>m;
    for (int i=1; i<=n; ++i)
    {
        rdp[i] = -1;
    }
    for (int i=1; i<=m; ++i)
    {
        cin>>x>>y;
        g[x].pb(y);
        ++gi[y];
    }
    for (int i=1; i<=n; ++i)
    {
        if (!gi[i])
        {
            dp(i);
        }
    }
    cout<<ans<<'\n';
    return 0;
}


Measured memory_bytes: 11136
import bisect
n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
sA = set(A)
sB = set(B)
x = 0
for i in sA & sB:
    r = bisect.bisect_right(A, i)
    l = bisect.bisect_left(B, i)
    x = max(x, r-l)
ans = B[-x:] + B[:-x]
for a, b in zip(A, ans):
    if a == b:
        print("No")
        break
else:
    print("Yes")
    print(*ans)


Measured memory_bytes: 57068
#include <cstdio>
#include <cstring>
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int M[100][100];
bool vst[100][100];
int w,h,xs,ys,xg,yg,n;
bool dfs(int x,int y) {
	if(x==xg&&y==yg) return true;
	vst[x][y]=true;
	for(int i=0;i<4;i++) {
		int nx=x+dx[i],ny=y+dy[i];
		if(0>nx||nx>=w||0>ny||ny>=h)continue;
		if(M[x][y]!=M[nx][ny])continue;
		if(vst[nx][ny])continue;
		if(dfs(nx,ny))return true;
	}
	return false;
}
int main() {
	while(scanf("%d %d",&w,&h),w) {
		memset(vst,0,sizeof(vst));
		memset(M,0,sizeof(M));
		scanf("%d %d",&xs,&ys);xs--;ys--;
		scanf("%d %d",&xg,&yg);xg--;yg--;
		scanf("%d",&n);
		for(int i=0;i<n;i++) {
			int c,d,x,y;
			scanf("%d %d %d %d",&c,&d,&x,&y);x--;y--;
			if(d==1) {
				for(int j=0;j<4;j++)
					for(int k=0;k<2;k++)
						M[x+k][y+j]=c;
			}else {
				for(int j=0;j<2;j++)
					for(int k=0;k<4;k++) 
						M[x+k][y+j]=c;
			}
		}
		printf("%s\n",dfs(xs,ys)?"OK":"NG");
	}
}

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

int main(){
  int N,K; cin >> N >> K;
  int A[510];
  int sum=0;
  for(int i=0; i<N; i++){
    cin >> A[i];
    sum+=A[i];
  }
  
  vector<int> div;
  int d=1;
  while(d<=sqrt(sum)){
    if(sum%d==0){
      div.push_back(d);
      div.push_back(sum/d);
    }
    d++;
  }
  sort(div.begin(),div.end(),greater<int>());
  
  for(int i=0; i<div.size(); i++){
    int p=div[i];
    
    vector<int> r(N);
    int rsum=0;
    for(int j=0; j<N; j++){
      r[j]=A[j]%p;
      rsum+=r[j];
    }
    sort(r.begin(),r.end());
    rsum/=p;
    int ksum=0;
    for(int j=0; j<N-rsum; j++){
      ksum+=r[j];
    }
    if(ksum<=K){
      cout << p << endl;
      return 0;
    }
  }
} 

Measured memory_bytes: 384
import java.util.*; 
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        Queue<String> qProcess = new LinkedList<String>();
        Queue<Integer> qTime = new LinkedList<Integer>();        
        int totalTime = 0;
        for (int i = 0; i < n; i++) {
            qProcess.add(sc.next());
            qTime.add(sc.nextInt());
        }         
        while (qProcess.size()>0) {
            if (qTime.peek() - q > 0) {
                qProcess.add(qProcess.poll());
                qTime.add(qTime.poll()-q);
                totalTime = totalTime + q;
            } else {
                totalTime = totalTime + qTime.poll();
                System.out.println(qProcess.poll() + ' ' + totalTime);
            }
        }
    }
}


Measured memory_bytes: 73940
n,m = map(int, input().split())
a = set([int(input()) for i in range(m)])
step = [1] + [0]*n
mod = 10**9 + 7
for i in range(1,n+1):
    if i in a:
        continue
    else:
        if i-1 not in a:
            step[i] += step[i-1]%mod
        if i-2 not in a and i>=2:
            step[i] += step[i-2]%mod
        if i-1 in a and i-2 in a:
            print(0)
            exit()
print(step[n]%(10**9+7))

Measured memory_bytes: 13216
import fileinput
triangle = 0
diamond = 0
for line in fileinput.input():
    if line == "\n":
        break
    else:
        a, b, c = map(int, line.split(","))
        if a**2 + b**2 == c**2:
            triangle += 1
        if a == b:
            diamond += 1
print(triangle)
print(diamond)

Measured memory_bytes: 7516
#include <bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(),(obj).end()
const int INF=99999;


int main()
{
    int x,a,b;
    cin >> x >> a >> b;
    if(a-b<0){
        if(b-a>x){
            cout << "dangerous" << endl;
        }else{
            cout << "safe" << endl;
        }
    }else{
        cout << "delicious" << endl;
    }
    return 0;
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll N, A, B;
    cin >> N >> A >> B;
    
    if((B-A+1)%2 == 1) PR((B-A)/2);
    else PR(MIN(A+(B-A-1)/2,N-B+1+(B-A-1)/2));

    return 0;
}

/*



*/

Measured memory_bytes: 3576
import java.util.Scanner;

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

        long x = scan.nextInt();

        for (long a = -150; a < 150; a++) {
            for (long b = -150; b < 150; b++) {
                if (Math.pow(a, 5) - Math.pow(b, 5) == x) {
                    System.out.println(a + " " + b);
                    return;
                }
            }
        }
    }
}

Measured memory_bytes: 38920
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long int

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, x;
    cin >> a >> b >> x;

    int ans = 0;
    if (a % x == 0) ans++;
    ans += b / x;
    ans -= a / x;
    cout << ans << endl;

    return 0;
}


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

using namespace std;
int prime_num[1000001];

void prime(){  
  bool prime[1000001];
  prime_num[0]=0;
  prime_num[1]=0;
  prime_num[2]=1;

  for(int i=0;i<1000001;i++)
    prime[i]=true;
  for(int i=2;i<=1000001;i++)
    {
      if(prime[i])
	{
	  prime_num[i]=prime_num[i-1]+1;
	  for(int j=i+i;j<1000001;j+=i)
	    prime[j]=false;
	}
      else
	prime_num[i]=prime_num[i-1];
    }
}
int main()
{
  prime();
  int n;
  for(;cin>>n,n;)
    {
      int sum=0;
      for(int i=0;i<n;i++)
	{
	  int p,m;
	  cin>>p>>m;
	  int t1=p+m,t2=p-m-1;
	  if(t1>1000000)
	    t1=1000000;
	  if(t2<0)
	    t2=0;
	  if(prime_num[t1]-prime_num[t2]==0)
	    sum-=1;
	  else
	    sum+=prime_num[t1]-prime_num[t2]-1;
	  //	  cout<<prime_num[t1]<<"-"<<prime_num[t2]<<endl;
	  //	  cout<<"tmp-sum:"<<sum<<endl;
	}
      cout<<sum<<endl;
    }
  //  cout<<prime_num[1000000];
}

Measured memory_bytes: 6036
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using ull = unsigned long long;
using ll = long long;
using namespace std;

int main(void) {
    int n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> even;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i]%2 == 0){
            even.push_back(a[i]);
        }
    }

    int out = 0;
    // sort(even.begin(), even.end(), greater<ll>());
    for(int i = 0; i < even.size(); ++i) {
        while(true) {
            if (even[i]%2 == 0) {
                out++;
                even[i]/=2;
            } else {
                break;
            }
        }
    }
    // n <= 10000
    cout << out << endl;

    return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <vector>
#include <array>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <unordered_map>


using std::string;
using std::vector;


void solve() {
    int n;
    scanf("%d", &n);
    vector<int> list(n);
    for (int i = 0; i < n; i++){
        int v;
        scanf("%d", &v);
        list[i] = v;
    }
    int swaped = 0;
    for(int i = 0; i < list.size(); i++){
        for(int j = list.size() - 1; i < j; j--){
            if(list[j] < list[j-1]){
                std::swap(list[j], list[j-1]);
                swaped++;
            }
        }
    }
    for(int i = 0; i < list.size(); i++){
        printf("%d", list[i]);
        if(i != list.size() -1){
            printf(" ");
        }
    }
    printf("\n%d\n", swaped);
    
}

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


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

typedef long long ll;

const ll M = 1000000007;

ll mypow(ll x,ll e) {
    if( e == 0 )  return 1;
    if(e%2 == 0) return mypow(x*x%M, e/2) % M;
    else   	  return mypow(x*x%M, e/2) * x % M;
}

int main () {
    ll m,n;
    cin >> m >> n;
    cout << mypow(m,n) << endl;
    return 0;
}

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

const char wall = '#';
vector<vector<char>> fields;
vector<vector<bool>> used;
vector<vector<ll>> dist;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};

vector<ll> A;
// vectorのリサイズ
// A.resize(N);

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return b/gcd(a,b)*b;}

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

  ll n, m;
  cin >> n >> m;
  vector<ll> a(n);
  priority_queue<ll> q;
  rep(i, n) {
    cin >> a[i];
    q.push(a[i]);
  }
  ll ans = 0;


  //// O(mnlongn) TLEしそう
  //while(m>0) {
  //  a[0] /= 2;
  //  m--;
  //  sort(a.begin(), a.end(), greater<ll>());
  //}
  //
  while(m>0) {
    ll maxV = q.top(); q.pop();
    maxV /= 2;
    q.push(maxV);
    m--;
  }
  
  while (!q.empty()) {
    ans += q.top();
    q.pop();
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2168
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
    int a,b,c;
    int x,y;
    int minxy;
    cin >> a >> b >> c >> x >> y;

    minxy = x;
    if(x > y) minxy = y;

    if(a > 2*c || b > 2*c){
      if(x > y && a > 2*c){
        cout << 2*c*x << endl;
      }else if(x < y && b > 2*c){
        cout << 2*c*y << endl;
      }else{
        cout << a*(x-minxy) + b*(y-minxy) + 2*c*minxy << endl;
      }
      return 0;
    }

    if (a + b < 2*c) {
      cout << a*x + b*y << endl;
    } else {
      cout << a*(x-minxy) + b*(y-minxy) + 2*c*minxy << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define y_n(ans) cout<<(ans?"Yes":"No")<<endl;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> neigh(n, vector<int>(0));
    rep(i, m) {
        int a, b; cin >> a >> b;
        a--; b--;
        neigh[a].push_back(b);
        neigh[b].push_back(a);
    }
    vector<int> next(n, -1);
    next[0] = -10;
    queue<int> q;
    for (int i: neigh[0]) {
        q.push(i);
        next[i] = 0;
    }
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i: neigh[now]) {
            if (next[i] != -1) continue;
            else {
                q.push(i);
                next[i] = now;
            }
        }
    }
    bool ans = true;
    for (int i=1; i<n; ++i) {
        if (next[i] == -1) {
            ans = false;
        }
    }
    y_n(ans);
    if (ans) {
        for (int i=1; i<n; ++i) {
            cout << next[i]+1 << endl;
        }
    }
}

Measured memory_bytes: 10244
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007

ll n;
ll dp[3005][3005][2];
ll a[3005];
ll rec(int l,int r, int p)
{
	if(l>r)
		return 0;
	ll & res=dp[l][r][p];
	if(res!=-1)
		return res;
	if(p==0)
	res=max(a[l]+rec(l+1,r,1-p),a[r]+rec(l,r-1,1-p));
else
	res=min(rec(l+1,r,1-p)-a[l],rec(l,r-1,1-p)-a[r]);
return res;
}
 
int main()
{
	
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	memset(dp,-1,sizeof(dp));
	cout<<rec(0,n-1,0);
	

	
	
	
	
 
	return 0;
}

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

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

using namespace std;

int main(){
	int a[3][3];
	rep(i,3) rep(j,3) scanf("%d",&a[i][j]);

	int n; scanf("%d",&n);
	rep(i,n){
		int b; scanf("%d",&b);
		rep(y,3) rep(x,3) if(a[y][x]==b) a[y][x]=0;
	}

	rep(i,3){
		int cnt=0;
		rep(j,3) if(a[i][j]==0) cnt++;
		if(cnt==3) return puts("Yes"),0;
	}
	rep(j,3){
		int cnt=0;
		rep(i,3) if(a[i][j]==0) cnt++;
		if(cnt==3) return puts("Yes"),0;
	}
	{
		int cnt=0;
		rep(i,3) if(a[i][i]==0) cnt++;
		if(cnt==3) return puts("Yes"),0;
	}
	{
		int cnt=0;
		rep(i,3) if(a[i][2-i]==0) cnt++;
		if(cnt==3) return puts("Yes"),0;
	}

	puts("No");

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
typedef long long LL;
const int N=2e5;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
int R,C;
inline int get(int x,int y) {
	if (!y) return x;
	if (x==R) return y+R;
	if (y==C) return R+C+R-x;
	if (!x) return R+C+R+C-y;
	return -1;
}
int main()
{
	R=gi(),C=gi();
	int n=gi(),i,a,b,c,d;
	vector<pair<int,int>>v;
	for (i=1;i<=n;i++) {
		a=gi(),b=gi(),c=gi(),d=gi();
		if ((a=get(a,b))!=-1&&(b=get(c,d))!=-1)
			v.push_back(make_pair(a,i)),v.push_back(make_pair(b,i));
	}
	sort(v.begin(),v.end());
	stack<int>st;st.push(0);
	for (auto t:v)
		st.top()==t.second?st.pop():st.push(t.second);
	puts(st.size()==1?"YES":"NO");
	return 0;
}


Measured memory_bytes: 2420
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        boolean[] used = new boolean[1_000_001];
        Arrays.sort(a);
        Set<Integer> set = new HashSet<>();
        Set<Integer> d = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (set.contains(a[i])) {
                d.add(a[i]);
                continue;
            }
            if(used[a[i]])continue;
            set.add(a[i]);
            int x = a[i];
            while(x < 1_000_001){
                used[x] = true;
                x += a[i];
            }

//            if(set.contains(a[i])){
//                d.add(a[i]);
//                continue;
//            }
//            Map<Integer, Integer> map = new HashMap<>();
//            List<Integer> list = new ArrayList<>();
//            int x = a[i];
//            for (int j = 2; j < Math.sqrt(a[i])+1; j++) {
//                int c = 0;
//                while(x % j == 0){
//                    c++;
//                    x /= j;
//                }
//                if(0 < c) {
//                    map.put(j, c);
//                    list.add(j);
//                }
//            }
//            if(1 < x){
//                map.put(x, 1);
//                list.add(x);
//            }
//            Set<Integer> p = new HashSet<>();
//            p.add(1);
//            for(int b : list){
//                Set<Integer> nex = new HashSet<>();
//                int y = 1;
//                for (int j = 0; j <= map.get(b); j++) {
//                    for(int c : p){
//                        nex.add(c * y);
//                    }
//                    y *= b;
//                }
//                p = nex;
//            }
//            boolean able = true;
//            for(int b : p){
//                if(used[b]){
//                    able = false;
//                    break;
//                }
//            }
//            if(able)set.add(a[i]);
//            used[a[i]] = true;
        }
        System.out.println(set.size() - d.size());
        sc.close();

    }

}


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

int main() {
    int sum = 0, N, n_tmp;
    int max_n = 100000000;

    cin >> N;
    n_tmp = N;
    while (max_n != 0) {
        sum += (n_tmp / max_n);
        n_tmp %= max_n;
        max_n /= 10;
    }
    if ((N % sum) == 0) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = Integer.parseInt(sc.nextLine());
    int a = N / 100;
    int b = (N - 100 * a) / 10;
    int c = (N - 100 * a - 10 * b);
    if (a == c){
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}

Measured memory_bytes: 25172
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n, m;
int a[100010], b[100010];

bool solve() {
    int c[n+1];
    memset(c, 0, sizeof(c));
    for (int i = 0; i < m; i++) {
        c[a[i]]++;
        c[b[i]]++;
    }

    for (int i = 0; i <= n; i++) {
        if (c[i] % 2)
            return false;
    }
    return true;
}

void input() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> a[i] >> b[i];
}

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

    input();
    cout << (solve() ? "YES" : "NO") << endl;
}


Measured memory_bytes: 1408
#include <stdio.h>
 #include <queue>
 #include <iostream>
 #include <string.h> 
 #include <algorithm>
 using namespace std;
 char s1[51][51];
int main(){
	int h,w,i,j,k,l,m,n;
	int u[4][2]={-1,0,1,0,0,-1,0,1};
	scanf("%d%d",&h,&w);
	for(i=0;i<h;i++){
		scanf("\n");
		scanf("%s",s1[i]);
	} 
	for(i=0;i<h;i++){
	for(j=0;j<w;j++){
	if(s1[i][j]=='#'){
		l=0;
	for(k=0;k<4;k++){
		m=u[k][0]+i;
		n=u[k][1]+j;
		if((m>=0)&&(m<h)&&(n>=0)&&(n<w))if(s1[m][n]=='#')l=1;
	}
	if(!l){printf("No");return 0;}
	}
	}
	}
	printf("Yes");

	return 0;
}
	
	

 	
 	
 	
 	
 	
 	
 	
 

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    int i,n,a[100],p=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(i=1;i<=n;i=i+2)
    {
        if(a[i]%2==1)
        {
            p=p+1;
        }
    }
    cout<<p<<endl;
    return 0;
}


Measured memory_bytes: 3560
#include <string>
#include <vector>
#include <iostream>
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <cmath>
#include<algorithm>
using namespace std;
int main()
{
    int x,a[3];
    cin>>x;
    for(int i=1;i<x+1;i++){
        cin>>a[0]>>a[1]>>a[2];
        sort(a,a+3);
        if(a[0]*a[0]+a[1]*a[1]==a[2]*a[2])cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

Measured memory_bytes: 1168
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Integer> set = new HashSet<>();
        for (int i = 0 ; i < n ; i++) {
            set.add(sc.nextInt());
        }
        System.out.println(set.size() == n ? "YES" : "NO");
    }

}


Measured memory_bytes: 102656
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define P pair<ll,ll>
#define FOR(I,A,B) for(int I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))




void get_forest_size(const vector<int> &u,const vector<int> &v,vector<vector<int>> &forest){
	// 木で、ある頂点を除いた時にできる森の各木のサイズを出力 0-index
	// out[i][j] := 頂点iを取り除いてできた森のうちj個目の木のサイズ
	// 辺集合が引数
	// vector<vector<int>> &forest -> 出力用
	int N = u.size() + 1;

	vector<int> us(N-1,0),vs(N-1,0);
	// us[i] := i番目の辺のv[i]側から見たu[i]側にある頂点数
	// vs[i] := i番目の辺のu[i]側から見たv[i]側にある頂点数

	set<int> connect[N];
	vector<int> num(N,0);
	vector<int> did(N-1,0);//1->uでやった 2->vでやった
	for(int i=0;i<N-1;i++){
		connect[u[i]].insert(i);
		connect[v[i]].insert(i);
	}
	queue<int> Q;//辺の番号が入る
	for(int i=0;i<N;++i){
		if(connect[i].size() == 1){
			Q.push( *connect[i].begin() );
		}
	}
	//葉の接続してる辺から取り除いていき、また葉ができら取り除いていく
	while( Q.size() ){
		int ie = Q.front();
		Q.pop();
		if(connect[u[ie]].size() == 1){
			us[ie] = num[u[ie]] + 1;
			num[v[ie]] += us[ie];
			connect[u[ie]].clear();
			connect[v[ie]].erase(ie);
			if(connect[v[ie]].size()==1){
				Q.push( *connect[v[ie]].begin() );
			}
			if(not did[ie]) did[ie] = 1;
		}else{
			vs[ie] = num[v[ie]] + 1;
			num[u[ie]] += vs[ie];
			connect[v[ie]].clear();
			connect[u[ie]].erase(ie);
			if(connect[u[ie]].size()==1){
				Q.push( *connect[u[ie]].begin() );
			}
			if(not did[ie]) did[ie] = 2;
		}
	}
	forest.resize(N);
	for(int i=0;i<N-1;i++){
		if(did[i]==1){
			vs[i] = N - us[i];
		}else{
			us[i] = N - vs[i];
		}
		forest[u[i]].push_back(vs[i]);
		forest[v[i]].push_back(us[i]);
	}
	return;
}



ll calc(ll a,ll b,ll p){//a^(b) mod p   
	if(b==0)return 1;
	ll y = calc(a,b/2,p);y=(y*y)%p;
	if(b & 1) y = (y * a) % p;
	return y;
}

int main(){
	ll N;
	cin >> N;
	vector<int> u(N-1),v(N-1);
	FOR(i,0,N-1){
		cin >> u[i] >> v[i];
		u[i]--;
		v[i]--;
	}
	vector<vector<int>> fs;
	get_forest_size(u,v,fs);
	ll ans = 0;
	FOR(i,0,N){
		ll sum = 0;
		for(auto s : fs[i]){
			sum += s;
			(ans += MOD - calc(2,s,MOD) + 1 ) %= MOD;
		}
		(ans += calc(2,sum,MOD)) %= MOD;
		(ans += MOD - 1) %= MOD;
	}
	(ans *= calc(calc(2,N,MOD),MOD-2,MOD)) %= MOD;
	cout << ans << endl;
}


Measured memory_bytes: 33536
N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
def f(i):
  res=0
  t=2**i
  a_nex=sorted([p%(2*t) for p in a])
  b_nex=sorted([p%(2*t) for p in b])
  l=0
  p=q=r=0
  for k in reversed(a_nex):
    while p<N and k+b_nex[p]<t:
      p+=1
    while q<N and k+b_nex[q]<2*t:
      q+=1
    while r<N and k+b_nex[r]<3*t:
      r+=1
    l+=q-p+N-r
  res=(l%2)<<i
  return res
for k in range(29):
  ans+=f(k)
print(ans)   
  


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

int main() {
	int n, m;
	while(cin >> n >> m ,n){
		int ans = 0;
		for(int i=0;i<n;i++){
			int a;
			cin >> a;
			ans += min(a, m/n);
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3084
s=str(input())
k=int(input())

one=0
#最初に連続する1の数を数える
for i in s:
    if i=='1':
        one+=1
    else:
        break

if(k<=one):
    #kより1の数が多ければ1
    print(1)
else:
    #そうでない場合1の次に出てくる数字
    print(s[one])

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

const int INF=0x3f3f3f3f;

vector<int>E[600000];
int dp[600000];

int main(){
	int n;string s;cin>>n>>s;
	int start=count(s.begin(),s.end(),'1');
	rep(i,int(s.size())-2){
		if(s[i]=='1'&&s[i+1]=='0'&&s[i+2]=='1'){
			int l=i,r=i+2;
			while(r<s.size()&&s[r]=='1'){
				E[l].push_back(r);
				r++;
			}
			l=i;r=i+2;
			while(l>=0&&s[l]=='1'){
				E[l].push_back(r);
				l--;
			}
		}
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	rep(i,s.size()){
		if(dp[i]==INF)continue;
		dp[i+1]=min(dp[i+1],dp[i]+(s[i]=='1'));
		for(int u:E[i]){
			dp[u+1]=min(dp[u+1],dp[i]+1);
		}
	}
	cout<<start-dp[s.size()]<<endl;
}

Measured memory_bytes: 35460
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
ll w[maxn];
ll f[405][405][405];

ll solve(){
    memset(f,-1,sizeof f);
    for(int i = 1;i<=N;i++) f[1][i][i] = 0;
    for(int len = 2;len<=N;len++){
        for(int i = 1;i<=N-len+1;i++){
            int j = i+len-1;
            for(int k = i;k<j;k++){
                int lenl = k-i+1,lenr = len-lenl;
                if(f[len][i][j] == -1) f[len][i][j] = f[lenl][i][k] + f[lenr][k+1][j] + w[j] - w[i-1];
                else f[len][i][j] = min(f[len][i][j],f[lenl][i][k] + f[lenr][k+1][j] + w[j] - w[i-1]);
            }
        }
    }
    return f[N][1][N];
}

int main(){
    // debug;
    ios;

    cin>>N;
    for(int i = 1;i<=N;i++) cin>>w[i];
    for(int i = 1;i<=N;i++) w[i] += w[i-1];

    cout<<solve()<<'\n';
    
    return 0;
}


Measured memory_bytes: 520448
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

constexpr int64_t DIV1097 = 1000000007LL;

using namespace std;

int main()
{
    std::string S;
    std::cin >> S;

    int64_t a, b, c;
    a = b = c = 0;
    for (size_t i = 0; i < S.size(); ++i) {
        switch (S[i]) {
        case 'a':
            a++;
            break;
        case 'b':
            b++;
            break;
        case 'c':
            c++;
            break;
        }
    }

    auto max = std::max({a, b, c});
    auto min = std::min({a, b, c});

    if (max - min >= 2) {
        std::cout << "NO" << std::endl;
    }
    else {
        std::cout << "YES" << std::endl;
    }

    return 0;
}


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

using namespace std;

const int MAX = 1e4 + 9;
int digit[11] = {2, 5, 5, 4, 5, 6, 3, 7, 6}, dp[MAX], n, m, a[11];

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a[i]; 
		a[i]--;
	}
	sort(a, a + m, greater<int>());
	dp[0] = 1;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			if (i - digit[a[j]] < 0) continue;
			if (dp[i - digit[a[j]]] > 0) dp[i] = max(dp[i], dp[i - digit[a[j]]] + 1);
		}
	}
	int len = dp[n];
	while (n) {
		for (int i = 0; i < m; i++) {
			if (n - digit[a[i]] < 0) continue;
			if (dp[n - digit[a[i]]] == len - 1) {
				cout << (char)(a[i] + 1 + '0');
				n -= digit[a[i]];
				len--;
				break;
			}
		}
	}
	
	return 0;
}


Measured memory_bytes: 256
import sys
N=int(input())

if 100<=N<=105:
    print(1)
    sys.exit()

min_=N//105
max_= N//100 + 1
#print(min_,max_)
count=0
for m in range(min_,max_):
    X = N - 100*m
    for i in range(0,X+1):
        for j in range(0,(X-i)//2 +1):
            for k in range(0,(X-i-2*j)//3 +1):
                for l in range(0,(X-i-2*j-3*k)//4 +1):
                    count+=1
                    if count >= 5*10**7:
                        print(1)
                        sys.exit()
                    temp = (X-i-2*j-3*k-4*l)
                    if (temp % 5 == 0) and (m-i-j-k-l-temp//5>=0):
                        a=m-i-j-k-l-temp//5
                        t=temp // 5
                        print(1)
                        #print(N,m,a,i,j,k,l,t,100*a+101*i+102*j+103*k+104*l+105*t)
                        sys.exit()
else:
    print(0)

Measured memory_bytes: 42668
#include "bits/stdc++.h"
#include <chrono> 
 
using namespace std;
using namespace std::chrono; 
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define gcd(a,b) __gcd(a,b)
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
#define vc vector<char>
#define pb(n) push_back(n)
#define pp pop_back()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define type(a) typeid(a).name();
#define print(arr) cout << "[" ;for(unsigned int i=0;i<(unsigned int) arr.size();i++){ (i==arr.size()-1)?cout << arr[i]:cout << arr[i] << ",";}cout << "]" << endl
#define Arr(arr,l) cout << "[" ;for(unsigned int i=0;i<(unsigned int) l;i++){ (i==l-1)?cout << arr[i]:cout << arr[i] << ",";}cout << "]" << endl
#define console(arr) cout << "["<<endl; for(ll i=0;i<(ll)arr.size();++i){cout << " [";for(ll j=0;j<(ll)arr[i].size();++j){(j==(int)arr[i].size()-1)?cout << arr[i][j]:cout << arr[i][j] << ",";}cout << "]"<<endl;} cout << "]"<<endl
#define starting() auto start = high_resolution_clock::now()
#define ending() auto stop = high_resolution_clock::now();auto duration = duration_cast<microseconds>(stop - start);cout << endl << endl << "Execution Time : "<<duration.count()/1000 << " ms" << endl
 
template <typename T1,typename T2>
void mapped(map<T1,T2>m){for(auto ite=m.begin();ite!=m.end();++ite){cout << "'" << ite->first << "'"<<" : "<<ite->second <<endl;}}
 
template <typename T1 , typename T2>
void mappedArr(map<T1,vector<T2>>m){for(auto ity=m.begin();ity!=m.end();++ity){cout << "'"<< ity->first <<"'"<<" : "<<"[";
for(int i=0;i<(int)ity->second.size();++i){(i==(int)ity->second.size()-1)?cout << ity->second[i]:cout << ity->second[i] << ",";}cout << "]"<<endl;}}
 
string int_to_string(int x){ stringstream ss; ss << x; string ni = ss.str(); return ni;}
int char_to_int(char c){ int n = (int)c - 48; return n; }
int string_to_int(string x){ int n; stringstream s(x); s >> n; return n; }
 
template <typename T1,typename T2>
void ArrPair(vector<pair<T1,T2>>vp){for(int i=0;i<(int)vp.size();++i){
cout << "(" << vp[i].first << "," << vp[i].second << ")"<<endl ;}}
 
const int MOD = 1e9 + 7;
const ll INF = 1e18L + 5;
 
int main(){
  string s,s1,s2;
  cin >> s >> s1 >> s2;
  cout << s[0] << s1[0] << s2[0]; 
}














Measured memory_bytes: 256