akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

struct edge {
	int u, v, cost;
};


typedef long long ll;
typedef pair<int, int> P;
const int MAX_N = 100;
const int MAX_E = 100*99/2;
int par[MAX_N];
int rank[MAX_N];
edge es[MAX_E];

int V, E;	//  頂点数と辺数

// n要素で初期化
int init_union_find (int n )
{
	rep (i, n ){
		par[i] = i;
		rank[i] = 0;
	} // end for
}

// 木の根を求める
int find (int x )
{
	if (par[x] == x )
		return x;

	// 親を遡る
	return par[x] = find (par[x] );
}

// xとyの属する集合をマージ
void unite (int x, int y )
{
	x = find (x);
	y = find (y);

	// 親が一緒なら何もしない
	if (x == y )
		return;

	// ランクが小さい方の木をぶら下げる
	if (rank[x] < rank[y] ){
		// x を y にぶら下げる
		par[x] = y;
	}else{
		// ランクが同じか rank[x] > rank[y]
		par[y] = x;
		if (rank[x] == rank[y] )
			rank[x]++;
	} // end if
}

// xとyが同じ集合に属するか否か
bool same (int x, int y )
{
	return (find (x) == find (y) );
}



bool comp (const edge& e1, const edge& e2 )
{
	return e1.cost < e2.cost;
}

int kruskal (void )
{
	sort (es, es + E, comp );
	init_union_find (V );
	int res = 0;
	rep (i, E ){
		edge e = es[i];
		if (!same (e.u, e.v ) ){
			unite (e.u, e.v );
			res += e.cost;
		} // end if
	} // end rep

	return res;
}

int main()
{
//	cut here before submit 
//	freopen ("testcase.carden_lentern", "r", stdin );
	int n;
	while (scanf ("%d", &n ), n ){
		int m;
		scanf ("%d", &m );
		set<int> cnt_V; cnt_V.clear();
		rep (i, m ){
			int from, to, cost;
			scanf ("%d,%d,%d", &from, &to, &cost );
			cnt_V.insert (from ); cnt_V.insert (to );
			es[i].u = from; es[i].v = to; es[i].cost = cost; 
		} // end rep
		E = m;
		V = cnt_V.size();
		int ans = kruskal();	// 最小全域木の経路の長さ
		int res = ans/100 - (V-1);
		printf ("%d\n", res );
	} // end loop

	return 0;
}

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

string x;
int satu,nol,ans;

int main(){
	cin>>x;
	int pan = x.length();
	for(int i =0;i<pan;i++){
		if(x[i]=='0') nol++;
		else satu++;
	}
	ans = min(satu,nol)*2;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int pos = 0;
    int ans = 1;
    while(pos < n-1)
    {
        if(s[pos] != s[pos+1])
        {
            ans++;
        }
        pos++;
    }
    cout << ans << endl;
}



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

int main(){
  string s;
  cin >> s;
  
  bool flag = true;
  
  if(s[0] != 'A') flag = false;
  
  ll Cidx = 0;
  string sub = s.substr(2,s.size()-3);
  if(count(sub.begin(),sub.end(),'C')!=1) flag = false;
  
  if(!flag){
    cout << "WA" << endl;
    return 0;
  }
  
  //ちょっとコード汚いけれど、大文字Cが１文字確定しているので以下のif文が通る
  for(ll i=1; i<=s.size(); i++){
    if(s[i]!='C' && isupper(s[i])) flag = false;
  }
  
  if(flag) cout << "AC" << endl;
  else cout << "WA" << endl;
}

Measured memory_bytes: 3648
//test
#include<bits/stdc++.h>
using namespace std;
const int N=200;
int n,m,f[2][N][N][N];
char s[N][N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)scanf("%s",s[i]+1);
    for(int i=n; i; i--)
        for(int j=i; j<=n; j++)
            for(int k=m; k; k--)
                if(i==j)
                {
                    if(k==m)f[0][i][j][k]=m+1;
                    else f[0][i][j][k]=s[i][k]==s[i][k+1]?f[0][i][j][k+1]:k+1;
                }
                else f[0][i][j][k]=s[i][k]==s[i+1][k]?min(f[0][i][i][k],f[0][i+1][j][k]):k;
    for(int ans=0,t=0;; ans++,t^=1)
    {
        if(f[t][1][n][1]==m+1)
        {
            printf("%d\n",ans);
            return 0;
        }
        for(int i=n; i; i--)
            for(int j=i; j<=n; j++)
                for(int k=m; k; k--)
                {
                    f[t^1][i][j][k]=f[t][i][j][k]==m+1?m+1:f[t][i][j][f[t][i][j][k]];
                    if(i<j)
                    {
                        int l=i,r=j-1,mid;
                        while(l<=r)
                        {
                            mid=l+r>>1;
                            if(f[t][i][mid][k]<=f[t][mid+1][j][k])
                                f[t^1][i][j][k]=max(f[t^1][i][j][k],f[t][i][mid][k]),r=mid-1;
                            else f[t^1][i][j][k]=max(f[t^1][i][j][k],f[t][mid+1][j][k]),l=mid+1;
                        }
                    }
                }
    }
}

Measured memory_bytes: 61440
#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 int lli;
lli gcd(lli m, lli n) {
  if (m % n == 0) {
    return n;
  } else {
    return gcd(n, m % n);
  }
}
lli countMulti(lli a, lli b, lli N) {
  lli a0 = a / N;
  lli a1 = a % N;
  lli b0 = b / N;
  if (a1 == 0) {
    return b0 - a0 + 1;
  } else {
    return b0 - a0;
  }
}
int main() {
  lli A, B, C, D;
  cin >> A >> B >> C >> D;
  lli X = C / gcd(C, D);
  X *= D;
  // cout << X << endl;
  lli Ap = A / X;
  lli Aq = A % X;
  lli Bp = B / X;
  lli Bq = B % X;

  lli baseX = X / C + X / D - 1;
  lli ans;
  if (Ap == Bp) {
    //いずれか割り切れる個数
    ans = countMulti(Aq, Bq, C);
    ans += countMulti(Aq, Bq, D);
    ans -= countMulti(Aq, Bq, X);
    ans *= -1;
  } else {
    ans = baseX * (Bp - Ap - 1);
    ans += countMulti(Aq, X - 1, C);
    ans += countMulti(Aq, X - 1, D);
    ans -= countMulti(Aq, X - 1, X);
    ans += countMulti(0, Bq, C);
    ans += countMulti(0, Bq, D);
    ans -= countMulti(0, Bq, X);
    ans *= -1;
    //端
  }
  ans += (B - A + 1);
  cout << ans << endl;
  //  int gcdM = gcd(C, D);
}

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

int main(){
  int X;
  cin >> X;
  
  int ans = X;
  if(ans == 2){
    cout << ans;
    return 0;
  } 
  
  while(true){
    for(int i = 2; i < ans; i++){
      if(ans % i == 0) break;
      if(i == ans-1){
        cout << ans;
        return 0;
      } 
    }
    ans++;
  }
  return 0;
}

Measured memory_bytes: 256
/*
Author : N_o_o_B
Created : April 22 2020 23:04:15 
*/
#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
#define TRACE
#ifdef TRACE
#define trace(...) { cerr<<"[ "; __trace__(#__VA_ARGS__, __VA_ARGS__);}
#undef endl
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const pair<Arg1,Arg2> &x) {
    return out<<"("<<x.first<<","<<x.second<<")";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const vector<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const set<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const map<Arg1,Arg2> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
void __trace__(const string name, Arg1&& arg1){
    cerr << name << " : " << arg1 << " ] " << endl;
}
 
template <typename Arg1, typename... Args>
void __trace__(const string names, Arg1&& arg1, Args&&... args){
    const string name = names.substr(0,names.find(','));
    cerr<<name<<" : "<<arg1<<" | ";
    __trace__(names.substr(1+(int)name.size()), args...);
}
#else
    #define trace(args...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vll;
typedef vector<vl> vvl;
//typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define fori(i,n) for(int i=0;i<n;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
#define ford(i,n)  for(int i=n-1;i>=0;i--)
#define trav(x,a) for(auto& x:a)
#define all(x) x.begin(),x.end()
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define fi first
#define se second
clock_t time_p=clock();
void time_taken()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
//const ll mod=998244353;
const ll mod=1e9+7;
const ll INF=1e18;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cout.precision(12);cout << fixed;

    int n;
    cin >> n;
    map<string,int> m;
    int mx = 0;
    while(n--){
        string s;
        cin >> s;
        m[s]++;
        mx = max(mx,m[s]);
    }
    for(auto x:m){
        if(x.se==mx) cout << x.fi << endl;
    }


    time_taken();
    return 0;
}

Measured memory_bytes: 23808
import bisect

N = int(input())
A = sorted([int(i) for i in input().split()])
B = sorted([int(i) for i in input().split()])
C = sorted([int(i) for i in input().split()])

cnt = 0
for b in B:
    cnt += bisect.bisect_left(A, b) * (N - bisect.bisect_right(C, b))
    
print(cnt)

Measured memory_bytes: 23156
//{
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(i,n) memset(i,n,sizeof i)
#define X first
#define Y second
#define SZ(_a) (int)_a.size()
#define ALL(_a) _a.begin(),_a.end()
#define pb push_back
#ifdef brian
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // brian
//}


const ll MAXn=1e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=ll(1e15);

int main()
{
    IOS();
    ll a,b;
    cin>>a>>b;
    if(a >8 || b>8)cout<<":("<<endl;
    else cout<<"Yay!"<<endl;
}


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

class Program {
  static void Main (string[] args) {
    var p = Console.ReadLine ().Split (' ');
    long N = long.Parse (p[0]);
    long K = long.Parse (p[1]);
    var aa = Console.ReadLine ().Split (' ');
    long[] A = new long[100000];

    long pos =0;
    for (int i = 0; i < N; i++) {
      A[i] = long.Parse (aa[i]);
      if (A[i]==1)pos = i;
    }

    // long w = K-1;

    // long forw = (N-1-pos)/(K-1);
    // if ((N-1-pos)%(K-1) !=0)if (pos!=N-1)forw++;



    // long backw = pos/(K-1);
    // if (pos%(K-1) !=0)if (pos!=0)backw++;
    long num = (N-1)/(K-1);
    if ((N-1)%(K-1)!=0)num++;


    // long num=forw + backw;

    Console.WriteLine (num);

  }
}

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

int main() {
	int n;
	cin >> n;
	bool G[n + 1][n + 1];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			G[i][j] = false;
	for (int i = 0; i < n; i++) {
		int u, k;
		cin >> u >> k;
		for (int j = 0; j < k; j++) {
			int v;
			cin >> v;
			G[u][v] = true;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n - 1; j++) {
			cout << G[i][j] << " ";
		}
		cout << G[i][n] << endl;
	}
	return 0;
}



Measured memory_bytes: 3112
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if(a>b) {a=b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if(a<b) {a=b; return true;} return false;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N; cin >> N;
  vector<pair<int, int>> itv(N);
  rep(i, N) {
    int X, L;
    cin >> X >> L;
    itv[i].first = L + X;
    itv[i].second = max(0,X-L);
  }
  sort(itv.begin(), itv.end());
  int ans = 0, t = 0;
  rep(i, N) {
    if(t <= itv[i].second) {
      ++ans;
      t = itv[i].first;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3984
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
    string S, T;
    cin >> S >> T;
    int ans = T.size();
  
    for (int start = 0; start <= S.size() - T.size(); start++)
    {
        int diff = 0;
        for (int i = 0; i < T.size(); i++)
        {
            if (T[i] != S[start + i]) {
                diff++;
            }
        }
        ans = min(ans, diff);
    }
 
    cout << ans << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int k;
	scanf("%d",&k);
	if(k%10!=1&&k%10!=3&&k%10!=7&&k%10!=9){
		cout<<-1<<endl;
		return 0;
	}
	int po = 7;
	int ans;
	for(int i=1;i<=k;i++){
		po%=k;
		if(po%k==0){
			ans = i;
			break;
		}
		po=po*10+7;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3752
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#include<bitset>
#include<iomanip>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int N;
vector<pair<int,double> > adj[1002];
double d[1002];
int color[1002],p[1002];
void dijkstra(int s){
	priority_queue<pair<double,int> > PQ;
	rep(i,N){
		d[i]=INFl;
		color[i]=0;
		p[i]=-1;
	}
	d[s]=0;
	color[s]=1;
	PQ.push(mp(0,s));
	while(!PQ.empty()){
		pair<double,int> f=PQ.top();
		PQ.pop();
		int u=f.second;
		color[u]=2;
		if(d[u]< -f.first) continue;
		rep(j,adj[u].size()){
			int v=adj[u][j].first;
			if(color[v]==2) continue;
			if(d[v]>d[u]+adj[u][j].second){
				d[v]=d[u]+adj[u][j].second;
				PQ.push(mp(-d[v],v));
				color[v]=1;
				p[v]=u;
			}
		}
	}
}
int main(){
	pint st,go;
	pint x[1002];
	int r[1002];
	int bnum;
	scan(st.first);scan(st.second);scan(go.first);scan(go.second);
	scan(bnum);
	N=bnum+2;
	x[0]=st,x[bnum+1]=go,r[0]=0,r[bnum+1]=0;
	rep1(i,bnum){
		scan(x[i].first);scan(x[i].second);scan(r[i]);
	}
	rep(i,bnum+1){
		for(int j=i+1;j<=bnum+1;j++){
			double nobarrier=sqrt(pow(x[i].first-x[j].first,2)+pow(x[i].second-x[j].second,2))-(r[i]+r[j]);
			nobarrier=max(nobarrier,0.0);
			adj[j].push_back(mp(i,nobarrier));
			adj[i].push_back(mp(j,nobarrier));
		}
	}
	dijkstra(0);
	prin(setprecision(10)<<d[N-1]);
	return 0;
}


Measured memory_bytes: 22676
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n,m,cnt,ans;
int main()
{
	int i,s,a,b,j,k;
	scanf("%lld%lld",&n,&m);
	if(n==1 && m==1){printf("1");return 0;}
	if(n==1){printf("%lld",m-2);return 0;}
	if(m==1){printf("%lld",n-2);return 0;}
	if(n==2 || m==2){printf("0");return 0;}
	printf("%lld",(n-2)*(m-2));
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll fc[2002002]={1ll},nv[2002002]={1ll};

ll rwpw(ll a, ll p = MOD-2){
	ll ret = 1ll;
	while(p){
		if(p&1){
			mul_mod(ret,a);
		}
		mul_mod(a,a);
		p /= 2;
	}
	return ret;
}

int main(void){
	int r[2],c[2],i;
	ll x,y,ans=0ll;
	for(i=1; i<=2000020; ++i){
		fc[i] = fc[i-1]*i%MOD;
		nv[i] = rwpw(fc[i]);
	}
	for(i=0; i<2; ++i){
		cin >> r[i] >> c[i];
	}
	for(i=r[0]; i<=r[1]; ++i){
		x = fc[c[0]+i]*nv[c[0]]%MOD;
		y = fc[c[1]+i]*nv[c[1]]%MOD;
		mul_mod(x,c[0]);
		mul_mod(y,c[1]+i+1);
		add_mod(y,MOD-x);
		mul_mod(y,nv[i+1]);
		add_mod(ans,y);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 31488
{-# LANGUAGE CPP #-}
module Main where

import qualified Data.Vector.Unboxed as V 
import qualified Data.Map.Strict as M
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Maybe
import Data.Char
import qualified Data.List as L

dump :: (Show a) => a -> IO()
#if __GLASGOW_HASKELL__ >= 800
dump x = print x
#else
dump _ = pure ()
#endif

-- "101010" -> [1,0,1,0,1,0]
readToList :: String -> [Int]
readToList [] = []
readToList (x:xs) = read [x] : readToList xs

 
readInt :: BS.ByteString -> Int
readInt = fst . fromJust . BS.readInt

getInt :: IO Int
getInt = readInt <$> BS.getLine

-- "10 10 10" -> [10, 10, 10]
getlist :: IO [Int]
getlist = (fmap (read . BS.unpack) . BS.words) <$> BS.getLine

-- "10 10 10" -> [10, 10, 10]
getIntVec :: Int -> IO (V.Vector Int)
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readmat :: Int -> IO [[Int]]
readmat rows = replicateM rows getlist

newtype UF a = UF (M.Map a a) deriving (Show) -- Map node parent

makeuf :: Int -> UF Int
makeuf n = let m = M.fromList $ zip [0..n] [0..n]
                in UF m

union :: (Eq a, Ord a) => a -> a -> UF a -> UF a
union l r uf@(UF m) = let lp = find l uf
                          rp = find r uf
                      in if lp == rp
                         then uf
                         else if size l uf < size r uf
                              then UF $ M.update (const $ Just rp) lp m
                              else UF $ M.update (const $ Just lp) rp m

find :: (Eq a, Ord a) => a -> UF a -> a
find x uf@(UF m) = let px = m M.! x
                in if px == x
                   then px
                   else find px uf -- TODO 貼り直し

size :: (Eq a, Ord a) => a -> UF a -> Int
size x (UF m) = M.size $ M.filter (\par -> par==x) m

genbit :: Int -> [[Int]]
genbit 0 = []
genbit 1 = [[0],[1]]
genbit len = do
  x <- [0,1]
  map (x:) $ genbit (len-1)

base :: Int
base = 10 ^ 9 + 7

forn :: (Num a, Enum a, Monad m) => a -> (a -> m b) -> m [b]
forn x = forM [0..(x-1)]

count :: (Eq a) => a -> [a] -> Int
count y = length . filter (== y)

main :: IO()
main = do
  [n] <- getlist
  xs <- getlist
  let rest = foldl (\i x -> if x == i then i+1 else i) 1 xs
  print $ if rest == 1 
           then -1
           else n - rest + 1



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

int main()
{
    int n;
    cin >> n;
    vector<int> h(n);
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> h.at(i);
    }

    for (int i = 0; i < n; i++)
    {
        bool flag = true;
        for (int j = 0; j < i; j++)
        {
            if(h.at(j) > h.at(i))
            {
                flag = false;
            }
        }
        if(flag)
            {
                count++;
            }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))

c = defaultdict(int)
for ai in a:
    c[ai] += 1

m = 0
for n in c.keys():
    sum_c = c[n]
    if n - 1 in c: sum_c += c[n - 1]
    if n + 1 in c: sum_c += c[n + 1]
    m = max(m, sum_c)
print(m)


Measured memory_bytes: 14564
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

/* Dijkstra O(NlogM)*/

template <typename Type = int>
struct Dijkstra{
  int V;
  vector<vector<pair<int,Type>>> G;
  vector<Type> cost;

  Dijkstra(int n):
    V(n), G(n, vector<pair<int,Type>>()) {}

  void add_edge(int u, int v, Type c){
    G[u].push_back({v, c});
  }

  Type solve(int s, int g = -1){
    cost.assign(V, -1);
    priority_queue<pair<Type,int>> pq;
    Type max_cost = 0;

    pq.push({0, s});

    while(pq.size()){
      Type now_cost = pq.top().first;
      int now = pq.top().second;
      pq.pop();

      if(cost[now] >= 0) continue;

      cost[now] = -now_cost;
      max_cost = max(max_cost, -now_cost);

      if(now == g) return -now_cost;

      for(int i=0; i<(int)G[now].size(); i++)
        pq.push({now_cost - G[now][i].second, G[now][i].first});
    }

    return max_cost;
  }
};

int t[SIZE], e[SIZE];

int main(){
  int N, R;

  scanf("%d%d", &N, &R);

  Dijkstra<ll> dijk(N+1);

  int S = N;

  for (int i=0; i<N; i++) {
    scanf("%d%d", t+i, e+i);
    dijk.add_edge(S, i, t[i]);
  }

  for (int i=0; i<R; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--; b--;
    dijk.add_edge(b, a, c-1);
  }

  dijk.solve(S);

  ll ans = 0;

  for (int i=0; i<N; i++) {
    ans += dijk.cost[i] * e[i];
  }

  cout << ans << endl;


  return 0;
}



Measured memory_bytes: 14592
#include<stdio.h>
int main(){

int n,d=0;
scanf("%d",&n);
char c[n];
scanf("%s",c);
for(int i=0;i<n;i++){

  if(c[i]=='A'&&c[i+1]=='B'&&c[i+2]=='C'){
    d++;
  }

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

}


Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;

#define show(x) cerr << #x << " = " << x << endl ;
#define input_from_file freopen("input.txt","r",stdin)
#define output_to_file freopen("output.txt" , "w",stdout)
#define fastio ios_base::sync_with_stdio(0)
#define endl '\n'

const int N = 1e3+1 , W = 2e4+5;
vector < vector < int > > v(N , vector < int > (3));
long long dp[N][W];
bool compare(vector < int > &v1 , vector < int > &v2)
{
	return (v1[0] + v1[1] < v2[0] + v2[1]);
}
int main()
{
	 #ifdef LOCAL
        input_from_file;
        output_to_file;
    #endif
	fastio;cin.tie(0);cout.tie(0);
	int n ; cin >> n ;
	for(int i = 1 ; i <= n ; ++i)
		cin >> v[i][0] >> v[i][1] >> v[i][2];
	sort(v.begin()+1 , v.begin()+n+1 , compare);
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 0 ; j < W ; ++j)
		{
			dp[i][j] = max(dp[i][j] , dp[i-1][j]);
			if(v[i][1] >= j && v[i][0] + j < W)
			{
				dp[i][j+v[i][0]] = max(dp[i][j+v[i][0]] , dp[i-1][j] + v[i][2]);
				// cerr <<i << " " << j <<" "<< j + v[i][0] << " "<<dp[i][j+v[i][0]] << endl; 
			}
			// cerr << i << " "<< j << " "<< dp[i][j] <<endl;
		}
	}
	long long ans = INT_MIN;
	for(int i = 1 ; i < W ; ++i)
		ans = max(dp[n][i] , ans);
	cout << ans;

	return 0;
}

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

using lli = long long int;
using Vint = vector<int>;
using Vlli = vector<lli>;
using Wint = vector<Vint>;
using Wlli = vector<Vlli>;
using pii = pair<int, int>;
using pll = pair<lli, lli>;

const int MOD = 1e9 + 7;
const int INFi = 2e9 + 1;
const lli INFl = (lli)(9e18) + 1;
// const vector<pii> DXDY = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define FOReq(i, a, b) for(int (i) = (a); (i) <= (b); (i)++)
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); i--)
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define vREP(i, vec) for(auto (i) = (vec).begin(); (i) != (vec).end(); (i)++)
#define vrREP(i, vec) for(auto (i) = (vec).end()-1;(i) != (vec).begin()-1;(i)--)

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

template<class T>
T gcd(T a, T b){
  if(b == 0) return a;
  T q = a % b;
  if(q == 0) return b;
  return gcd(b, q);
}

int main(void){
  int n; cin >> n;
  vector<int> A(n);
  vREP(ele, A) cin >> *ele;
  int res = A.at(n-1);
  REP(i, n - 1) res = gcd<int>(res, A.at(i));
  cout << res << "\n";
  return 0;
}

Measured memory_bytes: 640
import sys
p=['41412121','41212141','21414121','21214141','14141212','14121214','12141412','12121414']
for e in sys.stdin:
 d={}
 for f in p:d[sum(s-t for s,t in zip(map(int,e.split()),map(int,f))if s>t)]=f
 print(*list(d[min(d)]))


Measured memory_bytes: 5724
from collections import defaultdict

S = input()
B = defaultdict(int)
B[0]=1
ans=0
prev=0

for i in range(len(S)):
    m=(prev+int(S[-i-1])*pow(10,i,2019))%2019
    ans+=B[m]
    B[m]+=1
    prev=m

print(int(ans))

Measured memory_bytes: 9644
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>
#include <tuple>
#include <iostream>
#include <deque>
#include <array>
#include <set>
#include <functional>
#include <memory>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
int solve(const int max, const std::vector<int>& counter, const std::vector<int>& target, const int counter_pos, const int overflow, std::vector<std::vector<int>>& memo) {
	if (counter_pos == 0) {
		return solve(max, counter, target, counter_pos + 1, 0, memo) + (target[0] - counter[0] + max) % max;
	}
	else if (counter_pos == counter.size()) {
		return 0;
	}
	else if (memo[counter_pos][overflow] >= 0) {
		return memo[counter_pos][overflow];
	}
	else {
		auto prev = (target[counter_pos - 1] - counter[counter_pos - 1] + max) % max;
		auto temp = (counter[counter_pos] + prev) % max;
		memo[counter_pos][overflow] = solve(max, counter, target, counter_pos + 1, (prev + (target[counter_pos] - temp + max) % max >= max) ? overflow + 1 : overflow, memo) + (target[counter_pos] - temp + max) % max;
		if ((target[counter_pos] - counter[counter_pos] + max) % max <= prev) {
			memo[counter_pos][overflow] = std::min(memo[counter_pos][overflow], solve(max, counter, target, counter_pos + 1, overflow, memo));
		}
		if (overflow > 0) {
			memo[counter_pos][overflow] = std::min(memo[counter_pos][overflow], solve(max, counter, target, counter_pos + 1, overflow - 1, memo));
		}
		return memo[counter_pos][overflow];
	}
}
int main() {
	while (true) {
		int n, m; std::cin >> n >> m;
		if (n == 0) break;
		std::vector<int>counter(n); for (auto& a : counter) std::cin >> a;
		std::vector<int>target(n); for (auto& b : target) std::cin >> b;
		std::vector<std::vector<int>> memo(n, std::vector<int>(n, -1));
		std::cout << solve(m, counter, target, 0, 0, memo) << std::endl;
	}
}


Measured memory_bytes: 6860
#include<stdio.h>
int main()
{
    int a,b,c,d,e;
    scanf("%d%d",&a,&b);
    c=a+b;
    d=a-b;
    e=a*b;
    if(c>=d&&c>=e)
        printf("%d\n",c);
    else if(d>=c&&d>=e)
        printf("%d\n",d);
    else if(e>=c&&e>=d)
        printf("%d\n",e);
    return 0;
}


Measured memory_bytes: 128
def palindrome?(t)
  ok = true
  for i in 0...(t.length / 2) do
    if t[i] != t[-1 - i]
      ok = false
      break
    end
  end
  return ok
end

s = gets.chomp
n = s.length
puts (palindrome?(s) && palindrome?(s.slice(0, (n - 1) / 2)) && palindrome?(s.slice((n + 1) / 2, (n - 1) / 2))) ? "Yes" : "No"


Measured memory_bytes: 1788
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>    // bitset
#include <cctype>    // isupper, islower, isdigit, toupper, tolower
#include <cstdint>   // int64_t, int*_t
#include <cstdio>    // printf
#include <deque>     // deque
#include <iomanip>   // setprecision
#include <iostream>  // cout, endl, cin
#include <map>       // map
#include <queue>     // queue, priority_queue
#include <set>       // set
#include <stack>     // stack
#include <string>    // string, to_string, stoi
#include <tuple>     // tuple, make_tuple
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <utility>       // pair, make_pair
#include <vector>        // vector
using namespace std;

int gcd(long long a, long long b) { return b != 0 ? gcd(b, a % b) : a; }
// cout << fixed << setprecision(10);

int main() {
    int N;
    cin >> N;
    string ret = "APPROVED";
    for(size_t i = 0; i < N; i++) {
        int a;
        cin >> a;
        if (a%2 == 0) {
            if (a%3 != 0 && a%5 != 0) {
                ret = "DENIED";
                break;
            }
        }
    }
    cout << ret << endl;
}

Measured memory_bytes: 384
#include <stdio.h>
int main(void){
    int x,y,W,H,r;
    scanf("%d %d %d %d %d\n",&W,&H,&x,&y,&r);
    if(x-r>=0&&x+r<=W&&y-r>=0&&y+r<=H){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 2140
#include<iostream>
using namespace std;
int main(void)
{
    int n;
    int a[1000],i;
    cin>>n;


    for(i=0;i<n;i++)
    {
    
        cin>>a[i];

    }

    for(i=n-1;i>=0;i--)
    {
        cout<<a[i];
    
        if(i>0)
        {
            cout<<" ";
        }

    }
    

    cout<<endl;
return 0;
}


Measured memory_bytes: 3120
#include<iostream>
#include<stdio.h>
#include<string>
#include<stdlib.h>
using namespace std;

long long n;

long long *T;


void insert(long long a){
  for(long long i = 0; i < n; i++){
    long long j = (((a % n) + i * (1 + a % (n - 1))) % n);
    if(T[j] == '\0'){
      T[j] = a;
      break;
    }
  }
}

string findx(long long a){
  for(long long i = 0; i < n; i++){
    long long j = (((a % n) + i * (1 + a % (n - 1))) % n);
    if(T[j] == a){
      return "yes";
    }
    else if(T[j] == '\0'){
      return "no";
    }
  }
}

int main(){

  cin >> n;

  string s, x;

  long long cnt = 0;

  string *yn = new string[n];

  T = new long long[n];



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

    cin >> s >> x;

    long long a = 0, b = 1;

    for(long long i = 0; i < (long long)x.size(); i++){

      if(x[i] == 'A'){
        a = a + 1 * b;
      }
      else if(x[i] == 'C'){
        a = a + 2 * b;
      }
      else if(x[i] == 'G'){
        a = a + 3 * b;
      }
      else if(x[i] == 'T'){
        a = a + 4 * b;
      }

      b = b * 10;

    }

    if(s == "insert"){
      insert(a);
    }
    else if(s == "find"){
      yn[cnt] = findx(a);
      cnt++;
    }
  }

  for(long long i = 0; i < cnt; i++){
    cout << yn[i] << endl;
  }
  return 0;
}



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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

typedef long long ll;
typedef long double R;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:

int main() {
  string S; cin >> S;
  string s="";
  for(int i = 0; i < S.size(); ++i) {
    if(i!=0) {
      if(S[i] == 'A' && S[i-1] == 'A') {
        cout << "NO" << endl;
        return 0;
      } else if(S[i] == 'A' && S[i-1] == 'K') {
        cout << "NO" << endl;
        return 0;
      } else if(S[i] == 'A' && S[i-1] == 'I') {
        cout << "NO" << endl;
        return 0;
      }
    }
    if(S[i] == 'A') continue;
    s.push_back(S[i]);
  }
  if(s == "KIHBR") {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

const int maxn = 333;

int n;
char s[maxn][maxn], t[maxn][maxn];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    REP(i, n) cin >> s[i];
    int answer = 0;
    REP(b, n) {
        REP(i, n) REP(j, n) t[i][j] = s[i][(j + b) % n];
        bool ok = 1;
        REP(i, n) REP(j, n) if (t[i][j] != t[j][i]) {
            ok = 0;
            break;
        }
        if (ok) answer += n;
    }
    cout << answer << "\n";
    return 0;
}

Measured memory_bytes: 512
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

score = B[0]
tmp = A[0]

for i in range(1, N):
	score += B[i]
	if (tmp == (A[i] - 1)):
		score += C[tmp-1]
	tmp = A[i]

print(score)

Measured memory_bytes: 3064
#include <fstream>
#include <iostream>
#include <string>

#define nmax 105
using namespace std;
char semn[5];
string s;
int n, i;

bool finish;

void bkt(int p, int sum)
{
    if (finish)
        return;
    if (p <= 3) {
        semn[p - 1] = '+';
        bkt(p + 1, sum + (s[p] - '0'));

        semn[p - 1] = '-';
        bkt(p + 1, sum - (s[p] - '0'));
    }
    else {
        if (finish)
            return;

        if (sum == 7) {
            cout<<s[0];

            cout<<semn[0];
            cout<<s[1];

            cout<<semn[1];
            cout<<s[2];

            cout<<semn[2];
            cout<<s[3];

            finish = 1;

            cout<<'='<<'7'<<'\n';
        }
    }
}

int main()
{
    getline(cin, s);
    bkt(1, s[0]-'0');

    return 0;
}


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

using namespace std;


int main() {
    int n, k, s;
    cin >> n >> k >> s;
    vector<int> ans;
    if(s == 1) {
        for(int i = 0; i < k; i++) {
            ans.push_back(1);
        }
        for(int i = 0; i < n - k; i++) {
            ans.push_back(3);
        }
    }
    else if(s == 2) {
        for(int i = 0; i < k; i++) {
            ans.push_back(2);
        }
        for(int i = 0; i < n - k; i++) {
            ans.push_back(3);
        }
    }
    else {
        for(int i = 0; i < k; i++) {
            ans.push_back(s);
        }
        for(int i = 0; i < n - k; i++) {
            ans.push_back(s-1);
        }
    }
    for(int i = 0; i < n - 1; i++) {
        cout << ans[i] << " ";
    }
    cout << ans[n-1] << "\n";
    return 0;
}

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n), b(n), c(n);
	typedef long long nagai;
	for (auto& x : a)
		cin >> x;
	for (auto& x : b)
		cin >> x;
	for (auto& x : c)
		cin >> x;
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	sort(c.begin(), c.end());
	int p = 0;
	vector<nagai> cntb(n), cntc(n);
	for (int i = 0; i < n; ++i)
	{
		int x = b[i];
		while (p < n && a[p] < x)
			++p;
		cntb[i] = p;
	}
	p = 0;
	nagai sum = 0;
	nagai ans = 0;
	for (int x : c)
	{
		while (p < n && b[p] < x)
			sum += cntb[p++];
		ans += sum;
	}
	cout << ans << endl;
}


Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
	char ch=getchar();
	putchar(ch);
	for(int i=1;i<=5;i++)ch=getchar();
	
	putchar(ch);
	for(int i=1;i<=5;i++)ch=getchar();
	
	putchar(ch);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
const int M=998244353;
int n,a[maxn],b[maxn],ans,f[maxn];
char s[maxn];
void add(int &x,int y){x+=y; if (x>=M) x-=M;}
int calc(int d){
    int p=0;
    for (int i=0;i<d;i++) b[i]=a[i],p=(p*2+a[i])%M;
    for (int i=d;i<n;i++) b[i]=b[i-d]^1;
    bool flag=1;
    for (int i=0;i<n;i++) if (a[i]!=b[i]){
        if (a[i]<b[i]) flag=0;
        break;
    }
    if (flag) add(p,1);
    return p;
}

int main(){
    scanf("%d%s",&n,s);
    for (int i=0;i<n;i++) a[i]=s[i]-'0';
    f[1]=1; for (int i=2;i<maxn;i++) f[i]=M-1ll*(M/i)*f[M%i]%M;
    for (int i=1;i<maxn;i++) for (int j=2;j*i<maxn;j++) add(f[i*j],M-f[i]);
    for (int i=1;i<maxn;i++) if (i%2==1&&n%i==0) add(ans,1ll*f[i]*calc(n/i)%M);
    printf("%d\n",1ll*n*2*ans%M);
    return 0;
}


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

int main() {
  double A, B;
  cin >> A >> B;
  
  for(int i=1;i<10100;i++){
    if((int)(i*0.08)==A && (int)(i*0.1)==B){
      cout << i << endl;
      break;
    }
    if(i==10099) cout << -1 << endl;
  }
  
  //cout << (int)(value*0.1);
}

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

using namespace std;

int main()
{
  string s;
  int count;
  cin >> s;

  for (int k; k < s.size(); k++)
  {
    if (s[k] == '1') count++; 
  }
  printf("%d\n", count);
  return 0;
}

Measured memory_bytes: 256
//https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/M
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int N;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;

	vector<string> ans;
	if (N == 1) ans.push_back("0");
	else if (N == 2) ans.push_back("0"), ans.push_back("11");
	else {
		rep(i, 0, N - 1) {
			string ones = "";
			rep(j, 0, i) ones += "1";
			ans.push_back("0" + ones + "0");
		}
	}

	int n = ans.size();
	printf("%d\n", n);
	fore(s, ans) printf("%s\n", s.c_str());
}





/* ///////////////////////// writeup1 start
///////////////////////// writeup2 start
N=1 {0}
N=2 {0, 11}
N=3 {00, 111}
N=4 {00, 111, 1010}
N=5 {00, 010, 0110, 01110}
N=6 {101010, 10100, 1100}
///////////////////////// writeup2 end */
//　


Measured memory_bytes: 3464
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

int32_t main(){
	IOS;
	int n, m, k;
	cin >> n >> m >> k;
	char arr[n][m];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> arr[i][j];
		
	int ans = 0;
	for(int i = 0; i < 1<<n; i++){
		for(int j = 0; j < 1<<m; j++){
			int cur = 0;
			for(int x = 0; x < n; x++)
				for(int y = 0; y < m; y++)
					if( arr[x][y] == '#' && ((1<<x)&i) == 0 && ((1<<y)&j) == 0 )
						cur++;
			if( cur == k )
				ans++;

		}
	}

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

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define inf 999999999
#define loop(i, a, b) for (int i = (a), i##len = (b); i < i##len; ++i)
#define rep(i, n) loop(i, 0, n)
#define lin long long
#define lfl long double

int main(void)
{
    string s;
    cin >> s;
    string y = s.substr(0,4);
    string m = s.substr(5,2);
    int yy = atoi(y.c_str());
    int mm = atoi(m.c_str());

    if(yy > 2019 || (yy >= 2018 && mm >= 5))
        cout << "TBD" << endl;
    else
        cout << "Heisei" << endl;

    return 0;
}


Measured memory_bytes: 256
n = int(input())
d = {}
d['AC'] = 0
d['WA'] = 0
d['TLE'] = 0
d['RE'] = 0

for _ in range(n):
	s = input()
	d[s] += 1

print("AC x",d["AC"])
print("WA x",d["WA"])
print("TLE x",d["TLE"])
print("RE x",d["RE"])

Measured memory_bytes: 69820
n,m = map(int,input().split())
row = []
count = [0]*m
ans = 0
for it in range(n):
	row.append(list(map(int,input().split())))
# print(row)
# print(count)
for it in range(n):
	for mc in row[it][1:]:
		count[mc-1] += 1
		if count[mc-1] == n:
			ans += 1
# print(count)
print(ans)


Measured memory_bytes: 3060
fun main(arr: Array<String>) {
    var str = readLine()!!
    var prev = ""
    var ans = 0
    while (str.length > 0) {
        var tmp = ""
        if(str.substring((0 until 1)) == prev) {
            if(str.length == 1) {
                break
            } else {
                tmp = str.substring(0 until 2)
                str = str.drop(2)
                ans++
            }
        } else {
            tmp = str.substring(0 until  1)
            str = str.drop(1)
            ans++
        }
        prev = tmp
    }
    println(ans)
}



Measured memory_bytes: 58168
#include <iostream>

int main(){
  int n,m,i,lMax=0,rMin=100000;
  std::cin>>n>>m;
  int l[m],r[m];
  for (i=0;i<m;i++)std::cin >> l[i]>>r[i];
  for (i=0;i<m;i++){
    if (lMax<l[i])lMax=l[i];
    if (rMin>r[i])rMin=r[i];
  }
  if (rMin-lMax+1>0)std::cout << rMin-lMax+1 << '\n';
  else std::cout << 0 << '\n';

}


Measured memory_bytes: 1152
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cctype>

using namespace std;

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define Decimal fixed << setprecision(20)
#define SHOWP(x) cerr<<"["<<(x).FI<<", "<<(x).SE<<"]";
#define SHOWX(x) cerr<<#x<<": "<<x<<endl;
#define SHOWVEC(v, e) REP(i, e) cerr << (v[i]) << ' '; cerr << endl;
#define SHOW2D(a, h, w) REP(i, h){REP(j, w)cerr<<setw(3)<<(a[i][j])<<' ';cerr<<endl;}
constexpr int INF = 1 << 30 - 1;
constexpr long long LLINF = 1LL << 60;
constexpr long long MOD = 1000000007;

typedef long long ll;
typedef pair<ll, ll> P;


int main()
{
  ll N, M;
  cin >> N >> M;
  vector<ll> A(N);
  REP(i, N) cin >> A[i];
  vector<P> v;
  REP(i, M) {
    ll B, C;
    cin >> B >> C;
    v.PB(MP(C, B));
  }
  sort(ALL(v), greater<P>());
  ll cnt = 0;
  vector<ll> vt;
  REP(i, M) {
    REP(j, v[i].SE) {
      vt.PB(v[i].FI);
      cnt++;
      if (cnt >= N) break;
    }
    if (cnt >= N) break;
  }
  while (vt.size() < N) vt.PB(-1);
  sort(ALL(A));
  ll ans = 0;
  REP(i, N) {
    ans += max(A[i], vt[i]);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 4464
// ProblemURL : https://atcoder.jp/contests/abc072/tasks/abc072_b
// ---------------------------------------------
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	ans := make([]byte, 0, len(s))
	for i := range s {
		if i%2 == 0 {
			ans = append(ans, s[i])
		}
	}
	fmt.Println(string(ans))
}


Measured memory_bytes: 1408
#include <stdio.h>
#include <string.h>

int main(void)
{
    int N, M, a, b;
    int lane[11][3];
    int car[10000][2];
    int i, j;
    int top;
    int min;
    int p;
    
    scanf("%d%d", &N, &M);

    memset(lane, 0, sizeof(lane));
    memset(car, 0, sizeof(car));
    for (i = 1; i <= 9999; i++){
        car[i][0] = i;
    }
    
    for (i = 0; i < M; i++){
        scanf("%d%d", &a, &b);
        if (a == 0){
            top = car[lane[b][0]][0];
            printf("%d\n", top);
            lane[b][0] = car[top][1];
            lane[b][2]--;
            if (lane[b][2] == 0){
                lane[b][1] = 0;
            }
            car[top][1] = 0;
        }
        else {
            min = 1;
            for (j = 1; j <= N; j++){
                if (lane[min][2] > lane[j][2]){
                    min = j;
                }
            }
            if (lane[min][2] == 0){
                lane[min][0] = lane[min][1] = b;
            }
            else {
                car[lane[min][1]][1] = b;
                lane[min][1] = b;
            }
            car[b][1] = 0;
            lane[min][2]++;
        }
#if 0        
        for (j = 1; j <= N; j++){
            printf("lane%d(top=%d end=%d n=%d):", j, lane[j][0], lane[j][1], lane[j][2]);
            p = lane[j][0];
       
            while (1){
                printf("(%d next=%d)", car[p][0], car[p][1]);
                if (car[p][1] == 0){
                    break;
                }
                p = car[p][1];
            }
            printf("\n");
        }
#endif        
        
    }
    
    return (0);
}



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

using int64 = long long;

static int table[200005][31];

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

    int N;
    cin >> N;

    vector<int64> x(N);
    for (int i = 0; i < N; i++) {
        cin >> x[i];
    }

    int64 L;
    cin >> L;

    // ダブリングテーブルの構築
    for (int i = 0; i < N; i++) {
        int idx = lower_bound(x.begin(), x.end(), x[i] + L) - x.begin();
        if (idx >= N or x[idx] == x[i] + L) {
            table[i][0] = idx;
        } else {
            table[i][0] = idx - 1;
        }
    }

    /*
    cerr << "ダブリングテーブル" << endl;
    for (int i = 0; i < N; i++) {
        cerr << "[" << i + 1 << "] ";
        for (int j = 0; j < 4; j++) {
            cerr << "(" << j << ", " << table[i][j] << ") ";
        }
        cerr << endl;
    }
    */

    for (int shift = 1; shift < 31; shift++) {
        for (int i = 0; i < N; i++) {
            int nxt = table[i][shift - 1];
            if (nxt < N) nxt = table[nxt][shift - 1];
            table[i][shift] = nxt;
        }
    }

    /*
    cerr << "ダブリングテーブル" << endl;
    for (int i = 0; i < N; i++) {
        cerr << "[" << i + 1 << "] ";
        for (int j = 0; j < 4; j++) {
            cerr << "(" << j << ", " << table[i][j] << ") ";
        }
        cerr << endl;
    }
    */

    int Q;
    cin >> Q;

    for (int i = 0; i < Q; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (a > b) swap(a, b);
        int ans = 0,
            ptr = a;
        while (ptr < b) {
            int idx = 0;
            // table[ptr][j]<=bを満たす最大のjを見つける
            for (int j = 0; j < 31; j++) {
                if (table[ptr][j] <= b) {
                    idx = j;
                }
            }
            ptr = table[ptr][idx];
            ans += 1 << idx;
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 13952