akhauriyash/Code-Regression huggingface dataset:
N = int(input())

alist = list(map(int,input().split()))

alist.sort()

# print(alist)

mod = (10**9 + 7)

if N % 2 == 1:
    alist.pop(0)
    for i in range(N//2):
        # print('it', alist[i*2], 2*(i + 1), alist[i*2 + 1], 2*(i + 1))
        if alist[i*2] != 2*(i + 1) or alist[i*2 + 1] != 2*(i + 1):
            print(0)
            exit(0)
    print(2**(N//2)%mod)
else:
    for i in range(N//2):
        # print('it', alist[i*2], 2*(i + 1), alist[i*2 + 1], 2*(i + 1))
        if alist[i*2] != 2*i + 1 or alist[i*2 + 1] != 2*i + 1:
            print(0)
            exit(0)
    print(2**(N//2)%mod)


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

int main(){
	char b;
	cin >> b;
	if(b == 'A' || b == 'T')
		cout << (b == 'A' ? 'T' : 'A') << endl;
	else
		cout << (b == 'C' ? 'G' : 'C') << endl;

	return 0;
}


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

int main() {
  int N;
  cin >> N;
  int c=4,d=7;
  for(int i=0;i<30;i++){
    for(int j=0;j<20;j++){
      if(N == i*c+j*d){
        //cout << i<<j << endl;
         cout << "Yes" << endl;
         return 0;
      }
    }
  }


 cout << "No" << endl;
  }


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	// AtCoder Beginner Contest 121
	// https://atcoder.jp/contests/abc121/tasks
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		int m = sc.nextInt();
		int c = sc.nextInt();
		int[] b = new int[m];
		int res = 0;
		
		for (int i = 0; i < m; i++) {
			b[i] = sc.nextInt();
		}
		
		for (int i = 0; i < n; i++) {
			int total = 0;
			int[] k = new int[m];
			for (int j = 0; j < m; j++) {
				k[j] = sc.nextInt();
			}
			
			for (int l = 0; l < m; l++) {
				total += (k[l] * b[l]);
			}
			if (total + c > 0) { 
				res++;
			}
		}
		
		System.out.println(res);
	}
	
	static class FastReader { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine()); 
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() { 
            String str = ""; 
            try{ 
                str = br.readLine(); 
            } catch (IOException e) { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
}


Measured memory_bytes: 22484
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <tuple>
#include <numeric>

using namespace std;

typedef long long ll;

int main(void){
    string str;
    cin >> str;
    ll cnt = 0;
    for(ll i = 0;i < 3;i++){
        cnt = str[i] == '1' ? cnt + 1 : cnt;
    }
    cout << cnt << endl;
    return 0;

}


Measured memory_bytes: 256
object Main {
  def main(args: Array[String]): Unit = {
    solve
  }

  def solve(): Unit = {
    val sc = new java.util.Scanner(System.in)
    val s = sc.nextLine.toCharArray.zipWithIndex

    var count1 = 0
    var count2 = 0
    for (i <- 0 until s.size) {
      if (s(i)._2 % 2 == 0) {
        if (s(i)._1 != '0') count1 += 1
      } else {
        if (s(i)._1 != '1') count1 += 1
      }

      if (s(i)._2 % 2 == 0) {
        if (s(i)._1 != '1') count2 += 1
      } else {
        if (s(i)._1 != '0') count2 += 1
      }
    }

    println(math.min(count1, count2))
  }
}


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

const int N = (int) 2e5 + 5;
const long long INF = (long long) 1e18;

int n;
int a[N];
long long s[N];

long long sum(int i, int j) {
	return s[j] - s[i - 1];
}

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	int l = 1, r = 3;
	long long res = INF;
	for (int i = 2; i <= n - 2; i++) {
		while (l + 1 < i && abs(sum(1, l) - sum(l + 1, i)) > abs(sum(1, l + 1) - sum(l + 2, i))) l++;
		r = max(r, i + 1);
		while (r + 1 < n && abs(sum(i + 1, r) - sum(r + 1, n)) > abs(sum(i + 1, r + 1) - sum(r + 2, n))) r++;
		long long mi = min({sum(1, l), sum(l + 1, i), sum(i + 1, r), sum(r + 1, n)});
		long long ma = max({sum(1, l), sum(l + 1, i), sum(i + 1, r), sum(r + 1, n)});
		res = min(res, ma - mi);
	}
	cout << res;
	return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
using ll = long long;

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

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

    vector<int> a(n, 0);
    int r[2] = {};
    for (int i = 0; i < m; i++) {
        int p;
        char s[3];
        cin >> p >> s;
        p--;

        if (a[p] < 0) continue;
        if (s[0] == 'A') {
            r[0]++;
            r[1] += a[p];
            a[p] = -1;
        } else {
            a[p]++;
        }
    }

    cout << r[0] << ' ' << r[1] << endl;

    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1);
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; }

template<int MOD> struct modint {
    long long val;
    constexpr modint(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr modint operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr modint operator + (const modint& r) const noexcept { return modint(*this) += r; }
    constexpr modint operator - (const modint& r) const noexcept { return modint(*this) -= r; }
    constexpr modint operator * (const modint& r) const noexcept { return modint(*this) *= r; }
    constexpr modint operator / (const modint& r) const noexcept { return modint(*this) /= r; }
    constexpr modint& operator += (const modint& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr modint& operator -= (const modint& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr modint& operator *= (const modint& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr modint& operator /= (const modint& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const modint& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const modint& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const modint<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr modint<MOD> modpow(const modint<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};
using mint = modint<MOD>;

int main() {
    ll n, m; cin >> n >> m;
    vector<ll> x(n), y(m);
    rep(i, n) cin >> x[i];
    rep(i, m) cin >> y[i];

    mint sx = 0, sy = 0;
    rep(i, n) {
        sx += mint(x[i]) * mint(i - (n - 1 - i));
    }
    rep(i, m) {
        sy += mint(y[i]) * mint(i - (m - 1 - i));
    }
    cout << sx * sy << endl;
}


Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#include<queue>
#define ll long long
#define itn int
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
#define MAX 510000
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
using namespace std;

int selectionSort(int A[],int N){
    int i,j,t,sw=0,minj;
    for(int i=0; i<N-1; ++i){
        minj=i;
        for(int j=i; j<N; ++j){
            if(A[j]<A[minj]) minj=j;
        }
        t=A[i];
        A[i]=A[minj];
        A[minj]=t;
        if(i!=minj) sw++;
    }
    return sw;
}

int main(){
    int A[100],N,i,sw;
    
    scanf("%d",&N);
    for(int i=0; i<N; ++i) scanf("%d",&A[i]);
    
    sw=selectionSort(A,N);
    
    for(int i=0; i<N; ++i){
        if(i>0) printf(" ");
        printf("%d",A[i]);
    }
    printf("\n");
    printf("%d\n",sw);
    
    return 0;
}


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

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

	for(int i=n;i>0;i--){
		int j=2, sum=ans[i];
		while(i*j<=n){
			sum+=ans[i*j];
			j++;
		}
		if(sum%2 != a[i]%2) ans[i]=1;
		else ans[i]=0;
	}

	int sum=0;
	for(int i=1;i<=n;i++) if(ans[i]) sum++;

	bool flag=true;
	if(sum%2 != a[1]) flag=false;

	if(flag==true){
		if(sum){
			cout<<sum<<endl;
			for(int i=1;i<=n;i++){
				if(ans[i]){
					cout<<i<<" ";
				}
			}
			cout<<endl;
		}else{
			cout<<0<<endl;

		}
	}else{
		cout<<-1<<endl;
	}



	return 0;
}


Measured memory_bytes: 2432
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAX_N 5001


/* -----------------------------------------------------------------------------
	型とクラス定義
----------------------------------------------------------------------------- */

/* -----------------------------------------------------------------------------
	大域データ
----------------------------------------------------------------------------- */
int N;			// 文字列長
char s[MAX_N];	// 文字列


int main () {

	int skip = 1, len = 0;

	// 個数の読込み
	scanf("%d %s", &N, s);
	// 
	for(int i = 0; i + 2 * len < strlen(s); i ++) {
		int j = i + len + 1;
		while(j + len < strlen(s)) {
			int cnt = 0;
			while(i + cnt < j && j + cnt < strlen(s) && s[i + cnt] == s[j + cnt]) cnt++;
			len = std::max(len, cnt);	// 最長長さ更新
			skip = std::max(skip, cnt);
			j ++;
		}
	}

	printf("%d\n", len);

	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
public static class P
{
    public static void Main()
    {
        var nk = Console.ReadLine().Split().Select(long.Parse).ToArray();
        var k = nk[1];
        var n = nk[0] % k;
        Console.WriteLine(Min(n, k - n));
    }
}

Measured memory_bytes: 28196
n,W=map(int,input().split())
x=[0]+[-1]*W

for i in range(n):
    w,v=map(int,input().split())

    for j in range(W-w,-1,-1):
        if x[j]>=0:
            x[j+w]=max(x[j+w],x[j]+v)

print(max(x))

Measured memory_bytes: 41824
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
    
    // 1. 入力情報.
    LL H, W;
    scanf("%lld %lld", &H, &W);
    
    // 2. 移動可能なマスの個数.
    LL ans = H * W / 2;
    if(H * W % 2 == 1) ans++;
    
    // 3. H = 1, W = 1 の ケース.
    // ex.
    // 1 3
    // -> 1 のはず, 2 は 誤り.
    if(H == 1 || W == 1) ans = 1;
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

Measured memory_bytes: 256
import sys
import math

n=int(input())
a=n%100
b=math.floor(n/100)+1
f=True
while b != 0:
  for i in range(b):
    for j in range(b-i):
      for k in range(b-i-j):
        for l in range(b-i-j-k):
          for m in range(b-i-j-k-l):
            if i+2*j+3*k+4*l+5*m == a:
              print(1)
              sys.exit()
  a+=100
  b-=1
print(0)


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

int A[100005];

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

    int N, x;
    cin >> N >> x;

    long long ans = 0;

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

    for(int i=1; i<=N; i++)
    {
        int k = max(0, A[i] + A[i-1] - x);
        ans += k;
        A[i] -= k;
    }

    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 640
N,K = map(int,input().split())
R,S,P = map(int,input().split())
T = input()
ans = 0
memo = [0 for i in range(N)]
for i in range(N):
    check = T[i]
    if i >= K and T[i-K] == check and memo[i-K] == 0:
        memo[i] = 1
        continue
    if check == "r":
        ans += P
    elif check == "p":
        ans += S
    elif check == "s":
        ans += R
print(ans)

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

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

    int n;
    ll mod = 1e9 + 7;
    cin >> n;
    vector<ll> dp(1 << n);

    vector<vector<int>> a(n, vector<int>(n));
    rep(i, n) rep(j, n) cin >> a[i][j];
    dp[0] = 1;

    rep(s, 1 << n)
    {
        int m = s;
        int i = 0;
        while (m > 0)
        {
            i += m & 1;
            m >>= 1;
        }
        rep(j, n) if ((s >> j) & 1 && a[i - 1][j] == 1)
        {
            dp[s] = (dp[s] + dp[s ^ (1 << j)]) % mod;
        }
    }
    cout << dp[(1 << n) - 1] << endl;
    return 0;
}

Measured memory_bytes: 16640
// ACPC_sakenichia
// coder : naan

#include <bits/stdc++.h>

int main(){
    using namespace std;
    constexpr unsigned long MOD = 1000000007;
    unsigned long M;
    cin >> M;
    string C;
    cin >> C;
    if(M == 0 && C.size() == 1)return 0 & puts("0");
    unsigned long t = C[0] - '0';
    vector<unsigned long> cnt(10), dig{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    for(unsigned long i = 1, j = 1; i <= C.size(); ++i){
        (cnt[C[C.size() - i] - '0'] += j) %= MOD;
        (j *= 10) %= MOD;
    }
    do{
        if(!dig[t])continue;
        if(inner_product(dig.begin(), dig.end(), cnt.begin(), 0UL) % MOD == M){
            for(const auto& c : C)cout << dig[c - '0'];
            return 0;
        }
    }while(next_permutation(dig.begin(), dig.end()));
    puts("-1");
    return 0;
}


Measured memory_bytes: 3340
from itertools import permutations
N, M, R = map(int, input().split())
r = [int(c)-1 for c in input().split()]
cost = [[float('inf')]*N for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c
def warshall_floyd(d,n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
dist = warshall_floyd(cost,N)
ls = list(permutations(r))
ans = -1
for l in ls:
  m = 0
  p = l[0]
  flag = False
  for q in l[1:]:
    m += dist[p][q]
    p = q
  if ans==-1 or ans>m:
    ans = m
print(ans)

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

using namespace std;

int main() {
  	char str;
    cin >> str;
    if (str == 'a' || str == 'e' || str == 'i' || str == 'o' || str == 'u') {
    	puts("vowel");
    } else {
    	puts("consonant");
    }
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int a[]={0,1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main(){
	int k;
	scanf("%d",&k);
	printf("%d\n",a[k]);
	return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=55;
int dp[N][N][N][2];
int a[N],b[N],vis[N];
ll ans,tot;
int n,m,totS;

/*void DP(){
	memset(dp,0,sizeof(dp));
	dp[1][a[n]][n][0][0]=1;
	rep(i,1,m){
		rep(p,0,n-1) rep(S,0,totS) if(!(S>>p&1)){
			rep(j,i,m+1) rep(k,0,n) rep(opt,0,1) if(dp[i][j][k][S][opt]){
		 		curj=i+b[p];
		 		if(curj>j)	curk=p;
		 		else if(curj==j)	curk=max(p,k);
		 		else curk=k;
				curopt=opt|(p<k);
				curS=S|(1<<p);
				dp[i][curj][curk][curS][curopt]+=dp[i][j][k][S][opt];
			}
		}
		rep(j,i,m+1) rep(k,0,n) rep(S,0,totS) rep(opt,0,1) if(dp[i][j][k][S][opt]){
			if(opt||(j>i))	dp[i+1][j][k][S][0]+=dp[i][j][k][S][opt];
		}	
	}
}*/
		
void DP(){
	register int i,j,k,S,p,opt;
	register int curj,curk,curopt,curS;
	int ret=0;
	memset(dp,0,sizeof(dp));
	if(a[n]==1)	dp[a[n]][n][0][0]=1;
	else dp[a[n]][n][0][1]=1;
	rep(i,1,m){
		/*printf("%d:\n",i);
		rep(j,i,m+1) rep(k,0,n) rep(S,0,totS) rep(opt,0,1)	if(dp[j][k][S][opt]){
			printf("dp[%d][%d][%d][%d]=%d\n",j,k,S,opt,dp[j][k][S][opt]);
		}*/
		rep(p,0,n-1) rep(S,0,totS) if(!(S>>p&1)){
			rep(j,i,m+1) rep(k,0,n) rep(opt,0,1) if(dp[j][k][S][opt]){
		 		curj=min(i+b[p],m+1);
		 		if(curj>j)	curk=p;
		 		else if(curj==j)	curk=max(p,k);
		 		else curk=k;
		 		curj=max(curj,j);
				curopt=opt|(p<k);
				curS=S|(1<<p);
				dp[curj][curk][curS][curopt]+=dp[j][k][S][opt];
			}
		}
		rep(j,i,m+1) rep(k,0,n) rep(S,0,totS){
			//if(j==i)	dp[j][k][S][0]=0;
			//dp[j][k][S][0]+=dp[j][k][S][1];
			//dp[j][k][S][1]=0;
			dp[j][k][S][0]=0;
			if(j==i+1)	{dp[j][k][S][0]=dp[j][k][S][1];dp[j][k][S][1]=0;}
		}
	}
	rep(i,0,n-1)	ans+=dp[m+1][i][totS][0];//,ret+=dp[m+1][i][totS][0],printf("%d\n",dp[m+1][i][totS][0]);
	//printf("%d\n",ret);
}		

void dfs(int now){
	if(now==n){DP();return;}
	int i;
	rep(i,0,n-1) if(!vis[i]){
		b[now]=a[i];vis[i]=1;dfs(now+1);vis[i]=0;
	}
}

int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int i;
	scanf("%d%d",&n,&m);
	rep(i,0,n-1)	scanf("%d",&a[i]);
	sort(a,a+n);n--;totS=(1<<n)-1;	
	dfs(0);
	tot=1;rep(i,1,n)	tot=tot*m*i;
	printf("%.15f\n",(double)ans/(double)tot);
}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

Measured memory_bytes: 1408
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int main(void){
	vector<int>a;
	vector<int>b;
	int c, d;
	int k;
	int n, m;
	int s, t;
	int x, y, z;

	scanf("%d %d", &n,&m);

	for (int i = 0; i < m; i++){
		scanf("%d %d", &x,&y);
		if (x == 1)a.push_back(y);
		if (y == n)b.push_back(x);
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	s = 0;
	t = 0;
	z = 0;
	for (;s<a.size()&&t<b.size();){
		if (a[s] < b[t])s++;
		else if (a[s]>b[t])t++;
		else {
			z = 1;
			break;
		}
	}

	if(z==1)printf("POSSIBLE\n");
	else printf("IMPOSSIBLE\n");

	return 0;
}


Measured memory_bytes: 1276
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int mx=0,cnt=0;
	for(int i=0; i<s.length(); i++)
	{
		if(s[i]=='R') cnt++;
		else cnt=0;
		mx=max(cnt, mx);
	}
	cout<<mx<<endl;
	
	return 0;
	
}

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

int wa(int x){
  if(x<10) return x;
  else return wa(x/10)+x%10;
}

int main(){
  int64_t N;
  int tmp=0,ans=10000000;
  cin>>N;
  for(int i=1;i<N;i++){
    tmp=wa(i)+wa(N-i);
    ans=min(tmp,ans);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
<?php
// Your code here!
    $vertex_num = intval(trim(fgets(STDIN)));
    
    //入力値を深さ優先探索に適した形にすることを気を付ける
    for($i=1;$i<=$vertex_num;$i++){
        $graph[$i] = array_map('intval',explode(" ",trim(fgets(STDIN))));
        array_shift($graph[$i]);
        array_shift($graph[$i]);
    }
    
    //すでに探索したかどうか
    global $seen;
    $seen=array_fill(1,$vertex_num,0);
    
    //検知したがまだ訪れていない
    global $todo;
    $todo=array_fill(1,$vertex_num,0);
    
    //最初に訪れた時のタイムスタンプ
    global $time_first;
    //調査が終わった後のタイムスタンプ
    global $time_last;
    //タイムカウント
    global $count;
    $time_first=array_fill(1,$vertex_num,0);
    $time_last =array_fill(1,$vertex_num,0);
    $count=1;
    //開始は頂点1でグラフが途切れている場合を考慮
    for($j=1;$j<=$vertex_num;$j++){
        if($seen[$j]==0){
            //グラフ情報,探索開始の頂点番号値から探索を行う
            dfs($graph,$j);
        }
    }
    
    for($k=1;$k<=$vertex_num;$k++){
        echo $k;
        echo " ";
        echo $time_first[$k];
        echo " ";
        echo $time_last[$k];
        echo "\n";
        
    }
    
    //深さ優先探索の肝部分
    function dfs($graph,$vertex){
        global $seen;
        global $todo;
        global $time_first;
        global $time_last;
        global $count;
        
        //訪問された
        $seen[$vertex]=1;
        
        $time_first[$vertex] = $count++;
        
        //頂点から伸びている先の頂点の調査
        foreach($graph[$vertex] as $vertex_a){
            //探索済みならスルー
            if($seen[$vertex_a]==1)continue;

            $info = dfs($graph,$vertex_a);
        }
        
        $time_last[$vertex] = $count++;
    }
    
?>


Measured memory_bytes: 9452
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std; 
#define MAXN 20
#define MAXA 100
#define MAXB 2000
int main(int argc,char const* argv[])
{
  int length;
  string s;
  int harsh=0;
  cin >> s;
  length=s.size();
  vector<int> keta(8,0);
  int num=atoi(s.c_str());
  for(int i=0;i<length;i++)
    {
      keta[i]=(int)(s[i]-'0');
    }
  for(int i=0;i<length;i++)
    {
      harsh+=keta[i];
    }
  if(num % harsh ==0)
    {
      cout << "Yes" << endl;
    }
  else
    {
      cout << "No" << endl;
    }
  return 0;
}

Measured memory_bytes: 256
h, w = [int(i) for i in input().split()]
s = [input() for i in range(h)]

def is_check():
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#' and (j+1 >= w or s[i][j] != s[i][j+1]) and (j-1 < 0 or s[i][j] != s[i][j-1]) and (i+1 >= h or s[i][j] != s[i+1][j]) and (i-1 < 0 or s[i][j] != s[i-1][j]):
                return 'No'
    return 'Yes'

print(is_check())

Measured memory_bytes: 3064
def main():
    a, b, c, k = map(int, input().split())

    total = 0
    rem = k
    total += min(a, rem)
    rem = max(0, rem - a)
    rem = max(0, rem - b)
    total -= min(c, rem)
    rem = max(0, rem - c)

    print(total)

if __name__ == '__main__':
    main()


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 100010

vector<int> G[MAX_N];
int n,m;
int num[MAX_N],par[MAX_N],low[MAX_N];
int cnt;

void dfs(int v,int prev){
	num[v]=low[v]=++cnt;
	for(int i=0;i<G[v].size();i++){
		int nv=G[v][i];
		if(num[nv]==-1){
			par[nv]=v;
			dfs(nv,v);
			low[v]=min(low[v],low[nv]);
		}else if(nv!=prev){
			low[v]=min(low[v],num[nv]);
		}
	}
}

vector<int> art_points(){
	memset(num,-1,sizeof(num));
	cnt=0;
	dfs(0,-1);
	set<int> ap;
	int np=0;
	for(int i=1;i<n;i++){
		int p=par[i];
		if(p==0)np++;
		else if(num[p]<=low[i])ap.insert(p);
	}
	if(np>1)ap.insert(0);
	vector<int> res;
	for(set<int>::iterator it=ap.begin();it!=ap.end();it++)res.push_back(*it);
	return res;
}

int main(){
	cin.sync_with_stdio(false);
	cin>>n>>m;
	rep(i,m){
		int s,t;
		cin>>s>>t;
		G[s].pb(t); G[t].pb(s);
	}
	vector<int> a=art_points();
	rep(i,a.size())cout<<a[i]<<endl;
	return 0;
}

Measured memory_bytes: 7272
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

def main():
    A = list(map(int, input().split()))

    if sum(A) > 21:
        print("bust")
    else:
        print("win")


if __name__ == '__main__':
    main()

Measured memory_bytes: 2940
a = int(input())
b = int(input())
c = int(input())
x = int(input())

count = 0

task1 = (x // 500) if (x // 500) < a else a
for i in range(task1 + 1):
    new_x = x - 500 * i
    task2 = (new_x // 100) if (new_x // 100) < b else b
    for i in range(task2 + 1):
        y = new_x - 100 * i
        if y <= 50 * c:
            count += 1
print(count)

Measured memory_bytes: 3064
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n = int(input())
    a = list(map(int, input().split()))
    for i in a:
        if i == 0:
            print(0)
            return

    s = 1
    for i in a:
        s *= i
        if s > int(1e18):
            print(-1)
            return
    print(s)

main()


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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s,t;
	cin>>s>>t;
	if( s.size() + 1 == t.size() and t.substr(0,s.size()) == s ){
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}

	return 0;
}


Measured memory_bytes: 3648
using System;
using System.Collections.Generic;
using System.Linq;

namespace AOJ0519
{
    class Program
    {
        static void Main()
        {
            var teams = int.Parse(Console.ReadLine() ?? "");
            var nodes = Enumerable.Range(1, teams).Select(i => new Node(i)).ToArray();

            var count = int.Parse(Console.ReadLine() ?? "");
            for (var i = 0; i < count; i++)
            {
                var values = (Console.ReadLine() ?? "").Split(' ').Select(int.Parse).ToArray();
                Node.Connect(nodes[values[0] - 1], nodes[values[1] - 1]);
            }

            var noInputs = new Queue<Node>(from node in nodes
                                           where !node.Inputs.Any()
                                           select node);
            var sorted = new List<Node>();
            var unique = true;
            while (noInputs.Any())
            {
                if (noInputs.Count != 1) unique = false;
                var node = noInputs.Dequeue();
                sorted.Add(node);
                foreach (var next in new List<Node>(node.Outputs))
                {
                    Node.Disconnect(node, next);
                    if(!next.Inputs.Any()) noInputs.Enqueue(next);
                }
            }

            foreach (var node in sorted)
            {
                Console.WriteLine(node.Value);
            }

            Console.WriteLine(unique ? 0 : 1);
        }
    }

    public class Node
    {
        public List<Node> Inputs { get; set; }
        public List<Node> Outputs { get; set; }
        public int Value { get; set; }

        public Node(int value)
        {
            Inputs = new List<Node>();
            Outputs = new List<Node>();
            Value = value;
        }

        public static void Connect(Node from, Node to)
        {
            from.Outputs.Add(to);
            to.Inputs.Add(from);
        }

        public static void Disconnect(Node from, Node to)
        {
            from.Outputs.Remove(to);
            to.Inputs.Remove(from);
        }
    }
}

Measured memory_bytes: 12296
package main

import (
	"fmt"
	"math"
	"strconv"
)

func main() {
	var s string
	fmt.Scan(&s)

	min := calcDiff(s[0:3])
	for i := 1; i < len(s)-2; i++ {
		diff := calcDiff(s[i : i+3])
		if diff < min {
			min = diff
		}
	}
	fmt.Println(min)
}

func calcDiff(s string) int {
	x, _ := strconv.Atoi(s)
	return int(math.Abs(float64(753 - x)))
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> vec;
	int sum, x;
	for (int i = 0; i < n; i++) {
    	cin >> x;
      	sum += x;
      	vec.emplace_back(x);
    }
  	int avg1 = sum / n;
	int avg2 = sum / n + 1;
	int result1 = 0;
  	int result2 = 0;
  	for (int y : vec) {
     	result1 = result1 + (y - avg1) * (y - avg1);
      	result2 = result2 + (y-avg2) * (y-avg2);
    }
  	cout << min(result1, result2) << endl;	
	return 0;
}

Measured memory_bytes: 256
a = int(input())
ar = []
for i in range(a):
    l = input()
    ar.append(l)
br = set(list(ar[0]))
dr = []
for r in br:
    cr =[]
    count = 0
    for rr in ar:
        if rr.count(r) > 0:
            cr.append(rr.count(r))
            count += 1
        if count == a:
            for i in range(min(cr)):
                dr.append(r)
print("".join(sorted(dr)))
                

Measured memory_bytes: 3064
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

int main() {
  ll h,w,y1,x1;
  cin>>h>>w>>y1>>x1;
  rep(y,0,h){
    rep(x,0,w){
      if(y<x1&&x<y1){
        cout << "1";
      }
      else if(y>=x1&&x>=y1){
        cout << "1";
      }
      else cout << "0";
    }
    cout << endl;
  }
  return 0;
}

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

using namespace std;

typedef long long ll;

ll A[505050], L[505050], R[505050];
ll n;

int main()
{
	ll q, i, x;
	
	scanf("%lld%lld", &n, L);
	
	for(i=1; i<=n; i++){
		scanf("%lld", A + i);
		L[i] = min(L[i - 1], abs(L[i - 1] - A[i]));
	}
	
	R[n + 1] = 0;
	
	for(i=n; i>=1; i--){
		if(A[i] <= R[i + 1] * 2 + 1){
			R[i] = R[i + 1] + A[i];
		}
		else R[i] = R[i + 1];
	}
	
	scanf("%lld", &q);
	
	for(; q--; ){
		scanf("%lld", &x);
		printf("%s\n", L[x - 1] <= R[x + 1]? "NO" : "YES");
	}
	
	return 0;
}

Measured memory_bytes: 13696
//状态:
//题号:
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <iomanip>
#include <cassert>
#include <complex>
#include <functional>
#include <list>
#include <cmath>
using namespace std;
typedef long long ll;
int n;
map<int,int> mp;
int p[1005]={};
int cnt;
bool f[1005];
void tod(int num){
	int t=num;
	for(int i=0;p[i]<=t&&num>1;i++){
		if(num%p[i]==0){
			while(num%p[i]==0&&num!=0){
				num/=p[i];
				mp[p[i]]++;
				//cout<<p[i]<<endl;
			}
		}
	}
}
int main(){
	for(int i=2;i<=1000;i++){
		if(f[i])continue;
		p[cnt++]=i;
		for(int j=i;j<=1000;j+=i){
			f[i]=true;
		}
	}
	cin>>n;
	for(int i=2;i<=n;i++){
		tod(i);
	}
	ll ans=1;
	for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
		ans=(ans*(it->second+1))%(1000000007);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=6005;
vector<string>a;
bool vis[3][N];
vector<int>v;
void solve(int x,int y,int p)
{
    for(int i=0;i<a[x].size();i++)
        for(int j=0;j<a[y].size()&&i+j<a[x].size();j++)
        {
            if(a[x][i+j]=='?'||a[y][j]=='?') continue;
            if(a[x][i+j]!=a[y][j])
            {
                vis[p][i]=false;break;
            }
        }
}
int solve()
{
    int x=v[0],y=v[1],z=v[2];
    memset(vis,true,sizeof(vis));
    solve(x,y,0);
    solve(x,z,1);
    solve(y,z,2);
    int ans=6000;
    for(int i=0;i<=6000;i++)
    {
        if(!vis[0][i]) continue;
        for(int j=0;i+j<=6000;j++)
        {
            if(!vis[2][j]||!vis[1][i+j]) continue;
            int res=a[x].size();
            res=max(res,(int)a[y].size()+i);
            res=max(res,(int)a[z].size()+i+j);
            ans=min(ans,res);
        }
    }
    return ans;
}
int main()
{
    for(int i=0;i<3;i++)
    {
        string s;cin>>s;
        a.push_back(s);
    }
    int ans=a[0].size()+a[1].size()+a[2].size();
    v.push_back(0);v.push_back(1);v.push_back(2);
    while(true)
    {
        ans=min(ans,solve());
        if(!next_permutation(v.begin(),v.end())) break;
    }
    cout<<ans<<endl;
}


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

int a[30]={0};

int main ()
{
	int n,m,i,j;
	cin>>n>>m;
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			char c;
			cin>>c;
			a[c-'a']++;
		}
	int num[4]={0};
	for(i=0;i<30;i++)
		num[a[i]%4]++;
	if(n%2==0&&m%2==0)
	{
		if(num[1]+num[2]+num[3])
			cout<<"No"<<endl;
		else
			cout<<"Yes"<<endl;
	}
	else if((m+n)%2==1)
	{
		if(m%2==1)
		{
			int tmp;
			tmp=n; n=m; m=tmp;
		}
		if(num[2]>m/2||num[1]||num[3])
			cout<<"No"<<endl;
		else
			cout<<"Yes"<<endl;
	}
	else
	{
		if(num[1]+num[3]>1||num[2]>(n/2+m/2))
			cout<<"No"<<endl;
		else 
			cout<<"Yes"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
/*
 * @Author: Kaizyn
 * @Date: 2020-03-07 21:08:03
 * @LastEditors: Kaizyn
 * @LastEditTime: 2020-03-07 21:09:48
 * @FilePath: \Code\atcoder\abc158B.cpp
 */
#include <bits/stdc++.h>

// #define DEBUG

using namespace std;

const int N = 1e2;
const int MOD = 1e9+7;
const double eps = 1e-7;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

long long n, a, b;

inline void solve()
{
    cin >> n >> a >> b;
    long long t = n/(a+b), r = n-t*(a+b);
    cout << t*a+min(a, r) << endl;
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int testcase = 1;
    // cin >> testcase;
    for (int i = 1; i <= testcase; ++i) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    count = 0
    x_list =[3**3*5, 3**3*7, 3*5*7, 3*5*11, 3*5*13]
    for one in x_list:
        if one<=n:
            count+=1
    print(count)

if __name__=="__main__":
    main()


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = INT_MAX / 2;

int main() {
  string s; cin >> s;
  if (s.size() % 2) {
    cout << "No\n";
    return 0;
  }
  bool ok = 1;
  rep(i, s.size()) {
    if (i % 2 == 1 && s[i] != 'i') ok = 0;
    if (i % 2 == 0 && s[i] != 'h') ok = 0;
  }
  cout << (ok ? "Yes\n" : "No\n");
}


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

long long n;

int main() {
  cin >> n;
  n %= 10;
  if (n == 3)
    cout << "bon" << endl;
  else if (n == 2 || n == 4 || n == 5 || n == 7 || n == 9)
    cout << "hon" << endl;
  else
    cout << "pon" << endl;
  return 0;
}

Measured memory_bytes: 3636
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A= sc.nextInt();
      	int B= sc.nextInt();
      	int C= sc.nextInt();
      	int D= sc.nextInt();
      	int c1 = 0;
      	int c2 = 0;
        while(C > 0){
          C = C - B;
          c1 += 1;
        }
      	while(A > 0){
          A = A - D;
          c2 += 1;
        }
      	if (c2 >= c1)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Measured memory_bytes: 35720
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>

using namespace std;
typedef long long ll;
typedef double db;
#define inf 0x3f3f3f3f
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll gcd(ll a, ll b) {
	return a % b ? gcd(b, a % b) : b;
}
bool fun(ll n) {
	if (n < 3)return n - 1;
	ll q = sqrt(n + 0.5) + 1, i;
	for (i = 2; i < q; ++i) {
		if (n % i == 0)return 0;
	}
	return 1;
}
signed main() {
	ll a, b;
	cin >> a >> b;
	ll n = gcd(a, b);
	ll q = sqrt(n + 0.5) + 1;
	ll i;
	ll ans = 1;
	for (i = 2; i < q; ++i) {
		if (n % i == 0) {
			if (fun(i))++ans;
			if (n / i != i) {
				if (fun(n / i))++ans;
			}
		}
	}
	if (n > 1 && ans == 1)++ans;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3680
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

N=gets.to_i
A=get_i
A.unshift(0)
dis=array(N+1,0)
N.times do|i|
    dis[i]=(A[i]-A[i+1]).abs
end
dis[N]=(A[0]-A[N]).abs
sum=dis.inject(:+)
N.times do|i|
    puts sum-dis[i]-dis[i+1]+(A[i]-A[(i+2)% (N+1)]).abs
end

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

#define ll long long

const int mxN=1e5, M=1e9+7;
int n, c[mxN+1];
vector<int> a[mxN];
bool b[mxN];
ll ans=1, d[mxN+1];

void fk() {
	cout << 0;
	exit(0);
}

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

	cin >> n;
	for(int i=0, b; i<n; ++i) {
		cin >> b, --b;
		a[b].push_back(i);
	}
	for(int i=0; i<n; ++i)
		if(a[i].size()>2)
			fk();
	for(int i=0; i<n; ++i) {
		if(b[i]||a[i].size()<2)
			continue;
		int u1=a[i][0], u2=a[i][1];
		while(1) {
			if(u2==i)
				swap(u1, u2);
			if(u1==i)
				break;
			b[u1]=1;
			vector<int> v=a[u1];
			if(~u2) {
				v.insert(v.end(), a[u2].begin(), a[u2].end());
				b[u2]=1;
			}
			if(v.size()>2||!v.size())
				fk();
			u1=v[0];
			if(v.size()>1)
				u2=v[1];
			else {
				ans=ans*(1+(u2>=0))%M;
				u2=-1;
			}
		}
		b[u1]=1;
		if(~u2) {
			if(a[u2].size())
				fk();
			b[u2]=1;
		}
	}
	for(int i=0; i<n; ++i) {
		if(b[i])
			continue;
		int s=0;
		for(int u=i; !b[u]; u=a[u][0]) {
			b[u]=1;
			++s;
		}
		++c[s];
	}
	d[0]=1;
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=c[i]; ++j)
			d[j]=(d[j-1]*(i&1&&i>1?2:1)+(j>1?d[j-2]*(j-1)%M*i:0))%M;
		ans=ans*d[c[i]]%M;
	}
	cout << ans;
}

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

bitset<4000005>bs;
int n;

int main(){
	scanf("%d",&n);
	bs[0]=1;
	int sum=0;
//	bs=bs<<1;
//	cout<<bs[1]<<endl;
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		bs=(bs|(bs<<x));
		sum+=x;
	}
	int ans=sum;
	for(int i=sum;i>=1;i--)
		if(bs[i]==1&&i*2>=sum)ans=i;
	printf("%d\n",ans);
	return 0;
}

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

int main() {
  string s;
  cin >> s;
  int sum = 0;
  for (int i = 0; i < s.length(); i++) {
    sum += s[i] - '0';
  }
  if (!(sum % 9) )
    cout << "Yes" << endl;
  else {
    cout << "No" << endl;
  }

  system("pause");
  return 0;
}


Measured memory_bytes: 3768
//include
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath> 
#include <iomanip>
#include <math.h>
#include <utility>
#include <functional>
#include <cstdlib>
//using
using namespace std;
using vl = vector <long long>;
using vs = vector <string>;
using vc = vector <char>;
using ll= long long;
using vvl = vector<vector<ll> >;
using vvc = vector<vector<char> >;
//vector<vector<char> > hyou(N, vector<char>(N));
using vd = vector <double>;
//define
//#define int long long
#define rep(i,n) for(int i=0; i<n; i++)
#define print(n) cout<<n<<endl;
#define sortp(d) sort(d.begin(),d.end()) //1234
#define sortm(d) sort(d.rbegin(),d.rend()) //4321
//素数判定　O(√A) 
bool is_prime(int x){
 if(x<=1) return false;
 for(int i=2;i*i<=x;i++)
 if(x%i==0) return false;
 return true;
 }
 //各位の和　
int wa(ll x)
{
ll sum = 0;
while(x!=0){
  sum += x% 10;
  x /= 10;
}
return sum;
}
/*順列生成
do {
  // 順列に対する処理
} while (next_permutation(配列変数.begin(), 配列変数.end()));*/

//絶対値　abs()
//文字→数字　'0' アルファベット→数字　'a'　'A'が65番,'a'が97番だわ
//型キャスト　char('a'+1)
//reverse 回文
//if(isupper('A'))->大なら真


//グローバル変数宣言
ll p=0,q=0,r=0;

int main()
{
  ll n;
  cin>>n;
  vl a(n),b(n);
  
  rep(i,n)
  {
    cin>>a[i];
  }
  p=1;
  rep(i,n)
  {
    if(a[i]==p)
    {
      p++;
    }
  }
  if(p!=1)
  print(n-p+1)
  else print(-1)
}

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

#define scd second
#define fst first
#define mkp make_pair
#define pb push_back

using namespace std;

typedef long long int ll;
typedef vector<int> vint;
typedef vector<ll> vlong;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

int main(){
	string str;
	cin>>str;
	string ans="";
	int n=str.length();
	for(int i=0; i<n; i+=2){
		ans+=str[i];
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 512
#pragma GCC optimize ("-O3")
#ifdef LOCAL
  #include "helper_funcs.hpp"
#else
  #include <bits/stdc++.h>
#endif
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define frn(i,a,b) for(ll i=a;i<b;i++)
#define rfrn(i,a,b) for(ll i=a;i>b;--i)
#define forn(i,a,b) for(ll i=a;i<=b;i++)
#define rforn(i,a,b) for(ll i=a;i>=b;--i)
#define sqfrn(i,a,b) for(ll i=a;i*i<b;i++)
#define sqforn(i,a,b) for(ll i=a;i*i<=b;i++)
#define frt(it,v) for(auto &it:v)
#define MP make_pair
#define F first
#define S second
#define PB push_back
#define SQR(a) (a)*(a)
#define SUM(n) ((n)*(n+1))/2
// #define SqSUM(n) ((n)*(n+1)*(2*n+1))/2
// #define GMSUM(a,r,n) (a*pow(r,n)-a)/(r-1)
#define ciel(x, y) (((x) / (y)) + ((x) % (y) != 0))
#define input(v,a,b) for(ll i = a ; i<b ; i++) cin>>v[i]
#define output(v,a,b) cout<<"["<<#v<<"]: "; for(ll i = a ; i<b ; i++) cout<<v[i]<<" "; cout<<ln
#define cout_p(x, p) cout << fixed << setprecision((p)) << x
#define dbg(x) cerr << #x << "is" << (x) << endl
#define leadzero(a) __builtin_clz(a)      // count leading zeroes
#define trailzero(a) __builtin_ctz(a)     // count trailing zeroes
#define bitcount(a) __builtin_popcount(a) // count set bits (add ll)
#define ln "\n"
const long long int md = 998244353;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pi;
typedef vector<ll> v1;
typedef vector<vector<ll > > vv2;
#define M 32
#ifndef M_PI
  #define M_PI 3.14159265358979323846
#endif
typedef bitset<M> btst;
typedef priority_queue<int, vector<int>, greater<int>> min_heap;
typedef priority_queue<int, vector<int>> max_heap;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//     indexed_set;
const ll MAX = LONG_MAX;
const ll lrg = 1000000007;

vector<ll> f(1e5+1), ivf(1e5+1, -1);

ll pw(ll a, ll x)
{
	ll cp=x, pr=a, ans=1;
	while(cp>0)
	{
		if(cp%2!=0)
		{
			ans=(ans*pr)%lrg;
		}
		cp/=2;pr=(pr*pr)%lrg;
	}
	return ans;
}

void fact()
{
	f[0]=1;
	for(int i=1;i<5000;i++)
	{
		f[i]=(f[i-1]*i)%lrg;
	}
}

ll invfact(ll n)
{
	if(ivf[n]==-1)
		ivf[n]=pw(f[n], lrg-2);
	return ivf[n];
}

void solve()
{
	ll s;
	cin>>s;
	ll sm=0;
	ll cp=1;
	while(cp<=floor(s/3.0))
	{
		ll tmp=s;
		tmp-=3*cp;

		sm=(sm+(f[tmp+cp-1]*((invfact(cp-1)*invfact(tmp))%lrg))%lrg)%lrg;
		cp++;
	}
	cout<<sm;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t=1,cp;
  // cin>>t;
  cp=t;
  fact();
  while(t--){
   // cout<<"Case #"<<cp-t<<": ";
   solve();
   cout<<"\n";
  }
  return 0;
}

Measured memory_bytes: 4696
// Aizu 2216: Summer of KMC
// 2017.9.23 bal4u@uu
// Greedy

#include <stdio.h>

int c[3] = {1000, 500, 100};  //??°????????£???????????????

int main()
{
	int a, b, i, ans[3];

	while (scanf("%d%d", &a, &b) && a > 0) {
		b -= a;  //??£????????????
		for (i = 0; i < 3; i++) {
			ans[i] = b/c[i];
			b %= c[i];
		}
		printf("%d %d %d\n", ans[2], ans[1], ans[0]);
	}
	return 0;
}

Measured memory_bytes: 1720
import sys

input = sys.stdin.readline

def main():
    n = int(input())
    A = list(map(int, input().split()))
    allB = exc = 1
    for i in A:
        allB *= 3
        if i%2 == 0:
            exc *= 2
    print(allB - exc)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9044
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<utility>
#include<vector>
#include<string>

using namespace std;

int main(void){
    char S[100];
    scanf("%s",S);
    int i=0;
    while(S[i]!='\0'){
        printf("x");
        i++;
    }
    return 0;
}

Measured memory_bytes: 128