akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;



int main()
{
	vector<vector<int> > graph;
	int Nodes(0), edges(0);
	cin >> Nodes >> edges;
	graph.resize(Nodes);
	for (int i = 0; i < edges; ++i)
	{
		int left, right;
		cin >> left >> right;
		graph[left - 1].push_back(right - 1);
		graph[right - 1].push_back(left - 1);
	}
	queue<int> Q;
	set<int> visited;
	visited.insert(0);
	vector<int> signpost(Nodes);
	Q.push(0);
	while (!Q.empty())
	{
		int prefix(0);
		prefix = Q.front();
		Q.pop();
		for (int i = 0; i < graph[prefix].size(); ++i)
		{
			int next = graph[prefix][i];
			if (visited.count(next))	continue;
			visited.insert(next);
			Q.push(next);
			signpost[next] = prefix;
		}
	}
	if (visited.size() == Nodes)
	{
		cout << "Yes" << endl;
		for (int i = 1; i < signpost.size(); ++i)
			cout << signpost[i] + 1 << endl;
	}
	else
		cout << "No" << endl;
}



Measured memory_bytes: 14940
#include <iostream>
#include <iomanip>
#include<vector>
#include <algorithm>
#include <queue>
#include<string>
#include <map>
#include <cmath>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <utility>
#include <set>
#include <bitset>
#include <cstring>
typedef long long ll;
typedef long double ld;

#define REP(i,s,n)for(ll i=s;i<(n);++i)
#define rep(i,n) REP(i,0,n)
using namespace std;
using Graph = vector<vector<ll>>;
/* 4 方向への隣接頂点への移動を表すベクトル */
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
ll H, W;
ll sX, sY, gX, gY;
char maze[100];
bool reached[100];
ll sectin = 0;
ll flg = true;
vector<string>field;

int main() {
	cin >> H >> W;
	field = vector<string>(H);
	Graph status = Graph(H,vector<ll>(W,-1));
	queue<pair<ll, ll>>que;
	rep(i,H) {
		cin >> field[i];
		rep(j,W) {
			if (field[i][j]=='#') {
				status[i][j] = 0;
				que.push(make_pair(i, j));
			}
		}
	}

	ll ans = 0;
	while (!que.empty()) {
		pair<ll, ll>tmp = que.front();
		que.pop();
		ll x = tmp.first;
		ll y = tmp.second;

		rep(directions,4) {
			ll nextX = x + dx[directions];
			ll nextY = y + dy[directions];
			if (nextX < 0 || H <= nextX || nextY < 0 || W <= nextY)continue;
			if (field[nextX][nextY] == '#')continue;

			field[nextX][nextY] = '#';
			status[nextX][nextY] = status[x][y] + 1;
			ans = max(ans, status[nextX][nextY]);
			que.push(make_pair(nextX, nextY));
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 29188
#include <stdio.h>


int main()
{
    int n,i,x,m[100],min=1000,nsum=0,msum=0;
    scanf("%d %d",&n,&x);
    
    for(i=0;i<n;i++){
        scanf("%d",&m[i]);
        if(m[i]<min){min=m[i];}
        nsum+=m[i];
    }
    x-=nsum;
    msum=n+x/min;
    printf("%d\n",msum);
    
    

    return 0;
}

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

const ll MAX_N = 200010;
ll n;
vector<pair<int, int>> P(MAX_N);

int main() {
  cin >> n;
  for (ll i = 1; i <= n; i++) {
    int a, b, c;
    a = i % 10;
    b = i / 10;
    if (b == 0) c = a;
    else {
      while (b > 0) {
        c = b % 10;
        b /= 10;
      }
    }
    P[i].second = a;
    P[i].first = c;
  }
  
  ll ans = 0;

  if (n < 10) {
    for (ll i = 1; i <= n; i++) {
      for (ll j = 1; j <= n; j++) {
        if (P[i].first == P[j].second && P[i].second == P[j].first) {
          ans++;
        }
      }
    }
  }
  else {
    ll a = n / 10;
    ans = a*a + 8;
    for (ll i = a*10 + 1; i <= n; i++) {
      for (ll j = 1; j <= n; j++) {
        if (P[i].first == P[j].second && P[i].second == P[j].first && i == j) {
          ans++;
        }
        else if (P[i].first == P[j].second && P[i].second == P[j].first) {
          ans = ans + 2;
        }
      }
    }
  }
  cout << ans << endl;
}


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

int main() {
  int a,b;
  cin >> a >> b;
  int a_b =0; int b_a=0;
  for(double i=0; i<b; i++) {
    a_b += ((int)pow(10, i))*a;
  }
  for(double i=0; i<a; i++) {
    b_a += ((int)pow(10, i))*b;
  }

  if(a>b) {
    cout << b_a;
  } else if(a<b) {
    cout << a_b;
  } else {
    cout << a_b;
  }
}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  l=[]
  for _ in range(m):
    a=LI()
    l.append(a[1:])

  lp=LI()

  a=[]
  for i in range(1<<n):
    _a=[]
    for j in range(n):
      if i&(1<<j):
        _a.append(1)
      else:
        _a.append(0)
    a.append(_a)

  ans=0
  for x in a:
    f=True
    for i,y in enumerate(l):
      _sum=0
      for z in y:
        _sum+=x[z-1]
      if _sum%2!=lp[i]:
        f=False
        break
    if f:
      ans+=1

  return ans

# main()
print(main())


Measured memory_bytes: 6988
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <map>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <sstream>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define ALL(x) (x).begin(),(x).end()
#define sort_key(struct_name,key_name) [](const struct_name &x, const struct_name &y){return x.key_name < y.key_name;}
#define pb(x) push_back(x)
typedef long long ll;
const ll MOD = 1e9 + 7;
using namespace std;

//main
int main(){
    double N,K; cin >> N >> K;
    double remain;
    double c;
    double dice;
    double p;
    rep(i,N){
        dice = i+1;
        c = 1.0;
        while(dice < K){
            c /= 2;
            dice *= 2;
        }
        p += c;
    }
    cout << setprecision(20) << p/N << endl;
}

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

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; }

#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define sqrep(i,cc,n) for(long long i=cc;i*i<=n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;

const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
const double PI = 3.1415926535;
const ll inf = 1001001001;
const ll e9  = 1000000000;
const ll mod = 1000000007;

ll xorp(ll p){
    ll q  = (p+1)/2; 
    if((p+1)%2==1){
        if(q%2==1){
            ll ans = 1^p;
            return ans;
        }else{
            ll ans = 0^p;
            return ans;
        }
    }else{
        if(q%2==1){
            ll ans = 1;
            return ans;
        }else{
            ll ans = 0;
            return ans;
        }
    }
}

int main(){
  ll a, b;
  cin >> a >> b;
  ll res =  xorp(b)^xorp(a-1);
  cout << res << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define m_p make_pair
#define pb push_back
#define si set<int>
#define ld long double
#define X first
#define Y second
#define st string
#define ull unsigned long long
#define mod 1000000007
#define INF 1000000007
#define x1 XZVJDFADSPFOE
#define y1 GASDIJSLDAEJF
#define x2 DFDAJKVOHKWIW
#define y2 PSFSAODSXVNMQ
#define LLINF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
inline void read(int &x)
{
	short negative=1;
    x=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
		if(c=='-')
			negative=-1;
		c=getchar();
	}
    while(c>='0' && c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=negative;
}
ll quickpower(ll n,ll k){
	ll ans=1;
	while(k){
		if(k%2){
			ans*=n;
			ans%=mod;
		}
		n*=n;
		n%=mod;
		k/=2;
	}
	return ans;
}
string int_to_string(int n)
{
	string s="";
	while(n)
	{
		int now=n%10;
		s+=now+'0';
		n/=10;
	}
	reverse(s.begin(),s.end());
	return s;
}
int string_to_int(string s)
{
	int n=0;
	rep(i,s.size())
	{
		n*=10;
		n+=s[i]-'0';
	}
	return n;
}
bool b[7][7];
int main()
{
	ios::sync_with_stdio(0);
	//think twice,code once
	int h,w,k;
	cin>>h>>w>>k;
	char c[7][7];
	rep(i,h)rep(j,w)cin>>c[i][j];
	int ans=0;
	rep(i,1<<(h+w))
	{
		memset(b,1,sizeof(b));
		rep(j,h)
		{
			if(i>>j&1)
			{
				rep(kk,w)b[j][kk]=0;
			}
		}
		forn(j,h,h+w-1)
		{
			if(i>>j&1)
			{
				rep(kk,h)b[kk][j-h]=0;
			}
		}
		int cnt=0;
		rep(j,h)rep(kk,w)if(c[j][kk]=='#'&&b[j][kk]==1)cnt++;
		if(cnt==k)
		{
		ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
char a[1005];
int main()
{
	cin>>a;
	int b;
	cin>>b;
	for(int i=0;i<strlen(a);i++)
	{
		if(i%b==0)
		{
			cout<<a[i];
		}
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const int mod=1e9+7;
const int inf = (1<<30);
string toBin(ll a);
void printMat(int arr[], int n);
void printMat(vector<int> arr, int n);
void printMat(vector<vector<int> > arr, int n, int m);
void printMat(vector<int> arr[], int n);
//void printMat(int arr[][], int n, int m);

void solve(){
	ll i, j, n;
	cin>>n;
	string s="";
	while(n>0){
		for(i=1;i<=26;i++){
			if((n-i)%26 ==0){
				break;
			}
		}
		s=char('a'+(i-1))+s;
		n=n-i;
		n/=26;
	}
	cout<<s;
}

int main()
{
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
	return 0;
}
string toBin(ll a){
	string s="";
	while(a>0){
		if(a&1){
			s="1"+s;
		}else{
			s="0"+s;
		}
		a>>=1;
	}
	return s;
}
void printMat(int arr[], int n){
	for(int i=0;i<n;i++){
		cout<<arr[i]<<" ";
	}cout<<endl;
}
void printMat(vector<int> arr, int n){
	for(int i=0;i<n;i++){
		cout<<arr[i]<<" ";
	}cout<<endl;
}
void printMat(vector<int> arr[], int row, int col){
	for(int i=0;i<row;i++){
		for(int j=0;j<col;j++){
			cout<<arr[i][j]<<" ";
		}cout<<endl;
	}cout<<endl;
}
void printMat(vector<vector<int> > arr, int row, int col){
	for(int i=0;i<row;i++){
		for(int j=0;j<col;j++){
			cout<<arr[i][j]<<" ";
		}cout<<endl;
	}cout<<endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
long long arr[1000000];
int main()
{
	long long n,i,sum,mn,x;
	x=0;
	sum=0;
	mn=1e16;
	cin>>n;
	for (i=0;i<n;i++)
	{
		cin>>arr[i];
		sum+=arr[i];
	}
	for (i=0;i<n;i++)
	{
		x+=arr[i];
		mn=min(mn,abs(sum-2*x));
	}
	cout<<mn<<endl;
}

Measured memory_bytes: 1792
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {
	int n; cin >> n;
	n = n % 10;
	if (n == 3) {
		cout << "bon" << endl;
	}
	else if (n == 0 || n == 1 || n == 6 || n == 8) {
		cout << "pon" << endl;
	}
	else {
		cout << "hon" << endl;
	}
	return 0;

}

Measured memory_bytes: 3524
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N ;
  int m = 10000;
  for(int i = 1; i < N ; i ++){
    int A = i;
    int B = N -i;
    int count_a = 0;
    int count_b = 0;
    while(A>0){
      count_a+= A % 10;
      A = A/10;
    }
    while(B> 0){
      count_b+= B % 10;
      B = B/10;
    }
    m = min(count_a + count_b, m);
  }
  cout << m << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<functional>
#include<utility>
#include<stack>
#include<queue>
#include<cmath>
#include<list>
#include<cstdint>
#include<vector>
#include<map>
#include<deque>
#define rep(i,rept)	for(int i = 0; i<(int)rept;++i)
typedef long long ll;
const ll MOD = 1e9 + 7;
using namespace std;

int main() {
	//10日目

	cin.tie(0); ios::sync_with_stdio(false);

	int n = 0,count = 0;
	int out = 114514;
	string s[50] = {};
	cin >> n;
	rep(i, n) {
		cin >> s[i];
	}

	for (int i = 'a'; i <= 'z'; i++) {

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

			for (int k = 0; k < s[j].size(); k++) {
				if (s[j][k] == i) {
					count++;
				}
			}

			out = std::min(out, count);

			count = 0;

		}

		std::cout << string(out, i);

		out = 114514;

	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <set>

using namespace std;

const string YES = "Yes";
const string NO = "No";

int main() {
  int N;
  cin >> N;
  set<string> s;
  string W;
  char lastc{'\0'};
  bool pred{true};
  for (int i = 0; i < N; ++i) {
    cin >> W;
    if(!s.insert(W).second || (lastc && W.front() != lastc)) {
      pred = false;
      break;
    }
    lastc = W.back();
  }

  cout << (pred ? YES : NO) << endl;
  return 0;
}


Measured memory_bytes: 256
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


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

    ans = INF
    total = sum(A)
    now = 0
    for i in range(N - 1):
        now += A[i]
        ans = min(ans, abs((total - now) - now))
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 25836
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
	int  x = 0, f = 1, c = getchar();
	for (;!isdigit(c); c = getchar()) if (c == '-') f ^= 1;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	return f ? x : -x;
}
int main() {
	int n, k;
	cin >> n >> k;
	cout << n - k + 1;
	return 0;
}


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

using namespace std ;
#define ll long long int
#define pb push_back
#define mod 1000000007;
#define db long double

int n;

int main()
{

   #ifdef patil
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif

   cin>>n;
   db p[n];
   for(int i=0;i<n;i++)cin>>p[i];
   	
   	db dp[n+1][n+1];
    for(int i=0;i<=n;i++)
    	dp[0][i]=0;
    dp[0][0]=1;

    for(int i=1;i<=n;i++)
    {
    	for(int j=0;j<=i;j++)
    	{
    		if(j==0)dp[i][j]=(1-p[i-1])*dp[i-1][0];
            else if(i==j)dp[i][j]=p[i-1]*dp[i-1][j-1];
    		else dp[i][j] = p[i-1]*dp[i-1][j-1] + (1-p[i-1])*dp[i-1][j];
    	}
    }
    db ans=0;
    int index = n/2;
    index++;
    for(int i=index;i<=n;i++)
    	ans +=dp[n][i]; 
    cout<<setprecision(15)<<ans<<endl;


	return 0;

}

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

using namespace std;

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

  for (int i = 1; i < 10; i ++) {
    for (int j = 1; j < 10; j ++) {
      cout << i << "x" << j << "=" << i * j << endl;
    }
  }
}


Measured memory_bytes: 3164
// #include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <numeric>
// #include <windows.h>
using namespace std;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
template<class T> using VVV = V<VV<T>>;
template<class T1, class T2> using P = pair<T1, T2>;
using I = int;
using D = double;
using B = bool;
using C = char;
using S = string;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = P<I, I>;
using VPII = V<PII>;
using PLL = P<LL, LL>;
using VPLL = V<PLL>;
using VI = V<I>;
using VVI = VV<I>;
using VLL = V<LL>;
using VVLL = VV<LL>;
using VC = V<C>;
using VVC = VV<C>;
using VS = V<S>;
using VVS = VV<S>;
using VB = V<B>;
using VVB = VV<B>;
#define REP(type, i, n) for (type i = 0; i < (type)(n); ++i)
#define REP2(type, i, m, n) for (type i = (m); i < (type)(n); ++i)
#define REPR(type, i, n) for (type i = (n)-1; i >= 0; --i)
#define REPR2(type, i, m, n) for (type i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a, type) sort(ALL(a), greater<type>())
#define SORTF(a, comp) sort(ALL(a), comp)
#define REVERSE(a) reverse(ALL(a))
#define SIZE(a, type) ((type)(a).size())
#define bit_search(bit, n) REP(LL, bit, 1LL<<(n))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) (lower_bound(ALL(a), (x)) - a.begin())
#define bisect_right(a, x) (upper_bound(ALL(a), (x)) - a.begin())
#define INPUT(a) REPx(&x, a) cin >> x;
#define INPUT2(a) REPx(&x, a) INPUT(x);
#define INPUTP(a) REPx(&x, a) cin >> x.first >> x.second;
#define ENDL cout << endl;

const int INF = 2e9;
// const LL INF = 9e18;
const LL MOD = 1e9+7;

template<class T> using PRIORITY_QUEUE = priority_queue< T, V<T>, greater<T> >;
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;}
template<class T> inline void debug1(V<T> A){REP(int, i, SIZE(A, int)){if (A[i] == INF) cout << "I ";else cout << A[i] << " ";}ENDL}
template<class T> inline void debug2(VV<T> A){REP(int, i, SIZE(A, int)){REP(int, j, SIZE(A[i], int)){if (A[i][j] == INF) cout << "I "; else cout << A[i][j] << " ";}ENDL}}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, ans = 0;
  cin >> n;
  VI a(n);
  INPUT(a);
  VB check(n, false);
  REP(int, i, n)
  {
    if (check[i]) continue;
    check[i] = true;
    if (i+1 == a[a[i]-1])
    {
      ++ans;
      check[a[i]-1] = true;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3704
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,b;
    cin>>a>>b;
    if(b==1){
       cout<<0<<endl;
    }
    else{
      n=a-b;
      int p=n+1;
      p=p-1;
      cout<<p<<endl;
    }
}


Measured memory_bytes: 256
n, m = map(int, input().split())
groups = [x for x in range(n)]
count = [0]*n

def UnionFind(x):
    a = x
    while a != groups[a]:
        a = groups[a]
    groups[x] = a
    return a

for _ in range(m):
    x, y = map(int, input().split())
    x, y = UnionFind(x-1), UnionFind(y-1)
    if x != y:
        groups[y] = x
    
for i in range(n):
    count[UnionFind(i)] += 1
print(max(count))

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

int N;
int A[200001], nozoki[200001];
vector<int> E[200001];
int kotae[200001];
deque<int> dq;

void dfs(int p, int mae) {

	auto itr = lower_bound(dq.begin(), dq.end(), A[p]);

	if (itr != dq.end()) {
		nozoki[p] = *itr;
		*itr = A[p];
	}
	else {
		dq.pb(A[p]);
	}

	kotae[p] = dq.size();

	for (auto to : E[p]) {
		if (to != mae) {
			dfs(to, p);
		}
	}

	if (!nozoki[p]) {
		dq.pop_back();
	}
	else {
		itr = upper_bound(dq.begin(), dq.end(), nozoki[p]);

		*(--itr) = nozoki[p];
	}

}

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

	cin >> N;
	rep1(i, N) cin >> A[i];
	rep(i, N - 1) {
		int u, v;
		cin >> u >> v;
		E[u].pb(v);
		E[v].pb(u);
	}

	dq.pb(2000000000);
	dfs(1, -1);

	rep1(i, N) co(kotae[i]);

	Would you please return 0;
}

Measured memory_bytes: 36888
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define li long
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pli pair<li,li>
#define pll pair<ll,ll>
#define pb push_back
#define fori(i,k,n) for(int i = k;i<n; i++)
#define rfori(i,k,n) for(int i = k; i>=n; i--)
#define tc int t;cin>>t;while(t--)
#define all(v) v.begin(),v.end()
void fastio()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
} 
class dsu{
    public:
    unordered_map<int,int> p,sz;
    void make_set(int x)
    {
        p[x] = x;
        sz[x]+=1;
    }
    int find(int x)
    {
        if(x == p[x])return x;
        return p[x] = find(p[x]);
    }
    void merge(int a,int b)
    {
        a = find(a);
        b = find(b);
        if(a == b)return;
        if(sz[a]<sz[b])swap(a,b);
        p[b] = a;
        sz[a]+=sz[b];
        sz.erase(b);
    }
};
template<class T>
T power(T a,T b){
    T res = (T)1;
    while(b>0){
        if(b&1)res = (res*a);
        b>>=1;
        a*=a;
    }
    return res;
}
class wemen{
public:
    int b,i,r;
    wemen(){

    }
    bool operator<(const wemen& o){
        if(b!=o.b)return b>o.b;
        else if(i!=o.i)return i>o.i;
        else return r>=o.r;
    }
};
void online_judge(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

int kmp(string s){
    vector<int> lps(s.size(),0);
    for(int i = 1; i<lps.size(); ++i){
        int prev_index = lps[i-1];
        while(prev_index>0&&s[i]!=s[prev_index]){
            prev_index = lps[prev_index-1];
        }
        lps[i] = prev_index+(s[i] == s[prev_index]?1:0);
    }
    return lps[lps.size()-1];
}
int ask1(int node){
    cout<<1<<' '<<node<<endl;
    int ans;
    cin>>ans;
    return ans;
}
int ask2(int node,int y){
    cout<<2<<' '<<node<<' '<<y<<endl;
    int ans;
    cin>>ans;
    return ans;

}
int main()
{
    fastio();
   string s;
   cin>>s;
   if(s[2] == s[3]&&s[4] == s[5])cout<<"Yes";
   else cout<<"No";
}

Measured memory_bytes: 256
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    s = input()
    print(eval(s))


if __name__ == '__main__':
    main()


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

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

class Key {
    public:
        int cost;
        vector<int> boxes;

        int conv_boxes_to_bit() const {
            int res = 0;
            for (int i = 0; i < (int) boxes.size(); i++) {
                res |= 1 << boxes[i];
            }
            return res;
        }
};

const int DP_SIZE = (1 << 12) + 5;
const int INF = 100005;

int dp[DP_SIZE];

int solve(int bits, const int N, const int M, const vector<Key> &keys) {
    if (dp[bits] >= 0) {
        return dp[bits];
    }

    int min_cost = INF;
    for (int i = 0; i < M; i++) {
        int key_cost = keys[i].cost;
        int key_bits = keys[i].conv_boxes_to_bit();
        if ((bits & (~key_bits)) != bits) {
            int new_bits = bits & (~key_bits);
            chmin(min_cost, solve(new_bits, N, M, keys) + key_cost);
        }
    }
    dp[bits] = min_cost;

    return dp[bits];
}

int main(void) {
    int N, M;
    cin >> N >> M;

    vector<Key> keys(M);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        keys[i].cost = a;
        for (int j = 0; j < b; j++) {
            int c;
            cin >> c;
            c--;
            keys[i].boxes.push_back(c);
        }
    }

    for (int i = 0; i < DP_SIZE; i++) {
        dp[i] = -1;
    }
    dp[0] = 0;

    int ans = solve((1 << N) - 1, N, M, keys);
    if (ans == INF) {
        cout << "-1" << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}


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

int main() {
    int n;
    cin >> n;
    int x = n / 1.08;
    int nn = x * 1.08;
    if (n == nn) cout << x << endl;
    else {
        x++;
        nn = x * 1.08;
        if (n == nn) cout << x << endl;
        else cout << ":(" << endl;
    }
}


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

fn main() {
    let mut stdin = io::stdin();
    let mut lines = String::new();
    let _ = stdin.read_to_string(&mut lines);
    let vec = lines.lines().collect::<Vec<&str>>();
    let n :usize = vec[0].trim().parse().unwrap();
    let mut a :Vec<usize> = Vec::new();
    for i in 0..n {
        a.push(vec[i+1].trim().parse().unwrap());
    }
    let a = a;
    
    let mut amari = false;
    let mut cnt = 0;
    for j in &a {
        let jj;
        if amari && *j >= 1 {
            cnt += 1;
            jj = *j - 1;
        } else {
            jj = *j;
        }
        cnt += jj / 2;
        amari = (jj % 2 != 0);
    }

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



Measured memory_bytes: 5560
#include <bits/stdc++.h>
#define ll long long
#define foru(i,a,n) for(int i=(a); i<=(n); i++)
using namespace std;
const int N = 555;
ll n, a[N], ans = 0;
int main()
{
    cin >>n;
    foru(i,1,n) cin >>a[i];
    while(1){
        int cnt = 0;
        foru(i,1,n) cnt += ((a[i]%2)==0);
        ans = ans + (cnt==n);
        if(cnt<n) break;
        foru(i,1,n) a[i] = a[i] / 2;
    }
    cout <<ans;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		int A = sc.nextInt();
		int B = sc.nextInt();

		int C = 6-(A+B);

		System.out.println(C);

	}

}


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

    int main() {
    int N,Y;
    cin >> N >> Y;
    int EN10000=-1,EN5000=-1,EN1000=-1; //一応EN5000にしておく

    bool flag = false; //2重ループを抜けるかどうかを示すインジケーター
    for(int i=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            int s = Y - i*10000 - j*5000;
            int sn = N - i - j;
            if ( s == sn*1000 && sn >= 0 ) {
                EN10000 = i;
                EN5000 = j;
                EN1000 = sn;
                flag = true;//組が見つかった瞬間2重ループを一気に抜ける
                break;
                }
            }
            if(flag) break;
        }
    cout << EN10000 << " " << EN5000 << " " << EN1000 << endl;
    return 0;
    }

Measured memory_bytes: 384
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;
const ll INF=100000000000000LL;

int main() {
	char x,y;
	cin>>x>>y;
	if(x>y)cout<<">"<<endl;
	if(x<y)cout<<"<"<<endl;
	if(x==y)cout<<"="<<endl;
	return 0;
}


Measured memory_bytes: 256
import std.stdio;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;
 
void main() {
    int N; scanf("%d\n", &N);
    foreach (i; 0 .. N) {
        int[] a = new int[3];
        foreach (j; 0 .. 3) scanf("%d", &a[j]);
        sort(a);
        writeln(a[0] * a[0] + a[1] * a[1] == a[2] * a[2] ? "YES" : "NO");
    }
}

Measured memory_bytes: 1060
//Tran Thuy Duong
#include <bits/stdc++.h>
#define maxn 400005
#define maxc 1000000009
#define MOD 1000000007
#define reset(x) memset(x, 0, sizeof x)
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;

int n, h[maxn];

int main()
{
    //freopen("inp.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    cin >> n;
    for (int i=1; i<=n; i++)
        cin >> h[i];
    h[0] = -1;
    bool ok = 1;
    for (int i=1; i<=n; i++)
    {
        if (h[i] >= h[i-1]) continue;
        h[i]++;
        if (h[i] >= h[i-1]) continue;
        ok = 0;
    }
    if (ok) cout << "Yes";
    else cout << "No";
	return 0;
}


Measured memory_bytes: 640
function Main(input) {
  input = input.trim();
  var N = parseInt(input, 10);
  var maxN = 0;
  var n = 10;
  var A = 0;
  var B = 0;
  while (true) {
    n_1 = Math.pow(n, 5);
    n_2 = Math.pow(n - 1, 5);
    if (n_1 - n_2 > Math.pow(10, 9)) {
      maxN = n + 1;
      break;
    }
    n++;
  }

  for (var i = -maxN; i < maxN; i++) {
    for (var j = -maxN; j < maxN; j++) {
      var a = Math.pow(i, 5);
      var b = Math.pow(j, 5);
      if (a - b === N) {
        A = i;
        B = j;
        console.log(A, B);
        return;
      }
    }
  }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

int main(){
	string s; cin>>s;
	ll ans=0;
	for(int i=0; i<(1<<(s.size()-1)); i++){
		string now=""; now+=s[0];
		for(int j=0; j<s.size()-1; j++){
			if(i &(1<<j)) now+="+";
			now+=s[j+1];
		}
		ll sum=0;
		int pos=0;
		while(now.find("+",pos)!=string::npos){
			int npos=now.find("+",pos);
			sum+=stoll(now.substr(pos,npos-pos));
			pos=npos+1;
		}
		sum+=stoll(now.substr(pos));
		ans+=sum;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3612
//BISMILLAHHIR RAHMANIR RAHIM
#include<bits/stdc++.h>
using namespace std;
typedef long long int            ll;
typedef unsigned long long int   ull;
#define min3(a,b,c)              min(a,min(b,c))
#define F                        first
#define S                        second
#define PB                       push_back
#define MP                       make_pair
#define PI                       2*acos(0.0)
#define MOD                      998244353
int main()
{
   int t, a=0,b=0,c=0,d=0;
   cin>>t;
   while(t--){
    string s;
    cin>>s;
    if(s=="AC")a++;
    else if(s=="WA")b++;
    else if(s=="TLE")c++;
    else d++;
   }
   cout<<"AC "<<"x "<<a<<endl;
   cout<<"WA "<<"x "<<b<<endl;
   cout<<"TLE "<<"x "<<c<<endl;
   cout<<"RE "<<"x "<<d<<endl;

}


Measured memory_bytes: 3644
loop do
  m, f, r = gets.split(" ").map(&:to_i)
    exit if m == -1 and f == -1 and r == -1

  if (m == -1 or f == -1) or (m + f < 30)
    puts "F"
  elsif 80 <= m + f
    puts "A"
  elsif 65 <= m + f and m + f < 80
    puts "B"
  elsif 50 <= m + f and m + f < 65
    puts "C"
  elsif 30 <= m + f and m + f < 50
    puts 50 <= r ? "C" : "D"
  else
    exit 1
  end
end

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

class UnionFind
{
public:
    vector<long long> root;

    UnionFind(long long N)
    {
        root = vector<long long>(N + 1, -1);
    }

    long long find_root(long long A)
    {
        if (root[A] < 0)
        {
            return A;
        }
        else
        {
            root[A] = find_root(root[A]);
        }
        return root[A];
    }

    long long size(long long A)
    {
        return -root[find_root(A)];
    }

    bool unite(long long A, long long B)
    {
        A = find_root(A);
        B = find_root(B);
        if (A == B)
        {
            return false;
        }

        if (size(A) < size(B))
        {
            swap(A, B);
        }

        root[A] += root[B];
        root[B] = A;

        return true;
    }

    bool has_same_root(long long A, long long B)
    {
        return find_root(A) == find_root(B);
    }
};

int main()
{
    int N, M;
    cin >> N >> M;

    UnionFind uf(N);

    int X, Y, Z;
    for (int i = 0; i < M; i++)
    {
        cin >> X >> Y >> Z;
        uf.unite(X, Y);
    }

    int ans = 0;
    for (int i = 1; i <= N; i++)
    {
        if (uf.find_root(i) == i)
        {
            ans++;
        }
    }
    cout << ans << endl;
}


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

long long int N, ans;
long long int A[100000];
long long int mina = 0;

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        scanf("%d", A + i);
    }
    for(int i = 0; i < N; i++){
        long long int a = (A[i] - 1) / (mina + 1);
        ans += a;
        A[i] -= a * (mina + 1);
        if(a > 0){
            A[i] = 1;
        }
        if(A[i] - 1 < mina + 1){
            mina = max(mina, A[i]);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1152
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		boolean[][] a = new boolean[n][m];
		long[][] dp = new long[n][m];
		for(int i=0;i<n;i++) {
			char[] x = in.next().toCharArray();
			for(int j=0;j<m;j++) {
				if(x[j]=='.') {
					a[i][j]=true;
				}else {
					a[i][j]=false;
				}
			}
		}
		dp[0][0] = 1;
		for(int i=1;i<n;i++) {
			if(a[i][0])dp[i][0] = dp[i-1][0]; 
		}
		for(int i=1;i<m;i++) {
			if(a[0][i])dp[0][i] = dp[0][i-1];
		}
		for(int i=1;i<n;i++) {
			for(int j=1;j<m;j++) {
				if(a[i][j]) {
					dp[i][j] = (dp[i-1][j]+dp[i][j-1])%1000000007;
				}
			}
		}
		System.out.println(dp[n-1][m-1]);
	}
}


Measured memory_bytes: 51300
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))


K = int(input())
def main():
    k = 7
    count = 1
    re = 1
    if K % 2==0:
        print(-1)
        return
    while True:
        if k % K == 0:
            print(count)
            return
        re =  (re*10)%K
        k = (k+7*re)%K
        count += 1
        if count >= 10**7:
            print(-1)
            return


main()


Measured memory_bytes: 69200
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;
using vi  = vector<int>;
#define _GLIBCXX_DEBUG
#define IO_STREAM cin.tie(0);ios::sync_with_stdio(false)
#define all(x) x.begin(),x.end()
#define rep(i,sta,end) for(int i=sta;i<end;++i)
#define lcm(a,b) (a)/__gcd((a),(b))*(b)
#define pb push_back
const ll INF = 1000000000000000;
const ll MOD = 1000000007;
const double PI = acos(-1);
//||
#define DBG(a,b,c,d) //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl
//DBG("","","","");

signed main(){
	IO_STREAM;
	int N;
	cin>>N;
	vl a(N);
	rep(i,0,N){
		cin>>a[i];
	}
	ll S=a[0];
	rep(i,1,N){
		S^=a[i];
	}
	rep(i,0,N){
		cout<<(S^a[i])<<endl;
	}
	return 0;
}


Measured memory_bytes: 4744
main=do
 getLine
 s<-lines<$>getContents
 putStr"AC x "
 print$length[1|t<-s,t=="AC"]
 putStr"WA x "
 print$length[1|t<-s,t=="WA"]
 putStr"TLE x "
 print$length[1|t<-s,t=="TLE"]
 putStr"RE x "
 print$length[1|t<-s,t=="RE"]

Measured memory_bytes: 23012
/*
  テヲツィツ凖ヲツコツ姪・ツ?・テ・ツ?コテ・ツ環崚」ツつ津ィツ。ツ古」ツ??」ツδ療」ツδュテ」ツつーテ」ツδゥテ」ツδ?」ツつ津、ツスツ愿ヲツ按静」ツ?療」ツ?ヲテ、ツクツ凝」ツ?陛」ツ??)
 */

import java.util.*;
public class Main{
    public static void main(String[] args){
	new Main().run();
    }
    Scanner sc = new Scanner(System.in);
    int n;

    void run(){
	while(sc.hasNext()){
	    n = sc.nextInt();
	    if(n!=0)
		solve();
	}
    }

    void solve(){
	for(int i=0; i<9; i++){
	    n -= sc.nextInt();
	}
	System.out.println(n);
    }
}

Measured memory_bytes: 17260
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <algorithm>   
static int N; 
static int stones[100004];
static int rem[100004];

using namespace std;




int solotion(int i) {
	if (i >= N -1) {
		return 0;
	}
	if (rem[i] != -1) {
		return rem[i];
	}
	int first = abs(stones[i] - stones[i + 1])+solotion(i + 1);
	int second = i + 2 < N ? abs(stones[i] - stones[i + 2]) + solotion(i + 2) : first + 1;
	rem[i] = min(first, second);
	return rem[i];
}

int main() {
	cin >> N;
	
	for (int i = 0; i < N; i++) {
		cin >> stones[i];
		rem[i] = -1;
	}

	printf("%d", solotion(0));
}



Measured memory_bytes: 4096
N = int(input())
A = list(map(int,input().split()))
maxa = max(A)
minx = min(A)
lista = [0]*(max(A)+1)
for i in range(len(A)):
  #print(A[i])
  for j in range(0,maxa+1,A[i]):
    lista[j] += 1
    #print(j)
count = 0
for i in range(len(A)):
  if lista[A[i]] == 1:
    count += 1
print(count)

Measured memory_bytes: 32188
// package app;

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

    public static void main(final String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);

        // final String N = sc.next();

        final int r = sc.nextInt();
        final int g = sc.nextInt();
        final int b = sc.nextInt();
        // final int N = sc.nextInt();
        // final int D = sc.nextInt();
        // System.out.println();
        System.out.println(( r * 100 + g * 10 + b ) % 4 == 0 ? "YES" : "NO");

        // System.out.println(A <= X && A + B >= X ? "YES" : "NO");

    }
}

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

using namespace std;

const int M = 16;
const int MSK = 1 << 16;
const int mod = 1000000007;
const int inv9 = 111111112;

void add(int &x,int y) {
	x += y;
	if (x >= mod) {
		x -= mod;
	}
}

int mul(int x,int y) {
	return (long long) x * y % mod;
}

int power(int x,int y) {
	int ans = 1;
	while (y) {
		if (y & 1) {
			ans = mul(ans, x);
		}
		x = mul(x, x);
		y >>= 1;
	}
	return ans;
}

int val[M];
int f[MSK], nf[MSK], coef[MSK];
vector<pair<int, int>> go[M];

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	vector<pair<int, int>> all;
	
	all.push_back(make_pair(0, 0));
	
	for (int i = 1; i <= m; ++i) {
		int l, r;
		scanf("%d %d", &l, &r);
		--l;
		all.push_back(make_pair(l, i));
		all.push_back(make_pair(r, i));
	}
	++m;
	
	sort(all.begin(), all.end());
	
	int ans = 1;
	
	for (int i = 1; i < (int) all.size(); ++i) {
    	int u = all[i - 1].second, v = all[i].second;
    	if (all[i - 1].first == all[i].first) {
      	val[u] |= 1 << v;
      	val[v] |= 1 << u;
    	} else {
      	int nw = mul(inv9, power(10, all[i].first - all[i - 1].first) - 1);
      	ans = mul(ans, nw);
      	nw = mul(nw + 1, power(nw, mod - 2));
      	go[u].push_back(make_pair(v, nw));
    	}
  	}
  	ans = mul(ans, power(10, n - all.back().first));
	
	for (int msk = 0; msk < (1 << m); ++msk) {
    	coef[msk] = 1;
    	for (int i = 0; i < m; ++i) {
      	if (msk & (1 << i)) {
        		if ((val[i] & msk) != val[i]) {
          		coef[msk] = 0;
          		break;
        		}
        		for (auto p : go[i]) {
          		if (msk & (1 << p.first)) {
            		coef[msk] = mul(coef[msk], p.second);
          		}	
        		}
      	}
    	}
  	}
	
	f[0] = 1;
	for (int x = 0; x < 9; ++x) {
		for (int msk = 0; msk < (1 << m); ++msk) {
			int revmsk = msk ^ ((1 << m) - 1);
			for (int submsk = revmsk; ; submsk = (submsk - 1) & revmsk) {
				if (x || (submsk & 1)) {
					add(nf[msk | submsk], mul(f[msk], coef[submsk]));
				}
				if (!submsk) {
					break;
				}
			}
		}
		
		for (int msk = 0; msk < (1 << m); ++msk) {
			f[msk] = nf[msk];
			nf[msk] = 0;
		}
	}
	
	printf("%d\n", mul(ans, f[(1 << m) - 1]));
}


Measured memory_bytes: 1152
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

main=do
    [n,x]<-map read.words<$>getLine
    as <- unfoldr (B.readInt.B.dropWhile(==' '))<$>B.getLine::IO[Int]
    print $ f x 0 as

f x i [a,b] = max 0 (i+(a+b)-x)
f x i (a:b:as)
    | a+b <= x = f x i (b:as)
    | a > x    = f x (i+a-x+b) (0:as)
    | True     = f x (i+a+b-x) ((x-a):as)


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

long long int a[100000+1][3]; //a[k][l]

long long int dp[100000+1][3];

long long int q(int k, int l) {
    int x, y;
    if (dp[k][l] != -1) return dp[k][l];

    if (l == 0) x = 1, y = 2;
    else if (l == 1) x = 0 , y = 2;
    else x = 0, y = 1; 
    
    if (k == 0) {
        dp[k][l] = a[k][l];
    }
    else {
        dp[k][l] = max(q(k-1, x) + a[k][l], q(k-1, y) + a[k][l]);
    }

    return dp[k][l];
}

int main() {
    int i, k, N;

    cin >> N;
    for (k=0; k<N; k++) {
        for (i=0; i<3; i++) {
            cin >> a[k][i];
            dp[k][i] = -1;
        }
    }

    cout << max(max(q(N-1, 2), q(N-1, 1)), q(N-1, 0)) << endl;
}

Measured memory_bytes: 9600
#include<iostream>
#include <algorithm>

using namespace std;

int main()
{
  int N;
  int mochi[100];

  for(int i=0;i < 100;i++)mochi[i] = -1;

  cin >> N;

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

  sort(mochi,mochi+N);

  int count = 1;
  for(int i=1;i < N;i++){
    if(mochi[i-1] != mochi[i])count++;
  }

  cout << count << endl;
}

Measured memory_bytes: 256
N=int(input())
s=[list(input()) for _ in range(N)]
b=0
cnt=0
for i in range(N):
    s[i].sort()
s.sort()
for i in range(N-1):
    if s[i]==s[i+1]:
        b=b+1
    if not(s[i]==s[i+1])and(s[i]!=0):
        cnt=cnt+(b*(b+1))//2
        b=0
    #print(b)
cnt=cnt+(b*(b+1))//2
print(cnt)


Measured memory_bytes: 98392
// abc056_d
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N, K;
    cin >> N >> K;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    sort(ALL(A));

    auto check = [&](int x){

        vector<bool> dp(K);

        dp[0] = true;
        REP(i, N){
            if (i == x) continue;
            REP_REV(j, K-A[i]){
                dp[j + A[i]] = dp[j + A[i]] | dp[j];
            }
//            print(x, A[x], i, A[i], dp);

        }

        bool noneed = true;
        REPN(j, 1, A[x]+1){
            if (dp[K - j]){
                noneed = false;
                break;
            }
        }
        return noneed;
    };

    int inf = -1;
    int sup = N;
    while (sup - inf > 1){
        int x = (sup + inf) / 2;
        if (check(x)){
            inf = x;
        } else {
            sup = x;
        }
    }

    print(inf+1);


    return 0;
}


Measured memory_bytes: 256
N = int(input())
Hs = list(map(int, input().split()))
res = [0] * N

for index, h in enumerate(Hs):
    l = 0
    if index > 0:
        l = max(res[index - 1] - 3, 0)

    tmp = h
    while index + l + 1 < N and tmp >= Hs[index + l + 1]:
        tmp = Hs[index + l + 1]
        l += 1
    res[index] = l

print(max(res))

Measured memory_bytes: 14252
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
using namespace std;
typedef long long ll;

int main()
{
  int N;
  int p[210000];
  int m[210000];
  int res=0;
  cin >> N;

  rep(i,N) {
    cin >> p[i];
  }

  m[0]=p[0];
  FOR(i,1,N-1){
    m[i] = min(m[i-1], p[i]);
  }
  //rep(i,N) cout << m[i] <<":" << p[i] << endl;                                         
  rep(i,N){
    if(m[i]>=p[i]) res++;
  }

  cout << res << endl;
}

Measured memory_bytes: 1792
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			list.add(in.nextInt());
		}
		int minv = list.get(0);
		int maxv = list.get(1) - list.get(0);
		for (int i = 1; i < n; i++) {
			maxv = max(maxv,minv,list.get(i));
			minv = min(minv,list.get(i));
		}
		System.out.println(maxv);
	}
	static int max(int maxv, int minv, int r){
		if(maxv > (r -minv) ){
			return maxv;
		}else{
			return r -minv;
		}
	}
	static int min(int minv, int r){
		if(minv > r){
			return r;
		}else{
			return minv;
		}
	}
}

Measured memory_bytes: 105116
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repo(i,N) for(int i = 1; i < (N); i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//#define int long long

int main() {
  int a;
  cin >>a;
  
  string ans="Christmas";
  
  rep(i,25-a) {
  ans += " Eve";
  }
  
  cout << ans << endl;
  
}


Measured memory_bytes: 256
import itertools

def f(bin, x):
    if bin == 0:
        return x
    else:
        return -x

def g(x):
    r = str(n[-1])
    for i in range(ketasu - 1):
        if x[i] == 0:
            r += "+"
        else:
            r += "-"
        r += str(n[-i - 2])
    r+="=7"
    return r

abcd = input()
ketasu = len(abcd)
abcd = int(abcd)
n = [None] * ketasu
for i in range(ketasu):
    n[i] = abcd % 10
    abcd //= 10

for i in itertools.product([0, 1], repeat=ketasu - 1):
    ans = n[-1]
    for j in range(ketasu-1):
        ans += f(i[j], n[-j-2])
    if ans == 7:
        ans = g(i)
        break
print(ans)

Measured memory_bytes: 3064