akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

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

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        p: usize,
        a: [i32; p],
    }
    // -(x^p - x) / (x - i) is one-hot.
    let mut ans = vec![0; p];
    for i in 0..p {
        if a[i] == 0 { continue; }
        let mut rec = vec![0; p];
        if i == 0 {
            rec[p - 1] = p - 1;
            rec[0] = 1;
        } else {
            let mut cur = p - 1;
            for j in (1..p).rev() {
                rec[j] = cur;
                cur = cur * i % p;
            }
        }
        for j in 0..p {
            ans[j] = (ans[j] + rec[j]) % p;
        }
    }
    for i in 0..p {
        puts!("{} ", ans[i]);
    }
    puts!("\n");
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
#define PB_VEC(Itr1,Itr2) (Itr1).insert((Itr1).end(),(Itr2).begin(),(Itr2).end())
#define UNIQUE(Itr) sort((Itr).begin(),(Itr).end()); (Itr).erase(unique((Itr).begin(),(Itr).end()),(Itr).end())
#define LBOUND(Itr,val) lower_bound((Itr).begin(),(Itr).end(),(val))
#define UBOUND(Itr,val) upper_bound((Itr).begin(),(Itr).end(),(val))

typedef long long ll;

int main(){
    
    string s;
    cin>>s;
    s.insert(s.begin()+4,' ');
    cout<<s<<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a[105],swp,tmp,i,j;
    while(scanf("%d",&n)==1)
    {
        for(i=0; i<n; i++)
            scanf("%d",&a[i]);
        swp=0;
        for(i=0; i<=n-1; i++)
        {
            for(j=n-1; j>=i+1; j--)
            {
                if(a[j]<a[j-1])
                {
                    swp++;
                    tmp=a[j];
                    a[j]=a[j-1];
                    a[j-1]=tmp;
                }
            }
        }
        //sort(a,a+n);

        printf("%d",a[0]);
        for(i=1; i<=n-1; i++)
        {
            printf(" %d",a[i]);
        }
        printf("\n");
        printf("%d\n",swp);

    }
    return 0;
}

Measured memory_bytes: 3212
def gcd(a, b):
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    return gcd(r, b)

N,X = map(int,input().split())
x = list(map(int,input().split()))

x.append(X)
x.sort()
diff = [x[1]-x[0]]
for i in range(N):
    diff.append(x[i+1]-x[i])

D = gcd(diff[0],diff[1])
for i in range(2,N+1):
    D = gcd(D,diff[i])
print(D)

Measured memory_bytes: 14252
import java.io.*;
import java.util.*;

public class Main {
	static final Reader in = new Reader();
	static List<Integer>[] adj;
	static boolean[] vis, act, ic;
	static List<Integer> cyc = new ArrayList<Integer>();
	static int[] a;
	
	public static void main(String[] args) {
		int n=in.nextInt();
		adj = new List[n];
		for(int i=0; i<n; ++i)
			adj[i] = new ArrayList<Integer>();
		for(int i=0; i<n; ++i)
			adj[in.nextInt()-1].add(i);
		vis = new boolean[n];
		act = new boolean[n];
		ic = new boolean[n];
		a = new int[n];
		for(int i=0; i<n; ++i)
			if(!vis[i]&&dfs1(i))
				break;
		cyc.remove(cyc.size()-1);
		Arrays.fill(a, -1);
		a[cyc.get(0)]=n;
		if(dfs2(cyc.get(0))!=a[cyc.get(1)]) {
			System.out.println("POSSIBLE");
			return;
		}
		int a1=a[cyc.get(0)];
		Arrays.fill(a, -1);
		a[cyc.get(0)]=a1;
		if(dfs2(cyc.get(0))==a1)
			System.out.println("POSSIBLE");
		else
			System.out.println("IMPOSSIBLE");
	}
	
	static boolean dfs1(int u) {
		vis[u]=true;
		act[u]=true;
		for(int v : adj[u]) {
			if(act[v]) {
				cyc.add(v);
				ic[v]=true;
				cyc.add(u);
				ic[u]=true;
				return true;
			}
			if(dfs1(v)) {
				if(ic[v]&&v!=cyc.get(0)) {
					cyc.add(u);
					ic[u]=true;
				}
				return true;
			}
		}
		act[u]=false;
		return false;
	}
	
	static int dfs2(int u) {
		List<Integer> b = new ArrayList<Integer>();
		b.add(0);
		b.add(Integer.MAX_VALUE);
		for(int v : adj[u])
			b.add(a[v]==-1?dfs2(v):a[v]);
		Collections.sort(b);
		for(int i=0; ; ++i)
			if(b.get(i+1)>b.get(i)+1)
				return a[u]=b.get(i)+1;
	}
	
	static class Reader {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		String next() {
			while(st==null||!st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(Exception e) {}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Measured memory_bytes: 144732
N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A, reverse=False)
A.sort(reverse=True)

if N == 2:
    print(abs(A[0] - A[1]))
else:
    l_in = 0
    r_in = len(A) - 1
    ans_a = (A[l_in] - A[r_in]) + (A[l_in] - A[r_in - 1])
    hashi = [A[r_in], A[r_in-1]]
    l_in += 1
    r_in -= 2
    while l_in != r_in and N != 3:
        l_max = max(abs(A[l_in] - hashi[0]), abs(A[l_in] - hashi[1]))
        r_max = max(abs(A[r_in] - hashi[0]), abs(A[r_in] - hashi[1]))
        if l_max > r_max:
            if abs(A[l_in] - hashi[0]) > abs(A[l_in] - hashi[1]):
                ans_a += abs(A[l_in] - hashi[0])
                hashi[0] = A[l_in]
            else:
                ans_a += abs(A[l_in] - hashi[1])
                hashi[1] = A[l_in]
            l_in += 1
        else:
            if abs(A[r_in] - hashi[0]) > abs(A[r_in] - hashi[1]):
                ans_a += abs(A[r_in] - hashi[0])
                hashi[0] = A[r_in]
            else:
                ans_a += abs(A[r_in] - hashi[1])
                hashi[1] = A[r_in]
            r_in -= 1
    # last
    if l_in == r_in:
        if abs(A[l_in] - hashi[0]) > abs(A[l_in] - hashi[1]):
            ans_a += abs(A[l_in] - hashi[0])
            hashi[0] = A[l_in]
        else:
            ans_a += abs(A[l_in] - hashi[1])
            hashi[1] = A[l_in]

    l_in = 0
    r_in = len(B) - 1
    ans_b = abs(B[l_in] - B[r_in]) + abs(B[l_in] - B[r_in - 1])
    hashi = [B[r_in], B[r_in - 1]]
    l_in += 1
    r_in -= 2
    while l_in != r_in and N != 3:
        l_max = max(abs(B[l_in] - hashi[0]), abs(B[l_in] - hashi[1]))
        r_max = max(abs(B[r_in] - hashi[0]), abs(B[r_in] - hashi[1]))
        if l_max > r_max:
            if abs(B[l_in] - hashi[0]) > abs(B[l_in] - hashi[1]):
                ans_b += abs(B[l_in] - hashi[0])
                hashi[0] = B[l_in]
            else:
                ans_b += abs(B[l_in] - hashi[1])
                hashi[1] = B[l_in]
            l_in += 1
        else:
            if abs(B[r_in] - hashi[0]) > abs(B[r_in] - hashi[1]):
                ans_b += abs(B[r_in] - hashi[0])
                hashi[0] = B[r_in]
            else:
                ans_b += abs(B[r_in] - hashi[1])
                hashi[1] = B[r_in]
            r_in -= 1
    # last
    if l_in == r_in:
        if abs(B[l_in] - hashi[0]) > abs(B[l_in] - hashi[1]):
            ans_b += abs(B[l_in] - hashi[0])
            hashi[0] = B[l_in]
        else:
            ans_b += abs(B[l_in] - hashi[1])
            hashi[1] = B[l_in]

    print(max(ans_a, ans_b))


Measured memory_bytes: 8328
#include <stdio.h>
int main()
{
  int a,b,i;
  scanf("%d %d",&a,&b);
  i = 0;
  if (a >= b)
  {
    while (i < a)
    {
      printf("%d",b);
      i++;
    }
    return (0);
  }
  while (i < b)
  {
    printf("%d",a);
    i++;
  }
}
  

Measured memory_bytes: 128
#include <bits/stdc++.h>  
using namespace std;  
typedef long long ll; 
typedef long double ld; 
const int INF = 0x3f3f3f3f;  
const int N = 200000 + 5;
int a[N],b[N];
 
int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);
	int n,x,y;
	cin >> n >> x >> y;
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            int z = min(j - i, abs(i - x) + 1 + abs(y - j));
            a[z]++;
        }
    }
    for(int i = 1; i < n; i++)
		cout << a[i] << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public  static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();

        boolean check = false;

        for (int n = a;n <= b ; n++){
            if(n % k == 0){
                check = true;
                break;
            }
        }

        if(check){
            System.out.println("OK");
        }else{
            System.out.println("NG");
        }
    }
}


Measured memory_bytes: 35548
// D - Even Relation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const int MOD = 1e9 + 7;

struct Edge {
	int destination;
	int length;
};

struct Node {
	vector<Edge> edges;
	int parent = -1;
	int color = -1;
};

void set_parent(vector<Node>& nodes, int this_node, int parent) {
	nodes[this_node].parent = parent;

	for (Edge edge : nodes[this_node].edges) {
		if (edge.destination == parent) continue;

		set_parent(nodes, edge.destination, this_node);
	}
}

void set_color(vector<Node>& nodes, int this_node, int parent, int color) {
	//cout << " set color:" << this_node << endl; // **** debug ****
	nodes[this_node].color = color;

	for (Edge edge : nodes[this_node].edges) {
		if (edge.destination == parent) continue;

		if (nodes[this_node].color == 0) {
			if (edge.length % 2 == 0) {
				set_color(nodes, edge.destination, this_node, 0);
			} else {
				set_color(nodes, edge.destination, this_node, 1);
			}
		} else {
			if (edge.length % 2 == 0) {
				set_color(nodes, edge.destination, this_node, 1);
			} else {
				set_color(nodes, edge.destination, this_node, 0);
			}
		}
	}
}

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

	vector<Node> nodes(N);

	for (int i=0; i<N-1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--;
		v--;

		Edge edge;
		edge.length = w;

		edge.destination = v;
		nodes[u].edges.push_back(edge);

		edge.destination = u;
		nodes[v].edges.push_back(edge);
	}

	set_parent(nodes, 0, -1);
	set_color(nodes, 0, -1, 0);

	for (int i=0; i<N; i++) {
		cout << nodes[i].color << endl;
	}

	return 0;
}

Measured memory_bytes: 9344
#include <stdio.h>

int main()
{
	int H,W;
	int i,j;
	
	while(1){
	
		scanf("%d %d",&H,&W);
		if(H == 0 && W == 0) break;
		
		for( i = 1;i <= H; i++){
			for( j = 1; j <= W; j++){
				printf("#");
			}
		printf("\n");
	}
	printf("\n");
		}
		return 0;
}
	

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

int main()
{
  int n;
  while( cin >> n, n ) {
    int target;
    int cnt = 0;
    int l = 0, r = n-1, m;
    int data[100001];
   
    for(int i=0; i<n; i++) cin >> data[i];
    cin >> target;
    
   

    while( l <= r ) {
      m = (l+r) / 2;
      cnt++;
      if( data[m] == target ) break;
      if( target > data[m] ) l = m+1;
      else r = m-1;
    }

    cout << cnt << endl;
  }

}

Measured memory_bytes: 1168
#include<iostream>
#include<string>
#include<cstdlib>
#include<algorithm>
#include<vector>

using namespace std;

int main(){
	int n,m;
	cin >> n >> m;
	int a[m], b[m], c[n] = {0};
	for(int i = 0; i < m; i++){
		cin >> a[i] >> b[i];
	}
	
	for(int i = 0; i < m; i++){
		for(int j = 1; j < n+1; j++){
			if(a[i] == j){
				c[j-1]++;
				break;
			}
		}
		for(int j = 1; j < n+1; j++){
			if(b[i] == j){
				c[j-1]++;
				break;
			}
		}
	}
	
	for(int i = 0; i < n; i++){
		cout << c[i] << endl;
	}
	
 	return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter;
import java.util.*;

public class Main {
    void run() {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = sc.nextInt();
        long d = sc.nextLong();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            if (x * x + y * y <= d * d) {
                ans++;
            }
        }
        System.out.println(ans);

        // out.println("Hello World");
        out.flush();
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


Measured memory_bytes: 61236
#include<stdio.h>
#include<string.h>
#define NUM 3

int main(){
   char s[NUM];
   int i;
   for(i=0;i<NUM;i++){
      scanf("%c",&s[i]);
   }
   if(s[0]!=s[1]||s[1]!=s[2]){
      printf("Yes");
   }else{
      printf("No");
   }
   return 0;
}
   

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

using namespace std;

int main(void)
{
    int N;
    cin >> N;
    string C;
    cin >> C;

    int w = 0;
    int r = N - 1;
    int count = 0;
    while(true)
    {
        optional<int> wp;
        optional<int> rp;
        for (; w < N; ++w)
        {
            if (C[w] == 'W')
            {
                wp = w;
                break;
            }
        }
        for (; r > w; --r)
        {
            if (C[r] == 'R')
            {
                rp = r;
                break;
            }
        }
        if(wp.has_value() && rp.has_value())
        {
            ++count;
        }
        else
        {
            break;
        }
        ++w;
        --r;
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3688
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, e) for (int i = s; i < e; ++i)
#define sort_(a) stable_sort(a.begin(), a.end())
#define rsort(a) stable_sort(a.rbegin(), a.rend())
#define sum(a) accumulate(a.begin(), a.end(), 0LL)
#define join(a, d) accumulate(a.begin() + 1, a.end(), a[0], [](string s, string t) {return s + d + t;})
#define all(a) a.begin(), a.end()
#define __lcm(a, b) std::__detail::__lcm(a, b)
typedef long long ll;
const long mod = 1e9 + 7;

int main(void) {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
#endif

  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int N;
  cin >> N;
  vector<int> A(N + 1, 0);
  rep(i, 1, N + 1) {
    cin >> A[i];
  }
  pair<int, int> p;
  map<pair<int, int>, long> cnt{};
  rep(i, 1, N + 1) {
    p.first = min(i, A[i]);
    p.second = max(i, A[i]);
    cnt[p] += 1;
  }
  long ans = 0;
  for (auto n : cnt) {
    if (n.second == 2)
      ans += 1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,b,c;
  cin>>a>>b>>c;
  if((a==5&&b==5&&c==7)||(a==5 and b==7 and c==5)||(a==7 and b==5 and c==5))
  {
    cout<<"YES"<<endl;
  }
  else
  {
    cout<<"NO"<<endl;
  }
}

Measured memory_bytes: 384
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 100
using namespace std;
char Map[MAXN+5][MAXN+5];
int n,m,ex,ey;
int sumr[MAXN+5][MAXN+5],sumc[MAXN+5][MAXN+5];
int dp[MAXN+5][MAXN+5][MAXN+5];
void Init()
{
	memset(dp,-1,sizeof(dp));
}
int main()
{
	Init();
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",Map[i]+1);
		for(int j=1;j<=m;j++)
		{
			sumr[i][j]=sumr[i][j-1];
			sumc[i][j]=sumc[i-1][j];
			if(Map[i][j]=='E')
				ex=i,ey=j;
			else if(Map[i][j]=='o')
			{
				sumr[i][j]++;
				sumc[i][j]++;
			}
		}
	}
	int L,R,U,D,ans=0;
	L=ey-1;
	R=m-ey;
	U=ex-1;
	D=n-ex;
	dp[0][0][0]=0;
	for(int l=0;l<=L;l++)
		for(int r=0;r<=R;r++)
			for(int u=0;u<=U;u++)
				for(int d=0;d<=D;d++)
				{
					if(dp[r][u][d]==-1)
						continue;
					ans=max(dp[r][u][d],ans);
					int up=max(ex-u,d+1);
					int down=min(ex+d,n-u);
					int left=max(ey-l,r+1);
					int right=min(ey+r,m-l);
					if(up>down||left>right)
						continue;
					int add;
					if(u<U-d)
					{
						add=sumr[ex-u-1][right]-sumr[ex-u-1][left-1];
						dp[r][u+1][d]=max(dp[r][u+1][d],dp[r][u][d]+add);
					}
					if(d<D-u)
					{
						add=sumr[ex+d+1][right]-sumr[ex+d+1][left-1];
						dp[r][u][d+1]=max(dp[r][u][d+1],dp[r][u][d]+add);
					}
					if(r<R-l)
					{
						add=sumc[down][ey+r+1]-sumc[up-1][ey+r+1];
						dp[r+1][u][d]=max(dp[r+1][u][d],dp[r][u][d]+add);
					}
					if(l<L-r)
					{
						add=sumc[down][ey-l-1]-sumc[up-1][ey-l-1];
						dp[r][u][d]=max(dp[r][u][d],dp[r][u][d]+add);
					}
				}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 4736
N,X = map(int,input().split())
L_input = list(map(int,input().split()))
L = [0]
for i in range(N):
    L.append(L[-1] + L_input[i])
cnt = 0
for l in L:
    if l <= X:
        cnt += 1
    else:
        break
print(cnt)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric>
#include <set>
#include <cstdlib>

using namespace std;
typedef long long llint;
typedef long double ld;
#define inf 1e18

llint l;
void solve(){
	cin >> l;
	ld ans;
	ld a=pow(l,3);
	ans=a/27;
	printf("%06Lf\n",ans);
}

int main(int argc, char *argv[]) {
  solve();
  return 0;
}


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

int main()
{   
    long long n,m,a,b;
    cin>>n>>m;
    string s,t;
    cin>>s>>t;
    long long tmp,r,x,ans,i=0,j=0;
    a=n;
    b=m;
    x=n*m;
    if(n<m){
        tmp=n;
        n=m;
        m=tmp;
    }
    r=n%m;
    while(r!=0){
        n=m;
        m=r;
        r=n%m;
    }
    ans=x/m;
    while(1){
        if(s[i]!=t[j]){
            cout<<-1<<endl;
            return 0;
        }
        i+=ans/b;
        j+=ans/a;
        if((i>(a-1))||(j>(b-1))){
            cout<<ans<<endl;
            return 0;
        }
    }
    
}

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

const int INF = 1e9;
vector<int> arr;
vector<int> dp;
int N;

int solve(int x) {
    if (x >= N - 1) return 0;
    if (dp[x] != -1) return dp[x];

    int j1 = abs(arr[x] - arr[x+1]) + solve(x + 1);

    int j2 = INF;
    if (x < N - 2) j2 = abs(arr[x] - arr[x+2]) + solve(x + 2);
    return dp[x] = min(j1, j2);
}

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

    cin >> N;
    arr = vector<int>(N);
    dp = vector<int>(N, -1);
    for (auto& x : arr) cin >> x;

    cout << solve(0) << "\n";
}



Measured memory_bytes: 5760
#[doc = " https://github.com/hatoo/competitive-rust-snippets"]
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};
#[allow(unused_imports)]
use std::iter::FromIterator;
mod util {
    use std::fmt::Debug;
    use std::io::{stdin, stdout, BufWriter, StdoutLock};
    use std::str::FromStr;
    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }
    #[allow(dead_code)]
    pub fn chars() -> Vec<char> {
        line().chars().collect()
    }
    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
    #[allow(dead_code)]
    pub fn with_bufwriter<F: FnOnce(BufWriter<StdoutLock>) -> ()>(f: F) {
        let out = stdout();
        let writer = BufWriter::new(out.lock());
        f(writer)
    }
}
#[allow(unused_macros)]
macro_rules ! get { ( [ $ t : ty ] ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . split_whitespace ( ) . map ( | t | t . parse ::<$ t > ( ) . unwrap ( ) ) . collect ::< Vec < _ >> ( ) } } ; ( [ $ t : ty ] ; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( [ $ t ] ) ) . collect ::< Vec < _ >> ( ) } ; ( $ t : ty ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . trim ( ) . parse ::<$ t > ( ) . unwrap ( ) } } ; ( $ ( $ t : ty ) ,* ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; let mut iter = line . split_whitespace ( ) ; ( $ ( iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . unwrap ( ) , ) * ) } } ; ( $ t : ty ; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ ( $ t : ty ) ,*; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ ( $ t ) ,* ) ) . collect ::< Vec < _ >> ( ) } ; }
#[allow(unused_macros)]
macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }
const BIG_STACK_SIZE: bool = true;
#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}
fn solve() {
    let n = get!(usize);
    let ps = get!([usize]);

    let ans = (1..n - 1)
        .filter(|&i| {
            let k = if ps[i - 1] < ps[i] { 1 } else { 0 } + if ps[i + 1] < ps[i] { 1 } else { 0 };
            k == 1
        })
        .count();

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


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

struct RollingHash {
  typedef tuple<ll,ll,ll> HashType;

  const ll mod1 = 999999893;
  const ll mod2 = 999999929;
  const ll mod3 = 999999937;
  const ll b1 = 3422539;
  const ll b2 = 1245103;
  const ll b3 = 22961;
  vector<ll> h1, h2, h3;
  vector<ll> pow1, pow2, pow3;

  RollingHash(const string &s) {
    const int n = s.size();
    h1.assign(n+1, 0);
    h2.assign(n+1, 0);
    h3.assign(n+1, 0);
    pow1.assign(n+1, 1);
    pow2.assign(n+1, 1);
    pow3.assign(n+1, 1);
    REP(i, n) {
      h1[i+1] = (h1[i] * b1 + s[i]) % mod1;
      h2[i+1] = (h2[i] * b2 + s[i]) % mod2;
      h3[i+1] = (h3[i] * b3 + s[i]) % mod3;
      pow1[i+1] = pow1[i] * b1 % mod1;
      pow2[i+1] = pow2[i] * b2 % mod2;
      pow3[i+1] = pow3[i] * b3 % mod3;
    }
  }

  HashType get(int l, int r) {
    ll v1 = ((h1[r] - h1[l] * pow1[r-l]) % mod1 + mod1) % mod1;
    ll v2 = ((h2[r] - h2[l] * pow2[r-l]) % mod2 + mod2) % mod2;
    ll v3 = ((h3[r] - h3[l] * pow3[r-l]) % mod3 + mod3) % mod3;
    return HashType {v1, v2, v3};
  }
};

int main2() {
  int N, M; cin >> N >> M;
  string s; cin >> s;
  RollingHash hash(s);
  int l = 0;
  int r = 1;
  set<RollingHash::HashType> st;
  REP(_, M) {
    string cmd; cin >> cmd;
    if (cmd == "R++") { r++; }
    if (cmd == "R--") { r--; }
    if (cmd == "L++") { l++; }
    if (cmd == "L--") { l--; }
    auto key = hash.get(l, r);
    st.insert(key);
  }
  cout << st.size() << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}



Measured memory_bytes: 35992
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

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

  int ans=0;
  for(int i=1;i<=N/2;i++){
    if(i!=N-i) ans++;
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class Cell{
    Cell prev;
    Cell next;
    int value;

    Cell(){ // head生成用のコンストラクタ
        this.prev = this;
        this.next = this;
    }

    Cell(int val){
        value = val;
        this.prev = null;
        this.next = null;
    }
}

class Main{
    static Cell head = new Cell();

    static void insert(int value){
        Cell newone = new Cell(value);
        newone.next = head.next;
        newone.prev = head;
        newone.next.prev = newone;
        head.next = newone;
    }

    static void delete(int value){
        Cell run = head.next;
        while(run != head){
            if(run.value == value){
                run.prev.next = run.next;
                run.next.prev = run.prev;
                run.prev = null;
                run.next = null;
                return;
            }
            run = run.next;
        }
    }

    static void deleteFirst(){
        delete(head.next.value);
    }

    static void deleteLast(){
        Cell del = head.prev;
        head.prev = del.prev;
        del.prev.next = head;

        del.prev = null;
        del.next = null;
    }

    static void show(){
        Cell run = head.next;
        if(run == head){
            System.out.println();
            return;
        }
        StringBuilder sb = new StringBuilder();
        boolean format = true;
        while(run != head){
            if(format){
                sb.append(run.value);
                format = false;
            }else{
                sb.append(" " + run.value);
            }
            run = run.next;
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        for(int i = 0; i < n; i++){
            String[] input = br.readLine().split(" ");

            switch(input[0]){
                case "insert":
                    insert(Integer.parseInt(input[1]));
                    break;
                case "delete":
                    delete(Integer.parseInt(input[1]));
                    break;
                case "deleteFirst":
                    deleteFirst();
                    break;
                case "deleteLast":
                    deleteLast();
                    break;
            }
        }
        show();
    }
}


Measured memory_bytes: 186348
from collections import defaultdict, deque

N, M = map(int, input().split())
path = defaultdict(list)

for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    path[A].append(B)
    path[B].append(A)

prev = [0] * N
dist = [0] * N
q = deque([0])

while (len(q) > 0):
    a = q.popleft()
    for b in path[a]:
        if dist[b] != 0:continue
        q.append(b)
        prev[b] = a
        dist[b] = dist[a] + 1

print('Yes')

for a in prev[1:]:
    a += 1
    print(a)

Measured memory_bytes: 39904
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0; i<(n); i++)
const long long INF = numeric_limits<long long>::max();
int main(){
    int n,ans=0;
    cin >> n;
    map<string,int> S;
    rep(i,n){
        string s;
        cin>>s;
        S[s]++;
    }
    ans=S.size();
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 19208
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
using namespace std;

signed main() {
  int K, A, B; cin >> K >> A >> B;
  if(B-A <= 2) {
    std::cout << K+1 << std::endl;
  } else {
    int ans = max(K+1, (A+(K-(A-1))/2*(B-A))+(K-(A-1))%2);
    std::cout << ans << std::endl;
  }
  return 0;
}


Measured memory_bytes: 256
#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[i];}
	long long ans=0;
	for(i=1;i<n;i++){
		long long x=max((long long)0,a[i-1]-a[i]);
		ans += x;
		a[i] += x;
	}
	cout<< ans<<"\n";
	return 0;
}

Measured memory_bytes: 4820
#include<iostream>

using namespace std;
int main()
{
    char s[2][3];
    char t[2][3];
    for(int i=0;i<2;i++){
        for(int j=0;j<3;j++){
            cin>>s[i][j];
        }
    }
    for(int i=0;i<2;i++){
        for(int j=0;j<3;j++){
            if(s[1-i][2-j]!=s[i][j]){
                cout<<"NO"<<endl;
                return 0;
            }
        }
    }
    cout<<"YES"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

long process(const vector<long> &A, int st, int ed, int mul, vector<vector<long>> &memo) {
	if (st == ed-1) {
		return max(A[st]*mul+A[ed], -A[st]*mul-A[ed]);
	}
	if (memo[st][mul+1] != -1)
		return memo[st][mul+1];
	long cand1 = A[st]*mul+ process(A,st+1,ed,1,memo);
	long cand2 = -A[st]*mul + process(A,st+1,ed,-1,memo);
	memo[st][mul+1] = max(cand1,cand2);
	return memo[st][mul+1];
}

int main() {
	int total_n;
	int i;
	
	cin >> total_n;
	vector<long> A(total_n);
	vector<vector<long>> memo(total_n, vector<long>(3,-1));
	for (i=0; i<total_n; i++) {
		cin >> A[i];
	}
	
	cout << process(A,0,A.size()-1,1,memo) << endl;
	return 0;
}


Measured memory_bytes: 15872
#ダイクストラ法
#O(ElogV)
import heapq
def dijkstra_heap(s,edge):
  #始点sから各頂点への最短距離
  d = [float("inf")] * (n+1)
  used = [False] * (n+1)
  d[s] = 0
  used[s] = True
  edgelist = []
  #edgelist : (sからの暫定(未確定)最短距離,頂点)のリスト
  #edge[s] : sから出る枝の(重み,終点)の配列
  for w,v in edge[s]:
    heapq.heappush(edgelist,w*10**6+v) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    minedge = heapq.heappop(edgelist)
    #minedge : (sからの(確定)最短距離,頂点)
    v = minedge%10**6
    if used[v]:
      continue
    d[v] = minedge//10**6
    used[v] = True
    for w,u in edge[v]:
      if not used[u]:
        heapq.heappush(edgelist,(d[v]+w)*10**6+u)
  return d

################################
n,m,s,t = map(int,input().split()) #n:頂点数　w:辺の数

edge_yen = [[] for _ in range(n+1)]
edge_snuke = [[] for _ in range(n+1)]

for i in range(m):
  u,v,a,b = map(int, input().split())
  edge_yen[u].append((a,v))
  edge_yen[v].append((a,u))
  edge_snuke[u].append((b,v))
  edge_snuke[v].append((b,u))

d_yen = dijkstra_heap(s,edge_yen)
d_snuke = dijkstra_heap(t,edge_snuke)
ans = [0]*(n)
m = float("inf")
for i in range(n,0,-1):
  m = min(d_yen[i]+d_snuke[i],m)
  ans[i-1]=10**15-m
print(*ans,sep='\n')

Measured memory_bytes: 81512
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

template<typename flow_type> struct Dinic{

    struct edge{
        int to, rev;
        flow_type cap;
        edge(int t, int r, flow_type c): to(t), rev(r), cap(c){}
    };

    vector<vector<edge>> G;
    vector<int> level, nxt;
    flow_type flow_inf;

    Dinic(int n): G(n), level(n), nxt(n), flow_inf(numeric_limits<flow_type>::max()){}

    void add_edge(int from, int to, flow_type cap){
        G[from].emplace_back(to, G[to].size(), cap);
        G[to].emplace_back(from, G[from].size()-1, 0);
    }

    bool bfs(int s, int t){
        fill(level.begin(), level.end(), -1);
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while(!que.empty()){
            int v = que.front();
            que.pop();
            for(auto &e: G[v])if(e.cap > 0 && level[e.to] < 0){
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
        return level[t] != -1;
    }

    flow_type dfs(int v, int t, flow_type bottleneck){
        flow_type ret = 0;
        if(v == t) return bottleneck;
        for(int &i=nxt[v]; i<G[v].size(); ++i){
            auto &e = G[v][i];
            if(e.cap == 0 || level[e.to] != level[v] + 1) continue;
            flow_type tmp = dfs(e.to, t, min(bottleneck, e.cap));
            e.cap -= tmp;
            G[e.to][e.rev].cap += tmp;
            ret += tmp;
            bottleneck -= tmp;
            if(bottleneck == 0) break;
        }
        return ret;
    }

    flow_type max_flow(int s, int t){
        flow_type ret = 0;
        while(bfs(s, t)){
            fill(nxt.begin(), nxt.end(), 0);
            ret += dfs(s, t, flow_inf);
        }
        return ret;
    }
};

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    Dinic<lint> dinic(n);
    rep(i, m){
        int u, v; lint c;
        scanf("%d%d%lld", &u, &v, &c);
        dinic.add_edge(u, v, c);
    }
    printf("%lld\n", dinic.max_flow(0, n-1));
}


Measured memory_bytes: 3276
let n = stdin.ReadLine() |> int
let x = stdin.ReadLine().Split() |> Array.map int
let max = Array.max x
let min = Array.min x
let rec f i v p = if i=n then v else f (i+1) (v+(x.[i]-p)*(x.[i]-p)) p
[min..max] |> List.map (f 0 0) |> List.min |> stdout.WriteLine

Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
int main(){
    long n,m;
    cin>>n>>m;
    long ans=0;
    if(n>=m/2){
        ans+=m/2;
        cout<<ans<<endl;
        return 0;
    }
    else ans+=n;
    m-=2*n;
    ans+=m/4;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

point = {'s':r, 'p':s, 'r':p}

score = 0
flag = [('0', 1)] * k
for i in range(n):
    if flag[i % k][0] != t[i]:
        score += point[t[i]]
        flag[i % k] = (t[i], -1)
    elif flag[i % k][0] == t[i] and flag[i % k][1] == 1:
        score += point[t[i]]
        flag[i % k] = (t[i], -1)
    else:
        flag[i % k] = (t[i], 1)

print(score)

Measured memory_bytes: 9460
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define maxn 100010
using namespace std;
int n;
int a[maxn];
map<int,int>ma1,ma2;
int ans;
int book[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)  cin>>a[i];
    int mx1=0,mx2=0,pos;
    for(int i=1;i<=n;i+=2)  ma1[a[i]]++;
    for(int i=1;i<=n;i+=2)   
    {
        if(book[a[i]]==1) continue;
        book[a[i]]=1;
        if(ma1[a[i]]>=mx1)
        {
            mx2=mx1;
            mx1=ma1[a[i]];
            pos=a[i];
        }
        else if(ma1[a[i]]>=mx2)
        {
            mx2=ma1[a[i]];
        }
    }
    int tmx1=0,tmx2=0,posx;
    for(int i=2;i<=n;i+=2)  ma2[a[i]]++;
    memset(book,0,sizeof(book));
    for(int i=2;i<=n;i+=2)
    {
        if(book[a[i]]==1)  continue;
        book[a[i]]=1;
        if(ma2[a[i]]>=tmx1)
        {
            tmx2=tmx1;
            tmx1=ma2[a[i]];
            posx=a[i];
        }
        else if(ma2[a[i]]>=tmx2)
        {
            tmx2=ma2[a[i]];
        }          
    }
    if(pos!=posx){
        cout<<n-mx1-tmx1<<endl;
        return 0;
    }
    int ans=0;
    ans=max(ans,mx1+tmx2);
    ans=max(ans,mx2+tmx1);
    cout<<n-ans<<endl;
    return 0;
}

Measured memory_bytes: 5760
// Problem : A - HonestOrDishonest
// Contest : AtCoder - AtCoder Beginner Contest 056
// URL : https://atcoder.jp/contests/abc056/tasks/abc056_a
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

double pi=acos(-1.0);
const int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}

void solve()
{
char c1,c2;
cin>>c1>>c2;
if(c1=='H')
{
	if(c2=='H')
	cout<<"H";
	else
	cout<<"D";
}
else
{
	if(c2=='D')
	cout<<"H";
	else
	cout<<"D";
}
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef long long int ll;

ll a, b, c, d, e;
ll N, H, K, W;

void input()
{
    cin >> a >> b >> c;
}
void solve()
{
    if (a * a + b * b == c * c)
    {
        cout << a * b / 2 << endl;
    }
    else if (a * a + c * c == b * b)
    {
        cout << a * c / 2 << endl;
    }
    else
    {
        cout << c * b / 2 << endl;
    }
}

int main()
{
    input();
    solve();
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int K,N,i,j;
	double a,sum;
	scanf("%d",&N);
	scanf("%d",&K);
	sum=0;
	for(i=1;i<=N;i++){
		a=(double)1/N;
		for(j=i;j<K;){
			j=j*2;
			a=a/2;
		}
	sum=sum+a;
	}
	printf("%.10lf",sum);
	return 0;
}


Measured memory_bytes: 1736
#include<bits/stdc++.h>
#define int long long
using namespace std;
int q;
int32_t main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> q;
    while (q--) {
	int a, b;
	cin >> a >> b;
	if (a < b)
	    swap(a, b);
	if (a == b || a == b + 1)
	    cout << 2 * b - 2 << '\n';
	else {
	    int val = a * b, c = sqrt(val);
	    if (c * c == val)
		c--;
	    if (c * (c + 1) >= val)
		cout << 2 * c - 2 << '\n';
	    else
		cout << 2 * c - 1 << '\n';
	}
    }
}


Measured memory_bytes: 256
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;
const ll MOD = 1000000007;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

ll n;
vector<ll> d;

bool solve(ll k) {
	ll abc = 0, arc = 0;
	for (auto v : d) {
		if (v >= k) {
			arc++;
		} else {
			abc++;
		}
	}

	return abc == arc;
}

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

	cin >> n;

	d.resize(n);
	for (auto &v : d) {
		cin >> v;
	}
	sort(begin(d), end(d));
	ll ans = d[n / 2] - d[n / 2 - 1];
	cout << ans << endl;
	return 0;
}


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

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
	
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;

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

    int n, q, l ,r;
    cin>>n>>q;

    string s;
    cin>>s;
    int occ[n];
    occ[0] = 0;

    FOR(i, 1, n){
        occ[i] = occ[i-1];
        if (s[i] == 'C' && s[i-1]=='A'){
            occ[i]++;
        }
    }

    while (q--){
        cin>>l>>r;
        l--; r--;
        cout<<occ[r]-occ[l]<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 1488
#include<iostream>
using namespace std;
int main(){
  int n,i,j,ans=0;
  cin >> n;
  for(i=1;i<=n;i=i+2){
    int count=0;
    for(j=1;j<=i;j++){
      if(i%j==0){
        count++;
      }
    }
    if(count==8){
      ans++;
    }
  }
  cout << ans << endl;
}


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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define pll pair<ll, ll>
#define vll vector<ll>

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

ll N, A, B, C;
vector<ll> v_list;

ll dfs(ll i, ll a, ll b, ll c) {
  if (i == N) {
    if (a == 0 || b == 0 || c == 0) {
      return INF;
    }

    return abs(A - a) + abs(B - b) + abs(C - c) - 30;
  }

  ll v = v_list[i];

  ll r0 = dfs(i + 1, a, b, c);
  ll r1 = dfs(i + 1, a + v, b, c) + 10;
  ll r2 = dfs(i + 1, a, b + v, c) + 10;
  ll r3 = dfs(i + 1, a, b, c + v) + 10;

  return min(min(min(r0, r1), r2), r3);
}

int main() {
  scanf("%lld %lld %lld %lld", &N, &A, &B, &C);

  v_list = vll(N);

  for (ll i = 0; i < N; i++) {
    ll v;
    scanf("%lld", &v);
    v_list[i] = v;
  }

  cout << dfs(0, 0, 0, 0) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("unroll-loops") 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define int long long
#define fr(i,a,b) for(int i = a ; i <= b ; ++i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define fst first
#define snd second
using namespace __gnu_pbds;
using ordered_set =
 tree<int, null_type,less<int>,
 rb_tree_tag,tree_order_statistics_node_update>;
//find_by_order(k):returns iterator to kth element starting from 0
//order_of_key(k):returns count of elements strictly smaller than k
typedef long long ll;typedef pair<int, int> pii;
typedef vector<int> vi;typedef long double ld;
template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T>>; 
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
template<typename T> 
void remdup(vector<T>& v) {
	sort(all(v)); v.erase(unique(all(v)), v.end());
}
template<typename T> void re(vector<T> &v) {trav(i,v) cin >> i;}
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
#ifdef np
#include "C:\Users\navodit\Desktop\mycodes\pr.h"
#else
#define trace(...)
#endif

#define MOD 1000000007  





void solve(){
	int n ; 
	string s ;cin >> n >> s ;
	string mat = "ABC";
	int cnt =0 ;
	rep(i,0,n){
		if(s.substr(i,3) == mat) cnt++;
	}
	cout << cnt << endl;
}

signed main() {
	unsyncIO();
	int tt =1 ;
	// cin >> tt;
	rep(i,0,tt) solve();













#ifdef np
	cout <<endl<<endl<< "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}


Measured memory_bytes: 3664
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Node
    {
        internal int key;
        internal Node left, right;

        public Node(int key)
        {
            this.key = key;
        }
    }

    class Program
    {
        static StringBuilder sb;
        static Node root;

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            for(int i = 0; i < n; i++)
            {
                string input = Console.ReadLine();

                if (input[0] == 'i')
                {
                    string[] temp = input.Split(' ');
                    Insert(int.Parse(temp[1]));
                }
                else
                {
                    sb = new StringBuilder();
                    Inorder(root);
                    sb.AppendLine();
                    Preorder(root);
                    Console.WriteLine(sb);
                }
            }
        }
        
        static void Insert(int k)
        {
            Node x = root;
            Node y = null;
            Node z = new Node(k);

            while (x != null)
            {
                y = x;
                x = z.key < x.key ? x.left : x.right;
            }

            if (y != null)
            {
                if (z.key < y.key) y.left = z;
                else y.right = z;
            }
            else root = z;
        }

        static void Inorder(Node u)
        {
            if (u == null) return;

            Inorder(u.left);
            sb.Append(" " + u.key);
            Inorder(u.right);
        }

        static void Preorder(Node u)
        {
            if (u == null) return;

            sb.Append(" " + u.key);
            Preorder(u.left);
            Preorder(u.right);
        }
    }
}

Measured memory_bytes: 84060