akhauriyash/Code-Regression huggingface dataset:
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

char table[100][100];
int H,W;
void dfs(int x, int y){
	char c=table[x][y];
	table[x][y]='.';
	int dxs[4]={0,-1,0,1};
	int dys[4]={-1,0,1,0};
	for(int i=0;i<4;i++){
		int xx=x+dxs[i];
		int yy=y+dys[i];
		if(0<=xx&&xx<H&&0<=yy&&yy<W&&
			table[xx][yy]==c){
			dfs(xx,yy);
		}
	}
}
bool search()
{
	cin >> H >> W;
	if (H==0&&W==0){
		return false;
	}

	for(int i=0;i<H;i++){
			cin >> table[i];
	}
	int ret=0;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(table[i][j]!='.'){
				ret++;
				dfs(i,j);
			}
		}
	}
	cout << ret << endl;
	return true;
}
int main() {
	while(search()){
		;
	}
}

Measured memory_bytes: 1948
#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>;
const int MOD=1000000007;

int main() {
  int x, n;
  cin >> x >> n;
  set<int> p;
  rep(i,n) {
    int y;
    cin >> y;
    p.insert(y);
  }
  rep(i,x+1) {
    if(!p.count(x-i)) {
      cout << x-i << endl;
      return 0;
    }
    if(!p.count(x+i)) {
      cout << x+i << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 3604
// D - Triangles
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define all(x) (x).begin(),(x).end()

int solve(int N, vi &L){
	sort(all(L));
	int ans = 0;
	rp(b, 0, N) rp(a, 0, b){
		int maxL = L[a] + L[b];
		int r = lower_bound(all(L), maxL) - L.begin();
		int l = b + 1;
		ans += max(0, r-l);
	}
	return ans;
}

int main(){
	int N; cin>>N;
	vi L(N);
	rp(i, 0, N) cin>>L[i];
	cout<< solve(N, L) <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int main(){
	int n, a, m;
	while( cin >> n , n ){
		map<int,int> p;
		m = 0;
		
		for(int i=0 ; i<n; i++ ){
			cin >> a;
			m = max( m , a );
			p[a] = 1;
		}
		bool flag = false;
		bool flag2 = false;
		for(int i=1 ; i<=m+1 ; i++ ){
			if( flag == false ){
				if( p.count( i ) ){
					cout << i ;
					flag = true;
					flag2 = true;
				}else{}
			}else{
				if( p.count( i ) ){
					if( flag2 )
						cout << "-";
					flag2 = false;
				}else{
					if( !flag2 )
						cout << (i-1);
					if( i < m )
						cout << " ";
					flag2 = false;
					flag = false;
				}
			}
		}
		cout << endl;
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#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 ALL(a) (a).begin(), (a).end()

int main() {
    int x, a, b;
    cin >> x >> a >> b;
    if (abs(x - a) < abs(x - b)) cout << "A" << endl;
    else cout << "B" << endl;
    return 0;
}

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

import static java.lang.Integer.parseInt;

/**
 * Sum of Integers II - Accepted
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		long[][] dp = new long[10][1001];

		dp[0][0] = 1;
		dp[1][0] = 1;

		for (int i = 1; i <= 100; i++) {
			for (int j = 9; j >= 1; j--) {
				for (int k = i; k <= 1000; k++) {
					dp[j][k] += dp[j - 1][k - i];
				}
			}
		}

		while ((line = br.readLine()) != null && !line.isEmpty()) {

			int n, s;
			n = parseInt(line.substring(0, line.indexOf(' ')));
			s = parseInt(line.substring(line.indexOf(' ') + 1));
			if ((n | s) == 0) return;

			System.out.println(dp[n][s]);
		}
	}
}

Measured memory_bytes: 25360
#include<bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define FORR(i,a,b) for (int i = b - 1; i >= a; --i)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) FORR(i,0,n)

template<class T>
inline void read(T& x) {
  T s = 0, base = 1;
  char c;
  while (!isdigit(c=getchar())) if (c == '-') base = -base;
  while (isdigit(c)) {
    s = s * 10 + (c^48);
    c = getchar();
  }
  x = base * s;
}

int main() {
  int N, K;
  read(N);
  read(K);
  if (N % K == 0) printf("0\n");
  else printf("1\n");
  return 0;
}


Measured memory_bytes: 256
H,W = map(int,input().split())

if H%3==0 or W%3==0:
    print(0)
    exit()

ans = min(H,W)
if H%2==0:
    for w in range(1,W):
        s1 = w*H
        s2 = (W-w)*H//2
        ans = min(ans, abs(s1 - s2))
if W%2==0:
    for h in range(1,H):
        s1 = h*W
        s2 = (H-h)*W//2
        ans = min(ans, abs(s1 - s2))

for h in range(H//2,H//2+2):
    if h >= H: break
    for w in range(W//2,W//2+2):
        if w >= W: break
        s1 = h*W
        s2 = (H-h)*w
        s3 = (H-h)*(W-w)
        ans = min(ans, s1, s2, s3)

print(ans)


Measured memory_bytes: 3064
/*|In The Name Of Allah|*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

string s;
char nw[N];

int main(){
    cin >> s;
    int cnt = 0;
    int k = 0;
    for(int i = 0; i < s.size(); i++){
        while(k >= 2 && nw[k - 2] != s[i]){
            cnt++;
            k--;
        }
        nw[k ++] = s[i];
    }
    if(cnt & 1){
        cout << "First" << endl;
    } else {
        cout << "Second" << endl;
    }
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main() {
    while(true) {
        int m,f,r;
        cin >> m >> f >> r;
        if(m==-1 && f==-1 && r==-1) break;
        else if (m == -1 || f == -1) cout << 'F' << endl;
        else if (m + f >= 80) cout << 'A' << endl;
        else if (m + f >= 65) cout << 'B' << endl;
        else if (m + f >= 50) cout << 'C' << endl;
        else if (m + f >= 30 && r >= 50) cout << 'C' << endl;
        else if (m + f >= 30) cout << 'D' << endl;
        else cout << 'F' << endl;
    }
}


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <set>
#include <queue>
#include <string>
#include <string.h>
#include <deque>
#include <functional>
#include <tuple>
#include <stdio.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vec;
typedef vector<vec> vec2;

//for文
#define FOR(i,a,b) for(ll i = (ll)a;i < (ll)b;i++)
#define FORE(i,a,b) for(ll i = (ll) a;i <= (ll) b;i++ )
#define REP(i,size_of_array)  for(ll i =(ll)0;i<size_of_array;i++)
#define REPE(i,size_of_array)  for(ll i =(ll)0;i<=size_of_array;i++)
#define REPR(i,size_of_array)  for(ll i =(ll)size_of_array;i>=0;i--)

//ソート
#define ALL(vec) (vec).begin(),(vec).end()
#define SORT(vec) sort(ALL(vec))
#define INVSORT(vec) sort((vec).rbegin(),(vec).rend())

//最大値最小値
#define MAX(vec) *max_element(ALL(vec))
#define UNIQ(vec) SORT(vec);vec.erase(unique(ALL(vec)),vec.end())
#define MIN(vec) *min_element(ALL(vec))

//表示
#define printl(a) cout << a << endl
#define print(a) cout << a
#define SP cout << " "

//入力
#define inputV(vec) REP(i,vec.size()){cin >> vec[i];}
#define input(a) cin >> a

//型
#define float ld
#define double ld
#define P pair<ll,ll>
#define vp vector<P>
#define F first
#define S second

//特殊
#define int ll
#define DEBUG(x) cerr << #x << ":" << x<<endl
#define  DEBUGV(V) REP(i,V.size()){cerr << #V[i] << ":" << V[i]<<endl;}

template<class T> inline void umax(T &a,const T &b) { if(a < b) a = b; }
template<class T> inline void uhmin(T &a,const T &b) { if(a > b) a = b; }

const ll INF = 1ll << 60;
const ld EPS = 1e-8;

signed main(){
    ll N;
    input(N);
    vec A(N);
    inputV(A);
    ll cnt = 0;
    bool dec = false;
    bool inc = false;
    FOR(i,1,A.size()){
        if(A[i-1] > A[i]) dec = true;
        else if(A[i-1] < A[i] ) inc = true;

        if(dec and inc){
            dec = false;
            inc = false;
            cnt++;
        }
        DEBUG(cnt);
    }

    print(++cnt);
}




Measured memory_bytes: 1024
#include <stdio.h>
int main (int argc, char * argv[])
{
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    if(a<b&&b<c){
        printf("Yes\n");
    }else {
          printf("No\n");
    }
    return 0;
}



Measured memory_bytes: 2100
#include<bits/stdc++.h>
using namespace std;
int n,k;
long long a[200010],b[200010],s;
int main(){
	cin>>n>>k;
	a[1]=0;
	b[1]=n;
	for(int i=2;i<=n+1;i++){
		a[i]=a[i-1]+i-1;
		b[i]=b[i-1]+n-i+1;
	}
	for(int i=k;i<=n+1;i++){
		s=s+b[i]-a[i]+1;
		s=(s*1ll)%1000000007;
	}
	cout<<s;
	return 0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  
  vector<int> a(n);
  int sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
    sum += a.at(i);
  }
  
  int dif = 1e9, keep = 0;
  for (int i = 0; i < n; i++) {
    if (abs(sum - a.at(i) * n) < dif) {
      dif = abs(sum - a.at(i) * n);
      keep = i;
    }
  }
  
  cout << keep << '\n';
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

const int INF = INT_MAX / 2;

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

    while(--t >= 0){
        int n;
        cin >> n;

        string s;
        cin >> s;
        s = 'N' + s.substr(0, 2*n) + "NN" + s.substr(2*n) + 'N';

        vector<int> dp(3, INF);
        dp[0] = -2;

        for(int i=0; i<n+1; ++i){
            for(int j=0; j<3; ++j)
                dp[j] += 2;

            vector<int> book;
            if(s[2*i] == 'Y' || s[2*i+1] == 'Y')
                book.push_back(1);
            if(s[2*n+2+2*i] == 'Y' || s[2*n+2+2*i+1] == 'Y')
                book.push_back(3);
            if(book.size() == 0)
                continue;

            vector<int> next(3, INF);
            for(int j=0; j<3; ++j){
                for(int k=0; k<3; ++k){
                    int x = abs(j*2 - book.front()) + abs(k*2 - book.back());
                    if(book.size() == 2){
                        x = min(x, abs(j*2 - book.back()) + abs(k*2 - book.front()));
                        x += abs(book[0] - book[1]);
                    }
                    next[k] = min(next[k], dp[j] + x);
                }
            }
            dp.swap(next);
        }

        cout << (dp[0] / 2) << endl;
    }

    return 0;
}

Measured memory_bytes: 0
{-# LANGUAGE FlexibleInstances    #-}
{-# LANGUAGE TypeSynonymInstances #-}

import           Control.Applicative
import           Control.DeepSeq
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                    as A
import qualified Data.Array.IArray             as IA
import qualified Data.Array.IO                 as AI
import qualified Data.Array.MArray             as MA
import qualified Data.Array.ST                 as STA
import qualified Data.Array.Unboxed            as AU
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import qualified Data.Graph                    as G
import           Data.Int
import qualified Data.IntMap                   as IM
import qualified Data.IntSet                   as IS
import           Data.List
import qualified Data.Map.Strict               as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Sequence                 as SQ
import qualified Data.Set                      as S
import           Data.Time
import qualified Data.Tree                     as T
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readInteger :: IO [Integer]
readInteger = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegers :: Int -> IO [[Integer]]
readIntegers n = replicateM n readInteger

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

put :: Show a => a -> IO ()
put = putStr . show

putLn :: Show a => a -> IO ()
putLn = print

putList :: Show a => [a] -> IO ()
putList [n     ] = put n
putList (n : ns) = do
  put n
  putStr " "
  putList ns

putStrList :: [String] -> IO ()
putStrList [n     ] = putStr n
putStrList (n : ns) = do
  putStr n
  putStr " "
  putStrList ns

yesNoUpper b | b         = putStrLn "YES"
             | otherwise = putStrLn "NO"

yesNo b | b         = putStrLn "Yes"
        | otherwise = putStrLn "No"

main = do
  [a,b,c]<-readInt
  yesNoUpper $ (b-a)==(c-b)

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

using namespace std;
#define sz(x) (int)((x).size())
#define forn(i,n) for (int i=0; i < n; i++)
#define forse(i,s,e) for (int i=s; i < e; i++)
#define pb push_back
#define pf push_front
#define rb pop_back
#define rf pop_front
#define mp make_pair
#define fi first
#define se second
#define all(vec) vec.begin(), vec.end()
#define time() ((double)clock() / CLOCKS_PER_SEC)

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


void solve(){
	int n;
	cin >> n;
	n%=10;
	vector<set<int>> tem={{2,4,5,7,9},{0,1,6,8},{3}};
	vector<string> out={"hon","pon","bon"};
	forn(i,3){
		if(tem[i].find(n)!=tem[i].end()){
			cout << out[i];
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	int T=1;
//	cin >> T;
	forn(c,T){
//		cout << "Case #" << c+1 << ": ";
		solve();
	}
}


Measured memory_bytes: 3656
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <climits>
#include <cassert>
#include <algorithm>
#include <utility>

using namespace std;
using Int = long long int;
using UInt = unsigned long long int;
using VI = vector<long long int>;
using VVI = vector<vector<long long int> >;

// 分数の Ceil を求める関数
UInt Ceil(const UInt a, const UInt b) {
    if (a % b == 0) {
        return a / b;
    } else {
        return a / b + 1;
    }
}

int main(void) {
    Int n;
    cin >> n;
    cout << Ceil(n, 2) - 1 << endl;
    return 0;
}


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

bool b[10000][4];
int dp[20000][1<<4];
int main(){
	int h,n;scanf("%d%d",&h,&n);
	rep(i,n){
		int x,y;scanf("%d%d",&y,&x);
		b[h-x-1][y]=true;
	}
	rep(i,h-1)rep(j,1<<4){
		dp[i+1][0]=max(dp[i+1][0],dp[i][j]);
		rep(k,3){
			if(!(j>>k&1)&&!(j>>(k+1)&1)&&!b[i][k]&&!b[i][k+1]&&!b[i+1][k]&&!b[i+1][k+1]){
				dp[i+1][(1<<k)|(1<<(k+1))]=max(dp[i+1][(1<<k)|(1<<(k+1))],dp[i][j]+1);
			}
		}
		if(j==0){
			bool flag=true;
			rep(k,2)rep(t,4){
				if(b[i+k][t]==1)flag=false;
			}
			if(flag){
				dp[i+1][(1<<4)-1]=max(dp[i+1][(1<<4)-1],dp[i][j]+2);
			}
		}
	}
	int ans=0;
	rep(i,1<<4){
		ans=max(ans,dp[h-1][i]);
	}
	cout<<ans<<endl;
}

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

int main(int, char**) {
  int N, K;
  cin >> N >> K;

  cout << (1 + (N - K) / (K - 1) + ((N-K) % (K-1) !=0)) << endl;

  // vector<int> nums;
  // nums.resize(N);
  // for (int i = 0; i < N; i++) {
  //   cin >> nums[i];
  // }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> PL;
typedef pair<P, LL> PP;
typedef pair<P, LL> PP;
typedef long long LL;

#define xx first
#define yy second

vector<int> G[1100];
int n,m;
int mi=1000000;
vector<int> vmi;
vector<int> st;
int onstack[11000];
int vis[11000];

bool check(const vector<int>& ret) {
  set<int> A(ret.begin(), ret.end());
  for (auto& u : ret) {
    int cnt = 0;
    for (auto& v : G[u]) {
      if (A.count(v)) ++cnt;
    }
    if (cnt > 1) return false;
  }
  return true;
}

void ck(int adj){
  vector<int> tp;
  for(int i = st.size()-1;st[i]!=adj;i--)
    tp.push_back(st[i]);
  tp.push_back(adj);
  if(tp.size()<mi && check(tp)){
    mi = tp.size();
    vmi = tp;
  }
}

void dfs(int p){
  st.push_back(p);
  onstack[p]=1;
  vis[p] = 1;
  for(int adj:G[p]){
    if(vis[adj]==0)dfs(adj);
    else if(onstack[adj])ck(adj);
  }
  onstack[p]=0;
  st.pop_back();
}

int main()
{
  // #ifndef ONLINE_JUDGE
  //freopen("input", "r", stdin);
  // freopen("output", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    G[a].push_back(b);
  }
  for(int i=1;i<=n;i++)
    if(!vis[i])dfs(i);
  if(mi==1000000){cout<<-1<<endl;return 0;}
  cout<<mi<<endl;
  for(int i:vmi)
    cout<<i<<endl;
  // cout<<endl;

}


Measured memory_bytes: 384
n, k = map(int, input().split())

p = 0
# for i in range(1, n + 1):
#     m = np.ceil(np.log2(k / i))
#     p += 1 / n * (1 / 2 ** m)

for i in range(1, n + 1):
    s = i
    tmp = 1 / n
    while s < k:
        s *= 2
        tmp /= 2
    p += tmp

print(p)

"""
2**3 = 8
3 = np.log2(8)

n * 2**x = k
2**x = k / n
x = np.log2(k / n)
"""


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

const int N = 200010;
const ll MOD = ll(1e9 + 7);

int n;
int b[2];
int c[N], w[N];
int p[N];
map<int, int> cc[N];
vector<int> v[N];

ll fact[N];
ll ifact[N];

int get(int x) {
    if (p[x] == -1) {
        return x;
    }
    return p[x] = get(p[x]);
}

void unite(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) {
        return;
    }
    p[a] = b;
}

ll pw(ll a, ll b = MOD - 2) {
    ll r = 1;
    for (; b > 0; b >>= 1) {
        if (b & 1) {
            r = r * a % MOD;
        }
        a = a * a % MOD;
    }
    return r;
}

void precalc() {
    fact[0] = 1;
    ifact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = i * fact[i - 1] % MOD;
        ifact[i] = pw(fact[i], MOD - 2);
    }
}

int main() {
    precalc();

    scanf("%d %d %d", &n, &b[0], &b[1]);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &c[i], &w[i]);
        c[i]--;
        v[c[i]].push_back(i);
    }

    fill_n(p, n, -1);

    vector<int> cand;

    for (int i = 0; i < n; i++) {
        if (v[i].empty()) {
            continue;
        }

        sort(v[i].begin(), v[i].end(), [&](int x, int y) { return w[x] < w[y]; });
        int x = v[i][0];
        for (int y: v[i]) {
            if (x == y) {
                continue;
            }
            if (w[x] + w[y] > b[0]) {
                break;
            }
            unite(x, y);
        }

        cand.push_back(x);
    }

    sort(cand.begin(), cand.end(), [&](int x, int y) { return w[x] < w[y]; });
    for (int i = 0; i < min(2, int(cand.size())); i++) {
        int x = cand[i];
        for (int y = 0; y < n; y++) {
            if (c[x] != c[y] && w[x] + w[y] <= b[1]) {
                unite(x, y);
            }
        }
    }

/*    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            if (w[i] + w[j] <= b[(c[i] != c[j])]) {
                unite(i, j);
            }
        }
    }*/

    for (int i = 0; i < n; i++) {
        int j = get(i);
        cc[j][c[i]]++;
    }

    ll ans = 1;
    for (int i = 0; i < n; i++) {
        int tot = 0;
        for (auto z: cc[i]) {
            ans = ans * ifact[z.second] % MOD;
            tot += z.second;
        }
        ans = ans * fact[tot] % MOD;
    }

    printf("%lld\n", ans);
}


Measured memory_bytes: 34164
#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
#include<cmath>
#include<functional>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    vector<vector <int> > l(N, vector<int>(N));
    vector<int> v(N-1);
    for (int i=0; i< N-1; i++){
        v.at(i) = i+1;
    }
    for (int i=0; i< M; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        l.at(a).at(b) = 1;
        l.at(b).at(a) = 1;
    }
    int r = 0;
    do{
        if(l.at(0).at(v.at(0))==0){
            continue;
        }
        int t = 0;
        for(int i=0; i<N-2; i++){
            if(l.at(v.at(i)).at(v.at(i+1)) == 0){
                break;
            }
            t++;
        }
        if (t == N-2){
            r++;
        }
    }while(next_permutation(v.begin(), v.end()));
    cout << r << endl;
}


Measured memory_bytes: 3612
q = int(input())

L = [True] * (10**5 + 1)

L[0], L[1] = False, False

for i in range(2, int((10**5) ** 0.5) + 1):
    if not L[i]:
        continue
    j = 2
    while i * j <= 10**5:
        L[i * j] = False
        j += 1

A = [0] * (10**5 + 1)
for i in range(1, 10**5 + 1):
    if L[i] and L[(i+1)//2]:
        A[i] = A[i-1] + 1
    else:
        A[i] = A[i-1]

for i in range(q):
    l, r = map(int, input().split())
    if l == r:
        if L[l] and L[(l+1)//2]:
            print(1)
        else:
            print(0)
    else:
        if L[l] and L[(l+1)//2]:
            print(A[r] - A[l-1])
        else:
            print(A[r] - A[l])

Measured memory_bytes: 10812
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//
//    #pragma GCC optimize("unroll-loops")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC optimize("-O3")
//    #pragma GCC optimize("no-stack-protector")
//    #pragma GCC optimize("fast-math")

#define fi first
#define f first
#define se second
#define s second
#define vi_a vector<int>a;
#define p_b emplace_back
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ll long long
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define fast_io cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(),x.end()
#define getfiles    ifstream cin("input.txt");ofstream cout("output.txt");
#define pw(x) (1ll << x)
#define sz(x) (ll)x.size()
#define endl "\n"
#define rall(x) x.rbegin(),x.rend()
#define len(a) (ll)a.size()
#define rep(x,l,r) for(ll x=l;x<r;x++)
//#define for(int i=0;i<n;i++) for(ll i=0;i<n;i++)
using namespace std;
//using namespace __gnu_pbds;
ld eps = (ld)1 / 1e7;
ll inf = 1e18, mod2 = 998244353, mod1 = 1e9 + 7;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//const ll to[5]={0,4,6,7,9};
//const ll N=2*1e5+1;
const ll R=1e4;
//const ll to[7]={1,2,3,1,3,2,1};
const ll tx[4]={2,-1,2,1};
const ll ty[4]={-1,2,1,2};
const char rev_to[4]={'E','W','N','S'};
const int N=3001;
int dp[N][N],a[N],b[N],p[N][N];int ans[N];
signed main(){
    ll n,m;
    cin>>n>>m;
    vector<ll>a(m);
    ll sum=0;
    for(auto &z : a){
        cin>>z;sum+=z;
    }
    if(sum>n){
        cout<<-1;
    }
    else{
        cout<<n-sum;
    }
    return 0;
}
/*

    если WA , то чекер говно, поэтому почекай l8 строчку

*/


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

int main()
{
    long long n;
    cin >> n;
    vector<long long> a;
    for(int i = 0; i < n; i++){
        long long in;
        cin >> in;
        a.push_back(in);
    }
    sort(a.begin(), a.end(), greater<long long>());
    long long tate = 0;
    long long yoko = 0;
    for(int i = 0; i < n - 1; i++){
        if(a[i] == a[i + 1]){
            if(tate == 0){
                tate = a[i];
            }
        else {
            yoko = a[i];
            }
        a[i + 1] = 0;
        }
        if(yoko != 0){
            break;
        }
    }
    cout << tate * yoko << endl;
    return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    int d[N];
    for(int i=0; i < N; i++) cin >> d[i];
    int temp = -1;
    int mochi = 0;
    sort(d, d+N, greater<int>());
    for(int i=0; i<N; i++){
        if(temp != d[i]){
            mochi++;
        }
        temp = d[i];
    }

    cout << mochi << endl;
    return 0;
}

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

int main() {
    double a, b, c, d, e, f;
    while (cin >> a >> b >> c >> d >> e >> f) {
        double x, y;
        x=(c*e-b*f)/(a*e-b*d)+1e-10;
        y=(c*d-a*f)/(b*d-a*e)+1e-10;
        printf("%.3f %.3f\n",x,y);
    }
    return 0;
}

Measured memory_bytes: 3088
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstdlib>
#include<algorithm>
using namespace std;
double n,s;
int main()
{
cin>>n>>s;
cout<<int((n+s)/2+0.5);
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)
using ll = long long;
using P = pair<int,int>;
// auto mod int
const int mod = 1000000007;//998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint dp[2001];
int main() {
   int s;cin>>s;
   dp[0]=1;
   for (int i = 3; i <= s; i++){
      for (int j = 0; j < i; j++){
         int k=i-j;
         if(k==1||k==2||j==1||j==2)continue;
         dp[i]+=dp[j];
      }
   }
   cout<<dp[s]<<endl;
}

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

int main() {
    int n,x,t;cin>>n>>x>>t;
    int ans = 0;
    int cc=0;
    rep(i,n){
        cc+=x;
        ans+=t;
        if(cc>=n){
            cout<<ans<<endl;
            return 0;
        }
    }
	return 0;
}

Measured memory_bytes: 3624
n, m = map(int, input().split())
list_place_student = []
for _ in range(n):
  a, b = map(int, input().split())
  list_place_student.append((a, b))
list_checkpoint = []
for _ in range(m):
  c, d = map(int, input().split())
  list_checkpoint.append((c, d))
  
result = []
for place in list_place_student:
  min_dist = 10 ** 9
  min_point = 100
  for i, point in enumerate(list_checkpoint):
    temp_dist = abs(place[0] - point[0]) + abs(place[1] - point[1])
    if temp_dist < min_dist:
      min_dist = temp_dist
      min_point = i + 1
  result.append(min_point)

for one_result in result:
  print(one_result)

Measured memory_bytes: 3064
/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<int> adj[N];
int n, sz[N];

void dfs(int u, int par) {
	sz[u] = 1;
	int cnt = 0;
	for (auto v: adj[u])
		if (v ^ par) {
			dfs(v, u);
			sz[u] += sz[v];
			cnt += sz[v] & 1;
		}
	if (cnt > 1) {
		cout << "First\n";
		exit(0);
	}
}

inline void readInput() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;

		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

inline void solve() {
	dfs(0, 0);
	cout << (n & 1? "First\n": "Second\n");
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	readInput(), solve();
	return 0;
}

Measured memory_bytes: 6144
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

N,M = map(int,input().split())

facterint = [1]
for i in range(1,max(N,M)+1):
    facterint.append(facterint[-1]*i%mod)


if abs(N-M) > 1:
    print(0)
    exit()

if N==M:
    ans = 2*facterint[N]*facterint[M]%mod
else:
    ans = facterint[N]*facterint[M]%mod

print(ans)


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

typedef long long ll;
const ll INF = 1e18;
const int BIG = 1e9 + 555;
const int maxN = 100 + 9;

int n;
double v[maxN];

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

	for(int i = 1; i <= n; i++){
		cin >> v[i];
	}
	
	sort(v + 1, v + n + 1);

	double ans = (v[1] + v[2]) / 2.00;
	
	for(int i = 3; i <= n; i++){
		ans = (ans + v[i]) / 2.00;
	}
	
	cout << setprecision(10) << fixed;
	cout << ans << '\n';

	return 0;
}

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

using namespace std;

int n,a,b,c,d;

bool solve(){
    int i,j;
    string str;
    cin >> n >> a >> b >> c >> d;
    a--;b--;c--;d--;
    cin >> str;
    if(c > d){
        int f = 0;
        for(i = b-1,j = 0;i <= d+1;i++){
            if(str[i] == '.') j++;
            else j = 0;
            if(j == 3){
                f = 1;
                break;
            }
        }
        if(f == 0) return false;
    }
    for(i = a+1;i < max(c,d)-1;i++){
        if(str[i] == '#' && str[i+1] == '#') return false;
    }
    return true;
}

int main(){
    if(solve()) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m;cin>>n>>m;
    vector<int>v[n+1];
    int h[n+1];
    for(int i=1;i<=n;++i)
    {
        cin>>h[i];
    }
    int x,y;
    for(int i=0;i<m;++i)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);

    }
    int c=0,k=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<(int)v[i].size();++j)
        {
            if(h[i]>h[v[i][j]])
            {
                k++;
                //cout<<i<<endl;
                //cout<<h[i]<<" "<<v[i][j]<<endl;
            }
        }
        if(k==v[i].size())
        {
            c++;
           // cout<<i<<endl;
        }
        k=0;
    }
    cout<<c<<"\n";
    return 0;
}

Measured memory_bytes: 9132
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
for i in range(n):
    if B[i] >= A[i]:
        ans += A[i]
        B[i] -= A[i]
        if B[i] >= A[i+1]:
            ans += A[i+1]
            A[i+1] = 0
        else:
            ans += B[i]
            A[i+1] -= B[i]
    else:
        ans += B[i]

print(ans)

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

int main(){
  int N,X;cin>>N>>X;
  int m[N];
  int sum=0;
  for(int i=0;i<N;i++){
    cin>>m[i];
    sum+=m[i];
  }
  int min=*min_element(m,m+N);
  cout<<N+(X-sum)/min<<endl;
}
  
        

Measured memory_bytes: 256
#include<stdio.h>
 
int main(void){
  int i;
  int n;
  int m;
  int a[10000];
  scanf("%d%d",&n, &m);
  for(i = 0; i < m; i++){
    scanf("%d", &a[i]);
    n -= a[i];
  }
  if (n < -1)
    n=-1;
  printf("%d",n);
}

Measured memory_bytes: 1768
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ul=unsigned long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

void solve(){
    int n;
    cin>>n;
    vector<ul> a(n);
    set<ul> base;
    for(auto&i:a) cin>>i;
    string s;
    cin>>s;
    ifr(i,n){
        for_each(base.rbegin(),base.rend(),[&](auto&v){
            chmin(a[i],a[i]^v);
        });
        if(a[i]){
            if(s[i]=='0') base.insert(a[i]);
            else{
                cout<<1<<'\n';
                return;
            }
        }
    }
    cout<<0<<'\n';
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    fr(i,t) solve();
}


Measured memory_bytes: 3576
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#define fi first
#define se second
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=10000009;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };
int main() {
	double x1,y1,x2,y2,x3,y3,px,py,r;
	double a1,a2,a3,a4;
 	int n,count=0;
 	cin>>n;
	while(true){
		if(count==n) break;
		cin>>x1>>y1>>x2>>y2>>x3>>y3;
		a1=(y1-y3)*(y1*y1-y2*y2+x1*x1-x2*x2)-(y1-y2)*(y1*y1-y3*y3+x1*x1-x3*x3);
		a2=(y1-y3)*(x1-x2)-(y1-y2)*(x1-x3);
		a2*=2.0;
		a3=(x1-x3)*(x1*x1-x2*x2+y1*y1-y2*y2)-(x1-x2)*(x1*x1-x3*x3+y1*y1-y3*y3);
		a4=(x1-x3)*(y1-y2)-(x1-x2)*(y1-y3);
		a4*=2.0;
		px=a1/a2;
		py=a3/a4;
		r=(px-x1)*(px-x1)+(py-y1)*(py-y1);
		r=pow(r,0.5);
		printf("%.3lf %.3lf %.3lf\n",px,py,r);
		count++;
	}
}

Measured memory_bytes: 3344
# -*- coding: utf-8 -*-
import sys
def solve(lines):
    N,K = map(int, lines.pop(0).split(' '))
    S = lines.pop(0)
    print(S[:K-1] + S[K-1].lower() + S[K:])
#contents = '''\
#3 1
#CAB\
#'''
#lines = contents.split('\n')

# 2. use stdin

lines = [x.strip() for x in sys.stdin.readlines()]

#
# solve !!
#
solve(lines)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#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;
typedef long long ll;
typedef pair<ll, ll> P;

const char wall = '#';
vector<vector<char>> fields;
vector<vector<bool>> used;
vector<vector<ll>> dist;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};

vector<ll> A;
// vectorのリサイズ
// A.resize(N);

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return b/gcd(a,b)*b;}

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

  ll n;
  cin >> n;
  vector<ll> a(n), b(n), c(n-1);
  rep(i, n) {
    cin >> a[i];
    a[i]--;
  }
  rep(i, n) {
    cin >> b[i];
  }
  rep(i, n-1) {
    cin >> c[i];
  }
  ll ans = 0;
  rep(i, n) {
    ans += b[a[i]];
    if (i > 0 && a[i]-a[i-1] == 1) {
      ans += c[a[i-1]];
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	void run(){
		Scanner s = new Scanner(System.in);
		int sec  = s.nextInt();
	    int m = 0;
	    int h = 0;
	    m= sec / 60;
	    sec = sec - m * 60;
	    h = m / 60;
	    m = m - h * 60;
	    System.out.println(h + ":" + m + ":" + sec);
	}
	public static void main(String[] args) {
		
		new Main().run();
		
	}
}

Measured memory_bytes: 26356
N = int(input())
ans = [0]*(N+1)
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            tmp = x*x+y*y+z*z+x*y+y*z+z*x
            if 1 <= tmp <= N:
                ans[tmp] += 1
for i in range(1,N+1):
    print(ans[i])

Measured memory_bytes: 74128
#include <iostream>//cout<<right で右揃え
#include <iomanip>//cout<<setw(数字) で空白による桁揃え
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <cstdlib>//abs()で整数絶対値
#include <cmath>//abs()かfabs()で少数絶対値
#include <functional>//sort第三引数greater<型名>()で降順
#include <map>

using namespace std;
using ll = long long int;

int main(){
    ll A,V;cin>>A>>V;
    ll B,W;cin>>B>>W;
    ll T;cin>>T;
    ll dis_a = V*T;
    ll dis_b = W*T; 
    if(abs(A-B)<=dis_a-dis_b){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 3636
//15:53-17:33
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define mod 1000000007
ll modpow(ll x,ll n)
{
	ll res=1;
	while(n>0)
	{
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll F[300005],R[300005];
void make(){
	F[0] = 1;
	for(int i=1;i<300005;i++) F[i] = F[i-1]*i%mod;
	for(int i=0;i<300005;i++) R[i] = modpow(F[i],mod-2);
}
int n,a[100005],pos[100005];
ll C(int a,int b){ return F[a]*R[b]%mod*R[a-b]%mod;}
int main(){
	cin >> n;
	int x;
	for(int i=1;i<=n+1;i++){
		cin >> a[i];
		if(!pos[a[i]]) pos[a[i]] = i;
		else{
			x = i+1-pos[a[i]];
		}
	}
	make();
	for(int k=1;k<=n+1;k++){
		ll ret = 0;
		//0
		if(n-1 >= k) ret += C(n-1,k);
		//1
		if(n-1 >= k-1) ret += 2LL*C(n-1,k-1);
		if(n+1-x >= k-1) ret -= C(n+1-x,k-1);
		//2
		if(n-1 >= k-2 && k != 1) ret += C(n-1,k-2);
		ret = (ret%mod+mod)%mod;
		cout << ret << endl;
	}
}

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

const int MAX = 200;

int N,M;
int data[MAX];

void shuffle(){
  int tmp[MAX];
  for(int i = 0 ; i < 2*N ; i++)tmp[i] = data[i];
  for(int i = 0 ; i < 2*N ; i++){
    int now = i/2;
    if(i%2)data[i] = tmp[N+now];
    else  data[i] = tmp[now];
  }
}

void cut(int k){
  vector<int>v1,v2;
  for(int i = 0 ; i < k ; i++)v1.push_back(data[i]);
  for(int i = k ; i < 2*N ; i++)v2.push_back(data[i]);
  for(int i = 0 ; i < v2.size() ; i++)data[i] = v2[i];
  for(int i = 0 ; i < v1.size() ; i++)data[v2.size() + i] = v1[i];
}

void solve(){
  for(int i = 0 ; i < 2*N ; i++)data[i] = i+1;
  cin >> M;
  for(int i = 0 ; i < M ; i++){
    int k;
    cin >> k;
    if(k == 0)shuffle();
    else cut(k); 
  }
  
  for(int i = 0 ; i < 2*N ; i++){
    cout << data[i] << endl;
  }

}

int main(){
  cin >> N;
  solve();
  return 0;
}

Measured memory_bytes: 1216
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using ull = unsigned long long;
#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1);
const double EPS = 1e-10;
const ll MOD = 1e9+7;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main(){
  int n;
  cin >> n;
  vvi a(n);
  int q;
  cin >> q;
  REP(i,q){
    int b,t;
    cin >> b >> t;
    if(b==0){
      int x;
      cin >> x;
      a[t].eb(x);
    }else if(b==1){
      if(!a[t].empty()){
        cout << a[t].back() << endl;
      }
    }else{
      if(!a[t].empty()){
        a[t].pop_back();
      }
    }
  }
}



Measured memory_bytes: 4928
#AGC019-B Reverse and Compare
"""
全通りのスワップから、重複する要素を引くことで求まる。
(解説では、この逆で貪欲に重複しない要素を数え上げる解法だが、本質的には同じ)

1.Ai==Ajとなる添字を選んだとき、その結果は
A[i+1:j]の結果と等しくなるのでこれを省く。

2.Ai!=Ajとなる添字を選んだとき、必ずそれと重複するようなスワップの方法、また
スワップをしなかった場合とは異なるものになる。

よって、答えは全通りからi<jとなるAi,Ajに対して、Ai==Ajの個数を引いた数になる。
つまり、文字列の長さをnとしたとき、まず全通りは
ans = nC2
で表され、
ここからi<jとなるi,jにおいて、Ai==Ajとなる文だけ引く。
このとき、Kという事前に準備した配列を用いているが、
各アルファベットの出現回数について、一括で重複回数を求められるようにしてある。
"""
import sys
from collections import defaultdict
dic1 = defaultdict(int)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
s = readline().rstrip().decode('utf-8')
n = len(s)

#二項係数(modなし) O(k)
def large_conbination(n,k): #no mod. return nCk.
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
    res2 = 1
    for i in range(1,k+1):
        res2*= i
    return res1//res2

ans = large_conbination(n,2)

for i in s:
    dic1[i] += 1

K = [0]
for i in range(2*(10**5)):
    K.append(K[-1]+(i+1))

for i in dic1.values():
    if i < 2:
        continue
    ans -= K[i-1]

print(ans+1)


Measured memory_bytes: 54600
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>

using namespace std;

#define ll long long int

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n,m;
    cin >> n >> m;

    vector<ll> sum(m+1,0);

    for(int i = 0; i < n; i++){
        ll t;
        cin >> t;
        for(int j = 0; j < t; j++){
            ll a;
            cin >> a;
            sum[a]++;
        }
    }

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

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

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

typedef long long ll;
const ll MOD = 1e9 + 7;
const ll inf = 1LL<<60;
const double eps = 1e-9;

int main()
{
    int N, M, ac = 0, wa = 0;
    cin >> N >> M;
    vector <int> p(M);
    vector <string> s(M);
    vector <int> tmp(N, 0), tmp2(N, 0);

    for (int i = 0; i < M; i++) {
        cin >> p[i] >> s[i];
        p[i]--;
        if (tmp[p[i]] == 0 && s[i] == "AC") {
            ac++;
            tmp[p[i]] = 1;
            wa += tmp2[p[i]];
        }
        if (s[i] == "WA") tmp2[p[i]]++;
    }
    cout << ac << " "  << wa << endl;
    return 0;
}



Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};



int main(){
    LL n;cin >> n;
    LL x,d;cin >> x >> d;
    if(x==0&&d==0){
        cout << 1 << endl;
        return 0;
    }
    if(d==0){
        cout << n + 1 << endl;
        return 0;
    }
    else if(x==0){
        cout << n * (n - 1) / 2 + 1 %mod << endl;
        return 0;
    }
    if(x*d>=0) x=abs(x),d=abs(d);
    else if(d<0) d=-d,x=-x;
    vector<LL> c(n+1,0),fc(n+1,0);
    for (int i = n-1; i >= 0; i--) {
        c[i] = c[i+1] + i;
    }
    for (int i = 0; i < n; i++) {
        fc[i+1] = fc[i] + i;
    }
    map<LL,vector<P>> ma;
    for (LL i = 0; i <= n; i++) {
        LL p = i * x;
        LL q = p / d;
        LL a = (p%d + d) %d;
        ma[a].pb(mp(q+fc[i],q+c[n-i]));
    }
    LL ans = 0;
    for(auto m:ma){
        sort(ALL(m.sc));
        ans += m.sc[0].sc - m.sc[0].fs + 1;
        LL af = m.sc[0].sc;
        for (int i = 0; i < m.sc.size(); i++) {
            if(m.sc[i].sc <= af) continue;
            else if(m.sc[i].fs <= af){
                ans += m.sc[i].sc - af;
            }
            else{
                ans += m.sc[i].sc - m.sc[i].fs + 1;
            }
            af = m.sc[i].sc; 
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 25216
N=input()
S=input()

A="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
B={}
for i in range(len(A)):
    B[A[i]]=i
#print(B)
C=[]
for i in range(len(S)):
    C.append((B[S[i]]+int(N))%26)

#print(C)
D={}
for i in range(len(A)):
    D[i]=A[i]
#print(D)
E=[]
for i in range(len(C)):
    E.append(D[C[i]])



muramatu =''

for x in E:
    muramatu += x

print(muramatu)













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

const int MAXN=1005;
const int MAXV=MAXN*(MAXN-1)/2;
vector<int> to[MAXV];
int id[MAXN][MAXN];
int toId(int i,int j){
  if(i>j)swap(i,j);
  return id[i][j];
}

bool visited[MAXV];
bool calculated[MAXV];
int dp[MAXV];
int dfs(int v){
  if (visited[v]) {
    if (!calculated[v])return -1;
    return dp[v];
  }
  visited[v]=true;
  dp[v]=1;
  for (int u: to[v]){
    int res=dfs(u);
    if (res==-1)return -1;
    dp[v]=max(dp[v],res+1);
  }
  calculated[v]=true;
  return dp[v];
}
  
int main(){
  int n;
  cin>>n;
  vector<vector<int>> a(n,vector<int>(n-1));
  rep(i,n){
    rep(j,n-1){
      cin>>a[i][j];
      a[i][j]--;
    }
  }
  int V=0;
  rep(i,n)rep(j,n){
    if (i<j){
      id[i][j]=V++;
    }
  }
  rep(i,n){
    rep(j,n-1){
      a[i][j]=toId(i,a[i][j]);
    }
    rep(j,n-2){
      to[a[i][j]].push_back(a[i][j+1]);
    }
  }
  int ans=0;
  rep(i,V){
    int res=dfs(i);
    if (res==-1){
      puts("-1");
      return 0;
    }
    ans=max(ans,dfs(i));
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 38528
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

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

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
  int N;
  while(cin>>N && N){
    vector<int> l(N);
    REP(i, N) cin>>l[i];
    int MAP = (1<<8) - 1;
    int as, aa, ac;
    double ent = 1e32;
    REP(S, 16)REP(A, 16)REP(C, 16){
      vector<int> R(N + 1);
      R[0] = S;
      REP(i, N){
        R[i + 1] = (A * R[i] + C) & MAP;
      }
      REP(i, N){
        R[i + 1] = (R[i + 1] + l[i]) & MAP;
      }
      double cnt[256] = {};
      REP(i, N) cnt[R[i + 1]] += 1.0;
      double e = 0;
      REP(i, 256)if(cnt[i] != 0){
        double c = cnt[i];
        e += -c * log(c/N);
        if(!(e + EPS < ent)) goto END;
      }
      ent = e;
      as = S, aa = A, ac = C;
END:;
    }
    printf("%d %d %d\n", as, aa, ac);
  }
  return 0;
}

Measured memory_bytes: 1220
#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;
  cin >> s;
  string a = s.substr(0, 4);
  string b = s.substr(4, 8);
  cout << a << " " << b << endl;
  return 0;
}

Measured memory_bytes: 3596