akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main() {
    int x, y, p;
    while (cin >> x >> y >> p, x || y || p) {
        int ans = 0;
        for (int i = 1; i < 1000; i++) {
            for (int j = i; j < 1000; j++) {
                int pre = i * (100 + x) / 100 + j * (100 + x) / 100;
                if (pre == p) {
                    ans = max(ans, i * (100 + y) / 100 + j * (100 + y) / 100);
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}



Measured memory_bytes: 3068
use std::collections::HashSet;
use std::io::{stdin, Read};

macro_rules! parse {
    ($iter: ident) => {
        $iter.next().unwrap().parse().unwrap()
    };
    ($iter: ident,2) => {
        (parse!($iter), parse!($iter))
    };
    ($iter: ident,3) => {
        (parse!($iter), parse!($iter), parse!($iter))
    };
    ($iter: ident,4) => {
        (parse!($iter), parse!($iter), parse!($iter), parse!($iter))
    };
    ($iter: ident, $n: ident) => {
        (&mut $iter).take($n).map(|e| e.parse().unwrap()).collect();
    };
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    let mut iter = s.split_whitespace();
    let (n, u, v): (usize, usize, usize) = parse!(iter, 3);
    let u = u - 1;
    let v = v - 1;
    let mut tree: Vec<Vec<usize>> = vec![vec![]; n];
    for _ in 0..(n - 1) {
        let (a, b): (usize, usize) = parse!(iter, 2);
        tree[a - 1].push(b - 1);
        tree[b - 1].push(a - 1);
    }
    let mut du = vec![-1; n];
    let mut dv = vec![-1; n];
    du[u] = 0;
    dv[v] = 0;
    dfs(u, 1, &tree, &mut du);
    dfs(v, 1, &tree, &mut dv);
    let mut ret = 0;
    for i in 0..n {
        if du[i] < dv[i] {
            ret = std::cmp::max(ret, dv[i] - 1)
        }
    }
    println!("{}", ret);
}

fn dfs(cur: usize, curd: isize, tree: &Vec<Vec<usize>>, d: &mut Vec<isize>) {
    for &c in &tree[cur] {
        if d[c] == -1 {
            d[c] = curd;
            dfs(c, curd + 1, tree, d);
        }
    }
}


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

using ll = long long;
using db = double;
using pll = pair < ll, ll >;

#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1) {
    cerr << name << " : " << arg1 << std :: endl;
}
template < typename Arg1, typename... Args >
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

#define pb push_back
#define mp make_pair
#define fastIo() ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

const int MOD = 1e9 + 7, INF = INT_MAX, N = 1e5 + 10;

int main(){
    ll n; cin >> n;
    ll a[n];
    int64_t res = 1;
    for(ll i = 0; i < n; i++)
    	cin >> a[i];
    sort(a, a + n);
    if(a[0] == 0) {
    	cout << 0 << endl;
    	return 0;
    }
    for(ll i = 0; i < n; i++) {
        if(res > 1000000000000000000LL/a[i]) {
            cout << -1 << endl;
            return 0;
        }
        res = res * a[i];
    }
    cout << res << endl;
}

Measured memory_bytes: 4408
#include <bits/stdc++.h>
using namespace std;
int main(){
    int A,B,C,D,L,R;
    cin>>A>>B>>C>>D;
    L=A+B,R=C+D;

    if(L>R){
        cout<<"Left"<<endl;
    }
    else if(L==R){
        cout<<"Balanced"<<endl;
    }
    else{
        cout<<"Right"<<endl;
    }
}

Measured memory_bytes: 256
// 有點不耐煩會破壞偉大的計劃

#include <bits/stdc++.h>

#define append push_back

using namespace std;
using ll = long long;

const int N = 1e5 + 3;
const int M = 1e6 + 7;
const long long MOD = 1e9 + 7;
const long long INF = 1e18 + 9;
const int SM = 1e3 + 5;
const int logN = 22, BL = 400;
const double EPS = 1e-9, PI = acos(-1);
const int dx[] = {1, 0, 0, -1, -1, 1, -1, 1};
const int dy[] = {0, 1, -1, 0, -1, 1, 1, -1};

void debug() {
	cerr << "\n";
}
template<typename Type1, typename... Type2>
void debug(Type1 a, Type2... b) {
    cerr << a << " ";
    debug(b...);
}

int main() {
//    freopen(".in", "r", stdin);
//    freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
    long long n, ans = 0; cin >> n;

    for(long long i = 1; i <= n; i++) {
    	long long j = n / i, k;
    	if(j & 1) {
    		k = (j + 1) / 2;
    		k *= j;
    	}
    	else {
    		k = j / 2;
    		k *= (j + 1);
    	}
    	k *= i;
    	ans += k;	
    }
   	
    cout << ans;
    
    return 0;
}


Measured memory_bytes: 3648
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

# 解説AC
if n <= 2:
    print(int(t == a))
    exit()

ans = 1
for i in range(1, n - 1):
    ht, ha = 0, 0
    if t[i - 1] < t[i] and a[i] > a[i + 1]:
        if t[i] != a[i]:
            print(0)
            break
    if t[i - 1] < t[i]:
        if t[i] > a[i]:
            print(0)
            break
    elif a[i] > a[i + 1]:
        if t[i] < a[i]:
            print(0)
            break
    else:
        ans = ans * min(t[i], a[i]) % mod
else:
    print(ans)


Measured memory_bytes: 97724
T1,T2= map(int, input().split())
A1,A2= map(int, input().split())
B1,B2= map(int, input().split())
if A1>B1 and A2>B2:
  print(0)
elif A1<B1 and A2<B2:
  print(0)
elif T1*A1+T2*A2==T1*B1+T2*B2:
  print('infinity')
elif A1>B1 and A2<B2:
  if T1*A1+T2*A2>T1*B1+T2*B2:
    print(0)
  else:
    se=abs(T1*A1+T2*A2-(T1*B1+T2*B2))
    ad=T1*A1-T1*B1
    d=-(-ad//se)
    ans=2*d-1
    if ad%se==0:
      ans+=1
    print(ans)
elif A1<B1 and A2>B2:
  if T1*A1+T2*A2<T1*B1+T2*B2:
    print(0)
  else:
    se=abs(T1*A1+T2*A2-(T1*B1+T2*B2))
    ad=T1*B1-T1*A1
    d=-(-ad//se)
    ans=2*d-1
    if ad%se==0:
      ans+=1
    print(ans)
  


Measured memory_bytes: 9256
/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 1e5 + 10;
const ll MX = 1e9;

int main() {
	fast_cin();
	ll s; cin >> s;
	ll p = (s / MX) + !!(s % MX);
	ll r = p * MX - s;
	ll x1 = 0, y1 = 0;
	ll x2 = MX, y2 = 1;
	ll x3 = r, y3 = p;
	assert(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2) == s);
	cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << x3 << ' ' << y3 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  char a,b; cin>>a>>b;
  if(a=='H' && b=='H') cout<<'H'<<endl;
  if(a=='H' && b!='H') cout<<'D'<<endl;
  if(a!='H' && b=='H') cout<<'D'<<endl;
  if(a!='H' && b!='H') cout<<'H'<<endl;  
}

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

ll gcd(ll x, ll y) {
  if (x%y == 0) {
    return y;
  }
  
  else {
    int mod = x%y;
    x = y;
    y = mod;
    return gcd(x, y);
  }
}

ll lcm(ll x, ll y) {
  return x*y/gcd(x, y);
}

int main() {
  ll A, B, C, D;
  cin >> A >> B >> C >> D;
  
  ll U = B - A + 1;
  ll modC = (B / C) - ((A-1) / C);
  ll modD = (B / D) - ((A-1) / D);
  ll modCD = (B / lcm(C,D)) - ((A-1) / lcm(C,D));
  
  ll ans = U - modC - modD + modCD;
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <list>

using namespace std;


int main() {
    int H;scanf("%d",&H);
    int W;scanf("%d",&W);
    int D;scanf("%d",&D);

    std::vector<int> d(H*W+1,0);
    std::vector<int> px(H*W+1,0);
    std::vector<int> py(H*W+1,0);

    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            int value;scanf("%d",&value);
            px[value] = j;
            py[value] = i;
        }
    }

    for(int i=1+D;i<=H*W;i++){
        d[i] = d[i-D] + abs(px[i]-px[i-D]) + abs(py[i]-py[i-D]);
    }

    int q;scanf("%d",&q);
    for(int i=0;i<q;i++){
        int l; scanf("%d", &l);
        int r; scanf("%d", &r);
        printf("%d\n",d[r]-d[l]);
    }

    return 0;

}

Measured memory_bytes: 2176
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            while(true) {
                if (array[i] % 2 == 0) {
                    array[i] /= 2;
                    ans++;
                } else {
                    break;
                }
            }
        }
        System.out.println(ans);
    }    
}


Measured memory_bytes: 34412
import math

A,B,H,M = map(int,input().split())

a = math.pi * 2 * (H + M / 60) / 12
b = math.pi * 2 * M / 60

c = abs(a-b)
c = min(c,math.pi*2-c)

print(math.sqrt(A*A+B*B-2*A*B*math.cos(c)))

Measured memory_bytes: 62668
import Control.Applicative
import Control.Monad
import Data.List
import Text.Printf

pf m = pfsub m (2:[3,5..])
  where
    pfsub n pl@(p:ps)
      | n == 1 = []
      | r == 0 = p : pfsub q pl
      | p * p > n = [n]
      | otherwise = pfsub n ps
      where
        (q, r) = divMod n p

solve [n, p] = product [head s ^ (length s `div` n)| s <- group $ pf p]

main = map read . words <$> getLine >>= print . solve

Measured memory_bytes: 1148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
const int maxn=1e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const double pi=acos(-1);
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b,x;
    cin>>a>>b>>x;
    if(a*a*b<=x*2)
    {
        double c=2*x*1.0/a/a-b;
        cout<<fixed<<setprecision(8)<<90-atan(a/(b-c))/pi*180<<'\n';
        return 0;
    }
    double c=x*1.0/a/b;
    c*=2;
    cout<<fixed<<setprecision(8)<<90-atan(c/b)/pi*180<<'\n';
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) x.begin(),x.end()
#define dmp(x) cerr<<#x<<":"<<x<<endl
typedef pair<int,int> P;
typedef pair<int,P> PP; 
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
const int MOD = 1e9+7;

signed main(){
  int p,q,r;
  cin>>p>>q>>r;
  cout<<min({p+q,q+r,r+p})<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
#define INF 1000000000000000000
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;

vector<ll> b;
ll rec(ll n, ll x) {
    if (n == 0)
        return 1;
    ll len = (1LL << (n + 1)) - 3; //　n-1回目のバンの数 
    ll num = (1LL << (n)) - 1;     //　n-1回目のパティの数
    // xの値で場合分け
    if (x == 1)
        return 0;
    else if (x <= len + 1)
        return rec(n - 1, x - 1);
    else if (x == len + 2)
        return num + 1;
    else if (x <= (len + 1) * 2)
        return num + 1 + rec(n - 1, x - len - 2);
    else
        return num * 2 + 1;   //　ぴったり
}

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

    ll N, X;
    cin >> N >> X;
    cout << rec(N, X) << endl;
}

Measured memory_bytes: 3612
// -D_GLIBCXX_DEBUG
#include <bits/stdc++.h>
    using namespace std;
#define int long long int
// #include "../../Template.cpp"

int n;
vector<int> arr;
vector<int> prefix;

vector<vector<int>> dp;

int solve(int l, int r) {
    if(l == r) return 0;
    if(dp[l][r] != -1) {
        return dp[l][r];
    }
    int ans = 1e18;
    for(int i = l; i < r; i ++) {
        ans = min(ans, solve(l, i) + solve(i+1, r) + prefix[r] - prefix[l-1]);
    }
    dp[l][r] = ans;
    return ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    arr.assign(n+1, 0);
    prefix.assign(n+1, 0);
    for(int i = 1; i <= n; i ++) {
        cin >> arr[i];
        prefix[i] = arr[i] + prefix[i-1];
    }
    dp.assign(n+1, vector<int>(n+1, -1));
    int ans = solve(1, n);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1536
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

K = ir()
A, B = lr()
left = -(-A//K)
right = B // K
bl = left <= right
print('OK' if bl else 'NG')


Measured memory_bytes: 9180
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

int n;
vector<int> g[100005];

void dfs(int cur, vector<bool> &used, vector<int> &depth){
    used[cur] = true;
    for(auto edge:g[cur]){
        if(not used[edge]){
            depth[edge] = depth[cur] + 1;
            dfs(edge, used, depth);
        }
    }
}

int search(int k, int cur, vector<int> &depth){
    if(k == 0) return cur;
    for(auto edge:g[cur]){
        if(depth[cur] > depth[edge]){
            return search(k - 1, edge, depth);
        }
    }
    return -1e8;
}

int countNode(int cur, vector<bool> &used, vector<int> &depth){
    int res = 1;
    used[cur] = true;
    for(auto edge:g[cur]){
        if(depth[cur] < depth[edge] && not used[edge]){
            res += countNode(edge, used, depth);
        }
    }
    return res;
}

int main(){
    cin >> n;

    rep(i,n - 1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }

    vector<bool> used(n,0);
    vector<int> depth(n);
    depth[0] = 0;

    dfs(0, used, depth);
    used = vector<bool>(n,0);

    //rep(i,n) show(depth[i])
    int start = search((depth[n - 1]  - 1) / 2, n - 1, depth);
    //show(start)

    int node = countNode(start, used, depth);
    //show(node)
    cout << (n - node > node ? "Fennec" : "Snuke") << endl;
}


Measured memory_bytes: 12416
/*https://atcoder.jp/contests/abc177/tasks/abc177_d*/

//simple dfs-Count the maximum no of visited node

#include<bits/stdc++.h>
using namespace std;
vector<set<int>>graph;
vector<int>visited;
int cnt;
void dfs(int u)
{
    if(!visited[u])
    {
        visited[u]=1;
        ++cnt;
        //cout<<cnt<<"->"<<u<<endl;
    }
    for(auto v:graph[u])
    {
        if(!visited[v])
        {
            dfs(v);
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;cin>>n>>m;
	graph = vector<set<int> > (n + 1, set<int> ());
	for(int i=0;i<m;++i)
	{
	    int x,y;
	    cin>>x>>y;
	    graph[x].insert(y);
	    graph[y].insert(x);
	}
// 	for(int i=1;i<=n;++i)
// 	{
// 	    cout<<i<<"->";
// 	    for(auto it:graph[i])
// 	    {
// 	        cout<<it<<" ";
// 	    }
// 	    cout<<endl;
// 	}
    visited=vector<int>(n+1);
    int groups=0;
    for(int i=1;i<=n;++i)
    {
        cnt=0;
        if(!visited[i])
        {
            dfs(i);
        }
        groups=max(groups,cnt);
    }
    cout<<groups<<endl;
	return 0;
}


Measured memory_bytes: 38244
#include <stdio.h>
int main(void){
    int n,i,cnt=0;
    scanf("%d",&n);
    int a[n];
    for(i=0;i<n;i++) scanf("%d",&a[i]);
    for(i=1;i<n-1;i++){
        if(a[i-1]<a[i] && a[i]<a[i+1] || a[i-1]>a[i] && a[i]>a[i+1]) cnt++;
    }
    printf("%d",cnt);
}


Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(2*n);
    for(int i=0; i<2*n; ++i)
        cin >> a[i];

    sort(a.begin(), a.end());
    int ans = 0;
    for(int i=0; i<n; ++i)
        ans += a[2*i];
    cout << ans << endl;

    return 0;
}

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

#define ipr pair<int, int>
#define pb push_back
#define ff first
#define ss second
#define fr(i, j, k) for (int i = j; i < k; i++)
#define rf(i, j, k) for (int i = j; i >= k; i--)
#define int long long
#define ll unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mp make_pair
#define inf INT_MAX
#define read_file()                   \
	;                                 \
	freopen("input.txt", "r", stdin); \
	freopen("output.txt", "w", stdout);
#define IOS                           \
	std::ios::sync_with_stdio(false); \
	cin.tie(NULL);                    \
	cout.tie(NULL);

const int mod = 2019;
const ld pi = acos(-1);
const int Maxn = 1000000007;

template <class T>
ostream &operator<<(ostream &out, vector<T> &A)
{
	for (auto x : A)
		out << x << " ";
	return out;
}
template <class T>
ostream &operator<<(ostream &out, set<T> &A)
{
	for (auto x : A)
		out << x << " ";
	return out;
}
template <class T1, class T2>
T1 powr(T1 a, T2 b)
{
	T1 res = 1;
	fr(i, 1, b + 1) res = res * a;
	return res;
}



int32_t main(){IOS
	int n,m,x,ans=0;	cin>>n>>m;
	priority_queue<int> pq;
	fr(i,0,n){
		cin>>x;
		pq.push(x);
	}
	for(;!pq.empty() and m>0;m--){
		int ele = pq.top();	pq.pop();
		ele/=2;
		if(ele>0)	pq.push(ele);
	}
	while(!pq.empty()){
		ans += pq.top();	pq.pop();
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1400
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>
#include <cstdint>
#define _USE_CMATH_DEFINES

const long INF = (1l << 30);
const long LINF = (1l << 60); //1.15*10^18

int main(){
    long n;
    scanf("%ld", &n);
    long ans = 0;
    long max = 0;
    for(int i = 0; i < n; i++){
        long a;
        scanf("%ld", &a);
        if(a < max){
            ans += max - a;
        }else{
            max = std::max(max, a);
        }
    }
    printf("%ld\n", ans);
}


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

int n,k,h,w;
string s;

int main() {
  cin >> s;
  int ans=1,n=s.size(); auto t=s[0]; 
  for(int i=1;i<n;i++){
    if(i==n-2 && s[n-2]==s[n-1]) 
    i++;
    else if(s[i]==t)  
    t=s[i]+s[i+1],i++;
    else 
    t=s[i];
    ans++;
  }
  cout << ans << endl;
}

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

int main(){
	// sengen
	priority_queue<long long> que;
	long long n,m;
	// nyuryoku
	cin >> n >> m;
	LL a[n];
	for(LL i=0;i<n;i++){
		cin >> a[i];
		que.push(a[i]);
	}
	// keisan
	for(LL i=0;i<m;i++){
		LL b = que.top();
		que.pop();
		que.push(b/2);
	}
	LL ans = 0;
	for(LL i=0;i<n;i++){
		ans += que.top();
		que.pop();
	}
	// syutsuryoku
	cout << ans << endl;
}

Measured memory_bytes: 4984
#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#include<functional>
#define INF 1 << 30
using namespace std;
typedef pair<int, int> PII;
typedef priority_queue<PII, vector<PII>, greater<PII> > PQ;

int root[101][101], n, k; //not use 0;

void newboat()
{
	int c, d, e;
	cin >> c >> d >> e;
	if (root[c][d] > e)	root[c][d] = root[d][c] = e;
	return;
}

int solve()
{
	int a, b, ans = INF;
	cin >> a >> b;
	bool though[101][101]; //not use 0;
	PQ cand;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++) though[i][j] = false;
	}

	cand.push(make_pair(0, a));
	while (!cand.empty()){
		PII now = cand.top();
		cand.pop();
		if (now.second == b) return now.first;

		for (int i = 1; i <= n; i++){
			if (root[now.second][i] != INF && !though[now.second][i]){
				though[now.second][i] = though[i][now.second] = true;
				cand.push(make_pair(now.first + root[now.second][i], i));
			}
		}
	}
	return -1;
}

int main()
{
	while (true){
		cin >> n >> k;
		if (!n && !k) break;
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= n; j++) root[i][j] = INF;
		}
		for (int i = 0; i < k; i++){
			bool in;
			cin >> in;
			if (in) newboat();
			else cout << solve() << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1264
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char s[100001];
	scanf("%s", s);
	bool flag = false;
	long long count = 0;
	long long n = strlen(s);
	for (int i = 0; i < n; i++)
	{
		const bool bit = (s[i] != '0');
		if (bit != flag)
		{
			count++;
		}

		flag = !flag;
	}

	count = std::min(count, n - count);
	printf("%lld\n", count);
	return 0;
}

Measured memory_bytes: 384
// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef double D;
typedef long double LD;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define mod9 1000000009LL
#define mod7 1000000007LL
#define INF  1023456789LL
#define INF16 10000000000000000LL
#define eps 1e-9
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#ifndef ONLINE_JUDGE
#define debug(...) printf(__VA_ARGS__)
#else 
#define debug(...)
#endif
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add( LL _x , LL _y , LL _mod = mod7 ){
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline LL sub( LL _x , LL _y , LL _mod = mod7 ){
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline LL mul( LL _x , LL _y , LL _mod = mod7 ){
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
LL mypow( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 1LL;
  LL _ret = mypow( mul( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = mul( _ret , _a , _mod );
  return _ret;
}
LL mymul( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 0LL;
  LL _ret = mymul( add( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = add( _ret , _a , _mod );
  return _ret;
}
inline bool equal( D _x ,  D _y ){
  return _x > _y - eps && _x < _y + eps;
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/
void build(){

}
#define N 101010
int n , r[ N ];
char c[ N ] , cc[ N ];
void init(){
  scanf( "%d" , &n );
  scanf( "%s" , c );
}
void solve(){
  for( int a = 0 ; a < 2 ; a ++ )
    for( int b = 0 ; b < 2 ; b ++ ){
      r[ 0 ] = a; r[ 1 ] = b;
      for( int i = 2 ; i < n ; i ++ )
        if( r[ i - 1 ] == 0 ){
          if( c[ i - 1 ] == 'o' )
            r[ i ] = r[ i - 2 ];
          else
            r[ i ] = 1 - r[ i - 2 ];
        }else{
          if( c[ i - 1 ] == 'o' )
            r[ i ] = 1 - r[ i - 2 ];
          else
            r[ i ] = r[ i - 2 ];
        }
      for( int i = 0 ; i < n ; i ++ )
        if( r[ i ] == 0 ){
          if( r[ ( i + 1 ) % n ] == r[ ( i - 1 + n ) % n ] )
            cc[ i ] = 'o';
          else
            cc[ i ] = 'x';
        }else{
          if( r[ ( i + 1 ) % n ] == r[ ( i - 1 + n ) % n ] )
            cc[ i ] = 'x';
          else
            cc[ i ] = 'o';
        }
      bool same = true;
      for( int i = 0 ; i < n ; i ++ )
        if( c[ i ] != cc[ i ] ){
          same = false;
          break;
        }
      if( same ){
        for( int i = 0 ; i < n ; i ++ )
          printf( "%c" , "SW"[ r[ i ] ] );
        puts( "" );
        Bye;
      }
    }
  puts( "-1" );
}
int main(){
  build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}


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

// using ll = long long;
#define int long long

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, r, n) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))

using P = pair<int, int>;
using PP = pair<P, int>;  //<<y,x>,distance>

const int MAX = 105;
int H,W;
bool g[MAX][MAX]; // 通れるマスならtrue
bool visited[MAX][MAX];
int dp[MAX][MAX];
bool bfs(int start_y, int start_x) {
  queue<PP> q;
  PP qt = PP(P(start_y, start_x),0);
  q.push(qt);
  while(!q.empty()) {
    qt = q.front();
    int curr_x = qt.first.second;
    int curr_y = qt.first.first;
    int curr_d = qt.second;
    q.pop();
    for(int dy = 0; dy <= 1; ++dy) {
      for(int dx = 0; dx <= 1; ++dx) {
        if(!dy && !dx) continue;  // 自分の位置
        if(dy+dx == 2) continue;
        

        int next_x = curr_x + dx;
        int next_y = curr_y + dy;
        int next_d = curr_d + 1;

        // 範囲外
        if(next_x < 0 || next_x >= W) continue;
        if(next_y < 0 || next_y >= H) continue;

        if(g[next_y][next_x]) {
          dp[next_y][next_x] = min(dp[next_y][next_x], dp[curr_y][curr_x]);
        } else {
          dp[next_y][next_x] = min(dp[next_y][next_x], dp[curr_y][curr_x]+1);
        }
        q.push(PP(P(next_y,next_x),next_d));
      }
    }
  }
  return true;
}

signed main() {
  cin >> H >> W;
  REP(h, H) {
    REP(w, W) {
      char c;
      cin >> c;
      g[h][w] = (c == '.');
      dp[h][w] = MAX * MAX;
    }
  }
  if(!g[0][0]) dp[0][0] = 1;
  else dp[0][0] = 0;
  REP(h, H) {
    REP(w, W) {
      if(h == 0 && w == 0) continue;
      if(g[h][w]) {
        if(h-1 >= 0) {
          dp[h][w] = min(dp[h][w], dp[h-1][w]);
        }
        if(w-1 >= 0) {
          dp[h][w] = min(dp[h][w], dp[h][w-1]);
        }  
      } else {
        if(h-1 >= 0) {
          if(g[h-1][w]) {
            dp[h][w] = min(dp[h][w], dp[h-1][w]+1);
          } else {
            dp[h][w] = min(dp[h][w], dp[h-1][w]);
          }
        }
        if(w-1 >= 0) {
          if(g[h][w-1]) {
            dp[h][w] = min(dp[h][w], dp[h][w-1]+1);
          } else {
            dp[h][w] = min(dp[h][w], dp[h][w-1]);
          }
        }
      }
    }
  }
  cout << dp[H-1][W-1];
  cout << "\n";
  return 0;
}
/***** MAIN *****/


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

int main()
{
    int N, M, X;
    int right = 0, left = 0;
    cin >> N >> M >> X;
    for (int i = 0; i < M; i++)
    {
        int x;
        cin >> x;
        if (x < X)
        {
            left++;
        }
        else
        {
            right++;
        }
    }

    cout << min(left, right) << endl;

    return 0;
}

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

//----***型定義***----
using ll = long long;
using P = pair<int,int>;

//----***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.0)
#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 100000000000000000
#define EPS 1e-9
const vector<vector<int>> DXY={{-1,0},{1,0},{0,-1},{0,1}};

//----***パーツ***----
#define fr first
#define se second
#define pb push_back
#define re return
#define br break

//----***入出力***---
void print() { std::cout << "\n"; }
template <class T>void print(const T &x) {std::cout << x<<"\n";}
template <class T, class... Args>void print(const T &x, const Args &... args) {std::cout << x << " ";print(args...);}
#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 A,B,C,a,b,c;cin>>A>>B>>C;
  int cnt=0;
  if(A%2==1||B%2==1||C%2==1){
    print(cnt);
    re 0;;
  }
  if(A==B&&B==C){
    print(-1);
    return 0;
  }
  while(true){
    if(A%2==1||B%2==1||C%2==1){
      break;
    }
    A/=2;B/=2;C/=2;
    a=A,b=B,c=C;
    A=b+c;
    B=c+a;
    C=a+b;
    cnt++;
  }
  print(cnt);


}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int i;
    char ch;
    char inputStr[1200];
    int buket[26];
    for (i = 0; i < 26; i++) {
        buket[i] = 0;
    }

    while (fgets(inputStr, 1200, stdin) != NULL) {
        i = 0;
        while (inputStr[i] != '\n')
        {
            ch = inputStr[i];
            if ('A' <= ch && ch <= 'Z')
            {
                ch += 32;
            }
            if ('a' <= ch && ch <= 'z')
            {
                buket[ch - 97]++;
            }
            else
            {
            }
            i++;
        }
    }

    for (i = 0; i < 26; i++) {
        ch = i + 97;
        printf("%c : %d\n", ch, buket[i]);
    }

    return 0;
}


Measured memory_bytes: 2104
package main
 
import (
  "fmt"
)

func main() {
  
  var n,k,h int
  fmt.Scan(&n,&k)
  ride := 0
  
  for i := 0; i < n; i++ { 
    fmt.Scan(&h)
    if h >= k {
      ride++
    }
  }
  fmt.Println(ride)  
}


Measured memory_bytes: 5504
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e12;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

int main(){
    ll N; cin >> N;
    vl a(N, 0); REP(i, N) cin >> a[i];
    
    vl l(N+1, 1), r(N, 1);
    REP(i, N){
        if(i == 0){
            l[0] = LINF;
            l[1] = a[0]; continue;
        }
        l[i+1] = gcd(l[i], a[i]);
    }
    for(ll i = N-1; i>= 1; i--){
        if(i == N-1){
            r[N-1] = LINF;
            r[N-2] = a[N-1]; continue;
        }
        r[i-1] = gcd(r[i], a[i]);
    }
    
    ll ans = -LINF;
    REP(i, N){
        ll tmp = 0;
        if(i == 0) tmp = r[0];
        else if(i == N-1) tmp = l[N-1];
        else tmp = gcd(l[i], r[i]);
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  int N;
  int cou = 0;
  cin >> N;
  char S[N];
  for (int i = 1; i <= N; i++) {
    cin >> S[i];
  }
  if (N % 2 == 1) {
    cout << "No";
  } else {
    for (int i = 1; i <= N / 2; i++) {
      if (S[i] == S[i + N / 2]) {
        cou++;
      }
    }
    if (cou == N / 2) {
      cout << "Yes";
    } else {
      cout << "No";
    }
  }
}
// g++ lo.cpp
// ./a.exe

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;

int N;
const int MAX_N = 100010;

int a[MAX_N];

int main(){
	
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d",&a[i]);
	}
	sort(a,a+N);

	int ans=0;
	for(int i=0,j=0;i<N;i++){
		while(j<N&&a[j]-a[i]<=2)j++;
		ans=max(ans,j-i);
	}
	printf("%d\n",ans);

	return 0;
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define low lower_bound
#define upp upper_bound
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define Rep(i,n) for (int i = (int)(n); i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define rever(vec) reverse(all(vec));
#define cend cout << endl;
#define prique(T) priority_queue<T,vector<T>,greater<T>>
struct edge { int to, cost; };
typedef pair<int, int> P;
const int mod = 1e9 + 7, inf = 1e16;
 
int modpow(int x, int n) {
	if (n == 0) return 1;
	if (n & 1) return (x * modpow(x * x % mod, n / 2) % mod + mod) % mod;
	return (modpow(x * x % mod, n / 2) + mod) % mod;
}
 
int fact(int n) {
	int ans = 1;
	rep(i, n) {
		ans *= (i + 1);
		ans %= mod;
	}
	return (ans + mod) % mod;
}
 
int comb(int n, int r) {
	if (n < r) swap(n, r);
	if (n - r < r) r = n - r;
	return fact(n) * modpow(fact(n - r), mod - 2) % mod * modpow(fact(r), mod - 2) % mod;
}
 
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
 
int lcm(int a, int b) {
	return a * b / gcd(a, b);
}
 
bool pri(int p) {
	for (int i = 2; i * i <= p; i++) if (p % i == 0) return false;
	return p > 1;
}

int q,h,s,d,n;
signed main() {
	cin>>q>>h>>s>>d>>n;
	h=min(h,2*q);
	s=min(s,2*h);
	d=min(d,2*s);
	cout<<d*(n/2)+s*(n&1)<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds;
using namespace std;
#define F first
#define S second
#define pb push_back
#define powerof2 ()
using ll = long long;
const ll M = 1000000007;
const ll infi = 1000000000000000;
const ll md = 998244353;
using vl = vector<ll>;
using pll =  pair<ll,ll>;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> is;
ll power(ll x,ll y){
    if(y==0)
    return 1;
    ll res=power(x,y/2);
    res=(res*res)%M;
    if(y&(ll)1)
    res=(res*x)%M;
    return res;
}


/*int n,ma=0;
vector<vector<int>> gr;
vector<int> color;
void dfs(int c,int p)
{
    vector<int> v;
    int j;
    for(j=1;j<gr[c].size()+2;j++)
    {
        if(j==color[c]||j==color[p])
        continue;
        //cout<<j<<" ";
        v.pb(j);
    }
    //cout<<endl;
    j=0;
    for(int i=0;i<gr[c].size();i++)
    {
        if(gr[c][i]!=p)
        {
            color[gr[c][i]]=v[j];j++;
            dfs(gr[c][i],c);
        }
    }
}*/
void solve(){
    string s;
    cin>>s;
    if(s[0]!=s[2]||s[0]!=s[1])
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // int t;
    // cin>>t;
    // while(t--)
    solve();
    return 0;
}

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

int main()
{
    int n, m, ans = 0;

    cin >> n >> m;
    vector<int> x(m);
    vector<int> L;
    cin >> x[0];
    for (int i = 1; i < m; i++)
    {
        cin >> x[i];
    }
    sort(x.begin(), x.end());

    for (int i = 1; i < m; i++)
    {
        L.push_back(x[i] - x[i - 1]);
    }
    sort(L.begin(), L.end());
    if (m == 1)
    {
        ans = 0;
    }
    else
    {
        for (int i = 0; i <= m - 1 - n; i++)
        {
            // cout << L[i] << endl;
            ans += L[i];
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  
  if (N*A < B) {
	cout << N*A << endl;
  }
  else if (N*A > B){
    cout << B << endl;
  }
  else{
    cout << B << endl;
  }
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;

using namespace std;

int main() {
  string s, t, u;
  cin >> s >> t;
  int a, b;
  cin >> a >> b;
  cin >> u;
  
  if (u == s) {
    a--;
  }
  if (u == t) {
    b--;
  }

  cout << a << " " << b << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int k;
  cin>>k;
  string s;
  cin>>s;
  int n=s.length();
  if(n<=k)
    cout<<s;
  else
  {
    for(int i=0;i<k;i++)
    {
      cout<<s[i];
    }
    cout<<"...";
  }
  return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<int ,int>;
const int INF = 1e9;
const int MOD = 1e9+7;

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

    int n; cin >> n;
    vector<int> a(n, 0);
    ll ans = 1ll;
    rep(i, n) {
        int x; cin >> x;
        if (x==0) ans *= ll(3ll-a[0]);
        else ans *= ll(a[x-1]-a[x]);
        ans %= MOD;
        a[x]++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 640
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
//  cout.precision(15); cout << fixed;

int main() {
  int n; cin >> n;
  int a = n/500;
  n -= a*500;
  int b = n/5;
  cout << 1000*a + 5*b << endl;
  return 0;
}


Measured memory_bytes: 3640
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#define oo 2000000000
#define M 500005
using namespace std;
int a[M];
int main(){
	int n;
	scanf("%d",&n);
	int l=250000;
	int r=250001;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(i%2){
			a[l--]=x;
		}
		else {
			a[r++]=x;
		}
	}
	if(n%2){
		for(int i=l+1;i<r;i++)printf("%d ",a[i]);
	}
	else for(int i=r-1;i>l;i--)printf("%d ",a[i]);
//	else cout<<a<<endl;
	return 0;
}

Measured memory_bytes: 2944
import sys
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
d=dict()
for i,a in enumerate(A):
    d[i+1] = a
p=1
li = set()
li.add(1)
for i in range(k):
    #print(p,li)
    p = d[p]
    #print(p,li)
    if p in li:
        cyc =  i + 1
        q = 1
        st=0
        while q != p:
            q = d[q]
            st+=1
        cyc -=st
        k = (k-st) % cyc + st
        r = 1
        #print(k)
        for _ in range(k):
            #print(r)
            r = d[r]
        print(r)
        sys.exit()
    li.add(p)
else:
    print(p)

Measured memory_bytes: 134188
/***********************************
*******AUTHOR SHASHI KANT **********         
****GMAIL Shshiksnt140895@gmail.com*
************************************                                  
***********************************/
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
vector<int>dp(100002);
class graph
{
	map<int,list<int>>adj;
		
	public :
	       void addedge(int a, int b)
	       {
	           adj[a].push_back(b);
	       }
	int dfs(int root)
     {
 	    int res = 0;
         if(dp[root] != -1)
 	    	return dp[root];

    	for(auto x : adj[root])
    	{
          int len = 1+ dfs(x);
          res = max(res, len);
        }

        dp[root] = res;
        return dp[root];
    }
    int res()
    {
    	int mx = INT_MIN;
    
    	
    	for(auto x : adj)
    	{
            dfs(x.first);
        }
    	return  *max_element(dp.begin(), dp.end());
    }

};

int main(){

    	graph g;
      int n, m,a,b;
      cin>>n>>m;
         for(int i=0; i<m; i++)
         {
       	     cin>>a>>b;
       	     g.addedge(a,b);
         }
         int mx = INT_MIN;
        for(int i=0; i<=100001; i++)
        	dp[i] = -1;
         cout<<  g.res() << endl;
        
            return 0;
}

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

#define Debug(x) x
typedef int regular_int;
// #define int ll
typedef long long ll;

regular_int main() {
	ios_base::sync_with_stdio(false);
	cout << setprecision(12) << fixed;

	int H, W, A, B;
	cin >> H >> W >> A >> B;
	for (int i = 0; i < B; ++i) {
        cout << string (A, '1') << string (W - A, '0') << endl;
	}
	for (int i = 0; i < H - B; ++i) {
        cout << string (A, '0') << string (W - A, '1') << endl;
	}
	return 0;
}


Measured memory_bytes: 1280
M = 10**9+7

def factorial(n):
    f = 1
    for i in range(1,n+1):
        f = f*i%M
    return f

def comb(n,k):
    if n==0 or k == 0:
        return 1
    if n<k:
        return 0

    return perm(n,k)*inverse(factorial(k))%M

def mcomb(n,k):
    return comb(n+k-1,k)

def perm(n,k):
    if n==0 or k == 0:
        return 1
    if n<k:
        return 0

    p = 1
    for i in range(n-k+1,n+1):
        p = p*i%M

    return M

def inverse(a):
    return pow(a,M-2,M)
  
print(factorial(int(input())))


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

using namespace std;

const int L = 100000 + 1;

void calc(vector<vector<int>>& cache, int x, int n, const vector<int>& table, const vector<int>& Vs, const vector<int>& Ws){
	if(x <= n){
		const auto v = Vs[x - 1];
		const auto w = Ws[x - 1];
		vector<int> new_table = table;
		for(int w0 = L - 1; w0 >= 0; w0--){
			const int w1 = w0 + w;
			const int v1 = new_table[w0] + v;
			if(w1 <= L && new_table[w1] < v1){
				new_table[w1] = v1;
			}
		}
		calc(cache, x * 2, n, new_table, Vs, Ws);
		calc(cache, x * 2 + 1, n, new_table, Vs, Ws);
		cache[x - 1] = move(new_table);
	}
}

int main(void){
	int N;
	cin >> N;
	vector<int> Vs(N);
	vector<int> Ws(N);
	for(int i = 0; i < N; i ++){
		cin >> Vs[i];
		cin >> Ws[i];
	}
	
	const int n = N < 512 ? N : 512;

	vector<vector<int>> cache(n);

	calc(cache, 1, n, vector<int>(L, 0), Vs, Ws);
	
	int Q;
	cin >> Q;
	for(int q = 0; q < Q; q ++){
		int i, l;
		cin >> i;
		cin >> l;
		if(i <= n){
			cout << cache[i - 1][l] << endl;
		}else{
			int j = i;
			vector<int> target_vs(0);
			vector<int> target_ws(0);
			while(j > n){
				target_vs.push_back(Vs[j - 1]);
				target_ws.push_back(Ws[j - 1]);
				j /= 2;
			}
			const vector<int>& table = cache[j - 1];
			int topvalue = 0;
			int b_max = 1;
			for(int k = 0; k < target_ws.size(); k ++){
				b_max *= 2;
			}
			for(int b = 0; b < b_max; b ++){
				int v0 = 0;
				int w0 = 0;
				int x = 0;
				int b2 = b;
				while(b2 > 0){
					if(b2 % 2 == 1){
						v0 += target_vs[x];
						w0 += target_ws[x];
					}
					x += 1;
					b2 /= 2;
				}
				if(w0 <= l){
					int v1 = v0 + table[l - w0];
					if(v1 > topvalue){
						topvalue = v1;
					}
				}
			}
			cout << topvalue << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 206004
#include<bits/stdc++.h>
#include <math.h>
#include <algorithm>
#include <functional>
#include<iostream>
#include <string>
using namespace std;
typedef long long ll;
#define pb pushback
#define fr(i,n) for(int i=0;i<n;i++)
#define fro(i,j,n) for(int i=j;i<n;i++)
#define ifr(i,n) for(int i=n-1;i>=0;i--)

ll a[51];
ll p[51];

ll num(ll n, ll x){
  ll ans;
  if(x<=1){
    if(n==0&&x==1)ans=1;
    else ans=0;
  }
  else if(x<=a[n-1]+1)ans=num(n-1,x-1);
  else ans=p[n-1]+num(n-1,x-a[n-1]-2)+1;
  return ans;
}

int main() {
    int n;
    ll x;
	cin >> n>>x;
    
    a[0]=1;
    p[0]=1;
    fr(i,50){
      a[i+1]=a[i]*2+3;
      p[i+1]=p[i]*2+1;
    }
    
      cout << num(n,x) << endl;
}

Measured memory_bytes: 256
def is_possible(start_i):
    for i in range(lenT):
        if S[start_i + i] != '?' and S[start_i + i] != T[i]:
            return False
    return True


if __name__ == '__main__':
    S = input()
    T = input()
    lenS = len(S)
    lenT = len(T)
    tmp_i = None
    for i in range(lenS):
        if i + lenT > lenS:
            break
        else:
            if is_possible(i):
                tmp_i = i

    if tmp_i is None:
        print('UNRESTORABLE')
    else:
        print(S[:tmp_i].replace('?', 'a') + T + S[tmp_i + lenT:].replace('?', 'a'))


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

int h, w, k, M=1e9+7, d[105][9]={0,1};
int main() {
	int i, j, x, y;
	cin>>h>>w>>k;
	for(i=1; i<=h; i++) {
		for(x=0; x<1<<(w-1); x++) if(!(x & x/2)) {
			y = x<<1;
			for(j=1; j<=w; j++) {
				if(y>>(j-1) & 1) d[i][j] += d[i-1][j-1];
				else if(y>>j & 1) d[i][j] += d[i-1][j+1];
				else d[i][j] += d[i-1][j];
				d[i][j] %= M;
			}
		}
	}
	cout<<d[h][k];
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

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

    int n, k; cin>>n>>k;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin>>a[i];

    if(k == 1){
        cout << 0 << endl;
        return 0;
    }

    vector<ll> sum(n+1, 0);
    for(int i=0; i<n; i++) sum[i+1] = sum[i] + a[i];

    map<int, int> cnt;
    cnt[0] = 1;

    ll ans = 0;
    for(int r=1; r<=n; r++){
        int x = (sum[r] - r) % k;
        ans += cnt[x];
        cnt[x]++;

        // 要素の数が k 以上になった場合、左から消していく
        int l = r - k + 1;
        if(0 <= l){
            int y = (sum[l] - l) % k;
            cnt[y]--;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 12032
#include<bits/stdc++.h>
using namespace std;
priority_queue<long long> q;
int main()
{
    int n;cin>>n;
    int k;cin>>k;
    long long data;
    for (int i = 0; i < n; ++i) {
        cin>>data;
        q.push(data);
    }
    while(!q.empty()&&k--){
        q.pop();
    }
    long long t=0;
    while(!q.empty()){
        t+=q.top();
        q.pop();
    }
    cout<<t<<endl;
}

Measured memory_bytes: 2420