akhauriyash/Code-Regression huggingface dataset:
<?php
$w=trim(fgets(STDIN));
$value=array();
for($i=1;$i<$w+1;$i++){
	$value[$i]=$i;
}
$n=trim(fgets(STDIN));
for($i=0;$i<$n;$i++){
	list($a,$b)=explode(",",trim(fgets(STDIN)));
	$tmp=$value[$a];
	$value[$a]=$value[$b];
	$value[$b]=$tmp;
}
foreach($value as $hoge) {
	echo $hoge."\n";
}

Measured memory_bytes: 15364
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using stkll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x << ": " << x << endl;
#else
    #define debug(x)
#endif


ll dp[3100][3100];

int main() {
    cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(20);

    ll N; cin >> N;
    vll a(N);
    rep(i,N) cin >> a[i];

    for(ll w = 1; w <= N; w++) {
        rep(l, N) {
            ll r = l + w;
            if(w % 2 == N % 2) {
                dp[l][r] = max(dp[l+1][r] + a[l], dp[l][r-1] + a[r-1]);
            }
            else {
                dp[l][r] = min(dp[l+1][r] - a[l], dp[l][r-1] - a[r-1]);
            }
        }
    }
    cout << dp[0][N] << endl;
}


Measured memory_bytes: 73984
#include<bits/stdc++.h>
#define pr(x) cerr << "\n" << (#x) << " is " << (x) << endl
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define ull unsigned long long
#define Toggle(n,i) (n^(1<<i))
#define Check(n,i) (n&(1<<i))
#define Set(n,i) (n|(1<<i))
#define Reset(n,i) (n&(~(1<<i)))
#define fo(a,x,y) for(int i=(x);i<=(y);++i){cout<<a[i]<<" ";}cout<<endl;
#define me(arr,val) memset(arr,val,sizeof arr)
#define inf 10e8
#define infd DBL_MAX
#define infl LLONG_MAX
#define mod 1000000007ll
#define f first
#define s second
#define  g(t,a)  (get<a>(t))
#define pra(a) for(auto i:a){cout<<i<<endl;}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
//int dx[]={+1,-1,0,0};//vertical horizontal
//int dy[]={0,0,+1,-1};//vertical horizontal
//int dx[]={+1,+1,-1,-1,+2,-2,+2,-2};//knights move
//int dy[]={+2,-2,+2,-2,+1,+1,-1,-1};//knights move
//int dx[]={+1,-1,0,0,+1,+1,-1,-1};//vertical horizontal diagonal
//int dy[]={0,0,+1,-1,-1,+1,+1,-1};//vertical horizontal diagonal
using namespace std;
using namespace __gnu_pbds;
/*typedef tree<int, null_type,less<int>, rb_tree_tag,
             tree_order_statistics_node_update>indexed_set;
for set use above*/
typedef tree<pair<int,int>, null_type,less<pair<int, int>>, rb_tree_tag,
tree_order_statistics_node_update> indexed_multiset;

ll nck[2005][2005];

void f()
{
    //nck[0][0]=1;
    for(ll i=0;i<=2000;++i)
    {
        nck[i][i]=1;
        nck[i][0]=1;
        for(ll j=1;j<=i;++j)
        {
            nck[i][j]=(nck[i-1][j-1]+nck[i-1][j])%mod;
        }
    }
}


int main()
{
    f();
    //pr(nck[2][1]);
    ll s,ans=0;
    scanf("%lld",&s);
    for(ll n=1;n<=s/3;++n)
    {
        ll k=s-n*3;
        //pr(n);
        //pr(k);
        ans=(ans+nck[n+k-1][n-1])%mod;
        //pr(ans);
    }
    printf("%lld",ans);
    return 0;
}



Measured memory_bytes: 26444
#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
  int N,i,j,ans=0,M=0;
  cin>>N;
  vector<int> A(N),a(1000001);
  for(i=0;i<N;i++){
    cin>>A[i];
    a[A[i]]++;
    M=max(A[i],M);
  }
  sort(A.begin(), A.end());
  for(i=0;i<N;i++){
    if(a[A[i]]==1)ans++;
    for(j=2;A[i]*j<=M;j++)a[A[i]*j]=0; 
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 7996
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//Micro Futures scalping to get my tendies 
int main(){
	ll n,k; cin>>n>>k;
	ll arr[n]; for(int i = 0; i < n; i++){
		cin>>arr[i];
	}
	ll pre[n+1]; pre[0] = 0;
	for(int i = 1; i < n+1; i++){
		pre[i] = pre[i-1]+arr[i-1];
	}
	for(int i = k+1; i <= n; i++){
		double sum1 = pre[i-1]-pre[(i-1)-k];
		double sum2 = pre[i]-pre[i-k];
		sum1 = sum1/(double)k;
		sum2 = sum2/(double)k;
		if(sum2-sum1 > 0.000000000) cout<<"Yes\n";
		else cout<<"No\n";
	}
}





Measured memory_bytes: 6716
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int max_ind(int n, int a[]){
    int ind = 0;
    int max = a[0];
    for(int i = 0;i < n;i++){
        if(max < a[i]){
            ind = i;
            max = a[i];
        }
    }
    return ind;
}

int main(void){
    int n;
    scanf("%d", &n);
    int l[n];
    for(int i = 0;i < n;i++){
        scanf("%d", &l[i]);
    }
    int ind = max_ind(n, l);
    int sum = 0;
    for(int i = 0;i < n;i++){
        if(i != ind)sum += l[i];
    }
    if(sum > l[ind])printf("Yes\n");
    else printf("No\n");
    return 0;
}

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

int pow(int n){

        int ans = 1;
        for(int i=0;i<n;i++){
            ans *= 10;
        }
    return ans;

}

int main()
{
    long long H;
    cin >> H;

    long long ans=0;
    long long kosuu=1;

    while(H!=0){
        ans += kosuu;
        H = H/2;
        kosuu = kosuu*2;
    }

    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
#define F first
#define S second
#define ios ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
ll x;
vector<int>tmp[6005];
vector<int>shel_dplft[6005];
vector<int>shel_dprt[6005];
int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll>a(n + 1);
    for(int i  = 1; i <= n; i++)
        cin >> a[i];
    vector<int>dp(5001, 0);
    dp[0] = 1;
    for(int i = 1; i <= n; i++){
        vector<int>lol;
        for(int j = 5000 - a[i]; j>=0; j--)
            dp[j + a[i]] += dp[j];
        for(int j = 0; j <= 5000; j++)
            if(dp[j])
                lol.push_back(j);
        shel_dplft[i] = lol;
    }
    dp.clear();
    dp.assign(5001, 0);
    dp[0] = 1;
    for(int i = n; i >= 1; i--){
        vector<int>lol;
        for(int j = 5000 - a[i]; j>=0; j--)
            dp[j + a[i]] += dp[j];
        for(int j = 0; j <= 5000; j++)
            if(dp[j])
                lol.push_back(j);
        shel_dprt[i] = lol;
    }
    shel_dplft[0].push_back(0);
    shel_dprt[n + 1].push_back(0);
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        vector<int>red = shel_dplft[i-1];
        vector<int>blue = shel_dprt[i + 1];
        for(auto v : red){
            int lo = 0, hi = blue.size() - 1;
            while(lo < hi){
                int md =lo + (hi - lo + 1)/2;
                if(v + blue[md] < k)
                    lo = md;
                else
                    hi = md - 1;
            }
            if(v + blue[lo] + a[i] >= k && v + blue[lo] < k){
                cnt++;
                break;
            }
        }
    }
    cout << n - cnt << '\n';
    return 0;
}


Measured memory_bytes: 194560
#include<bits/stdc++.h>
using namespace std;
const long long INF=2E17;
typedef pair<int,int> Pair;
typedef long long int LL;
const int MAX=100010;

vector<int> sosu(int n){
    vector<int> v; 
    for(int i=2;i<=55555;i++){
        bool flag=true;
        for(int j=0;j<v.size();j++){
            if(i%v.at(j)==0) {
                flag=false;
                break;
            }
            if(v.at(j)*v.at(j)>i)break;
        }
        if(flag){
            v.push_back(i);
        }
        
    }
    return v;
}

int main(){
    int n=55555;
    int N;
    cin >> N;
    vector<int> prime=sosu(n);
    vector<int> ans;
    for(int i=0;i<prime.size();i++){
        if(prime[i]%5==1){
            ans.push_back(prime[i]);
        }
        if(ans.size()==N)break;
    }
    for(auto itr=ans.begin();itr!=ans.end();itr++){
        cout << *itr;
        if(itr!=ans.end()-1) cout << " ";
        else cout << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;
#define ll long long
int n, A[25];
ll Getans(int l, int r, ll L, ll R)
{
	if (l + 1 == r)
		return L * A[l] + R * A[r];
	ll ret = 0x7f7f7f7f7f7f7f7fll;
	for (int i = l + 1; i < r; i++)
		ret = min(Getans(l, i, L, L + R) + Getans(i, r, L + R, R) - A[i] * (L + R), ret);
	return ret;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &A[i]);
	printf("%lld\n", Getans(1, n, 1, 1));
}


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

int main(){
  int n,m;
  cin >> n >> m;
  
  vector<vector<int>> a(n), b(m);
  
  for ( int i = 0; i < n; i++ ){
    string s;
    cin >> s;
    for ( int j = 0; j < n; j++ )
      a[i].push_back(s[j] == '#' ? 1 : 0);
  }
  
  for ( int i = 0; i < m; i++ ){
    string s;
    cin >> s;
    for ( int j = 0; j < m; j++ )
      b[i].push_back(s[j] == '#' ? 1 : 0);
  }
    
  for ( int i = 0; i < n - m + 1; i++ ){
    for ( int j = 0; j < n - m + 1; j++ ){
      bool ok = true;
      for ( int k = 0; k < m; k++ ){
        for ( int l = 0; l < m; l++){
          if ( a[i+k][j+l] == b[k][l] ) continue;
          else{
            ok = false;
            break;
          }
        }
        if ( !ok ) break;
      }
      
      if ( ok ) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
using namespace std;

int main() {
  int a,b;
  cin >> a >> b;
  if(a > b) cout << a - 1 << endl;
  else cout << a << endl;
}


Measured memory_bytes: 256
#define  _USE_MATH_DEFINES
#define  _USE_MATH_DEFINES

#define  rep(i, n) for(int i = 0; i < n; i++)
#define  repx(i, a, n) for(int i = a; i < n; i++)
#define  loop while(1)
#define  lli long long int
#define  aryout(ary) rep(i, ary.size()) cout << ary[i] << (i < ary.size() - 1 ? " " : "\n");
 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <utility>
#include <set>

using namespace std;

int main() {

  int n;
  cin >> n;

  vector<int> vA(n, 0), vB(n, 0), vC(n, 0);

  rep(i, n) cin >> vA[i];
  rep(i, n) cin >> vB[i];
  rep(i, n) cin >> vC[i];

  sort(vA.begin(), vA.end());
  sort(vB.begin(), vB.end());
  sort(vC.begin(), vC.end());

  lli ans = 0;
  lli tmpA, tmpB;

  rep(i, n) {
    tmpA = lower_bound(vA.begin(), vA.end(), vB[i]) - vA.begin();
    tmpB = vC.end() - upper_bound(vC.begin(), vC.end(), vB[i]);
    ans += (lli)tmpA * tmpB;
  }
 
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1408
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type Node struct {
	value  int
	parent *Node
	left   *Node
	right  *Node
}

type Tree struct {
	root *Node
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	tree := &Tree{}
	for i := 0; i < n; i++ {
		command := nextText(sc)
		if command == "insert" {
			x, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			insertTree(x, tree)
		} else if command == "print" {
			printTree(tree)
		} else if command == "find" {
			x, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			if findTree(x, tree) {
				fmt.Println("yes")
			} else {
				fmt.Println("no")
			}
		} else {
			panic(fmt.Errorf("unknown command: %s\n", command))
		}
	}
}

func insertTree(x int, tree *Tree) {
	if tree.root == nil {
		tree.root = &Node{x, nil, nil, nil}
	} else {
		insertNode(x, tree.root)
	}
}

func insertNode(x int, node *Node) {
	for {
		if node.value < x {
			if node.right == nil {
				node.right = &Node{x, node, nil, nil}
				break
			} else {
				node = node.right
			}
		} else {
			if node.left == nil {
				node.left = &Node{x, node, nil, nil}
				break
			} else {
				node = node.left
			}
		}
	}
}

func printTree(tree *Tree) {
	if tree.root == nil {
		fmt.Println("")
		fmt.Println("")
	} else {
		printResult(inorder(tree.root, []int{}))
		printResult(preorder(tree.root, []int{}))
	}
}

func findTree(x int, tree *Tree) bool {
	return findNode(x, tree.root)
}

func findNode(x int, node *Node) bool {
	for node != nil {
		if node.value == x {
			return true
		} else if node.value < x {
			node = node.right
		} else {
			node = node.left
		}
	}
	return false
}

func preorder(top *Node, vs []int) []int {
	vs = append(vs, top.value)
	if top.left != nil {
		vs = preorder(top.left, vs)
	}
	if top.right != nil {
		vs = preorder(top.right, vs)
	}
	return vs
}

func inorder(top *Node, vs []int) []int {
	if top.left != nil {
		vs = inorder(top.left, vs)
	}
	vs = append(vs, top.value)
	if top.right != nil {
		vs = inorder(top.right, vs)
	}
	return vs
}

func nextText(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

func printResult(result []int) {
	writer := bufio.NewWriter(os.Stdout)
	for i := 0; i < len(result); i++ {
		writer.Write([]byte(fmt.Sprintf(" %d", result[i])))
	}
	writer.Write([]byte("\n"))
	writer.Flush()
}



Measured memory_bytes: 39416
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;

#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
///////////////////////////////////////



int main(){fastio
    ll n,m;cin>>n>>m;
    ll l=1,r=n;
    rep(i,1,m){
        ll a,b;cin>>a>>b;
        Max(l,a);
        Min(r,b);
    }
    cout<<max(0,r-l+1)<<endl;
    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int q,i,j,k,l1,l2,m,n;
    string X,Y;
    cin>>q;
    for(i=0; i<q; i++)
    {
        cin>>X>>Y;
        l1=X.length()+1;
        l2=Y.length()+1;
        int arr[l2][l1];
        for(k=0; k<l1; k++)
        {
            arr[0][k]=0;
        }
        for(k=0; k<l2; k++)
        {
            arr[k][0]=0;
        }
        for(k=1; k<l2; k++)
        {
            for(j=1; j<l1; j++)
            {
                if(Y[k-1]==X[j-1])
                {
                    arr[k][j]=1+arr[k-1][j-1];
                }
                else
                {
                    m=arr[k-1][j];
                    n=arr[k][j-1];
                    arr[k][j]=max(m,n);
                }
            }
        }
        cout<<arr[l2-1][l1-1]<<endl;
    }
}




Measured memory_bytes: 7028
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>
#include <map>
using namespace std;

int main() {
    long long a, b, c, k;
    cin >> a >> b >> c >> k;
    long long ans = 0;
    if (k > a) {
        ans += a;
        k -= a;
    }
    else {
        ans += k;
        goto last;
    }
    if (k > b) {
        k -= b;
    }
    else goto last;
    if (k > 0) {
        ans -= k;
    }
    last:
    cout << ans << endl;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int  long long int
#define pb push_back
#define fe first
#define se second
#define endl "\n"
#define pii pair<int, int>

#define PI 3.14159265358979323846
const int N = 100 + 10;
const int INF=2e9;

vector<pii> v;
int n,cnt1;
int a[N],wyn;

void solve() {
	int n;
	cin>>n;
	wyn=n;
	if(n%2==0) 
	  wyn++;
	  
	  for( int i=1;i<=n;i++) {
		    for(int j=1;j<i;j++) {
				   if(i+j==wyn)
				     continue;
				   v.pb({i,j}); 			   
				}	       
		  }
		  
		  cout<<v.size()<<endl;
		  
		  for(int i=0;i<v.size();i++)
		      cout<<v[i].fe<<" "<<v[i].se<<endl;
	
	

     

		
}


int32_t main() {
  fast;
  int t = 1;
  while (t--)
	solve();

  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <cstring>
using namespace std;

int main() {
    char kanChars[][3] = {
        "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m",
        "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z",
        "ld", "mb", "mp", "nc", "nd", "ng", "nt", "nw", "ps", "qu", "cw", "ts",
    };
    map<string, int> kanCharOrder;
    for (int i = 0; i < 38; i++) {
        kanCharOrder.insert(make_pair(kanChars[i], i + 1));
    }
    int appeareTable[39][39];
    memset(appeareTable, 0, sizeof(appeareTable));
    int n;
    cin >> n;
    queue<string> insertQueue;
    string word;
    while (cin >> word) {
        for (string::iterator it = word.begin(); it != word.end(); it++) {
            if ((it + 1) != word.end() && kanCharOrder.find(string(it, it + 2)) != kanCharOrder.end()) {
                insertQueue.push(string(it, it + 2));
                it += 1;
            } else {
                insertQueue.push(string(it, it + 1));
            }
        }
        string prev = "";
        while (insertQueue.empty() == false) {
            if (prev.empty() == false) {
                ++appeareTable[kanCharOrder[prev]][kanCharOrder[insertQueue.front()]];
            }
            prev = insertQueue.front();
            insertQueue.pop();
        }
    }
    for (int i = 0; i < 38; i++) {
        int max = 0, maxChar = 0;
        for (int j = 0; j < 38; j++) {
            if (max < appeareTable[i + 1][j + 1]) {
                max = appeareTable[i + 1][j + 1];
                maxChar = j;
            }
        }
        cout << kanChars[i] << " " << kanChars[maxChar] << " " << max << endl;
    }
}

Measured memory_bytes: 0
import numpy as np

H,W = map(int,input().split())
grid = []

for i in range(H):
  line = list(input())
  grid.append(line)

mod_grid = []
for i in range(H):
  if '#' in grid[i]:
    mod_grid.append(grid[i])
    
mod_grid = np.array(mod_grid).T
mod_grid2 = []
for i in range(W):
  if '#' in mod_grid[i]:
    mod_grid2.append(mod_grid[i])
    
mod_grid2 = np.array(mod_grid2).T
for i in range(mod_grid.shape[1]):
  if '#' in mod_grid2[i]:
    print(''.join(mod_grid2[i]))

  

Measured memory_bytes: 12508
n = int(input())

a = [0]*n

a = [int(s) for s in input().split()]


dic = {}
for s in a:
    if not (s in dic):
        dic[s] = 1
    else:
        dic[s] += 1


for i in range(n):
    if not(i+1 in dic):
        print(0)
    else:
        print(dic[i+1])

Measured memory_bytes: 34804
#include <cstdio>
#define SENTINEL 2000000000

int *L, *R;
int cnt;

void merge(int A[], int n, int left, int mid, int right) {
    int n1 = mid - left;
    int n2 = right - mid;

    for (int i = 0; i < n1; i++) L[i] = A[left + i];
    for (int i = 0; i < n2; i++) R[i] = A[mid + i];
    L[n1] = R[n2] = SENTINEL;
    int i = 0, j = 0;
    for (int k = left; k < right; k++) {
        cnt++;
        if (L[i] < R[j]) {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
        }
    }
}

void mergeSort(int A[], int n, int left, int right) {
    if (left + 1 < right) {
        int mid = (left + right) / 2;
        mergeSort(A, n, left, mid);
        mergeSort(A, n, mid, right);
        merge(A, n, left, mid, right);
    }
}

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

    int A[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }

    L = new int[int(n/2+1)];
    R = new int[int((n+1)/2+1)];
    mergeSort(A, n, 0, n);

    for (int i = 0; i < n; i++) {
        if (i) printf(" ");
        printf("%d", A[i]);
    }
    printf("\n");

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

    return 0;
}


Measured memory_bytes: 6524
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let s = read::<String>().as_bytes().to_vec();
    let k: u64 = read();

    let mut count = 1;
    let mut v = vec![];

    for sub in s.windows(2) {
        if sub[0] == sub[1] {
            count += 1;
        } else {
            v.push((sub[0], count));
            count = 1;
        }
    }
    v.push((*s[..].last().unwrap(), count));

    let ans: u64 = if v.len() == 1 {
        v[0].1 * k / 2
    } else if s[..].last() == s[..].first() {
        let mut sum = 0;
        for i in 1..v.len() - 1 {
            sum += v[i].1 / 2;
        }
        sum *= k;
        sum += ((v[..].last().unwrap().1 + v[..].first().unwrap().1) / 2) * (k - 1);
        sum += v[..].first().unwrap().1 / 2;
        sum += v[..].last().unwrap().1 / 2;
        sum
    } else {
        v.iter().map(|x| x.1 / 2).sum::<u64>() * k
    };

    println!("{}", ans);
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


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

using namespace std;

#define REP(i, N) for (int i = 0; i < (int)N; i++)
#define RREP(i, N) for (int i =(int)N-1; i >= 0; i--)
#define FOR(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define INF (1 << 30)
#define LLINF (1LL << 62)
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;



int main(){
  int h,w;
  cin>>h>>w;
  char t[h][w];
  vector<int> hv;
  vector<int>::iterator hitr;
  vector<int>::iterator witr;
  vector<int> wv;
  REP(i,h){
    REP(j,w){
      cin>>t[i][j];
    }
  }
  REP(i,h){
    REP(j,w){
      if(t[i][j]=='#')break;
      if(j==w-1){
        hv.push_back(i);
      }
    }
  }
  REP(j,w){
    REP(i,h){
      if(t[i][j]=='#')break;
      if(i==h-1){
        wv.push_back(j);
      }
    }
  }
  if(hv.empty()==0){
  hitr=hv.begin();
  }
  if(wv.empty()==0){
  witr=wv.begin();
  }
  REP(i,h){
    if(!hv.empty()&&i==*hitr){
      hitr++;
      continue;
    }
    REP(j,w){
      if(!wv.empty()&&j==*witr){
        witr++;
        continue;
      }else{
        cout<<t[i][j];
      }

    }
    witr=wv.begin();
    cout<<endl;
  }
}


Measured memory_bytes: 256
from statistics import mean, median,variance,stdev
import sys
import math
import fractions
def j(a):
    if a: print("AC")
    else :print("WA")


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())

l = ip()                              #入力整数1つ
a,b= (int(i) for i in input().split())      #入力整数横2つ
#x,y,z = (int(i) for i in input().split())    #入力整数横3つ
#n,m,x,y= (int(i) for i in input().split())  #入力整数横4つ
x = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
sorted(x)
c = []
d = []
e = []
for i in range(len(x)):
    if x[i] <= a:
        c.append(x[i])
    elif a < x[i] and x[i] <=b:
        d.append(x[i])
    else:
        e.append(x[i])
f = len(c)
g = len(d)
i = len(e)

print(min(f,g,i))


Measured memory_bytes: 5788
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

//vector string deque break continue
#define forn(i, s, f) for (int i = (int)s; i < (int)f; i++)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define fs first
#define sc second
#define pf push_front
#define pb push_back
#define pop_f pop_front
#define pop_b pop_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

template <typename T> istream& operator>>(istream& in, vector <T>& a) {for (auto& i : a) in >> i; return in;}
template <typename T> ostream& operator<<(ostream& out, vector <T>& a)  {for (auto& i : a) out << i << " "; return out;}
template <typename T, typename U> void chkmin(T& a, U b) {if (a > b) a = b;}
template <typename T, typename U> void chkmax(T& a, U b) {if (a < b) a = b;}

#define int long long

struct Edge {
    int to, cost, time;
};

main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m, s;
    cin >> n >> m >> s;
    vector <vector <Edge>> gr(n);
    forn (i, 0, m) {
        int v, u, c, t;
        cin >> v >> u >> c >> t;
        --v, --u;
        gr[v].pb({u, c, t});
        gr[u].pb({v, c, t});
    }
    vector <pii> a(n);
    forn (i, 0, n)
        cin >> a[i].fs >> a[i].sc;
    set <pair <int, pii>> q;
    const int INF = 2501;
    chkmin(s, INF);
    vector <vector <long long>> dst(n, vector <long long> (INF + 1, 1e18));
    dst[0][s] = 0;
    forn (i, 0, n)
        forn (j, 0, INF + 1)
            q.insert({dst[i][j], {i, j}});
    int cnt = 0;
    while (!q.empty()) {
        int time = q.begin() -> fs;
        auto [v, money] = q.begin() -> sc; 
        q.erase(q.begin());
        int nxt = money;
        forn (i, 1, INF + 1) {
            nxt += a[v].fs;
            chkmin(nxt, INF);
            if (dst[v][money] + i * a[v].sc < dst[v][nxt]) {
                q.erase(q.find({dst[v][nxt], {v, nxt}}));
                dst[v][nxt] = dst[v][money] + i * a[v].sc;
                q.insert({dst[v][nxt], {v, nxt}});
            }
            if (nxt == INF)
                break;
        }
        for (auto i : gr[v]) {
            int u = i.to, cost = i.cost, time = i.time;
            if (money >= cost &&
                dst[v][money] + time < dst[u][money - cost]) {
                q.erase(q.find({dst[u][money - cost], {u, money - cost}}));
                dst[u][money - cost] = dst[v][money] + time;
                q.insert({dst[u][money - cost], {u, money - cost}});
            }
        }
        ++cnt;
    }
    //cout << cnt << "\n";
   /* forn (i, 0, n) {
        forn (j, 0, INF + 1)
            cout << dst[i][j] << " ";
        cout << "\n";
    }*/
    forn (i, 1, n) {
        cout << *min_element(all(dst[i])) << "\n";
    }
    return 0;
}

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

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

    int r, g, b, n;
    cin >> r >> g >> b >> n;

    int res = 0;
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= n; ++j){
            if((n - (i*r + j*g)) < 0) continue;

            if((n - (i*r + j*g))%b == 0) ++res;
        }
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define int ll

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

int const N = 1e5 + 20 ;
int n , sum , ans ;
pii a[N] ;

inline bool cmp (pii x , pii y) {
	return x.F - x.S > y.F - y.S ;
}

int32_t main(){
	ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;

	cin >> n ;

	for (int i = 0 ; i < n ; i ++) cin >> a[i].F ;
	for (int i = 0 ; i < n ; i ++) cin >> a[i].S ;

	sort(a , a + n , cmp) ;

	for (int i = n - 1 ; i >= 0 ; i --) {
		int v = a[i].S - a[i].F ;
		if (v > 0) sum += v , ans ++ ;
	}

	for (int i = 0 ; i < n ; i ++) {
		if (sum <= 0) {
			ans += i ;
			break ;
		}
		sum -= a[i].F - a[i].S ;
	}

	if (sum > 0) ans = -1 ;

	cout << ans << '\n' ;
}


Measured memory_bytes: 1792
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc=new Scanner(System.in);
        int H=sc.nextInt();
        int W=sc.nextInt();
        int[][] map=new int[H][W];
        boolean[] isWhite=new boolean[H];
        
        for(int i=0;i<H;i++){
            String tmp=sc.next();
            for(int j=0;j<W;j++){
                if(tmp.charAt(j)=='#'){
                    map[i][j]=1;
                }else{
                    map[i][j]=0;
                }
            }
        }
        
        for(int i=0;i<H;i++){
            isWhite[i]=true;
            for(int j=0;j<W;j++){
                if(map[i][j]==1){
                    isWhite[i]=false;
                    break;
                }
            }
        }
        
        for(int i=0;i<H;i++){
            if(isWhite[i]){
                for(int j=0;j<W;j++){
                    map[i][j]=2;
                }
            }
        }
        
        boolean[] check2=new boolean[W];
        
        for(int i=0;i<W;i++){
            check2[i]=true;
            for(int j=0;j<H;j++){
                if(map[j][i]==1){
                    check2[i]=false;
                    break;
                }
            }
        }

        for(int i=0;i<W;i++){
            if(check2[i]){
                for(int j=0;j<H;j++){
                    map[j][i]=2;
                }
            }
        }
        
        for(int i=0;i<H;i++){
            boolean print=false;
            for(int j=0;j<W;j++){
                if(map[i][j]==2){
                }else if(map[i][j]==1){
                    System.out.print('#');
                    print=true;
                }else{
                    System.out.print('.');
                    print=true;
                }
                    
            }
            
            if(print){
                System.out.println();
            }
        }
        
    }
}


Measured memory_bytes: 27248
n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)

con = a.dup
[k, 50].min.times do |i|
  imos = Array.new(n, 0)
  n.times do |j|
    imos[[0, j - con[j]].max] += 1
    if j + con[j] + 1 < n
      imos[j + con[j] + 1] -= 1
    end
  end

  1.upto(n-1) do |j|
    imos[j] += imos[j - 1]
  end

  con = imos
end

puts con.join(' ')


Measured memory_bytes: 84656
#include <stdio.h>

int main(){
    int a, b;
    
    scanf("%d %d", &a, &b);
    
    if (a < b) {
        printf("a < b\n");
    } else if (a > b) {
        printf("a > b\n");
    } else {
        printf("a == b\n");
    }
    
    return 0;
}



Measured memory_bytes: 2064
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
  int N;
  string S;
  cin >> N;
  cin >> S;

  if (N%2 == 1) {
    cout << "No" << endl;
    return 0;
  }

  for (int i = 0; i < N/2; i++)
  {
    if (S[i] != S[i+(N/2)] ) {
      cout << "No" << endl;
      return 0;
    }
  }
  
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG

#include"bits/stdc++.h"
using namespace std;

//loops
#define REP(i,n) for(int i=0;i<(ll)(n);i++)
#define REPD(i,n) for(int i=(ll)(n)-1;i>=0;i--)
#define OneToN(i,n) for(int i=1;i<(ll)(n+1);i++)
#define ZeroToN(i,n) for(int i=0;i<(ll)(n+1);i++)
#define AToB(i,a,b) for(int i=a;i<(ll)(b+1);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)

//bitsearch
#define BITSEARCH(bit, n) for (int bit = 0; bit < (1<<n); ++bit)
#define isOne(bit, i) bit & (1<<i)


//arrays
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define add push_back


#define remove_unique(v) v.erase(unique(ALL(v)), v.end())

//pair
#define fir first
#define sec second

//types
#define ll long long
#define vec vector
#define cord2d pair<int,int>
//UNCOMMENT WHEN NEEDED
//#define int ll

//input
template <class T> T get(){ T s; cin >> s; return(s);}
#define gi get<int>()
#define gs get<string>()

template <class T> vector<T> getv(int n) { vec<T> v(n); REP(i, n) cin >> v[i]; return v; }
#define gim(n) getv<int>(n)
#define gsm(n) getv<string>(n)

//output
void print(int a){ cout << a << endl; }
void print(long long a){ cout << a << endl; }
void print(string a){ cout << a << endl; }
void print(char a){ cout << a << endl; }
void print(double a){ cout << a << endl; }
void print(double a, int dig){ cout << std::setprecision(dig) << a << endl; }

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

template <class T = int>
void print(vec<T> v){ cout << v << endl; }

template <class T = int>
void print2dVec(vec<vec<T>> v2d){for(vec<T> v: v2d) {print(v);}}

void YesNo1(bool i = true){ return print(i?"Yes":"No"); }
void YESNO2(bool i = true){ return print(i?"YES":"NO"); }

//debug output
#define var_name(var) #var
template <class T> void debug(T &var, int nest = 0, string before = "") { cout << string("          ", nest) << before; print(var); }

//name replacement
#define y0 y0__
#define y1 y1__
#define j0 j0__
#define j1 j1__

//bool lambdas
#define lamb(exp) [](auto i){return exp;}
#define isEven [](int i){return i % 2 == 0;}
#define isOdd [](int i){return i % 2 != 0;}

//constants
const ll INF = 1e18;
const int MOD = 10000007;

//maths
int factorial(int k){ int sum = 1; for (int i = 1; i <= k; ++i) { sum *= i; } return sum; }
int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

////////////////////

void Main() {
    //code here
    int n = gi, k = gi;
    vec<int> nums = gim(n);
    vec<int> dp {0};
    AToB(i, 1, n-1) {
        int minV = INF;
        OneToN(dif,min(i, k)) {
            if (dif == 1) minV = abs(nums[i]-nums[i-dif]) + dp[i-dif];
            minV = min(minV, abs(nums[i]-nums[i-dif]) + dp[i-dif]);
        }
        dp.add(minV);
    }
    print(dp[n-1]);
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Main();
}


Measured memory_bytes: 1276
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define forin(in) for(int i=0; i<(int)in.size(); i++) cin>>in[i]
#define forout(out) for(int i=0; i<(int)out.size(); i++) cout<<out[i]<<endl
#define rep(i, n) for(int i=0; i<(n); i++)

int main(){
    string S; cin >> S;
    string T; cin>> T;
    int cnt = 0;
    if(S[0] == T[0]) cnt++;
    if(S[1] == T[1]) cnt++;
    if(S[2] == T[2]) cnt++;

    cout<< cnt << endl;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)
#define ALL(x) (x).begin(), (x).end()
const long long INF = 1e18;
using namespace std;
typedef long long ll;
int main() {
  std::cout << std::fixed << std::setprecision(10);
  ll N;
  cin >> N;
  vector<double> a(N);
  REP(i, N) cin >> a[i];

  double ans = 0;

  REP(i, N) { ans += 1 / a[i]; }
  cout << 1 / ans;
  return 0;
}

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

namespace AtCoder.Contest.D
{
	class Program
	{
		public static void Main(string[] args)
		{
			var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
			Console.SetOut(sw);

			Scanner cin = new Scanner();

			int n = cin.nextInt();
			long[] a = cin.ArrayLong(n);
			long sum = a.Sum();
			var ans = new long[n];
			long[] re = new long[n];
			for (int i = 0; i < n; i++)
			{
				if (i % 2 == 1) re[i / 2] = a[i];
				else re[i / 2 + n / 2] = a[i];
			}
			long[] ruiseki = new long[2*n];
			ruiseki[0]=0;
			for (int i = 0; i < 2*n-1; i++)
			{
				ruiseki[i+1] = ruiseki[i] + re[i%n];
			}
			for (int i = 0; i < n; i++)
			{
				ans[i] = sum;
				if (i % 2 == 0)
				{
					ans[i] -= 2 * (ruiseki[i / 2 + n / 2] - ruiseki[i / 2]);
				}
				else
				{
					ans[i] -= 2 * (ruiseki[(i + 1) / 2 + 2 * (n / 2)] - ruiseki[(i + 1) / 2 + n / 2]);
				}
			}
			Console.WriteLine(String.Join(" ", ans));

			Console.Out.Flush();
		}
	}

	class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

		public Scanner()
		{
			s = new string[0];
			i = 0;
		}

		public string next()
		{
			if (i < s.Length) return s[i++];
			string st = Console.ReadLine();
			while (st == "") st = Console.ReadLine();
			s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
			if (s.Length == 0) return next();
			i = 0;
			return s[i++];
		}

		public int nextInt()
		{
			return int.Parse(next());
		}

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextInt() + add;
			}
			return Array;
		}

		public long nextLong()
		{
			return long.Parse(next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextLong() + add;
			}
			return Array;
		}

		public double nextDouble()
		{
			return double.Parse(next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextDouble() + add;
			}
			return Array;
		}
	}
}

Measured memory_bytes: 33500
#include <bits/stdc++.h>
 
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
// #define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
 
struct S002 {
  int n;
  S002& operator > (long& x) {
    n = x;
    return *this;
  }
  S002& operator > (long&& x) {
    n = x;
    return *this;
  }
  S002& operator >= (long& x) {
    if( scanf("%ld", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (double& x) {
    if( scanf("%lf", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (std::string& s) {
    if( not (std::cin >> s) ) exit(0);
    return *this;
  }
  template<typename a>
  S002& operator >= (std::vector<a>& v) {
    v.resize(n);
    for(long i = 0; i < n; ++i) {
      *this >= v[i];
    }
    return *this;
  }
  template<typename a, std::size_t s>
  S002& operator >= (std::array<a, s>& x) {
    for(long i = 0; i < (long)s; ++i) {
      *this >= x[i];
    }
    return *this;
  }
};


struct Solver {
  std::array<std::string, 3> xs;
  Solver() {
    S002 reader;
    reader >= xs;
  }
  void solve() {
    puts(*xs[0].rbegin() == *xs[1].begin() and
	 *xs[1].rbegin() == *xs[2].begin()     ? "YES" : "NO");
  }    
  ~Solver() { fprintf(stderr, "--end--\n"); }
};
 

int main() {
  loop std::unique_ptr<Solver>(new Solver())->solve();
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;

int main() {
  int N; cin >>N;
  set<string> U;
  REP(i, N){
    string s; cin >>s;
    U.insert(s);
  }
  bool o = false;
  int M; cin >>M;
  REP(i, M){
    string s; cin >>s;
    if(U.find(s) == U.end()) cout <<"Unknown " <<s <<endl;
    else{
      cout <<(!o ? "Opened by " : "Closed by ") <<s <<endl;
      o = (o + 1) % 2;
    }
  }
  return 0;
}

Measured memory_bytes: 1232
mod=1000000007
n=input()
a=map(int, raw_input().split())
fac=[1]
for i in range(1, 100001):
	fac.append(fac[-1]*i%mod)
inv=[0, 1]
for i in range(2, 100001):
	inv.append(-(mod/i)*inv[mod%i]%mod)
inv_sum=[0]
for i in range(1, 100000):
	inv_sum.append((inv_sum[-1]+inv[i+1])%mod)
result=0
for i in range(n):
	result+=(inv_sum[i]+1+inv_sum[n-i-1])*a[i]%mod
	result%=mod
print result*fac[n]%mod


Measured memory_bytes: 19148
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
mod = 10**9+7

memo = [{} for _ in range(N+1)]

def ok(x, y, z, nx):
    if y=='A' and z=='G' and nx=='C':
        return False
    if x=='A' and z=='G' and nx=='C':
        return False
    if y=='G' and z=='A' and nx=='C':
        return False
    if y=='A' and z=='C' and nx=='G':
        return False
    if x=='A' and y=='G' and nx=='C':
        return False
    return True

def dfs(idx, lis):
    if idx==N:
        return 1
    x, y, z = lis
    if (x, y, z) in memo[idx]:
        return memo[idx][(x, y, z)]
    ret = 0
    for nx in ['A', 'G', 'C', 'T']:
        if ok(x, y, z, nx):
            ret += dfs(idx+1, (y, z, nx))
    memo[idx][(x, y, z)] = ret%mod
    return ret%mod

print(dfs(0, 'TTT'))

Measured memory_bytes: 75944
def s():
 for e in iter(input,'0 0'):
  w,h=map(int,e.split())
  M=[[[1,0]*2 for _ in[0]*h]for _ in[0]*w]
  for i in range(1,w):
   for j in range(1,h):
    a,b=M[i-1][j][:2]
    c,d=M[i][j-1][2:]
    M[i][j]=[d,a+b,b,c+d]
  print((sum(M[w-2][h-1][:2])+sum(M[w-1][h-2][2:]))%10**5)
if'__main__'==__name__:s()


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

int main(void){
    int W, H, x, y, r;
    cin >> W >> H >> x >> y >> r;
    
    if(0 <= (x - r) && (x + r) <= W && 0 <= (y - r) && (y + r) <= H) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3040
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define INT(x) int x; scanf("%d",&x)
#define LL(x) ll x; scanf("%lld",&x)
#define INPUT(x) cin >> x
#define REP1(x,n) for(int x = 0; x < n; x++)
#define REP2(x,s,e) for(int x = s; x <= e; x++)
#define RREP1(x,n) for(int x = n-1; x >= 0; x--)
#define RREP2(x,s,e) for(int x = s; x >= e; x--)
#define BR printf("\n")
#define INF_INT 2147483647
#define INF_LL 9223372036854775807

typedef long long ll;

char table[6] = "MARCH";
int num_table[5] = {};

int com[10][5] = {
    {1,1,1,0,0},
    {1,1,0,0,1},
    {1,0,0,1,1},
    {0,0,1,1,1},
    
    {1,1,0,1,0},
    {1,0,1,0,1},
    {0,1,0,1,1},
    
    {1,0,1,1,0},
    {0,1,1,0,1},
    
    {0,1,1,1,0}
};

int main(){
    INT(N);
    REP1(i,N){
        string s;
        cin >> s;
        REP1(j,5){
            if(table[j] == s[0]) num_table[j]++;
        }
    }
    ll sum = 0;
    
    REP1(i,10){
        ll temp = 1;
        REP1(j,5){
            if(com[i][j] == 1){
                temp *= num_table[j];
            }
        }
        sum += temp;
    }
    
    cout << sum << endl;
    
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <string>
using namespace std;
int main (){
    int N,i,j;
    string S;
    cin >> N >> S;
    for(i=0;i<S.size();i++){
        for (j=0;j<N;j++){
            if(S[i]=='Z')S[i]='A';
            else{
                S[i]++;
            }
        }
    }
    cout << S << endl;
    return 0;
}

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

int N, total;
vector<int> B;

int main() {
  cin >> N;
  for (int i = 0; i < N - 1; i++) {
    int number;
    cin >> number;
    B.push_back(number);
  }

  total = 0;

  total += B[0];
  for (int i = 0; i < B.size() - 1; i++) {
    total += min(B[i], B[i + 1]);
  }
  total += B[N - 2];

  cout << total << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a:A) cin >> a;}

void topsort(int v, const VVI &G, vector<bool> &seen, VI &order){
    seen[v] = true;
    for(int nv : G[v]){
        if (seen[nv]) continue;
        topsort(nv, G, seen, order);
    }
    order.push_back(v);
}

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

int V, E; cin >> V >> E;
VVI G(V);
rep(_, 0, E){
    int s, t;  cin >> s >> t;
    G[s].push_back(t);
}

vector<bool> seen(V, 0);
VI order; // トポロジカルソート順。
rep(v, 0, V){
    if (seen[v]) continue;
    topsort(v, G, seen, order);
}
reverse(ALL(order));

for(int i: order) cout << i << "\n";

return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 問題文から考える。自分ができることから考える。
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索。逆から考える。
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．




Measured memory_bytes: 4048
#include <stdio.h>
#include <algorithm>
typedef long long LL;

int n,mx=0;
LL ans=0;

int main(){
	scanf("%d",&n);
	for(int i=1,a;i<=n;i++){
		scanf("%d",&a);
		mx = std::max(mx,a);
		ans += mx-a;
	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 3248
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>

using namespace std;

int main() {
	int n, m, x, a;
	cin >> n >> m >> x;

	int s = 0, t = 0;
	for (int i = 0; i < m; i++) {
		cin >> a;

		a < x ? s++ : t++;
	}

	cout << min(s, t) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;

typedef long long Int;
typedef pair<Int,Int> P;
#define print(x) cout<<(x)<<endl

#define INF10 10000000000
#define INF5 100000
#define EPS 1e-10
#define MOD 1000000007


int main() {
	string O, E;
	string out;
	cin >> O >> E;
	for (int i = 0; i < O.size() + E.size(); i++) {
		if (i % 2 == 1)out += E[i/2];
		else out += O[i/2];
	}
	print(out);





	return 0;
}

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

int main (){
    int a , b ,ans;
    char op;
    
    while(1){
        cin >> a >> op >> b;
    if (op == '+'){
        ans = a + b;
        cout << ans <<endl;
    }
    else if (op == '-'){
        ans = a-b;
        cout << ans << endl;
    }
    else if (op == '*'){
        ans = a * b;
        cout << ans << endl;
    }
    else if(op == '/'){
        ans = a / b;
        cout << ans << endl;
        
    }
    else if(op == '?') break;    
    }
    
    return 0;
}


Measured memory_bytes: 3064
#include <numeric>
#include<iostream>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
using namespace std;
#define inf 1000000007
#define int long long
#define rep(i,j,n) for(int i=j;i<n;i++)
typedef pair<int,int>  P;
struct edge{int to,cost;};
double pi = 3.141592653589793;
//使うやつはここから下に置こうな
signed main(){
    int a[3];cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    if((a[1]-a[0])%2==0)cout<<(a[1]-a[0])/2+a[2]-a[1]<<endl;
    else {
        a[0]++;a[2]++;
        cout<<(a[1]-a[0])/2+a[2]-a[1]+1<<endl;
    }
    return 0;
}



Measured memory_bytes: 256