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

int main(void) {

	long long a[100000], n;
	long long product = 1, b = 1000000000000000000;

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%lld", &a[i]);
	}

	for (int i = 0; i < n; i++) {
		if (a[i] == 0) {
			printf("0");
			return 0;
		}
	}

	for (int i = 0; i < n; i++) {
		

			if (b / product < a[i]) {
			product = -1;
			break;
		    }

		product *= a[i];
	
	}

	

	printf("%lld", product);

	return 0;
}

Measured memory_bytes: 2508
# -*- coding: utf-8 -*-
"""
Created on Sun Feb  9 20:19:26 2020

@author: W_Indicate
"""
S, T = input().split()
A, B = map(int, input().split())
U = input()

if S == U:
    A = A-1
else:
    B = B-1

#出力
print("{} {}".format(A,B))

Measured memory_bytes: 2940
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+10;
struct edge{int next,to;}a[N];
int n,m,head[N],cnt,Ans,f[N],dep[N],U,V,k[N],P[N],tt,len,tot;
void link(int x,int y) {a[++cnt]=(edge){head[x],y};head[x]=cnt;}
void NO() {puts("-1");exit(0);}
void dfs(int x,int fr)
{
	dep[x]=dep[fr]+1;
	f[x]=(dep[x]&1)?1:-1;tot+=f[x];
	for(int i=head[x];i;i=a[i].next)
	{
		int R=a[i].to;if(R==fr) continue;
		if(dep[R]) len=abs(dep[x]-dep[R])+1,U=x,V=R;
		else dfs(R,x);
	}
}
void dfs2(int x,int fr)
{
	for(int i=head[x];i;i=a[i].next)
	{
		int R=a[i].to;if(R==fr) continue;
		if((x==U&&R==V)||(x==V&&R==U)) continue;
		dfs2(R,x);k[x]+=k[R],f[x]+=f[R];
	}
	if(!k[x]) Ans+=abs(f[x]);
	else P[++tt]=f[x]*k[x];
}
int main()
{
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++)
		scanf("%d%d",&x,&y),link(x,y),link(y,x);
	dfs(1,0);
	if(m==n-1) {if(tot) NO();}
	else if(len&1) {if(tot%2) NO();int v=tot/2;Ans+=abs(v),f[U]-=v,f[V]-=v;}
	else {if(tot) NO();k[U]=1,k[V]=-1;}
	dfs2(1,0);
	P[++tt]=0;sort(P+1,P+tt+1);
	for(int i=1;i<=tt;i++) Ans+=abs(P[tt/2]-P[i]);
	cout<<Ans<<endl;
}


Measured memory_bytes: 9600
import sys
from heapq import heappop, heappush


class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    @classmethod
    def from_array(cls, arr, INF):
        ins = cls(len(arr), INF)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = min(ins.tree[l], ins.tree[r])
        return ins

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


n, *ppp = map(int, sys.stdin.buffer.read().split())
INF = 10 ** 18

sgt0 = SegTreeMin.from_array([(p if i % 2 == 0 else INF, i) for i, p in enumerate(ppp)], (INF, -1))
sgt1 = SegTreeMin.from_array([(p if i % 2 == 1 else INF, i) for i, p in enumerate(ppp)], (INF, -1))
sgt = [sgt0, sgt1]
ans = []
heap = []
first_p, i = sgt0.get_min(0, n)
first_q, j = sgt1.get_min(i, n)
heap.append((first_p, first_q, 0, n, i, j))
while heap:
    p, q, l, r, i, j = heappop(heap)
    ans.append(p)
    ans.append(q)
    if l < i:
        k = l % 2
        np, ni = sgt[k].get_min(l, i)
        nq, nj = sgt[k ^ 1].get_min(ni, i)
        heappush(heap, (np, nq, l, i, ni, nj))
    if i + 1 < j:
        k = (i + 1) % 2
        np, ni = sgt[k].get_min(i + 1, j)
        nq, nj = sgt[k ^ 1].get_min(ni, j)
        heappush(heap, (np, nq, i + 1, j, ni, nj))
    if j + 1 < r:
        k = (j + 1) % 2
        np, ni = sgt[k].get_min(j + 1, r)
        nq, nj = sgt[k ^ 1].get_min(ni, r)
        heappush(heap, (np, nq, j + 1, r, ni, nj))

print(*ans)


Measured memory_bytes: 128892
#include <iostream>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <iomanip>
#include <cstdio>
#include <new>
#include <vector>
#include <cstdlib>
#include <string>
#include <set>
#include <tuple>
#include<map>

using namespace std;
int main() {
	int a, b, c;
	cin >> a >> b >> c;

	int ans = 0;

	ans = min(a + b, a + c);
	ans = min(ans, b + c);

	cout << ans << endl;

}

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

int main(){
  int N, a, b, c, d;
  cin >> N;
  a = N / 1000;
  N %= 1000;
  b = N / 100;
  N %= 100;
  c = N / 10;
  N %= 10;
  d = N;

  if((a == b && b == c) ||(b == c && c == d)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define en "\n"
using namespace std;
const int M=1e5+100;



int main()
{
    int n,ans=0,ma=0,tem;
    cin>>n;
    while(n--)
    {
        cin>>tem;
        if(tem>=ma)ans++;
        ma=max(ma,tem);
    }
    cout<<ans<<en;
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <ccomplex>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <numeric>
#include <sstream>
#include <set>

using namespace std;
#define MAX 1000000000

int main(){

    int N;
    cin >> N;

    int cnt = 0;
    set<char> sample;
    sample.insert('3');
    sample.insert('5');
    sample.insert('7');

    for (int i = 357; i <= N; i = i + 2){
        int contiFlg = false;
        string temp = to_string((long long int)i);
        for (int len = temp.size(); len > 3; len--){
            temp = temp.substr(temp.size() - len,temp.size());
            if ((temp[0] != '3') && (temp[0] != '5') && temp[0] != '7'){
                i += (int)pow(10.0, (int)temp.size() - 1);
                contiFlg = true;
                break;
            }
        }
        if (contiFlg) continue;
        temp = to_string((long long int)i);
        set<char> tempS;
        for (unsigned int i = 0; i < temp.size(); i++){
            tempS.insert(temp[i]);
        }
        if(tempS != sample) continue;
        cnt++;
    }
    std::cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_map>
#include<string>
#define ll long long
using namespace std;
const ll INF = 1LL << 60;
const int inf = 1 << 30;
const int N= 1e5 + 10;
inline void fastio()
{ 
     ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
int teleport[200005], path[200005];
int main()
{
    int n;
    ll k;
    map<int, int> visit;
    cin >> n>> k;
    for (int i = 1; i <= n;i++)
    {
        cin >> teleport[i];
    }

    ll cur = 1, path_len = 0, circle_entrance, start_to_entrance = 0;
    path[0] = 1;
    while(cur<=n)
    {
        
        if(visit.find(cur)==visit.end())
        {
            visit[cur] = 1;
            path_len++;
            cur = teleport[cur];
            path[path_len] = cur;
        }
        else
        {
            circle_entrance = cur;
            int len = path_len;
            for (int i = 0; (i <=len) && (path[i]!=circle_entrance);i++)
                {
                    path_len--;
                    start_to_entrance++;
                }
            break;
        }
    }
    ll ans;
    if(k<=start_to_entrance)
    {
        ans = k;
    }
    else
    ans = k<=start_to_entrance?k:(k-start_to_entrance) % path_len+start_to_entrance ;

    cout << path[ans] << endl;
    return 0;
}

Measured memory_bytes: 14432
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define ub upper_bound
#define lb lower_bound
#define all(v) ((v).begin()),((v).end())
#define allr(v) ((v).rbegin()),((v).rend())
#define ff first
#define ss second
#define mp make_pair
#define pll pair<ll,ll> 
#define fo(i,n) for(ll i=0;i<n;i++)
#define foa(i,s,e) for(ll i=(s);i<e;i++)
#define fod(i,s,e) for(ll i= (s);i>=(e);i--)
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
#define sz(x) (ll)(x.size())
#define ANS cout<<ans<<'\n'
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
const ld pi = 3.14159265358979323846;
ll MOD = 1e9 + 7;
//ll MOD = 998244353;
const char nl = '\n';
const ll inf = 1e15;
#define fill(a,b) memset(a, b, sizeof(a))
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) fo(i, n){fo(j, m)cout<<dp[i][j]<<" ";cout<<"\n";}
ll nxt(){ll x; cin >> x; return x;}
ll mul(ll x,ll y){
    return (1ll* (x%MOD)*(y%MOD));
}
ll modpow(ll x,ll y){ll z=1;while(y>0){if(y%2)z=mul(z,x);x =mul(x,x) ;y/=2;}return z;}
ll power(ll x,ll y){ll z=1;while(y>0){if(y%2)z=z*x;x =x*x ;y/=2;}return z;}
ll gcd(ll a,ll b){if(a<b) return gcd(b,a);if(b==0) return a;return gcd(b,a%b);} 
ll min(ll a,ll b){if(a<b)return a;return b;}
ll max(ll a,ll b){if(a>b)return a;return b;}
ll sq(ll a){
    ll ans = (1ll*a*a);
    return ans;
}
void solve(){
    ll d, t, s;
    cin >> d >> t >> s;
    if(s * t >= d)Yes;
    else No;
}
int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif
    ll TC = 1;
    //cin>>TC;
    fo(TT, TC){
        // Google,FB cout << "Case #"<< TT + 1 << ": ";
        solve();
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}


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

main()
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(a%2==1||b%2==1||c%2==1)
	{
		printf("0\n");
		return 0;
	}
	for(int i=1;i<=1000000;i++)
	{
		int na=(b+c)/2,nb=(a+c)/2,nc=(b+c)/2;
		if(na%2==1||nb%2==1||nc%2==1)
		{
			printf("%d\n",i);
			return 0;
		}
		a=na;
		b=nb;
		c=nc;
	}
	printf("-1");
}

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

int main(void) {
	int P, Q, R;
	cin >> P >> Q >> R;
	int min,PQ,QR,PR;
	PQ = P + Q;
	QR = Q + R;
	PR = P + R;
	if (PQ >= QR) {
		min = QR;
	}
	else {
		min = PQ;
	}
	if (min >= PR) {
		min = PR;
	}
	cout << min;
	
}

Measured memory_bytes: 256
N = int(input())
A = [int(i) for i in input().split()]
mod = 10**9+7
#並びが可能なら、2**(N//2)
#無理なら0
opt = {}
for i in range(N):
  a = abs((N-i-1)-i)
  if a not in opt :
    opt[a] = 1
  else :
    opt[a] += 1 
for i in range(N):
  if A[i] not in opt or opt[A[i]] == 0 :
    print(0)
    exit()
  else:
    opt[A[i]] -= 1 
ans = (2**(N//2))%mod
print(ans)

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<long long> a(n);
	for(int i=0;i<n;i++)
		cin >> a[i];
	
	vector<long long> left(n+1);
	left[0]=0;
	for(int i=1;i<=n;i++)
		left[i]=left[i-1]+a[i-1];

	sort(left.begin(),left.end());
	long long ans=0;
	long long bef=1000000000009;
	long long count=0;
	for(int i=0;i<=n;i++)
	{
//		cout << left[i] << endl;
		if(bef==left[i])
			count++;
		else
		{
			ans+=((count*(count-1))/2);
			count=1;	
		}
		bef=left[i];
	}
	ans+=((count*(count-1))/2);

	cout << ans << endl;


}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int c[N][N],n;
int main() {
	scanf("%d",&n);
	if(n==1) printf("Yes\n1\n");
	else {
		if(n&1) printf("No\n");
		else {
			printf("Yes\n");
			for(int i=1;i<n;i++) c[i][1]=c[n-1][i+1]=i;
			for(int i=n-2;i>=2;i--) {
				for(int j=2;j<=i;j++) c[i][j]=c[i+1][j-1];
			}
			for(int i=1;i<n;i++) c[n][i]=c[i][i];
			for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(i<j) c[i][j]=c[j][i]+n-1;
			for(int i=1;i<=n;i++) c[i][i]=2*n-1;
			for(int i=1;i<=n;i++) 
				for(int j=1;j<=n;j++) printf("%d%c",c[i][j],j==n?'\n':' '); 
		}
	}
	return 0;
}



Measured memory_bytes: 4176
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

const double INF=1e10;

int n;
pi ps[20];
double d[20][20];
int ar[20];
double sq(double a){
  return a*a;
}
struct uf{

  static const int MAXN=18;
  int par[MAXN];
  int size[MAXN];
  void init(){
    memset(par,-1,sizeof(par));
    REP(i,MAXN) size[i]=1;
  }
  int root(int a){
    if(par[a]==-1) return a;
    return par[a]=root(par[a]);
  }
  void unite(int a,int b){
    a=root(a);b=root(b);
    if(a==b) return;
    if(size[a]<size[b]) swap(a,b);

    par[b]=a;
    size[a]+=size[b];
  }
  bool same(int a,int b){
    return root(a)==root(b);
  }
};


uf u;
vector<int> g[20];
pair<double,pi> es[150];

double dfs(int v,int p,double thr){
  double cur=ar[v];
  for(auto to:g[v]){
    if(to==p) continue;
    double a=dfs(to,v,thr);
    if(a>0){
      cur-=d[v][to]+a;
    }else{
      cur+=max(0.0,-a-d[v][to]);
    }
  }
  return -(cur-thr);
}
bool check(double thr,int r){
  double req=dfs(r,-1,thr);
  if(req<=0) return true;
  return false;
}
double calc(int bit){
  int m=0;
  int r=-1;
  REP(i,n) g[i].clear();
  REP(i,n) if(bit>>i&1){
    REP(j,i) if(bit>>j&1){
      es[m++]=mp(d[i][j],mp(i,j));
    }
    r=i;
  }
  sort(es,es+m);
  u.init();
  REP(i,m){
    int a=es[i].sc.fr,b=es[i].sc.sc;
    if(!u.same(a,b)){
      u.unite(a,b);
      g[a].pb(b);
      g[b].pb(a);
    }
  }

  double lb=0,ub=1e9+10;
  REP(i,100){
    double md=(lb+ub)/2;
    if(check(md,r)) lb=md;
    else ub=md;
  }
  return lb;
}

double wat[1<<15];
double dp[1<<15];
int main(){
  cin>>n;
  REP(i,n){
    cin>>ps[i].fr>>ps[i].sc>>ar[i];
  }
  REP(i,n) REP(j,n) {
    d[i][j]=sqrt(sq(ps[i].fr-ps[j].fr)+sq(ps[i].sc-ps[j].sc));
  }

  REP(i,1<<n) if(i>0){
    wat[i]=calc(i);
  }
  dp[0]=INF;
  for(int i=1;i<(1<<n);++i){
    int cur=i;
    do{
      chmax(dp[i],min(wat[cur],dp[i^cur]));
      cur=(cur-1)&i;
    }while(cur>0);
  }
  printf("%.10f\n",dp[(1<<n)-1]);
  return 0;
}





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


int main() {
  int N,M,X;
  cin>>N>>M>>X;
  
  int Ai;
  int cnt1=0,cnt2=0;
  for(int i=0;i<M;i++){
    cin>>Ai;
    if(Ai>X)
      cnt1++;
    else
      cnt2++;
  }
  
  cout<<min(cnt1,cnt2)<<endl;
  
  return 0;
}


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

using namespace std;

using ll = long long;

int main(){
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cout.setf(ios::fixed); cout.precision(17);
  int n, k;
  cin >> n >> k;

  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  int ans = 2e9;
  for(int i = 0; i <= n - k; i++){
    int l = a[i], r = a[i + k - 1];
    if(r <= 0){
      ans = min(ans, -l);
    } else if(l >= 0){
      ans = min(ans, r);
    } else {
      int foo = min(2 * r - l, 2 * (-l) + r);
      ans = min(ans, foo);
    }
  }
  cout << ans << "\n";
  return 0;
}



Measured memory_bytes: 640
// -----------------------------------
// author   : MatsuTaku
// country  : Japan
// created  : 05/31/20 18:19:57
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  ll a; cin>>a;
  string s; cin>>s;
  int i = 0;
  while (s[i] != '.') ++i;
  ll bn = stoi(s.substr(0, i));
  ll bf = stoi(s.substr(i+1, 2));
  ll ans = a*bn + a*bf/100;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3640
#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
vector<pair<long long, long long>>x[120000];
pair<long long, long long>dist[120000];
long long n, m, h, a[320000], b[320000], c[320000], H[120000];
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>>Q;
void dijkstra() {
	for (int i = 1; i <= n; i++)dist[i] = make_pair(999999999999999999LL, -999999999999999999LL);
	Q.push(make_pair(0, 1)); dist[1] = make_pair(0, h);
	while (!Q.empty()) {
		long long a1 = Q.top().first, a2 = Q.top().second; Q.pop();
		for (int i = 0; i < x[a2].size(); i++) {
			long long to = x[a2][i].first, cost = x[a2][i].second, height = dist[a2].second - cost;
			if (height < 0) { cost -= height; height = 0; }
			if (height > H[to]) { cost += (height - H[to]); height = H[to]; }
			if (dist[to] > make_pair(a1 + cost, height)) {
				dist[to] = make_pair(a1 + cost, height);
				Q.push(make_pair(dist[to].first, to));
			}
		}
	}
}
int main() {
	cin >> n >> m >> h; for (int i = 1; i <= n; i++)cin >> H[i];
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		if (H[a[i]] >= c[i])x[a[i]].push_back(make_pair(b[i], c[i]));
		if (H[b[i]] >= c[i])x[b[i]].push_back(make_pair(a[i], c[i]));
	}
	dijkstra();
	long long J = dist[n].first + (H[n] - dist[n].second);
	if (J >= 1000000000000000LL)J = -1;
	cout << J << endl;
	return 0;
}

Measured memory_bytes: 30212
func readIntArray() -> [Int] {
    readLine()!.split(separator: " ").map({Int($0)!})
}


let N = Int(readLine()!)!
let a = readIntArray()
var total = 0
a.forEach({
    total ^= $0
})
a.forEach({
    print(total ^ $0, terminator: " ")
})


Measured memory_bytes: 21476
#include<iostream> 
#include<algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e6+100;
const long long INF = 999999999999;
long long dis[N][3];
vector<int> G[N];
bool vis[N][3];
struct node{
    int id;
    int  dis;
};
int n,m,S,T;
queue<node> q;
void dijkstra(int S){
    for(int i=1;i<=n+100;i++){
        for(int j=0;j<3;j++) dis[i][j]=INF,vis[i][j]=0;
    }
    dis[S][0]=0;
    q.push({S,0});
    while(!q.empty()){
        node rt=q.front();q.pop();
        int u=rt.id;
        int L=rt.dis;
        if(vis[u][L]) continue;
        vis[u][L]=1;
        for(auto v:G[u]){
            int nowL=(L+1)%3;
            if(dis[v][nowL]>dis[u][L]+1){
                dis[v][nowL]=dis[u][L]+1;
                q.push({v,nowL});
            }
        }
    }
}
int main(){
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        G[u].push_back(v);
    }
    cin>>S>>T;
    dijkstra(S);
    //cout<<dis[T][0]<<endl;
    if(dis[T][0]==INF) puts("-1");
    else cout<<dis[T][0]/3<<endl;
    return 0;
}



Measured memory_bytes: 34680
N = int(input())

tmps = []
tmps.append(list(map(int,input().split())))
tmps.append(list(map(int,input().split())))

As = [[0 for _ in range(N+1)] for _ in range(3)]
for r in range(2):
	for c in range(N):
		As[r][c] = tmps[r][c]
		
#print(As)

sums = [[-1 for _ in range(N+1)] for _ in range(3)]
sums[0][0] = As[0][0]

for r in range(2):
	for c in range(N):
		if sums[r+1][c] < As[r+1][c] + sums[r][c]:
			sums[r+1][c] = As[r+1][c] + sums[r][c]
			
		if sums[r][c+1] < As[r][c+1] + sums[r][c]:
			sums[r][c+1] = As[r][c+1] + sums[r][c]
			
		#print(sums)
			
print(sums[1][N-1])

Measured memory_bytes: 38384
#include <bits/stdc++.h>
//For ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MOD 1000000007
#define test int t; cin>>t; while(t--)
#define init(arr,val) memset(arr,val,sizeof(arr))
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopr(i,a,b) for(int i=a;i>=b;i--)
#define loops(i,a,b,step) for(int i=a;i<b;i+=step)
#define looprs(i,a,b,step) for(int i=a;i>=b;i-=step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define PLL pair<long long, long long>
#define PII pair<int, int>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define all(a) a.begin(),a.end()
#define ld long double
using namespace std;
// For ordered_set
using namespace __gnu_pbds;
template <typename T>
using ord_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll maxn = 1e5;
const ll inf = 1e9;
const double pi = acos(-1);

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

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

#define FOR(i,n) for(int i=0;i<n;i++)
#define PRINT(a) cout<<a<<"\n"
 
int main(){

	char a;

	cin>>a;

	if(a=='a'||a=='e'||a=='i'||a=='o'||a=='u')PRINT("vowel");
	else PRINT("consonant");

	return 0;
}

Measured memory_bytes: 256
unittest
{
	assert( [ "4 5", "5 1 3 4 2", "2 5 3 1 4", "2 3 1 4 5", "2 5 4 3 1" ].parse.expand.solve == 2 );
	assert( [ "3 3", "2 1 3", "2 1 3", "2 1 3" ].parse.expand.solve == 3 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nm = input.front.split.to!( long[] );
	auto ass = new long[][]( nm[ 0 ], nm[ 1 ] );
	foreach( ref as; ass )
	{
		input.popFront;
		as = input.front.split.to!( long[] );
		as[] -= 1;
	}
	return tuple( nm[ 1 ], ass );
}

auto solve( long m, long[][] ass )
{
	auto ans = long.max;
	auto bs = new bool[ m ];
	LOOP: while( true )
	{
		// 最大参加人数を計算
		long cm = 0L;
		long[ long ] cs;
		foreach( as; ass )
		{
			while( !as.empty && bs[ as.front ] ) as.popFront;
			if( as.empty ) break LOOP;
			cs[ as.front ]++;
			cm = max( cm, cs[ as.front ] );
		}
		ans = min( ans, cm );
		
		// 参加人数が最大のスポーツを中止にする
		foreach( k, c; cs )
		{
			bs[ k ] = ( c == cm );
		}
	}
	return ans;
}


Measured memory_bytes: 4988
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//(a+b-1)/b

signed main(){
	ll n; cin>>n;
	cout<<n*(n+1)/2-n<<endl;
	
	return 0;
}

Measured memory_bytes: 3648
#include<cstdio>
int main(void){int r,c,e[101][101]={0},i,j;scanf("%d%d",&r,&c);for(i=0;i<r;++i){for(j=0;j<c;++j){scanf("%d",&e[i][j]);}}for(i=0;i<r;++i){for(j=0;j<c;++j){e[i][c]+=e[i][j];e[r][j]+=e[i][j];}e[r][c]+=e[i][c];}for(i=0;i<r+1;++i){for(j=0;j<c+1;++j){printf("%d",e[i][j]);if(j!=c){printf(" ");}}puts("");}return(0);}



Measured memory_bytes: 2744
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define LL long long
#define MAXN 600
#define INF 100000000000000000
#define DB double
#define PI acos(-1.0)
int n,m;
int u[MAXN+5],v[MAXN+5],tmp;
DB f[MAXN+5],ans;
vector<int> G[MAXN+5];
LL read(){
  LL x=0,F=1;char c=getchar();
  while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}
  while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
  return x*F;
}
DB del(int x){
  f[n]=1;
  for(int i=n-1;i>=1;i--){
      f[i]=0;
      int siz=G[i].size(),id=i;
      DB mx=0;
      for(int k=0;k<siz;k++){
          int pre=G[i][k];
          f[i]+=f[pre];
          mx=max(mx,f[pre]);
      }
      if(siz>=2&&x==i){
        f[i]-=mx;
        siz--;
      }
      f[i]=f[i]/siz+1;
  }
  return f[1]-1;
}
int main()
{
  n=read(),m=read();tmp=n+1;
  for(int i=1;i<=m;i++){
    int a=read(),b=read();
    G[a].push_back(b);
  }
  ans=del(0);
  for(int i=1;i<n;i++)
  ans=min(ans,del(i));
  printf("%.10f",ans);
}


Measured memory_bytes: 1408
#include <iostream>
using namespace std;
int main(){
  int n,q,y;cin>>n>>q;string s;const string S="kogakubu10gokan";
  int f=0;
  for(int i=0;i<n;i++){
    cin>>y;
    if(f) {cin>>s;continue;}
    if(i==0 && q<y) {cout<<S<<endl;cin>>s;f=1;}
    else if(q<y) {cout<<s<<endl;cin>>s;f=1;}
    else cin>>s;
  }
  if(!f) cout << s << endl;
  return 0;
}

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

int main() {
  string S;
  cin >> S;
  int ans = S.size(), sc = 0;
  for (int i = 0; i < S.size(); i++) {
    if (S[i] == 'S') sc++;
    else if (0 < sc && S[i] == 'T') {
      sc--;
      ans -= 2;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

int main()
{
  int N;
  cin >> N;
  vector<ll> vec(N);
  vector<ll> left(N+1, 0);
  vector<ll> right(N+1, 0);
  REP(i, N) {
    cin >> vec[i];
  }
  for (int i = 0; i < N; i++) {
    left[i+1] = gcd(left[i], vec[i]);
  }
  for (int i = N-1; 0 <= i; i--) {
    right[i] = gcd(right[i+1], vec[i]);
  }
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    ans = max(ans, gcd(left[i], right[i+1]));
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2560
from itertools import combinations

H , W , K = map(int, input().split())
C = []

for i in range(H):
	C.append(input())#C[i-1][j-1]でi行j列指定できる。

count = 0
Count = 0


#行、列いずれも1~H-1,W-1個選ぶ。
for k in range(1,H):
	for l in range(1,W):
		for i in combinations(list(range(1,H+1)),k):
			for j in combinations(list(range(1,W+1)),l):		
				count = 0
				for m in range(1,H+1):
					for n in range(1,W+1):
						if not(m in i) and not(n in j) and C[m-1][n-1] == '#':
							count += 1
				if K == count:
					Count += 1

#行のみ選ぶ、
for k in range(1,H):
	for i in combinations(list(range(1,H+1)),k):
		count =0
		for m in range(1,H+1):
			for n in range(1,W+1):
				if not(m in i) and C[m-1][n-1] == '#':
					count += 1
		if K == count:
			Count += 1

#列のみ選ぶ。
for l in range(1,W):
	for j in combinations(list(range(1,W+1)),l):
		count = 0
		for m in range(1,H+1):
			for n in range(1,W+1):
				if not(n in j) and C[m-1][n-1] == '#':
					count += 1
		if K == count:
			Count += 1


#一つも選ばない
count = 0 
for m in range(1,H+1):
	for n in range(1,W+1):
		if C[m-1][n-1] == '#':
			count += 1
if K == count:
	Count += 1





print(Count)
						




Measured memory_bytes: 9328
#include<cstdio>
#include<iostream>
#include<cmath>

using namespace std;

#define PI  3.14159265358979323846264338327950288 
int main(void){

	int n,s[10000],sum;
	double ave,sta;

	while(1){
		cin>>n;
		if(n==0) break;
		sum=0,ave=0,sta=0;
		for(int i=0;i<n;i++){
			cin>>s[i];
			sum+=s[i];
		}
		ave=(double)sum/n;
		for(int i=0;i<n;i++){
			sta+=pow((double)s[i]-ave,2.0);
		}
		sta=sqrt((double)sta/n);
		printf("%.8f\n",sta);
	}

	return 0;
}

Measured memory_bytes: 1200
//

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define irep(i,a) for(auto i = a.begin(); i != a.end(); ++i)
#define nvarep(n,a) ll n;cin>>n;vector<ll>a(n);rep(i,0,n)cin>>a[i]
#define vecrep(n,a,type) vector<type>a(n);rep(i,0,n)cin>>a[i]
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
using p = pair<ll, string>;
using garph = vector<vector<ll>>;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

signed main (){
    nvarep(n,a);
    int ans=0;
    rep(i,0,n){
        while(i<n-1&&a[i]==a[i+1])i++;
        if(i<n-1&&a[i]<a[i+1]){
            while(i<n-1&&a[i]<=a[i+1])i++;
        }else if(i<n-1&&a[i]>a[i+1]){
            while(i<n-1&&a[i]>=a[i+1])i++;
        }
        ans++;
    }
    cout<<ans<<nnn;
    return 0;
}

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

using namespace std;

int main(){
    long long int N,ans=0;
    bool remain = false;
    cin >> N;
    vector<long long int> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
    }

    for(int i=0;i<N;i++){
        if(remain && 0<A[i]){
            ans++;
            A[i]--;
        }
        
        ans += A[i]/2;

        if(A[i]%2==1){
            remain = true;
        }else{
            remain = false;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
da  = int(input())

k = list(input())
p = [0]*da
for i in range(da):
  if k[i] == "E" and i < da -1:
    p[i+1] += 1
  elif k[i] == "W":
    p[0] += 1
    p[i] -= 1

for i in range(1,da):
  p[i] += p[i-1]

k = max(p)
if max(p) != p[0] or max(p) != p[da-1]:
  k += 1
print(da - k)

Measured memory_bytes: 66032
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
#define endl '\n'
using namespace std;

int dig(int num){
    if(num <= 9) return num;
    int res = 0;
    while(num){
        res += num % 10;
        num /= 10;
    }
    return res;
}

int main(){
    int n, a, b;
    cin >> n >> a >> b;
    int sum = 0;
    for(int i=1; i<=n; i++){
        int temp = dig(i);
        if(temp>=a && temp<=b)
            sum += i;
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define N 500
#define INFTY 10000000
#define BLACK 0
#define GRAY 1
#define WHITE 2

int a;
int G[N][N];
int d[N];
int p[N];
int color[N];
int sum[N];

void change()
{
	int i,j,k,u,v,c;
	for (i = 0; i < N; i++) {
		color[i] = WHITE;
		d[i] = INFTY;
		p[i] = -1;
	}
	d[0] = 0;

	while (1)
	{
		int minCost = INFTY;
		for (i = 0; i < a; i++) {
			if (color[i] != BLACK && d[i] < minCost) {
				minCost = d[i];
				u = i;
			}
		}

		if (minCost == INFTY) break;
		
		color[u] = BLACK;
		
		for (i = 0; i < N; i++) {
			if (G[u][i] != INFTY && color[i] != BLACK) {
				if (d[u] + G[u][i] < d[i]) {
					color[i] = GRAY;
					d[i] = d[u] + G[u][i];
					p[i] = u;
				}
			}			
		}
	}
}


int main()
{
	int i, j, k, u, v, c;
	scanf("%d", &a);
	for (i = 0; i < a; i++)
		for (j = 0; j < a; j++)
			G[i][j] = INFTY;
	for (i = 0; i < a; i++) {
		scanf("%d", &u);
		scanf("%d", &k);
		for (j = 0; j < k; j++) {
			scanf("%d %d", &v, &c);
			G[u][v] = c;
		}
	}
	change();
	for (i = 0; i < a; i++) 
		printf("%d %d\n", i, d[i]);
	return 0;
}



Measured memory_bytes: 2104
import sys
a,b,c = map(int,input().split())
k = int(input())

for i in range(k):
    if a >= b:
        b = 2 * b
        continue
    if b >= c:
        c = 2 * c
        continue
if a < b and b < c:
        print('Yes')
else:
    print('No')

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

typedef struct {
	double x, y, z, r;
} Coord;

typedef struct {
	int from, to;
	double weight;
} Edge;

Coord coord[ 100 ];
int node[ 100 ];
Edge edge[ 4950 ];

int compare( const void *a, const void *b ) {
	double at = (*(Edge *)a).weight, bt = (*(Edge *)b).weight;

	if ( at < bt )
		return -1;
	if ( at > bt )
		return 1;
	return 0;
}

int find( int x ) {
	if ( node[ x ] == x )
		return x;
	else
		return node[ x ] = find( node[ x ] );
}

int main( void ) {
	int i, j;
	int n;

	while ( scanf( "%d", &n ), n ) {
		int cnt;
		double sum;

		for ( i = 0; i < n; i++ )
			scanf( "%lf %lf %lf %lf", &coord[ i ].x, &coord[ i ].y, &coord[ i ].z, &coord[ i ].r );

		cnt = 0;
		for ( i = 0; i < n; i++ )
			for ( j = i + 1; j < n; j++ ) {
				double x = coord[ i ].x - coord[ j ].x, y = coord[ i ].y - coord[ j ].y, z = coord[ i ].z - coord[ j ].z;

				edge[ cnt ].from = i;
				edge[ cnt ].to = j;
				edge[ cnt ].weight = fmax( sqrt( x * x + y * y + z * z ) - coord[ i ].r - coord[ j ].r, 0.0 );
				cnt++;
			}
		qsort( edge, cnt, sizeof(Edge), &compare );

		for ( i = 0; i < n; i++ )
			node[ i ] = i;

		sum = 0.0;
		for ( i = 0; i < cnt; i++ ) {
			int set1 = find( edge[ i ].from ), set2 = find( edge[ i ].to );
			if ( set1 != set2 ) {
				node[ set2 ] = set1;
				sum += edge[ i ].weight;
			}
		}

		printf( "%.3f\n", sum );
	}

	return 0;
}

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>

#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;


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

	vector<long long int> a(n), b(n), c(n);
	rep(i, n){
		cin >> a[i];
	}
	rep(i, n){
		cin >> b[i];
	}
	rep(i, n){
		cin >> c[i];
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	sort(c.begin(), c.end());

	long long int ans = 0;
	rep(i, n){
		long long int cnt_a = 0;
		long long int cnt_c = 0;

		cnt_a = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
		cnt_c = c.end() - upper_bound(c.begin(), c.end(), b[i]);

		ans += cnt_a * cnt_c;
	}

	cout << ans << endl;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define eps 0.000000001
using namespace std;
typedef long double ld;
typedef pair<int,int> p;
typedef pair<ld,p> P;

int n;
ld px[200],py[200],pz[200],vx[200],vy[200],vz[200],r[200],vr[200];

ld getlen(int a,int b,ld M){
  ld ax=px[a]+vx[a]*M,ay=py[a]+vy[a]*M,az=pz[a]+vz[a]*M,ar=r[a]-vr[a]*M;
  ld bx=px[b]+vx[b]*M,by=py[b]+vy[b]*M,bz=pz[b]+vz[b]*M,br=r[b]-vr[b]*M;
  ld dx=ax-bx,dy=ay-by,dz=az-bz;
  return sqrt(dx*dx+dy*dy+dz*dz)-(ar+br);
}

ld check(int a,int b){
  ld mt=min(r[a]/vr[a],r[b]/vr[b]);
  ld L=0,R=mt,M;
  int s=0;
  while(s++<50){
    M=(L+R)/2;
    ld len=getlen(a,b,M),len1=getlen(a,b,M+eps);
    if(len<len1||len<0)R=M;
    else L=M;
  }
  if(getlen(a,b,R)>0)return 1000;
  return R;
}

int main(){
  while(cin>>n,n){
    for(int i=0;i<n;i++)
      cin>>px[i]>>py[i]>>pz[i]>>vx[i]>>vy[i]>>vz[i]>>r[i]>>vr[i];
    priority_queue<P,vector<P>,greater<P> > q;
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++)
	q.push(P(check(i,j),p(i,j)));
      q.push(P(r[i]/vr[i],p(i,i)));
    }
    ld used[200]={};
    while(!q.empty()){
      ld t=q.top().first;
      int a=q.top().second.first,b=q.top().second.second;
      q.pop();
      if(used[a]||used[b])continue;
      used[a]=used[b]=t;
    }
    for(int i=0;i<n;i++)printf("%.10Lf\n",used[i]);
  }
  return 0;
}

Measured memory_bytes: 4460
def search(x,r):
  low = 0
  high = len(r) - 1
  while low < high:
    mid = (low+high)//2
    if x < r[mid]:
      high = mid
    else:
      low = mid + 1
  return(abs(r[low-1]-x),abs(r[low]-x))
      
a, b, q = [int(i) for i in input().split()]
s = [-float('inf')] + [int(input()) for _ in range(a)] + [float('inf')]
t = [-float('inf')] + [int(input()) for _ in range(b)] + [float('inf')]
x = [int(input()) for _ in range(q)]

for xx in x:
  
  s_l,s_r=search(xx,s)
  t_l,t_r=search(xx,t)
  
  if s_l <= t_l:
    l = t_l
    lr = s_l*2 + t_r
  else:
    l = s_l
    lr = t_l*2 + s_r
  if s_r <= t_r:
    r = t_r
    rl = s_r*2 + t_l
  else:
    r = s_r
    rl = t_r*2 + s_l
 
  ans = min(l,r,lr,rl)
  print(ans)
  

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

const double PI = acos(-1.0);
int main() {
    double A, B, H, M;
    cin >> A >> B >> H >> M;
    double alpha = (H * 60 + M) / 720 * (PI * 2);
    double beta = M / 60 * (PI * 2);
    double theta = alpha - beta;
    double res = sqrt(A*A + B*B - 2.0*A*B*cos(theta));
    cout << fixed << setprecision(10) << res << endl;
}

Measured memory_bytes: 4184
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define INF 100000000
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define repp(i,n,s) for (int i= (int)(n); i >= (int)(s); i--)
#define mp make_pair
ll mod = 1000000007;
ll mod2 = 998244353;

int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,d;cin>>n>>d;
    ll ans = 0;
    rep(i,0,n){
        ll x,y;cin>>x>>y;
        if (x*x+y*y<=d*d){
            ans++;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const ll b   = 1069;

ll mpow(ll x,ll n){
    ll res = 1;
    while(n != 0){
        if(n&1) res = res*x % mod;
        x = x*x % mod;
        n = n >> 1; 
    }
    return res;
}

// s0中のs1を探す
void search_hash(string s0,string s1,vector<bool> &v){
    ll l0 = s0.size(),l1 = s1.size();
    ll h0 = 0,h1 = 0,bp = mpow(b,s1.size());

    if(l0<l1) return ;

    for(int i = 0;i < l1;i ++){
        h0 = (h0*b+s0[i])%mod;
        h1 = (h1*b+s1[i])%mod;
    }
    for(int i = 0;i+l1 <= l0;i ++){
        if(h0==h1)          v[i] = true;
        if(i+l1<s0.size())  h0 = (h0*b+s0[i+l1]-s0[i]*bp%mod+mod)%mod;
    }
}

int main(){
    string s0,s4,t;
    cin >> s0 >> t;
    string s = s0;
    while(s.size()<t.size()) s = s+s;
    s4 = s+s+s+s;

    vector<bool> v(s4.size()-t.size()+1,0);
    int ans = 0;
    vector<int> dp(v.size(),0);

    search_hash(s4,t,v);
    for(int i = 0;i < v.size();i ++){
        if(i>=t.size()&&v[i])   dp[i] = dp[i-t.size()]+v[i];
        else                    dp[i] = v[i];

        if(ans<dp[i]){
            if(i>=s.size()*2) {ans = -1;break;}
            ans = dp[i];
        }
    }
    cout << ans << endl;
    return 0;
}


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

int n;
int x[24],y[24],r[24],c[24];
bool memo[1<<24];

bool ok(int a,int bit){
    for(int i=0;i<a;i++){
        if(((bit>>i)&1)==0)continue;
        int dist=(x[i]-x[a])*(x[i]-x[a])+(y[i]-y[a])*(y[i]-y[a]);
        int sum=(r[i]+r[a])*(r[i]+r[a]);
        if(dist<sum)return false;
    }
    return true;
}

int dfs(int bit){
    memo[bit]=true;

    int ret=n;
    for(int i=0;i<n;i++)if((bit>>i)&1)ret--;

    for(int i=0;i<n;i++){
        if(((bit>>i)&1)==0)continue;
        for(int j=i+1;j<n;j++){
            
            if(((bit>>j)&1)==0)continue;
            int to_bit=(bit^(1<<i))^(1<<j);
            if(c[i]==c[j]&&ok(i,bit)&&ok(j,bit)&&!memo[to_bit]){
                ret=max(ret,dfs(to_bit));
            }
        }
    }


    return ret;
}

void solve(){
    fill_n(memo,1<<n,false);

    cout<<dfs((1<<n)-1)<<endl;
}

bool input(){
    cin>>n;
    if(!n)return false;
    for(int i=0;i<n;i++)cin>>x[i]>>y[i]>>r[i]>>c[i];
    return true;
}



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

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;


#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};

template< int mod >
struct ModInt {
  int x;

  ModInt() : x(0) {}

  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

  ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }

  ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }

  ModInt &operator*=(const ModInt &p) {
    x = (int) (1LL * x * p.x % mod);
    return *this;
  }

  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

  bool operator==(const ModInt &p) const { return x == p.x; }

  bool operator!=(const ModInt &p) const { return x != p.x; }

  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }

  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }

  static int get_mod() { return mod; }
};

using modint = ModInt< (int)1e9+7 >;

int main()
{
    ll n,k;
    cin>>n>>k;
    vector<modint> sigma2(n+10);
    for (int i = 1; i < n+5; i++)
    {
        sigma2[i]=sigma2[i-1]+i*2;
        //cout<<i<<"  "<<sigma2[i]<<endl;//
    }
    modint ans=0;
    for (int i = k; i <= n+1; i++)
    {
        //cout<<i<<" "<<modint(i)*n-sigma2[i-1]+1<<endl;//
        ans+=modint(i)*n-sigma2[i-1]+1;
    }
    cout<<ans<<endl;
    
    return 0;
}

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

int main(){
	int eh,em,es,oh,om,os;
	for(int i=0;i<3;i++){
		scanf("%d%d%d%d%d%d",&eh,&em,&es,&oh,&om,&os);
		os-=es; om-=em; oh-=eh;
		if(os<0){os+=60; om--;}
		if(om<0){om+=60; oh--;}
	printf("%d %d %d\n",oh,om,os);
	}
}

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

// macros
#define overload_rep(_1, _2, _3, name, ...) name
#define re_p(i, n) for(int i = 0; i < (n); ++i)
#define r_ep(i, x, y) for(int i = (x); i <= (y); ++i)
#define rep(...) overload_rep(__VA_ARGS__, r_ep, re_p)(__VA_ARGS__)
#define all(a) a.begin(), a.end()
#ifndef STOP_DEBUG
#define debug(...)\
    do { cerr << boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_cerr(__VA_ARGS__); cerr << noboolalpha; } while (0)
#else
#define debug(...)
#endif

// functions
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
void debug_cerr(){ cerr << '\n'; }
template<class Head, class... Tail>
void debug_cerr(Head head, Tail... tail){
    cerr << ' ' << head;
    debug_cerr(tail...);
}

// cin/cout setup
struct IoSetup{
    IoSetup(){
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} iosetup;

// libraries
struct UnionFind{
private:
    int comp;
    vector<int> par, rank;
public:
    inline UnionFind(){}
    inline UnionFind(int sz){ init(sz); }
    inline void init(int sz){
        comp = sz;
        par.resize(sz, -1);
        rank.resize(sz, 0);
    }
    inline int find(int x){
        if(par[x] < 0)return x;
        else return par[x] = find(par[x]);
    }
    inline int size(int x){
        return -par[find(x)];
    }
    inline int size(){
        return int(par.size());
    }
    inline int component(){
        return comp;
    }
    inline bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y)return false;
        if(rank[x] < rank[y])swap(x, y);
        if(rank[x] == rank[y])rank[x]++;
        par[x] += par[y];
        par[y] = x;
        comp--;
        return true;
    }
    inline bool same(int x, int y){
        return find(x) == find(y);
    }
};

// declarations

// solve
int main(){

    int N;
    cin >> N;
    vector<pair<int, int>> ba(N);
    rep(i, N)cin >> ba[i].second;
    rep(i, N)cin >> ba[i].first;
    sort(all(ba));

    vector<int> ord(N);
    iota(all(ord), 0);
    sort(all(ord), [&](int i, int j){
        return ba[i].second < ba[j].second;
    });

    rep(i, N){
        if(ba[ord[i]].second > ba[i].first){
            cout << "No\n";
            return 0;
        }
    }

    UnionFind uni(N);
    rep(i, N)uni.unite(i, ord[i]);
    if(uni.component() > 1){
        cout << "Yes\n";
        return 0;
    }

    rep(k, N - 1){
        int i = ord[k + 1];
        if(ba[i].second <= ba[k].first){
            cout << "Yes\n";
            return 0;
        }
    }

    cout << "No\n";
    return 0;

}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
vector<int>v;
int a[N],b[N],n,ans;
int main(){
	//freopen("input.txt","r",stdin);
	scanf("%d",&n);
	for(int i = 0;i < n;i++)scanf("%d",a + i);
	for(int i = 0;i < n;i++)scanf("%d",b + i);
	for(int log = 1;log < 3e8;log<<=1){
		for(int i = 0;i < n;i++)v.push_back(b[i]%(log<<1));
		sort(v.begin(),v.end());
		bool temp = 0;
		for(int i = 0;i < n;i++){
			int val = a[i]%(log<<1);
			temp ^= ((upper_bound(v.begin(),v.end(),2*log - 1 - val) - v.begin()) - (lower_bound(v.begin(),v.end(),log - val) - v.begin()))&1;
			temp ^= ((upper_bound(v.begin(),v.end(),4*log - 1 - val) - v.begin()) - (lower_bound(v.begin(),v.end(),3*log - val) - v.begin()))&1;
		}
		v.clear();
		ans+=temp*log;
	}
	cout << ans << endl;
}

Measured memory_bytes: 2936
import math
n=int(input())
X=[0]*(10**6+1)
if n==1:
    ans=0
else:
    p=int(math.sqrt(n))
    for i in range(2,int(math.sqrt(n)+1)):
        cnt=0
        while n%i==0:
            n//=i
            cnt+=1
        X[i]=cnt
    ans=0
    for x in X:
        if x>=55:
            ans+=10
        elif x>=45:
            ans+=9
        elif x>=36:
            ans+=8
        elif x>=28:
            ans+=7
        elif x>=21:
            ans+=6
        elif x>=15:
            ans+=5
        elif x>=10:
            ans+=4
        elif x>=6:
            ans+=3
        elif x>=3:
            ans+=2
        elif x>=1:
            ans+=1

    if n!=1:
        ans+=1

print(ans)

Measured memory_bytes: 72676
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
class Program
{
    static void Main(string[] args)
    {
            // 入力
            string[] sS = System.Console.ReadLine().Trim().Split(' ');
            int iN = int.Parse(sS[0]);
            int iM = int.Parse(sS[1]);
            sS = System.Console.ReadLine().Trim().Split(' ');

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析
            int iSum = 0;
            for (int i = 0; i < sS.Length; i++)
            {
                iSum += int.Parse(sS[i]);
            }
            int iOut = iN - iSum;
            if (iOut < 0) { iOut = -1; }

            // 出力
            System.Console.WriteLine("{0}", iOut.ToString().Trim());

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }

}


Measured memory_bytes: 28252
using System;

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            double ans = 0;
            if (n % 2 == 0)
            {
                ans = 0.5;
            }
            else
            {
                int temp = n/2;
                ans = (double)(temp+1)/n;
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 27584