akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,a,b) for(int i=(a); i>=(b);i--) 

const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;




int main()
{
   ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
   int a,b; cin >> a >> b;
   rep(i,b - a + 1, b + a - 1) cout << i << " ";
   
   return 0;
}

Measured memory_bytes: 256
# n,k = map(int, input().split())
n = int(input())
h = list(map(int,input().split()))
dp = [0] * n
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2,n):
    dp[i] = min(abs(h[i]-h[i-1])+dp[i-1], abs(h[i]-h[i-2])+dp[i-2])
# dp[2] = min((h[2] - h[1])+dp[1], (h[2]-h[0])+dp[0])
# dp[3] = min((h[3] - h[2])+dp[2], (h[3]-h[1])+dp[1])
print(dp[-1])

Measured memory_bytes: 13928
def examA():
    N, i = LI()
    ans = N - i + 1
    print(ans)
    return

def examB():
    H, W = LI()
    A = [SI() for _ in range(H)]
    h = [[]for _ in range(H)]
    for i in range(W):
        flag = False
        for j in range(H):
            if A[j][i]=="#":
                flag = True
                break
        if flag:
            for j in range(H):
                h[j].append(A[j][i])
    #print(h)
    ans = []
    for i,a in enumerate(h):
        if "#" in a:
            ans.append(i)
    for v in ans:
        print("".join(map(str,h[v])))
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examB()

"""

"""

Measured memory_bytes: 4976
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}

template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}

template<typename T,typename Y>
ostream& operator<<(ostream& os,const pair<T,Y>& p){
   return os<<"{"<<p.fs<<","<<p.sc<<"}";
}
template<typename T> ostream& operator<<(ostream& os,const V<T>& v){
   os<<"{";
  for(auto e:v)os<<e<<",";
  return os<<"}";
}
template<typename ...Args>
void debug(Args&... args){
  for(auto const& x:{args...}){
    cerr<<x<<' ';
  }
  cerr<<ENDL;
}



signed main(){
  cin.tie(0);cerr.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  char c;cin>>c;
  if('A'<=c && c<='Z')cout<<'A'<<ENDL;
  else cout<<'a'<<ENDL;
}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 3612
import sys
#やけくそで書いたのを書きなおした
def 解():
    iN,iM = [int(_) for _ in input().split()]
    def addCity(d,p,m,i):
        if p in d:
            d[p].append((m,i))
        else:
            d[p]=[(m,i)]
    dC = {}
    iIndex = 1
    for p,m in [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]:
        addCity(dC,p,m,iIndex)
        iIndex += 1
    oAns = []
    for iCity in dC.keys():
        iIndex = 1
        for m,i in sorted(dC[iCity]):
            oAns.append((i,'{:06}{:06}'.format(iCity,iIndex)))
            iIndex += 1
    oAns.sort()
    print("\n".join(map(lambda x:x[1] ,oAns)))
解()


Measured memory_bytes: 54284
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;
typedef long long ll;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; i++){
        cin >> h[i];
    }

    sort(h.begin(), h.end());

    int ans = 2e9;
    for (int i = 0; i < n - k + 1; i++){
        int sub = h[i + k - 1] - h[i];
        if (sub < ans) ans = sub;
    }
    cout << ans << endl;
    return 0;
}

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

const int N = 3005;

int dp[N*2], n, A[N], B[N], id[N], T;

int main() {
	scanf("%d %d", &n, &T);
	for (int i = 1; i <= n; i ++) scanf("%d %d", &A[i], &B[i]), id[i] = i;
    memset(dp, -1, sizeof dp);
    dp[0] = 0;
    sort(id+1, id+n+1, [](int x, int y){return A[x] < A[y];});
    for (int j = 1; j <= n; j ++) {
		int o = id[j];
        int a = A[o], b = B[o];
		for (int i = T-1; i >= 0; i --) if (dp[i] >= 0) dp[i+a] = max(dp[i+a], dp[i] + b);
    }
    int ans = *max_element(dp, dp + N*2);
    cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3776
package main

import "fmt"

func main() {
	var x1, y1, x2, y2 int
	fmt.Scan(&x1, &y1, &x2, &y2)

	dx := x2 - x1
	dy := y2 - y1

	x3 := x2 - dy
	y3 := y2 + dx
	x4 := x1 - dy
	y4 := y1 + dx

	fmt.Println(x3, y3, x4, y4)
}


Measured memory_bytes: 1768
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <math.h>

#define MOD 1000000007
#define REP(i,n) for ((i)=0;i<(n);i++)
#define SET(a,c) memset(a,c,sizeof a)
#define CLR(a) memset(a,0,sizeof a)
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
#define LL long long
#define ULL unsigned long long



int main(void) {

	char s[1001];
	int N,E,W,S,i;
	N = 0;
	E = 0;
	W = 0;
	S = 0;

	scanf("%s", &s);

	for(i=0;s[i]!='\0';i++){
		switch(s[i]){
		case 'N':
			N = 1;
			break;
		case 'E':
			E = 1;
			break;
		case 'W':
			W = 1;
			break;
		case 'S':
			S = 1;
			break;
		}
	}

	if(N+S%2==1||E+W%2==1){
		puts("No");
	}else{
		puts("Yes");
	}


	return 0;
}

/* 最後の改行忘れるな！！ */


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int b[4];
struct node{
	int a1,b1;
}a[6];
int main()
{
	int n,m,i;
	cin>>n>>m;
	for(i=1; i<=m; i++)
		cin>>a[i].a1>>a[i].b1;
	for(i=1; i<=m; i++)
	{
		if(b[a[i].a1]!=0)
			for(int j=1; j<i; j++)
				if(a[j].a1==a[i].a1)
				{
					if(a[j].b1!=a[i].b1)
					{
						cout<<"-1";
						return 0;
					}	
				}
		if(a[i].a1==1 && a[i].b1==0 && n!=1)
		{
			cout<<"-1";
			return 0;
		}
		if(a[i].a1>n)
		{
			cout<<"-1";
			return 0;
		}
		b[a[i].a1]=a[i].b1;
	}
	if(b[1]==0 && n!=1)
		b[1]=1;
	for(i=1; i<=n; i++)
		cout<<b[i];
	return 0;
 } 

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

int N;
int A[20];
int x[20][20];
int y[20][20];
 

int counter(int x) {
    if (x == 0) return 0;
    int num = counter(x >> 1) + (x & 1);
    return num;
}
 
void solve() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        for (int j = 1; j <= A[i]; j++) {
            cin >> x[i][j] >> y[i][j];
        }
    }
    int ans = 0;
    // N = 2 case: 00 (no honest person) 01 (1st person is honest) 10 (2nd person is honest) 11 (both are honest)
    for (int bits = 1; bits < (1 << N); bits++) {
        bool ok = true;
        for (int i = 1; i <= N; i++) {
            // If ith person is honest, check all conditions are satisfied
            if (!(bits & (1 << (i-1)))) continue;
            for (int j = 1; j <= A[i]; j++) {
                if (((bits >> (x[i][j]-1)) & 1) ^ y[i][j]) ok = false;  // Contradiction
            }
        }
        if (ok) ans = max(ans, counter(bits));
    }
    cout << ans << endl;
    return;
}
 
int main() {
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)

using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using ull= unsigned long long;
const ll K_MAX=1e5+5;
const ll Lmax=ll(1e18);
const ll INF=1e15+4;
const int Nmax=2e5+1;
const int Nd=61;
ll dfs[3003][3003][4];
ll  v[3003][3003];


int main(){
  ll n,a,b; cin>>n>>a>>b;
  vector<ll> x(n);
  ll hiroA,hiroB=b;
  ll now=0;
  rep(i,n)cin>>x[i];

  rep(i,n-1){//位置iにいる場合を考える
    hiroA=(x[i+1]-x[i])*a;
    if(hiroA>=hiroB){
      now+=hiroB;
    }else{
      now+=hiroA;
    }
  }
  cout<<now<<endl;


}


Measured memory_bytes: 3968
#include <iostream>
using namespace std;
int main (int argc, const char * argv[])
{
    int x,y;
    while(1){
        cin >>x>>y;
        if(x==0&&y==0)break;
        
         else if (x<y){
             cout << x <<" "<<y<<endl;
        }else{
            cout << y <<" "<<x<<endl;
            
        }
    }
    // insert code here...
   // std::cout << "Hello, World!\n";
    return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    int a, ans=0;
    cin >> n;
    for(int i=n; i<=999; i++)
    {
        if(i%111==0)
        {
            a=i;
            break;
        }
    }
    cout << a << '\n';
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
  int month,day,bell;
  string s;
  while(1){
    cin >> month >> day;
    if(month==0 && day==0){
      break;
    }
    if(month==1 || month==4 || month==7){
      bell=4;
    }
    else if(month==2 || month==8){
      bell=7;
    }
    else if(month==3 || month==11){
      bell=1;
    }
    else if(month==5){
      bell=6;
    }
    else if(month==6){
      bell=2;
    }
    else if(month==9 || month==12){
      bell=3;
    }
    else if(month==10){
      bell=5;
    }

    for(int i=1;i<day;i++){
      bell++;
      if(bell>=8){
	bell=1;
      }
    }

    if(bell==1){
      s="Monday";
    }
    else if(bell==2){
      s="Tuesday";
    }
    else if(bell==3){
      s="Wednesday";
    }
    else if(bell==4){
      s="Thursday";
    }
    else if(bell==5){
      s="Friday";
    }
    else if(bell==6){
      s="Saturday";
    }
    else if(bell==7){
      s="Sunday";
    }
    cout << s << endl;
  }
  return (0);
}

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


int main() {
  int N ;
  cin >> N ;
  
 for(int i=0; i<N ; i++){
   if(N==1){
     cout << 1 << endl;
     break;
   }
   else if (N <=3 ){
     cout << 2 << endl;
     break;
   }
   else if (N <= 7){
     cout << 4 << endl;
     break;
   }
   else if (N <= 15){
     cout << 8 << endl;
     break;
   }
   else if (N <=31) {
     cout << 16 << endl;
     break;
   }
   else if (N<= 63){
     cout << 32 << endl;
     break;
   }
   else{
     cout << 64 << endl;
     break;
   }
   
    }
      
      

}

Measured memory_bytes: 256
k = int(input())
s = input()
mod = 10**9+7

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

modp = mod
max_n = k + len(s)+1 # 必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod modp)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod modp)
inv = [0, 1]  # factinv 計算用

for i in range(2, max_n + 1):
    fact.append((fact[-1] * i) % modp)
    inv.append((-inv[modp % i] * (modp // i)) % modp)
    factinv.append((factinv[-1] * inv[-1]) % modp)

ans = 0
for i in range(k+1):
    now = pow(26, k-i, mod)
    now = (now * pow(25, i, mod))%mod
    now = (now * cmb(i+len(s)-1, len(s)-1, mod))%mod
    ans += now
print(ans%mod)

Measured memory_bytes: 227156
//#include <bits/stdc++.h>
//#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>


#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 LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979
#define MAXI 7500000

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;
typedef string::const_iterator State;

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


int main(void) {
	string s;
	int w;

	cin >> s >> w;

	for (int i = 0; i <= s.size() - 1; i += w) {
		cout << s[i];
	}
	cout << endl;

	
	

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
int a[610][610];
int sumx[610][610],sumy[610][610];
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int h,w,ans=0,twice=0;
    cin>>h>>w;
    char s[310][310];
    rep(i,h){
        rep(j,w){
            cin>>s[i][j];
            if(s[i][j]=='#'){
                int x=i+300,y=j;
                a[x+y-300][x-y]=1;
            }
        }
    }
    rep(i,600){
        sumx[i][0]=a[i][0];
        rep(j,599){
            sumx[i][j+1]=sumx[i][j]+a[i][j+1];
        }
    }
    rep(j,600){
        sumy[0][j]=a[0][j];
        rep(i,599){
            sumy[i+1][j]=sumy[i][j]+a[i+1][j];
        }
    }
    rep(x,600){
        rep(y1,600){
            rep(y2,600){
                if(a[x][y1]&&a[x][y2]&&y2>y1){
                    int d=y2-y1;
                    if(x-d>=0){
                        ans+=sumx[x-d][y2]-(y1?sumx[x-d][y1-1]:0);
                        twice+=a[x-d][y2];
                        twice+=a[x-d][y1];
                    }
                    if(x+d<600){
                        ans+=sumx[x+d][y2]-(y1?sumx[x+d][y1-1]:0);
                        twice+=a[x+d][y2];
                        twice+=a[x+d][y1];
                    }
                }
            }
        }
    }
    rep(y,600){
        rep(x1,600){
            rep(x2,600){
                if(a[x1][y]&&a[x2][y]&&x2>x1){
                    int d=x2-x1;
                    if(y-d>=0){
                        ans+=sumy[x2][y-d]-(x1?sumy[x1-1][y-d]:0);
                        twice+=a[x2][y-d];
                        twice+=a[x1][y-d];
                    }
                    if(y+d<600){
                        ans+=sumy[x2][y+d]-(x1?sumy[x1-1][y+d]:0);
                        twice+=a[x2][y+d];
                        twice+=a[x1][y+d];
                    }
                }
            }
        }
    }
    cout<<ans-twice/2<<endl;
    return 0;
}

Measured memory_bytes: 7996
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
static const uint64_t MOD = 1000000007LL;
// uint64_t dp[100005][13];

int main()
{
    int n, m;
    cin >> n >> m;

    map<long, long, greater<long>> mcb;
    priority_queue<long, vector<long>, greater<long>> q;
    for (int i = 0; i < n; i++) {
        long a;
        cin >> a;
        q.push(a);
    }
    for (int i = 0; i < m; i++) {
        long b, c;
        cin >> b >> c;
        mcb[c] += b;
    }

    for (auto e: mcb) {
        long c = e.first;
        long b = e.second;
        for (int i = 0; i < b; i++) {
            if (q.top() < c) {
                q.pop();
                q.push(c);
            } else {
                break;
            }
        }
    }

    long ans = 0;
    while (!q.empty()) {
        ans += q.top();
        q.pop();
    }

    cout << ans << endl;
}


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

string s;
bool bl = true;

int main() {
  cin >> s;
  if (s[0] != 'A') bl = false;
  int cnt = 0;
  for (int i = 2; i < s.size()-1; i++) {
    if (s[i] == 'C') cnt++;
  }
  if (cnt != 1) bl = false;
  if (bl) {
    cnt = 0;
    rep (i, s.size()) {
      if (s[i] <= 'Z') cnt++;
    }
    if (cnt != 2) bl = false;
  }
  cout << (bl ? "AC" : "WA") << endl;
  return 0;
}


Measured memory_bytes: 3580
#include <iostream>
#include <limits>
#include <vector>
#include <stack>
#include <algorithm>
#include <array>
#include <queue>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>
#include <cassert>

typedef uint_fast64_t u64;
typedef int_fast64_t i64;
typedef uint_least32_t u32;
typedef int_fast32_t i32;
typedef uint_least16_t u16;
typedef int_fast16_t i16;
typedef uint_least8_t u8;
typedef int_fast8_t i8;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  u64 n,k;
  std::cin >> n>>k;
  std::cout << n-k+1<<std::endl;
  return 0;
}

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

int main() {
  vector<string> day(7);
  string today;
  cin >> today;
  day={"SUN","MON","TUE","WED","THU","FRI","SAT"};
  for(int i=0;i<7;i++){
    if(today==day.at(i)){
      cout << 7-i << endl;
    }
  }
}



Measured memory_bytes: 256
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

using namespace std;

int main() {
    int d;
    cin >> d;
    if (d == 25)
        cout << "Christmas" << endl;
    else if (d == 24)
        cout << "Christmas Eve" << endl;
    else if (d == 23)
        cout << "Christmas Eve Eve" << endl;
    else if (d == 22)
        cout << "Christmas Eve Eve Eve" << endl;
    return 0;
}

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

int main() {
  int n,k;
  cin >> n >> k;

  vector<int> x(n);
  rep(i,n) cin >> x[i];

  int answer = 0;
  for (int i = 0; i < n; i++) {
    int min_dist = min(abs(x[i]), abs(x[i] - k));
    answer += min_dist * 2;
  }
  cout << answer << '\n';
}


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

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

  vector<int> v(N+1), w(N+1);
  for(int i=1; i<=N; i++) cin>>v[i]>>w[i];

  vector<int> dp(W+1, 0);

  for(int i=1; i<=N; i++){
    for(int j=1; j<=W; j++){ 
      if(j>=w[i]){
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
      }
    }
  }
  cout<<dp[W]<<endl;
}


Measured memory_bytes: 3168
a, b, c, x, y = map(int,input().split())

ans = max(x,y)*2*c
s = max(x,y)

while s:
    tmp = 0
    tmp -= c*2
    s -= 1
    if x > s:
        tmp += a
    if y > s:
        tmp += b
    if tmp > 0:
        print(ans)
        exit()
    else:
        ans += tmp
        
print(ans)

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

int main(){
    int a, b;
    cin >> a >> b;
    bool odd = false;
    int d = a*b;
    if(d*1 % 2 != 0 || d*3 % 2 !=0 || d*2 % 2 != 0) odd = true;
    if(odd) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<utility>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iomanip>
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i <= n; i++)
#define FORR(i, m, n) for(ll i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n)
#define MAX 100000
#define inf 1000000007
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

int main() {
    //cin高速化
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k,ans,tmp,a;
    cin >> n >> k;
    ans = 0;
    vll dp(n+1, 0);//初期化忘れない
    REP(i, k){
        cin >> tmp;
        REP(j,tmp){
            cin >> a;
            dp[a] = 1;
        }
    }
    FOR(i, 1, n){
        if(dp[i] == 0){
            ans ++;
        }
    }
    cout << ans <<"\n";
	return 0;
}

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

int main() {
  int a,b,k;
  cin >> a;
  cin >> b;
  int sum = a+b;
  
  if(sum%2 == 0){
    k = sum/2;
    cout << k << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }  
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int main(void){
char o[51],e[51];
int flag=0;
scanf("%s",o);
scanf("%s",e);


for(int i=0;;i++){
    if(o[i]!='\0'){printf("%c",o[i]);}
    else{flag++;}
    if(e[i]!='\0'){printf("%c",e[i]);}
    else{flag++;}
    if(flag>=1){break;}
}




}


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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

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

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

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

vector<int>h(N);
REP(i, N) cin >> h[i];

int ans = 0;
while(true){
  bool zero = true;
  int cnt = 0;
  int i = 0;
 while(i < N){ 
     

     if(h[i] == 0) ++i;
     else{
       cnt++;
       zero = false;
       while(i < N && h[i] > 0){
       --h[i];
       ++i;
       }
     }
 }
ans += cnt;
if(zero) break;

}
print(ans);

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 2e9
#define int ll
#define vi          vector<int>
#define de          deque<int>
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()//全範囲指定を簡略化
typedef long long ll;
using namespace std;
//配列の要素数は　sizeof(ar)/sizeof(ar[0]) で求める
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int H, A;
    cin >> H >> A;

    if (H%A == 0){
        cout << H / A << endl;
    }else{
        cout << H / A + 1 << endl;
    }

    return 0;
}

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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<int, int> P;
struct Edge{ll from, to, cost;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

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

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

vector<vector<int> > G;
ll N;
map<pair<ll, ll>, ll> mp;
ll maxnum = 0;

void dfs(ll from, ll current, ll color){
  ll num = G[current].size();
  ll a=current;
  rep(i, num){
    ll b = G[current][i];
    if(b==from)continue;
    color++;
    color %=maxnum;
    if(current>b){
      mp[{b, current}]= color+1;
    }else{
      mp[{current, b}]= color+1;
    }
    dfs(current, b, color);
  }
}

/**************************************
** A main function starts from here  **
***************************************/
int main(){
  
  cin >> N;
  G.resize(N);
  llvec a(N-1, 0), b(N-1, 0);
  rep(i, N-1){
    cin >> a[i] >> b[i];
    a[i]--;b[i]--;
    if(a>b)swap(a, b);
    G[a[i]].emplace_back(b[i]);
    G[b[i]].emplace_back(a[i]);
  }
  
  ll rootID;
  rep(i, N){
    if(maxnum<=G[i].size()){
      rootID=i;
      maxnum=G[i].size();
    }
  }
  dfs(-1, rootID, 0);
  cout << maxnum << endl;
  rep(i, N-1){
    cout << mp[{a[i], b[i]}] << endl;
  }
  
  return 0;
}


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

int main() {
  long long x, a = 100, count = 0;
  cin >> x; 
  
  for(int i = 1; ;i++){
      a += a * 1 / 100;
      count++;
    if(a >= x)
      break;
  }
  cout << count << endl;
}


Measured memory_bytes: 3596
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

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

    int ans = min(b / a, c);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
  return list(map(int,input().split()))
def m(): #複数文字
  return map(int,input().split())
def onem(): #Nとかの取得
  return int(input())
def s(x): #圧縮
  a = []
  if len(x) == 0:
    return []
  aa = x[0]
  su = 1
  for i in range(len(x)-1):
    if aa != x[i+1]:
      a.append([aa,su])
      aa = x[i+1]
      su = 1
    else:
      su += 1
  a.append([aa,su])
  return a
def jo(x): #listをスペースごとに分ける
  return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
  return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n = onem()

s = input()[:-1]

R = [0 for _ in range(n)]
B = [0 for _ in range(n)]
G = [0 for _ in range(n)]

co = 0

if s[0] == "R":
  R[0] = 1
elif s[0] == "G":
  G[0] = 1
else:
  B[0] = 1

for i in range(1,n):
  if s[i] == "R":
    R[i] += 1
  elif s[i] == "G":
    G[i] += 1
  else:
    B[i] += 1
  R[i] += R[i-1]
  G[i] += G[i-1]
  B[i] += B[i-1]

for i in range(1,n-1):
  if s[i] == "G":
    for j in range(i):
      if s[j] == "R":
        un = (1 if (i + (i-j) < n) and s[i + (i - j)] == "B" else 0)
        co += B[-1] - B[i] - un
      elif s[j] == "B":
        un = (1 if (i + (i-j) < n) and s[i + (i - j)] == "R" else 0)
        co += R[-1] - R[i] - un

  elif s[i] == "R":
    for j in range(i):
      if s[j] == "G":
        un = (1 if (i + (i-j) < n) and s[i + (i - j)] == "B" else 0)
        co += B[-1] - B[i] - un
      elif s[j] == "B":
        un = (1 if (i + (i-j) < n) and s[i + (i - j)] == "G" else 0)
        co += G[-1] - G[i] - un

  elif s[i] == "B":
    for j in range(i):
      if s[j] == "G":
          un = (1 if (i + (i-j) < n) and s[i + (i - j)] == "R" else 0)
          co += R[-1] - R[i] - un
      elif s[j] == "R":
          un = (1 if (i + (i-j) < n) and s[i + (i - j)] == "G" else 0)
          co += G[-1] - G[i] - un
    
print(co)





Measured memory_bytes: 74256
#include <bits/stdc++.h>
#define ll long long
#define MAX 500005
using namespace std;

int n, m, a[MAX], s;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        s += a[i];
    }
    sort(a+1, a+n+1, greater<int>());
    if(a[m]*4*m < s){
        puts("No");
    }
    else puts("Yes");

    return 0;
}

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

int main() {
  int payment, yenCount;
  cin >> payment >> yenCount;

  int zan = payment % 500;
  if(yenCount >= zan){
  	cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


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 n = sc.nextInt();
		int m = sc.nextInt();
		int answer;
		int count = 0;
		int[] parent = new int[n];
		int[] rank = new int[n];

		for(int i=0; i<n ; i++) {
			parent[i] = i;
			rank[i] = 0;
		}

		for(int i=0; i<m ;i++) {
			int a = sc.nextInt()-1;
			int b = sc.nextInt()-1;

			while(a != parent[a]) {
				a = parent[a];
			}
			while(b != parent[b]) {
				b = parent[b];
			}
			int rootA = a;
			int rootB = b;

			if (rank[rootA] > rank[rootB]) {
	            parent[rootB] = rootA;        //x の木に結合
	        }
	        else if(rank[rootA] < rank[rootB]) {
	            parent[rootA] = rootB;        //y の木に結合
	        }
	        else if (rootA != rootB) {        //同じ高さで根が違うとき
	            parent[rootB] = rootA;        //x の木に結合
	            rank[rootA]++;                //x の木の高さを加算
	        }
		}

		for(int i=0; i<n; i++) {
			if(i == parent[i]) {
				count += 1;
			}
		}

		answer = count-1;

		System.out.println(answer);
	}
}


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

int main(int argc, char *argv[]) {
  int H, W;
  cin >> H >> W;
  char a[H][W];
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      cin >> a[i][j];
    }
  }

  int h_skip[H];
  int w_skip[W];

  for(int i = 0; i < H; i++) {
    h_skip[i] = 1;
    for(int j = 0; j < W; j++) {
      if(a[i][j] == '#') {
        h_skip[i] = 0;
        break;
      }
    }
  }
  for(int j = 0; j < W; j++) {
    w_skip[j] = 1;
    for(int i = 0; i < H; i++) {
      if(a[i][j] == '#') {
        w_skip[j] = 0;
        break;
      }
    }
  }

  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      if(h_skip[i] != 1 && w_skip[j] != 1) {
        cout << a[i][j];
      }
    }
    if(h_skip[i] != 1) cout << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double LD;
using namespace std;
const int INF = 2147483647;
const int INF2 = 0x3f3f3f3f;
const ll INF64 = 4e18;
const double INFD = 1e30;
const double EPS = 1e-10;
const long double PI = acosl(-1);
const int MOD = 1e9 + 7;
template <typename T>
inline T read() {
    T X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return w ? -X : X;
}
const int MAXN = 200005;
const int MAXV = 60;
int n, m, k;
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
int dr2[8] = {1, 1, 1, -1, -1, -1, 0, 0};
int dc2[8] = {1, 0, -1, 1, 0, -1, 1, -1};
int CASE = 1;
char text[MAXN];
int a[MAXN];
int main() {
#ifdef LOCALLL
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        a[i] = read<int>();
    }
    ll ans = 0;
    int maxx = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] < maxx) {
            ans += maxx - a[i];
        }
        maxx = max(maxx, a[i]);
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 4608
n = int(input())
a = [int(input()) for _ in range(n)]

ans = 0
for i in range(n):
    ans += a[i] // 2
    if a[i] % 2 == 1 and i+1 < n:
        if a[i+1] > 0:
            a[i+1] -= 1
            ans += 1
            
print(ans)


Measured memory_bytes: 7072
#include <iostream>
using namespace std;
 //Compiler version g++ 6.3.0

 int main()
 {
 	int a,b,c;
 	cin >> a>>b>>c;
 	if(c>a+b){
 		cout << "No" << endl;
 	}else{
 		cout << "Yes" << endl;
 	}
 }

Measured memory_bytes: 256
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

int main()
{
    int64_t N;
    std::cin >> N;

    std::unordered_set<int64_t> A;
    for (int64_t i = 0; i < N; ++i) {
        int64_t t;
        std::cin >> t;
        if (A.count(t) != 0) {
            A.erase(t);
        }
        else {
            A.insert(t);
        }
    }

    std::cout << A.size() << std::endl;

    return 0;
}


Measured memory_bytes: 4388
from math import sqrt
N=int(input())
XY=[tuple(map(int,input().split())) for _ in range(N)]

def calc(r):
  lst=[]
  for i in range(N-1):
    x1=XY[i][0]
    y1=XY[i][1]
    for j in range(i+1,N):
      x2=XY[j][0]
      y2=XY[j][1]
      diff=sqrt((x1-x2)**2+(y1-y2)**2)
      if diff>2*r:
        return False
      
      h=sqrt(r**2-diff**2/4)
      if x1==x2:
        ny=(y1+y2)/2
        lst.append([x1-h,ny])
        lst.append([x1+h,ny])
      elif y1==y2:
        nx=(x1+x2)/2
        lst.append([nx,y1-h])
        lst.append([nx,y1+h])
      else:
        a=(y2-y1)/(x2-x1)
        b=-1/a
        size=sqrt(1+b**2)
        dx=h/size
        dy=dx*b
        nx=(x1+x2)/2
        ny=(y1+y2)/2
        lst.append([nx+dx,ny+dy])
        lst.append([nx-dx,ny-dy])
  nr=r+10**(-9)
  for x,y in lst:
    flag=True
    for X,Y in XY:
      tmp=(x-X)**2+(y-Y)**2
      if tmp>nr**2:
        flag=False
        break
    if flag:
      return True
  return False
l=0
r=1000
for i in range(100):
  mid=(l+r)/2
  if calc(mid):
    r=mid
  else:
    l=mid
print(r)
       
        


Measured memory_bytes: 9432
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int mincount=100000;
  int p[n+1];
  for(int i=1;i<=n;i++){
    cin >> p[i];
  }
  for(int k=0;k<=p[1];k++){
    int count=0;
    int c[n+1];
    for(int i=1;i<=n;i++){
      c[i]=p[i];
    }
    c[1]-=k;
    count+=k;
    for(int i=1;i<=n-1;i++){
      if(c[i]<=0){
        continue;
      }
      count+=c[i]*2;
      c[i+1]-=c[i];
    }
    if(c[n]>0){
      count+=c[n];
    }
    mincount=min(count,mincount);
  }


  cout <<mincount <<endl;
  return 0;
}

Measured memory_bytes: 3136
def mine(n,m):
    try:
        if n >= 0 and n<=H and m>=0 and m<=W:
            s[n][m] += 1
    except:
        None


H,W = map(int,input().split())
s = [[0 if i == "." else "#" for i in input()]for j in range(H)]
      
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            mine(i-1,j-1)
            mine(i-1,j)
            mine(i-1,j+1)
            mine(i,j+1)
            mine(i,j-1)
            mine(i+1,j-1)
            mine(i+1,j)
            mine(i+1,j+1)
        else:
            None
      
for k in s:
    a = list(map(str,k))
    print("".join(a))

Measured memory_bytes: 3064
n = int(input())
l = []
m1 = 0
m2 = 0
for i in range(n):
    num = int(input())
    l.append(num)
    if num > m1:
        m1 = num
    elif num > m2:
        m2 = num

for i in range(n):
    if l[i] != m1:
        print(m1)
    else:
        print(m2)


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

// f(0,x): 0-xのxorを返す
long long func(long long x){
  // [1] 2進表示で2^0の桁について、
  //     mod4で可能 (0,3: 0, 1,2: 1)
  // [2] 2進表示で2^1以上の桁について、
  //     0が立ってる…その桁は0（必ず偶数回の1が足されている）
  //     1が立ってる…2^0が0なら奇数回、1なら偶数回足される
  
  // [1]
  long long result=((x+1)%4<2?0:1);
  
  // [2]
  // 桁の並びは逆
  string binstr="";
  while(x>0){
    binstr+=(x%2==0?'0':'1');
    x/=2;
  }
  
  long long add=1;
  for(int i=1; i<binstr.size(); i++){
    add*=2;
    if(binstr[i]=='1'&&binstr[0]=='0'){
      result+=add;
    }
  }
  
  return result;
}

int main(){
  long long A,B; cin >> A >> B;
  
  // f(A,B)=f(0,B)(+)f(0,A-1) (A>0)
  if(A==0) cout << func(B) << endl;
  else cout << (func(B)^func(A-1)) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int solve(vector<int> a,int n)
{
  vector<int> dp(n+1);
  dp[1] = 0;
  for(int i = 2;i <= n;i++)
  {
    int op1 = abs(a[i] - a[i-1]) + dp[i-1];
    int op2 = (i==2) ? INT_MAX:abs(a[i] - a[i-2]) + dp[i-2];
    dp[i] = min(op1,op2);
  }
  return dp[n];
}
int main()
{
  int n;
  cin>>n;
  vector<int> a(n+1);
  for(int i = 1;i <=n;i++)
  {
    cin>>a[i];
  }
  cout<<solve(a,n)<<endl;
}

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

#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin>>n;
vector<int>a(n);
map<int,int>dic;
rep(i,n){
    cin>>a[i];
    dic[a[i]]++;
}
int cnt=dic.size();
string judge="Yes";
if(cnt==3){
    int res=0;
    for(auto v:dic){
        res=res^v.first;
        if(v.second*3!=n){
            judge="No";
            break;
        }
    }
    if(res!=0){
        judge="No";
    }
}
else if(cnt==2){
    for(auto v:dic){
        if(v.first==0){
            if(v.second*3!=n){
                judge="No";
                break;
            }
        }
        else{
            if(v.second*3!=2*n){
                judge="No";
                break;
            }
        }
    }
}
else if(cnt==1){
    for(auto v:dic){
        if(v.first!=0){
            judge="No";
            break;
        }
    }
}
else{
    judge="No";
}
cout<<judge<<endl;
return 0;
}

Measured memory_bytes: 7200
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll MOD = 1000000007;

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

  string s;
  cin >> s >> s;

  string ss;

  int i = 0;
  while(i < s.length()) {
    if(i + 1 < s.length() && s[i] == s[i + 1]) {
      ss += 'h';
      i += 2;
    }else {
      ss += 'v';
      i += 1;
    }
  }

  ll ans = 1;

  if(ss[0] == 'v') {
    ans = 3;
  }else {
    ans = 6;
  }

  for(int i = 0; i < ss.length() - 1; i++) {
    string sub = ss.substr(i, 2);
    if(sub == "vv") {
      ans = ans * 2;
    }else if(sub == "vh") {
      ans *= 2;
    }else if(sub == "hh") {
      ans *= 3;
    }else if(sub == "hv") {
      ans *= 1;
    }

    ans %= MOD;
  }

  cout << ans << endl;


}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#define llint long long
#define inf 1000000000
#define mod 998244353

using namespace std;

struct UnionFind{
	int size;
	vector<int> parent;
	
	UnionFind(){}
	UnionFind(int size){
		this->size = size;
		parent.resize(size+1);
		init();
	}
	void init(){
		for(int i = 0; i <= size; i++) parent[i] = i;
	}
	int root(int i){
		if(parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	void unite(int i, int j){
		int root_i = root(i), root_j = root(j);
		if(root_i == root_j) return;
		parent[root_i] = root_j;
	}
};

llint n;
llint a[300005];
llint l[300005], r[300005];
llint R[300005];
UnionFind uf(300005);
set<llint> S;

int main(void)
{
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	
	for(int i = 0; i < n-1; i++){
		if(a[i] == a[i+1]) uf.unite(i, i+1);
	}
	if(a[0] == a[n-1]) uf.unite(0, n-1);
	
	llint len = 0;
	for(int i = 1; i <= n; i++) R[i] = -1;
	for(int i = 0; i < n; i++){
		if(R[a[i]] != -1 && R[a[i]] != uf.root(i)){
			cout << 0 << endl;
			return 0;
		}
		R[a[i]] = uf.root(i);
		if(a[i] == 1) len++;
	}
	if(len == n){
		llint ans = 1;
		for(int i = 1; i <= n; i++) ans *= i, ans %= mod;
		cout << ans << endl;
		return 0;
	}
	
	for(int i = 1; i <= n; i++) l[i] = inf, r[i] = -inf;
	for(llint i = 0; i < n; i++){
		l[a[i]] = min(l[a[i]], i);
		r[a[i]] = max(r[a[i]], i);
	}
	if(a[0] == a[n-1]){
		for(int i = 0; i < n; i++){
			if(a[i] != a[0]){
				r[a[0]] = i-1;
				break;
			}
		}
		for(int i = n-1; i >= 0; i--){
			if(a[i] != a[n-1]){
				l[a[n-1]] = i+1;
				break;
			}
		}
		if(l[a[0]] > r[a[0]]) r[a[0]] += n;
	}
	//for(int i = 1; i <= n; i++) cout << l[i] << " " << r[i] << endl;
	
	for(int i = 1; i <= n; i++){
		if(l[i] == inf) continue;
		if(r[i]-l[i]+1 > len){
			cout << 0 << endl;
			return 0;
		}
	}
	
	llint ans = 1, valid = 0;
	for(int i = l[1]; i <= r[1]; i++) S.insert(i%n);
	for(int i = 2; i <= n; i++){
		if(l[i] == inf){
			if(valid <= 0){
				cout << 0 << endl;
				return 0;
			}
			ans *= valid, ans %= mod;
			valid--;
			continue;
		}
		bool lflag = S.count((l[i]-1+n)%n), rflag = S.count((r[i]+1)%n);
		if(!lflag && !rflag){
			if(len != r[i]-l[i]+1){
				cout << 0 << endl;
				return 0;
			}
		}
		else if(!lflag || !rflag) valid += r[i]-l[i];
		else{
			ans *= len - (r[i]-l[i]+1) + 1, ans %= mod;
			valid += len-1+(r[i]-l[i]+1)-1;
		}
		for(int j = l[i]; j <= r[i]; j++) S.insert(j%n);
		//cout << i << " " << S.size() << " " << valid << " " << ans << endl;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 27648
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;
const int MaxN = 1e5;
int T, n, m;
int a[MaxN + 5];
int main()
{
	int a, b, c, d;
	scanf("%d%d%d%d", &a,&b, &c, &d);
	int sum = a+b;
	int ans = c + d;
	if(sum > ans) printf("Left\n");
	else if(sum == ans) printf("Balanced\n");
	else printf("Right\n");
}

Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,d = map(int, input().split())
    x = [list(map(int, input().split())) for _ in range(n)]
    res = 0
    def calc(a, b):
        total = 0
        for i in range(d):
            total += (a[i]-b[i])**2
        total = total ** 0.5
        return total.is_integer()

    for i in range(n-1):
        for j in range(i+1, n):
            if calc(x[i], x[j]):
                res += 1
    print(res)

if __name__ == '__main__':
    main()

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repi(i, a, b) for (int i = (a); i < int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())

using namespace std;
using i32 = int;
using i64 = long long;
using f64 = double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf64 = vector<f64>;
using vstr = vector<string>;

template<typename T, typename S> void amax(T &x, S y) { if (x < y) x = y; }
template<typename T, typename S> void amin(T &x, S y) { if (y < x) x = y; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(16);
  int n; cin >> n;
  vi32 a(n), b(n);
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> b[i];
  i32 ans = 0;
  rep(i, 30) {
    vi32 ma = a, mb = b;
    rep(j, n) ma[j] %= bit(i + 1);
    rep(j, n) mb[j] %= bit(i + 1);
    sort(all(mb));
    i32 cnt = 0;
    rep(j, n) {
      i32 c1 = lower_bound(all(mb), 2 * bit(i) - ma[j])
             - lower_bound(all(mb), 1 * bit(i) - ma[j]);
      i32 c2 = lower_bound(all(mb), 4 * bit(i) - ma[j])
             - lower_bound(all(mb), 3 * bit(i) - ma[j]);
      cnt += c1 + c2;
    }
    if (cnt % 2) ans += bit(i);
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
  ll n; cin >> n;
  if (n%2) {
    cout << 0;
    return 0;
  }
  ll ans = 0;
  n /= 2;
  while(n) {
    ans += n / 5;
    n /= 5;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 998244353
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl

int n,a[200005];
int at[1000005];
int val[1000005];

ll powmod(ll a,ll b)
{
    ll an=1;
    while(b>0)
    {
        if((b&1))
            an=(an*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return an;
}

int main()
{
    SPEED;
    
    cin>>n;
    
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        at[a[i]]=(at[a[i]]+a[i])%MOD;
    }

    int ans=0;
    
    for(int i=1000000;i>=1;i--)
    {
        int sum=0;
        for(int j=i;j<=1000000;j+=i)
        {
            val[i]=(val[i]-val[j]+MOD)%MOD;
            sum=(sum+at[j])%MOD;
        }
        sum=(sum*1ll*sum)%MOD;
        val[i]=(val[i]+sum)%MOD;
        sum=val[i];
        int cnt=(at[i]*1ll*powmod(i,MOD-2))%MOD;
        sum=(sum-cnt*1ll*i*1ll*i+MOD*1ll*MOD)%MOD;
        sum=(sum*1ll*powmod(2,MOD-2))%MOD;
        ans = (ans + sum*1ll*powmod(i,MOD-2))%MOD;
    }

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

Measured memory_bytes: 8832
def f(n, r)
  unless $memo[n][r]
    $memo[n][r] = f(n - 1, r - 1).map{|i|i + [1]}
    $memo[n][r] += f(n - r, r).map{|i|i.map{|j|j + 1}} if n >= 2 * r
  end
  return $memo[n][r]
end
def main(input = STDIN)
  while (n = input.gets.to_i) != 0
    $memo = Array.new(n + 1){|i|[[[0]], [[i]]]}
    arr = []
    (1..n).each{|i|arr += f(n, i)}
    puts arr.sort.reverse.map{|i|i.join(" ")}
  end
end
main

Measured memory_bytes: 11808