akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

int gcd(int a, int b)
{
    if (!b) {
        return a;
    }

    return gcd(b, a % b);
}

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

int main()
{
    int n, k, s;
    std::cin >> n >> k >> s;

    for (int i = 0; i < k; i++) {
        std::cout << s << " ";
    }

    for (int i = 0; i < n - k; i++) {
        std::cout << (s == 1000000000 ? s - 1 : s + 1) << " ";
    }
    std::cout << std::endl;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
//#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
template<class T> bool chmax(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 (a>b) { a=b; return 1; } return 0; }

int main(){
    int n; cin>>n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    sort(all(a));
    bool nega = false, posi = false;
    if(a[0]<0)nega=true;
    if(a[n-1]>=0)posi = true;

    if(posi&&nega){
        vector<int> po, ne;
        ll ans = 0;
        rep(i,n){
            if(a[i]>=0)po.push_back(a[i]);
            else ne.push_back(a[i]);
            ans += abs(a[i]);
        }
        cout<<ans<<endl;
        while(po.size()>1){
            cout<<ne[0]<<" "<<po.back()<<endl;
            ne[0]-=po.back();
            po.pop_back();
        }
        while(ne.size()){
            cout<<po[0]<<" "<<ne.back()<<endl;
            po[0]-=ne.back();
            ne.pop_back();
        }
        return 0;
    }

    else if(posi){
        ll ans = 0;
        rep(i,n-1)ans+=a[i+1];
        cout<<ans-a[0]<<endl;
        rep(i,n-2){
            cout<<a[0]<<" "<<a[i+1]<<endl;
            a[0]-=a[i+1];
        }
        cout<<a[n-1]<<" "<<a[0]<<endl;
        return 0;
    }
    
    else {
        ll ans = 0;
        reverse(a.begin(), a.end());
        rep(i,n-1)ans-=a[i+1];
        cout<<ans+a[0]<<endl;
        rep(i,n-1){
            cout<<a[0]<<" "<<a[i+1]<<endl;
            a[0]-=a[i+1];
        }
        return 0;
    }
    return 0;
}

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

#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)

using ll = long long;
#define INF 1e9

int main(){ 
  int N;
  cin >> N;
  vector<int> d(N);
  REP(i, N){
    cin >> d[i];
  }
  sort(d.begin(), d.end());
  int ans = d[N/2] - d[N/2-1];
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 640
#!/usr/bin/env python3
from functools import reduce

mod = 10**9 + 7


def cmb(n, r, m):
    def mul(a, b):
        return a * b % m

    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over * pow(under, m - 2, m)


n, a, b = map(int, input().split())
print((pow(2, n, mod) - 1 - cmb(n, a, mod) - cmb(n, b, mod)) % mod)


Measured memory_bytes: 9636
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <istream>
#include <map>
#include <set>
#include <queue>
#define rep0(i,n) for (int i = 0; i <= (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define REP(a,b) for (int i = a; i <= (b); ++i) 
#define mREP(a,b) for (int i = a; i == (b); --i)
#define mod 1e9 + 7
typedef long long ll;
using namespace std;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	/*
	　　　　　 　 _... ..._
	　　　　　 , ´⌒ ⌒ヽ
	　　　 　 ﾉｨ（ノﾉ）ﾉ）ﾉ）
	　　　 　 （（q|.ﾟ ヮﾟﾉ|ﾊ
	　　　　　　△ﾑ,8ﾑﾌつ
	　　　　　/(ﾝ_/＿ヽ＼
	　　　　 ～～i_ﾌ_ﾌ～´
	*/
	string a, b, c;
	cin >> a >> b >> c;
	a[0] -= 32;
	b[0] -= 32;
	c[0] -= 32;
	cout << a[0] << b[0] << c[0] << endl;
	return 0;
}
 

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef vector<int> vi;
#define f first
#define s second
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> matrix;

ll dp[2];
ll ndp[2];
void solve() {
	string s;
	cin >> s;
	reverse(all(s));
	s += "0";
	dp[1] = 1e18;
	for(int i = 0; i < sz(s); i++) {
		ndp[0] = 1e18;
		ndp[1] = 1e18;
		int need = s[i] - '0';
		// if you paid exact before
		// pay exact now
		ndp[0] = min(ndp[0], dp[0] + need);
		// receive change for this one
		ndp[1] = min(ndp[1], dp[0] + (10 - need));
		// if you accepted one above
		need++;
		ndp[0] = min(ndp[0], dp[1] + need);
		ndp[1] = min(ndp[1], dp[1] + (10 - need));
		dp[0] = ndp[0];
		dp[1] = ndp[1];
	}
	cout << dp[0] << "\n";
}

// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	solve();
}


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

int main (void){
  
  int A,B,C,D,L,R;
  cin >> A >> B >> C >> D;
  
  L = A+B;
  R = C+D;
  
  if (L>R){
    cout <<"Left" << endl;
  }
    else if (L==R){
      cout <<"Balanced"<< endl;
    }
      else {
        cout << "Right" << endl;
      }
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<list>
using namespace std;
using ll = long long;
int main() {
    int N; cin >> N;
    string S; cin >> S;
    int A[300005];//iまでにあるWの個数
    int B[300005];//iまでにあるEの個数
    for (int i = 0; i < N; ++i) {
        A[i] = 0;
    }
    if (S[0] == 'W')
        A[0]++;
    for (int i = 1; i < N; ++i) {
        if (S[i] == 'W')
            A[i] = A[i - 1] + 1;
        else
            A[i] = A[i - 1];
    }
    for (int i = 0; i < N; ++i) {
        B[i] = i + 1 - A[i];
    }
    int ans = 1e9;

    for (int i = 0; i < N; ++i) {
        int sum = 0;
        if (i == 0)
            sum = B[N - 1] - B[0];
        else {
            sum += A[i - 1] + B[N - 1] - B[i];
        }
        ans = min(ans, sum);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2948
#include <iostream>
using namespace std;
int main(void){
   string s = "",t;
   while(getline(cin,t)){
       s = s+t;
   }
   for(int j='A';j<='Z';j++){
       int num=0;
       for(int i=0;i<s.size();i++){
              char c=s[i];
              if(c==j||c==j+32){
                  num++;
              }
       }
       cout << char(j+32) << " : " << num << endl;
   }
}


Measured memory_bytes: 3172
import java.util.Scanner;

public class Main {

	private static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int n = sc.nextInt();
		int[] a = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			a[i] = sc.nextInt();
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			if (a[a[i]] == i) {
				ans++;
			}
		}
		System.out.println(ans / 2);
	}
}

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

int main(){
    int a,b;
    cin>>a>>b;
    
    for(int i=ceil(a*12.5);i<(a+1)*12.5;i++){
        if(i/10==b){
            cout<<i<<endl;
            return 0;
        }
    }
    
    cout<<-1<<endl;
    return 0; 
}

Measured memory_bytes: 256
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const long long h=0x7ffffff/2,MAXN=100+5;
long long t[h];
struct Hash
{
	char st[15];
	int hash;
}s[MAXN];
int main()
{ 
    int n,sum=0,hash;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    	scanf("%s",s[i].st);hash=0;
    	int len=strlen(s[i].st);
    	for(int j=0;j<len;j++)
    		hash=(hash*len+s[i].st[j]-'a'+1)%h;s[i].hash=hash;
    	if(t[s[i].hash]>0)sum=1;++t[s[i].hash];
    	if(i>1&&s[i-1].st[strlen(s[i-1].st)-1]!=s[i].st[0])sum=1;
	}sum==0?printf("Yes"):printf("No");
    return 0;
}

Measured memory_bytes: 176384
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner kbScanner = new Scanner(System.in);
		
		int num1 = kbScanner.nextInt();
		int num2 = kbScanner.nextInt();
		int num3 = kbScanner.nextInt();
		String answer = "No";
		
		if(num1 < num2 && num2 < num3){
			answer = "Yes";
		}
		
		System.out.println(answer);
	}
}

Measured memory_bytes: 26316
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using data=pair<int,int>;
#define rep(i,N) for(i=0;i<N;i++)
#define rep1(i,N) for(i=1;i<N;i++)
#define mod 1000000007

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}
 
ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll euclidean_gcd(ll a, ll b) {
  if(a<b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)){a=b;b=r;}
  return b;
}

int main(){
  ll i,j,k,N,K,cnt=0,ansid,ans=10000000;
  cin>>N;
  vector<ll> a(N); 
  rep(i,N){
    cin>>a[i];
    cnt+=a[i];
    a[i]*=N;
  }
  rep(i,N){
    if(ans>labs(a[i]-cnt)){
      ans=labs(a[i]-cnt);
      ansid=i;
    }
  }
  cout<<ansid<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
	int n;
	int i ,j ,k ,t ;
	int namelen ,kanbanlen ;
	int cnt  = 0 ;
	char name[ 26 ] ,kanban[ 201 ] ;
	scanf("%d",&n);
	scanf("%s",name);
	namelen=strlen(name);
	for( i = 0 ; i < n ; i++ )
	{
		scanf("%s",kanban);
		kanbanlen=strlen(kanban);
		for( j = 0 ; j < kanbanlen ; j++ )
		{
			for( k = 1 ; j + ( namelen - 1 ) * k < kanbanlen ; k++ )
			{
				for( t = 0 ; t < namelen ; t++ )
				{
					if( kanban[ j + t * k ] != name[ t ] )
					{
						goto one ;
					}
				}
				cnt++ ;
				goto two ;
				one : ;
			}
		}
		two : ;
	}
	printf("%d\n", cnt);
	return 0;
}

Measured memory_bytes: 2748
#include<iostream>
using namespace std;
int main()
{
	long long int n,a,sum=0,minn=99999999,maxx=-99999999;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		sum+=a;
		if(a>maxx)
		maxx=a;
		if(a<minn)
		minn=a;
	}
	cout<<minn<<" "<<maxx<<" "<<sum<<endl;
	return 0;
 } 


Measured memory_bytes: 3124
(defun rec (acc lst x i)
  (if (<= acc x)
	(if (null lst)
	  i
	(rec (+ acc (car lst)) (cdr lst) x (1+ i)))
	(1- i)))
(compile 'rec)
(defun splitat (c line)
  (labels ((rec (line acc)
				(let ((pos (position-if (lambda(cc) (char= c cc)) line)))
				  (if pos
					  (rec (subseq line (1+ pos)) (cons (subseq line 0 pos) acc))
					(nreverse (cons line acc))))))
	(rec line nil)))
(let* ((line0 (read-line nil nil))
	   (splited0 (mapcar #'parse-integer (splitat #\space line0)))
	   (line1 (read-line nil nil))
	   (splited1 (mapcar #'parse-integer (splitat #\space line1)))
	   )
  (format t "~A~%" (rec 0 splited1 (cadr splited0) 1)))


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

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}


void solve() {
    int H, W;
    cin >> H >> W;
    const int inf = 1e9;

    map<int, int> mp; // mp[今] = 最初の位置
    multiset<int> diff; // mpで管理してる区間における 今 - 最初 の集合

    for (int i = 0; i < W; i++) {
        mp[i] = i;
        diff.insert(0);     
    }
    
    for (int i = 0; i < H; i++) {
        // cerr << "mp: ";
        // for(auto e : mp) {
        //     cerr << e << " ";
        // }
        // cerr << endl;

        // cerr << "diff: ";
        // for(auto e : diff) {
        //     cerr << e << " ";
        // }
        // cerr << endl;

        int a, b;
        cin >> a >> b;
        a--; // 半開区間 [a, b)
        auto it = mp.lower_bound(a);
        while(it->first < b && it != mp.end()) {
            if (mp.find(b) == mp.end() || it->second > mp[b]) {
                if (b == W) {
                    if (diff.find(inf) == diff.end()) {
                        diff.insert(inf);
                    }
                } else {
                    if (mp.find(b) != mp.end() && diff.find(b - mp[b]) != diff.end()) {
                        diff.erase(diff.lower_bound(b - mp[b]));
                    }
                    diff.insert(b - it->second);
                }
                mp[b] = it->second;
            }
            diff.erase(diff.lower_bound(it->first - it->second));
            it = mp.erase(it);
        }

        if (*diff.begin() >= inf) {
            cout << -1 << endl;
        } else {
            cout << *diff.begin() + i + 1 << endl;
        }
    }
    // cerr << "mp: ";
    // for(auto e : mp) {
    //     cerr << e << " ";
    // }
    // cerr << endl;
    // cerr << "diff: ";
    // for(auto e : diff) {
    //     cerr << e << " ";
    // }
    // cerr << endl;

}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}

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

using namespace std;

int main(){

        double bmi[3];

        while(scanf("%lf,%lf,%lf", &bmi[0], &bmi[1], &bmi[2]) != EOF){

                if(bmi[1] / (bmi[2] * bmi[2]) >= 25) cout << bmi[0] << endl;

        }

}

Measured memory_bytes: 1276
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
s  = input()
#  = int(input())
#  = map(int, input().split())
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

query = list('keyence')

import re

for p in range(8):
    b = ''.join(query[:p])
    a = ''.join(query[p:])

    pattern1 = r'{}{}'.format(b, a)
    pattern2 = r'^{}.*{}$'.format(b, a)
    #print(re.findall(pattern1, s))
    #print(re.findall(pattern2, s))
    if re.findall(pattern1, s) or re.findall(pattern2, s):
        print('YES')
        break
else:
    print('NO')



Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
int n;
string s;
int main(){
	cin>>n;
	for (int i=0;i<n;i++){
		cin>>s;
		mp[s]++;
	}
	cout<<mp.size()<<endl;
	return 0;
}

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

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

  vector<int> fib(n + 5);

  fib[0] = 1;
  fib[1] = 1;

  for(int i = 2; i <= n; i++) fib[i] = fib[i-2] + fib[i-1];

  cout << fib[n] << endl;; 

  return 0;

}



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

using namespace std;

int main() {

	string str;
	cin >> str;

	bool reach = false;
	bool isout = false;
	int n = str[0] - '0';
	for (int i = 1; i < str.size(); i++) {
		if (n == str[i] - '0') {
			if (reach) {
				isout = true;
			}
			else {
				reach = true;
			}
		}
		else {
			n = str[i] - '0';
			reach = false;
		}
	}
	if (isout) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}

	return 0;
}


Measured memory_bytes: 256
let n = Scanf.sscanf (read_line ()) "%d" @@ fun n -> n

let () =
  let a = n mod 10 in
  if a = 2 || a = 4 || a = 5 || a = 7 || a = 9 then
    print_endline "hon"
  else if a = 0 || a = 1 || a = 6 || a =8 then
    print_endline "pon"
  else
    print_endline "bon"

Measured memory_bytes: 3696
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <random>

using namespace std;

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define epr(...) fprintf(stderr, __VA_ARGS__)
#define db(x) cerr << #x << " = " << x << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n"; 
#define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")\n"
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)a.size()
#define pw(n) (1ll << (n))

#define equal equalll
#define less lesss
const int N = 2e5 + 10;
const long long INF = 1e9 + 19;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;


vector<int> e[N];
int color[N];
int n, m;
bool flag;

void dfs(int v, int c) {
    color[v] = c;
    for (auto u: e[v]) {
        if (color[u] == -1) {
            dfs(u, c ^ 1);
        }
        if (color[u] != (c ^ 1))
            flag = 1;
    }
}

int main(){
#ifdef HOME 
    freopen("in", "r", stdin);
#endif
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int v, u;
        scanf("%d%d", &v, &u); v--; u--;
        e[v].pb(u);
        e[u].pb(v);
    }
    int even = 0; 
    int odd = 0;
    memset(color, -1, sizeof(color));
    int one = 0;
    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            if (e[i].empty()) {
                one++;
            }
            else {
                flag = 0;
                dfs(i, 0);
                if (flag)
                    odd++;
                else
                    even++;
            }
        }
    }
    db3(odd, even, one);
    ll answer = odd + even * 2; 
    answer += odd * 1ll * even * 2;
    answer += odd * 1ll * (odd - 1);
    answer += even * 1ll * (even - 1) * 2;
    //db(answer);
    answer += one * 1ll * one;
    answer += one * 1ll * (n - one) * 2;
    cout << answer << endl;


    return 0;
}



Measured memory_bytes: 12672
n=int(input())
p=list(map(int,input().split()))
cnt=0
for i in range(n-1):
        if p[i]==(i+1):
            p[i],p[i+1]=p[i+1],p[i]
            cnt+=1
if p[-1]==n:
    cnt+=1
 
print(cnt)


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

using namespace std;

typedef long long ll;
#define SWAP(x,y,z) {if ( y > z ) swap(y,z); if ( x > y ) swap(x,y); if (y > z) swap(y,z);}


double const eps = 1e-10;
ll const mod = 1e9+7;

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

    string s,s1,result = "";
    int length;
    cin >> s;
    cin >> s1;
    length = max(s.size(),s1.size());
    for ( int i = 0; i < length; i++ )
    {
        if ( i < s.size() ) result += s[i];
        if ( i < s1.size() )result += s1[i];
    }
    cout << result;



    return 0;

    // 274751WM
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main() {
 
  int N; cin >> N;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  
  vector<int> cosuu(100010);
  for(int i=0; i<N; i++){
    cosuu.at(vec.at(i))++;
  }
  
  int ans = 1;
  for(int i=0; i<100000; i++){
    if(i == 0){
      if(cosuu.at(i) + cosuu.at(i+1) >= ans)  ans = cosuu.at(i) + cosuu.at(i+1);
    }else if(0 < i < 99999){
      if(cosuu.at(i-1) + cosuu.at(i) + cosuu.at(i+1) >= ans){
        ans = cosuu.at(i-1) + cosuu.at(i) + cosuu.at(i+1);
      }
    }else if(i == 99999){
      if(cosuu.at(i-1) + cosuu.at(i) >= ans){
        ans = cosuu.at(i-1) + cosuu.at(i) ;
      }
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 1024
#![allow(non_snake_case)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!(
        n: usize,
        mut l: [isize; n],
    );
    l.sort();
    // println!("{:?}", l);
    let mut count = 0;
    for i in 0..(n-2) {
        let a = l[i];
        for j in (i+1)..(n-1) {
            // let b = l[j];
            let wa = a + l[j];
            let left = j + 1;
            if !(l[left] < wa) {
                // sort済みなので右を探しても条件に当てはまる棒はない
                continue;
            }
            // 適合する最後のINDEX+1を返す
            let right = {
                let mut low = left;
                let mut high = n;
                while low != high {
                    let mid = (low + high) / 2;
                    if l[mid] < wa {
                        low = mid + 1;
                    } else {
                        high = mid;
                    }
                }
                high
            };
            count += right - left;
            // print!("[{},{}]", i,j);
            // println!("left:{} right:{}", left, right);
        }
    }
    println!("{}", count);
}


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

const string YES = "YES";
const string NO = "NO";

void solve(std::string S){
    int end = S.size();
    int charsUsed = 0;
  for (int start = S.size(); start >= 0; start--) {
      auto currString = S.substr(start, end-start);
      if (currString == "dream" or currString == "dreamer" or
              currString == "erase" or currString == "eraser") {
	  charsUsed += end-start;
	  end = start;
      }
  }
  if (charsUsed == S.size()) {
      cout << YES << endl;
  } else {
      cout << NO << endl;
  }
}

// Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=j; i<=k; i++)
#define FFOR(i, j, k) for(int i=j; i<k; i++)
#define DFOR(i, j, k) for(int i=j; i>=k; i--)
#define bug(x) cerr<<#x<<" = "<<x<<'\n'
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "D"
int n;
string s;
int main(){
    #ifdef Megumin
        if(fopen(taskname".inp", "r"))
            freopen(taskname".inp", "r", stdin);
    #endif // Megumin
    cin>>s;
    n=s.size();
    int ans=0;
    s='0'+s;
    FOR(i, 1, n){
        if(i%2) ans-=(s[i]=='p');
        else ans+=(s[i]=='g');
    }
    write(ans);
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
using namespace std;
int b[10001];
vector< vector< pair<int,int> > > a;
int main (){
  int n,m;
  cin>>n>>m;
  a.resize(n+1);
  int s,t,e;
  while(cin>>s>>t>>e && (s||t||e)){
    a[s].push_back(make_pair(t,e));
  }
  int L;
  cin>>L;
  for(int k=0;k<L;k++){
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
      int sumab=0;
      for(int j=0;j<a[i].size();j++) sumab+=a[i][j].second*b[a[i][j].first];
      cout <<sumab;
      if(i==n) cout<<endl;
      else  cout<<" ";
    }
  }
       
  return 0;
}

Measured memory_bytes: 2060
N = int(input())
cards = list(map(int, input().split()))
A, B = 0, 0
while cards != []:
    A += cards.pop(max(zip(cards, range(len(cards))))[1])
    if cards == []:
        break
    B += cards.pop(max(zip(cards, range(len(cards))))[1])
print(A - B)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define zero(v) memset(v,0,sizeof(v))
#define rep(i,n) for(int i=0;i<(n);i++)
#define foreach(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();it++)
#define all(v) (v).begin(),(v).end()
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
typedef long long ll;
typedef unsigned uint;
const int INF=0x3f3f3f3f;
const double EPS=1e-10;
typedef pair<int,int>P;
int inline in(){int x=0,c;for(;(uint)((c=getchar())-'0')>=10;)
{if(c=='-')return -in();if(!~c)throw ~0;}do{x=(x<<3)+(x<<1)+(c-'0');}
while((uint)((c=getchar())-'0')<10);return x;}
int n;
int A,B,C;
const int Maxn=1e5+5;
bool dp[Maxn][8][8][8];
tuple<int,int,int>bt[Maxn][8][8][8];
char op[Maxn][8][8][8];
int main(){
	cin>>n>>A>>B>>C;
	A=min(A,7);
	B=min(B,7);
	C=min(C,7);
	dp[0][A][B][C]=1;
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		rep(aa,8)rep(bb,8)rep(cc,8)if(dp[i-1][aa][bb][cc]){
			if(s=="AB"){
				if(aa){
					dp[i][aa-1][min(bb+1,7)][cc]=1;
					bt[i][aa-1][min(bb+1,7)][cc]=make_tuple(aa,bb,cc);
					op[i][aa-1][min(bb+1,7)][cc]='B';
				}
				if(bb){
					dp[i][min(aa+1,7)][bb-1][cc]=1;
					bt[i][min(aa+1,7)][bb-1][cc]=make_tuple(aa,bb,cc);
					op[i][min(aa+1,7)][bb-1][cc]='A';
				}
			}
			if(s=="BC"){
				if(cc){
					dp[i][aa][min(bb+1,7)][cc-1]=1;
					bt[i][aa][min(bb+1,7)][cc-1]=make_tuple(aa,bb,cc);
					op[i][aa][min(bb+1,7)][cc-1]='B';
				}
				if(bb){
					dp[i][aa][bb-1][min(cc+1,7)]=1;
					bt[i][aa][bb-1][min(cc+1,7)]=make_tuple(aa,bb,cc);
					op[i][aa][bb-1][min(cc+1,7)]='C';
				}
			}
			if(s=="AC"){
				if(cc){
					dp[i][min(aa+1,7)][bb][cc-1]=1;
					bt[i][min(aa+1,7)][bb][cc-1]=make_tuple(aa,bb,cc);
					op[i][min(aa+1,7)][bb][cc-1]='A';
				}
				if(aa){
					dp[i][aa-1][bb][min(cc+1,7)]=1;
					bt[i][aa-1][bb][min(cc+1,7)]=make_tuple(aa,bb,cc);
					op[i][aa-1][bb][min(cc+1,7)]='C';
				}
			}
		}
	}
	rep(aa,8)rep(bb,8)rep(cc,8)if(dp[n][aa][bb][cc]){
		cout<<"Yes"<<endl;
		int s=n,i=aa,j=bb,k=cc;
		vector<char>result;
		while(s){
			result.push_back(op[s][i][j][k]);
			int ii,jj,kk;
			ii=get<0>(bt[s][i][j][k]);
			jj=get<1>(bt[s][i][j][k]);
			kk=get<2>(bt[s][i][j][k]);
			i=ii;j=jj;k=kk;
			s--;
		}
		reverse(all(result));
		for(char x:result){
			cout<<x<<endl;
		}
		return 0;
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 703748
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.B
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = ReadLong();
            var a = ReadLongs().OrderByDescending(x => x).ToList();

            var scoreA = 0L;
            var scoreB = 0L;
            var isTurnOfA = true;
            foreach (var item in a)
            {
                if (isTurnOfA)
                {
                    scoreA += item;
                }
                else
                {
                    scoreB += item;
                }

                isTurnOfA = !isTurnOfA;
            }

            return scoreA - scoreB;
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


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

int sign(long long int num) {
  if (num==0) {
    return 0;
  }
  else {
    return num/abs(num);
  }
}

int main() {
  int n;
  cin >> n;
  vector<long long int> list(n);
  for (int i=0;i<n;i++) {
    cin >> list.at(i);
  }
  long long int count1=0,count2=0,sum=0;
  for (int i=0,s=1;i<n;i++) {
    sum+=list.at(i);
    if(sum*s<=0) {
      count1+=abs(sum)+1;
      sum=s;
      //cout << "1 " << count1 << endl;
    }
    //cout << sum << endl;
    s*=-1;
  }
  sum=0;
  for (int i=0,s=-1;i<n;i++) {
    sum+=list.at(i);
    if(sum*s<=0) {
      count2+=abs(sum)+1;
      sum=s;
      //cout << "2 " << count2 << endl;
    }
    //cout << sum << endl;
    s*=-1;
  }
  
  cout << min(count1,count2) << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    int C,N;
    cin >> C >> N;
    int P[N][N];

    for(int i=0;i<N;i++){
        string s;
        cin >> s;
        for(int j=0;j<N;j++){
            P[i][j] = (s[j] == '1');
        }
    }

    set<pair<int,int>> nS;

    for(int i=0;i<N/2;i++){
        for(int j=0;j<N/2;j++){
            int p = P[i][j] + P[N-1-i][j] + P[i][N-1-j] + P[N-1-i][N-1-j];
            if(p == 1 || p == 2 || p == 3)  nS.insert({i,j});
        }
    }

    int ans = (nS.size() == 0);
    
    for(int i=0;i<C - 1;i++){
        int D; cin >> D;
        for(int j=0;j<D;j++){
            int r,c;
            cin >> r >> c;
            r--, c--;
            P[r][c] = !(P[r][c]);
            int p = P[r][c] + P[N-1-r][c] + P[r][N-1-c] + P[N-1-r][N-1-c];

            r = min(r,N-1-r);
            c = min(c ,N-1-c);

            if(p == 1 || p == 2 || p == 3) nS.insert({r,c});
            else if(p == 0 || p == 4) nS.erase({r,c});
        }
        if(nS.size() == 0) ans++;
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 16108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<char,ll> P;

vector<P>A,B,C;
void input(vector<P> &a){
  int num;
  char ch;
  while(cin>>ch,ch!='$'){
    cin>>num;
    a.push_back(P(ch,num));
  }
}

bool check(int i){
  int n = A.size();
  int m = B.size();
  if(i+m>n) return 0;

  if(A[i].first!=B[0].first||A[i].second<B[0].second)return 0;
  if(m == 1) return 1;

  int j = 0;
  for(j++,i++;j<m-1;j++,i++)
    if(A[i].first!=B[j].first||A[i].second!=B[j].second)return 0;
  
  if(A[i].first!=B[j].first||A[i].second<B[j].second)return 0;
  
  return 1;
}

void mergePush(vector<P> &res,P a){
  int c = a.second;
  char ch = a.first;
  if(c == 0)return;
  if(res.size() && res.back().first == ch)res.back().second+=c;
  else res.push_back(P(ch,c));
}

vector<P> solve(){
  vector<P> res;
  int n = A.size();
  int m = B.size();
  int l = C.size();
  int flg = 0;

  for(int i=0;i<n;i++){
    if(!check(i)||flg++){mergePush(res,A[i]);continue;}
    A[i].second -= B[0].second;

    if(m == 1) for(int j=0;j<l;j++) mergePush(res,C[j]);
    else {
      mergePush(res,P(A[i].first,A[i].second));   
      for(int j=0;j<l;j++) mergePush(res,C[j]);
      A[i+m-1].second -= B.back().second;
    }
    i+=m-2;
  }
  return res;
}


int main(){
  input(A),input(B),input(C);
  vector<P> ans = solve();
  for(P a:ans) cout<<a.first<<" "<<a.second<<" ";
  cout<<"$"<<endl;
  return 0;
}

Measured memory_bytes: 3212
a,b,k=map(int,input().split())
for i in range(k):
  if i % 2 == 0 and a % 2 ==1:
    a=(a-1)//2
    b+=a
  elif i % 2 ==0 and a%2==0:
    a=a//2
    b+=a
  elif i%2==1 and b%2==1:
    b=(b-1)//2
    a+=b
  else:
    b=b//2
    a+=b
print(a,b)

Measured memory_bytes: 3064
import java.util.Scanner;

class Main{
     public static void main(String[] args){

        Scanner as = new Scanner(System.in);
       
        int a;
        int b;
        int c;
        int count=0;

       
           
        a = as.nextInt();
        b = as.nextInt();
        c = as.nextInt();


        for(int i=a;i<=b;i++){
                if(c%i==0)
                   count++;
             }

        System.out.println(count);
           
           
           

           
   
 }
 
}

Measured memory_bytes: 26300
#include <iostream>
#include <string>
#include <unordered_map>
#include <stdio.h>
#include <list>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

int main()
{
	int n,k;cin >>n>>k;
	vector<int> a(n);
	rep(i,n)cin >> a[i];

	int ans = 0;
	int right = 0;
	while(1)
	{
		if(ans==0)right+=k;
		else right += k-1;
		ans ++;
		if(right>=n)break;
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int r,d,x0;
  cin >> r >> d >> x0;
  rep(i,10) cout << (x0 = r*x0-d) << endl;
}


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

const int maxn = 6e3+5;
string a,b,c;
int al,bl,cl;
bool ab[maxn],ba[maxn],bc[maxn],cb[maxn],ac[maxn],ca[maxn];
bool eql(char x,char y){
	return (x==y || x=='?' || y=='?');	
}
bool  check(int k,string x,int xl,string y,int yl){
	int j;
	for (int i=0;i<xl;i++){
		j = i-k;
		if (j<0) continue;
		else if (j>=yl) break;
		else if (eql(x[i],y[j])) continue;
		else return false;	
	}
	return true;
}
int b_a,c_b;

int getl(int b_a,int c_b){
//	cout << b_a << ' ' << c_b << ' ' << al << ' ' << bl << ' ' << cl << endl;
	int lft = min(min(0,b_a),b_a+c_b);
	int rght = max(max(al,b_a+bl),b_a+c_b+cl);
//	cout << rght << ' ' << lft << ' ' << rght-lft << endl;
//	if (rght-lft == 10) cout << "this is ans!!" << endl;
	return (rght - lft);	
}

int minl=1e9;

int main(){
	cin >> a >> b >> c;
	al=a.length(),bl=b.length(),cl=c.length();
	for (int p=(-1)*(bl+cl);p<=al+cl;p++){
		if (check(p,a,al,b,bl)){
//			cout << p << ' ' << a << ' ' << al << ' ' << b << ' ' << bl << endl; 
			if (p>=0) ab[p]=1;
			else ba[-p]=1;
		}
	}
	for (int p=(-1)*(al+cl);p<=al+bl;p++){
		if (check(p,b,bl,c,cl)){
			if (p>=0) bc[p]=1;
			else cb[-p]=1;
		}
	}
	for (int p=(-1)*(al+bl);p<=bl+cl;p++){
		if (check(p,c,cl,a,al)){
			if (p>=0) ca[p]=1;
			else ac[-p]=1;
		}
	}
	for (int i=(-1)*(bl+cl);i<=al+cl;i++){
		if ((i<0 && ba[-i]) || (i>=0 && ab[i])){
			b_a = i;
			for (int j=(-1)*(al+cl);j<=al+bl;j++){
				if ((j<0 && cb[-j]) || (j>=0 && bc[j])){
					c_b = j;
					if ((i+j <= 0 && ca[-i-j]) || (i+j>0 && ac[i+j])){
						int y = getl(b_a,c_b);
						if (y < minl){
							minl = y;
						}
					}
				}
			}
		}
	}
	cout << minl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;

int a, b;

int main(){
	while (cin >> a >> b){
		cout << a + b << endl;
	}
}

Measured memory_bytes: 1160
#include "bits/stdc++.h"
#include <random>
#define REP(i, n) for (ll i = 0; i < ll(n); ++i)
#define RREP(i, n) for (ll i = ll(n) - 1; i >= 0; --i)
#define FOR(i, m, n) for (ll i = m; i < ll(n); ++i)
#define RFOR(i, m, n) for (ll i = ll(n) - 1; i >= ll(m); --i)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template <class T> bool chmin(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s; cin >> s;
  REP(i, s.size())if (s[i] == '?')s[i] = 'D';
  cout << s << endl;
}


Measured memory_bytes: 3744
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
#include <functional>
#include <cstring>
#include <queue>
#include <cmath>
#include <deque>
#include <list>
#include <iomanip>
#include <fstream>
#include <string>
#include <iterator>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, N) FOR(i, 0, N)
#define SZ(x) ((int)(x).size())

const int MAXN = 200007, INF = 100000007;

int n, p[MAXN], col[MAXN], root = -1, cur, a[MAXN], res, aroot;
vector <int> G[MAXN], A;
bool c[MAXN];

void dfs1(int v){
	col[v] = 1;
	REP(i, SZ(G[v])){
		int to = G[v][i];
		if (col[to] == 1) {root = to; return;}
		if (col[to] == 0) dfs1(to);
		if (root != -1) return;
	}
	col[v] = 2;
}

void dfs2(int v){
	col[v] = 1;
	REP(i, SZ(G[v]))
		if (col[G[v][i]] == 0) dfs2(G[v][i]);
	res = 0;
	A.clear();
	REP(i, SZ(G[v]))
		A.push_back(a[G[v][i]]);
	sort(A.begin(), A.end());
	REP(i, SZ(A))
		if (A[i] == res) ++res;
	a[v] = res;
}

int main()
{
	scanf("%d", &n);
	REP(i, n){
		scanf("%d", p + i);
		G[--p[i]].push_back(i);
		a[i] = -1;
	}
	memset(col, 0, 4*MAXN);
	memset(c, 0, MAXN);
	REP(i, n)
		if (root == -1 && col[i] == 0) dfs1(i);
	c[root] = true;
	cur = p[root];
	while (cur != root){
		c[cur] = true;
		cur = p[cur];
	}
	memset(col, 0, 4*MAXN);
	REP(i, n) if (!c[i] && col[i] == 0) dfs2(i);
	res = 0;
	A.clear();
	REP(i, SZ(G[root]))
		A.push_back(a[G[root][i]]);
	sort(A.begin(), A.end());
	REP(i, SZ(A))
		if (A[i] == res) ++res;
	a[root] = res;
	cur = p[root];
	while (cur != root){
		res = 0;
		A.clear();
		REP(i, SZ(G[cur]))
			A.push_back(a[G[cur][i]]);
		sort(A.begin(), A.end());
		REP(i, SZ(A))
			if (A[i] == res) ++res;
		a[cur] = res;
		cur = p[cur];
	}
	res = 0;
	A.clear();
	REP(i, SZ(G[root]))
		A.push_back(a[G[root][i]]);
	sort(A.begin(), A.end());
	REP(i, SZ(A))
		if (A[i] == res) ++res;
	if (a[root] == res) {printf("POSSIBLE"); return 0;}
	res = 0;
	A.clear();
	A.push_back(aroot);
	REP(i, SZ(G[root]))
		A.push_back(a[G[root][i]]);
	sort(A.begin(), A.end());
	REP(i, SZ(A))
		if (A[i] == res) ++res;
	a[root] = res;
	cur = p[root];
	while (cur != root){
		res = 0;
		A.clear();
		REP(i, SZ(G[cur]))
			A.push_back(a[G[cur][i]]);
		sort(A.begin(), A.end());
		REP(i, SZ(A))
			if (A[i] == res) ++res;
		a[cur] = res;
		cur = p[cur];
	}
	res = 0;
	A.clear();
	REP(i, SZ(G[root]))
		A.push_back(a[G[root][i]]);
	sort(A.begin(), A.end());
	REP(i, SZ(A))
		if (A[i] == res) ++res;
	if (a[root] != res) printf("IM");
	printf("POSSIBLE");
	//cout << endl; system("pause");//please
	return 0;
}//don't forget about const, please
/*
4 1
1 2 2 1
fict
*/

Measured memory_bytes: 20480
#include<stdio.h>
int main()
{
    int n,k=0,count=0;
    scanf("%d",&n);
    char s[n];
    scanf("%s",s);
    for(int i=k;i<n;i++)
    {
            if((s[i]=='A')&&(s[i+1]=='B')&&(s[i+2]=='C'))
            {
                count=count+1;
                k=i+2;
            }
    }
    printf("%d",count);
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef long double ld;
#define mp make_pair
#define pb push_back
const ll mod = 1000000007;

void sayNo() {
	cout << "No" << endl;
}

void sayYes() {
	cout << "Yes" << endl;
}

vector< ll > divisor(ll n) {
	vector< ll > ret;
	for (ll i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			ret.push_back(i);
			if (i * i != n) ret.push_back(n / i);
		}
	}
	// sort(begin(ret), end(ret));
	return (ret);
}

int main() {
	ll S;
	cin >> S;
	double dr = sqrt(S);

	ll r = ceil(dr);

	ll remain = r * r - S;

	ll x1 = 0, y1 = 0, x2 = r, y3 = r;
	ll y2 = 0, x3 = 0;

	if (remain == 0) {
		cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << x3 << " " << y3 << endl;
		return 0;
	}

	auto div = divisor(remain);
	/*
	for (auto d : div) {
		cout << d << endl;
	}
	*/
	int size = div.size();
	
	y2 = div[size - 1];
	if (y2 * y2 == remain) {
		x3 = y2;
	}
	else {
		x3 = div[size - 2];
	}

	cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << x3 << " " << y3 << endl;
	// cout << x2 * y3 - x3 * y2 << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<math.h>
#include<iomanip>
using namespace std;

#define ll long long
using vt = int; //ここで数値の型を変えられる
#define rep(i, n) for (vt i = 0; i < (vt)(n); i++)
#define reps(i, s, n) for(vt i = (vt) (s); i < (vt) (n); i++) 
#define MOD 1000000007

int main() {
	string s;
	cin >> s;
	vt q;
	cin >> q;
	deque<char> d;
	rep(i, s.size()) d.push_back(s.at(i));
	int r = 0;
	rep(i, q) {
		int x;
		cin >> x;
		if(x == 1) r++;
		else {
			int y;
			cin >> y;
			char c;
			cin >> c;
			if((y == 1 && r % 2 == 0) || (y == 2 && r % 2 == 1)) d.push_front(c);
			else d.push_back(c);
		}
	}
	if (r % 2 == 1) reverse(d.begin(), d.end());
	rep(i, d.size()) cout << d.at(i);
	return 0;
}

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

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

    vector<string> v;
    for(int i = 0; i < (int)s.size(); i++){
        for(int j = 1; j <= K; j++){
            v.push_back(s.substr(i, j));
        }
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    cout << v[K-1] << endl;

    return 0;
}

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

using namespace std;

using ll = long long;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int digit(int x) {
  int cnt = 0;
  while(x > 0) {
    x = x >> 1;
    cnt++;
  }
  return cnt;
}

int main () {
  cin.tie(0);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  vector<ll> a(n);
  map<int, bool> mp;
  int all = 0;
  for(int i=0;i<n;++i) {
    cin >> a[i];
    all ^= a[i];
    int x = a[i] ^ (a[i] - 1);
    int k = digit(x);

    mp[k] = true;
  }

  vector<int> v;
  while(all > 0) {
    v.push_back(all & 1);
    all = all >> 1;
  }
  reverse(v.begin(), v.end());
  // printv(v);
  int sz = v.size();
  int cnt = 0;
  bool now = 1;
  for(int i=0;i<sz;++i) {
    if(v[i] == now) {
      if(!mp[sz-i]) {
        cout << -1 << endl;
        return 0;
      } else {
        cnt++;
        now = !now;
      }
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b,c,d;
cin>>a>>b>>c>>d;
int ans1=min(a,b);
int ans2=min(a,c);
int ans3=min(b,c);
int ans4=max(a,b);
int ans5=max(a,c);
int ans6=max(b,c);



if(ans5-ans2<=d||ans4-ans1<=d&&ans6-ans3<=d)
{
cout<<"Yes"<<endl;}

else 
cout<<"No"<<endl;

}




Measured memory_bytes: 256