akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <map>

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

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

  std::map<int, int> m;
  int i = 1;
  m[s] = 1;
  while (true)
  {
    if (m[s] > 1)
    {
      cout << i << endl;
      return 0;
    }
    if (s % 2 == 0)
    {
      s /= 2;
    }
    else
    {
      s = 3 * s + 1;
    }
    m[s]++;
    i++;
  }

  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,V,U = LI()
V -= 1
U -= 1

edges = [[] for _ in range(n)]

for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

if n == 2:
    print(0)
else:
    depth_v = [None]*n
    depth_v[V] = 0
    que = deque()
    que.append(V)
    while que:
        v = que.popleft()
        for u in edges[v]:
            if depth_v[u] == None:
                depth_v[u] = depth_v[v]+1
                que.append(u)
    
    depth_u = [None]*n
    depth_u[U] = 0
    que = deque()
    que.append(U)
    while que:
        u = que.popleft()
        for v in edges[u]:
            if depth_u[v] == None:
                depth_u[v] = depth_u[u] + 1
                que.append(v)
    
    ans = 0
    for v in range(n):
        if depth_v[v] < depth_u[v]:
            ans = max(ans,depth_u[v]-1)
    print(ans)

Measured memory_bytes: 65312
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  string s, t;
  cin >> s >> t;
  sort(s.begin(), s.end());
  sort(t.rbegin(), t.rend());
  if (s < t) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
using namespace std;

#define ABS(a) (((a) >= 0) ? (a) : -(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define RFOR(i, a, b) for (int i = a; i > b; --i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define int long long

typedef long long ll;
typedef pair<int, int> Pair;

const int kMaxH = 1000;
const int kMaxW = 1000;
const int kInf = 1000000000;

int H, W, N;
string maze[kMaxH];
int ans = 0;

int d[kMaxH][kMaxW];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

int Bfs(char s, char g) {
  int sx, sy, gx, gy;
  REP(i, H) {
    REP(j, W) {
      if (maze[i][j] == s) { sx = i; sy = j; }
      if (maze[i][j] == g) { gx = i; gy = j; }
    }
  }

  queue<Pair> que;
  REP(i, H) { REP(j, W) { d[i][j] = kInf; } }
  que.push(Pair(sx, sy));
  d[sx][sy] = 0;

  while (que.size()) {
    Pair p = que.front(); que.pop();
    int x = p.first; int y = p.second;
    if (x == gx && y == gy) { break; }
    REP(i, 4) {
      int nx = x+dx[i]; int ny = y+dy[i];
      if (0 <= nx && nx < H && 0 <= ny && ny < W) {
        if (maze[nx][ny] != 'X' && d[nx][ny] == kInf) {
          que.push(Pair(nx, ny));
          d[nx][ny] = d[x][y]+1;
        }
      }
    }
  }

  return d[gx][gy];
}

signed main() {
  cin >> H >> W >> N;
  REP(i, H) { cin >> maze[i]; }

  ans += Bfs('S', '1');
  REP(i, N-1) { ans += Bfs('1'+i, '2'+i); }

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



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

int m,n;
int w[222222];
int t[222222];
int c[222222];
int b[222222];

int dp[1<<16];

vector<int>A,B;

main(){

  A.push_back(0);
  B.push_back(0);

  
  cin>>m>>n;
  r(i,m) cin>>w[i]>>t[i] , A.push_back(w[i]) , B.push_back(t[i]);
  r(i,n) cin>>c[i]>>b[i];

  r(i,m){
    A[i+1] += A[i];
    B[i+1] += B[i];
  }

  A.push_back(4e18);
  B.push_back(4e18);

  dp[0]=0;

  for(int i=0;i<(1<<n);i++){
    for(int j=0;j<n;j++){
      if(i&(1<<j))continue;
      
      int ai = upper_bound(A.begin(),A.end(),A[dp[i]]+c[j]) - A.begin(); ai--;
      int bi = upper_bound(B.begin(),B.end(),B[dp[i]]+b[j]) - B.begin(); bi--;
      int x = min( ai , bi );
      //cout<<x<<endl;
      dp[i|(1<<j)] = max(dp[i|(1<<j)],x);
    }
  }

  cout<< dp[(1<<n)-1] <<endl;
  
}



Measured memory_bytes: 9736
#include<cstdio>
#include<cmath>
using namespace std;

int gcd(int x,int y){
  if(y==0)
    return x;
  else
    return gcd(y,x%y);
}

int main(){
  int n,p,x[100000],ans;
  scanf("%d %d",&n,&p);
  for(int i=0;i<n;i++){
    scanf("%d",&x[i]);
    x[i]-=p;
  }
  ans=abs(x[0]);
  for(int i=0;i<n;i++)
    ans=gcd(ans,abs(x[i]));
  printf("%d\n",ans);
}

Measured memory_bytes: 512
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
#define rint register int
using namespace std;
const int maxn=2e5+5;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int n,k;
int a[maxn];
int sum[maxn];
int ans;
int c[maxn];
inline void msort(int l,int r)
{
	if(l==r)
	return ;
	int mid=(l+r)>>1;
	msort(l,mid);
	msort(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j])
		{
			ans+=r-j+1;
			c[k++]=a[i++];
		}
		else
		c[k++]=a[j++];
	}
	while(i<=mid)
	c[k++]=a[i++];
	while(j<=r)
	c[k++]=a[j++];
	for(int i=l;i<=r;i++)
	a[i]=c[i];
}
signed main()
{
	n=read()+1;
	k=read();
	for(rint i=2;i<=n;i++)
	{
		a[i]=read();
		sum[i]=sum[i-1]+a[i];
		a[i]=sum[i]-k*(i-1);
	}
	msort(1,n);
	cout<<ans;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
#define re return
#define all(a) a.begin(),a.end()
#define int long long
using namespace std;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
vector<int>prime(1e6+10,1);
signed main()
{
	int n;
	cin>>n;
	int ans=0;
	for (int i=2;i<1e6+5;i++){
		if (prime[i]){
			for (int j=i*i;j<1e6+5;j+=i)  prime[j]=0;
			int t=0;
			while (n%i==0){
				t++;
				n/=i;
			}
			int k=0;
			for (int j=1;t>=j;j++){
				t-=j;
				k=j;
			}
			ans+=k;
		}
	}
	if (n!=1)  ans++;
	cout<<ans;
	re 0;
}

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

#define long long long

long sol(long);

int main(){
	long a=0;
	cin>>a;
	cout<<sol(a)<<endl;
	return 0;
}

long pow10(long a){
	if(a<0)return 0;
	long r=1,c=10;
	while(a>0){
		if(a&1)r*=c;
		c*=c;
		a>>=1;
	}
	return r;
}

long will[50];

long dfs(long d,long pos,long n,long ned){
	if(abs(d-ned)>pow10(n-pos+1)-pow10((n+1)/2)-pow10(n/2)+pow10(pos-1))return 0;
	if(pos>(n+1)/2)return ned==d;
	long ans=0;
	for(will[pos]=-9;will[pos]<=9;will[pos]++){
		if(pos==1&&will[pos]==9)continue;
		if(pos==n/2+1&&will[pos]!=0)continue;
		if(will[pos]>=0)ans+=(9-will[pos]+(pos!=1))*dfs(d+(pow10(n-pos)-pow10(pos-1))*will[pos],pos+1,n,ned);
		else ans+=(10+will[pos])*dfs(d+(pow10(n-pos)-pow10(pos-1))*will[pos],pos+1,n,ned);
	}
	will[pos]=0;
	return ans;
}

long sol(long d){
	if(d%9)return 0;
	long ans=0;
	for(long i=2;pow10((i+1)/2)-pow10((i-1)/2)<=d;i++)
		ans+=dfs(0,1,i,d);
	return ans; 
}

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

using namespace std;

int main()
{
  int N, M, A[100];

  cin >> N >> M;
  for(int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  for(int i = 1; i <= M; i++) {
    for(int j = 0; j < N - 1; j++) {
      if(A[j] % i > A[j + 1] % i) {
        swap(A[j], A[j + 1]);
      }
    }
  }
  for(int i = 0; i < N; i++) {
    cout << A[i] << endl;
  }
}

Measured memory_bytes: 1160
#include <stdio.h>

int main()
{
	int a=0,b=0,c=0;
	
	scanf("%d %d %d",&a,&b,&c);

	if( a < b && b < c ){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}

	return 0;
}

Measured memory_bytes: 1008
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;ch=getchar();
    }
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}

inline bool read(int& a){
    int s=0,w=1;
    char ch=getchar();
    if(ch==EOF){
		return false;
	}
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;ch=getchar();
    }
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    a=s*w;
    return true;
}

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

inline void writeln(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    puts("");
}

int a[200010];
int n;
int ans;

signed main(){
    read(n);
    
    for(int i=1;i<=n;i++)
        read(a[i]);
        
    for(int i=2;i<=n;i++){
        if(a[i-1]>a[i]){
            ans+=a[i-1]-a[i];
            a[i]=a[i-1];
        }
    }
    
    writeln(ans);
    return 0;
}

Measured memory_bytes: 5180
n=int(input())
a=list(map(int,input().split()))
m=max(a)
b=[0]
b*=m
for i in range(n):
    b[a[i]-1]+=1
c=[]
for i in range(m):
    if b[i]>=2:
        c.append(int(b[i]*(b[i]-1)/2))
    else:
        c.append(0)
d=sum(c)
for i in range(n):
    if c[a[i]-1]>=1:
        e=c[a[i]-1]-int((b[a[i]-1]-1)*(b[a[i]-1]-2)/2)
        print(d-e)
    else:
        print(d)



Measured memory_bytes: 32340
#include <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(s) int(s.size())
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

int main(){FIN;
	ll a; string s; cin>>a>>s;
	ll b=0; for(auto x:s) if(x!='.') b=10*b+x-'0';
	ll ans=a*b; ans/=100;
	cout<<ans<<"\n";
}

Measured memory_bytes: 3668
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int n,q,a,b,c,i,x[100010];
string s;
int main(){
  for(cin>>n>>q>>s,i=1;i<n;++i){
    x[i+1]=x[i];
    if(s[i-1]=='A'&&s[i]=='C')x[i+1]++;
  }
  for(i=0;i<q;++i){
    cin>>a>>b;
    cout<<x[b]-x[a]<<endl;
  }
}

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

int main()
{
    int n;
    cin>>n;
    int v[n],c[n];
    
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
    }
    
    for(int i=0;i<n;i++)
    {
        cin>>c[i];
    }
    
    int sum=0;
    
    for(int i=0;i<n;i++)
    {
        if(v[i]>c[i])
        {
            sum+=v[i]-c[i];
        }
    }
    
    cout<<sum<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define int long long
#define endl "\n"
#define pii pair<int,int> 
#define ff first
#define ss second
#define mii map<int,int>
#define si set<int>
#define sti stack<int>
#define qi queue<int>
#define vi vector<int>
#define pq priority_queue<int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int M=998244353;
vector<pair<int,int>> v[20];
pair<int,int> p;

bool check(vector<int> V,int n){
	int a[n];
	for(int i=0;i<n;i++) a[i]=0;
	for(int i=0;i<V.size();i++){
		a[V[i]]=1;
	}
	for(int i=0;i<V.size();i++){
		int x=V[i];
		for(int j=0;j<v[x].size();j++){
			p=v[x][j];
			if(p.ss==1&&a[p.ff-1]==0) return false;
			else if(p.ss==0&&a[p.ff-1]==1) return false;
		}
	}
	return true;
}

int32_t main(){
	IOS;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int a;
		cin>>a;
		for(int j=0;j<a;j++){
			int x,y;
			cin>>x>>y;
			p.ff=x;
			p.ss=y;
			v[i].pb(p);
		}
	}
	int ans=0;
	for(int i=0; i < ( ( 1 << n ) ) ; i++){
		vector<int> V;
		for(int j=0;j<n;j++){
			int x= ( ( 1 << j ) ) ;
			if( ( ( ( i ) & ( x ) ) > 0 ) ){
				V.pb(j);
			}
		}
		if(check(V,n)){
			ans=max(ans,(int)V.size());
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define x first
#define y second
#define sz(a) ((int)(a.size()))
#define OTIMIZA 2
#define INSERE 1
#define REMOVE 0
#define move aslzxc
int main()
{
	int a , b, c;
	cin >> a >> b >> c;
	swap(a , b);
	swap(a, c);
	cout << a << " " << b << " " << c;
}


Measured memory_bytes: 256
#include<iostream>
#include<climits>
#include<algorithm>
using namespace std;
#define ll long long

ll T(ll h, ll w)
{
    ll s = LLONG_MAX;
    for(ll i = 1; i < h; i++){
        if(w % 2 == 0){
            s = min(s, max(w*i, w/2*(h-i)) - min(w*i, w/2*(h-i)));
        }
        else{
            s = min(s, max(w*i, (w+1)/2*(h-i)) - min(w*i, w/2*(h-i)));
        }
    }
    return s;
}

int main()
{
    ll h, w;
    cin >> h >> w; // h, w
    if(h % 3 == 0 || w % 3 == 0){
        cout << 0 << endl;
    }
    else{
        cout << min({h, w, T(h, w), T(w, h)}) << endl;
    }
    return 0;
}

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


int main() {
  int n; string s,t; cin >> n >> s >> t;
  string sum;
  
  for(int i=0; i < 2*n; i++){
    if(i%2 ==0){
      sum += s.at(i/2);
    }
    else{
      sum += t.at(i/2);
    }
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10;

int x, y, a, b, c;
int p[nax], q[nax], r[nax];

int main () {
    scanf("%d %d %d %d %d", &x, &y, &a, &b, &c);

    for (int i = 1 ; i <= a ; ++ i) {
        scanf("%d", p + i);
    }

    for (int i = 1 ; i <= b; ++ i)
        scanf("%d", q + i);

    for (int i = 1 ; i <= c ; ++ i)
        scanf("%d", r + i);

    sort(p + 1, p + 1 + a);
    sort(q + 1, q + 1 + b);
    sort(r + 1, r + 1 + c);

    reverse(p + 1, p + 1 + a);
    reverse(q + 1, q + 1 + b);
    reverse(r + 1, r + 1 + c);

    long long ans = 0;
    priority_queue<int, vector<int>, greater<int> > m, n;

    for (int i = 1 ; i <= x ; ++ i) {
        ans += p[i];
        m.push(p[i]);
    }


    for (int i = 1 ; i <= y ; ++ i) {
        ans += q[i];
        n.push(q[i]);
    }

    for (int i = 1 ; i <= c ; ++ i) {

        int good1 = -1, good2 = -1;
        if (!n.empty() && r[i] > n.top()) {
            good1 =  r[i] - n.top();
        }
        if (!m.empty() && r[i] > m.top()) {
            good2 = r[i] - m.top();
        }

        if (good1 > good2) {
            ans += good1;
            n.pop();
        } else if (good2 > good1) {
            ans += good2;
            m.pop();
        } else if (good1 == good2 && good1 != -1) {
            ans += good1;
            n.pop();
        }
    }

    printf("%lld\n", ans);
}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 2552
#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
/*----------------------------------------------------------------*/

// int MOD = 998244353;
int MOD = 1000000007;

/*----------------------------------------------------------------*/
signed main(){

    int n,k;
    cin >> n >> k;
    vll h(n);
    rep(i,n)cin >> h[i];

    int ans = 0;
    SORT(h);
    for(int i = n-1;i >= 0;i--){
        if(k > 0){
            k--;
        }else{
            ans += h[i];
        }
    }
    cout << ans << endl;
    
	return 0;
}
/*----------------------------------------------------------------*/

// g++ -std=c++14 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2018-quala.contest.atcoder.jp/tasks/code_festival_2018_quala_c
// rm -r -f test;oj dl https://ddcc2020-qual.contest.atcoder.jp/tasks/ddcc2020_qual_b
// rm -r -f test;oj dl https://abc153.contest.atcoder.jp/tasks/abc153_b

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int d[1000];
    for(int i=0; i<n; i++){
        cin >> d[i];
    }
    int sum = 0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            sum += (d[i]*d[j]);
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;


int main(){
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll nr = 0;
    ll ng = 0;
    ll nb = 0;
    
    rep(i, n) {
        if (s[i]=='R') nr++;
        if (s[i]=='G') ng++;
        if (s[i]=='B') nb++;
    }

    ll ans;
    ans = nr*ng*nb;

    rep(i, n) {
        char c = s[i];
        int j = 1;
        while (i-j>=0 && i+j<n) {
            char c1 = s[i-j];
            char c2 = s[i+j];
            if (c!=c1 && c!=c2 && c1!=c2) ans--;
            j++;
        }
    }
    
    
    
    cout << ans << endl;
    return 0;
}


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

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

  std::vector<int> v;
  v.push_back(a);
  v.push_back(b);
  v.push_back(c);
  std::sort(v.begin(), v.end());

  std::cout << v.at(0) << " " << v.at(1) << " " << v.at(2) << std::endl;
  
  return 0;
}


Measured memory_bytes: 3060
N,M = map(int,input().split())
bit = [0]*M
for i in range(N):
    info = list(map(int,input().split()))[1:]
    for e in info:
        bit[e-1] += 1
cnt = 0
for b in bit:
    if b == N:
        cnt +=1
print(cnt)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define rep(i,m) for(long long i=0; i<m; i++)
#define per(i,m) for(long long i=m-1; i>=0; i--)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define ROF(i,n,m) for(long long i=n-1; i>=m; i--)
#define all(x) (x).begin(),(x).end()
#define EPS (1e-7)
#define INF (1e18)
#define PI (acos(-1))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
typedef pair<ll, ll> LP;

ll POW(ll x,ll n){
  if(n==0)return 1;
  if(n%2==0)return POW(x*x%MOD,n/2);
  return x*POW(x,n-1)%MOD;
}

ll gcd(ll u, ll v) {
  ll r;
  while (0 != v) {
    r = u % v; u = v; v = r;
  }
  return u;
}
 
ll KAI(ll m)
{
  if(m<0) return 0;
  if(m==0) return 1;
  return m*KAI(m-1)%MOD;
}
 
ll extGCD(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extGCD(b, a%b, y, x);
    y -= a / b * x;
    return d;
}
 
inline ll mod(ll a, ll m) {
    return (a % m + m) % m;
}
 
ll modinv(ll a) {
    ll x, y;
    extGCD(a, MOD, x, y);
    return mod(x, MOD);
}
 
ll COM(ll m,ll n)
{
  if(m<n) return 0;
  if(n<0) return 0;
  if(n==0) return 1;
  if(m==n) return 1;
  return KAI(m)%MOD*modinv(KAI(n)%MOD*KAI(m-n)%MOD)%MOD;
}

ll DEC(ll x,ll m,ll n)
{
  return x%POW(m,n+1)/POW(m,n);
}

ll keta(ll x,ll n)
{
  if(x==0)return 0;
  return keta(x/n,n)+1;
}

ll DIV(ll x,ll n)
{
  if(x==0)return 0;
  return x/n+DIV(x/n,n);
}


int main()
{
  ll n,l[12],a;
  a=0;
  cin >> n;
  rep(i,n)cin >> l[i];
  sort(l,l+n);
  rep(i,n-1)a+=l[i];
  if(a<=l[n-1])printf("No");
  else printf("Yes");
}

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

using namespace std;

vector<set<int>> gs(200001);
int main()
{
    int n; cin >> n;

    unordered_map<int, int64_t> vals;
    vector<int> as(n);
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        vals[a]++;
        as[i] = a;
    }

    int64_t ans = 0;
    for (auto it : vals) {
        ans += it.second * (it.second - 1) / 2;
    }

    for (int i = 0; i < n; i++) {
        int64_t cn = vals.find(as[i])->second;
        if (cn <= 1) {
            cout << ans << endl;
        }
        else {
            cout << ans - (cn - 1) << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 17736
n,k = gets.chomp.split.map(&:to_i)

array = Array.new(n,0)
k.times do
	d = gets.to_i
	as = gets.chomp.split.map(&:to_i)
	as.each do |a|
		array[a-1] += 1
	end
end

puts array.count(0)

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

int main(){
	int n;
	cin >> n;
	vector<tuple<string,int,int>> cnt;
	rep(i,n){
		string s;
		int p;
		cin >> s >> p;
		p = -p;
		cnt.push_back(tie(s,p,i));
	}
	sort(cnt.begin(),cnt.end());
	rep(i,n){
		cout << get<2>(cnt[i])+1 << endl;
	}
}

// cout << fixed << setprecision(15) <<  << endl;

Measured memory_bytes: 3604
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define rush() int T;scanf("%d",&T);while(T--)
#define mm(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define pf(a) printf("%d\n",a)
#define pf2(a,b) printf("%d %d\n",a,b)
#define p_f(a) printf("%d ",a)
#define fi first
#define se second
#define db double
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const db eps=1e-9;

int main()
{
    string s,t;
	cin>>s>>t;
	cout<<t<<s<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
} P;

P Q[LEN];
int head,tail,n;

void enqueue(P x){
  Q[tail]=x;
  tail=(tail+1)%LEN;
}

P dequeue(){
  P x=Q[head];
  head = (head+1)%LEN;
  return x;
}

int min(int a,int b){return a<b?a:b;}

int main(){
  int elaps=0,c;
  int i,q;
  P u;
  scanf("%d %d",&n,&q);
  for(i=1;i<=n;i++){
    scanf("%s",Q[i].name);
    scanf("%d",&Q[i].t);
  }
  head=1;
  tail=n+1;

  while(head != tail){
    u=dequeue();
    c=min(q,u.t);
    u.t -= c;
    elaps += c;
    if(u.t>0) enqueue(u);
    else{
      printf("%s %d\n",u.name,elaps);
    }
  }

  return 0;
}



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


int main(){
    int n,k;
    cin>>n>>k;
    int h[n],i,dp[n];
    for(i=0;i<n;i++){
        cin>>h[i];
    }
    int s=0;
    fill_n(dp,n,INT_MAX);
    dp[0]=0;
    for(i=1;i<n;i++){
        for(int j=max(0,i-k);j<i;j++){
            dp[i]=min(dp[j]+abs(h[i]-h[j]),dp[i]);
        }
    }
    cout<<dp[n-1]<<endl;
    return 0;
}

Measured memory_bytes: 1024
n,m = map(int,input().split())
a = list(map(int,input().split()))

d1 = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
d2 = {2:[1],3:[7],4:[4],5:[5,3,2],6:[9,6],7:[8]}

# dp[i]:i本のマッチを使用した場合の最大桁数
dp = [-float('inf') for _ in range(n+1)]
dp[0] = 0
for i in range(1,n+1):
  for ai in a:
    if i-d1[ai] >= 0:
      dp[i] = max(dp[i-d1[ai]]+1,dp[i])

a.sort(reverse = True)
ans = ''
r = n
k = dp[n]
while(r > 0):
  for ai in a:
    if r-d1[ai] >= 0 and dp[r-d1[ai]] == k-1:
      ans += str(ai)
      r -= d1[ai]
      k -= 1
      break

print(ans)


Measured memory_bytes: 42732
#include<bits/stdc++.h>
#define INF 2147483647
#define maxn 200010
using namespace std;
int a[maxn];
int get_mx(int l, int r)
{
	int len = r - l + 1, res = 0;
	for (int i = 1; i <= len / 2; i++)
		res = max(res, a[l + i - 1] + a[r - i + 1]);
	return res;
}
int get_mn(int l, int r)
{
	int len = r - l + 1, res = INF;
	for (int i = 1; i <= len / 2; i++)	
		res = min(res, a[l + i - 1] + a[r - i + 1]);
	return res;
}
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= 2 * n; i++)
		scanf("%d", &a[i]);
	sort(a + 1, a + 2 * n + 1);
	int lef = 0, righ = n, ch;
	while (lef <= righ)
	{
		int mid = (lef + righ) / 2, tmp = get_mn(2 * mid + 1, 2 * n);
		if (tmp >= m) {ch = mid; righ = mid - 1;}
		else lef = mid + 1;
	}
	int t1 = get_mx(1, 2 * ch), t2 = get_mx(2 * ch + 1, 2 * n);
	printf("%d\n", max(t1 % m, t2 % m));
	return 0;
}

Measured memory_bytes: 1024
n = int(input())
ans = [0]*n

for i in range(1,101):
  for j in range(1,101):
    for k in range(1,101):
      l = i**2 + j**2 + k**2 + i*j + j*k + k*i
      if l <= n:
        ans[l-1] += 1
      
for m in range(n): 
  print(ans[m])

Measured memory_bytes: 9176
master_set = set()
for mk in [1, 2, 3, 4]:
    for i in range(1, 14):
        master_set.add((mk, i))

idx = int(input())
distribute_set = set()
bufstr = []
soot_dict = {'S': 1, 'H': 2, 'C': 3, 'D': 4}
rev_soot_dict = {1: 'S', 2: 'H', 3: 'C', 4: 'D'}
for i in range(idx):
    bufstr = input().split()
    distribute_set = distribute_set | \
                     {(soot_dict[bufstr[0]], int(bufstr[1]))}

master_set = master_set - distribute_set

out_set = sorted(list(master_set), key=lambda x: (x[0], x[1]))

for out in out_set:
    print("{} {}".format(rev_soot_dict[out[0]],
                         out[1]
                         ))

Measured memory_bytes: 7664
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include<string>
using namespace std;

struct team_data {
    int id;
    int p;
    int solved;
};

int main(){
    int T,R,P;
    while(cin>>T>>P>>R,T){
        int data[51][11]={},data1[51][11]={},ts[51]={};
        for(int i=0;i<R;i++){
            int t,p,time;
            string massage;
            cin>>t>>p>>time>>massage;
            if(massage=="CORRECT"){
                data[t][p]=time;
                data[t][p]+=data1[t][p]*1200;
                data1[t][p]=-1;
                ts[t]++;
            }else{
                data1[t][p]++;
            }
        }
        for(int i=1;i<=T;i++){
            for(int j=1;j<=P;j++){
                data[i][0]+=data[i][j];
            }
        }
        
        vector<team_data> v(T);
        for(int i=0; i<T; ++i) {
            v[i].id = i+1;
            v[i].p=data[i+1][0];
            v[i].solved=ts[i+1];
        }
        
        stable_sort(v.begin(), v.end(), [](team_data const& t1, team_data const& t2) {
            return t1.p < t2.p;
        });
        stable_sort(v.begin(), v.end(), [](team_data const& t1, team_data const& t2) {
            return t1.solved > t2.solved;
        });
        
        for(auto x : v) {
            cout << x.id << " " << x.solved << " " << x.p << endl;
        }
    }
}
            

Measured memory_bytes: 3180
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define show(x) cout<<#x<<"="<<x<<"\n"
using namespace std;

int h,w;
int c[10][10];
int a[210][210];
ll dp[10][10];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
   cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin); 
    freopen("out","w",stdout);
#endif
  cin>>h>>w;
  for(int i=0;i<10;i++){
   for(int j=0;j<10;j++){
    cin>>c[i][j];
    dp[i][j]=c[i][j];
   }
  }
  for(int k=0;k<10;k++){
   for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
     dp[i][j]=min(dp[i][k]+dp[k][j],dp[i][j]);
    }
   }
  }
  ll ans=0;
  for(int i=0;i<h;i++){
   for(int j=0;j<w;j++){
    cin>>a[i][j];
    if(a[i][j]==-1)continue;
    ans+=dp[a[i][j]][1];
   }
  }
  cout<<ans<<endl;
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int W,H,x,y,r;
    cin >> W >> H >> x >> y >>r;
    
        if(x-r >= 0 && x+r <= W && y-r >= 0 && y+r <= H){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}



Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
int main()
{
  int n;
  cin>>n;
  double sum=0;
  while(n--)
  {
    ld x;
    string s;
    cin>>x>>s;
    if(s=="JPY") sum+=x;
    else sum+=(x*380000.0);
  }
  //cout<<(ld)sum;
  printf("%.5lf",sum);
  return 0;
}

Measured memory_bytes: 256
mod = 998244353
n,k = map(int,input().split())
K = [list(map(int,input().split())) for i in range(k)]

dp = [0]*(n+1)
dp[0] = 1
dp2 = [0]*(n+1)
for i in range(n):
    dp2[i] = (dp2[i]+dp2[i-1])%mod
    dp[i] = (dp[i]+dp2[i])%mod
    for l,r in K:
        dp2[min(i+l,n)] = (dp2[min(i+l,n)]+dp[i])%mod
        dp2[min(i+r+1,n)] = (dp2[min(i+r+1,n)]-dp[i])%mod
print(dp[n-1]%mod)


Measured memory_bytes: 82716
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<ll, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<ldouble, ldouble> pdd;

int n;
vector <pii> E[100010];
int A[100010];
int B[16];
int ans;

void dfs(int x, int fa) {
	for(pii e : E[x]) if(e.Se != fa) {
		dfs(e.Se, x);
		A[e.Se] ^= e.Fi;
		A[x] ^= e.Fi;
	}
}

int D[1<<16];
int X[1<<16];

void solve() {
	scanf("%d", &n);
	rep(i, n-1) {
		int x, y, z; scanf("%d%d%d", &x, &y, &z); ++x; ++ y;
		E[x].pb(pii(z, y));
		E[y].pb(pii(z, x));
	}
	dfs(1, -1);
	for(int i=2;i<=n;i++) B[A[i]]++;
	B[0] = 0;
	rep(i, 16) ans += B[i] / 2, B[i] &= 1;
	vector <int> v;
	int L = 0;
	rep(i, 16) {
		if(B[i]) v.pb(i), L |= 1<<i;
	}
	rep(b, 1<<16) {
		rep(i, 16) if(1<<i & b) X[b] ^= i;
	}
	rep(b, 1<<16) {
		for(int i=b;i;i=(i-1)&b) {
			if(X[i] == 0) {
				D[b] = max(D[b], D[b^i] + 1);
			}
		}
	}
	
	printf("%d\n", ans + szz(v) - D[L]);
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}




Measured memory_bytes: 14080
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;

const int inf = 99999;
int tbl[40][400][400];
int n, ma, mb;

int as[40], bs[40], cs[40];

int solve(int cur, int ca, int cb) {
  if (cur == n) {
    if (ca != 0 && cb != 0 && ca * mb == ma * cb)
      return 0;
    return inf;
  }

  int &ret = tbl[cur][ca][cb];
  if (ret >= 0) {
    return ret;
  }

  ret = solve(cur + 1, ca, cb);
  ret = min(ret, solve(cur + 1, ca + as[cur], cb + bs[cur]) + cs[cur]);
  ret = min(ret, inf);

  return ret;
}

int main() {
  cin >> n >> ma >> mb;

  for (int i = 0; i < n; i++) {
    cin >> as[i] >> bs[i] >> cs[i];
  }

  memset(tbl, -1, sizeof(tbl));
  auto ans = solve(0, 0, 0);

  if (ans >= inf) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 25344
#include<stdio.h>
#include<string>
#include<utility>
#include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<bitset>

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

char s[25][25]={};

int search(int sx,int sy,int gx,int gy, int h, int w){
    int dx[4] = {1,0,-1,0};
    int dy[4] ={0,-1,0,1};
    if(s[sy][sx]=='#' || s[gy][gx]=='#')return -1;
    std::queue<pair<int, int>> st;
    int visited[25][25]={};
    st.push(make_pair(sy,sx));
    visited[sy][sx]=1;
    while(!st.empty()){
        pair<int,int> p = st.front();
        st.pop();
        if(gy==p.first && gx==p.second){
            
            return visited[gy][gx]-1;
        }
        REP(i,4){
            int ny = p.first+dy[i];
            int nx = p.second+dx[i];
            if(!(ny>=0 && ny<h))continue;
            if(!(nx>=0 && nx<w))continue;
            if(visited[ny][nx]>0)continue;
            if(s[ny][nx]=='.'){
                st.push(make_pair(ny, nx));
                visited[ny][nx]= visited[p.first][p.second]+1;
            }
        }
    }
}

int main(){
    int h,w;
    scanf("%d%d",&h,&w);
    char row[25]={};
    REP(i,h){
        scanf("%s",row);
        REP(j,w)s[i][j]=row[j];
    }
    int max = -1;
    REP(sx,w)REP(sy,h)REP(gx,w)REP(gy,h){
        int score = search(sx,sy,gx,gy,h,w);
        if(max<score)max=score;
    }
    printf("%d\n",max);
    //printf("%d\n", search(0,0,2,2,3,3));
    return 0;
}

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

int main() {
    char c;
    cin >> c;

    if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
        cout << "vowel" << endl;
    else
        cout << "consonant" << endl;

}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define MaxN 100000+1000
typedef long long LL;
LL my_m=0;
LL q_y[MaxN];
LL q_z[MaxN];
LL x[MaxN];
LL v[MaxN];
LL my_max(LL a,LL b)
{
    return a>b ? a:b;
}
int main()
{
    int N;
    LL C;
    scanf("%d %lld",&N,&C);
    for(int i=0;i<N;i++)
        scanf("%lld %lld",&x[i],&v[i]);
    LL sum=0;
    LL my_ma=0;
    for(int i=0;i<N;i++)
    {
        if(i==0)
            sum+=(v[i]-x[i]);
        else
            sum+=(v[i]-(x[i]-x[i-1]));
        my_ma=my_max(my_ma,sum);
        q_y[i]=my_ma;
        my_m=my_max(my_m, my_ma);
//        printf("%lld\n",sum);
    }
 //   printf("\n");
    sum=0;
    my_ma=0;
    for(int i=N-1;i>=0;i--)
    {
        if(i==N-1)
            sum+=(v[i]-(C-x[i]));
        else
            sum+=(v[i]-(x[i+1]-x[i]));
        my_ma=my_max(my_ma, sum);
        q_z[i]=my_ma;
        my_m=my_max(my_m, my_ma);
 //       printf("%lld\n",sum);
    }
    sum=0;
    for(int i=0;i<N-1;i++)
    {
        if(i==0)
            sum+=(v[i]-2*x[i]);
        else
            sum+=(v[i]-2*(x[i]-x[i-1]));
        my_m=my_max(my_m, sum+q_z[i+1]);
    }
    sum=0;
    for(int i=N-1;i>0;i--)
    {
        if(i==N-1)
            sum+=(v[i]-2*(C-x[i]));
        else
            sum+=(v[i]-2*(x[i+1]-x[i]));
        my_m=my_max(my_m, sum+q_y[i-1]);
    }
    printf("%lld\n",my_m);
    return 0;
}


Measured memory_bytes: 3328
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s; cin >> s;
	reverse(all(s));
	s = s.substr(8);
	reverse(all(s));
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;

void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    bool flag = true;
    rep(i,n-1){
        if(a[i]!=a[i+1]) flag = false;
    }
    if(flag){
        cout << a[0];
        return 0;
    }
    int g = a[0];
    rep(i,n){
        g = __gcd(g,a[i]);
    }
    cout << g << endl;

    return 0;
}

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

typedef long long ll;

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n = 0, m = 0;
    cin >> n >> m;

    ll sum = 0;
    ll temp =0;
    for(int i = 0; i < m; i++) {
        cin >> temp;
        sum += temp;
    }

    if(n - sum < 0) cout << -1 << endl;
    else cout << n - sum << endl;

    


    return 0;
}

Measured memory_bytes: 3656
#include <cstdio>
#include <string.h>
using namespace std;

char w[16], t[1024];

bool lower(char* a) {
	int p = 0;
	while (a[p] != '\0') {
		if (a[p] >= 'A' &&a[p] <= 'Z') {
			a[p] -= ('A' - 'a');
		}
		p++;
	}
	return true;
}

int main(){
	int c = 0;
	scanf("%s", w);
	lower(w);
	while (scanf("%s", t), strcmp(t, "END_OF_TEXT") != 0) {
		lower(t);
		if (strcmp(w, t) == 0) {
			c++;
		}
	}
	printf("%d\n", c);
	
	return 0;
}

Measured memory_bytes: 2724
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <iostream>
#include <cmath>
#include <map>
#include <cstdlib>
using namespace std;
#define ABS(x) ((x)>=0?(x):(-x))
const int maxn = 100100;
long long cnt[maxn];
const long long mod = 998244353;
int n;
long long pow(long long a, long long t)
{
	if (a == 0)
		return 0;
	long long ret = 1;
	while (t)
	{
		if (t & 1)
			ret = ret * a%mod;
		a = a * a%mod;
		t /= 2;
	}
	return ret%mod;
}
void solve()
{
	if (cnt[0] != 1)
	{
		puts("0");
		return;
	}
	long long ans = 1;
	for (int i = 2; i <= n; i++)
	{
		ans = ans * pow(cnt[i - 1], cnt[i])%mod;
	}
	cout << ans << endl;


}
int main()
{
	
	//cout << pow(3, 4) << endl;
	scanf("%d", &n);
	int ok = 1;
	for (int i = 1; i <= n; i++)
	{
		int tmp;
		
		scanf("%d", &tmp);
		if (i == 1 && tmp != 0)
			ok = 0;
		cnt[tmp]++;
	}
	if (ok == 0)
	{
		puts("0");
		return 0;
	}

	int lstpos=n;
	for (int i = 1; i <= n; i++)
		if (cnt[i])
			lstpos = i;
	n = lstpos;

	solve();
	
}
//1000000000000

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

int main(void){
    int n;
    cin >> n;
    int beg,fin,none;
    cin >>beg;
    fin=beg;
    for(int i=0;i<n-1;i++){
        cin >> none;
        if(fin<none) fin=none;
        if(beg>none) beg=none;
    }
    cout << (fin-beg+1)/2 << endl;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
#define eprintf(...) fprintf(stderr,__VA_ARGS__)

const int N=int(1e5)+5;

int n;

inline int bitlen(const int x){
	int k=0;
	for(;x>>k;k++);
	return k;
}

struct node;
struct edge{
	node *ed;
	edge *next;
} E[N<<1],*newE=E;
struct node{
	edge *son;
	node *pa;
	int f;
	void dfs(){
		int pre=0,tmp=0;
		for(edge *e=son;e;e=e->next) if(e->ed!=pa){
			e->ed->pa=this;
			e->ed->dfs();
			tmp|=e->ed->f&pre;
			pre|=e->ed->f;
		}
		int k=bitlen(tmp);
		f=((pre>>k)+1)<<k;
	}
} V[N];

int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y; scanf("%d%d",&x,&y);
		*newE=(edge){V+y,V[x].son},V[x].son=newE++;
		*newE=(edge){V+x,V[y].son},V[y].son=newE++;
	}
	V[1].dfs();
	printf("%d\n",bitlen(V[1].f)-1);
}

Measured memory_bytes: 7552
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

bool search(int s[], int n, int t)
{
    for (std::size_t i = 0; i < n; ++i) {
        if (s[i] == t) {
            return true;
        }
    }

    return false;
}

int main()
{
    int n, q;
    std::cin >> n;
    int s[n];
    for (std::size_t i = 0; i < n; ++i) {
        std::cin >> s[i];
    }

    std::cin >> q;
    int t, cnt = 0;;
    for (std::size_t i = 0; i < q; ++i) {
        std::cin >> t;
        if (search(s, n, t)) {
            ++cnt;
        }
    }

    std::cout << cnt << std::endl;

    return 0;
}


Measured memory_bytes: 3128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
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; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<ll> a(n+1);
  rep(i, n+1) cin >> a[i];
  if (!n && a[0] == 1) {
    cout << 1 << endl;
    return 0;
  }
  if (a[0]) {
    cout << -1 << endl;
    return 0;
  }
  ll ans = 1, idx = 0;
  vector<ll> imos(n+1);
  imos[0] = 2;
  imos[1] = -2;
  rep(i, n) {
    if (i)
      imos[i] += imos[i-1];
    ll rem = imos[i];
    while (rem) {
      if (idx > n)
        break;
      if (!a[idx]) {
        idx++;
        continue;
      }
      ll num = min(a[idx], rem);
      imos[i+1] += num;
      imos[idx] -= num;
      ans += (idx-i)*num;
      a[idx] -= num;
      rem -= num;
    }
  }
  rep(i, n+1) {
    if (a[i]) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4780
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
	int t=1,sum=0;char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') t=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		sum=sum*10+ch-'0',ch=getchar();
	return t*sum;
}
const int Max=6e5,mod=924844033;
int fir[Max],siz[Max],f[Max],g[Max],fac[Max],inv[Max],n,cnt;
int eps[Max],inv_eps[Max],N;
struct edge
{
	int to,nxt;
	edge () {}
	edge (int x,int y)
	{
		to=y; nxt=fir[x];
		fir[x]=cnt;
	}
}e[Max<<1];
void add(int x,int y)
{
	e[++cnt]=edge(x,y);
	e[++cnt]=edge(y,x);
}
int pul(int x,int y)
{
	x+=y;
	if(x>=mod) x-=mod;
	return x;
}
int dec(int x,int y)
{
	x-=y;
	if(x<0) x+=mod;
	return x;
}
void up(int &x,int y)
{
	x+=y;
	if(x>=mod) x-=mod;
}
void dn(int &x,int y)
{
	x-=y;
	if(x<0) x+=mod;
}
int fpm(int x,int y)
{
	int ans=1;
	for(;y;y>>=1,x=1LL*x*x%mod)
		if(y&1)
			ans=1LL*ans*x%mod;
	return ans;
}
void get_ready()
{
	int W=fpm(5,(mod-1)/N),IW=fpm(W,mod-2),i;
	eps[0]=inv_eps[0]=1;
	for(i=1;i<N;i++)
		eps[i]=1LL*eps[i-1]*W%mod,
		inv_eps[i]=1LL*inv_eps[i-1]*IW%mod;
}
void dft(int *x,int n,int *Eps)
{
	int i,j,k,u,t,wn,w;
	for(i=j=0;i<n;i++)
	{
		if(i<j) swap(x[i],x[j]);
		for(k=n>>1;(j^=k)<k;k>>=1);
	}
	for(i=1;i<n;i<<=1)
	{
		wn=(N/i)>>1;
		for(j=0;j<n;j+=i<<1)
			for(k=w=0;k<i;k++,w+=wn)
			{
				u=x[j+k]; t=1LL*Eps[w]*x[j+k+i]%mod;
				x[j+k]=pul(u,t);
				x[j+k+i]=dec(u,t);
			}
	}
}
void idft(int *x,int n,int *Eps)
{
	dft(x,n,Eps);
	int Inv=fpm(n,mod-2),i;
	for(i=0;i<n;i++)
		x[i]=1LL*x[i]*Inv%mod;
}
void dfs(int x,int p)
{
	int i,v; siz[x]=1;
	for(i=fir[x];i;i=e[i].nxt)
		if(e[i].to!=p)
		{
			v=e[i].to;
			dfs(v,x);
			g[siz[v]]++;
			siz[x]+=siz[v];
		}
	g[n-siz[x]]++;
}
int C(int x,int y)
{
	if(x<y) return 0;
	return 1LL*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
	int i,x,y;
	n=read();
	fac[0]=inv[0]=inv[1]=1;
	for(i=2;i<=n;i++)
		inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
	for(i=1;i<=n;i++)
		fac[i]=1LL*fac[i-1]*i%mod,
		inv[i]=1LL*inv[i-1]*inv[i]%mod;
	for(i=1;i<n;i++)
	{
		x=read(); y=read();
		add(x,y);
	}
	dfs(1,0);
	for(i=0;i<=n;i++)
		f[i]=inv[i];
	for(i=1;i<=n;i++)
		g[i]=1LL*g[i]*fac[i]%mod;
	for(i=0;i<n-i;i++)
		swap(g[i],g[n-i]);
	for(N=1;N<=(n+n);N<<=1);
	get_ready();
	dft(f,N,eps); dft(g,N,eps);
	for(i=0;i<N;i++) f[i]=1LL*f[i]*g[i]%mod;
	idft(f,N,inv_eps);
	for(i=1;i<=n;i++)
		printf("%d\n",dec(1LL*n*C(n,i)%mod,1LL*f[n-i]*inv[i]%mod));
}


Measured memory_bytes: 32512
#include <iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n,c=0;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        
        
    }
    
    for(int i=0;i<n-2;i++)
    {int b[3];
    b[0]=a[i];
    b[1]=a[i+1];
    b[2]=a[i+2];
    int h=b[1];
    sort(b,b+3);
    if(b[1]==h)c++;
     
    
    }
    cout<<c<<endl;
}


Measured memory_bytes: 256
'use strict';

const main = input => {
  const arr = input.split('\n');
  const n = Number(arr[0].split(' ')[0]);
  const q = Number(arr[0].split(' ')[1]);
  arr.shift();

  initialize();
  for (let i = 0; i < n; ++i) {
    enqueue({
      name: arr[i].split(' ')[0],
      t: Number(arr[i].split(' ')[1]),
    });
  }
  let elaps = 0;
  while (!isEmpty()) {
    const p = dequeue();
    if (p.t > q) {
      p.t -= q;
      enqueue(p);
      elaps += q;
    } else {
      elaps += p.t;
      console.log(p.name, elaps);
    }
  }
};

const MAX = 100000;
let head = 0;
let tail = 0;
let Q = [];

function initialize() {
  head = 0;
  tail = 0;
  Q = [];
}

function isEmpty() {
  return head === tail;
}

function isFull() {
  return head === (tail + 1) % MAX;
}

function enqueue(x) {
  if (isFull()) {
    // Error
    console.log('isFull');
    return;
  }
  Q[tail] = x;
  tail = (tail + 1) % MAX;
}

function dequeue() {
  if (isEmpty()) {
    // Error
    console.log('isEmpty');
    return;
  }
  const x = Q[head];
  head = (head + 1) % MAX;
  return x;
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));



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

int main(){
	int x, n;
	char y;
	bool cards[4][14] ={};
	cin >> n;
	for( int i = 0; i < n; i++ ){ cin >> y >> x;
	if( y == 'S' ){ cards[0][x] = 1; }
	else if( y == 'H' ){ cards[1][x] = 1; }
	else if( y == 'C' ){ cards[2][x] = 1; }
	else if( y == 'D' ){ cards[3][x] = 1; }
	}
	for( int i = 0; i < 4; i++){ for( int j = 1; j < 14; j++){ if( cards[i][j] == 0 ){
	if( i == 0 ) { cout << "S " << j << "\n"; }
	else if( i == 1 ) { cout << "H " << j << "\n"; }
	else if( i == 2 ) { cout << "C " << j << "\n"; }
	else if( i == 3 ) { cout << "D " << j << "\n"; }
	} } }

return 0;
}

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

int main(){
  int N, M;
  cin >> N >> M;
  vector<int> C(N,0);
  for(int i = 0; i < M; ++i){
    int a, b;
    cin >> a >> b;
    --a,--b;
    if(!a) ++C[b];
    if(b == N-1) ++C[a];
  }
  if(*max_element(C.begin(), C.end()) > 1) cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;
  return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

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

                int A = scan.nextInt();
                int B = scan.nextInt();
                int C = scan.nextInt();
                int D = scan.nextInt();

                while (true) {
                	C -= B;
                	if (C <= 0 ) {
                		System.out.println("Yes");
                		break;
                	}
                	A -= D;
                	if (A <= 0 ) {
                		System.out.println("No");
                		break;
                	}
                }

        }

}

Measured memory_bytes: 35620
#include <stdio.h>

inline void gc(int *x) {
    *x = 0;
    for (;;) {
        int c = getchar_unlocked();
        if ('0' <= c && c <= '9') {
            *x = *x * 10 + c - '0';
        } else {
            break;
        }
    }
}

#define KMAX (1000)
int s[KMAX + 1][2 * KMAX + 1];
int main(void) {
    char c;
    int n, k, x, y;
    scanf("%d %d\n", &n, &k);
    for (int i = 0; i < n; i++) {
        gc(&x);
        gc(&y);
        c = getchar_unlocked();
        getchar_unlocked();
        y %= 2 * k;
        if (c == 'W') {
            if (y >= k) {
                y -= k;
            } else {
                x += k;
            }
        } else {
            if (y >= k) {
                y -= k;
                x += k;
            }
        }
        x %= 2 * k;
        s[y + 1][x + 1]++;
    }
    for (int y = 0; y < k; y++) {
        for (int x = 0; x < 2 * k; x++) {
            s[y + 1][x + 1] += s[y][x + 1] + s[y + 1][x] - s[y][x];
        }
    }
    int max = 0;
    int v = s[0][0] - s[0][2 * k];
    for (int y = 0; y < k; y++) {
        int u = v - s[y][0] + s[y][2 * k];
        for (int x = 0; x < k; x++) {
            int t = u - s[0][x] - s[k][x] + s[0][x + k] + s[k][x + k] +
                    2 * s[y][x] - 2 * s[y][x + k];
            t = t < n / 2 ? n - t : t;
            max = t > max ? t : max;
        }
    }
    printf("%d", max);
    return 0;
}


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

int main() {
    int n;
    cin >> n;
    int four = 0;
    int two = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x % 4 == 0) four++;
        else if (x % 2 == 0) two++;
    }
    n -= (two % 2 == 0 ? two : two - 1);
    cout << (n / 2 <= four ? "Yes" : "No") << endl;
}


Measured memory_bytes: 384