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

#define all(container) container.begin(), container.end()
#define sortall(container) (sort(container.begin(), container.end()))
#define yn(cond) ((cond) ? (cout << "yes" << endl) : (cout << "no" << endl))
#define Yn(cond) ((cond) ? (cout << "Yes" << endl) : (cout << "No" << endl))
#define YN(cond) ((cond) ? (cout << "YES" << endl) : (cout << "NO" << endl))

typedef long long       ll;

typedef vector<int>     vi;
typedef vector<ll>      vll;
typedef vector<double>  vd;
typedef vector<bool>    vb;
typedef vector<char>    vc;
typedef vector<string>  vs;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;
typedef vector<vi>		vvi;
typedef vector<vll>		vvll;
typedef vector<vd>		vvd;
typedef vector<vb>		vvb;
typedef vector<vc>		vvc;
typedef vector<vs>		vvs;
typedef vector<pii>     vpii;
typedef vector<pll>     vpll;

typedef struct edge_ {
	ll to;
	ll cost;
} edge;

typedef struct point_ {
	ll x, y;
	point_(ll x = 0, ll y = 0) : x(x), y(y) {}
} point;

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

constexpr double	PI = 3.14159265358979323846;
constexpr ll		INF = 1 << 15;
constexpr ll		MOD = (ll)1e9 + 7;
constexpr double	EPS = 1e-7;
constexpr int		dy4[4] = { 0, 1, 0, -1 };
constexpr int		dx4[4] = { 1, 0, -1, 0 };
constexpr int		dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
constexpr int		dx8[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };

template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
	for (T& x : vec) is >> x;
	return is;
}

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
	for (const T& x : vec) os << x << " ";
	return os;
}

template<typename S, typename T>
istream& operator >> (istream& is, pair<S, T>& p) {
	is >> p.first >> p.second;
	return is;
}

istream& operator >> (istream& is, point& p) {
	is >> p.x >> p.y;
	return is;
}

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

template<typename T>
ostream& operator << (ostream& os, const set<T>& s) {
	for (const T& x : s) os << x << " ";
	return os;
}

ostream& operator << (ostream& os, const edge e) {
	os << "{to: " << e.to << ", cost: " << e.cost << "}";
	return os;
}

ostream& operator << (ostream& os, const point& p) {
	os << "(" << p.x << " " << p.y << ")";
	return os;
}

/******************************************************************************/
/**********************         Don't make WA !!         **********************/
/******************************************************************************/

int main()
{
	int N, M;
	cin >> N >> M;
	vvc A(N, vc(N)), B(M, vc(M));
	cin >> A >> B;

	if (N == M) {
		Yn(A == B);
		return 0;
	}

	for (int h = 0; h < N - M; h++) {
		for (int w = 0; w < N - M; w++) {
			bool match = true;
			for (int hh = 0; hh < M; hh++) {
				for (int ww = 0; ww < M; ww++) {
					if (A[h + hh][w + ww] != B[hh][ww])
						match = false;
				}
			}

			if (match) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}

	cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 256
require 'openssl'
def extended_gcd(a, b)
  last_remainder, remainder = a.abs, b.abs
  x, last_x, y, last_y = 0, 1, 1, 0
  while remainder != 0
    last_remainder, (quotient, remainder) = remainder, last_remainder.divmod(remainder)
    x, last_x = last_x - quotient*x, x
    y, last_y = last_y - quotient*y, y
  end

  return last_remainder, last_x * (a < 0 ? -1 : 1)
end

def modinv(e, et)
  g, x = extended_gcd(e, et)
  if g != 1
    raise 'The maths are broken!'
  end
  x % et
end

MOD = 10**9 + 7
h,w,a,b = gets.chomp.split().map(&:to_i)

hw = h+w
kaijo = Array.new(hw)
kaijo[0] = 1
1.upto(hw).each do |i|
  kaijo[i] = (kaijo[i-1] * i) % MOD
end

ans = 0
(h-a).times do |i|
  path1 = ((kaijo[b-1 + i] * modinv(kaijo[b-1], MOD) % MOD) * modinv(kaijo[i], MOD)) % MOD
  path2 = ((kaijo[h-i-1 + w-b-1] * modinv(kaijo[h-i-1], MOD) % MOD) * modinv(kaijo[w-b-1], MOD)) % MOD
  path = (path1 * path2) % MOD
  ans = (ans + path) % MOD
  #p [path1, path2, '', path, ans]
end

puts ans


Measured memory_bytes: 4732
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

struct Graph
{
    int n;
    vector<vector<int>> g;
    
    Graph(int n) : n(n){
        g.resize(n);
    }
    
    void init(int n_){
        n = n_;
        g.resize(n_);
    }
    
    void add_edge(int from, int to){
        g[from].push_back(to);
    }
};

struct Tree	//create tree(directed) from graph(undirected)
{
    int n;
    int root;
    vector<vector<int>> t;
    vector<int> par;
    vector<int> dpt;
    
    void init(Graph &g, int root_){
        n = g.n;
        root = root_;
        t.resize(n);
        par.resize(n);
        dpt.resize(n);
        fill(dpt.begin(), dpt.end(), -1);
        queue<int> que;
        par[root] = -1;
        dpt[root] = 0;
        que.push(root);
        while(que.size()){
            int pa = que.front();
            que.pop();
            for(int ch : g.g[pa]){
                if(dpt[ch] == -1){
                    t[pa].push_back(ch);
                    par[ch] = pa;
                    dpt[ch] = dpt[pa] + 1;
                    que.push(ch);
                }
            }
        }
    }

    Tree(){}
    
    Tree(Graph &g, int root_){
        init(g, root_);
    }
};

Tree t;
ll a[100002];
ll memo[100002];

ll dfs(int u){
    if(memo[u]) return memo[u];
    if((int)t.t[u].size() == 0) return memo[u] = a[u];
    ll s = 0, l = 0;
    for(int v : t.t[u]){
        ll c = dfs(v);
        if(c == -1) return memo[u] = -1;
        s += c;
        l = max(l, c);
    }
    if(a[u] * 2 >= s && a[u] >= l && a[u] <= s) return memo[u] = a[u] * 2 - s;
    return memo[u] = -1;
}

int main()
{
    int n;
    cin >> n;
    Graph g(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        u--; v--;
        g.add_edge(u, v);
        g.add_edge(v, u);
    }
    t.init(g, 0);
    if(((int)t.t[0].size() == 1 && dfs(0) == a[0]) || ((int)t.t[0].size() != 1 && dfs(0) == 0)) cout << "YES" << endl;
    else cout << "NO" << endl;
}

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

typedef long long int ll;
void solved(){
	ll n;cin>>n;
	ll s = 0;
	for(int i = 1; i <= n; i++){
		if(i % 3 == 0 || i%5 == 0)continue;
		s += i;
	}
	cout<<s<<endl;
}
int main(){
	solved();
	return 0;
} 

Measured memory_bytes: 3620
using System;

namespace _100B
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] read = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            int D = read[0];
            int N = read[1];
            if(N%100==0){
                N = N+1;
            }
            Console.WriteLine(Math.Pow(100,D)*N);
        }
    }
}

Measured memory_bytes: 13140
(loop with a = 0
      with b = 0
      with c = 0
      for char across (read-line)
      do (case char (#\a (incf a)) (#\b (incf b)) (#\c (incf c)))
      finally (if (<= (- (max a b c) (min a b c)) 1)
                  (write-line "YES")
                  (write-line "NO")))


Measured memory_bytes: 6504
n,*L=map(int,open(0).read().split())
s=sorted((a+b,a,b) for a,b in zip(*[iter(L)]*2))
ans=0
for i,(_,a,b) in enumerate(s[::-1]):
	if i%2:
		ans-=b
	else:
		ans+=a
print(ans)

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

const long INF = 1e9+2;

int main(){
    long N;
    long A[100010];
    long dp[100010];

    cin >> N;
    fill(dp, dp+N, INF);
    for(long i=0;i<N;i++) cin >> A[i];
    reverse(A, A+N);
    for(int i=0;i<N;i++){
        *upper_bound(dp, dp+N, A[i]) = A[i];
    }
    cout << lower_bound(dp, dp+N, INF) - dp;
    return 0;
}

Measured memory_bytes: 1792
//https://onlinejudge.u-aizu.ac.jp/#/problems/2331
//imos法
#include<vector>
#include<iostream>
#include<algorithm>
#define MAX_N 100010
using namespace std;
long long v[MAX_N];
long long ans[MAX_N];
int main()
{
	int K;//友達の総数
	cin >> K;
	for (long long i = 0; i < K; i++)
	{
		long long  a, b;
		cin >> a >> b;
		v[a] = v[a] + 1;
		v[b + 1]=v[b+1]-1;
		
	}
	for (long long i = 1; i < MAX_N ; i++)
	{
		v[i] = v[i] + v[i - 1];
	}
	long long x = 0;
	for (long long i = 0; i < MAX_N; i++)
	{
		
		if (i <= (v[i] + 1))
		{
			x = max(x, i);
		}
	}
	cout << x -1<< endl;
	
	return 0;
}



Measured memory_bytes: 3884
import sys
from collections import defaultdict

sys.setrecursionlimit(500000)

class Fraction:
    def gcd(self, a ,b):
        a,b = max(a,b),min(a,b)
        while a%b!=0:
            a,b = b,a%b
        return b

    def frac(self,a,b):
        if a==0 and b==0:
            return (0,0)
        elif a==0:
            return (0,1)
        elif b==0:
            return (1,0)
        else:
            d = self.gcd(abs(a),abs(b))
            if a<0:
                a = -a
                b = -b
            return (a//d,b//d)
    
    def __init__(self, a, b):
        self.value = self.frac(a,b)

    def v(self):
        return self.value

    def __lt__(self, other):
        assert self.value!=(0,0) and other.value!=(0,0), 'value (0,0) cannot be compared.'
        a,b = self.value
        c,d = other.value
        return a*d < b*c
    
    def __le__(self, other):
        assert self.value!=(0,0) and other.value!=(0,0), 'value (0,0) cannot be compared.'
        a,b = self.value
        c,d = other.value
        return a*d <= b*c

    def __eq__(self, other):
        a,b = self.value
        c,d = other.value
        return a==c and b==d

    def __ne__(self, other):
        a,b = self.value
        c,d = other.value
        return not (a==c and b==d)

    def __gt__(self, other):
        assert self.value!=(0,0) and other.value!=(0,0), 'value (0,0) cannot be compared.'
        a,b = self.value
        c,d = other.value
        return a*d > b*c

    def __ge__(self, other):
        assert self.value!=(0,0) and other.value!=(0,0), 'value (0,0) cannot be compared.'
        a,b = self.value
        c,d = other.value
        return a*d >= b*c

    def __add__(self, other):
        a,b = self.value
        c,d = other.value
        return Fraction(a*d + b*c, b*d)
        
    def __sub__(self, other):
        a,b = self.value
        c,d = other.value
        return Fraction(a*d - b*c, b*d)

    def __mul__(self, other):
        a,b = self.value
        c,d = other.value
        return Fraction(a*c, b*d)

    def __truediv__(self, other):
        a,b = self.value
        c,d = other.value
        return Fraction(a*d, b*c)
    
    def __neg__(self):
        a,b = self.value
        return Fraction(-a,b)
        
    def inv(self):
        return Fraction(1,1) / self

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())

    vec = [list(map(int,input().split())) for i in range(N)]

    arg = defaultdict(int)
    zero = 0
    for v in vec:
        if v[0] == 0 and v[1] == 0:
            zero += 1
        else:
            f = Fraction(v[0],v[1])
            arg[f.v()] += 1
            arg[(-f.inv()).v()] += 0

    pair = []
    fd = lambda : False

    checked_list = defaultdict(fd)
    for key in arg:
        if not checked_list[key]:
            inv = (-Fraction(*key).inv()).v()
            pair.append([arg[key],arg[inv]])
            checked_list[inv] = True

    mod = 1000000007

    ans = 1

    for p1,p2 in pair:
        ans *= pow(2,p1,mod) + pow(2,p2,mod) - 1
        ans %= mod

    ans += zero
    ans %= mod

    print((ans+mod-1)%mod)

if __name__ == '__main__':
    main()





Measured memory_bytes: 225108
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define int long long
#define F first
#define S second
using namespace std;
typedef long long ll;
ll n,m;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
ll num[105];
signed main()
{

    //ios_base::sync_with_stdio(0),cin.tie(0);
    while(cin>>n)
    {
        rep(i,n) cin>>num[i];
        double tmp=1;
        rep(i,n) tmp=tmp*num[i];
        double sum=0;
        rep(i,n) sum+=tmp/num[i];
        cout<<fixed<<setprecision(5)<<double(tmp/sum)<<"\n";
    }
    return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG //エラーを出すためのおまじない
#include <bits/stdc++.h>
using namespace std;
#define coYES cout << "YES" << endl
#define coNO cout << "NO" << endl
#define coYes cout << "Yes" << endl
#define coNo cout << "No" << endl
#define coyes cout << "yes" << endl
#define cono cout << "no" << endl
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  string s;
  cin >> s;
  int size = s.size();
  cout << s.at(0) << size-2 << s.at(size-1) << endl;
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  int A, B, C, X;
  cin >> A >> B >> C >> X;

  int ans = 0;
  REP(a,A+1) REP(b,B+1) REP(c,C+1)
	if(a*500+b*100+c*50 == X)
	  ++ans;
  cout << ans << endl;
  
  return 0;
}

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

bool bucket[26];

int main()
{
  string S;
  cin >> S;
  
  rep(i, S.size())
  {
    bucket[S[i] - 'a'] = true;
  }
  
  rep(i, 26)
  {
    if (false == bucket[i])
    {
      cout << (char)('a' + i) << endl;
      return 0;
    }
  }
  
  printf("None");

  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ar array
#define endl '\n'
#define ll long long
#define in insert
#define pb push_back
#define vt vector
#define P_Q(x) priority_queue<x>
#define p_q(x) priority_queue<x, vector<x>, greater<x>>
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(ll i=a;i>=b;i--)
#define FOR(m) Rep(i,1,m)
#define For(m) Rep(i,0,m-1)
#define Rbl(x,a) for(auto &x : a)
#define FIO ios::sync_with_stdio(0);   cin.tie(0);
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define vpii vector<pii>
#define vpll vector<pll>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define mod 1000000007
 
const int mxN = 1e5 + 1;
array<int, 3> a[mxN];
vt<array<int, 3>> dp(mxN);
ll n;
 
 
int main()
{
FIO
 
    cin >> n;
    FOR(n) cin >> a[i][0] >> a[i][1] >> a[i][2];
    dp[1] = a[1];
    Rep(i,2,n)
    {
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i][0];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + a[i][1];
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + a[i][2];
    }
    cout << max( dp[n][0], max(dp[n][1], dp[n][2]) ) << endl;
}

Measured memory_bytes: 5500
/**
 * Created by hiramekun at 20:44 on 2019-12-08.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    ll h, w;
    cin >> h >> w;
    int a[h][w], b[h][w];
    rep(i, h) rep(j, w) cin >> a[i][j];
    rep(i, h) rep(j, w) {
            cin >> b[i][j];
        }

    ll max_diff = 2 * 80 * 160;
    bool dp[h][w][max_diff];
    rep(i, h) rep(j, w) rep(l, max_diff) dp[i][j][l] = false;

    ll mid = max_diff / 2;
    dp[0][0][b[0][0] - a[0][0] + mid] = true;
    dp[0][0][-b[0][0] + a[0][0] + mid] = true;

    rep(i, h) {
        rep(j, w) {
            rep(l, max_diff) {
                if (dp[i][j][l]) {
                    if (i + 1 <= h - 1) {
                        dp[i + 1][j][l + b[i + 1][j] - a[i + 1][j]] = true;
                        dp[i + 1][j][l - b[i + 1][j] + a[i + 1][j]] = true;
                    }
                    if (j + 1 <= w - 1) {
                        dp[i][j + 1][l + b[i][j + 1] - a[i][j + 1]] = true;
                        dp[i][j + 1][l - b[i][j + 1] + a[i][j + 1]] = true;
                    }
                }
            }
        }
    }
    ll ans = ll_inf;
    rep(i, max_diff) {
        if (dp[h - 1][w - 1][i]) ans = min(ans, abs(i - mid));
    }
    cout << ans << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

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

N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = list(input())
score = {'r': P, 's': R, 'p': S}
ans = 0

for i in range(N):
    if i<K:
        ans += score[T[i]]
    else:
        if T[i]!=T[i-K]:
            ans += score[T[i]]
        else:
            T[i] = '?'
            
print(ans)

Measured memory_bytes: 49264
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const ll MOD = 1000000007;

/* --------------------------------------------------- */

int main() {
    int n;
    cin >> n;
    ll ans = 1;
    rrep(i, n) {
        ans *= i;
        ans %= MOD;
    }
    cout << ans << endl;

    return 0;
}

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

using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define lin "\n"
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(0)
#define mod 1000000007
#define PI 2 * acos(0.0)

void solve() {
    ll n;
    cin >> n;
    ll ans = 0;
    ll x = 1;
    for (int i = 1; i <= n; ++i) {
        x = 10 * x % mod;
    }
    ans += (x % mod);
    x = 1;
    for (int i = 1; i <= n; ++i) {
        x = 9 * x % mod;
    }
    ans = ans - (x % mod);
    if (ans < 0) {
        ans += mod;
    }
    ans = ans - (x % mod);
    if (ans < 0) {
        ans += mod;
    }
    x = 1;
    for (int i = 1; i <= n; ++i) {
        x = 8 * x % mod;
    }
    ans += (x % mod);
    cout << ans % mod << lin;
}

int main() {
    fast_io;
    int t = 1;
//    cin >> t;
//    scanf("%d", &t);
    int c = 1;
    while (t--) {
//        printf("Case %lld:\n", c);
//        cout << "Case " << c << ":\n";
        solve();
        c++;
    }
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<int> P(n); rep(i, n) cin >> P[i];
  vector<ll> A(n), B(n);
  ll d = ((ll)1e+9-20005) / (n-1);
  rep(i, n) {
    A[i] = B[n-1-i] = 1+d*i;
  }
  rep(i, n) {
    P[i]--;
    B[P[i]] += i;
  }
  rep(i, n) cout << A[i] << ' '; cout << endk;
  rep(i, n) cout << B[i] << ' '; cout << endk;
  return 0;
}


Measured memory_bytes: 3664
def selection_sort(A, N):
    c = 0
    for i in range(N):
        minj = i
        for j in range(i, N):
            if A[j] < A[minj]:
                minj = j
 
        if i != minj:
            A[i], A[minj] = A[minj], A[i]
            c += 1
    print " ".join(map(str, A))
    print c


n = int(raw_input())
A = map(int, raw_input().split())

selection_sort(A, n)

Measured memory_bytes: 6460
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> num(n);
  for(int i = 0; i < n; i++) {
    cin >> num.at(i);
  }
  int max = 0;
  for(int i = 0; i < n; i++) {
    if(max < num.at(i)) max = num.at(i);
  }
  int minp = 100000000;
  for(int j = 0; j <= max; j++) {
    int point = 0;
    for(int i = 0; i < n; i++) {
      point += pow(num.at(i) - j,2);
    }
    if(point < minp) minp = point;
  }
  cout << minp << endl;
}




Measured memory_bytes: 256
n,m=[int(x) for x in input().rstrip().split()]
A=[int(input()) for i in range(m)]
mod=10**9+7
dp=[0 for i in range(n+10)]
no=[True for i in range(n+10)]
for i in A:
  no[i]=False


if no[1]==True:
  dp[1]=1
dp[0]=1
for i in range(2,n+1):
  if no[i]==True:
    dp[i]=dp[i-1]+dp[i-2]

print(dp[n]%mod)

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

using ll = long long;

const int MAXN = 1010;
int N[3];
int K;

ll A[3][MAXN];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	for (int i = 0; i < 3; i++) cin >> N[i];
	cin >> K;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < N[i]; j++) {
			cin >> A[i][j];
		}
		sort(A[i], A[i] + N[i], greater<ll>());
	}

	using state = pair<ll, array<int, 3>>;
	priority_queue<state> q;
	q.push(make_pair(A[0][0]+A[1][0]+A[2][0], array<int, 3>({0, 0, 0})));		
	set<array<int, 3>> vis = {array<int, 3>{0, 0, 0}};
	for (int z = 0; z < K; z++) {
		assert(!q.empty());
		auto p = q.top();
		q.pop();
		cout << p.first << '\n';
		for (int i = 0; i < 3; i++) {
			if (p.second[i] == N[i]-1) continue;
			auto np = p;
			np.first += A[i][p.second[i]+1] - A[i][p.second[i]];
			np.second[i]++;
			if (vis.count(np.second)) continue;
			vis.insert(np.second);
			q.push(np);
		}
	}

	return 0;
}


Measured memory_bytes: 1024
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int N = Integer.parseInt(sc.next());
        int K = Integer.parseInt(sc.next());
        
        int num = 1;
        for(int i=0; i<N; i++){
            if(num*2 < num+K){
                num = num*2;
            }else{
                num = num+K;
            }
        }
        
        System.out.println(num);
    }
}

Measured memory_bytes: 21844
#include<iostream>
#include<vector>
using namespace std;
const int INF = 1 << 28;

int main()
{
  int s, d, m;
  vector< int > w[100], p[100];
  int dp[301];

  while(cin >> s >> d >> m){
    for(int i = 0; i < s; i++){
      int k;
      cin >> k;
      w[i].resize(k), p[i].resize(k);
      for(int j = 0 ; j < k; j++){
        cin >> w[i][j] >> p[i][j];
      }
    }
    fill_n( dp, m + 1, 0);
    for(int i = 0 ; i < d ; i++ ){
      int f;
      cin >> f;
      for(int j = 0 ; j < w[f].size(); j++){
        for(int k = m ; k - p[f][j] >= 0; k--){
          dp[k] = max( dp[k], dp[k - p[f][j]] + w[f][j]);
        }
      }
    }

    int pos = 0;
    for(int i = 0 ; i <= m ; i++ ){
      if( dp[i] > dp[pos] ) pos = i;
    }
    cout << dp[pos] << " " << pos << endl;
  }
}

Measured memory_bytes: 1288
#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(){
    double w, h, x, y;
    cin >> w >> h >> x >> y;
    double s = w*h/2.0;
    printf("%.10f ",s);
    if(w/2.0 == x && h/2.0 == y) cout << 1;
    else cout << 0;
}

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

int main() {
  int64_t a, b, k;
  cin >> a >> b >> k;
  if(a > k) {
    a-=k;
  }
  else if (a + b > k) {
    b -= k - a;
    a = 0;
  }
  else {
    a = 0;
    b = 0;
  }
  cout << a << " " << b << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define FAST_IO ios::sync_with_stdio(false)
using namespace std;
int x,y,a[1000000],vis[1000000];
vector <int> E[123456];
long long ans,maxx,max1,n,m,cnt,maxt;
void solve(int x)
{
	vis[x]=1;
	if (a[x]<maxx)
	  maxx=a[x],maxt=x;
   for(int i=0;i<E[x].size();i++){
        int u=E[x][i];
		if(!vis[u]) solve(u);
	}
	return;
}
int main()
{
	FAST_IO;
	cin>>n>>m;
	for (int i=1;i<=n;i++)
      cin>>a[i];
  
    for (int i=1;i<=m;i++)
    {
	
      cin>>x>>y;
      x++;
      y++;
      E[x].push_back(y);
      E[y].push_back(x);
    }
   
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;i++)
    {
    	maxx=2000000000;
    	maxt=0;
    	if (vis[i]==0)
         cnt++,solve(i),ans+=maxx; 
 
        
        a[maxt]=2000000001;
	}
	 if(cnt==1) {printf("0\n");return 0;}
	if (cnt*2-2>n) 
	{
	cout<<"Impossible";
	return 0;
    }
	sort(a+1,a+n+1);
	for (int i=1;i<=cnt-2;i++)
	{
		ans+=a[i];
		if (a[i]==2000000001)
		  {
		  	cout<<"Impossible";
	return 0;
		  }
	}
	cout<<ans;
	return 0;
} 


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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

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

    if ((a == 1 && b == 2) || (a == 2 && b == 1))
    {
        cout << 3;
    }
    else if ((a == 2 && b == 3) || (a == 3 && b == 2))
    {
        cout << 1;
    }
    else
    {
        cout << 2;
    }
}


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

int main(int argc, char const *argv[]) {
  string num;
  while (cin >> num && num[0] != '0') {
    int sum = 0;
    for (int i = 0; i < num.size(); i++) {
      sum += (num[i] - '0');
    }
    cout << sum << endl;
  }
  return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;
const ll MOD = 1000000007;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

ll n;
vector<ll> d;

bool solve(ll k) {
	ll abc = 0, arc = 0;
	for (auto v : d) {
		if (v >= k) {
			arc++;
		} else {
			abc++;
		}
	}

	return abc == arc;
}

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

	cin >> n;

	d.resize(n);
	for (auto &v : d) {
		cin >> v;
	}
	sort(begin(d), end(d));
	cout << d[n / 2] - d[n / 2 - 1] << endl;
	return 0;
}


Measured memory_bytes: 1024
// Daniel Grzegorzewski
// while (clock()<=69*CLOCKS_PER_SEC)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")

#define MP make_pair
#define PB push_back
#define ST first
#define ND second

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//X.find_by_order(k); - zwraca iterator na k-ty element (numeracja od zerowego)
//X.order_of_key(k); - zwraca liczbę elementów ostro mniejszych niż k

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}

int s, w;

int main() {
  init_ios();
  cin >> s >> w;
  if (w >= s)
    cout<<"unsafe\n";
  else
    cout<<"safe\n";
}

Measured memory_bytes: 3644
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.solve();
    }
    public void solve() throws Exception {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int W = scan.nextInt();
        int[] w = new int[N];
        long[] v = new long[N];
        for (int i = 0; i < N; i++) {
            w[i] = scan.nextInt();
            v[i] = scan.nextInt();
        }
        long[] dp = new long[W+1];
        Arrays.fill(dp, Long.MIN_VALUE);
        dp[0] = 0;
        for (int i = 0; i < N; i++) {
            long[] next_dp = new long[W+1];
            for (int j = 0; j <= W; j++) {
                next_dp[j] = Math.max(next_dp[j], dp[j]);
                if (dp[j] == Long.MIN_VALUE) {
                    continue;
                }
                if (j + w[i] <= W) {
                    next_dp[j + w[i]] = Math.max(next_dp[j + w[i]], dp[j] + v[i]);
                }
            }
            dp = next_dp;
        }
        System.out.println(Arrays.stream(dp).max().getAsLong());
    }
}


Measured memory_bytes: 59988
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pr;
const ll mxn = 3e3+5;
const ll mxm = 1e6+5;
const ll INF = 0x3f3f3f3f;
const ll mod = 1e9+7;
const double eps = 1e-7;
#define int ll
#define mpr make_pair
int gcd(int x,int y){if(y==0) return x; else return gcd(y,x%y);}
int qpow(int a,int b){int ans=1; while(b){ if(b&1) ans=ans*a%mod; b>>=1; a=a*a%mod; } return ans;}
int lowbit(int x){return (x&(-x));}
int qmul(int a,int b){int ans=0; while(b){ if(b&1) ans=(ans+a)%mod; b>>=1; a=(a+a)%mod; } return ans; }

int _get(int x){
    int ans=0;
    while(x){
        x/=10;
        ans++;
    }
    return ans;
}


signed main(void){
    int s;
    cin>>s;
    if(s<=1e9){
        printf("%lld %lld %lld %lld %lld %lld",1LL,0LL,0LL,0LL,0LL,s);
    }
    else if(s==1000000000000000000LL){
        printf("%lld %lld %lld %lld %lld %lld",1000000000LL,0LL,0LL,0LL,0LL,1000000000LL);
    }
    else{
        int wei=_get(s);
        int tmp=1LL;
        for(int i=1;i<=wei/2;i++){
            tmp*=10LL;
        }
//        cout<<tmp;

            int a=s/tmp,c=s%tmp;
//            printf("a=%lld tmp=%lld c=%lld\n",a,tmp,c);
//            int divvv = (int) sqrt(c),d;
//            if(c!=0)
//            {
//                for(;divvv>=1;divvv--){
//                    if(c%divvv==0) break;
//                }
//                int d=c/divvv;
//            }
//            else{
//                divvv=0,d=0;
//            }
//        printf("%lld %lld %lld %lld %lld %lld",a+divvv,0LL,0LL,0LL,divvv+d,tmp+divvv);
        printf("%lld %lld %lld %lld %lld %lld",a+1,c,1LL,0LL,0LL,tmp);
    }
}


Measured memory_bytes: 256
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

trait Joinable {
    fn join(self, sep: &str) -> String;
}

impl<U: ToString, T: Iterator<Item = U>> Joinable for T {
    fn join(self, sep: &str) -> String {
        self.map(|x| x.to_string()).collect::<Vec<_>>().join(sep)
    }
}

fn gcd(a: usize, b: usize) -> usize {
    match (a, b) {
        (a, 0) => a,
        (a, b) => gcd(b, a % b),
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let N: usize = sc.get();
    let A: Vec<usize> = sc.vec(N);
    let mut head_cum = vec![0; N+1];
    for i in 0..N {
        head_cum[i+1] = gcd(head_cum[i], A[i]);
    }
    let mut tail_cum = vec![0; N+1];
    for i in (0..N).rev() {
        tail_cum[i] = gcd(tail_cum[i+1], A[i]);
    }
    let mut ans = 0;
    for i in 0..N {
        ans = max(ans, gcd(head_cum[i], tail_cum[i+1]));
    }
    println!("{}", ans);
}


Measured memory_bytes: 6396
/* ex3_2 KitamoriFumiya */
#include <stdio.h>

int main(void){
	int pencil, ones_place; // pencil(鉛筆の本数), ones_place(1の位)をint型の変数として宣言
	scanf("%d", &pencil); // pencilを入力
	ones_place = pencil % 10; // 1の位を鉛筆の本数を10で割った余りとして計算
	
	// もし1の位が2, 4, 5, 7, 9ならhonを出力
	if (ones_place == 2 | ones_place == 4 | ones_place == 5 | ones_place == 7 | ones_place == 9){
		printf("hon\n");
	}
	
	// もし1の位が0, 1, 6, 8ならponを出力
	if (ones_place == 0 | ones_place == 1 | ones_place == 6 | ones_place == 8){
		printf("pon\n");
	}
	
	// もし1の位が3ならbonを出力
	if (ones_place == 3){
		printf("bon\n");
	}
	return 0;
}

Measured memory_bytes: 1600
#include<stdio.h>
#include<math.h>

int main(){
  int n;

  scanf("%d",&n);

  while(n>0){
    double x[3],y[3];
    double px,py,r;
    int i;

    for(i=0;i<3;i++){
      scanf("%lf %lf",&x[i],&y[i]);
    }

    px=((x[1]*x[1]-x[0]*x[0]+y[1]*y[1]-y[0]*y[0])*(y[2]-y[0])-
       (x[2]*x[2]-x[0]*x[0]+y[2]*y[2]-y[0]*y[0])*(y[1]-y[0]))/
      (2*((x[1]-x[0])*(y[2]-y[0])-(x[2]-x[0])*(y[1]-y[0])));
    py=((x[1]*x[1]-x[0]*x[0]+y[1]*y[1]-y[0]*y[0])*(x[2]-x[0])-
       (x[2]*x[2]-x[0]*x[0]+y[2]*y[2]-y[0]*y[0])*(x[1]-x[0]))/
      (2*((x[2]-x[0])*(y[1]-y[0])-(x[1]-x[0])*(y[2]-y[0])));
    r=sqrt((px-x[0])*(px-x[0])+(py-y[0])*(py-y[0]));

    printf("%.3f %.3f %.3f\n",px,py,r);
    n--;
  }

  return 0;
}

Measured memory_bytes: 664
import sys
nums, alice, borys = map(int,input().split())
if nums == 2:
    print("Borys")
    sys.exit()

if alice > borys:
    space = alice - borys-1
else:
    space = borys - alice-1

if space % 2 == 0:
    print("Borys")
elif space % 2 == 1:
    print("Alice")

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

using namespace std;

int main() {
	int n, l;
	cin >> n >> l;
	int ans = l;
	for (int i = 0; i < n; i++) {
		if (abs(l + i) < abs(ans)) {
			ans = l + i;
		}
	}
	cout << l * n + (n - 1) * n / 2 - ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
int mod(ll a){
    int c=a%1000000007;
    if(c>=0)return c;
    else return c+1000000007;
}
typedef pair<int,int> i_i;


int main(){
    int n,y;cin>>n>>y;
    y=y/1000;
    int a[3];for(int i=0;i<=2;i++)a[i]=0;
    int count=y%5+y/5;
    a[1]=y/5;
    a[2]=y%5;
    if(count==n);
    else if(count>n){
        int l=count-n;
        a[1]-=2*l;
        a[0]+=l;
    }else{
        int l=n-count;
        a[1]-=(l+3)/4;
        a[2]+=((l+3)/4)*5;
        if(l%4!=0){
            a[1]-=(4-l%4)*2;
            a[0]+=4-l%4;
        }
    }
    if(a[0]>=0&&a[1]>=0&&a[2]>=0&&a[0]+a[1]+a[2]==n)cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
    else cout<<"-1 -1 -1"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main(){
	bool ret = false;
	string s, p;
	cin >> s;
	cin >> p;

	for(int i = 0; i < s.length(); ++i){
		string str = s.substr(i, p.length());
		if(s.length() - i < p.length()){
			str += s.substr(0, p.length() - (s.length() - i));
		}
		if(0 == str.compare(p)){
			ret = true;
			break;
		}
	}

	cout << ((true == ret) ? "Yes" : "No") << endl;
	return 0;
}



Measured memory_bytes: 3208
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<stack>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;

int main() {
	int n, a[105] = {0}, sum = 0;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	sum /= n;
	int ans1 = 0, ans2 = 0;
	for(int i = 0; i < n; i++) {
		ans1 += (sum - a[i]) * (sum - a[i]);
	}
	sum++;
	for(int i = 0; i < n; i++) {
		ans2 += (sum - a[i]) * (sum - a[i]);
	}
	cout << min(ans1, ans2) << '\n';
	return 0;
}


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

int main(){
    ll X; cin >> X;
    if(X > 2100) cout << 1 << endl;
    else{
        int t = X / 100;
        if(t * 5 >= (X % 100)){
            cout << 1 << endl;
        }else{
            cout << 0 << endl;
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int main(int argc, char *argv[])
{
  int a,b;
  cin>>a>>b;
  if (a * b % 2 == 0)
    cout<<"No"<<endl;
  else
    cout<<"Yes"<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)
  val n = sc.nextInt
  val a = List.fill[Long](n)(sc.nextLong)
  val s = a.scanRight(0L)((x, y) => (x + y) % 1000000007L).drop(1)
  println(a.zip(s).foldLeft[Long](0L)((x, y) => (x + y._1 * y._2) % 1000000007L))
}


Measured memory_bytes: 92140
from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)

MOD = 10**9 + 7

def rec(vNow, vPar):
    W, B = 1, 1
    for v2 in adjL[vNow]:
        if v2 == vPar: continue
        W2, B2 = rec(v2, vNow)
        W = (W * (W2+B2)) % MOD
        B = (B * W2) % MOD
    return (W, B)

N = int(input())
adjL = [[] for v in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    adjL[x-1].append(y-1)
    adjL[y-1].append(x-1)

print(sum(rec(0, -1)) % MOD)


Measured memory_bytes: 100112
/* You lost the game. */

#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <numeric>
#include <cassert>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <vector>

#define fin(i,n) for (int i = 0; i < n; i++)
#define fin2(i,a,b) for (int i = a; i < b; i++)

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define mod 1000000009

#define si(n) scanf("%d", &n)
#define sii(n,m) scanf("%d %d", &n, &m)
#define siii(n,m,k) scanf("%d %d %d", &n, &m, &k)
#define sl(n) scanf("%lld", &n)
#define sll(n,m) scanf("%lld %lld", &n, &m)
#define slll(n,m,k) scanf("%lld %lld %lld", &n, &m, &k)
#define ss(s) scanf("%s", s)
#define sai(t,n) fin(i,n) { scanf("%d", &t[i]); }
#define sal(t,n) fin(i,n) { scanf("%lld", &t[i]); }

#define pi(n) printf("%d\n", n)
#define pc(n) printf("%c\n", n)
#define ps(s) printf("%s\n", s);
#define pii(n,m) printf("%d %d\n", n, m)
#define pl(n) printf("%lld\n", n)
#define pll(n,m) printf("%lld %lld\n", n, m)
#define pai(t,n) fin(i,n) { printf("%d ", t[i]); } printf("\n"); 
#define pal(t,n) fin(i,n) { printf("%lld ", t[i]); } printf("\n"); 

#define L long long int
#define D double
#define PII pair<int, int>
#define VPII vector<PII>
#define VL vector<L>
#define VI vector<int>
#define VVI vector<VI>

using namespace std;


int main() {
    int arbre[10][10] = {0};
    int n, m, u, v;
    sii(n, m);
    fin(i, m) {
        sii(u, v);
        u--; v--;
        arbre[u][v] = 1;
        arbre[v][u] = 1;
    }
    int tab[] = {0, 1, 2, 3, 4, 5, 6, 7};
    int res = 0, div = 1;
    fin(i, 9-n) { div *= (i+1); }
    do {
        int ok = 1;
        fin(i, n-1) {
            if (arbre[tab[i]][tab[i+1]] == 0) { ok = 0; break; }
        }
        if (ok == 1) { res++; }
    } while ( next_permutation(tab+1,tab+n) );
    pi(res);
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int reg[5][4][11];
    for(int i=1;i<=4;i++){
        for(int j=1;j<=3;j++){
            for(int k=1;k<=10;k++){
                reg[i][j][k]=0;
            }
        }
    }
    for(int i=0;i<n;i++){
        int b,f,r,v;
        cin>>b>>f>>r>>v;
        reg[b][f][r]+=v;
    }
    for(int i=1;i<=4;i++){
        for(int j=1;j<=3;j++){
            for(int k=1;k<=10;k++){
                cout<<" "<<reg[i][j][k];
            }
            cout<<endl;
        }
        if(i==1 ||i==2 ||i==3) cout<<"####################"<<endl;

    }
}



Measured memory_bytes: 3092
c1 = input()
c2 = input()
c3 = input()

counter = 0
f = None
s = None
t = None
for first, second, third in zip(c1, c2, c3):
  if counter == 0:
    f = first
    counter += 1
    continue
  if counter == 1:
    s = second
    counter += 1
    continue
  if counter ==2 :
    t = third
    
ans = f + s + t
print(ans)

Measured memory_bytes: 3064
#include<cstdio>
#include<algorithm>
using namespace std;
int x,y,a,b,k;
int tme(int x,int y){return 60*x+y;}
int main()
{
	scanf("%d%d%d%d%d",&x,&y,&a,&b,&k);
	printf("%d\n",tme(a,b)-tme(x,y)-k);
	return 0;
}

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


vector< vector<char> >V,C;
int count=0;

bool in(int x,int y){
	return x>=0 && y>=0 && x<6 && y<12;
}

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

void kesu(int x,int y,char col){
	if(C[y][x]!=col){
		if(C[y][x]=='O')
			C[y][x]='.';
		return;
	}
	count++;
	C[y][x]='.';
	for(int d=0;d<4;d++){
		if(in(x+dx[d],y+dy[d]))
			kesu(x+dx[d],y+dy[d],col);
	}
}

void otosu(){
	for(int y=10;y>=0;y--){
		for(int x=0;x<6;x++){
			if(V[y][x]=='.')
				continue;
			int ty=y;
			char temp=V[y][x];
			V[y][x]='.';
			while(ty<=11 && V[ty][x]=='.')
				ty++;
			ty--;
			V[ty][x]=temp;
		}
	}
}

void print(){
	for(int y=0;y<12;y++){
		for(int x=0;x<6;x++){
			cout<<V[y][x];
		}
		cout<<endl;
	}
}


void solve()
{
	V.clear();
	V.resize(12,vector<char>(6));
	for(int y=0;y<12;y++){
		string now;
		cin>>now;
		for(int x=0;x<6;x++)
			V[y][x]=now[x];
	}
	bool update=true;
	int res=-1;
	while(update){
		update=false;
		res++;
		for(int y=0;y<12;y++){
			for(int x=0;x<6;x++){
				if(V[y][x]=='.' || V[y][x]=='O')
					continue;

				count=0;
				C=V;
				kesu(x,y,V[y][x]);
				if(count>=4){
					V=C;
					update=true;
				}
			}
		}
		otosu();
	}
	cout<<res<<endl;
}

int main(){
	int t;
	cin>>t;
	for(int i=0;i<t;i++)
		solve();
	return 0;
}

Measured memory_bytes: 0
//　静かな海
#include <bits/stdc++.h>
using namespace std; typedef long long ll;

inline ll rd() {
  ll x=0,c,f=1;while(!isdigit(c=getchar()))if(c=='-')f=-1;
  for(;isdigit(c);c=getchar())x=x*10+c-'0';return x*f;
}
const int N = 2e5+3;

ll n, a[N], b[N], ans = 0;

int main() {
  n = rd();
  for (int i = 1; i <= n; i++) a[i] = rd(), b[i] = b[i-1] ^ a[i], a[i] += a[i-1];
  for (int l = 1, r = 0; r <= n; r++) {
    for (; (a[r]-a[l-1]) ^ (b[r]^b[l-1]); l++);
    ans += r - l + 1;
  } cout << ans << endl;
}

Measured memory_bytes: 3456
#include<bits/stdc++.h>
 
using namespace std;
#define MAXN   1000001 
  
// stores smallest prime factor for every number 
int spf[MAXN]; 
  
// Calculating SPF (Smallest Prime Factor) for every 
// number till MAXN. 
// Time Complexity : O(nloglogn) 
void sieve() 
{ 
    spf[1] = 1; 
    for (int i=2; i<MAXN; i++) 
  
        // marking smallest prime factor for every 
        // number to be itself. 
        spf[i] = i; 
  
    // separately marking spf for every even 
    // number as 2 
    for (int i=4; i<MAXN; i+=2) 
        spf[i] = 2; 
  
    for (int i=3; i*i<MAXN; i++) 
    { 
        // checking if i is prime 
        if (spf[i] == i) 
        { 
            // marking SPF for all numbers divisible by i 
            for (int j=i*i; j<MAXN; j+=i) 
  
                // marking spf[j] if it is not  
                // previously marked 
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
} 
  
// A O(log n) function returning primefactorization 
// by dividing by smallest prime factor at every step 
vector<int> get(int x) 
{ 
    vector<int> ret; 
    while (x != 1) 
    { 
        ret.push_back(spf[x]); 
        x = x / spf[x]; 
    } 
    return ret; 
}
int main()
{
ios_base::sync_with_stdio(false);
    cin.tie(NULL);
int n;
cin>>n;
int a[n];
sieve();
map<int,int>mp;
for(int i=2;i<MAXN;i++)
{
	if(spf[i]==i)mp[i]++;
}
for(int i=0;i<n;i++)
{
	cin>>a[i];
	vector<int>p= get(a[i]);
	set<int>s;
	for(int j=0;j<p.size();j++)
	{
		s.insert(p[j]);
	}
	for(auto x : s)
	{
		mp[x]++;
	}
}
bool flag=true;
for(auto x:mp)
{
	if(x.second>2)flag=false;
}
if(flag)
{
	cout<<"pairwise coprime";
    return 0;
}
else{
	int x=a[0];
	for(int i=0;i<n-1;i++)
	{
		x=__gcd(x,a[i+1]);
	}
	if(x==1)
	{
		cout<<"setwise coprime";

	}
	else{
		cout<<"not coprime";
	}
}


}

 
 

 


Measured memory_bytes: 15088
#include <cstdio>
#include <iostream>
#include <string>

using namespace std;
const int MAXN = 1e6+10;
int n,a[MAXN],r_levo[MAXN],l_desno[MAXN];
string s;
int main()
{
	cin>>s;

	r_levo[0] = 0;
	for (int i = 1;i<s.length();i++)
	{
		if (s[i] == 'R')r_levo[i] = 0;
		else r_levo[i] = r_levo[i-1] + 1;
	}

	l_desno[s.length()-1] = 0;
	for (int i = s.length()-1;i>=0;i--)
	{
		if (s[i] == 'L')l_desno[i] = 0;
		else l_desno[i] = l_desno[i+1] + 1;
	}

	for (int i = 0;i<s.length();i++)
	{
		if (s[i] == 'R')
		{
			int x = l_desno[i];
			if (x%2==0)a[x+i]++;else a[x-1+i]++;
		}else
		{
			int x = r_levo[i];
			if (x%2==0)a[i-r_levo[i]]++;else a[i-r_levo[i]+1]++;
		}
	}

	for (int i = 0;i<s.length();i++)printf("%d ",a[i]);printf("\n");
	
	return 0;
}

Measured memory_bytes: 9216