akhauriyash/Code-Regression huggingface dataset:
#if defined(LOCAL)
const double _max_double_error = 1e-9;
#include "testutils.h"
#define L(x...) (debug(x, #x))
#define I(x, ...) (x)
#define C(x...) CHECK(x)
#else
#define L(x, ...) (x)
#define I(x, ...) (x)
#define C(x, ...) ;
#endif
#include <algorithm>
#include <vector>
#include <string>
#include <iomanip>
#include <iostream>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <math.h>
#include <limits>
#include <numeric>
#include <queue>
#include <memory>

using namespace std;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using ii = pair<int,int>; using lu = unsigned long long; using l = long long;
using vs = vector<string>; using vii = vector<ii>;
using vl = vector<l>; using vvl = vector<vl>; using vvvl = vector<vvl>;
using ll = pair<l,l>; using vll = vector<ll>; using vvll = vector<vll>;
using vb = vector<bool>; using vvb = vector<vb>;
using vd = vector<double>; using vvd = vector<vd>;
using mll = unordered_map<l, l>; using sl = unordered_set<l>;
const l INF = numeric_limits<l>::max();
const double EPS = 1e-10; const double PI = M_PI;
const l e0=1, e3=1000, e5=100000, e6=10*e5, e7=10*e6, e8=10*e7, e9=10*e8;
const char lf = '\n';
#define all(x) begin(x), end(x)
#define F(a,b,c) for (l a = l(b); a < l(c); a++)
#define B(a,b,c) for (l a = l(c) - 1; a >= l(b); a--)
#define VVL(x, a, b, i) vvl x(a, vl(b, l(i)));
#define VVVL(x, a, b, c, i) vvvl x(a, vvl(b, vl(c, l(i))));

void solve(istream& in, ostream& out);
int main(int argc, char **argv) {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(15);
#if defined(LOCAL)
  tst::test_init(argc, argv);
  // _generate_random_test = generate_random;
  // _solve_brute = solve_brute;
  // _player_b = player_b;
  // _custom_solution_checker = solution_checker;
  tst::maybe_run_tests(cin, cout);
#else
  solve(cin, cout);
#endif
}
const l MOD = e9 + 7; // end of template

void solve(istream& in, ostream& out) {
  l n; in >> n;
  F(i, 1, 10) if (111 * i >= n) {
    out << 111 * i << lf;
    break;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cassert>
using namespace std;

// v----- Input -----v
struct Edge {
	int to;
	int dist;
};

int n, m;
vector< vector< Edge > > edge;
int T_MAX;
vector< int > dst;
// ^----- Input -----^

// v----- Shortest Path Management -----v
int len_uv[402][402];
int dist_st[402][402];
int next_st[402][402];

int getLen(int u, int v) { return len_uv[u][v]; }
int getDist(int s, int t) { return dist_st[s][t]; }
int getNext(int s, int t) { return next_st[s][t]; }

void findShortestPaths() {
	struct State {
		int v;
		int dist;
		bool operator > (const State& o) const { return dist > o.dist; }
	};
	
	memset(len_uv, -1, sizeof(len_uv));
	memset(dist_st, -1, sizeof(dist_st));
	memset(next_st, -1, sizeof(next_st));
	
	for (int v=0; v<n; ++v) {
		for (const Edge& e : edge[v]) {
			len_uv[v][e.to] = e.dist;
		}
	}
	
	for (int s=0; s<n; ++s) {
		priority_queue< State, vector< State >, greater< State > > que;
		que.push(State{s, 0});
		dist_st[s][s] = 0;
		
		while (!que.empty()) {
			State sta = que.top(); que.pop();
			if (dist_st[s][sta.v] < sta.dist) continue;
			for (const Edge& e : edge[sta.v]) {
				if (dist_st[s][e.to] == -1 || dist_st[s][e.to] > sta.dist + e.dist) {
					dist_st[s][e.to] = sta.dist + e.dist;
					next_st[e.to][s] = sta.v;
					que.push(State{e.to, dist_st[s][e.to]});
				}
			}
		}
	}
}
// ^----- Shortest Path Management -----^

// v----------------------------------- Solver -----------------------------------v

void COMMAND_STAY() { cout << -1 << endl; }
void COMMAND_MOVE(int w) { cout << w+1 << endl; }

void putOrder(vector< vector< int > >& order_que, int t1, int t2) {
	for (int t=t1; t<=t2; ++t) {
		if (dst[t] >= 0) {
			order_que[dst[t]].push_back(t);
		}
	}
}

void solve() {
	int cur_v = 0, tar_v = -1, len = 0, prev_put_t = 0;
	vector< vector< int > > order_que(n, vector< int >());
	
	for (int t=0; t<T_MAX; ++t) {
		if (cur_v == 0 && len == 0) { // put
			putOrder(order_que, prev_put_t, t);
			prev_put_t = t+1;
		}
		
		// decide target
		if (tar_v == -1) {
			tar_v = 0;
			int min_value = 1L << 30;
			for (int v=1; v<n; ++v) {
				int value = getDist(cur_v, v);
				if (!order_que[v].empty() && min_value > value) {
					tar_v = v;
					min_value = value;
				}
			}
		}
		
		if (cur_v == tar_v) {
			COMMAND_STAY();
			tar_v = -1;
		}
		else {
			int nxt_v = getNext(cur_v, tar_v);
			if (len == 0) len = getLen(cur_v, nxt_v);
			COMMAND_MOVE(nxt_v);
			--len;
			if (len == 0) cur_v = nxt_v;
			if (cur_v == tar_v) {
				order_que[tar_v].clear();
				tar_v = -1;
			}
		}
	}
}

// ^----------------------------------- Solver -----------------------------------^

int main() {
	cin >> n >> m;
	edge.assign(n, vector< Edge >());
	for (int i=0; i<m; ++i) {
		int u, v, d;
		cin >> u >> v >> d;
		--u; --v;
		edge[u].push_back(Edge{v, d});
		edge[v].push_back(Edge{u, d});
	}
	findShortestPaths();
	
	cin >> T_MAX;
	dst.assign(T_MAX, -1);
	for (int i=0; i<T_MAX; ++i) {
		int N_new;
		cin >> N_new;
		for (int j=0; j<N_new; ++j) {
			int id, v;
			cin >> id >> v;
			--v;
			dst[i] = v;
		}
	}
	
	solve();
}

Measured memory_bytes: 2304
#include <iostream>
#include <cstring>
#include <set>
#include <stack>
#include <list>
#include <vector>
#include <map>
#include <math.h>
#include <algorithm>

typedef long long ll;
using namespace std;

int main(){
    ll N, K;
    cin >> N >> K;
    ll a[N+1];
    ll dp[N+1];

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

    dp[0]=0;
    dp[1]=0;
    for(int i=2; i<=N; i++){
        dp[i] = 0x3f3f3f3f;
    }

    for(int i=2; i<=N; i++){
        for(int j=i-1; j>= max(1ll, i-K);j--){
            dp[i] = min(dp[i], dp[j] + abs(a[i]-a[j]));
        }
    }

    cout << dp[N];
    return 0;
}

Measured memory_bytes: 1792
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
using ll = long long;

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

int main () {
  int a, b;
  cin >> a >> b;
  if (5>=a)
    cout << 0;
  else if (a<=12)
    cout << b/2;
  else
    cout << b;
  
  return 0;
}


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

using namespace std;

int main()
{
    string first, second;
    cin >> first >> second;

    vector< vector<int> >
        EditD(first.length() + 1, vector<int>(second.length() + 1, 0));

    for (size_t i = 0; i <= first.length(); ++i) {
        EditD[i][0] = i;
    }
    for (size_t i = 0; i <=second.length(); ++i) {
        EditD[0][i] = i;
    }
    for (size_t i = 1; i <= first.length(); ++i) {
        for (size_t j = 1; j <= second.length(); ++j) {
            if (first[i-1] == second[j-1]) {
                EditD[i][j] = EditD[i-1][j-1];
            } else {
                EditD[i][j] =
                    1 + min(EditD[i-1][j],
                            min(EditD[i][j-1],
                                EditD[i-1][j-1]));
            }
        }
    }
    cout << EditD[first.length()][second.length()] << endl;
}



Measured memory_bytes: 6876
def collatz(n)
  n.odd? ? 3*n+1 : n/2
end

s=gets.to_i
i=1
h={}
h[s]=i
while true
  i+=1
  s=collatz(s)
  if h[s]
    puts i
    exit
  else
    h[s]=i
  end
end

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

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define INF  numeric_limits<int>::max()
#define NINF numeric_limits<int>::min()

using namespace std;
using ll = long long;

int A, B, C;

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

    std::cin >> A >> B >> C;

    if(B / A > C) {
        std::cout << C << std::endl;
    }
    else {
        std::cout << B / A << std::endl;
    }

    return 0;
}



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

typedef long long int ll;
ll powk(ll a, ll n){
    ll r = 1;
    for(ll i = 0;i < n;i++){
        r *= a;
    }

    return r;
}

int main()
{
    vector<vector<ll>> c(3,vector<ll>(3));
    vector<ll> ans(2);
    for(ll i = 0;i < 3;i++){
        for(ll j = 0;j < 3;j++){
            cin >> c[i][j];
        }
    }

    for(ll i = 0;i < 2;i++){
        ans[i] = c[0][i] - c[0][i + 1];
    }

    for(ll i = 0;i < 3;i++){
        vector<ll> t(2);
        for(ll j = 0;j < 2;j++){
            t[j] = c[i][j] - c[i][j + 1];
            //cout << c[j][i];
        }
        for(ll j = 0;j < 2;j++){
            if(t[j] != ans[j]){
                cout << "No";
                return 0;
            }
        }
    }

    for(ll i = 0;i < 2;i++){
        ans[i] = c[i][0] - c[i + 1][0];
    }

    for(ll i = 0;i < 3;i++){
        vector<ll> t(2);
        for(ll j = 0;j < 2;j++){
            t[j] = c[j][i] - c[j + 1][i];
        }
        for(ll j = 0;j < 2;j++){
            if(t[j] != ans[j]){
                cout << "No";
                return 0;
            }
        }
    }

    cout << "Yes";

    return 0;
}

Measured memory_bytes: 256
def gcd(x,y):
     if x%y==0:
             return y
     else:
             return gcd(y, x%y)

[n,m]=[int(i) for i in input().split()]
x=[int(i)-m for i in input().split()]
x.append(0)

li=[]
f=1
if n==1:
    f=0
    print(abs(x[0]-x[1]))

for i in range(len(x)-1):
    li.append(max(abs(x[i]-x[i+1]), (abs(x[i+1]-x[i]))))
temp=abs(min(x))
li.append(temp)


if f:
    a=li[0]
    for i in range(len(li)-1):
        a=gcd(a, li[i+1])
    print(a)


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

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long
#define MOD 1000000007

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

/*
    mod pow
    return pow(base, pow) % MOD
*/
long long mod_pow(const long long x, long long n, const long long mod) {
    long long res = 1;
    if (n == 0) return 1;
    if (n & 1) res = x;
    long long y = mod_pow(x, n >> 1, mod);
    res = (res * (y * y % mod)) % mod;
    return res;
}

/*
    mod (a can be negative)
*/
long long modulo(long long a, long long mod)
{
    return (a % mod + mod) % mod;
}

int main(){
    std::ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    ll ret = 0;

    ll count_table[k+1] = {};
    for(int i=k;i>=1;--i)
    {
        ll count_dividable = k / i;
        count_table[i] = mod_pow(count_dividable, n, MOD);

        for(int j=2;j*i<=k;++j)
        {
            count_table[i] = modulo(count_table[i] - count_table[i*j], MOD);
        }
    }

    for(int i=1;i<=k;++i)
    {
        ret += (count_table[i] * i) % MOD;
        ret %= MOD;
    }

    cout << ret << endl;
}

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


int main() {
  
  int N;
  cin  >> N;
  
  vector<int> b(N);
  
  int next=1;
  int num;
  
  
  rep(i,N){
    cin >> b.at(i);
  }
  
  rep(i,N){
    num++;
    if(b.at(next-1)==2){
      cout << num << endl;
      break;
    }else{
      next = b.at(next-1);
      //cout << next << endl;
    }
    
  }
  if(num==N)
    cout << -1 << endl;
  
  
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
using namespace std;
int a[1000006], b[1000006], c[1000006];
long long s[1000006];
int main(){
	int n;
	cin >> n;
	long long s1 = 0, s2 = 0;
	for (int i = 1; i <= n; ++ i){
		cin >> a[i] >> b[i];
		s1 += a[i];
		s2 += b[i];
		c[i] = a[i];
		c[i + n] = b[i];
	}
	long long ans = min(s1, s2);
	sort(c + 1, c + 1 + 2 * n);
	for (int i = 1; i <= n; ++ i)
		s[i] = s[i - 1] + c[i];
	for (int i = 1; i <= n; ++ i){
		int x = a[i], y = b[i];
		if (x > y)
			swap(x, y);
		int px = lower_bound(c + 1, c + 1 + 2 * n, x) - c;
		int py = lower_bound(c + 1, c + 1 + 2 * n, y) - c;
		if (px <= n - 1){
			if (py <= n - 1)
				ans = min(ans, s[n]);
			else
				ans = min(ans, y + s[n - 1]);
		}
		else
			ans = min(ans, x + y + s[n - 2]);
	}
	cout << ans << endl;
}

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

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

 
typedef pair<int,int> P;
typedef long long ll;
 
const int INF = 1001001001;
const int MOD = 1000000007;
const double PI=acos(-1);

int main(){
    int N;
    cin >> N;
    ll A[N];
    ll Asum = 0;
    ll Acum[N];
    rep(i,N) {
        ll a;
        cin >> a;
        A[i] = a;
        Asum+=a;
        if (i==0) {
            Acum[i] = a;
        }
        else {
            Acum[i] = a + Acum[i-1];
        }
    }
    ll ans = 1e12;
    rep(i,N-1) {
        ans = min(ans,abs(Acum[i]-(Asum-Acum[i])));
    }
    cout << ans << endl;
}


Measured memory_bytes: 6692
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
int main()
{
    int n;
    cin >> n;
    rep(i, 1, 10)
    {
        rep(j, 1, 10)
        {
            if (i * j == n)
            {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3620
// template version 1.15
using namespace std;
#include <bits/stdc++.h>

// varibable settings
#define int long long
const int INF=1e18;

// define basic macro {{{
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(a, b, c) make_tuple(a, b, c)
#define divceil(a,b) ((a)+(b)-1)/(b)
#define is_in(x, a, b) ((a)<=(x) && (x)<(b))
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ub upper_bound
#define lb lower_bound
#define posl(A, x) (lower_bound(all(A), x)-A.begin())
#define posu(A, x) (upper_bound(all(A),x)-A.begin())
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

#if defined(PCM) || defined(LOCAL)
  #include "lib/dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
  #define cerrendl 42
#endif
//}}}

signed main() {
  int n;cin>>n;
  vector<int> p(n);
  int ans = 0;
  int M = INF;
  rep(i, n) {
    cin>>p[i];
    dump(M, p[i]);
    if (p[i]<=M) ans++;
    chmin(M, p[i]);
  }
  dump(p);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include<math.h>
#include <algorithm>
#include<string>
using namespace std;

int main() {
        int N;
        int a[110];
        int Alice=0, Bob=0;

        cin >> N;
        for(int i=0; i<N; i++) cin >> a[i];

        sort(a, a+N, greater<int>());

        for(int i=0; i<N; i++){
                if(i%2==0)Alice+=a[i];
                else Bob+=a[i];
        }

        cout << Alice-Bob << endl;

        return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <cstring>
#include <utility>

using namespace std;

char a[1003][1003];
int r, c;

int bfs (int n)
{
    bool done[1003][1003];
    int cost[1003][1003];
    queue<pair<int, int>> que;
    memset(done, false, sizeof(done));
    done[r][c]=true;
    cost[r][c]=0;
    que.push({r,c});
    while (1)
    {
        r=que.front().first, c=que.front().second;
        que.pop();
        if (!done[r][c+1])
        {
            done[r][c+1]=true;
            if (a[r][c+1]-'0'==n) { c++; cost[r][c]=cost[r][c-1]+1; return cost[r][c]; }
            if (a[r][c+1]!='X') { cost[r][c+1]=cost[r][c]+1; que.push({r, c+1}); }
        }
        if (!done[r][c-1])
        {
            done[r][c-1]=true;
            if (a[r][c-1]-'0'==n) { c--; cost[r][c]=cost[r][c+1]+1; return cost[r][c]; }
            if (a[r][c-1]!='X') { cost[r][c-1]=cost[r][c]+1; que.push({r, c-1}); }
        }
        if (!done[r+1][c])
        {
            done[r+1][c]=true;
            if (a[r+1][c]-'0'==n) { r++; cost[r][c]=cost[r-1][c]+1; return cost[r][c]; }
            if (a[r+1][c]!='X') { cost[r+1][c]=cost[r][c]+1; que.push({r+1, c}); }
        }
        if (!done[r-1][c])
        {
            done[r-1][c]=true;
            if (a[r-1][c]-'0'==n) {r--; cost[r][c]=cost[r+1][c]+1; return cost[r][c]; }
            if (a[r-1][c]!='X') { cost[r-1][c]=cost[r][c]+1; que.push({r-1, c}); }
        }
    }
}

int main()
{
    int h, w, n, ans=0;
    cin>>h>>w>>n;
    memset(a, 'X', sizeof(a));
    for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) { cin>>a[i][j]; if (a[i][j]=='S') { r=i; c=j; } }
    for (int i=1; i<=n; i++) ans+=bfs(i);
    cout<<ans<<'\n';
    return 0;
}



Measured memory_bytes: 9048
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <complex>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
#include <limits>
#include <time.h>
#include <cstdint>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(ll i=n-1;i>=0;i--)
#define rRep(i,a,b) for(ll i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; }
template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

ll A[200007],B[200007];

signed main(){
  ll N,Q,K;
  cin >> N >> K;
  vector<ll> V;
  ll  Z=0;
  V = vector<ll>(N+1,0);
  rep(i,N){
    cin >> V[i];
    if(V[i]==N){
      Z++;
    }
  }
  rep(i,K){
    if(Z==N){
      rep(i,N){
        cout << N ;
        if(i==N-1){
          cout << endl;
        }
        else{
          cout << " ";
        }
      }
      return 0;
    }
    Z=0;
    rep(j,N){
      B[j]=0;
    }
    rep(j,N){
      B[max(0ll,j-V[j])]++;
      B[min((ll) N,j+V[j])+1]--;
    }
    rep(j,N){
      if(j==0){
        V[j]=B[j];
      }
      else{
        V[j]=V[j-1]+B[j];
      }
      if(V[j]==N){
        Z++;
      }
    }
  }
  rep(i,N){
    cout << V[i];
    if(i!=N-1){
      cout << " ";
    }
  }
  cout <<endl;
}

Measured memory_bytes: 6424
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007

int main() {
    long long n, c = 0, a[100010];
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        c += a[i];
    }
    if (c % (n * (n + 1) / 2))
    {
        cout << "NO\n";
        return 0;
    }
    c /= n * (n + 1) / 2;
    for (int i = 0; i < n - 1; ++i)
    {
        if ((a[i] + c - a[i + 1]) >= 0 && (a[i] + c - a[i + 1]) % n == 0)
        {
            a[i + 1] = a[i] + c;
        }
        else
        {
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
    return 0;
}


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

int main()
{
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            char C;
            scanf(" %c",&C);
            if(i == j)printf("%c",C);
        }
    }printf("\n");
    return 0;
}


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

typedef long long ll;
#define pii pair<int , int>
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAXX 200005

bool p[MAXX];
int n;

int main()
{
    _FastIO;

    memset(p , true, sizeof(p));
    p[0] = false;
    p[1] = false;
    for(int i = 2; i * i <= MAXX; i++){
        if(p[i])
            for(int j = i + i; j < MAXX; j += i)
                p[j] = false;
    }
    cin >> n;
    for(int i = n; i < MAXX; i++){
        if(p[i]){
            cout << i << endl;
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 512
S = gets.chomp
X, Y = gets.split.map(&:to_i)

cnt = 0
list = []

S.chars.each do |s|
  if s == 'F'
    cnt += 1
  else
    list << cnt
    cnt = 0
  end
end

list << cnt

list = list.group_by.with_index(0) { |v, i| i % 2 }
x_list = list[0]
y_list = list[1] || []

x_check = Hash.new
x_check[x_list.shift] = true

y_check = Hash.new
y_check[0] = true

x_list.each do |x|
  temp = Hash.new

  x_check.each do |v, _|
    temp[v + x] = true
    temp[v - x] = true
  end

  x_check = temp
end

y_list.each do |y|
  temp = Hash.new

  y_check.each do |v, _|
    temp[v + y] = true
    temp[v - y] = true
  end

  y_check = temp
end

if x_check[X] && y_check[Y]
  puts 'Yes'
else
  puts 'No'
end


Measured memory_bytes: 86140
a,b,x = map(int,input().split())

import math

# ans =math.degrees(math.atan(a*(b**2)/(2*x)))
h = x/a**2


if h>=b/2:
    V = 2*((a**2)*b - x)/a**3
    ans = math.degrees(math.atan(V))
else:
    V=a*(b**2)/(2*x)
    ans =math.degrees(math.atan(V))

print(ans)

Measured memory_bytes: 3060
#include<map>
#include<cmath>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m;
int main(){
    cin>>n>>m;
    if(n%500<=m)puts("Yes");
    else puts("No");
	return 0;
}

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

using ll = long long int;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

#define pi 3.14159265358979323846

template<class T>bool ch1000000(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }




ll cnt_rep = 0;
ll powmod(ll N, ll P, ll M){
  cnt_rep++;
  if(P == 0) return 1;
  if(P%2 == 0){
    ll t = powmod(N, P/2, M);
    return t*t % M;
  }
  return (N * powmod(N, P-1, M)) % M;
}


ll gcd(ll a, ll b){
  ll resi, g, l;
  if(a > b){
    g = a; l = b;
  }else if(b > a){
    g = b; l = a;
  }else{
    return a;
  }
  resi = g % l;
  if(resi != 0){
    return gcd(l, resi);
  }else{
    return l;
  } 
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

int ans = 0;
int N, M, Q;

template<typename T>
void showall(vector<T> v){
  rep(i, 0, v.size()){
    cout << v[i] << " ";
  }
  cout << endl;
}

template<typename T>
ll com(T n, T m, T mod){
  ll a = 1, b = 1, ans;
  if(n == m || m == 0){
    ans = 1;
  }else{
    for(ll i = 0;i < m; i++){
      a *= n-i;
      a %= mod;
      b *= i+1;
      b %= mod;
    }
    ans = (a * powmod(b, mod-2, mod)) % mod;
  }
  
  return ans;
}



int main() {

  int N;

  cin >> N;

  vector<int> A(N), cnt(1000000+1, 0), check(1000000+1, 0);

  rep(i, 0, N){
    cin >> A[i];
    cnt[A[i]]++;
  }
  

  int ans = 0;
  for(int i = 1; i <= 1000000; i++){
    if(cnt[i] > 0){
      if(cnt[i] == 1 && check[i] == 0) ans++;
      for(int j = i; j <= 1000000; j += i){
        check[j]++;
      }
    }
  }

  cout << ans << endl;

  

  
  // cout << setprecision(8) << ans << endl;  // For double
}



Measured memory_bytes: 11820
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;

const long long INF = 100000000000;
const long long MOD = 1000000007;

//書くくらいの輪を返す
long long f(long long N){
  string s = to_string(N);
  long long slen = s.length();
  long long ret=0;
  for (int i = 0; i < slen; i++)
    ret += (s[i] - '0');
  return ret;
}

int main()
{
  long long N;
  cin >> N;
  if(N%f(N)==0)cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


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

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define SUBL freopen("/home/ajinkya/Desktop/input.txt","r",stdin); freopen("/home/ajinkya/Desktop/output.txt","w",stdout); 
#define ll long long
#define ull unsigned long long
#define FI(i,a,n) for(int i=a; i<=n; i++)
#define RFI(i,n,a) for(int i=n; i>=a; i--)
#define FLL(i,a,n) for(ll i=a; i<=n; i++)
#define RFLL(i,n,a) for(ll i=n; i>=a; i--)
#define vi vector<int>
#define vll vector<ll>
#define all(v) v.begin(),v.end()
#define pll pair<ll,ll>
#define pi pair<int, int>
#define GCD(a,b) __gcd(a,b)
#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define debug(x) cout << x << endl
#define MOD 1000000007
#define INF LLONG_MAX
#define PI 3.14159265359
using namespace std;




int main()
{
    fastio 
   // SUBL
  	string s;
  cin >> s;
  set<char> ss;
  int i=0;
  while(i<4)
  {
    ss.insert(s[i]);
    i++;
  }
  if(ss.size()==2) cout << "Yes";
  else cout << "No";
    return 0;
}         	

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

int teleport(int from, vector<int> &a) {
  return a[from];
}

int main() {
  int n; ll k; cin >> n >> k;
  vector<int> a(n+1);
  for(int i=1; i<=n; i++) cin >> a[i];

  // テレポートをチェック
  int townFrom = 1, townTo;
  vector<bool> isArrived(n+1, false);

  vector<int> townBeforeLoop;
  vector<int> townLoop;
  for(int i=1; i<=n; i++) {
    // テレポート先を求める
    townTo = teleport(townFrom, a);
    //cout << townFrom << " -> " << townTo << endl;
    if(!isArrived[townTo]) {
      isArrived[townTo] = true;
      townBeforeLoop.push_back(townTo);
      townFrom = townTo;
    }
    else {
      // ループの開始点を探す
      vector<int>::iterator itr;
      ll loopFirst;
      itr = find(townBeforeLoop.begin(),townBeforeLoop.end(), townTo);
      loopFirst = distance(townBeforeLoop.begin(), itr);
      // ループ前とループ部分の切り分け
      copy(townBeforeLoop.begin()+loopFirst, townBeforeLoop.end(), back_inserter(townLoop));
      townBeforeLoop.erase(townBeforeLoop.begin()+loopFirst, townBeforeLoop.end());
      break;
    }
  }
  // テレポート先がループしていれば、後は割り算でいける
  /*
  for(auto v:townBeforeLoop) cout << v << " ";
  cout << endl;
  for(auto v:townLoop) cout << v << " ";
  cout << endl;
  */
  int ans;
  if(k<=(ll)townBeforeLoop.size()) ans = townBeforeLoop[k-1];
  else ans = townLoop[(k-(ll)townBeforeLoop.size()-1)%(ll)townLoop.size()];
  cout << ans << endl;
}


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

using namespace std;

int main() {
	int n, a = 0, b = 0, m = 0;
	string s;
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		if (s[i] == '#') a++;
		else a--, b++;
		m = min(m, a);
	}
	cout << m + b << endl;
	return 0;
}


Measured memory_bytes: 640
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author champon
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 9e18
#define ceill(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
#define sp << " " <<
ll mod = 1e9+7;
void ans(bool b, ostream& out=cout){ out << (b ? "Yes" : "No") << endl; }
void ans2(bool b, ostream& out=cout){ out << (b ? "YES" : "NO") << endl; }
template<typename T> inline bool chmax(T &a, T b){ if(a<b){a=b; return true;} return false; }
template<typename T> inline bool chmin(T &a, T b){ if(b<a){a=b; return true;} return false; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){fill((T*)array, (T*)(array+N), val);}
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

#ifndef INCLUDE_DEBUG_HPP
#define INCLUDE_DEBUG_HPP

class debug
{
public:
    template<typename T> void vdeb(T vec);
    template<typename T1, typename T2> void adeb(T1 *arr, T2 n);
    template<typename T> void mdeb(T mp);
};

#endif //INCLUDE_DEBUG_HPP

template<typename T> void debug::vdeb(T vec)
{
    cout << "#vector set debug" << endl;
    for(auto vv : vec) cout << vv << " ";
    cout << endl;
}

template<typename T1, typename T2> void debug::adeb(T1 *arr, T2 n)
{
    cout << "#adebug" << endl;
    for(int i=0; i<=n; i++) cout << arr[i] << " ";
    cout << endl;
}

template<typename T> void debug::mdeb(T mp)
{
    cout << "#map pair debug" << endl;
    for(auto const& m : mp) cout << m.first sp m.second << endl;
}
debug dbg;

class BThin {
public:
	void solve(std::istream& in, std::ostream& out)
	{
	    int h, w;
	    in >> h >> w;
	    string c;
	    for(int i=0; i<h; i++){
	        in >> c;
	        out << c << endl << c << endl;
	    }
	}
};


int main() {
	BThin solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

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

int N, Q;
string s;
char t[200001], d[200001];

bool ok1(int m)
{
    int idx = m;
    char cur = s[idx];
    rep(i, Q)
    {
        if (cur == t[i]) {
            if (d[i] == 'L') {
                idx--;
                cur = s[idx];
            }
            else {
                idx++;
                cur = s[idx];
            }
        }
        if (idx == 0 or idx == N+1) break;
    }

    return idx == 0;
}


bool ok2(int m)
{
    int idx = m;
    char cur = s[idx];
    rep(i, Q)
    {
        if (cur == t[i]) {
            if (d[i] == 'L') {
                idx--;
                cur = s[idx];
            }
            else {
                idx++;
                cur = s[idx];
            }
        }
        if (idx == 0 or idx == N+1) break;
    }

    return idx == N+1;
}

int main()
{
    cin >> N >> Q >> s;
    rep(i, Q) cin >> t[i] >> d[i];

    //
    s = "x" + s + "x";

    int ans = 0;
    {
        int l = 0, r = N+2;
        while (r-l>1) {
            int m = (l+r) / 2;
            if (ok1(m)) l = m;
            else r = m;
        }
        ans = (r-1);
        if (ans < 0) ans = 0;
    }
    {
        int l = 0, r = N+2;
        while (r-l>1) {
            int m = (l+r) / 2;
            if (ok2(m)) r = m;
            else l = m;
        }
        int tmp = N - r + 1;
        if (tmp < 0) tmp = 0;
        ans += tmp;
    }

    cout << N-ans << endl;

}


Measured memory_bytes: 1156
#include <stdio.h>

int main(void){
	int a, b, c, d, yen;

	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &c);
	scanf("%d", &d);

	if(a<b){
		yen = a;
	} else {
		yen = b;
	}

	if(c<d){
		yen += c;
	} else {
		yen += d;
	}

	printf("%d\n", yen);

	return 0;
}


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

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 5e4;

typedef pair<int,int>   ii;
typedef bitset<N>       bs;

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

    int n;  cin >> n;
    int m;  cin >> m;
    int T;  cin >> T;

    vector<ii>  E;

    for(int i = 0 ; i < m ; ++i)    {
        int x;  cin >> x;
        int y;  cin >> y;

        E.pb(x,y);
    }

    reverse(all(E));

    if (T == 1) {
        vector<bs>  f(n,0);
        bs  S;

        for(int i = 0 ; i < n ; ++i)    f[i][i] = S[i] = 1;
        for(int i = 0 ; i < m ; ++i)    {
            int x = E[i].X - 1;
            int y = E[i].Y - 1;

            f[x] = f[y] = (f[x] | f[y]);
        }

        for(int i = 0 ; i < n ; ++i)
            S &= f[i];

        int x = n;

        for(int i = 0 ; i < n ; ++i)
            if (S[i])   {
                x = i;
                break;
            }

        if (x < n)  {
            vector<int> t(n,0); t[x] = 1;

            string res = "";

            for(int i = 0 ; i < m ; ++i)    {
                int x = E[i].X - 1;
                int y = E[i].Y - 1;

                if (t[x])   res += '^', t[y] = 1;
                else        res += 'v', t[x] = t[y];
            }
            reverse(all(res));  cout << res << endl;
        }
        else    cout << "-1";
    }
    if (T == 2) {
        if (n < 3)  return  cout << "-1",0;

        vector<int> f(n);
        vector<int> c(n);

        iota(all(f),0);
        fill(all(c),1);

        string res = "";

        for(int i = 0 ; i < m ; ++i)    {
            int x = E[i].X - 1;
            int y = E[i].Y - 1;

            if (c[f[x]] > 1)
                c[f[x]]--,
                c[f[y]]++,
                f[x] = f[y],
                res += 'v';
            else
                c[f[y]]--,
                c[f[x]]++,
                f[y] = f[x],
                res += '^';
        }
        reverse(all(res));  cout << res << endl;
    }
}

Measured memory_bytes: 307060
sub p{my($a,$b)=@_;$b?p($a**2%$m,$b>>1)*($b%2?$a:1)%$m:1}
$f=1;$m=1e9+7;
@s=map$%=($%+p$_,$m-2)%$m,1..<>;
$s+=$_*($s[$i++]+$s[-$i]-1)%$m,$f=$f*$i%$m for glob<>;
print$s%$m*$f%$m

Measured memory_bytes: 34892
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int,int> P;
typedef pair<P,P> PP;
int n,m,INF=1<<29,dxx[4]={-1,0,1,0},dyy[4]={0,-1,0,1};
int dx[8]={-1,-1,0,1,2,2,0,1},dy[8]={0,1,-1,-1,0,1,2,2};
string s[55];
bool check(int x,int y) {return x>=0&&x<n&&y>=0&&y<m;}
bool check(int x,int y,int xx,int yy) {
  if(x>=0&&x<n&&y>=0&&y<m) {
    if(s[x][y]=='*') return 0;
    if(x==xx&&(y==yy||y==yy+1)) return 0;
    if(x==xx+1&&(y==yy||y==yy+1)) return 0;
    return 1;
  }
  return 0;
}
 
int calc(int sx,int sy,int tx,int ty,int xx,int yy) {
  if(!check(sx,sy,xx,yy)||!check(tx,ty,xx,yy)) return INF;
  int d[n][m];
  for(int i=0;i<n;i++)for(int j=0;j<m;j++) d[i][j]=INF;
  d[sx][sy]=0;
  queue<P> que;
  que.push(P(sx,sy));
  while(!que.empty()) {
    P p=que.front();que.pop();
    if(p.F==tx&&p.S==ty) return d[tx][ty];
    for(int i=0; i<4; i++) {
      int x=p.F+dxx[i],y=p.S+dyy[i];
      if(!check(x,y,xx,yy)||d[x][y]<=d[p.F][p.S]+1) continue;
      d[x][y]=d[p.F][p.S]+1;
      que.push(P(x,y));
    }
  }
  return d[tx][ty];
}
 
int main() {
  while(cin >> n >> m && n) {
    for(int i=0; i<n; i++) cin >> s[i];
    int d[n][m][4];
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)for(int k=0;k<4;k++)d[i][j][k]=INF;
    vector<P> v;
    P p=P(-1,-1);
    for(int i=0;i<n;i++)for(int j=0;j<m;j++) {
        if(s[i][j]=='.')v.push_back(P(i,j));
        if(s[i][j]=='X'&&p.F==-1) p=P(i,j);
      }
    if(p==P(0,0)) {
      cout << 0 << endl;
      continue;
    }
    priority_queue<PP,vector<PP>,greater<PP> > que;
    for(int i=0; i<4; i++) {
      int b[2]={0,1};
      do {
        int cost=calc(v[0].F,v[0].S,p.F+dx[i*2+b[0]],p.S+dy[i*2+b[0]],p.F,p.S);
        cost+=calc(v[1].F,v[1].S,p.F+dx[i*2+b[1]],p.S+dy[i*2+b[1]],p.F,p.S);
        d[p.F][p.S][i]=min(d[p.F][p.S][i],cost);
      } while(next_permutation(b,b+2));
      que.push(PP(P(0,i),p));
    }
    while(!que.empty()) {
      PP pp=que.top();que.pop();
      int x=pp.S.F,y=pp.S.S,k=pp.F.S,c=pp.F.F;
      if(x==0&&y==0) {
        cout << d[0][0][k] << endl;
        goto end;
      }
      if(d[x][y][k]<c) continue;
      for(int i=0; i<4; i++) {
        int xx=x+dxx[i],yy=y+dyy[i]; 
        int cost=INF;
        int b[2]={0,1};
        do {
          int sum=calc(x+dx[k*2],y+dy[k*2],x+dx[i*2+b[0]],y+dy[i*2+b[0]],x,y);
          sum+=calc(x+dx[k*2+1],y+dy[k*2+1],x+dx[i*2+b[1]],y+dy[i*2+b[1]],x,y);
          cost=min(cost,sum);
        }while(next_permutation(b,b+2));
        if(!check(xx,yy)||d[xx][yy][(i+2)%4]<=d[x][y][k]+cost+1) continue;
        d[xx][yy][(i+2)%4]=d[x][y][k]+cost+1;
        que.push(PP(P(d[xx][yy][(i+2)%4],(i+2)%4),P(xx,yy)));
      }
    }
    cout << -1 << endl;
  end:;
  }
  return 0;
}


Measured memory_bytes: 3208
import math

A,B,H,M=map(int,input().split())
H_deg=360/12*H+360/12/60*M
M_deg=360/60*M
if M_deg==0:
  M_deg=360
rsq=(A*A+B*B)-(2*A*B)*math.cos(math.radians(abs(H_deg-M_deg)))
print('{:.20f}'.format(math.sqrt(rsq)))


Measured memory_bytes: 9372
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

const int mod = 1e9 + 7;

struct Modint {
  int n;
  Modint(int n = 0) : n(n) {}
};

Modint operator+(Modint a, Modint b) { return (a.n += b.n) >= mod ? a.n - mod : a.n; }
Modint operator-(Modint a, Modint b) { return (a.n -= b.n) < 0 ? a.n + mod : a.n; }
Modint operator*(Modint a, Modint b) { return 1LL * a.n * b.n % mod; }
Modint &operator+=(Modint &a, Modint b) { return a = a + b; }
Modint &operator-=(Modint &a, Modint b) { return a = a - b; }
Modint &operator*=(Modint &a, Modint b) { return a = a * b; }

Modint modpow(Modint a, long long b) {
  Modint ans = 1;
  while (b > 0) {
    if (b & 1) ans *= a;
    a *= a;
    b >>= 1;
  }
  return ans;
}

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

Modint operator/(Modint a, Modint b) { return a * modinv(b); }

Modint fact[2020202];
Modint ifact[2020202];
Modint inv[2020202];

Modint C(int n, int r) {
  if (n < 0 || r < 0 || n < r) return 0;
  return fact[n] * ifact[r] * ifact[n - r];
}

int main() {
  int n;
  cin >> n;
  inv[1] = 1;
  for (int i = 2; i < 2020202; i++) {
    inv[i] = inv[mod % i] * (mod - mod / i);
  }
  fact[0] = 1;
  ifact[0] = 1;
  for (int i = 1; i < 2020202; i++) {
    fact[i] = i * fact[i - 1];
    ifact[i] = inv[i] * ifact[i - 1];
  }

  Modint ans = 0;
  n--;
  for (int i = 0; i < n; i++) {
    ans += 1 - C(i - 1, n - i) / C(n, i);
  }
  for (int i = 1; i <= n; i++) {
    ans *= i;
  }

  cout << ans.n << endl;
}

Measured memory_bytes: 24064
#include<stdio.h>
#define N 100

int main(){
  int n, a;
  int p[N+1], m[N+1][N+1];
  int i, j, k, l;

  scanf("%d", &n);
  
  for(i = 1; i <= n; i++){
    scanf("%d %d", &p[i - 1], &p[i]);
  }

  for(i = 1; i <= n; i++) m[i][i] = 0;

  for(i = 2; i <= n; i++) {
    for(j = 1; j <= n - i + 1; j++){
      k = j + i - 1;
      m[j][k] = (1 << 21);
      
      for(l = j; l <= k - 1; l++){
	a = m[j][l] + m[l+1][k] + p[j-1] * p[l] * p[k];
	
	if(m[j][k] > a) m[j][k] = a;
	  
      }
    }
  }
  printf("%d\n", m[1][n]);

  return 0;
}




Measured memory_bytes: 2112
N = gets.chop.to_i
S = gets.chop

str = []

before = 0
S.chars.each do |c|
  if c == '('
    before += 1
    str.push(c)
  elsif c == ')'
    if before == 0
      str.unshift('(')
      str.push(c)
    else
      before -= 1
      str.push(c)
    end
  end
end

before.times do
  str.push(')')
end

puts str.flatten.join('')

Measured memory_bytes: 1788
n = gets.to_i
as = gets.split.map(&:to_i).sort

max = as.last
dp = Array.new(max + 1, true)

as.each do |a|
  i = a * 2
  while i <= max
    dp[i] = false
    i += a
  end
end

as = as.chunk_while {|i, j| i == j}.reject {|ary| ary.size >= 2}.flatten

puts as.count {|a| dp[a]}

Measured memory_bytes: 47608
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

#include <math.h>
#include <iomanip>
#include <vector>
#include <queue>
using Graph = vector<vector<int>>;
const double PI = 3.14159265358979323846;


int main() {

	char ans;

	char a;

	cin >> a;

	if ((a >= 'A') && (a <= 'Z')) {
		ans = 'A';
	}
	if ((a >= 'a') && (a <= 'z')) {
		ans = 'a';
	}


	cout << ans << endl;

	cin >> ans;

	return 0;


}

Measured memory_bytes: 3592
import java.util.Scanner;

public class Main {
  static int n, m;
  static int[] p, t, x;

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt();
    t = new int[n];
    for(int i = 0; i < n; i++){
      t[i] = sc.nextInt();
    }
    m = sc.nextInt();
    x = new int[m]; p = new int[m];
    for(int i = 0; i < m; i++){
      p[i] = sc.nextInt() - 1;
      x[i] = sc.nextInt();
    }

    int sum = 0;
    for(int i = 0; i < n; i++){
      sum += t[i];
    }

    int[] ans = new int[m];
    for(int i = 0; i < m; i++){
      ans[i] = sum - (t[p[i]] - x[i]);
    }

    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < m; i++){
      sb.append(ans[i] + System.lineSeparator());
    }

    System.out.print(sb);
  }
}


Measured memory_bytes: 10308
import java.util.Scanner;

class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int h = scanner.nextInt();
        int a = scanner.nextInt();

        int c = (h + (a - 1)) / a;
        System.out.println(c);

        /*
         * public void kiriage(int h, int a) { int c = (h + (a - 1)) / a;
         * System.out.println(c);
         */

    }

}


Measured memory_bytes: 22868
S = list(input())
re = ['dream','dreamer','erase','eraser']
devide = False

T = []

for l in range(len(S)):
    T.insert(0,S.pop(-1))
    if len(T) >= 5:
        if ''.join(T) in re:
            T = []
    if len(T) > 7:
        break

if T == []:
    devide = True

if devide == False:
    print('NO')
else:
    print('YES')




Measured memory_bytes: 3956
#include<iostream>
#include<queue>
#include<string>
#include<stack>
#include<cstdio>
#include<algorithm>

using namespace std;

int main(void)
{
  int a[3];
  int i;
  int n;

  cin>>n;

  for(i=0;i<n;i++)
    {
      cin>>a[0]>>a[1]>>a[2];

      sort(a,a+3);

        if(a[2]*a[2]==a[0]*a[0]+a[1]*a[1])
          cout<<"YES"<<endl;

        else
          cout<<"NO"<<endl;
    }

}

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

/*
 * [Basic Idea]
 *   You can omit a substring between 2 points with the same depth.
 *
 * [Example]
 *           ( ( ( ) ( ) ) ( ) )
 *   depth: - 0 1 2 1 2 1 0 1 0 -
 *
 *   depth  frequency  fC2
 *     0        3       3
 *     1        4       6
 *     2        2       1
 *   ---------------------
 *              total  10
 */
typedef unsigned int freq_t;

void
map_freq_for_depth(FILE *fp, freq_t freq_for[], int depth_max)
{
    char c;
    int depth = -1;

    memset(freq_for, 0, (depth_max * sizeof(freq_for[0])));

    while (EOF != (c = fgetc(fp))) {
        if ('(' == c) {
            freq_for[++depth]++;
            continue;
        }
        if (')' == c) {
            if (--depth < 0) break; /* reaches the end of tree */
            freq_for[depth]++;
            continue;
        }
        if ('\n' == c) break;
        break; /* must not happen */
    }
}

unsigned long
combination2_of(freq_t freq)
{
    return freq * (freq-1) / 2;
}

unsigned long
calc_num_omittable_substrings(freq_t freq_for[])
{
    int i;
    unsigned long num_combinations = 0;

    for (i = 0; freq_for[i]; i++) {
        num_combinations += combination2_of(freq_for[i]);
    }
    return num_combinations;
}

int
main(int argc, char *argv[])
{
    const int LEN_INPUT_MAX = 100000;
    const int DEPTH_MAX = (LEN_INPUT_MAX / 2) + 1;
    freq_t freq_for[DEPTH_MAX];

    map_freq_for_depth(stdin, freq_for, DEPTH_MAX);
    printf("%lu\n", calc_num_omittable_substrings(freq_for));

    return 0;
}

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

using namespace std;

int main() {
  in(ll, n);
  vector<ll> x(n), y(n);
  vector<char> u(n);
  rep(i, n) cin >> x[i] >> y[i] >> u[i];

  const ll M = 400001;
  const ll inf = numeric_limits<ll>::max();
  ll t = inf;
  rep(rot, 4) {
    // R L
    {
      vector<vector<ll>> r(M);
      rep(i, n) if (u[i] == 'R') r[y[i]].push_back(x[i]);
      rep(i, M) sort(all(r[i]));
      rep(i, n) if (u[i] == 'L') {
        const auto& ri = r[y[i]];
        if (ri.empty()) continue;
        auto it = lower_bound(all(ri), x[i]);
        if (it != ri.begin()) {
          if (ll d = x[i] - *(it - 1); d > 0) {
            t = min(t, d * 10 / 2);
          }
        }
      }
    }
    // R U
    {
      vector<vector<ll>> r(M);
      rep(i, n) if (u[i] == 'R') r[x[i] + y[i]].push_back(x[i]);
      rep(i, M) sort(all(r[i]));
      rep(i, n) if (u[i] == 'U') {
        const auto& ri = r[x[i] + y[i]];
        if (ri.empty()) continue;
        auto it = lower_bound(all(ri), x[i]);
        if (it != ri.begin()) {
          if (ll d = x[i] - *(it - 1); d > 0) {
            t = min(t, d * 10);
          }
        }
      }
    }
    // Rotate 90 degrees.
    rep(i, n) {
      int nx = 200000 - y[i];
      int ny = x[i];
      x[i] = nx;
      y[i] = ny;
      u[i] =
          map<char, char>{{'R', 'U'}, {'L', 'D'}, {'U', 'L'}, {'D', 'R'}}[u[i]];
    }
  }
  if (t == inf) {
    out("SAFE");
  } else {
    out(t);
  }
}


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

using namespace std;
//typedef tree<int, nuint_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set; 
#define int long long
#define MOD 1000000007
#define what_is(x) cerr << #x << " is " << x << endl;
#define loop(i,a,n) for(int i=a;i<n;i++)
 

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)



signed main() {
 
	fastio();

	string s;
	cin>>s;
	string pre="",res="";
	int ans=0;	
	int n=s.length();	
	for(int i=0;i<n;i++)
	{
		if(res!=pre && res!="")
		{
			ans+=1,pre=res,res=s[i];
		}else{
			res+=s[i];
		}
	}
	if( res!="" && res!=pre )
		ans+=1;
	cout<<ans<<endl;
	return 0;

 }


Measured memory_bytes: 720