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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))
#define minvec(v) *min_element(all(v))
#define maxvec(v) *max_element(all(v))
#define sumvec(v) accumulate(all(v),0LL)
#define mapmin(v) v.rbegin()->first
#define mapmax(v) v.begin()->first
#define pb push_back
#define pf push_front
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK cerr<<"OK\n"
#define OK1 cerr<<"OK1\n"
#define OK2 cerr<<"OK2\n"
#define SIZE(s) (int)s.size()
#define INF ((1LL<<62)-(1LL<<31))
#define zero(x,n) setw(x) << setfill('0') << n
#define endl '\n'

typedef long long ll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;

const double pi = acos(-1.0);
const ll mod=1000000007;
const ll mod2=998244353;

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << " ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

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

void YES(bool b) {cout << ((b)?"YES\n":"NO\n");}
void Yes(bool b) {cout << ((b)?"Yes\n":"No\n");}
void yes(bool b) {cout << ((b)?"yes\n":"no\n");}
void Yay(bool b) {cout << ((b)?"Yay!\n":":(\n");}

template<typename T>
void VIN(vector<T> &v,int n){for(int i=0;i<n;i++) cin >> v[i];}

template<typename T>
void VOUT(vector<T> &v){
    ll n=(int)v.size();
    for(int i=0;i<n;i++) cout << v[i] << (i==n-1?"\n":" ");
}

template<typename T>
void VOUTL(vector<T> &v){
    ll n=(int)v.size();
    for(int i=0;i<n;i++) cout << v[i] << endl;
}

ll powmod(ll a,ll b){ll c=1; while(b>0){ if(b&1){ c=a*c%mod; } a=a*a%mod; b>>=1; } return c;}
ll gcd(ll x, ll y) {return __gcd(x,y);}
ll lcm(ll x, ll y) {return x/__gcd(x,y)*y;}

int main()
{
	ll n;
	cin >> n;
	vll a(n);
	rep(i,n) cin >> a[i];
	reverse(all(a));
	rep(i,n) cout << a[i] << (i==n-1?"\n":" ");
	return 0;
}


Measured memory_bytes: 3076
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXN = 200010;

int N;
int A[MAXN];

int main() {
  cin >> N;
  for(int i = 0;i < N;i++) {
    cin >> A[i];
    A[i] -= i+1;
  }
  sort(A,A+N);
  ll ans = 0;
  for(int i = 0;i < N;i++) ans += ((ll)ans,abs(A[i]-A[N/2]));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
using namespace std;
#define LL long long

LL n,a[210000],s[210000],sum,ans=999999999999;

inline LL myabs(const LL& x) {
	return x>0?x:-x;
}

inline void read(LL& sum)
{
    char ch; sum=0;
    bool f=true;
    ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
    if(ch=='-') f=false,ch=getchar();
    while(ch<='9'&&ch>='0')
        sum=(sum<<3)+(sum<<1)+ch-'0',ch=getchar();
    sum=(f?sum:-sum);
}

int main()
{
	read(n);
	for(LL i=1;i<=n;i++) {
		read(a[i]);
		s[i]=s[i-1]+a[i];
		sum+=a[i];
	}
	for(LL i=1;i<n;i++) {
		LL t=myabs(sum-2*s[i]);
		ans=min(t,ans);
	}
	printf("%lld\n",ans);
	return 0;
}

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

long long gcd(long long a, long long b){
    long long r;
    while(a % b){
        r = a % b;
        a = b;
        b = r;
    }
    return b;
}

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

int main(){
    long long A, B;
    cin >> A >> B;
    cout << lcm(A, B) << endl;

    return 0;
}

Measured memory_bytes: 256
// {{{
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
// }}}

using ll = long long;

int main() {
    ll a, b;
    cin >> a >> b;
    if (a % b == 0) cout << -1 << endl;
    else cout << a << endl;
    return 0;
}


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

using namespace std;

/*  テンプレここから */
typedef long long ll;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, start, end) for(int i = start; i < end; i++)
#define all(x) (x).begin(), (x).end()
#define INF (1e9)
#define add_mod(a, b, x) ( (ll)(a) + (ll)(b) ) % (ll)(x)
#define mul_mod(a, b, x) ( ((ll)(a) % (ll)(x)) * ((ll)(b) % (ll)(x)) ) % (ll)(x)
#define out(x) cout << (x) << endl;
#define outyes(bool_val) cout << (bool_val ? "yes" : "no") << endl;
#define outYes(bool_val) cout << (bool_val ? "Yes" : "No") << endl;
#define outYES(bool_val) cout << (bool_val ? "YES" : "NO") << endl;
#define outPossible(bool_val) cout << (bool_val ? "Possible" : "Impossible") << endl;
#define outPOSSIBLE(bool_val) cout << (bool_val ? "POSSIBLE" : "IMPOSSIBLE") << endl;

ll sub_mod(ll a, ll b, ll x){
    ll tmp = (a - b) % x;
    if(tmp < 0) tmp += x;
    return tmp;
}
ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b, a % b);
}

int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
/*  テンプレここまで */

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

    int a, b, c;
    cin >> a >> b >> c;

    outYes(a + b == c || a + c == b || b + c == a);
}

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

/*Range Sum Update Query*/

template<typename D, int useAssert = 1>
class RSUQ{
public :
  struct T{ //遅延データ
    int type; //0 - empty, 1 - update
    D value;
    T():type(0){}
    T(int type, D value):type(type), value(value){}
  };

  int n, n_;
  vector<D> dat;
  vector<T> td;

  RSUQ(){n=-1;}
  RSUQ(int n_):n_(n_){
    n=1;
    while(n<n_) n *= 2;
    td.resize(2*n-1, T());
    dat.resize(2*n-1, 0);
  }

  //目的データのマージ
  inline D mergeD(D l, D r){return l + r;}

  //遅延データのマージ
  inline T mergeT(const T &from, const T &to){
    if(to.type == 0) return from;
    return to;
  }

  //目的データに遅延データを反映
  inline void apply(D &a, const T &b, int len){
    if(b.type == 0) return;
    a = b.value * len; //update
  }

  D dfs(int a, int b,const T x, int k, int l, int r){
    if(r <= a || b <= l) return x.type == 0? 0 : dat[k];
    if(a <= l && r <= b){
      td[k] = mergeT(td[k], x);
      apply(dat[k], x, r - l);
      return dat[k];
    }
    int kl = k * 2 + 1, kr = k * 2 + 2;
    { //遅延を子に反映
      td[kl] = mergeT(td[kl], td[k]);
      td[kr] = mergeT(td[kr], td[k]);
      apply(dat[kl], td[k], (r - l)/2);
      apply(dat[kr], td[k], (r - l)/2);
      td[k] = T();
    }
    D vl = dfs(a, b, x, kl, l, (l+r)/2);
    D vr = dfs(a, b, x, kr, (l+r)/2, r);
    return x.type == 0? mergeD(vl,vr) : (dat[k] = mergeD(vl, vr));
  }

  //[l,r)の値をxに変更　update(l,r,x)
  void update(int l,int r, D x){
    if(useAssert) assert(l <= r), assert(l <= n && r <= n), assert(l >= 0 && r >= 0);
    dfs(l, r,  T(1, x), 0, 0, n);
  }

  //[l,r)の総和を得る　get(l,r);
  D get(int l,int r){
    if(useAssert) assert(l <= r), assert(l <= n && r <= n), assert(l >= 0 && r >= 0);
    return dfs(l, r, T(), 0 , 0 ,n);
  }
};


signed main(){
  int n,q;
  cin>>n>>q;

  RSUQ<int, 0> rsuq(n);

  while(q--){
    int cmd;
    cin>>cmd;
    if(cmd == 0){
      int s,t,x;
      cin>>s>>t>>x;
      rsuq.update(s,t+1,x);
    }

    if(cmd == 1){
      int s,t;
      cin>>s>>t;
      cout<<rsuq.get(s,t+1)<<endl;
    }
  }

  return 0;
}



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

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

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

void solve() {
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  a--;
  ll l = a - (a/c + a/d - a/lcm(c, d));
  ll r = b - (b/c + b/d - b/lcm(c, d));
  cout << r-l << endl;
}

int main() {
  solve();
  return 0;
}


Measured memory_bytes: 256
combinations :: Int -> [Int] -> [[Int]]
combinations n xs = comb n (length xs) xs where
  comb 0 _ _ = [[]]
  comb r n a@(x:xs)
    | n == r    = [a]
    | otherwise = map (x:) (comb (r - 1) (n - 1) xs) ++ comb r (n - 1) xs
main = do
 n <- read <$> getLine :: IO Int
 print =<< sum . (map (\[x,y] -> x * y)) . (combinations 2) . map read . words <$> getLine

Measured memory_bytes: 4320
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

typedef pair<long long int, long long int> P;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

long long int L;
vector<long long int> ans;

class Trie{
	public:
	Trie* next[2];
	
	Trie(){
		fill(next, next + 2, (Trie*)0);
	}

	void insert(const char *s){
		if(*s == '\0'){
			return;
		}
		if(this->next[*s - '0'] == NULL){
			this->next[*s - '0'] = new Trie();
		}
		this->next[*s - '0']->insert(s + 1);
	}

	void check(int pos){
		for(int i = 0; i < 2; i++){
			if(this->next[i] == NULL){
				if(L != pos){
					ans.push_back(L - pos);
				}
			}else{
				this->next[i]->check(pos + 1);
			}
		}
	}
};

int main(){

	int N;
	cin >> N >> L;

	Trie T = Trie();
	for(int i = 0; i < N; i++){
		string s;
		cin >> s;
		T.insert(s.c_str());
	}
	T.check(0);
	long long int grundy = 0;
	for(int i = 0; i < ans.size(); i++){
		long long int S = 1;
		while(ans[i] % 2 == 0){
			ans[i] /= 2;
			S *= 2;
		}
		grundy ^= S;
	}
	if(grundy){
		cout << "Alice" << endl;
	}else{
		cout << "Bob" << endl;
	}
	return 0;
}

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

int main() {
    int H,W;
    while (cin >> H >> W) {
        if (H == 0) {
            break;
        }
        for (int i = 0; i < H; i++) {
            for (int j= 0; j < W; j++) {
                if ((i + j) % 2 == 0) {
                    cout << "#";
                }
                else {
                  cout << ".";
                }
                
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}




Measured memory_bytes: 3124
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <regex>
#include <iomanip>
#include <climits>
#include <utility>
#include <queue>
using namespace std;
using ll = long long int;
using dd = long double;
const ll MOD = 1e9 + 7;
const dd PI = 3.1415926435;

class UnionFind
{
public:
    UnionFind(int N) : par(N)
    {
        for (ll i = 0; i < N; i++)
        {
            par[i] = i;
        }
    }

    int root(int x)
    {
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y)
    {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry)
            return;
        par[rx] = ry;
    }

    bool same(int x, int y)
    {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

private:
    vector<int> par;
};

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

ll fact(ll n)
{
    if (n == 0)
    {
        return 1;
    }
    if (n == 1)
    {
        return 1;
    }
    return n * fact(n - 1) % MOD;
}

ll pow_fast(ll n, ll k)
{
    if (k == 0)
    {
        return 1;
    }
    if (k == 1)
    {
        return n;
    }

    if (k % 2 == 0)
    {
        ll tmp = pow_fast(n, k / 2LL);
        return tmp * tmp % MOD;
    }
    else
    {
        ll tmp = pow_fast(n, k / 2LL);
        tmp *= tmp;
        tmp %= MOD;
        return tmp * n % MOD;
    }
}

map<ll, ll> sosuu(ll n)
{
    map<ll, ll> res;
    for (ll i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            res[i] += 1;
            n /= i;
        }
    }
    if (n != 1)
    {
        res[n] += 1;
    }
    return res;
}

struct Dish
{
    ll time;
    ll taste;
};

bool isP(ll n)
{
    string s = to_string(n);
    bool is_p = true;
    for (ll i = 0; i < s.size() / 2; i++)
    {
        is_p &= s[i] == s[s.size() - 1 - i];
    }
    return is_p;
}

int main()
{
    ll N, A, B;
    cin >> N >> A >> B;

    auto F = [] (ll n) {
        string s = to_string(n);
        ll ret = 0;
        for (ll i = 0; i < s.size(); i++)
        {
            ret += s[i] - '0';
        }
        return ret;
    };

    ll ans = 0;
    for (ll i = 1; i <= N; i++)
    {
        ll sum = F(i);
        if (A <= sum && sum <= B) {
            ans += i;
        }        
    }
    cout << ans << endl;
}

Measured memory_bytes: 3640
#include <iostream>
using namespace std;
int main(){
    int H,W;
    while(1){
        cin>>H>>W;
        if (H==0 && W==0){
            break;
        }else{
            for (int w1=0;w1<W;w1++){
                cout<<"#";
            }cout<<endl;
            
            for (int h=2;h<H;h++){
                cout<<"#";
                for (int w2=2;w2<W;w2++){
                    cout<<".";
                }
                cout<<"#";
                cout<<endl;
            }for (int w3=0;w3<W;w3++){
                cout<<"#";
            }cout<<endl;
        }cout<<endl;
    }return 0;
}


Measured memory_bytes: 3000
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;

#define FOR(i,n) for(int i = 0; i < n; i++)
#define FORa(i,a,b) for(int i = a; i < b; i++)
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define SORT(a,n) sort(begin(a), begin(a) + n)
#define VSORT(v) sort(v.begin(), v.end())
#define MAX 1000000
#define ll long long
#define LOW(s) transform(s.begin(),s.end(),s.begin(),::tolower)
#define UP(s) transform(s.begin(),s.end(),s.begin(),::toupper)

//-------------------------------------------------------//

int main() {
	int n, m, x;
	ll cost = 1e18;
	cin >> n >> m >> x;
	
	vector<vector<int>> book(n, vector<int>(m+1));
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j <= m; j++)
			cin >> book[i][j];
	}
	
	for(int i = 1; i < (1 << n); i++) { //0001 / 0010 / 0011 / 0100 ...
		ll total = 0;
		vector<ll> val(m);
		
		for(int j = 0; j < n; j++) {
			if(i&(1<<j)) { // this if gets the binary and checks if it is a 1
				total += book[j][0];
				for(int k = 0; k < m; k++) 
					val[k] += book[j][k+1]; //first indice is for the cost +1
			}
		}
		
		bool flag = 1;
		for(int j = 0; j < m; j++) {
			flag &= val[j] >= x;
		}
		
		if(flag) cost = min(cost, total);
	}
	
	cout << ((cost == 1e18) ? -1 : cost) << endl;
	
	return 0;
}


Measured memory_bytes: 3604
D, G=map(int, input().split())
PC=[0]+[list(map(int, input().split())) for _ in range(D)]

def function(G, i):
	if i==0:
		return 1e9
	n=min(G//(i*100), PC[i][0])
	s=n*i*100
	if n==PC[i][0]:
		s+=PC[i][1]
	if s<G:
		n+=function(G-s, i-1)
	return min(n, function(G,i-1))
print(function(G, D))


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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000009;
const long long INF = 1LL << 60;

int main() {
    int N;
    cin >> N;
    int res = 0;
    for (int i = 1; i <= N; ++i) {
        if (i % 2 == 0) continue;
        int count = 0;
        for (int j = 1; j <= N; ++j) {
            if (i % j == 0) ++count;
        }
        if (count == 8) ++res;
    } 
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3588
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>

using namespace std;

int main(void)
{
    string b;

    cin >> b;

    if(b[0]=='A'){
        cout << 'T' << endl;
    }
    else if(b[0]=='T'){
        cout << 'A' << endl;
    }
    else if(b[0]=='C'){
        cout << 'G' << endl;
    }
    else{
        cout << 'C' << endl;
    }

    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC168B
{
    class Program
    {
        static void Main(string[] args)
        {
            int K = int.Parse(Console.ReadLine());
            string S = Console.ReadLine();
            int num = S.Length;
            if (num <= K)
            {
                Console.WriteLine(S);
            }
            else
            {
                string ans = S.Substring(0, K);
                ans = ans + "...";
                Console.WriteLine(ans);
            }
        }
    }
}


Measured memory_bytes: 27484
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
    int x, y;
    cin >> x >> y;

    int val = 4 * x - y;

    if (val >= 0 && val % 2 == 0 && 2*x >= val)
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }

    return 0;
}


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

#define dump(x) cout << (x) << endl
#define Int int64_t
#define fi first
#define se second
 
Int INF = 1e18;
Int mod = 1e9+7;
//Int mod = 998244353;

int main() {
    string s;
    cin >> s;
    Int l = 0;
    Int r = (Int)s.size() - 1;
    Int res = 0;
    while (l < r) {
        if (s[l] != s[r]) {
            res++;
        }
        l++;
        r--;
    }
    dump(res);
    return 0;
}

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

#define nl '\n'
#define F fisrt
#define S second
#define pb push_back
#define mp make_pair
#define REP(i,a,b) for(int i = a; i < b; i++)
#define ForeachTC int t; cin >> t; while(t--)
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef stack<int> si;
typedef deque<int> di;
typedef pair<int,int> pi;

class Solution {
public:
    int climbStairs(int n) {
		if(n <= 2)
			return n;
		else{
			return climbStairs(n-1) + climbStairs(n-2);
		}
    }
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	//code here
	ll n,m;
	cin >> n >> m;
	ll total = 0l;
	REP(i,0,m){
		int temp;
		cin >> temp;
		total += temp;
	}
	if(total > n)
		cout << -1;
	else 
		cout << n - total;
}


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

int main(){
  int N, M; cin >> N >> M;
  int maxL=0, minR=100001;
  
  vector<int> L(M);
  vector<int> R(M);
  for(int i=0; i<M; i++) cin >>L.at(i) >>R.at(i);

  for(int i=0; i<M; i++){
    if(maxL < L.at(i)) maxL=L.at(i);
    if(minR > R.at(i)) minR=R.at(i);
  }
  
  int x=minR-maxL+1;
  if(x<0) cout << 0 <<endl;
  else cout << x <<endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
 
typedef long long   ll;
typedef long double ld;
const int N  = 5e5+10;
const ll mod = 1e9+7;
const ll inf = 1e18;
 
#define fast            ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb              push_back
#define mp              make_pair
#define ub              upper_bound                 // first element >  val(itr)
#define lb              lower_bound                 // first element >= val(itr) 
#define all(x)          (x).begin(),(x).end()
#define reset(a,x)      memset(a,x,sizeof(a))       // x can be 0 or -1
#define leadzero(a)     __builtin_clz(a)            // count leading zeroes
#define trailzero(a)    __builtin_ctz(a)            // count trailing zeroes
#define bitcount(a)     __builtin_popcount(a)       // count set bits
#define iceil(n,x)      ((n)+(x)-1)/(x)
#define test            int t; cin>>t; while(t--)
#define forn(i,a,e)     for(ll i = a; i < e; i++)
#define pll             pair<ll,ll>
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << endl;
  err(++it, args...);
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;   }
ll lcm(ll a, ll b) { ll r=((a*b)/gcd(a,b)); return r;}
ll isOnBit(ll n, ll b) {return (n >> b) & 1;         }
ll powm(ll base,ll exp){ll ans=1;while(exp){if(exp&1) ans=(ans*base)%mod;exp>>=1,base=(base*base)%mod;}return ans;}
ll add(ll a,ll b)  { return (a%mod+b%mod)%mod;        }
ll sub(ll a, ll b) { return (a%mod+mod-b%mod)%mod;    }
ll mult(ll a,ll b) { return ((a%mod)*(b%mod))%mod;    }
ll choose2(ll n)   { ll ans=(n*(n-1))/2; return ans;  }
ll digsum(ll n)    { ll cnt=0; while(n){cnt+=(n%10); n/=10;} return cnt;}
ll dist2(ll x1,ll y1,ll x2,ll y2){ ll ans=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1); return ans;}


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

    ll a[n];
    ll maxi=0;
    forn(i,0,n)
    {
        cin>>a[i];
        maxi=max(a[i],maxi);
    }
    sort(a,a+n);
    ll ans=0; 
    forn(i,0,maxi+1)
    {
        ll idx = lower_bound(a,a+n,i)-a;
        if(n-idx == idx)
            ans++;
    }

    cout<<ans;

    return 0;
}

Measured memory_bytes: 1024
import sys
import math as mt
input=sys.stdin.buffer.readline  
#t=int(input())
t=1
for __ in range(t):
    #n,k=map(int,input().split())
    n=int(input())
    l=list(map(int,input().split()))
    xori=0
    for i in l:
        xori^=i
    for i in l:
        print(xori^i,end=" ")
        

Measured memory_bytes: 92728
#include <stdio.h>

int main(void)
{
  int i;
  int a[3];
  scanf("%d %d %d", &a[0], &a[1], &a[2]);

  if (a[0] < a[1] && a[1] < a[2]) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }

  return 0;
}



Measured memory_bytes: 2060
N = int(input())
xmin = ymin = float('inf')
xmax = ymax = 0
p = []
for i in range(N):
    x,y = map(int, input().split())
    if x > y : 
        x,y= y,x
    p.append((x, y))
    if x < xmin:
        xmin = x
    elif x > xmax:
        xmax = x
    if y < ymin:
        ymin = y
    elif y > ymax:
        ymax = y
ret = (ymax-ymin) * (xmax-xmin)


p.sort()
dx = p[-1][0] - p[0][0]
ymin = p[0][0]
tymin = float('inf')
tymax = 0
for i in range(N-1):
    # print(i, dx, (xmax, xmin), end=' ==> ')
    tymin = min(tymin, p[i][1])
    xmax = max(xmax, p[i][1])
    xmin = min(tymin, p[i+1][0])
    dx = min(dx, xmax - xmin)
    # print(i, dx, (xmax, xmin))

# print(ret, (ymax-ymin) * (xmax-xmin) ,(ymax,ymin), (xmax,xmin), dx)
print(min(ret, (ymax-ymin) * dx))




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

 const int N=1000000000;
int main() {
  ll n,ans=1;
  cin>>n;
  vector<ll> a(n);
  rep(i,n){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  if(a[0]==0){
    cout<<0<<endl;
    return 0;
  }
  rep(i,n){
    ll p=ans,q=a[i];
    if(p>N){
      p/=N;
    }
    if(q>N){
      q/=N;
    }
    if(((p!=ans||q!=a[i])&&p*q>=N)||(p!=ans&&q!=a[i])){
      ans=-1;
      break;
    }
    ans=ans*a[i];
  }
  if(ans>1000000000000000000){
    cout<<-1<<endl;
    return 0;
  }
  cout<<ans<<endl;
}

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

using namespace std;

int main(){
char a;
cin >> a;
if(a == 'A'){
    return cout << 'T', 0;
}
if(a == 'T'){
    return cout << 'A', 0;
}
if(a == 'C'){
    return cout << 'G', 0;
}
if(a == 'G'){
    return cout << 'C', 0;
}
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    g = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        g[a].append(b)
        g[b].append(a)

    mod = 10**9+7 #出力の制限
    N = 10**6
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル

    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )

    # topological sort
    s = []
    s.append(0)
    parent = [-1]*n
    order = []
    while s:
        v = s.pop()
        order.append(v)
        for u in g[v]:
            if u == parent[v]:
                continue
            parent[u] = v
            s.append(u)

    dp = [1]*n
    c = [0]*n
    order.reverse()
    for v in order:
        dp[v] *= g1[c[v]]
        dp[v] %= mod
        c[v] += 1
        if parent[v] == -1:
            continue
        c[parent[v]] += c[v]
        dp[parent[v]] *= (dp[v]*g2[c[v]])
        dp[parent[v]] %= mod

    order.reverse()
    ans = [0]*n
    for v in order:
        ans[v] = dp[v]
        for u in g[v]:
            if u == parent[v]:
                continue
            dp[u] *= ans[v]*g2[c[v]-1]*g1[c[v]-1-c[u]]*g1[c[u]]*pow(dp[u],(mod-2),mod)
            dp[u] *= g2[c[u]-1]
            dp[u] *= g1[c[v]-1]
            dp[u] *= g2[c[v]-c[u]]
            dp[u] %= mod
            c[u] = c[v]
    for i in range(n):
        print(ans[i]%mod)

if __name__ == '__main__':
    main()

Measured memory_bytes: 175916
Sa = list(input())
Sb = list(input())
Sc = list(input())

card = Sa.pop()
while 1:
    if card == 'a':
        if len(Sa) > 0:
            card = Sa.pop(0)
        else:
            print('A')
            break
    elif card == 'b':
        if len(Sb) > 0:
            card = Sb.pop(0)
        else:
            print('B')
            break
    else:
        if len(Sc) > 0:
            card = Sc.pop(0)
        else:
            print('C')
            break


Measured memory_bytes: 38256
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(N)]

cd = sorted(cd, key=lambda x:x[0])
ab = sorted(ab, key=lambda x:x[1],reverse=True)


count = 0
i = 0
while i < N:
    for j in range(len(ab)):
        if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1]:
            count += 1
            del ab[j]
            break
    i += 1
print(count)


Measured memory_bytes: 3064
// きりみんちゃんの配信からきました
// 左右をとる+-1のしゃくとり、左がマイナスかつ右がプラスの場合には「左に行った後折り返す」vs「右に行ったあと折り返す」が発生する
// ゼロ含む場合マジでなんなんだよ
package main

import (
	"fmt"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	a := make([]int, n)
	includeZero := false
	zeroIdx := -1
	for i := 0; i < n; i++ {
		var j int
		fmt.Scan(&j)
		a[i] = j
		if j == 0 {
			includeZero = true
			zeroIdx = i
		}
	}
	if includeZero {
		// ゼロを含む場合、よくわかんなかったので値を更新することにした
		if zeroIdx != 0 && zeroIdx != n-1 {
			if abs(a[zeroIdx-1]) < abs(a[zeroIdx+1]) {
				a[zeroIdx] = a[zeroIdx-1]
			} else {
				a[zeroIdx] = a[zeroIdx+1]
			}
		}
	}
	ans := 10000000000000000
	r := 0
	tmp := 0
	// しゃくとりフェーズ
	for l := 0; l <= n-k; l++ {
		for r < n && r-l < k {
			r += 1
		}
		// 更新は3パターン
		if a[r-1] <= 0 {
			// 最大で0より小さい場合
			tmp = a[l] * -1
		} else if a[l] >= 0 {
			// 最小で0より大きい場合
			tmp = a[r-1]
		} else {
			// 最小が0より小さく、最大が0より大きい場合
			// これが無限にバグった原因 0を挟んでいる状態だと右にいくか左にいくかで変わるんだよ（あたりまえ）
			tmp = min(a[l]*-2+a[r-1], a[r-1]*2+a[l]*-1)
		}
		ans = min(ans, tmp)
		tmp -= a[l]
	}
	fmt.Println(ans)
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		a *= -1
	}
	return a
}


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

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

using namespace std;

using ll = long long;
using P = pair<int , int>;
  
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n; cin >> n;
  vector<int> ans(n, 0);

  int x;
  while(cin >> x) {
    ++ans[x-1];
  }
  for(auto aa : ans) cout << aa << endl;
}


Measured memory_bytes: 3976
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

using namespace std;
typedef long long  ll;
typedef long double ld;
typedef pair<ll,ll> pp;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> super_set;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> multi_set;
#define x1 dfds
#define y1 dsfdsfe
#define pb push_back
#define forn(i,n) for(ll i = 1;i<=n;++i)
#define fi first
#define sc second
#define endl '\n'
#define po(x) (1ll<<x)
const ll DIM = 3000+7;
const ll INF = 1e9;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll MOD = 998244353;
ll A[DIM],cnt[DIM],res = 0;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n,S;
    cin>>n>>S;
    forn(i,n)cin>>A[i];

    forn(i,n){

        cnt[0]++;
        if (A[i]>S)continue;
        res = (res+cnt[S-A[i]]*(n-i+1))%MOD;
        for(ll v = S-A[i];v>=1;--v){
            cnt[v+A[i]]=(cnt[v+A[i]]+cnt[v])%MOD;
        }
        cnt[A[i]]=(cnt[A[i]]+i)%MOD;

        //cout<<res<<' ';
    }
    cout<<res<<endl;
    return 0;
}



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

constexpr int64_t DIV1097 = 1000000007LL;

using namespace std;


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

    struct C {
        int64_t p;
        int64_t y;
    };

    std::vector<C> c;
    std::vector< std::vector<int64_t> > m;
    m.resize(N+1);
    for (decltype(M) i = 0; i < M; ++i) {
        C t;
        std::cin >> t.p >> t.y;
        c.push_back(t);
        m[t.p].push_back(t.y);
    }

    for (auto& v: m) {
        std::sort(std::begin(v), std::end(v));
    }

    for (int64_t i = 0; i < M; ++i) {
        auto& mp = m[c[i].p];
        auto itr = std::lower_bound(mp.begin(), mp.end(), c[i].y);

        std::cout << setfill('0') << setw(6) << right << c[i].p
                  << setfill('0') << setw(6) << right << std::distance(mp.begin(), itr) + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 8560
#include<iostream>
#include<cmath>

using namespace std; 

#define pi 3.1415926535

int main()
{
	int a, b, h, m;
	scanf("%d %d %d %d", &a, &b, &h, &m);
	h = h % 12;
	m = m % 60;
	double theta = fabs(6 * m - 0.5 * (60 * h + m)) / 180 * pi;
	double distance;
	distance = sqrt(a * a + b * b - 2 * a * b * cos(theta));
	printf("%.11lf", distance);
	return 0;
}

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

alphabet = ['a', 'b', 'c','d','e','f','g', 'h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
mm = 1
name = ''
while True:
    if N > 26 ** mm:
        N = N - 26 ** mm
        mm += 1
    else:
        break
#mmけた

for i in range(mm):
    
    

    if N< 1:
        name =  'a' +name
    else:
            if N%26 == 0:
                name = alphabet[25] + name
                N = N//26
            else:
                name = alphabet[N%26-1] + name
                N = N//26 +1
print(name)


Measured memory_bytes: 61976
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

H, W, D = map(int, raw_input().split())
m = [0] * (H * W + 1)
for i in range(H):
    A = map(int, raw_input().split())
    for j in range(W):
        m[A[j]] = (i, j)

DP = [0] * D

for i in range(D, H * W):
    x1, y1 = m[i + 1]
    x2, y2 = m[i + 1 - D]
    dist = abs(x1 - x2) + abs(y1 - y2)
    DP.append(DP[i - D] + dist)

Q = input()

for i in range(Q):
    L, R = map(int, raw_input().split())
    print DP[R - 1] - DP[L - 1]

Measured memory_bytes: 17168
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<int,int>;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define DIV int(1e9+7)
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
const double PI = M_PI;  
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}

/* Coding Space*/
using tiii = tuple<int,int,int>;
vector<tiii> vtiii; // time, type, channel

int check[10001] = {};

int main(){
  int n,c; cin >> n >> c;
  rep(i,n){
    int s,t,c; cin >> s >> t >> c;
    s *= 4, t *= 4;
    vtiii.pb(tiii{s-2,1,c});
    vtiii.pb(tiii{t-1,0,c});
  }
  sort(ALL(vtiii));
  int ans = 0;
  int t_ans = 0;
  rep(i,2*n){
    int tim,typ,channel;
    tie(tim,typ,channel) = vtiii[i];
    if(typ == 1){
      if(check[channel] == 0)
        t_ans++,check[channel]++;
      else
        check[channel]++;
      ans = max(ans,t_ans);
    }else{
      check[channel]--;
      if(check[channel] == 0)
        t_ans--;
    }
  }      
  cout << ans << endl;
}

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

typedef pair<int, int> P;

struct UnionFind {
    vector<int> Parent;

    UnionFind(int N) { Parent = vector<int>(N, -1); }

    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }

    int size(int A) { return -Parent[root(A)]; }

    bool connect(int A, int B) {
        A = root(A);
        B = root(B);
        if (A == B) {
            return false;
        }

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

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }

    bool same(int A, int B) { return root(A) == root(B); }
};

int main() {
    int N, K, L;
    cin >> N >> K >> L;
    UnionFind Uni1(N);
    for (int i = 0; i < K; i++) {
        int p, q;
        cin >> p >> q;
        p--;
        q--;
        Uni1.connect(p, q);
    }

    UnionFind Uni2(N);
    for (int i = 0; i < L; i++) {
        int r, s;
        cin >> r >> s;
        r--;
        s--;
        Uni2.connect(r, s);
    }

    map<P, int> ma;
    for (int i = 0; i < N; i++) {
        ma[P(Uni1.root(i), Uni2.root(i))]++;
    }

    for (int i = 0; i < N; i++) {
        cout << ma[P(Uni1.root(i), Uni2.root(i))] << " ";
    }
    cout << endl;
}

Measured memory_bytes: 13568
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
int32_t main(){
    if(fopen("input.txt", "r"))
    freopen("input.txt", "r", stdin),
    freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    int n,m,sum=0;
    cin >> m >> n;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        sum+=x;
    }
    if(sum>m)cout << -1;
    else cout << m-sum;
}

Measured memory_bytes: 3656
#include<stdio.h>
#include<string.h>

int main()
{
    char string[1000000], ch;
    int c = 0, count[26] = {0},p=0;
    gets(string);
    while ( string[c] != '\0' )
    {
        if ( string[c] >= 'a' && string[c] <= 'z' )
            count[string[c]-'a']++;
        c++;
    }

    for ( c = 0 ; c < 26 ; c++ )
    {
        if( count[c] == 0 )
        {
            printf("%c\n",c+'a');
            return 0;
        }

    }
    printf("None\n");

    return 0;
}


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

using namespace std;
const int N = 200200;

struct trie {
    int cnt[26];
    trie *child[26];

    trie() {
            for (int i = 0; i < 26; i++) {
                    child[i] = NULL;
                    cnt[i] = 0;
            }

    }
};

void add(trie *root, string s) {
        for (int i = s.size() - 1; i > 0; i--) {
                int c = s[i] - 'a';
                if (root->child[c] == NULL) root->child[c] = new trie();
                root = root->child[c];
        }
        root->cnt[s[0] - 'a']++;
}

string s[N];
int order[N];

void solve() {
        trie *root = new trie();

        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
                cin >> s[i];
                order[i] = i;
        }
        sort(order + 1, order + n + 1, [](int a, int b) { return (s[a].size() < s[b].size()); });
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
                string s = ::s[order[i]];
                trie *v = root;
                vector<int> f(26, -1);
                for (int j = (int) s.size() - 1; j >= 0; j--) {
                        f[s[j] - 'a'] = j;
                }
                for (int j = (int) s.size() - 1; j > 0; j--) {
                        int c = s[j] - 'a';
                        if (v->child[c] == NULL) {
                                break;
                        }
                        v = v->child[c];
                        for (int k = 0; k < 26; k++) {
                                if (f[k] != -1 && f[k] < j) {
                                        ans += v->cnt[k];
                                }
                        }
                }
                for (int k = 0; k < 26; k++) {
                        if (f[k] != -1) {
                                ans += root->cnt[k];
                        }
                }
                add(root, s);
        }
        cout << ans << endl;
}


int main() {
#ifdef QWERTY
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
#endif
        ios_base::sync_with_stdio(false);


        int t = 1;
//        cin >> t;

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

//                cout << "Case #" << i << ':' << endl;
                solve();
        }


        return 0;
}

Measured memory_bytes: 322856
#include <iostream>
using namespace std;
int main(void){
    long long int A,B,N;
    cin>>A>>B>>N;
    if(N>=B){
        N=B-1;
        long long int a=A*N/B;
        cout<<a-A*(N/B)<<endl;
    }
    else{
        long long int a=A*N/B;
        cout<<a-A*(N/B)<<endl;
    }
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define INF 1000000000
typedef long long ll;

int main(){
  int n, x, cnt = 1, sum = 0, j;
  cin >> n >> x;
  for(int i = 0; i < n; i++) {cin >> j; sum += j; if(sum<=x)cnt++;}
  cout << cnt;
}  

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
  int a , b;
  scanf("%d %d\n",&a , &b);


  if (a < b)
    printf("a < b\n");

  if(a > b)
    printf("a > b\n");

  if(a == b)
    printf("a == b\n");


return 0;
}


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

using namespace std;

const int max_n = 100111, inf = 1000111222;

int n, p[max_n], nxt[max_n], used[max_n], ans[max_n];
int cur;
vector<int> g[max_n], g2[max_n];

bool dfs(int v) {
    if (used[v] == cur) {
        return false;
    }
    used[v] = cur;
    for (int to : g[v]) {
        if (p[to] == -1 || dfs(p[to])) {
            p[to] = v;
            nxt[v] = to;
            return true;
        }
    }
    return false;
}

void dfs2(int v) {
    used[v] = 1;
    for (int to : g2[v]) {
        if (used[to] == 0) {
            dfs2(to);
            ans[to] = nxt[v];
        }
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i + 1 < n; ++i) {
        int k;
        scanf("%d", &k);
        g[i].resize(k);
        for (int &x : g[i]) {
            scanf("%d", &x);
            --x;
        }
    }
    memset(nxt, -1, sizeof(nxt));
    memset(p, -1, sizeof(p));
    for (int i = 0; i + 1 < n; ++i) {
        for (int to : g[i]) {
            if (p[to] == -1) {
                p[to] = i;
                nxt[i] = to;
                break;
            }
        }
    }
    for (int i = 0; i + 1 < n; ++i) {
        if (nxt[i] == -1) {
            ++cur;
            dfs(i);
        }
    }
    /*for (int run = 1; run; ) {
        run = 0;
        memset(used, 0, sizeof(used));
        for (int i = 0; i + 1 < n; ++i) {
            if (nxt[i] == -1 && dfs(i)) {
                run = 1;
            }
        }
    }*/
    for (int i = 0; i + 1 < n; ++i) {
        if (nxt[i] == -1) {
            puts("-1");
            return 0;
        }
    }
    int root;
    for (int i = 0; i < n; ++i) {
        if (p[i] == -1) {
            root = i;
            break;
        }
    }
    p[root] = n - 1;
    nxt[n - 1] = root;
    for (int i = 0; i + 1 < n; ++i) {
        for (int to : g[i]) {
            if (to != nxt[i]) {
                g2[p[to]].push_back(i);
            }
        }
    }
    memset(used, 0, sizeof(used));
    dfs2(n - 1);
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            puts("-1");
            return 0;
        }
    }
    for (int i = 0; i + 1 < n; ++i) {
        printf("%d %d\n", nxt[i] + 1, ans[i] + 1);
    }
    return 0;
}


Measured memory_bytes: 17664
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define INF 100000000
using namespace std;
const int mod = 1000000007;


bool changeToWhite(int& N,int& M,vector<string>& A) {
    vector<vector<int>> tmpmemo(N, vector<int>(M));
    for (int a1 = 0; a1 < N; a1++) { for (int a2 = 0; a2 < M; a2++) { tmpmemo[a1][a2] = INF;} }
    tmpmemo[0][0] = 0;
    queue<pair<int, int>> tmpque,tmp2que;
    tmpque.push(make_pair(0, 0));
    int yc, xc,yn,xn;
    vector<int> dy = { 1,0,-1,0 }, dx = { 0,1,0,-1 };
    while (tmpque.size() > 0 ) {
        if (A[0][0] == '#')break;
        yc = tmpque.front().first; xc = tmpque.front().second;
        tmpque.pop();
        for (int i = 0; i < 2; i++) {
            yn = yc + dy[i]; xn = xc + dx[i];
            if (0 <= yn && yn < N && 0 <= xn && xn < M && A[yn][xn] != '#' && tmpmemo[yn][xn] == INF) {
                if (yn == N-1 && xn == M-1) { return true; }
                tmpmemo[yn][xn] = tmpmemo[yc][xc] + 1;
                tmpque.push(make_pair(yn, xn));
            }
        }
    }
    for (int n = 0; n < N; n++) {
        for (int m = 0; m < M; m++) {
            if (A[n][m] == '#') {
                for (int b = 0; b < 2; b++) {
                    if (0 <= n - dy[b] && n - dy[b] < N && 0 <= m - dx[b] && m - dx[b] < M && tmpmemo[n - dy[b]][m - dx[b]] != INF) { tmp2que.push(make_pair(n-dy[b],m-dx[b])); break; }
                }
            }
        }
    }
    if (A[0][0] == '#') { tmp2que.push(make_pair(0, 0)); A[0][0] = '.'; }
    while (tmp2que.size() > 0) {
        yc = tmp2que.front().first; xc = tmp2que.front().second;
        tmp2que.pop();
        for (int i = 0; i < 2; i++) {
            yn = yc + dy[i]; xn = xc + dx[i];
            if (0 <= yn && yn < N && 0 <= xn && xn < M && A[yn][xn] == '#' && tmpmemo[yn][xn] == INF) {
                A[yn][xn] = '.';
                tmp2que.push(make_pair(yn, xn));
            }
        }
    }
    return false;
}

int main() {

    int N, M;
    cin >> N >> M;
    vector<string> A(N);
    for (int i = 0; i < N; i++) { cin >> A[i]; }
    int ans = 0;
    
    while (true) {
        if (changeToWhite(N, M, A)) break;
        ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
# -*- coding:utf-8 -*-

def is_onaji(S):
    pre_moji = S[0]
    for i in range(1, len(S)):
        if S[i] == pre_moji:
            pre_moji = S[i]
            continue
        else:
            return False
    return True


def solve():
    S = input()
    K = int(input())
    N = len(S)

    if N == 1:
        print(K//2)
        return

    # 1回目
    base1 = 0
    pre_moji = S[0]
    for i in range(1, N):
        if S[i] == pre_moji:
            base1 += 1
            pre_moji = "?"
        else:
            pre_moji = S[i]

    if K == 1:
        print(base1)
        return

    # 2回目
    base2 = 0
    for i in range(0, N):
        if S[i] == pre_moji:
            base2 += 1
            pre_moji = "?"
        else:
            pre_moji = S[i]

    if K == 2:
        print(base1+base2)
        return

    # 3回目
    base3 = 0
    for i in range(0, N):
        if S[i] == pre_moji:
            base3 += 1
            pre_moji = "?"
        else:
            pre_moji = S[i]

    if K == 3:
        print(base1+base2+base3)
        return

    if base1 == base2 and base2 == base3:
        print(base1*K)
    elif base1 != base2 and base2 == base3:
        print(base1 + base2*(K-1))
    else:
        # base1とbase2が交互にくる
        print(base1*((K+1)//2) + base2*(K//2))


if __name__ == "__main__":
    solve()


Measured memory_bytes: 3064
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

from fractions import gcd

N = int(input())

T = int(input())

for _ in range(N - 1):
    t = int(input())
    T = T * t // gcd(T, t)

print (T)

Measured memory_bytes: 5048
/**
*    created: 05.07.2020 20:41:36
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const int inf =1000000000;

int main() {
    int n;
    cin >> n;
    int ac=0, wa=0, tle=0, re = 0;
    rep(i,n){
        string s;
        cin >> s;
        if(s=="AC")
            ac++;
        else if(s=="WA")
            wa++;
        else if(s=="TLE")
            tle++;
        else
        {
            re++;
        }
    }
    cout << "AC x "<<ac << endl;
    cout << "WA x "<<wa << endl;
    cout << "TLE x "<<tle << endl;
    cout << "RE x "<<re << endl;
}

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

int main() {
  int N;
  cin >> N;
  
  vector<int> a(N);
  for (int i = 0; i < N; i++) cin >> a.at(i);
  
  int temp;
  for (int i = 0; i < N-1; i++) {
    for (int j = i+1; j < N; j++) {
      if (a.at(i) < a.at(j)) {
        temp = a.at(i);
        a.at(i) = a.at(j);
        a.at(j) = temp;
      }
    }
  }
  
  int S = 0;
  for (int i = 0; i < N; i++) {
    //cout << a.at(i);
    if (i%2 == 0) 
      S += a.at(i);
    else 
      S -= a.at(i);
  }
  cout << S << endl;
}

Measured memory_bytes: 256