akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int main()
{
	string a,b,c;
	cin >> a >> b >> c;
	
	if(a[a.size()-1] == b[0] && b[b.size() - 1] == c[0])
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	
	return 0;
}

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

using namespace std;

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

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

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1000000007;

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//myfuncs
//素数判定
template<class T> inline T isPrime(T x) {
	bool ret = true;
	if (x < 2) {
		ret = false;
	}
	for (LL i = 2; i <= sqrt(x); i++) {
		if (x%i == 0) {
			ret = false;
		}
	}
	return ret;
}

//Union FInd
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//main code

int main(int argc, char const* argv[])
{
	int n,m;
	cin >> n >> m;
	LL ans = ((n-m) * 100 + m * 1900) * (1 << m);
	cout << ans << endl;
	return 0;
}


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

int main() {
    long long q, h, s, d, n;
    cin >> q >> h >> s >> d >> n;
    cout << min({4 * q * n, 2 * h * n, s * n, n / 2 * d + min({4 * q, 2 * h, s}) * (n % 2)});
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<map>
#include<sstream>
#include<cctype>
using namespace std;
typedef string::const_iterator Cursol;
map < string , int > d;
bool ok;
int stoi(string s) {
  int v;
  stringstream ss(s);
  ss>>v;
  return v;
}
int Num(Cursol &c){
  int ret;
  string s;
  s += *c++;
  if(isdigit(*c)) s += *c++;
  return stoi(s);
}
int Atom(Cursol &c){
  int ret;
  string s;
  s += *c++;
  if(islower(*c)) s += *c++;
  ret = d[s];
  if(ret == 0) ok = false;
  return ret;
}
int Molecule(Cursol &c){
  if( *c == '\0' || *c == ')') return 0; 
  int ret = 0;
  if(*c == '('){
    ret = Molecule(++c) * Num(++c);
  }else if(isupper(*c)){
    ret = Atom(c);
    if(isdigit(*c)) ret *= Num(c);
  }
  return ret + Molecule(c);
}
int main(){
  string s;
  while(cin >> s , s != "END_OF_FIRST_PART"){
    cin >> d[s];
  }
  while(cin >> s , s != "0"){
    Cursol c = s.begin();
    ok = true;
    int ret = Molecule(c);
    if(ok) cout << ret << endl;
    else cout << "UNKNOWN" << endl;
  }
}

Measured memory_bytes: 1244
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

int main(){
	vector<long long> inv(100002);
	vector<long long> fact(100002);
	vector<long long> factInv(100002);
	for(int i=0;i<2;i++) inv[i] = fact[i] = factInv[i] = 1;
	for(int i=2;i<=100001;i++){
		inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
		fact[i] = fact[i-1] * i % MOD;
		factInv[i] = factInv[i-1] * inv[i] % MOD;
	}
	auto comb = [&](int n, int r){
		if(n < r) return 0LL;
		return fact[n] * factInv[n-r] % MOD * factInv[r] % MOD;
	};
	int N;
	while(cin >> N){
		vector<int> a(N+1);
		vector<int> c(N+1, 0);
		int d = 0;
		for(auto& t : a){
			cin >> t;
			c[t]++;
			if(c[t] == 2) d = t;
		}
		int cnt = 0, one = 0;
		for(const auto& t : a){
			if(t == d) ++one;
			else if(one%2 == 0) ++cnt;
		}
		cout << N << endl;
		for(int i=2;i<=N+1;i++){
			long long all = comb(N+1, i);
			long long sub = comb(cnt, i-1);
			cout << (all + MOD - sub) % MOD << endl;
		}
	}
}


Measured memory_bytes: 4352
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    X = I()
    ans = X//500*1000
    X -= X//500*500
    ans += X//5*5
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 6796
N = int(input())
A = list(map(int, input().split()))


A2 = [a for a in A if a % 2 == 0]

A35 = [a for a in A2 if not(a%3 == 0 or a%5 == 0)]


if len(A35) == 0:
    print('APPROVED')
else:
    print('DENIED')

Measured memory_bytes: 3060
#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, q;
    while (cin >> n >> q and (n or q)) {

        int d[102];
        fill(d, d+102, 0);

        rep(i, n) {
            int m; cin >> m;
            rep(t, m) { int tt; cin >> tt; d[tt]++; }
        }

        int sum=q-1, day=0;
        for (int i=1; i<=100; ++i) {
            if (d[i] >= q && d[i] > sum) {
                sum = d[i];
                day = i;
            }
        }

        cout << day << endl;

    }
    return 0;

}

Measured memory_bytes: 3028
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};
int n;
int main()
{
  cin >>n;
  vector<int> s;
  int x;
  int ans = 0;
  for(int i = 0;i < n;i++){
    cin >>x;
    s.push_back(x);
  }
  int q;
  cin >>q;
  vector<int> t;
  int y;
  for(int i = 0;i < q;i++){
    cin >>y;
    t.push_back(y);
  }
  int k = s.size();
  int l = t.size();
  sort(t.begin(),t.end());

  for(int i = 0;i <k;i++){
    int search = s[i];
    int left = 0;
    int right =t.size()-1;
    while(left <=right){
      int mid = (left+right)/2;
      if(search >t[mid]){
	left = mid+1;
      }else if(search <t[mid]){
	right = mid-1;
      }else{
	ans++;
	t[mid] = -1;
	sort(t.begin(),t.end());
	break;
      }
    }
  }
  cout <<ans<<endl;
  return 0;
}

Measured memory_bytes: 1324
#include <stdio.h>

int main(void)
{
    int n, i, min, max;
    long long int sum = 0;

    scanf("%d", &n);

    int a = 0;

    for (i = 0; i <= n - 1; i++)
    {
        scanf("%d", &a);

        if (i == 0)
        {
            min = max = a;
        } //min,maxをaと同じ値に初期化
        else if (a >= max)
        {
            max = a;
        } //aがmaxより大きい時、maxにa[i]を代入
        else if (a <= min)
        {
            min = a;
        }         //aがminより小さい時、minにaを代入
        sum += a; //aの合計
    }

    printf("%d %d %lld\n", min, max, sum);


    return 0;
}


Measured memory_bytes: 2112
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ll long long
#define mod 1000000007
#define vi vector<int>
#define vll vector<ll>
#define pb push_back

ll power(int x, unsigned int y){
    ll res = 1;
    while(y > 0){
        if(y & 1) res = res * x;
        y >>= 1;
        x *= x;
    }
    return res;
}

// Check for number of Cases!!
void solve() {
    int n; cin >> n;
    
    int a[n+3], b[n+3], c[n+3];

    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }

    ll dp[n+3][3];

    dp[1][0] = a[1], dp[1][1] = b[1], dp[1][2] = c[1];

    for(int i = 2; i <= n; i++) {
        dp[i][0] = max(dp[i-1][1] + a[i], dp[i-1][2] + a[i]);
        dp[i][1] = max(dp[i-1][0] + b[i], dp[i-1][2] + b[i]);
        dp[i][2] = max(dp[i-1][0] + c[i], dp[i-1][1] + c[i]);
    }

    cout << max({dp[n][0], dp[n][1], dp[n][2]});
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t = 1;
    // cin >> t;
    while(t--) {
      solve();
    }
}

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

using namespace std;

const int N = 1010;
int n, d[2][N];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> d[0][i] >> d[1][i];
  for (int i = 1; i <= n - 2; ++i) {
    bool flag = true;
    for (int j = 0; j < 3; ++j) {
      if (d[0][i+j] != d[1][i+j]) {
        flag = false;
        break;
      }
    }
    if (flag) {
      cout << "Yes" << '\n';
      return 0;
    }
  }
  cout << "No" << '\n';
}

Measured memory_bytes: 3616
x = gets.chomp

# 最終形は T...TS...S になる
s_count = 0
t_count = 0
x.each_char do |c|
  if c == "T"
    if s_count > 0
      # STで相殺
      s_count -= 1
    else
      t_count += 1
    end
  else
    s_count += 1
  end
end

# TとSの個数は同じ
puts t_count * 2


Measured memory_bytes: 14552
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    int mv = INT_MAX, cnt = 0;
    ll ans = 0;
    
    rep(i, n) {
        mv = min(mv, abs(a[i]));
        
        if (a[i] < 0) {
            cnt++;
        }
        
        ans += abs(a[i]);
    }
    
    if (cnt % 2 != 0) {
        ans = ans - 2LL * mv;
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>

using namespace std;

int gcd (int p, int q) {
  if (q == 0) return p;
  return gcd(q, p % q);
}

const int MAX_N = 1e5 + 5;

int arr [MAX_N];

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

  int gc = 0, mx = 0;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    gc = gcd(gc, arr[i]);
    mx = max(mx, arr[i]);
  }

  if (k > mx || k % gc != 0) {
    cout << "IMPOSSIBLE" << endl;
  } else {
    cout << "POSSIBLE" << endl;
  }
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,n) for (int i=0;i<(n);i++)

int main()
{
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep (i,N) {
        cin >> A[i];
    }

    vector<ll> cnt(100005, 0);
    rep (i,N) {
        cnt[A[i]] += 1;
    }
    ll ans = 0;
    rep (i,100000) {
        ans = max(ans, cnt[i] + cnt[i+1] + cnt[i+2]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
/*------------------------- Bism Allah Alruhmin Alrahim -------------------------------*/
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i > -1; i--)
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define vc vector
#define f first
#define s second
#define L size()

#define pb(i) push_back(i)
#define mx(ar, n) (*max_element(ar, ar + n))
#define mn(ar, n) (*min_element(ar, ar + n))

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // ----------------------
    string s;
    cin >> s;
    bool b = true; 
    for (int i = 1; i < 4; i++)
    {
        if(s[i] == s[i-1]){
            b = false;
        }
    }
    if(b){
        cout << "Good" << endl ;
    }
    else{
        cout << "Bad" << endl ;
    }
    
    return 0 ;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int H, W, i, j;

    while(1){
        scanf("%d %d", &H, &W);
        if(H == 0 && W == 0){
            break;
        }

        for(i = 0; i < H; i++){
            for(j = 0; j < W; j++){
                if(i % 2 == 0){
                    if(j % 2 == 0){
                        printf("#");
                    }else{
                        printf(".");
                    }
                }else{
                    if(j % 2 == 0){
                        printf(".");
                    }else{
                        printf("#");
                    }
                }
            }
            printf("\n");
        }
        printf("\n");
    }

    return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
#include <math.h>
#define lli long long int
 
using namespace std;
 
int main(){
    string s,t;
    cin>>s>>t;
  	lli n=s.size();
  lli ct=0;
        for(lli i=0;i<n;i++){
            if(s[i]!=t[i]){
              ct=ct+1;
            }
        }
       cout<<ct<<endl;
}

Measured memory_bytes: 3920
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        long[] A = new long[N];
        for(int n=0;n<N;n++) A[n]=sc.nextInt();
        long[] S = new long[N];
        S[0] = A[0]%M;
        for(int n=1;n<N;n++) S[n]=(S[n-1]+A[n])%M;
        Map<Long,Long> count = new HashMap<>();
        for(int n=0;n<N;n++){
        	count.put(S[n],count.getOrDefault(S[n], 0L)+1);
        }
        
        long ans = 0;
        for(Long a:count.keySet()){
        	ans += count.get(a) * (count.get(a)-1) / 2;
        }
        
        ans += count.getOrDefault(new Long(0), new Long(0));
        System.out.println(ans);
    }
}

Measured memory_bytes: 52660
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
ll inf=1e18+7;

//全ての競技を開催したとき，最も多くの人数Qが参加する競技を中止する．
//順次中止していって，最も最大参加人数が小さかった組み合わせが答え

int main(void){
	ll n,m,a[310][310],top[310]={},stop[310]={},ans=inf;
	cin>>n>>m;
	rep(i,n)rep(j,m)cin>>a[i][j];
	rep(i,m){
		ll c[310]={},max_id=1;
		rep(j,n){
			while(stop[a[j][top[j]]]!=0)top[j]++;//j人目の先頭位置を更新
			c[a[j][top[j]]]++;
		}
		reg(j,1,m){
			if(c[max_id]<c[j])max_id=j;
		}
		ans=min(ans,c[max_id]);
		stop[max_id]=1;//参加人数が最も多い競技を中止
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
//#include <unistd.h>
//#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const ll mod = 1000000007;
const ld pi = 3.14159265358;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}

ll fac[510000], finv[510000], inv[510000];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < 510000; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logN)
ll modpow(ll n,ll m,ll MOD){
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/

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


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    char c;
    cin >>c;
    if(isupper(c))cout << "A" << endl;
    else cout << "a" << endl;
}

Measured memory_bytes: 3640
#include <iostream>
using namespace std;
int main()
{
  int n, k; cin >> n >> k;
  int sum = n * (n - 1) / 2;
  if (k > sum - n + 1)
  {
    cout << -1 << endl;
    return 0;
  }
  int pairs = (n - 1) * (n - 2) / 2;
  int m = n - 1 + pairs - k;
  cout << m << endl;
  int a = 1;
  int b = 2;
  for (int i = 0; i < m; i++)
  {
    cout << a << " " << b << endl;
    b++;
    if (b > n)
    {
      a++;
      b = a + 1;
    }
  }
  return 0;
}

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

bool canimake(int m, int A[], int begin, int end) {
  // cout << "make " << m << " with ";
  // for (int i = begin; i < end; i++) {
  //   cout << A[i] << " ";
  // }
  // cout << endl;
  if (m == 0) {
    return true;
  } else if (m < 0) {
    return false;
  } else {  // m > 0
    for (int i = begin; i < end; i++) {
      if (canimake(m - A[i], A, i + 1, end)) {
        return true;
      }
    }
    return false;
  }
}

int main() {
  int n;
  cin >> n;
  int A[n];
  for (int i = 0; i < n; i++) {
    cin >> A[i];
  }
  // sort(A, A + n);
  // for (int i = 0; i < n; i++) {
  //   cout << A[i] << endl;
  // }

  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int m;
    cin >> m;
    if (canimake(m, A, 0, n)) {
      cout << "yes\n";
    } else {
      cout << "no\n";
    }
  }

  return 0;
}


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

int main(){
    int n;
    string s;
    cin >> n >> s;
    for(int i=0; i<s.size(); i++){
        char c = s[i];
        c = c + n;
        if (int(c) > 0x5A){
            c = c - int(26);
        }
        cout << c;
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <b; i++)
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
#define trace(x) cout<<#x<<"="<<x<<"\n";
#define llp 1000000007
#define mod 1000000007

template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "{";
    typename vector< T > :: const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "[";
    typename set< T > :: const_iterator it;
    for ( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
    os << "[";
    typename map< F , S >::const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]";
}

#define deb(x) cerr << #x << " = " << x << endl;


int main(){
	ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    vl aa(n);
    vl bb(n);
    //memset(aa,0,sizeof(aa));
    REP(i,0,n){
        //deb(i);

        int k;
        cin>>k;
        //deb(k);
        REP(j,0,k){
            ll aaa;
            cin>>aaa;
            //deb("before");
            //deb(aa[i]);
            bb[i]=bb[i]|(1L<<aaa);
            aa[i]=(bb[i]|bb[i]);

           // deb(aaa);
           // cout<<bitset<64>(aaa)<<"\n";
         //   deb("after");
     //       deb(aa[i]);
       //     cout<<bitset<64>(aa[i])<<"\n";
       //
        }
    }
    ll ans=(1L<<40)-1;
    //deb(ans);
    //cout<<bitset<64>(ans)<<"\n";
    REP(i,0,n){
        ans=ans&aa[i];
    }
    //deb(ans);
    //cout<<bitset<64>(ans)<<"\n";
    //deb(aa);

    cout<<__builtin_popcountll(ans)<<"\n";



	return 0;
}

Measured memory_bytes: 256
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

template <typename T>
using vec = vector<T>;

template <typename T>
using vec2 = vector<vector<T>>;

template <typename T>
using vec3 = vector<vector<vector<T>>>;

const Ld pi = M_PI;
const Int MOD = 1000000007;
const Int INF = 1LL << 61;

Int Floor(Int a, Int b) {
    return (a - (a % b)) / b;
}

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

    for (int i = 0; i < 5; i++) {
        int a;
        cin >> a;
        if (a == 0) {
            cout << i + 1 << endl;
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
inline void read(T &x) {
	x = 0;
	T f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
inline void d_read(double &x) {
	x = 0.0;
	int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	if (c == '.'){
		double num = 1.0;
		c = getchar();
		for (; isdigit(c); c = getchar()) x = x + (num /= 10) * (c ^ 48);
	}
	x *= f;
}

template <typename T>
inline void w(T x) {
	if (x > 9) w(x / 10);
	putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x, char c) {
	if (x < 0){
		putchar('-');
		x = -x;
	}
	w(x);
	putchar(c);
}
ll f[10000007];
int main(){
	ll n;
	read(n);
	for (int i = 1; i <= sqrt(n); i ++) {
		f[i * i] ++;
		for (int j = i + 1; j <= n / i; j ++) {
			f[i * j] += 2;
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n; i ++) {
		ans += (ll)(i) * f[i];
	}
	write(ans, '\n');
	return 0;
}


Measured memory_bytes: 81676
def lscan; gets.split.map(&:to_i); end

n,m = lscan
sc = m.times.map{lscan}
0.upto(999) do |x|
  t = x.to_s
  next if t.size != n
  
  if sc.all?{|s,c| t[s-1] == c.to_s}
    p x
    exit
  end
end
p -1

Measured memory_bytes: 1916
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
const int mod = 1000000007;
const int max_n = 200005;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
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;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
}comb(max_n);
int main(){
    ll n,k;cin >> n >>k;
    ll  ans=0;
    rep(i,n+2-k){
        ll p=k+i;
        ll l=(p)*(p-1)/2-1,r=(n+n-p+1)*p/2;
        ans+=r-l;
        ans%=MOD;
    }
    cout <<ans <<endl;
}

Measured memory_bytes: 6212
#include <bits/stdc++.h>
using namespace std;
template<class T> bool chmax(T& a,T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T& a,T b) { if (a > b) { a = b; return true; } return false; }

int main() {
    int n;
    cin >> n;
    vector<vector<int>> ans(n + 1, vector<int>(n + 1, -1));
    
    auto solve = [&] (int i) -> bool {
        const int step = (1 << i);
        int loop = (1 << (i - 1));
        int s = 1, t = 1 + (1 << (i - 1));
        if (n < t) return false;
        while (loop--) {
            if (n < t) break;
            vector<int> v1, v2;
            for (int v = s; v <= n; v += step) v1.push_back(v);
            for (int v = t; v <= n; v += step) v2.push_back(v);
            for (const int &a : v1) for (const int &b : v2) {
                if (a <= n and b <= n) ans[a][b] = ans[b][a] = i;
            }
            s++; t++;
        }
        return true;
    };
    
    int lv = 1;
    while (solve(lv)) lv++;
    
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            assert(ans[i][j] != -1);
            cout << ans[i][j] << (j == n ? '\n' : ' ');
        }
    }
    
    return 0;
}

Measured memory_bytes: 1536
#include <stdio.h>

int main(void)
{
	int n,c,i,j,a[10]={0};
	while(1)
	{
	for(i=0;i<10;i++){
	a[i]=0;
	}
	scanf("%d",&n);
	if(n==0)
	break;
		for(i=0;i<n;i++)
		{
			scanf("%d",&c);
			a[c]+=1;
		}
	for(i=0;i<10;i++)
	{
	if(a[i]==0)
	printf("_\n");
	else{
		for(j=0;j<a[i];j++)
		{
			printf("*");
		}
		printf("\n");
	}
	}
	}
return 0;
}


Measured memory_bytes: 2024
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long a,b,c,ans;
int main()
{
	scanf("%lld%lld%lld",&a,&b,&c);
	ans=a*b;
	if(a%2==0||b%2==0||c%2==0)
		ans=0;
	ans=min(ans,min(a*b,min(b*c,a*c)));
	printf("%lld",ans);
}

Measured memory_bytes: 128
use std::str::FromStr;
use std::fmt::Debug;

fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let line: Vec<u64> = read_as_vec();

    let (k, a, b) = (line[0], line[1], line[2]);

    //hit, hit and hit
    if a +1 >= b || a > k-1{
        //println!("just hit");
        println!("{}", 1 + k);
        return
    }else{
        let mut biskets: u64 = a;
        let rest_k = k - (a-1);
        biskets += rest_k/2 *(b-a);
        if rest_k%2 == 1{
            println!("{}", biskets+1);
        }else{
            println!("{}", biskets);
        }
    }
}

Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};


///////////////////////////
double pi = acos(-1);


double ang(double a, double b) {
	double r = acos(a / sqrt(a * a + b * b));

	
	if (b >= 0) { return r; }
	if (b < 0) { return 2*pi - r; }
	
}




int main() {
	
	cout << fixed << setprecision(10);
	ll N;
	cin >> N;

	vector<double> x(N + 1), y(N + 1);
	repn(i, N) cin >> x[i] >> y[i];

	repn(i, N) {
		vector<double> an(N);

		repn(j, N-1) {
			if (j < i) { an[j] = ang(x[j] - x[i], y[j] - y[i]); }
			else { an[j] = ang(x[j+1] - x[i], y[j+1] - y[i]); }
			//cout << i << j << an[j] << endl;

		}

		sort(++an.begin(), an.end());

		double dif = an[1] - an[N - 1] + 2.0 * pi;

		repn(j, N - 2) {
			dif = max(dif, an[j + 1] - an[j]);
		}

		//cout << dif << endl;

		double ans = max(dif - pi, 0.0) / 2.0 / pi;

		cout << ans<<endl;
	}

	
	system("PAUSE");
}


Measured memory_bytes: 888
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
using namespace std;

int main(){
    int n, m, x;
    cin >> n >> m >> x;
    int A[101] = {0};
    for(int i=0; i < m ; i++){
        int temp = 0;
        cin >> temp;
        A[temp] = 1;
    }

    int head = 0;
    for(int i=0; i < x; i++) head += A[i];
    int tail = 0;
    for(int j=x; j < n; j++) tail += A[j];

    if(head < tail) cout << head << endl;
    else cout << tail << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<string>
#include<cmath>
using namespace std;
int main(){
	string s;
	cin >> s;
	for(int i=0;i<4;i++){
		cout << s[i];
	}
	cout << " " ;
	for(int i=4;i<12;i++){
		cout << s[i];
	}
	cout << endl;
	
	return 0;	
};

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
  int n,i,j;
  cin >> n;
  for(i=1;i<=9;i++){
    for(j=1;j<=9;j++){
      if(i*j==n){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 3620
//Zory-2019
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// typedef __int128 ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define bin(x) (1ll<<(x))
#define fo(i,l,r) for(int i=(l),I=(r);i<=I;i++)
#define fd(i,r,l) for(int i=(r),I=(l);i>=I;i--)
#define Debug printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define debug(x) cerr<<#x<<'='<<x<<endl
#define mem(x,val) memset(x,val,sizeof x)
namespace mine
{
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num){if(num<0) putchar('-'),num=-num;if(num>=10) write(num/10);putchar('0'+num%10);}
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    template<typename T> void chmax(T &x,const T y) {x=(x>y?x:y);}
    template<typename T> void chmin(T &x,const T y) {x=(x<y?x:y);}
    ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
    bool IN(ll x,ll l,ll r){return l<=x and x<=r;}

    const int INF=0x3f3f3f3f;
    const int MOD=1e9;
    int mm(const int x){return x>=MOD?x-MOD:x;}
    template<typename T> void add(T &x,const int &y){x=(x+y>=MOD?x+y-MOD:x+y);}
    ll qpower(ll x,ll e,int mod=MOD){ll ans=1;while(e){if(e&1)ans=ans*x%mod;x=x*x%mod;e>>=1;}return ans;}
    ll invm(ll x){return qpower(x,MOD-2);}
    const int N=190+10;

    int cnt[N][N];char str[N];
    inline bool same(int x1,int x2,int y1,int y2){
        int tmp=cnt[x2][y2]-cnt[x1-1][y2]-cnt[x2][y1-1]+cnt[x1-1][y1-1];
        return tmp==(x2-x1+1)*(y2-y1+1) or !tmp;
    }
    short dp[21][N][N][N];
    void main()
	{
        int n=qread(),m=qread();
        fo(i,1,n){scanf("%s",str+1);fo(j,1,m) cnt[i][j]=cnt[i][j-1]+(str[j]=='#');}
        fo(j,1,m) fo(i,1,n) cnt[i][j]+=cnt[i-1][j];

        fo(l,1,m) fo(i,1,n+1) fo(r,l,m) fo(ned,0,20) dp[ned][i][l][r]=i-1;
        fd(i,n,1) fo(l,1,m) fo(r,l,m)
        {
            if(!same(i,i,l,r)) dp[0][i][l][r]=i-1;
            else if(same(i,i+1,l,l)) dp[0][i][l][r]=dp[0][i+1][l][r];
            else dp[0][i][l][r]=i;
        }
        fo(ned,1,20) fo(i,1,n) fo(l,1,m)
        {
            int pos=l-1;
            fo(r,l,m)
            {
                chmax(dp[ned][i][l][r],dp[ned-1][dp[ned-1][i][l][r]+1][l][r]);
                while(pos+1<r and dp[ned-1][i][l][pos+1]>=dp[ned-1][i][pos+2][r]) pos++;
                // write2(pos);
                if(l<=pos)  chmax(dp[ned][i][l][r],dp[ned-1][i][pos+1][r]);
                if(pos+1<r) chmax(dp[ned][i][l][r],dp[ned-1][i][l][pos+1]);
            }
        }
        int ans=0;while(dp[ans][1][1][m]<n) ans++;write(ans);
	}
};//(ans+MOD)%MOD
signed main()
{
    srand(time(0));
    mine::main();
}


Measured memory_bytes: 327936
n,m = map(int, input().split())
x = [int(i) for i in input().split()]
x.sort()
x2 = []
for i in range(len(x)-1):
  x2.append(x[i+1] - x[i])
x2.sort()
if n < m:
  print(sum(x2[:len(x2) - n + 1]))
else:
  print('0')

Measured memory_bytes: 13832
di = [list(input().split(' ')) for _ in range(int(input()))]
a = list('NNNNWNNNWNNNENNNENNNWNNN')
y = 0
for n in range(len(di)):
    for j in di[n+1:]:
        dice = j
        x = 0
        aa,bb,cc,dd,ee,ff  = di[n]
        for i in a:
            if i == 'W':
                dice = [dice[2],dice[1],dice[5],dice[0],dice[4],dice[3]]
            elif i == 'S':
                dice = [dice[4],dice[0],dice[2],dice[3],dice[5],dice[1]]
            elif i == 'N':
                dice = [dice[1],dice[5],dice[2],dice[3],dice[0],dice[4]]
            elif i == 'E':
                dice = [dice[3],dice[1],dice[0],dice[5],dice[4],dice[2]]
            if dice[0] == aa and dice[1] == bb and dice[2] == cc and dice[3] == dd and dice[4] == ee and dice[5] == ff:
                x = x + 1
        y = y + 1 if x > 0 else y
kome = 'No' if y > 0 else 'Yes'
print(kome)


Measured memory_bytes: 5616
N = int(input())

i = -1
lst = []
k = 1
while k == 1:
    i += 1
    j = i**5
    lst.append(j)
    for l, n in enumerate(lst):
        if j - n == N:
            print(i,l)
            k = 0
            break
        if j + n == N:
            print(i,-l)
            k=0
            break


Measured memory_bytes: 9020
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;
int par[100010];

int find(int x){
  if(par[x]==x) return x;
  else return par[x] = find(par[x]);
}
bool same(int x,int y){
  return find(x)==find(y);
}

int n,q;
int par2[100010];
pair<char,int> query[100010];
int main(){ _;
  while(cin>>n>>q,n|q){
    par[1]=1;
    par2[1]=1;
    REP(i,n-1) cin>>par2[i+2],par[i+2]=par2[i+2];
    for(int i=q-1;i>=0;i--){
      cin>>query[i].first>>query[i].second;
      if(query[i].first=='M'){
	if(par[query[i].second]==query[i].second)
	  query[i].first='-';
	par[query[i].second]=query[i].second;
      }
    }
    long long sum=0;
    REP(i,q){
      if(query[i].first=='M') par[query[i].second]=par2[query[i].second];
      else if(query[i].first=='Q') sum+=find(query[i].second);
    }
    cout<<sum<<endl;
  }
}

Measured memory_bytes: 4840
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
double x,ans,t;
int n;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    priority_queue<double,vector<double>,greater<double>> q;
    cin >> n;
    for(int i = 0;i < n; ++i){
        cin >> x;
        q.push(x);
    }
    while(q.size() >= 2){
        x = q.top();
        q.pop();
        t = q.top();
        q.pop();
        q.push((x+t)/2.0);
    }
    cout << q.top();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main (){
 int X;
 cin >> X;
  int Y;
  cin >>Y;
 	int Z = (4*X-Y);
	int z = (2*X-Y);
  if (Y%2 ==0 && Z >= 0 && z<=0){cout <<"Yes" <<endl;}
  else cout << "No" <<endl;

}



Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include<limits.h>
#include<stdio.h>
#include<cstring>
#include<string>
using namespace  std;
typedef long long ll;
typedef long double ld;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
#define fi first
#define se second
#define rsz(a,n) a.resize(n)
#define test(t) ll t;cin>>t;while(t--)
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define fillv(a,k) memset(a,k,sizeof(a))
#define leadzero(a) __builtin_clz(a) //count leading zeros
#define trailzero(a) __builtin_ctz(a) //count trailing zeros
#define bitcount(a) __builtin_popcount(a) // count set bits (add ll)
#define ln cout<<"\n"
// #define sp cout<<" "
#define spaceprint(a,i,s,n) {forsn(i,s,n) { cout<<a[i]; sp;}}
#define lineprint(a,i,s,n) {forsn(i,s,n) {cout<<a[i]; ln;}}
#define maxe(a) *max_element(a.begin(),a.end())
#define maxi(a) max_element(a.begin(),a.end())-a.begin()
#define mine(a) *min_element(a.begin(),a.end())
#define mini(a) min_element(a.begin(),a.end())-a.begin()
#define all(c) c.begin(),c.end()
#define trav(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define present(container, element) (container.find(element) != container.end())
#define cpresent(container, element)  (find(all(container),element) != container.end())// check the presence of element
//copy(from_begin, from_end, to_begin); copy function
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<string> vs;
typedef vector<int> v32;
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<p64> vp64;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
typedef map<ll,ll> m64;
const int LIM = 1e5+5, MOD =  1e9;
#define sumv(v) accumulate(all(v),ll(0))
#define productv(v) accumulate(all(v), ll(1), multiplies< ll >())
ll gcd(ll a, ll b) { if(b == 0) return a; return gcd(b, a % b); }
ll mod=1e9+7;
ll fastpowMOD(ll a, ll p,ll MOD){ if(p==0) return 1; ll z = fastpowMOD(a,p/2,MOD); z = (z*z)%MOD; if(p%2) z = (z*a)%MOD; return z; }

ll fact[200004];
void compfact ()
{
	fact[0]=1;
	for (ll i=1;i<=200002;i++)
		fact[i]=(fact[i-1]%mod*i%mod)%mod;
}
vp64 v;
ll dp[2002][2002];

void solve (ll ind,ll l , ll r)
{
	if (dp[l][r]!=-1)
		return;
	else if (l>r)
		return;
	else if (l==r)
	{
		dp[l][r]=v[ind].fi*abs(v[ind].se-l);
	}
	else
	{
		solve(ind+1,l+1,r);
		solve(ind+1,l,r-1);
		dp[l][r]=max(dp[l][r],dp[l+1][r]+v[ind].fi*abs(v[ind].se-l));
		dp[l][r]=max(dp[l][r],dp[l][r-1]+v[ind].fi*abs(v[ind].se-r));

	}

}
int main()
{
	fast;
	ll n;
	cin>>n;
	for (ll i=1;i<=n;i++)
	{
		ll x;
		cin>>x;
		v.pb({x,i});
	}
	for (ll i=1;i<=n;i++)
	{
		for (ll j=1;j<=n;j++)

		{
			dp[i][j]=-1;
		}
	}
	sort(all(v));
	reverse(all(v));
	// for (auto x:v)
	// 	cout<<x.fi<<" "<<x.se<<endl;
	solve(0,1,n);
	cout<<dp[1][n];

}

Measured memory_bytes: 35196
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
const long double PI=3.14159265358979323846264338327950;
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  set<int> S;
  rep(i,n){
    int tmp;
    cin>>tmp;
    S.insert(tmp);
  }
  cout<<S.size()<<'\n';
  return(0);
}

Measured memory_bytes: 3652
import java.util.*;
public class Main {// Main
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);


		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int q = a/n;
		int q2 = b/n;
		if(q2>q || a%n==0) {
			System.out.println("OK");
		}else {
			System.out.println("NG");
		}
		
}
}

Measured memory_bytes: 35752
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
#define rep(i, n) for(int i=0;i<(int)n;i++)
#define PI acos(-1)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
ll mod=1e9+7;




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

   vector<int> east(n+1);
   east[0]=0;
    rep(i,n){
        if(s[i]=='E') east[i+1]++;
    }
    rep(i,n){
        east[i+1] += east[i];
    }
    ll ans=1e12;
    for(ll i=1;i<=n;i++){
        ans=min(ans, i-1-east[i-1]+east[n]-east[i]);
    }
    cout<<ans<<endl;
    

    return 0;
}


Measured memory_bytes: 4808
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MOD 1000000007
#define INF 800000000
#define MAX 1000

int main(){
  ll N;
  cin>>N;
  bool flag=false;
  for(int h=1;h<=3500;h++){
    for(int n=1;n<=3500;n++){
      ll x=h*n*N;
      ll y=4*h*n-N*(n+h);
      if(y==0){
        continue;
      }
      if(x%y==0&&x/y>0){
        cout<<h<<" "<<n<<" "<<x/y<<endl;
        flag=true;
        break;
      }
    }
    if(flag){
      break;
    }
  }
}


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

using namespace std;

template <class T>
using lim = numeric_limits<T>;

typedef long long ll;
typedef long double ld;

const int maxN = 50;

ll combi[maxN+1][maxN+1];

void computeCombi(){
	memset(combi, 0, sizeof combi);
	
	for (int i = 0; i <= maxN; i++){
		combi[i][0] = 1;
	}
	
	for (int i = 1; i <= maxN; i++){
		for (int j = 1; j <= maxN; j++){
			combi[i][j] = combi[i-1][j-1] + combi[i-1][j];
		}
	}
}


int computed[maxN*maxN+1];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	computeCombi();
	
	int n, a, b;
	cin >> n >> a >> b;
	ll v[n];
	
	for (int i = 0; i < n; i++){
		cin >> v[i];
	}
	
	sort(v, v+n, greater<ll>());
	
	ll totalA = v[0];
	vector<ll> unique;
	unique.push_back(v[0]);
	
	unordered_map<int, int> countInA;
	countInA[v[0]] = 1;
	for (int i = 1; i < a; i++){
		totalA += v[i];
		if (v[i]!=v[i-1]) unique.push_back(v[i]);
		countInA[v[i]]++;
	}
	
	ld mean = (ld) totalA / a;
	
	int countMax = 0;
	unordered_map<int, int> counters;
	for (int i = 0; i < n; i++){
		if (v[0]==v[i]) countMax++;
		counters[v[i]]++;
	}

	ll ways;
	
	int size = unique.size();
	if (size==1){	
		ways = 0;
		for (int i = a; i <= min(countMax,b); i++){
			ways += combi[countMax][i];
		}
	}
	else {
		ways = 1;
		for (ll num : unique){
			ways *= combi[counters[num]][countInA[num]];
		}
	}
	
	cout << fixed << setprecision(6) << mean << endl;
	cout << ways << endl;
}


Measured memory_bytes: 256