akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,m) for(long long i=0; i<m; i++)
#define per(i,m) for(long long i=m-1; i>=0; i--)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define ROF(i,n,m) for(long long i=n-1; i>=m; i--)
#define all(x) (x).begin(),(x).end()
#define EPS (1e-7)
#define INF (1e18)
#define PI (acos(-1))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
typedef pair<ll, ll> LP;

ll POW(ll x,ll n){
  if(n==0)return 1;
  if(n%2==0)return POW(x*x%MOD,n/2);
  return x*POW(x,n-1)%MOD;
}

ll gcd(ll u, ll v) {
  ll r;
  while (0 != v) {
    r = u % v; u = v; v = r;
  }
  return u;
}
 
ll KAI(ll m)
{
  if(m<0) return 0;
  if(m==0) return 1;
  return m*KAI(m-1)%MOD;
}
 
ll extGCD(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extGCD(b, a%b, y, x);
    y -= a / b * x;
    return d;
}
 
inline ll mod(ll a, ll m) {
    return (a % m + m) % m;
}
 
ll modinv(ll a) {
    ll x, y;
    extGCD(a, MOD, x, y);
    return mod(x, MOD);
}
 
ll COM(ll m,ll n)
{
  if(m<n) return 0;
  if(n<0) return 0;
  if(n==0) return 1;
  if(m==n) return 1;
  return KAI(m)%MOD*modinv(KAI(n)%MOD*KAI(m-n)%MOD)%MOD;
}

ll DEC(ll x,ll m,ll n)
{
  return x%POW(m,n+1)/POW(m,n);
}

ll keta(ll x,ll n)
{
  if(x==0)return 0;
  return keta(x/n,n)+1;
}

ll DIV(ll x,ll n)
{
  if(x==0)return 0;
  return x/n+DIV(x/n,n);
}


int main()
{
  ll a;
  string s;
  cin >> s;
  a=s.length();
  rep(i,a-1){
    if(s[i]=='A'&&s[i+1]=='C'){
      printf("Yes");
      return 0;
    }
  }
  printf("No");
}

Measured memory_bytes: 256
import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('b1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    K = read_int()
    S = read_str()
    if len(S) > K:
      res = S[:K] + '...'
    else:
      res = S
    print(res)


main()


Measured memory_bytes: 9852
// ARC091
// C - Flip,Flip, and Flip......

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

ll N, M;

ll solve(ll n, ll m) {
    if (n == 1 && m == 1) {
        return 1;
    }
    if (n > 1 && m == 1) {
        return n - 2;
    }
    if (n == 1 && m > 1) {
        return m - 2;
    }
    return max(0LL, n - 2) * max(0LL, m - 2);
}

int main() {
    cin >> N >> M;

    cout << solve(N, M) << endl;

    return 0;
}


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

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

    vector<vector<int>> t(m + 1);
    rep (i, n)
    {
        int a, b;
        cin >> a >> b;
        if (a > m)
            continue;
        t[a].push_back(b);
    }

    ll ans = 0;
    priority_queue<int> q;
    for (int i = 1; i <= m; i++)
    {
        for (auto v : t[i])
            q.push(v);
        if (!q.empty())
        {
            ans += q.top();
            q.pop();
        }
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8364
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cassert>

using namespace std;

const int N = 1e5 + 7;
const int MOD = 1e9 + 7;
const long long INF = 1LL << 60;

int n;
long long s[N];
long long fab[N], fba[N], sab[N], sba[N];
long long a, b;
int ga[N], gb[N];

void add(long long f[N], int l, int r, long long v) {
	if (l > r) return ;
	(f[l] += v) %= MOD;
	(f[r + 1] -= v) %= MOD;
}

int solve(long long a, long long b) {
	if (n == 1) return 1;
	for (int i = 0; i <= n; i++) {
		fab[i] = fba[i] = sab[i] = sba[i] = 0;
	}
	int ret = 0;
	for (int i = 2; i <= n; i++) {
		add(sab, i, i, 1);
		if (s[i] - s[i - 1] < a) break;
		if (i == n) ret++;
	}
	ga[n + 1] = gb[n + 1] = n + 1;
	for (int i = n; i >= 1; i--) {
		gb[i] = (s[i + 1] - s[i] >= b) ? gb[i + 1] : i;
		ga[i] = (s[i + 1] - s[i] >= a) ? ga[i + 1] : i;
	}
	long long cur_ab = 0, cur_ba = 0;
	for (int i = 2; i <= n; i++) {
		fab[i] = ((cur_ab += sab[i]) %= MOD);
		fba[i] = ((cur_ba += sba[i]) %= MOD);
		if (ga[i] >= n) (ret += fba[i]) %= MOD;
		if (gb[i] >= n) (ret += fab[i]) %= MOD;
		int pa = lower_bound(s + 1, s + n + 2, s[i - 1] + a) - s;
		pa = max(pa, i + 1);
		add(sba, pa, gb[i] + 1, fab[i]);
		int pb = lower_bound(s + 1, s + n + 2, s[i - 1] + b) - s;
		pb = max(pb, i + 1);
		add(sab, pb, ga[i] + 1, fba[i]);
	}
	return (ret % MOD + MOD) % MOD;
}

int main() {
	scanf("%d %lld %lld", &n, &a, &b);
	for (int i = 1; i <= n; i++) scanf("%lld", &s[i]);
	s[n + 1] = INF;
	cout << (solve(a, b) + solve(b, a)) % MOD << endl;
}


Measured memory_bytes: 4992
// input! macro is published in the following URLs.
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
// https://github.com/tanakh/competitive-rs.git
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        ws: [chars; n],
    }
    let mut set = std::collections::HashSet::new();
    let mut last_char = None;
    for w in ws.into_iter() {
        match last_char {
            Some(last_char) => {
                if w[0] != last_char {
                    println!("No");
                    return;
                }
            }
            None => {}
        }
        last_char = Some(*w.last().unwrap());
        match set.get(&w) {
            Some(_) => {
                println!("No");
                return;
            }
            None => {
                set.insert(w);
            }
        }
    }
    println!("Yes");
}


Measured memory_bytes: 4352
import math
def solve():
  s = input()
  n = len(s)
  ct = 0
  mae = -1
  usiro = 0
  times = (n+1)//2
  tim = 0
  while tim < times:
    tim += 1
    mae += 1
    usiro -= 1
    if s[mae] == s[usiro]:
      continue
    else:
      if s[mae] == "x":
        ct += 1
        usiro += 1
        tim -= 0.5
      elif s[usiro] =="x":
        ct += 1
        mae -= 1
        tim -= 0.5
      else:
        print("-1")
        exit()
  print(ct)

solve()

Measured memory_bytes: 3316
#include<iostream>
#include<vector>
#define MAX 2000000
using namespace std;

int A[MAX+1];
int top;

void heapify(int index){
    int parent = index / 2;
    if (parent < 1) return;
    if (A[index] <= A[parent]) return;
    int tmp = A[index];
    A[index] = A[parent];
    A[parent] = tmp;
    heapify(parent);
}

void insert(int key){
    A[++top] = key;
    heapify(top);
}

void Maxheapify(int i){
    int left  = i * 2;
    int right = i * 2 + 1;
    int largest = i;
    if (left <= top  && A[left]  > A[largest]) {
        largest = left;
    }
    if (right <= top && A[right] > A[largest]) {
        largest = right;
    }
    if (largest == left || largest == right) {
        int tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        Maxheapify(largest);
    }
}

void extract(){
    cout << A[1] << endl;
    A[1] = A[top--];
    Maxheapify(1);
}

int main(){
    while (1) {
        string command;
        cin >> command;
        if (command == "end") {
            return 0;
        }
        if (command == "insert") {
            int k;
            cin >> k;
            insert(k);
            continue;
        }
        if (command == "extract") {
            extract();
            continue;
        }
    }
    return 0;
}

Measured memory_bytes: 7048
def main():
    N = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))

    ans = 0
    for i in range(N):
        attack = min(A[i],B[i])
        A[i] -= attack
        B[i] -= attack
        ans += attack
        if B[i] == 0:
            continue
        else:
            attack = min(A[i+1],B[i])
            A[i+1] -= attack
            B[i] -= attack
            ans += attack
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 18476
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [list(input()) for _ in range(n)]


a,b = map(str, input().split())


if ((a=="H" and b =="H") or (a =="D" and b == "D")):
    print("H")
else:
    print("D")



Measured memory_bytes: 9016
#include <stdio.h>
#include <stdlib.h>
int gcd(int a,int b);

int main(){
  int k;
  scanf("%d",&k);
  int gcsub[100000];
  int ct = 0;
  int sum = 0;
  for(int b=1;b<=k;b++){
    for(int c=1;c<=k;c++){
      gcsub[ct] = gcd(b,c);
      ct++;
    }
  }

  for(int a=1;a<=k;a++){
    for(int i=0;i<k*k;i++){
      sum += gcd(a,gcsub[i]);
    }
  }

  printf("%d\n",sum);
  return 0;
}


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




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

using namespace std;

typedef long long int64;

const int64 mod = 1e9 + 7;

inline int64 modPow(int64 x, int64 n)
{
  if(n == 0) return (1);
  int64 ret = modPow(x, n / 2);
  (ret *= ret) %= mod;
  if(n & 1) (ret *= x) %= mod;
  return (ret);
}

inline int64 modInv(int64 a)
{
  return (modPow(a, mod - 2));
}

int main()
{
  int64 N, D, X;
  int dp[2001];
  int64 fact[2001];

  fact[0] = 1;
  for(int i = 1; i < 2001; i++) (fact[i] = fact[i - 1] * i) %= mod;


  while(cin >> N >> D >> X, N) {

    memset(dp, 0, sizeof(dp));
    dp[0] = 1;

    int64 ret = 0, now = 1;
    for(int64 i = 1; i <= min(D, N); i++) {
      // dp[i][j] := sum[k=j-X+1..j-1] dp[i - 1][k]
      for(int64 j = 1; j <= N; j++) (dp[j] += dp[j - 1]) %= mod;
      for(int64 j = N; j > 0; j--) {
        int64 sub = (j - X < 0 ? 0 : dp[j - X]);
        dp[j] = (dp[j - 1] - sub + mod) % mod;
      }
      dp[0] = 0;
      (now *= (D - i + 1) % mod) %= mod;
      (ret += now * modInv(fact[i]) % mod * dp[N] % mod) %= mod;
    }
    cout << ret << endl;
  }
}

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

int main() {
  int n;
  cin>>n;
  
  int ans=32;
  for(int i=0;i<n;++i){
    long long a;cin>>a;
    int temp=0;
    while(a%2==0 && ans>temp){
      a/=2;
      temp++;
    }
    ans=min(temp,ans);
  }
  
  cout<<ans<<endl;
}

Measured memory_bytes: 256
(* O(n) *)
let n = Scanf.scanf " %d" @@ (+) 0
let a_s = Array.init n @@ fun _ -> Scanf.scanf " %d" @@ (+) 0
let ans = ref max_int
let _ =
  for m = 0 to 1 do
    let sum = ref a_s.(0) in
    let c = ref 0 in
    if !sum >= 0 && m = 0 then (c := abs !sum + 1; sum := -1)
    else if !sum <= 0 && m = 1 then (c := abs !sum + 1; sum := 1);
    for i = 1 to n - 1 do
      sum := !sum + a_s.(i);
      if i mod 2 = m then
        if !sum >= 0 then (c := !c + abs !sum + 1; sum := -1) else ()
      else
        if !sum <= 0 then (c := !c + abs !sum + 1; sum := 1)
    done;
    ans := min !ans !c
  done;
  Printf.printf "%d\n" !ans

Measured memory_bytes: 5376
// All Heil Fire Lord Zuko

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

#define F first
#define S second
#define PB push_back
#define debug(x) cerr << #x << " = " << x << endl

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

typedef long long ll;
typedef long double ld;

const int N = 2 * 100 * 1000 + 19;

string s[] = {"Sunny", "Cloudy", "Rainy"};

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    string tmp;
    cin >> tmp;
    for (int i = 0; i < 3; i ++)
        if (tmp == s[i])
            cout << s[(i + 1) % 3];
    return 0;
}


Measured memory_bytes: 256
// スタックサイズ: 100MB

#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
using namespace std;

typedef int64_t ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const double EPS = 1e-10;
const ll mod = 1e9 + 7;
#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define fst first
#define snd second
ll pw(ll x, ll y) { ll r = 1;  rep(i, y) { r *= x; }; return r; }




int main() {
	fastio;

	ll x, y;
	cin >> x >> y;
	cout << (abs(x - y) <= 1 ? "Brown" : "Alice") << endl;
}

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

#define f(a, n) for (int a = 0; a<n; a++)
#define F(a, n) for (int a = 1; a<= n; a++)
struct modint{
	long long const static mod=998244353;
	long long a=0;
	modint(){} // If you want to declare modints without initialising a value
	modint(long long x){
		*this = x;
	}
	void operator=(long long x){
		a=x%mod;
		if (a<0) a+=mod;
	}
	bool operator==(modint y){
		return a==y.a;
	}
	bool operator!=(modint y){
		return a!=y.a;
	}
	modint operator+(modint y){
		return modint(a+y.a);
	}
	modint operator-(modint y){
		return modint(a-y.a+mod);
	}
	modint operator*(modint y){
		return modint(a*y.a);
	}
	modint pow (modint x, int y){ //If you want bad practice, you can overload ^ too (and bug due to order of operation :) )
		if (!y) return modint(1);
		if (y%2) return x * pow(x*x, y/2);
		return pow(x*x, y/2);	
	}
	modint operator/(modint y){
		return *this*pow(y, mod-2);
	}
	modint operator^(long long x){ //Warning about order of operations
		if (x==0) return 1;
		return (x%2 ? *this : modint(1)) * (((*this) * (*this)) ^ (x/2));
	}
};
long long n, a, b, k;
const int MAXN = 300005;
modint fac[MAXN+1], invfac[MAXN+1];
void initfac(){ //rmr to init
	fac[0] = 1;
	invfac[0] = 1;
	F(i, MAXN){
		fac[i] = fac[i-1] * i;
		invfac[i] = modint(1)/fac[i];
	}
}
modint choose(long long a, long long b){
	return b>a ? 0 : fac[a]*invfac[b]*invfac[a-b];
}

modint ways(long long x){
	if (x<0 || x>n) return modint(0);
	return choose (n, x);
}

int main() {
	initfac();
	cin>>n>>a>>b>>k;
	modint ans = 0;
	f(i, n+1){
		long long tmp = k - a*i;
		if (tmp%b==0){
			long long j = tmp/b;
			ans = ans + ways(i)*ways(j);
		}
	}
	cout<<ans.a<<endl;
	
	
}

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

int main() {

  string s;
  cin >> s;

  int left = 0;
  int right = 0;

  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'A') {
      left = i;
      break;
    }
  }

  for (int i = s.size() - 1; 0 <= i; i--) {
    if (s[i] == 'Z') {
      right = s.size() - i;
      break;
    }
  }

  cout << s.size () - left - right + 1 << endl;

}

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

int main(){
  int h,w;
  while(1){
     cin >> h >> w;
     if (( h == 0 && w == 0)||( h > 300 || w > 300) )break;
       for (int i=1 ; i <= h ; i++){
	 for (int j=1 ; j <= w ; j++){
	   cout << "#";
	 }
	 cout << endl;
       }
       cout << endl;
  }

  return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
int n,m,x,y;
vin graph[110000];
int dp[110000];

int dfs(int x){
  if(dp[x]!=-1)return dp[x];
 int ret=0;
  for(auto v:graph[x]){
    chmax(ret,dfs(v)+1);
  }
  return dp[x]=ret;
}

int main(){cout<<fixed<<setprecision(10);
           cin>>n>>m;
           rep(i,0,m){
            cin>>x>>y;
             graph[x].pb(y);
           }
           rep(i,0,110000)dp[i]=-1;
           rep(i,0,n){
            dfs(i+1); 
           }
           int ans=0;
           rep(i,0,n){
            chmax(ans,dp[i+1]); 
           }
           cout<<ans<<endl;
}

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

int main() {
  int N;
  cin >> N;
  bool b = 0;

  for(int i = 0; i < N; i++){
    string S;
    cin >> S;
    if(S == "Y"){
      b = 1;
    }
  }
  
  if(b == 0){
    cout << "Three" << endl;
  }
  else{
    cout << "Four" <<endl;
  }
}


Measured memory_bytes: 256
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    s = gete()

    if s in ['RRS', 'SRR']:
        print(2)
    elif s in ['SSS']:
        print(0)
    elif s in ['RRR']:
        print(3)
    else:
        print(1)


if __name__ == "__main__":
    main()

Measured memory_bytes: 64900
#include<iostream>
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main(){
    int N, T, A;
    cin >> N >> T >> A;
    double d = 10000;
    int e = 0;
    int x;
    double gap;
    rep(i, N){
        cin >> x;
        gap = abs(T-A-0.006*x);
        if(d>gap){
            d = gap;
            e = i+1;
        }
    }
    cout << e;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<queue>
#include<map>
using namespace std;
int main(){
	int w,h;
	while(cin>>w>>h,w+h!=0){
		string ban[100];
		int sx=0,sy=0;
		queue< pair<int,int> >bfs;
		bool table[100][100];
		for(int i=0;i<100;i++)for(int j=0;j<100;j++)table[i][j]=false;
		
		for(int i=0;i<h;i++){
			cin>>ban[i];
			for(int j=0;j<ban[i].size();j++){
			if(ban[i][j]=='@')sy=i,sx=j;
			}
		}
		pair<int,int> s(sx,sy);
		bfs.push(s);
		table[sy][sx]=true;
		int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
		while(bfs.empty()==false){
			pair<int,int>now=bfs.front();
			bfs.pop();
			int nx=now.first,ny=now.second;
			for(int i=0;i<4;i++){
				if(nx+dx[i]>=0&&nx+dx[i]<w&&ny+dy[i]>=0&&ny+dy[i]<h){
					if(table[ny+dy[i]][nx+dx[i]]==false&&ban[ny+dy[i]][nx+dx[i]]=='.'){
					pair<int,int>tmp(nx+dx[i],ny+dy[i]);
					bfs.push(tmp);
					table[tmp.second][tmp.first]=true;
				}
				}
			}
		}
		int cnt=0;
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)if(table[i][j])cnt++;
		cout<<cnt<<endl;
		for(int i=0;i<100;i++)ban[i].clear();
	}
	return 0;
}

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

const int MAX = 510000;
const int MOD = 998244353;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}
// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


vector<ll> powm;

int main() {
	COMinit();
	ll n, m, k;
	cin >> n >> m >> k;
	powm.push_back(1);
	for (ll i = 1; i < n; ++i) {
		powm.push_back((powm[i - 1] * (m - 1)) % MOD);
	}
	ll ans = 0;
	for (ll i = 0; i <= k; ++i) {
		ans += (COM(n - 1, i) * powm[n - i - 1]) % MOD;
		ans %= MOD;
	}
	ans = (ans * m) % MOD;
	cout << ans << endl;
}


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

int main(){
    int n;
    cin >> n;
    REP(i,1,10){
        int ans = n/i;
        int amari = n%i;
        if(ans <10 && amari == 0){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    int x,y,tmp;
    while(1){
        scanf("%d %d",&x, &y);
        if(x==0 && y==0){
            break;
        }
        if(x>y){
            tmp = x;
            x = y;
            y = tmp;
        }
        printf("%d %d\n",x,y);
    }
    return 0;
}



Measured memory_bytes: 2044
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

using namespace std;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using P = pair<int,int>;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

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

    deque<ll> deq;
    deq.push_front(a[0]);

    for(int i=1; i<n; ++i) {
        if (a[i]<=deq.front()) deq.push_front(a[i]);
        else {
            auto iter = lower_bound(all(deq),a[i]);
            --iter;
            *iter = a[i];
        }
    }
    cout << deq.size() << endl;
    return 0;
}























Measured memory_bytes: 1792
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
struct A
{
    ll val;
    string ans;
};
bool cmp(A a,A b)
{
    return a.val>b.val;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    while(cin>>n)
    {
        map<string,ll> mp;
        ll mx=0;
        for(int i=0;i<n;i++)
        {
            string ch;
            cin>>ch;
            mp[ch]++;
            mx=max(mx,mp[ch]);
        }
        vector<string> res;
        map<string,ll> ::iterator it;
        for(it=mp.begin();it!=mp.end();it++)
        {
            if((*it).second==mx)
            {
                res.push_back((*it).first);
            }
        }
        sort(res.begin(),res.end());
        for(int i=0;i<res.size();i++)
        {
            cout<<res[i]<<endl;
        }

    }
    return 0;
}


Measured memory_bytes: 25584
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using Plint = pair<lint, lint>;

lint N, X, D;

vector<int> par;
vector<vector<int>> chi;
vector<lint> m, ms, ns;

void dfsms(int i)
{
    ms[i] = m[i];
    ns[i] = 1;
    for (auto v : chi[i])
    {
        dfsms(v);
        ms[i] += ms[v];
        ns[i] += ns[v];
    }
}

bool efficient(const Plint &a, const Plint &b) {
    return a.first * b.second > b.first * a.second;
}

int main()
{
    cin >> N >> X >> D;
    m.resize(N);
    par.resize(N);
    chi.resize(N);
    cin >> m[0]; par[0] = -1;
    for (int i = 1; i < N; i++)
    {
        cin >> m[i] >> par[i];
        par[i]--;
        chi[par[i]].push_back(i);
    }

    ms.resize(N);
    ns.resize(N);
    dfsms(0);

    vector<Plint> info;
    for (int i=0; i<N; i++) info.push_back(Plint(ns[i], ms[i]));
    sort(info.begin(), info.end(), efficient);
    // for (auto v : info) cout << v.first << " " << v.second << endl;

    lint dp[51][2501];
    memset(dp, -1, sizeof(dp));
    lint maxnum[51];
    memset(maxnum, 0, sizeof(maxnum));
    dp[0][0] = 0;

    for (int i = 1; i <= N; i++)
    {
        lint v = info[i-1].first;
        lint w = info[i-1].second;

        maxnum[i] = maxnum[i-1];
        for (int j = 0; j < 2501; j++) if (dp[i-1][j] >= 0)
        {
            if (v != N) maxnum[i] = max(maxnum[i], maxnum[i-1] - j + min((X - dp[i-1][j]) / w, D) * v);
            else maxnum[i] = max(maxnum[i], maxnum[i-1] - j + (X - dp[i-1][j]) / w * v);
        }

        for (int j=0; j<2501; j++) if (dp[i-1][j] >= 0)
        {
            for (int k=(maxnum[i]-maxnum[i-1]+j)%v; k<2501; k+=v)
            {
                lint need = (maxnum[i]-k) - (maxnum[i-1]-j);
                if (need < 0) continue;
                if (v != N && need > D * v) continue;
                lint dp_tmp = dp[i-1][j] + need / v * w;
                if (dp_tmp > X) continue;
                if (dp[i][k] < 0 || dp[i][k] > dp_tmp) dp[i][k] = dp_tmp;
            }
        }
    }
    // for (auto vec : dp)
    // {
    //     for (auto v : vec) cout << v << " ";
    //     cout << endl;
    // }
    // for (auto v : maxnum) cout << v << " ";
    cout << maxnum[N] << endl;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
struct PersistentUnionFind{
  using T = pair<int, int>;
  int n;
  vector<int> r,p;
  stack<T> st;
  PersistentUnionFind(){}
  PersistentUnionFind(int sz):
    n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
  int find(int x){
    return x==p[x]?p[x]:find(p[x]);
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    st.emplace(-1,-1);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
    st.top()=T(x,y);
  }
  void undo(int t=1){
    for(int i=0;i<t;i++){
      int x,y;
      tie(x,y)=st.top();st.pop();
      if(x<0) continue;
      r[x]-=r[y];
      p[y]=y;
    }
  }
};

struct DynamicConnectivity{
  using edge = pair<int, int>;
  using range = pair<int, int>;

  int q;
  PersistentUnionFind puf;
  vector< vector<edge> > edges;
  vector <pair<range, edge> > prc;
  map<edge, int> cnt,app;

  DynamicConnectivity(){}
  DynamicConnectivity(int n,int q_):q(1),puf(n){
    while(q<q_) q<<=1;
    edges.resize(q*2);
  }

  void insert(int t,int u,int v){
    edge e=minmax(u,v);
    if(cnt[e]++==0) app[e]=t;
  }

  void erase(int t,int u,int v){
    edge e=minmax(u,v);
    if(--cnt[e]==0) prc.emplace_back(range(app[e],t),e);
  }

  void add(int a,int b,edge e,int k,int l,int r){
    if(r<=a||b<=l) return;
    if(a<=l&&r<=b){
      edges[k].emplace_back(e);
      return;
    }
    int m=(l+r)>>1;
    add(a,b,e,(k<<1)|0,l,m);
    add(a,b,e,(k<<1)|1,m,r);
  }

  void add(range r,edge e){
    add(r.first,r.second,e,1,0,q);
  }

  void build(){
    for(auto &e:cnt){
      if(!e.second) continue;
      prc.emplace_back(range(app[e.first],q),e.first);
    }
    for(auto &s:prc)
      add(s.first,s.second);
  }

  template<typename F>
  void exec(const F &f,int k=1){
    for(auto &e:edges[k])
      puf.unite(e.first,e.second);

    if(k<q){
      exec(f,(k<<1)|0);
      exec(f,(k<<1)|1);
    }else{
      f(k-q);
    }

    puf.undo(edges[k].size());
  }
};
//END CUT HERE

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

  int n,q;
  cin>>n>>q;
  DynamicConnectivity dc(n,q);
  vector<int> ts(q),us(q),vs(q);
  for(int i=0;i<q;i++){
    cin>>ts[i]>>us[i]>>vs[i];
    if(ts[i]==1) dc.insert(i,us[i],vs[i]);
    if(ts[i]==2) dc.erase( i,us[i],vs[i]);
  }
  dc.build();
  auto f=
    [&](int x){
      if(x>=q||ts[x]!=3) return;
      cout<<(dc.puf.same(us[x],vs[x])?"YES":"NO")<<endl;
    };
  dc.exec(f);
  return 0;
}
/*
  verified on 2018/01/07
  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2235
*/



Measured memory_bytes: 14792
#include<bits/stdc++.h>
using namespace std;
#include<cstdio>
#define el "\n"
#define sp " "
typedef long long ll;

main()
{
	ios_base::sync_with_stdio(false);
		cin.tie(NULL);
	ll n,m,i,j,r=1e9+7;
	cin>>n>>m;
	ll dp[n][m];
	for(i=0;i<n;i++)
	for(j=0;j<m;j++)
	dp[i][j]=0;
	char a;
	for(i=0;i<n;i++)
	for(j=0;j<m;j++)
	{
	
	cin>>a;
	if(a=='#')
	dp[i][j]=-1;
	}
	for(i=0;i<n;i++)
	{
		if(dp[i][0]!=-1)
		dp[i][0]=1ll;
		else
		break;
	}
	for(i=0;i<m;i++)
	{
		if(dp[0][i]!=-1)
		dp[0][i]=1ll;
		else
		break;
	}
	for(i=1;i<n;i++)
	for(j=1;j<m;j++)
	{
		if(dp[i][j]==-1)
		continue;
		if(dp[i-1][j]>0)dp[i][j]=(dp[i][j]%r+dp[i-1][j]%r)%r;
		if(dp[i][j-1]>0)dp[i][j]=(dp[i][j]%r+dp[i][j-1]%r)%r;
		
	}
	cout<<dp[n-1][m-1];
	
	
	
	
}

Measured memory_bytes: 8064
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <regex>
#include <random>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exout(x) printf("%.10f\n", x)
const double pi = acos(-1.0);
const ll MOD = 1000000007;
const ll INF = 1e10;
const ll MAX_N = 1010;

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

ll dp[101010][110];
ll dx[4] = { 0,0,-1,1 };
ll dy[4] = { -1,1,0,0 };

//long longしか使わない
//素数は1より大きい
int main() {
	ll n;
	cin >> n;
	vector<ll>b(n);
	vector<ll>flag(n);
	rep(i, n) {
		cin >> b[i];
		b[i]--;
		if (b[i] > i) {
			cout << -1 << endl;
			return 0;
		}
	}
	vector<ll>ans;
	rep(j, n) {
		ll m = b.size();
		for (ll i = m - 1;i >= 0;--i) {
			if (b[i] == i) {
				ans.push_back(b[i] + 1);
				b.erase(b.begin() + i);
				break;
			}
		}
	}

	reverse(ans.begin(), ans.end());
	rep(i, n) {
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 3500
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>

using namespace std;
int a,b;
stack<int> s;

bool que(int fr,int tar){
	if(fr==tar) return 1;
	cout<<"? "<<fr<<" "<<tar<<endl;
	string x; cin>>x;
	return x[0]=='y'||x[0]=='Y';
}

int main(){
	cin>>a>>b;
	if(a<=b) return puts("Impossible"),0;
	for(int t=0;t<a+b;++t)
		if(s.empty()) s.push(t);
		else 
			if(que(s.top(),t)) s.push(t);
			else s.pop();
	string x="! ";
	for(int t=0;t<a+b;++t)
		x=x+(que(s.top(),t)?"1":"0");
	cout<<x<<endl;
	return 0;
}



Measured memory_bytes: 724
#include <bits/stdc++.h>
#define rep(i,n) for((i)=1;(i)<=(n);(i)++)
using namespace std;
const int mod=1e9+7;
int n,i,dp[200005],sum[200005],a[200005];
int main(){
	cin>>n;
	rep(i,n)cin>>a[i];
	dp[0]=1;
	rep(i,n){
		if(a[i]!=a[i-1]) (sum[a[i]]+=dp[i-1])%=mod;
		dp[i]=sum[a[i]];
	}
	cout<<dp[n]<<endl;
	return 0;
}

Measured memory_bytes: 5912
/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */

const int maxn = 15;
int n, m, p[maxn], ans = 0, a[maxn][maxn];

int main() {
    scanf("%d%d", &n, &m);
    rep1(i, 1, m) {
        scanf("%d", &a[i][0]);
        rep1(j, 1, a[i][0]) scanf("%d", &a[i][j]);
    }
    rep1(i, 1, m) scanf("%d", &p[i]);
    rep1(i, 0, (1 << n) - 1) {
        int flag = 1, cmp = i, cur[20], light[20], cnt = 0;
        rep1(i, 1, 20) cur[i] = light[i] = 0;
        while (cmp)cur[++cnt] = cmp & 1, cmp >>= 1;
        rep1(i, 1, m)
        rep1(j, 1, a[i][0]) light[i] += cur[a[i][j]];
        rep1(i, 1, m) if ((light[i] % 2) != p[i]) {
            flag = 0; break;
        }
        if (flag) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){
 int N,M;
 cin >> N >> M;

 const int nmmax=50;
 char A[nmmax][nmmax],B[nmmax][nmmax];


 for(int y=0;y<N;++y){
 for(int x=0;x<N;++x){
 cin >> A[y][x];
 }
 }

 for(int y=0;y<M;++y){
 for(int x=0;x<M;++x){
 cin >> B[y][x];
 }
}

bool exist=false;

 for(int ly=0;ly<N;++ly){
 for(int lx=0;lx<N;++lx){
 if(ly+M-1>=N or lx+M-1>=N) continue;

 bool match=true;
 for(int y=0;y<M;++y){
 for(int x=0;x<M;++x){
 if(A[ly+y][lx+x]!=B[y][x]) match=false;
 }
 }
 if(match) exist=true;
 }
 }

 if(exist)
 cout << "Yes" << endl;
 else
 cout << "No" << endl;

 return 0;
}

Measured memory_bytes: 256
#include<cstdlib>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<stack>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<vector>
#define MAXN 1000
using namespace std;
typedef long long ll;
char str[200];
int main()
{
	ios::sync_with_stdio(false);
//	freopen("../in", "r", stdin);
//	freopen("../out", "w", stdout);
	ll cnt;
	cin>>str>>cnt;
	ll sum=0;
	ll len=strlen(str);

	ll sum1=0,sum2=0;
	ll index=0;
	while(str[index]==str[index+1])
		sum1++,index++;
	sum1++;
	char z=str[0];
	ll flag=1;
	for(ll i=1;i<len;i++)
	{
		if(str[i]!=z)
			flag=0;
		if(str[i]==str[i-1])
		{
			str[i]=1;
			sum++;
		}
	}
	if(flag)
		cout<<(cnt*len)/2<<endl;
	else if(cnt==1||str[0]!=str[len-1])
	{
		cout<<cnt*sum<<endl;
	}
	else
	{
		if(sum1%2==0)
		{
			cout<<cnt*sum<<endl;
		}
		else
		{
			cout<<cnt*sum+cnt-1<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(A, S):
    return S if A >= 3200 else 'red'





def main():
    A = read_int()
    S = read_str()
    print(slv(A, S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
def main():
    n = int(input())
    aa = list(map(int, input().split()))
    counts = [0] * 3
    for a in aa:
        if a % 4 == 0:
            counts[2] += 1
        elif a % 2 == 0:
            counts[1] += 1
        else:
            counts[0] += 1
    if counts[0] <= counts[2] or counts[0] == counts[2] + 1 and counts[1] == 0:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 14252
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
d = []
for _ in range(m):
  b,c = map(int,input().split())
  d.append([c,b])
d.sort(reverse = True)
e = []
f = 0
for j in range(m):
  for k in range(d[j][1]):
    e.append(d[j][0])
    f += 1
    if f == n:
      break
  else:
    continue
  break
else:
  e += [0] * (n-len(e))
ans = 0
#print(a)
#print(e)
for i in range(n):
  ans += max(a[i],e[i])
print(ans)

Measured memory_bytes: 82200
n=int(input())
ans1=0
ans2=0

a=list(map(int,input().split()))
avg=sum(a)/n
m1=int(avg)
m2=m1+1
for i in range(n):
    ans1 += (a[i]-m1)**2
    ans2 += (a[i]-m2)**2

print(min(ans1,ans2))


Measured memory_bytes: 3064
#include <map>
#include <queue>
#include <vector>
#include <iostream>
#include <functional>
using namespace std;
class SparseTable {
private:
	vector<int> ipw;
	vector<int> val;
	vector<vector<int> > arr;
public:
	SparseTable() : ipw(vector<int>()), val(vector<int>()), arr(vector<vector<int> >()) {};
	SparseTable(vector<int> v) {
		ipw = vector<int>(v.size() + 1);
		int cur = 0;
		for (int i = 1; i <= v.size(); i++) {
			if (2 << cur < i) cur++;
			ipw[i] = cur;
		}
		val = v;
		arr = vector<vector<int> >(ipw[v.size()] + 1);
		arr[0] = vector<int>(val.size());
		for (int i = 0; i < val.size(); i++) arr[0][i] = i;
		for (int i = 1; i < ipw[v.size()] + 1; i++) {
			arr[i] = vector<int>(val.size() - (1 << i) + 1);
			for (int j = 0; j < arr[i].size(); j++) {
				arr[i][j] = (val[arr[i - 1][j]] < val[arr[i - 1][j + (1 << (i - 1))]] ? arr[i - 1][j] : arr[i - 1][j + (1 << (i - 1))]);
			}
		}
	}
	int min_index(int l, int r) {
		int lc = arr[ipw[r - l]][l];
		int rc = arr[ipw[r - l]][r - (1 << ipw[r - l])];
		return val[lc] < val[rc] ? lc : rc;
	}
	int min_query(int l, int r) {
		return val[min_index(l, r)];
	}
};
int n, p[200009]; map<pair<int, int>, pair<int, int> > d; SparseTable v0, v1;
struct state {
	int l, r;
};
bool operator<(const state& s1, const state& s2) {
	pair<int, int> spl1 = d[make_pair(s1.l, s1.r)];
	pair<int, int> spl2 = d[make_pair(s2.l, s2.r)];
	return p[spl1.first] > p[spl2.first];
}
void solve(int l, int r) {
	if (l == r) return;
	int divl = (l % 2 == 0 ? v0.min_index(l / 2, r / 2) * 2 : v1.min_index(l / 2, r / 2) * 2 + 1);
	int divr = (l % 2 == 0 ? v1.min_index(divl / 2, r / 2) * 2 + 1 : v0.min_index(divl / 2 + 1, r / 2 + 1) * 2);
	d[make_pair(l, r)] = make_pair(divl, divr);
	solve(l, divl);
	solve(divl + 1, divr);
	solve(divr + 1, r);
}
int main() {
	cin >> n;
	vector<int> ve0, ve1;
	for (int i = 0; i < n; i++) {
		cin >> p[i];
		if (i % 2 == 0) ve0.push_back(p[i]);
		else ve1.push_back(p[i]);
	}
	v0 = SparseTable(ve0);
	v1 = SparseTable(ve1);
	solve(0, n);
	priority_queue<state> que; que.push(state{ 0, n });
	for (int i = 0; i < n / 2; i++) {
		state u = que.top(); que.pop();
		pair<int, int> spl = d[make_pair(u.l, u.r)];
		cout << p[spl.first] << ' ' << p[spl.second] << ' ';
		if (u.l != spl.first) que.push(state{ u.l, spl.first });
		if (spl.first + 1 != spl.second) que.push(state{ spl.first + 1, spl.second });
		if (spl.second + 1 != u.r) que.push(state{ spl.second + 1, u.r });
	}
	return 0;
}

Measured memory_bytes: 32492
#include<stdio.h>
 /* 確認のための提出 */
int main(void){
	int h,w,n,k,i,j,m[256][256] = {0},t = 1;
	unsigned long long int x = 1,r = 0;
	scanf("%d%d%d%d",&h,&w,&n,&k);
	for(i = 0;i < h;i++){
		for(j = 0;j < w;j++){
			printf("? %d %d %d %d\n",i,j,i,j);
			fflush(stdout);
			scanf("%d",&m[i][j]);
			if(m[i][j] == 1){n--;}
			if(n == 0){t = 0;break;}
		}
		if(!(t)){break;}
	}
	for(i = 0;i < h;i++){
		for(j = 0;j < w;j++){
			if(m[i][j]){r+=x;r%=k;}
			x*=2;x%=k;
		}
	}
	printf("! %llu\n",r);
	return 0;
}

Measured memory_bytes: 724
/*author: hyperion_1724
  date: 
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	string S;
	cin>>S;
	int o=0,z=0;
	for (int i = 0; i < S.length(); ++i)
	{
		if(S[i]=='0')
		{
			z++;
		}
		if(S[i]=='1')
		{
			o++;
		}
	}
	cout<<2*min(o,z)<<endl;

	return 0;
}

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

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

int main(void) {
    int n;
    cin >> n;
    vector<ll> t(n);
    rep(i, n) {
        cin >> t[i];
    }
    ll ans = t[0];
    rep(i, n) {
        ans = lcm(ans, t[i]);
    }
    cout << ans << endl;
    return 0;
}


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

typedef struct Node
{
  struct Node *node;
  long long int value;
  int island_number;
} Node;

using namespace std;

Node *get_root_node(Node *node)
{
  if (node->node)
  {
    return get_root_node(node->node);
  }
  else
  {
    return node;
  }
}

int main(void)
{
  int N, M;
  cin >> N >> M;
  long long int sum = 0;
  vector<int> As(M);
  vector<int> Bs(M);
  for (int i = 0; i < M; i++)
  {
    int a, b;
    cin >> a >> b;
    As[i] = a;
    Bs[i] = b;
  }

  vector<Node> nodes(N);
  for (int i = 0; i < N; i++)
  {
    nodes[i].value = 1;
    nodes[i].island_number = i;
  }

  vector<long long int> ans(M);
  for (int i = M - 1; i >= 0; i--)
  {
    int a = As[i];
    int b = Bs[i];
    Node *a_root_node = get_root_node(&nodes[a - 1]);
    Node *b_root_node = get_root_node(&nodes[b - 1]);
    if (a_root_node->island_number == b_root_node->island_number)
    {
      ans[i] = sum;
      continue;
    }
    sum += a_root_node->value * b_root_node->value;
    ans[i] = sum;
    if (a_root_node->value > b_root_node->value)
    {
      b_root_node->node = a_root_node;
      a_root_node->value += b_root_node->value;
    }
    else
    {
      a_root_node->node = b_root_node;
      b_root_node->value += a_root_node->value;
    }
  }

  for (int i = 1; i < M; i++)
  {
    cout << ans[0] - ans[i] << endl;
  }
  cout << ans[0] << endl;
  return 0;
}


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

ll dp[2001][2001];
int n, m;
vector<ll> u, v;

ll recur(int p, int q) {
	if(p >= n or q >= m)
		return 0;

	ll &ret = dp[p][q]; 
	if(ret != -1)
		return ret;

	ret = 0;
	if(u[p] == v[q])
		ret = 1 + recur(p+1, q+1);
	ret = (ret + ((recur(p+1, q) + recur(p, q+1))%MOD - recur(p+1, q+1) + MOD)%MOD)%MOD;

	return ret;
}

int main() {
	cin >> n >> m;
	u.resize(n), v.resize(m);
	memset(dp, -1, sizeof dp);
	
	for(int i = 0; i < n; ++i)
		cin >> u[i];
	for(int i = 0; i < m; ++i)
		cin >> v[i];

	cout << (recur(0, 0)+1)%MOD << endl;
	return 0;
}



Measured memory_bytes: 31872
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

long getRoot(vector<long> &vec, long x) {
//  cout << "x: " << x << endl;
  if (vec[x] == -1) return x;
  else return getRoot(vec, vec[x]);
}

void find(vector<long> &vec, long x, long y) {
  long nextRoot = getRoot(vec, x);
  if (vec[y] != -1) find(vec, nextRoot, vec[y]);
  vec[y] = nextRoot;
}

int main(void) {
  long N, M;
  cin >> N >> M;
  vector<long> union_find(N);
  rep (i, N) union_find[i] = -1;
  rep (i, M) {
    long X, Y, Z;
    cin >> X >> Y >> Z;
    X--;
    Y--;
    if (getRoot(union_find, X) == getRoot(union_find, Y)) continue;
    find(union_find, X, Y);
  }
  long result = 0;
  rep (i, N) if (union_find[i] == -1) result++;
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  string S;
  cin>>S;
  char now = S[0];
  int ans = 1;
  for(int i=1;i<N;++i) {
    if(S[i]!=now) {
      ans++;
      now = S[i];
    }
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 3732
#ifndef TEMPLATE_HPP
#define TEMPLATE_HPP
#include <bits/stdc++.h>
#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 reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())
using namespace std;
using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> void amax(T &x, T y) { x = max(x, y); }
template <typename T> void amin(T &x, T y) { x = min(x, y); }
template <typename T> T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename U> vector<U> make_vector(T&& n, U&& val) { return vector<U>(forward<T>(n), forward<U>(val)); }
template <typename T, typename... Args> decltype(auto) make_vector(T&& n, Args&&... args) { return vector<decltype(make_vector(forward<Args>(args)...))>(forward<T>(n), make_vector(forward<Args>(args)...)); }
const int INF = 1001001001;
const i64 LINF = 1001001001001001001ll;
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
#endif

bool check(string s, char c) {
  rep(i, sz(s)) {
    if (s[i] != c) return false;
  }
  return true;
}

void solve() {
  string s;
  cin >> s;
  int n = sz(s);
  rep(i, n) s[i] -= 'a';
  int ans = INF;
  rep(i, 26) {
    string t = s;
    int cnt = 0;
    while (!check(t, i)) {
      string u;
      rep(j, sz(t) - 1) {
        if (t[j] == i || t[j+1] == i) u += (char) i; else u += t[j];
      }
      swap(t, u);
      cnt += 1;
    }
    amin(ans, cnt);
  }
  cout << ans << endl;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(16);
  cerr << fixed << setprecision(16);
  solve();
  return 0;
}

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

int main(void) {
    int N, diff, taroScore, hanakoScore;
    char taro[101], hanako[101];
    scanf("%d", &N);

    taroScore = 0; hanakoScore = 0;
    while(N-- > 0) {
        scanf("%s %s", taro, hanako);
        diff = strcmp(taro, hanako);
        if(diff == 0) taroScore++, hanakoScore++;
        if(diff > 0) taroScore += 3;
        if(diff < 0) hanakoScore += 3;
    }
    printf("%d %d\n", taroScore, hanakoScore);

    return 0;
}

Measured memory_bytes: 3228