akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
class Main{
   public static void main(String[] args)throws java.io.IOException{
    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        
      String tmp = input.readLine();
      int S = Integer.parseInt(tmp);
  
      int h=0,m=0,s=0;
  
        
      s = S%60;
      m = (S/60)%60;
      h = S/3600;
  
      System.out.println(h+":"+m+":"+s);
    }
}

Measured memory_bytes: 16872
// Template from https://techracho.bpsinc.jp/jhonda/2019_08_05/78537

// input macro for competive-programming from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[allow(unused_macros)]
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)*}
    };

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

#[allow(unused_macros)]
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<_>>()
    };

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

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

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

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

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();

    println!("{}", solve(&s));
}

macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
r#"0 5"# => r#"5"#,
r#"1 11"# => r#"1100"#,
r#"2 85"# => r#"850000"#,
r#"0 100"# => r#"101"#,
r#"1 100"# => r#"10100"#,
r#"2 100"# => r#"1010000"#,
}


fn solve(src: &str) -> String {
    input! {
        source = src,
        d: usize,
        n: usize,
    }

    (100usize.pow(d as u32) * if n == 100 { 101 } else { n }).to_string()
}

Measured memory_bytes: 4352
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

const ll mod=1e9+7;

const ll INF=1e10+100;

int main()
{
    ll a,b,c;
    cin >> a >> b >> c;
    ll s=a*100+b*10+c;
    if(s%4==0) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
} 

Measured memory_bytes: 3544
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>

using namespace std;
typedef long long ll;
#define INF int(1e9)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define REPONE(i, n) for(int i = 1; i <= (int)(n); i++)
#define EACH(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(int i = m;i < n;i++)

const int MAX_N = 200000;
int N, X_copy[MAX_N];
vector<int> X;

void solve() {
    sort(X.begin(), X.end());
    REP(i, N) {
        if (X_copy[i] <= X[(N - 1) / 2]) cout << X[N / 2] << endl;
        else cout << X[(N - 1) / 2] << endl;
    }
}

int main() {
    cin >> N;
    int temp = 0;
    REP(i, N) {
        cin >> temp;
        X.emplace_back(temp);
        X_copy[i] = temp;
    }
    solve();
    return 0;
}

Measured memory_bytes: 3828
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll mod=1e9+7;
const int inf=1<<30;

ll dp[1000010][2];

int main(){
  string s; cin >> s;
  reverse(all(s));
  int n=s.size();
  rep(i,n+1)rep(j,2) dp[i][j]=inf;
  dp[0][0]=0;
  rep(i,n){
    int nd=s[i]-'0';
    chmin(dp[i+1][1],10-nd+dp[i][0]);
    chmin(dp[i+1][1],10-nd-1+dp[i][1]);
    chmin(dp[i+1][0],nd+dp[i][0]);
    chmin(dp[i+1][0],nd+1+dp[i][1]);
    dp[i+1][1]%=mod;
    dp[i+1][0]%=mod;
  }
  ll ans=min(dp[n][1]+1,dp[n][0]);
  cout << ans << endl;
}

Measured memory_bytes: 17028
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mod 1000000007ll
const ll maxn = 9e18;
using namespace std;

ll arr[200005], f[5];
void solve() {
	int n;
	cin >> n;
	ll ans = 9e18;
	for(int i = 1;  i <= n; ++i) cin >> arr[i], f[i] = arr[i] + f[i - 1];
	for(int i = 1; i < n; ++i) {
		ll a = f[i], b = f[n] - f[i];
		ans = min(ans, abs(a - b));
		}
		cout << ans << endl;
}

int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout.precision(35);
	solve();
	return 0;
	}


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

#define foreach(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
#define BETWEEN(a, x, b) (a<=x&&x<b)

using namespace std;
typedef long long ll;

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int a,b;cin>>a>>b;
  cout<< max( max(a+b, a-b), a*b) <<endl;

  return 0;
}


Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;


vector<int> divisor(int n) 
{
    vector<int> ret;
    for(int 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()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    
    map<int ,int> a;
    
    int buf;
    for(int i=0;i<n;i++){
        cin >> buf;
        a[buf]++;
    }

    int ans=0;
    vector<int> vec;
    for(auto p1: a){
        if(p1.second>=2) continue;
        
        bool check=true;
        vec = divisor(p1.first);

        for(int i=0;i<vec.size();i++){
            if(vec[i]==p1.first) continue;
            if(a[vec[i]]>0){
                check=false;
                break;
            }
        }

        if(check) ans++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 32424
#include <bits/stdc++.h>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
#define EPS (1e-10)
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
	ll h,w,n; cin>>h>>w>>n;
	ll a[n], b[n]; rep(i,n) cin>>a[i]>>b[i], a[i]--, b[i]--;
	int dh[9]={-1,-1,-1,0,0,0,1,1,1}, dw[9]={-1,0,1,-1,0,1,-1,0,1};
	map<PII,ll> d;
	rep(i,n){
		int u=a[i], v=b[i];
		rep(j,9){
			if(u+dh[j]<1||u+dh[j]>h-2||v+dw[j]<1||v+dw[j]>w-2) continue;
			d[MP(u+dh[j],v+dw[j])]++;
		}
	}

	ll e[9]; CLR(e);
	ll s=0LL;
	for(auto q: d){
		PII p; ll x; tie(p,x)=q;
		// cerr<<p.first SP p.second SP x<<endl;
		e[x-1]++; s++;
	}

	cout<<(h-2)*(w-2)-s<<endl;
	rep(i,9) cout<<e[i]<<endl;

	return 0;
}


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

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    ll t;
    cin>>t;
    ll sum{0};
    if(t<1000)
    {
        cout<<1000-t<<endl;
    }
    else if(t%1000==0)
    {
        cout<<0<<endl;
    }
    else if(t>1000)
    {
        while(t>sum)
        {
            sum=sum+1000;
        }
        cout<<sum-t<<endl;
    }
    return 0;
}

Measured memory_bytes: 3652
n = int(input())
a = list([])
b = list([])
c = list([])

happy = list([0 for i in range(3)] for j in range(n))

for i in range(n):
    aa,bb,cc = list(map(int, input().split()))
    a.append(aa)
    b.append(bb)
    c.append(cc)

happy[0] = [a[0], b[0], c[0]]

for i in range(1,n):
    happy[i][0] = max(happy[i-1][1], happy[i-1][2]) + a[i]
    happy[i][1] = max(happy[i-1][0], happy[i-1][2]) + b[i]
    happy[i][2] = max(happy[i-1][0], happy[i-1][1]) + c[i]

print(max(happy[-1]))

Measured memory_bytes: 36284
let n = Scanf.scanf "%d\n" (fun x -> x)

let ls =
  let rec aux n tmp =
    if n = 0 then List.rev tmp
    else
      let line = Scanf.scanf "%d %d %d\n" (fun t x y -> (t, x, y)) in
      aux (n - 1) (line :: tmp)
  in
  aux n [(0, 0, 0)]


let rec solve = function
  | [] | [_] -> "Yes"
  | (pt, px, py) :: ((nt, nx, ny) :: _ as t) ->
    let dift = nt - pt and difd = abs (nx - px) + abs (ny - py) in
    if difd <= dift && (dift + difd) mod 2 = 0 then solve t
    else "No"


let () = solve ls |> print_endline

Measured memory_bytes: 9984
use std::cmp;
use std::cmp::{max, Reverse};
use std::collections::BTreeMap;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let vw = (0..n)
        .map(|_| (sc.read::<usize>(), sc.read::<usize>()))
        .collect::<Vec<_>>();
    let q: usize = sc.read();
    let queries = (0..q)
        .map(|_| (sc.read::<usize>() - 1, sc.read::<usize>()))
        .collect::<Vec<_>>();
    let max_l = queries.iter().map(|q| q.1).max().unwrap();

    let mut cache = vec![vec![0; max_l + 1]];
    cache[0][vw[0].1] = vw[0].0;
    for i in 0..max_l {
        cache[0][i + 1] = max(cache[0][i + 1], cache[0][i]);
    }
    for i in 1..n {
        if i >= 1 << 10 {
            break;
        }
        let parent = (i - 1) / 2;
        let mut dp = cache[parent].clone();
        let (v, w) = vw[i];
        for i in (0..max_l).rev() {
            if i + w <= max_l {
                dp[i + w] = max(dp[i + w], dp[i] + v);
            }
        }
        cache.push(dp);
    }

    for (mut cur, capacity) in queries.into_iter() {
        let mut path = vec![];
        while cur >= cache.len() {
            path.push(vw[cur]);
            cur = (cur - 1) / 2;
        }

        let mut ans = 0;
        let n = path.len();
        for mask in 0..(1 << n) {
            let mut v = 0;
            let mut w = 0;
            for i in 0..n {
                if mask & (1 << i) == 0 {
                    continue;
                }
                v += path[i].0;
                w += path[i].1;
            }

            if w > capacity {
                continue;
            }

            let remain = capacity - w;
            ans = cmp::max(ans, cache[cur][remain] + v);
        }

        sc.write(ans);
        sc.write("\n");
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 811152
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

long P = 10^^9+7;
long[10^^5*2+50] F, RF;

long pow(long x, long n) {
    long y = 1;
    while (n) {
        if (n%2 == 1) y = (y * x) % P;
        x = x^^2 % P;
        n /= 2;
    }
    return y;
}

long inv(long x)
{
    return pow(x, P-2);
}

void init()
{
    F[0] = F[1] = 1;
    foreach (i, ref x; F[2..$]) x = (F[i+1] * (i+2)) % P;

    {
        RF[$-1] = 1;
        auto x = F[$-1];
        auto k = P-2;
        while (k) {
            if (k%2 == 1) RF[$-1] = (RF[$-1] * x) % P;
            x = x^^2 % P;
            k /= 2;
        }
    }
    foreach_reverse(i, ref x; RF[0..$-1]) x = (RF[i+1] * (i+1)) % P;
}

long comb(N)(N n, N k)
{
    if (k > n) return 0;
    auto n_b = F[n];    // n!
    auto nk_b = RF[n-k]; // 1 / (n-k)!
    auto k_b = RF[k];    // 1 / k!

    auto nk_b_k_b = (nk_b * k_b) % P; // 1 / (n-k)!k!

    return (n_b * nk_b_k_b) % P;  // n! / (n-k)!k!
}

Tuple!(long, long)[] prime_division(long n)
{
    Tuple!(long, long)[] res;
    foreach (long i; 2..10^^6+1) {
        if (n%i == 0) {
            long cnt;
            while (n%i == 0) {
                ++cnt;
                n /= i;
            }
            res ~= tuple(i, cnt);
        }
    }
    if (n != 1) res ~= tuple(n, 1L);
    return res;
}

void main()
{
    init();
    auto nm = readln.split.to!(long[]);
    auto N = nm[0];
    auto M = nm[1];

    auto ps = prime_division(M);
    long r = 1;
    foreach (p; ps) {
        r = r * comb(N+p[1]-1, N-1) % P;
    }
    writeln(r);
}

Measured memory_bytes: 3436
#include<bits/stdc++.h>
using namespace std;
const int N=605,mod=1e9+7;
typedef long long ll;
ll dp[N][N],F[N];
int sum[N],p[N];
bool vis[N][N];
vector<int>v[N];
ll f(int x)
{
    if(x<=1) return 1;
    if(F[x]) return F[x];
    return F[x]=x*f(x-2)%mod;
}
ll g(int x){if(x&1) return 0;return f(x-1);}
int main()
{
    int n,k;scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        p[x]=y;p[y]=x;
    }
    n*=2;
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(!p[i]);
    ll ans=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
    {
        if((sum[j]-sum[i-1])&1) continue;
        bool flag=true;
        for(int k=i;k<=j;k++)
            if(p[k]&&(p[k]<i||p[k]>j)) {flag=false;break;}
        if(!flag) continue;
        dp[i][j]=g(sum[j]-sum[i-1])%mod;
        for(int k=i+1;k<j;k++)
            dp[i][j]=(dp[i][j]-dp[i][k]*g(sum[j]-sum[k])%mod)%mod;
        ans=(ans+dp[i][j]*g(n-k*2-sum[j]+sum[i-1]))%mod;
    }
    ans=(ans+mod)%mod;
    printf("%lld\n",ans);
}


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

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

ll X, D, N,ST;
map<ll,ll> m;
vector<pll> vv;
ll i, j, k,ans;

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

int main(){
    scanf("%lld%lld%lld", &N, &X, &D);
    if(D<0){
        X = -X;
        D = -D;
    }
    if(D==0){
        if(X==0){
            printf("1");
        }else{
            printf("%lld", N + 1);
        }
        return 0;
    }
    vv.push_back({1e9, -1});
    j = 1;
    while(N*-X>=j*D){
        j *= 10;
    }
    fornum(i,0,N+1){
        vv.push_back({(i * X + D * j) % D, i});
    }
    sort(vv.begin(), vv.end());
    i = 0;
    while(i<=N){
        //printf("%lld ", i);
        ll a = vv[i].first;
        vector<pll> vv2;
        while(a==vv[i].first){
            ll ii = vv[i].second;
            ll l = ii * X + (ii * (ii - 1) / 2) * D;
            ll r = ii * X + (N * (N - 1) / 2 - (N - ii) * (N - ii - 1) / 2) * D;
            vv2.push_back({l, r});
            i++;
        }
        sort(vv2.begin(), vv2.end());
        a = -1e18;
        fornum(j,0,vv2.size()){
            if(a>=vv2[j].second)
                continue;
            //printf("%lld:%lld\n", j, ans);
            ans += (vv2[j].second - max(a, vv2[j].first - D)) / D;
            a = vv2[j].second;
        }
    }
    printf("%lld", ans);
    return 0;
}

Measured memory_bytes: 10348
fun main(args: Array<String>){
    d1()
}

class Dice(val face_origin: List<Int>,val roll: String){

    val face = face_origin.toMutableList()

    fun print_dice(){
        println(face)
        println(roll)
    }

    fun dice_rotation():MutableList<Int>{
        for(i in 0..roll.length-1){
            val direction = roll.substring(i,i+1)
            var tmp:Int
            when{
                direction == "N" ->{
                    tmp=face[0];face[0]=face[1];face[1]=face[5];face[5]=face[4];face[4]=tmp
                }
                direction == "E" ->{
                    tmp=face[0];face[0]=face[3];face[3]=face[5];face[5]=face[2];face[2]=tmp
                }
                direction == "W" ->{
                    tmp=face[0];face[0]=face[2];face[2]=face[5];face[5]=face[3];face[3]=tmp
                }
                direction == "S" ->{
                    tmp=face[0];face[0]=face[4];face[4]=face[5];face[5]=face[1];face[1]=tmp
                }
            }
        }
        return face
    }
}

fun d1(){
    val a = readLine()!!.split(" ").map(String::toInt)
    val b = readLine()!!
    val dice1 = Dice(a,b)
    val c = dice1.dice_rotation()
    println(c[0])
}


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


int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  vector<int> num(100000);
  int64_t sum = 0;
  for (int i = 0; i < N; i++) {
      cin >> vec.at(i);
      num.at(vec.at(i) - 1)++;
      sum += vec.at(i);
  }
  
  int Q;
  cin >> Q;
  vector<int> b(Q);
  vector<int> c(Q);
  for (int i = 0; i < Q; i++) cin >> b.at(i) >> c.at(i);
  
  for (int i = 0; i < Q; i++) {
      sum += (c.at(i) - b.at(i)) * num.at(b.at(i) - 1);
      cout << sum << endl;
      num.at(c.at(i) - 1) += num.at(b.at(i) - 1);
      num.at(b.at(i) - 1) = 0;
  }
}


Measured memory_bytes: 4836
"""memo
    いつものように，numpyを使いたくなかったので他人のコードを参考にした．
    enumerateは「https://note.nkmk.me/python-enumerate-start/」を参考．
"""

def main2():
    #1:初期化
    s = input()
    t = input()
    v = [0] * (len(t) + 1)
    dp = [v]
    #print(v)
    #print(dp)

    #2:初期値(いらない)

    #3:dp実行部(貰うDP)
    for str1 in s:
        v = v.copy()
        #print(i, str1, u, v)
        dp.append(v)
        #print("in",*dp,sep="\n")
        ll, ul = 0, 0
        for j, str2 in enumerate(t, 1):
            uu = v[j]
            if str1 == str2:
                v[j] = ll = ul + 1
            else:
                if ll > uu:
                    v[j] = ll
                else:
                    ll = uu
            ul = uu
        #print("out",*dp,sep="\n")
            
    # #4:出力
    #print(*dp,sep="\n")
    res = ""
    s_len = len(s)
    t_len = len(t)
    while s_len > 0 and t_len > 0:
        if dp[s_len][t_len] == dp[s_len-1][t_len]:
            s_len -= 1
        elif dp[s_len][t_len] == dp[s_len][t_len-1]:
            t_len -= 1
        else:
            res = s[s_len-1] + res
            s_len -= 1
            t_len -= 1
    print(res)

if __name__ == '__main__':
    main2()

Measured memory_bytes: 312820
S = input()
T = input()
lenS = len(S)
lenT = len(T)

for i in range(lenS - lenT, -1, -1):
    flag = True
    for ii in range(lenT):
        if S[i+ii] == '?' or S[i+ii] == T[ii]:
            continue
        else:
            flag = False
            break
    if flag == True:
        print((S[:i] + T + S[i + lenT:]).replace('?', 'a'))
        exit()
print('UNRESTORABLE')


Measured memory_bytes: 3060
from collections import deque
n,m = map(int,input().split())
v = [[] for i in range(n)]
f = [False]*n
step = [-1]*n
for i in range(m):
    a,b = map(int,input().split())
    v[a-1].append(b-1)
    v[b-1].append(a-1)
q = deque([(0,0)])
while(q):
    vi,s = q.popleft()
    #print(vi,s)
    if not(f[vi]):
        f[vi]=True
        step[vi]=s
        s+=1
        for vij in v[vi]:
            q.append((vij,s))
print("Yes")
for i in range(1,n):
    si = step[i]
    for vij in v[i]:
        if step[vij]==si-1:
            print(vij+1)
            break

Measured memory_bytes: 53248
#include <iostream>
#define NIL -1
struct Node {
    int parent, left, right;
};
int getDepth(Node* nodeList, int index)
{
    int parent = nodeList[index].parent;
    int depth = 0;
    while (parent != NIL) {
	depth++;
	parent = nodeList[parent].parent;
    }
    return depth;
}
std::string getType(Node* node)
{
    if (node->parent == NIL) {
	return "root";
    } else if (node->left == NIL) {
	return "leaf";
    } else {
	return "internal node";
    }
}
std::string getChildList(Node* nodeList, int index)
{
    if (nodeList[index].left == NIL) {
	return "";
    }
    std::string childList = "";
    int child = nodeList[index].left;
    while (child != NIL) {
	childList += std::to_string(child);
	child = nodeList[child].right;
	if (child != NIL) {
	    childList += ", ";
	}
    }
    return childList;
}

void print(Node* nodeList, int n)
{
    for (int i = 0; i < n; i++) {
	std::cout << "node " << i << ": ";
	std::cout << "parent = " << nodeList[i].parent << ", ";
	std::cout << "depth = " << getDepth(nodeList, i) << ", ";
	std::cout << getType(&nodeList[i]) << ", ";
	std::cout << "[" << getChildList(nodeList, i) << "]";
	std::cout << std::endl;
    }
}

Node* setNode(int index, int childNum, int* childList, Node* nodeList)
{
    for (int i = 0; i < childNum; i++) {
	nodeList[childList[i]].parent = index;
	if (i + 1 < childNum) {
	    nodeList[childList[i]].right = childList[i + 1];
	}
    }
    if (childNum > 0) {
	nodeList[index].left = childList[0];
    }
    return nodeList;
}
int main()
{
    int n;
    std::cin >> n;
    Node* nodeList = (Node*)malloc(n * sizeof(Node));
    //?????????
    for (int i = 0; i < n; i++) {
	nodeList[i].parent = NIL;
	nodeList[i].left = NIL;
	nodeList[i].right = NIL;
    }

    for (int i = 0; i < n; i++) {
	int index;
	int childNum;
	int* childList;
	std::cin >> index;
	std::cin >> childNum;
	childList = (int*)malloc(childNum * sizeof(int));
	for (int i = 0; i < childNum; i++) {
	    std::cin >> childList[i];
	}
	nodeList = setNode(index, childNum, childList, nodeList);
    }
    print(nodeList, n);
}

Measured memory_bytes: 8596
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>//sort,reverse
#include<utility>//pair
#include<queue>//queue,priority queue
#include<deque>//double_ended queue
using namespace std;
int main()
{ 
    int n;
    int ans;
    cin>>n;
    if(n%2==1){
        ans=(n-1)/2;
    }
    else{
        ans=(n-2)/2;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <unistd.h>

#define N 1000000
const int mod = 998244353;

int n;
int A[N+1];

char ibuf[1600100];
char *ibufe = ibuf-1;

void readall(){
  int k, t = 0;
  while((k=read(STDIN_FILENO, ibuf+t, sizeof(ibuf)-t))>0) t += k;
}

int read_uint(){
  int x=0;
  while(*(++ibufe) <'0');
  do {
    x *= 10;
    x += *ibufe-'0';
  } while(*(++ibufe) >='0');
  return x;
}

char buf[20];
char *bufe = buf;

void write_uintll(long long int x){
  int i;
  static char tmp[14];
  if(x==0){
    *bufe++ = '0';
    *bufe++ = '\n';
    return;
  }

  for(i=0; x; i++){
    tmp[i] = '0' + x % 10;
    x /= 10;
  }
  for(i--; i >= 0; i--){
    *bufe++ = tmp[i];
  }
  *bufe++ = '\n';
}

void writeall(){
  int k, t = 0;
  while((k=write(STDOUT_FILENO, buf+t, bufe-buf-t))>0) t += k;
}


/*
\sum_{i<j} lcm(Ai,Aj)
\sum_{i<j} Ai Aj / gcd(Ai,Aj)
\sum_{d} 1/d \sum_{i<j: gcd(Ai, Aj) = d} Ai Aj

f(d) = \sum_{i,j: gcd(Ai, Aj) = d} Ai Aj
F(d) = \sum_{i,j: d | gcd(Ai, Aj)} Ai Aj
F(d) = \sum_{i,j: d | Ai, d | Aj)} Ai Aj
F(d) = (\sum_{i: d | Ai} Ai)^2
\sum_{d} 1/d \sum_{n: d|n} m(n/d) F(n)
\sum_{n} F(n) \sum_{d: d|n} 1/d m(n/d)
\sum_{n} F(n)/n \sum_{d: d|n} n/d m(n/d)
\sum_{n} F(n)/n \sum_{d: d|n} d m(d)
\sum_{d: d|n} d m(d) = \sum_{d: p|d|n} d m(d) + \sum_{d: d|n/p^k} d m(d)
= \sum_{d: d|n/p^k} pd m(pd) + \sum_{d: d|n/p^k} d m(d)
= \sum_{d: d|n/p^k} d m(d) - pd m(d)
=(1-p0)(1-p1)...(1-pm)

[1    0    0] Z [1 0 0]
[0 2^-1    0]   [0 2 0]
[0    0 3^-1]   [0 0 3]
*/


template<int M>
struct const_arrs {
  constexpr const_arrs() : phi(), primes(), ps() {
    phi[1] = 1;
    for(int i=2;i<=N;i++){
      if(!phi[i]){
        phi[i] = mod+1-i;
        for(int j=2*i;j<=N;j+=i){
          if(phi[j]) phi[j] = (long long) phi[j] * (mod+1-i) % mod;
          else phi[j] = mod+1-i;
        }
        primes[ps++] = i;
      }
      phi[i] = (long long) phi[i] * i % mod;
    }
  }
  int phi[M+1];
  int primes[80000];
  int ps;
};
constexpr const_arrs<N> C{};

int main(){
  int r, s;
  
  readall();
  n = read_uint();
  s = 0;
  for(int i=0;i<n;i++){
    int x = read_uint();
    A[x]++;
    s += x;
    if(s >= mod) s -= mod;
  }

  for(int j=0;j<C.ps;j++){
    int p = C.primes[j];
    for(int i=N/p; i; i--){
      A[i] = (A[i] + (long long) p*A[i*p]) % mod;
    }
  }
  r = mod-s;
  for(int i=1;i<=N;i++){
    r = (r + (long long) A[i] * A[i] % mod * C.phi[i]) % mod;
  }

  write_uintll(r&1?(r+mod)/2:r/2);
  writeall();

  return 0;
}


Measured memory_bytes: 5376
def Bubble_Sort(n, L):
    flag = True
    j = 0
    count = 0
    while flag:
        flag = False
        for i in range(n-1, j, -1):
            if L[i] < L[i - 1]:
                L[i], L[i - 1] = L[i - 1], L[i]
                count += 1
                flag = True
    return count

n = int(input())
L = list(map(int, input().split()))

s = Bubble_Sort(n, L)
print(*L)
print(s)


Measured memory_bytes: 5604
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()

print((n-1)*n//2)

Measured memory_bytes: 38256
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        String[] s = scanner.next().split("T");
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        List<Integer> xList = new ArrayList<>();
        List<Integer> yList = new ArrayList<>();
        int i = 0;
        for (String t : s) {
            if (i++ % 2 == 0) {
                xList.add(t.length());
            } else {
                yList.add(t.length());
            }
        }

        if (x < 0 && xList.stream().mapToInt(Integer::intValue).sum() <= -x && xList.get(0) != 0) {
            System.out.println("No");
        } else {
            System.out.println(f(xList.toArray(new Integer[0]), x) && f(yList.toArray(new Integer[0]), y) ? "Yes" : "No");
        }
    }

    static boolean f(Integer[] a, int n) {
        boolean[][] dp = new boolean[a.length + 1][18000];
        dp[0][9000] = true;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < 18000; j++) {
                if (0 <= j - a[i]) {
                    dp[i + 1][j] |= dp[i][j - a[i]];
                }
                if (18000 > j + a[i]) {
                    dp[i + 1][j] |= dp[i][j + a[i]];
                }
            }
        }
        return dp[a.length][n + 9000];
    }
}

Measured memory_bytes: 131096
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 998244353
 
int main() {
 
	ll n;
	cin>>n;
	vector<ll> A(n);
	for(int i=0;i<n;i++) {
		cin>>A[i];
	}
	bool flag=0;
	for(int i=n-1;i>0;i--) {
		if(A[i]>=A[i-1]) continue;
		else A[i-1] -= 1;
		if(A[i]<A[i-1]){
			flag=1;
			break;
		}
	}
	if(flag==1)
		cout<<"No"<<endl;
	else 
		cout<<"Yes"<<endl;
 
	return 0;
} 

Measured memory_bytes: 1024
a = list(map(int,input().split()))
x = list(map(int,input().split()))
y = list(map(int,input().split()))
x_max = max(x)
y_min = min(y)
X = a[2]
Y = a[3]
check = 'War'
for i in range(X+1,Y+1):
    if (x_max < i) and (y_min >= i):
        check = 'No War' 
print(check)

Measured memory_bytes: 3064
import java.util.Scanner;
    
class Main {    
    public static void main(String[] args) { 
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(),zero=0;
        long[] arr = new long[n];
        long ans = 1;
        for(int i=0;i<n;++i) {
            arr[i] = in.nextLong();
            if(arr[i]==0) zero=1;
        }
        if(zero==1) {
            System.out.println("0");
            return ;
        }
        
        for(int i=0;i<n;++i) {
            if(ans <= 1000000000000000000L/arr[i]) ans = ans*arr[i];
            else {
                System.out.println("-1");
                return;
            }
        }
        System.out.println(ans);
    }
}

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n;
int a[maxn];

const int N = 1e5 + 10;
int bit[maxn];

void add(int i, int dx) {
    i += N;
    for (; i<=2*N; i+=i&-i) {
	bit[i] += dx;
    }
}

int qry(int i) {
    i += N;
    int res = 0;
    for (; i; i-=i&-i) {
	res += bit[i];
    }

    return res;
}


// True if (median of the subarrays) >= median
bool test(int median) {
    for (int i=0; i<=2*(N+2); i++) {
	bit[i] = 0;
    }


    
    int acc=0;
    add(acc, 1);
    
    ll cnt = 0;
    for (int i=1; i<=n; i++) {
	acc += (a[i]>=median ? +1 : -1);
	cnt += qry(acc);
	add(acc, 1);
    }

    //cout<<median<<": "<<cnt<<endl;
    
    ll len = 1ll*n*(n+1)/2;
    return cnt >= (len+1)/2;
    
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }

    int lo = 1;
    int hi = 1e9 + 1;
    while (hi-lo>1) {
	int mid = (lo+hi)/2;
	if (test(mid)) {
	    lo=mid;
	} else {
	    hi=mid;
	}
    }

    cout<<lo<<endl;
    return 0;
}


Measured memory_bytes: 4836
#include<cstdio>
#include<iostream>
#include<vector>
#include<complex>
#include<algorithm>
#include<cmath>

using namespace std;

#define reps(i,f,n) for(int i=f;i<int(n);i++)
#define rep(i,n) reps(i,0,n)

typedef complex<double> Point;

const double EPS = 0.000001;

int main(){
	
	A:;
	
	int n;
	cin>>n;
	
	if(n==0)return 0;
	
	vector<Point> point;
	rep(i,n){
		double a,b;
		cin>>a>>b;
		point.push_back(Point(a,b));
	}
	
	int ans = 1;
	rep(i,n){
		rep(j,n){
			if(i==j)continue;
			
			Point p1 = point[j];
			Point p0 = point[i];
			
			Point diff = p1-p0;
			Point d2 = diff/Point(2,0);
			
			double dlen = abs(d2);
			if(dlen>1.0)continue;
			
			double clen = sqrt(1-dlen*dlen);
			Point e = d2*Point(0,1);
			e = e/Point(abs(e),0)*Point(clen,0);
			
			Point t = p0 + d2 + e;
			
			int count = 0;
			rep(k,n){
				if(abs(t-point[k])<=1.0+EPS)count++;
			}
			ans = max(ans,count);
		}
	}
	
	printf("%d\n",ans);
	
	goto A;
}
/*
3
6.47634 7.69628
5.16828 4.79915
6.69533 6.20378

2
0 0
0.8 0

2
0 0
0.5 0.5

2
0 0
0 2

6
7.15296 4.08328
6.50827 2.69466
5.91219 3.86661
5.29853 4.16097
6.10838 3.46039
6.34060 2.41599

*/

Measured memory_bytes: 1260
#include<bits/stdc++.h>
using namespace std;   //author: madmin2619/mintu_agarwal
     
#define nfs() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//#define int long long int
#define endl "\n"
#define pb push_back
#define pf push_front
#define forin(i, n) for(int i=0;i<n;i++)
#define tr(c, it) for(auto it=c.begin();it!=c.end();it++)
#define sz(c) c.size()
#define all(c) c.begin(),c.end()
#define ff first
#define ss second
#define m_p(x, y) make_pair(x, y)

//const int inf = 1e15L;     
const int M = 1e9 + 7;
     
int32_t main(){
    nfs()
    int n, i, j, k, W, sum=0;
    cin >> n;
    vector<int> a(n), b(n), c(n), dp1(n), dp2(n), dp3(n);
    forin(i, n) cin >> a[i] >> b[i] >> c[i];
    dp1[0]=a[0];
    dp2[0]=b[0];
    dp3[0]=c[0];
    for(i=1;i<n;i++){
        if(dp1[i-1]>dp2[i-1])
            dp3[i]=dp1[i-1]+c[i];
        else
            dp3[i]=dp2[i-1]+c[i];

        if(dp2[i-1]>dp3[i-1])
            dp1[i]=dp2[i-1]+a[i];
        else
            dp1[i]=dp3[i-1]+a[i];

        if(dp3[i-1]>dp1[i-1])
            dp2[i]=dp3[i-1]+b[i];
        else
            dp2[i]=dp1[i-1]+b[i];
    }
    int res=max(dp1[n-1], dp2[n-1]);
    res=max(res, dp3[n-1]);
    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 2560
package main

import (
	"fmt"
	"strings"
)

type line struct {
	s string
}

func main() {
	var n int
	n = 1
	// fmt.Scan(&n, &m)

	lines := []line{}
	for i := 0; i < n; i++ {
		l := line{}
		fmt.Scan(&l.s)
		lines = append(lines, l)
	}
	// fmt.Println(lines)

	test := func(lines []line) string {
		for _, l := range lines {
			rest := ""
			for _, c := range l.s {
				rest = string(c) + rest
			}
			rTerms := []string{"maerd", "remaerd", "esare", "resare"}
			i := 0
			for i == 0 {
				for _, t := range rTerms {
					i = strings.Index(rest, t)
					if i == 0 {
						rest = rest[len(t):]
						break
					}
				}
			}
			if rest == "" {
				return "YES"
			}
		}
		return "NO"
	}
	fmt.Println(test(lines))
}


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

int main()
{
    int n;cin>>n;
    vector<long long> a(n);
    int i;
    for(i=0;i<n;i++)cin>>a.at(i);
    vector<long long> sum(n+1,0);
    for(i=1;i<=n;i++)sum.at(i)=sum.at(i-1)+a.at(i-1);
    long long ans=1e+15;
    long long kans;
    for(i=1;i<n;i++)
    {
        kans=abs(sum.at(i)-(sum.at(n)-sum.at(i)));
        ans=(kans<ans)?kans:ans;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// 遅延 区間和
class LazySegmentTree{
public:
    int n;
    vector<ll> node, lazy;

    LazySegmentTree(vector<ll> v){
        int sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, 0);
        lazy.resize(2*n-1, 0);
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[2*i+1] + node[2*i+2];
    }

    void eval(int k, int l, int r){
        if(lazy[k] != 0){
            node[k] += lazy[k];

            if(r - l > 1){
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }

            lazy[k] = 0;
        }
    }

    void add(int a, int b, ll x, int k=0, int l=0, int r=-1){
        if(r < 0) r = n;

        eval(k, l, r);

        if(b <= l || r <= a) return ;

        if(a <= l && r <= b){
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else{
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

    ll getsum(int a, int b, int k=0, int l=0, int r=-1){
        if(r < 0) r = n;
        if(b <= l || r <= a) return 0;

        eval(k, l, r);
        if(a <= l && r <= b) return node[k];
        ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};

int main(){
    ll n,d,a;cin >> n >> d >> a;
    vector<pair<int,int>> c(n);
    for(int i=0;i<n;i++){
        int x,h;cin >> x >> h;
        c[i]={x,h};
    }
    sort(c.begin(),c.end());
    vector<ll> x(n),h(n);
    for(int i=0;i<n;i++){
        x[i]=c[i].first;
        h[i]=c[i].second;
    }
    LazySegmentTree seg(vector<ll>(n,0));
    ll sum=0;
    vector<ll> b(n);
    for(int i=0;i<n;i++){
        ll cnt=max(0LL,(h[i]+seg.getsum(i,i+1)+a-1)/a);
        sum+=cnt;
        int t=upper_bound(x.begin(),x.end(),x[i]+2*d)-x.begin();
        seg.add(i,t,-a*cnt);
    }
    cout << sum << endl;
}

Measured memory_bytes: 14720
S = input()
x0 = int(S[:2])
x1 = int(S[2:])

if 0 < x0 <= 12 and 0 < x1 <= 12:
    print('AMBIGUOUS')
elif 0 < x0 <= 12:
    print('MMYY')
elif 0 < x1 <= 12:
    print('YYMM')
else:
    print('NA')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
//----***やべーやつら***----
using namespace std;
#define int long long

//----***型定義***----
using ll = long long;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
typedef long double ld;
typedef pair<int,int> P;

//----***Like a Pythonista***----
#define REP(ii,jj,nn) for (ll ii=jj;ii<(nn);ii++)
#define RREP(ii,nn,jj) for (ll ii = nn; jj<ii;ii--)
#define each(i,...) for (auto&& i:__VA_ARGS__)
#define ALL(vec) (vec).begin(),(vec).end()
#define sum(...) accumulate(ALL(__VA_ARGS__),0LL)
#define dsum(...) accumulate(ALL(__VA_ARGS__),0.0L)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

//----***定数***----
#define MOD 1000000007
#define INF 10*60
#define EPS 1e-9

//----***入出力***---
#define print(out) cout<< out  << "\n";
#define debug(var)  do{std::cerr << #var << " ↓ "<<"\n";view(var);}while(0);
#define dbg cerr<<"🥺🥺🥺🥺🥺🥺"<<endl;
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

//----***初期時読み込み***----
struct initial{initial(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}initial_;


signed main(){
  int N,a;cin>>N;
  vector<int> V(2*N);
  REP(i,2,N+1){
    int tmp=i;
    REP(j,2,N+1){
      while(tmp%j==0){
        V.at(j)++;
        tmp/=j;
      }
    }
  }
  int ans=1;
  REP(i,2,N+1){
    ans*=V.at(i)+1;
    ans%=MOD;
  }
  print(ans)

}


Measured memory_bytes: 256
#include <cstdlib>
#include <fstream>
#include <iostream>

using namespace std;

struct Node {
    int key;
    Node *parent, *left, *right;
};
/*
 * 
 */
//NIL mean null
Node *root, *NIL;


void insert(int key) {
    Node *y = NIL;
    Node *x = root;
    Node *z;
    
    z = (Node *)malloc(sizeof(Node));
    z -> key = key;
    z -> left = NIL;
    z -> right = NIL;
    
    while(x != NIL) {
        y = x;
        if(x -> key < key) {
            //??????
            x = x -> right;
        }
        else {
            //??????
            x =  x -> left;
        }
    }
    
    z -> parent = y;
    if(y == NIL) {
        root = z;
    }
    else if(y -> key < key) {
        y -> right = z;
    }
    else {
        y -> left = z;
    }
}


bool find(int key) {
    Node *node = root;
    while(node != NIL) {
        if(node -> key == key) {
            cout << "yes" << endl;
            return true;
        }
        else if(node -> key < key) {
            //??????
            node = node -> right;
        }
        else if(node -> key > key){
            //??????
            node = node -> left;
        }

    }
    cout << "no" << endl;
    return false;
}

void printInOrder(Node *node) {
    if(node == NIL) {
        return;
    }
    printInOrder(node -> left);
    cout << " " << node -> key;
    printInOrder(node -> right);
}

void printPreOrder(Node *node) {
    if(node == NIL) {
        return;
    }
    cout << " " << node -> key;
    printPreOrder(node -> left);
    printPreOrder(node -> right);
}

void releaseTree(Node *node) {
    if(node == NIL) {
        return;
    }
    releaseTree(node -> left);
    releaseTree(node -> right);
    free(node);
}
int main(void) {
    //ifstream ifs;
    //ifs.open("./input.txt", ifstream::in);
    
    int num, key;
    string command;
    cin >> num;
    
    for(int i = 0; i < num; i++) {
        cin >> command;
        if(command[0] == 'i') {
            cin >> key;
            insert(key);
        }
        else if(command[0] == 'p') {
            printInOrder(root);
            cout << endl;
            printPreOrder(root);
            cout << endl;
        }
        else if(command[0] == 'f') {
            cin >> key;
            find(key);
        }
    }
    
    releaseTree(root);
   
    return 0;
}

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

std::vector<ll> v(5);
std::vector<ll> a(6);

ll divide(ll a, ll b)
{
  if(a%b==0) return a/b;
  return a/b+1;
}

void print(std::vector<ll> a)
{
  std::vector<ll>::iterator itr;
  for(itr=a.begin(); itr!=a.end(); itr++)
  {
    cout << *itr << " ";
  }
  cout << endl;
}

int main()
{
  ll n;
  cin >> n;
  ll m=LONG_MAX;
  for(int i=0; i<5; i++)
  {
    ll tmp;
    cin >> tmp;
    if(m>tmp) m = tmp;
  }


  cout << 4+divide(n,m) << endl;

  /*
  int time=0;

  a[0] = n;
  while(a[5]!=n)
  {
    cout << "time = " << time <<" : ";
    print(a);
    for(int i=4; i>=0; i--)
    {
      if(a[i]!=0){
        ll tmp = min(a[i],v[i]);
        a[i+1] += tmp;
        a[i] -= tmp;
      }
    }
    time++ ;
  }
  cout << "time = " << time <<" : ";
  print(a);
  */
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int A[3][3];
bool seen[3][3];
 
int main(){
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
      cin >> A[i][j];
    }
  }
  int N; cin >> N;
  int b[N];
  for(int i=0; i<N; i++) cin>>b[i];
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
      seen[i][j] = false;
      for(int k=0; k<N; k++){
        if(A[i][j] == b[k]) seen[i][j] = true;
      }
    }
  }
  string ans = "No";
  for(int i=0; i<3; i++){
    if(seen[0][i] and seen[1][i] and seen[2][i]) ans = "Yes";
  }
  for(int i=0; i<3; i++){
    if(seen[i][0] and seen[i][1] and seen[i][2]) ans = "Yes";
  }
  if(seen[0][0] and seen[1][1] and seen[2][2]) ans = "Yes";
  if(seen[0][2] and seen[1][1] and seen[2][0]) ans = "Yes";
  cout << ans << endl;
}

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

int main()
{
    string name[100001];
    int work[100001];
    int i, n, q, rest, time, head;
    cin >> n >> q;
    name[0] = "*";
    work[0] = 0;
    rest = n; time = 0; head = 0;

    for(i = 1; i <= n; i++) cin >> name[i] >> work[i];

    while(rest > 0){
        for(i = 0; i <= n; i++){
            if(work[i] > q){
                time = time + q;  // q???????????????
                name[head] = name[i];
                work[head] = work[i] - q;
                head++;
                if(head > n) head = head - n - 1;
                work[i] = 0;
            }else if(work[i] > 0){
                time = time + work[i];  // work[i]???????????????
                cout << name[i] << " " << time << endl;
                work[i] = 0;
                rest--;
            }else{}
            if(rest == 0) break;
        }
    };

    return 0;
}

Measured memory_bytes: 4536
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;

int main()
{
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> as(n);
    vector<int> bs(n);
    vector<int> cs(n);

    for (auto& a : as)
        cin >> a;
    for (auto& a : bs)
        cin >> a;
    for (auto& a : cs)
        cin >> a;

    sort(as.begin(), as.end());
    sort(bs.begin(), bs.end());
    sort(cs.begin(), cs.end());

    int64_t sum = 0;

    for (auto& b : bs) {
        auto it = lower_bound(as.begin(), as.end(), b);
        auto jt = upper_bound(cs.begin(), cs.end(), b);

        sum += (int64_t)distance(as.begin(), it) * distance(jt, cs.end());

        // cerr << distance(as.begin(), it) << ", " << distance(jt, cs.end()) << endl;
    }

    cout << sum << endl;

    return 0;
}


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

using namespace std;

typedef long long int lli;

// ####################
//  Calc nCr
// ####################
const lli MAX = 1000000;
const lli MOD = 1000000007;

lli fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void NCRinit() {
    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;
    }
}

// 二項係数計算
lli NCR(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;
}
// ####################
//  Calc nCr END
// ####################

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

    int n, num[100001] = { 1 }, sect[3] = { 0 }, x;

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

        if (num[a[i]] == 2) x = a[i];
    }

    int ss = 0;
    for (auto aa : a) {
        if (aa != x) sect[ss]++;
        else ss++;
    }

    for (int k=1; k<=n+1; k++) {
        // 0, 1(*2), 2
        cout << ( NCR(n-1, k) + 
                  MOD + 2*NCR(n-1, k-1) - NCR(sect[0]+sect[2], k-1) +
                  NCR(n-1, k-2) ) % MOD
                  << endl;
    }

    return 0;
}


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

using ll = long long;

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

    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ans += A[i] / 2;
        A[i] %= 2;
        if (i + 1 < N && A[i] > 0 && A[i + 1] > 0) {
            ans++;
            A[i + 1]--;
        }
    }
    cout << ans << endl;

    return 0;
}


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

signed main(){
    // cout << fixed << setprecision(10) << flush;

    int x, n;
    cin >> x >> n;

    vector<bool> q(101, false);
    for(int i=0; i<n; i++){
        int p;
        cin >> p;
        q[p] = true;
    }

    for(int i=0; i<=x; i++){
        if(x-i < 0 || q[x-i] == false){
            cout << x-i << endl;
            return 0;
        }
        if(x+i > 100 || q[x+i] == false){
            cout << x+i << endl;
            return 0;
        }
    }


    return 0;
}

Measured memory_bytes: 3604
s = input()
s_length = len(s)

for i in range(1, s_length):
    if (s_length - i) % 2 != 0:
        continue
    mid = (s_length - i) // 2
    if s[:mid] == s[mid:s_length-i]:
        print(s_length - i)
        break
if s_length == 2:
    print(2)

Measured memory_bytes: 3068
n = int(input())
a = list(map(int,input().split()))

for i in range(n):
    if a[i] % 2 == 1:
        pass
    else:
        if a[i] % 3 != 0 and a[i] % 5 != 0:
            print("DENIED")
            exit()
print("APPROVED")

Measured memory_bytes: 3060