akhauriyash/Code-Regression huggingface dataset:
// 未回答: TLE
// 標準入力から一行を読み取り、指定の型に変換する
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
    
// 標準入力から一行を読み取り、空白文字で分割し、各要素を指定の型に変換する関数
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn lower_bound(v: &Vec<i32>, start: usize, key: i32) -> i32 {
    let mut result_index: i32 = v.len() as i32;

    for i in start..v.len()
    {
        if v[i] >= key
        {
            result_index = i as i32;
            break;
        }
    }

    result_index
}
    
fn main() {
    let number: i32 = read();
    let mut sticks: Vec<i32> = read_vec();
    
    let mut count_of_triangles: i32 = 0;

    // ソート
    sticks.sort();
    
    //a < b < cのとき、a + b > c
    for b in 0..(number - 1) as usize 
    {
        for a in 0..b as usize 
        {
            let ab: i32 = sticks[a] + sticks[b];
            let end_index: i32 = lower_bound(&sticks, b, ab);
            let begin_index: i32 = (b + 1) as i32;
            count_of_triangles += end_index - begin_index;
            //println!("a_index:{} b_index:{} ab_value:{} end_index:{} begin_index:{} count:{}", a, b, ab, end_index, begin_index, count_of_triangles);
        }
    }
    
    println!("{}", count_of_triangles);
}


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

char str[11];
int main()
{   int i;
    cin>>str;
    if(str[0]=='Y'&&str[1]=='A'&&str[2]=='K'&&str[3]=='I') cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}









Measured memory_bytes: 256
a,b,c  = map(int,input().split())

if a == b and b == c:
  print('No')
elif a == b and b != c:
    print('Yes')
elif a != b and b == c:
    print('Yes')
elif a == c and b != c:
    print('Yes')
elif a != b and b != c:
    print('No')


Measured memory_bytes: 38384
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

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

int main(){
   string a,b;
   cin>>a>>b;
   if(a[0]==b[2]&&a[1]==b[1]&&a[2]==b[0]){
       cout<<"YES"<<endl;
   }
   else{
       cout<<"NO"<<endl;
   }
  return 0;
}

Measured memory_bytes: 256
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import Data.Foldable (foldMap)
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
import Data.Array
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
 
readInt = read :: String -> Int
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
fnBin :: (b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d
fnBin op f g x = op (f x) $ g x
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
modifyArray :: (Ix i, MArray a e m) => a i e -> i -> (e -> e) -> m ()
modifyArray arr ix f = readArray arr ix >>= writeArray arr ix . f
-- end of templete

f h m
  | diff < 300 = "alert"
  | diff >=900 = "safe"
  | otherwise = "warning"
  where
    degH = h * 300 + m * 5
    degM = m * 60
    diff = minimum [mod (degH - degM) 3600, mod (degM - degH) 3600]

main = getInt >>= flip replicateM getLine >>= mapM_ (putStrLn . apply2 f . map readInt . wordsBy (==':'))

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

int main() {
  int N;
  string A, Y;
  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> A;
    if (A == "Y") {
      cout << "Four" << endl;
      break;
    }
  }
  
  if (A != "Y") {
  cout << "Three" << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
int main ()
{
	int n ,q, a,a1[10000],a2[100000],k=0;
	scanf("%d",&n);
	for(int i = 0;i<n;i++)
	{
		scanf("%d",&a1[i]);
	}
	scanf("%d",&q);
	for(int i=0;i<q;i++)
	{
		scanf("%d",&a2[i]);
		for(int j=0;j<n;j++)
		{
			if(a1[j]==a2[i])
			 {
			 k++;
			 break;
			 }
		}
	}
	printf("%d\n",k);
	return 0;
}




Measured memory_bytes: 2104
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <cmath>
typedef long long ll;
using namespace std;
ll intpow(int n,int m){
    if(m==0)return 1;
    return n*intpow(n,m-1);
}
ll gcd(ll n,ll m){
    if(n<m)swap(n,m);
    if(n%m == 0)return m;
    return gcd(m,n%m);
}
ll lcm(ll n,ll m){
    return n*m/gcd(n,m);
}
int main(){
    int n,g,a;
    cin >> n >> g;
    for(int i=0;i<n-1;i++){
        cin >> a;
        g = gcd(g,a);
    }
    cout << g << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
	int n,mi=10000000,ma=-10000000;
	long long sum=0;
	cin >> n;
	int i,b;
	for(i=0;i<n;i++){
		cin >> b;
		mi=min(mi,b);
		ma=max(ma,b);
		sum+=b;
	}
	cout << mi << " " << ma << " " << sum << endl;
	return 0;
}


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

//ライブラリ始まり

//定数
//円周率
const double pi = 3.1415926535897932384;
//天井
const int INF = 1000000000; // = 10^9
const ll LINF = 1000000000000000; // = 10^15
//ABC文字列
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZABC";
const string abc = "abcdefghijklmnopqrstuvwxyzabc";
//よくあるmodくん
const ll MOD = 1000000007; // = 10^9 + 7

//データ構造
//Union_Find木
struct UnionFind {
  vector<int> UF; // UF.at(i) : iの親の番号
  vector<int> SIZE; // SIZE.at(root(i)) : iと連結されてる要素の数
  UnionFind(int N) : UF(N), SIZE(N, 1) { // 最初は全てが根であるとして初期化
    for(int i = 0; i < N; i++) {
      UF.at(i) = i;
    }
  }
  int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
    if (UF.at(x) == x) {
      return x;
    }
    return UF.at(x) = root(UF.at(x));
  }
  void unite(int x, int y) { // xとyの木を併合
    int rx = root(x); // xの根をrx
    int ry = root(y); // yの根をry
    if (rx == ry) {
      return; // xとyの根が同じ(=同じ木にある)時はそのまま
    }
    // xとyの根が同じでない(=同じ木にない)時：小さい方の根を大きい方の根につける
    if (SIZE.at(rx) < SIZE.at(ry)) {
      UF.at(rx) = ry;
      SIZE.at(ry) += SIZE.at(rx);
      SIZE.at(rx) = 0;
    }
    else {
      UF.at(ry) = rx;
      SIZE.at(rx) += SIZE.at(ry);
      SIZE.at(ry) = 0;
    }
  }
  bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
  int size(int x) { // xと連結されてる要素の数を返す
    return SIZE.at(root(x));
  }
};

//関数
//ctoi
int ctoi(char c){
  if (c == '0') return 0;
  if (c == '1') return 1;
  if (c == '2') return 2;
  if (c == '3') return 3;
  if (c == '4') return 4;
  if (c == '5') return 5; 
  if (c == '6') return 6;
  if (c == '7') return 7;
  if (c == '8') return 8;
  if (c == '9') return 9;
  return -1;  
}
//to_char
char to_char(int i){
  if (i == 0) return '0';
  if (i == 1) return '1';
  if (i == 2) return '2';
  if (i == 3) return '3';
  if (i == 4) return '4';
  if (i == 5) return '5';
  if (i == 6) return '6';
  if (i == 7) return '7';
  if (i == 8) return '8'; 
  if (i == 9) return '9';
  return ' ';  
}
//素数判定
bool PN(int x) {
  if (x <= 1) return false; // 1や0,-1は素数ではない
  if (x == 2) return true; // √2 + 1 > 2 なので下でやると 2 ％ 2 = 0 となり判定できない
  for (int i = 2; i < sqrt(x) + 1; i++) {
    if (x % i == 0) return false; // 割れたら素数じゃない
  }
  return true;
}
// A^N mod M を計算する。modしたくなかったらM = LINFとかにすればよい。
ll modpow(ll A, ll N, ll M) {
  long long ans = 1;
  while (N > 0) {
    if (N & 1) ans = ans * A % M;
      A = A * A % M;
      N >>= 1;
   }
  return ans;
}

//ライブラリ終わり
  
//メイン処理
int main() {
  cout << fixed << setprecision(16); //精度向上
  //ここまでテンプレ
  vector<int> M(100001, 0);
  for (int i = 1; i <= 100000; i++) {
    if (i % 2 == 1) {
      if (PN(i) && PN((i + 1) / 2)) {
        M.at(i)++;
      }
    }
    M.at(i) += M.at(i - 1);
  }
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    cout << M.at(r) - M.at(l - 1) << endl;
  }
}

Measured memory_bytes: 3660
A, B, C, D = [int(i) for i in input().split()]

def lcm(a, b):
    ori_a, ori_b = a, b
    if a > b: a, b = b, a
    while True:
        a, b = b%a, a
        if a == 0:
            g = b
            break
        elif a == 1:
            g = 1
            break

    return ori_a // g * ori_b

S1 = A - ( A//C + A//D - A//lcm(C, D) ) - (1 if A%C and A%D else 0)
S2 = B - ( B//C + B//D - B//lcm(C, D) )

print(S2 - S1)

Measured memory_bytes: 3064
r, c = map(int, input().split())   #r, cを読み込む
l = [[0 for i in range(c + 1)] for i in range(r + 1)]
#0 for i in range(n)   n個の要素を0で初期化
for i in range(r) :
 l[i] = list(map(int, input().split()))   #行ごとに読み込み

for i in range(r) :
 s = sum(l[i])   #行ごとの和を求める
 l[i].append(s)   #sをi行目の最後に追加

for j in range(c) :   #列ごとの和を求める 横に1つずつ動く
 s = 0
 for i in range(r) :   #1行ずつ進む
   s += l[i][j]
 l[r][j] = s   #0行目から始まってる→r(r+1)行目にc列目の和

l[r][c] = sum(l[r])   #l[r][c] = l[r]の和

for i in range(r + 1) :   #range→(r+1)回
 for j in range(c + 1) :
   if(j == c) :
     print(l[i][j])
   else :
     print(str(l[i][j]) + " ", end = "")


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

//#define TRACE
#ifdef TRACE
#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 LL long long

const int mod = 998244353;
const int MX = 3005;

LL n, s;
LL inp[MX];
LL dp[MX][MX];
LL pre[MX][MX];

int main() {
	cin >> n >> s;
	for(int i=1;i<=n;i++) {
		cin >> inp[i];
	}

	for(int i=1;i<=n;i++) {
		dp[i][inp[i]] = i;
	}

	for(int i=1;i<=n;i++) {
		for(int k=1;k<=s;k++) {
			pre[i][k] = (pre[i-1][k] + dp[i][k])%mod;
		}
	}

	for(int i=1;i<=n;i++) {
		for(int k=1;k<=s;k++) {
			if(inp[i] < k) {
				dp[i][k] = (dp[i][k] + pre[i-1][k-inp[i]])%mod;
			}
			pre[i][k] = (pre[i-1][k] + dp[i][k])%mod;
		}
	}

	LL ans = 0;
	for(int i=1;i<=n;i++) {
		ans = (ans + (dp[i][s] * (n - i + 1))%mod)%mod;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 141184
#include <bits/stdc++.h>
#define pi 3.14159
using namespace std;
int main()
{
	long long int i,n,j,p,r,max=0;
	
	cin>>n;
	int a[n];
	for(i=0;i<n;i++)
		cin>>a[i];
		for(i=0;i<n;i++)
			{
				if(max<a[i])
				{
					max=a[i];
					p=i;
				}
					
			}
	sort(a,a+n);
	r=a[n-2];
	for(i=0;i<n;i++)
		{
			if(i!=p)
				cout<<max<<endl;
			else
				cout<<r<<endl;
		}
}


Measured memory_bytes: 4412
use proconio::{input, fastout};
use proconio::marker::{Chars};

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
      }
  }

#[fastout]
fn main() {
    input!{
        mut n: Chars,
    }

    for i in 0..n.len() {
        if n[i]=='1' {
            n[i] = '9';
        } else if n[i]=='9' {
            n[i] = '1';
        } else {
            continue;
        }
    }

    let n1: String = n.iter().collect();
    let n2: usize = n1.parse().unwrap();
    println!("{}", n2);

}


Measured memory_bytes: 2176
(* unihernandez22
 * https://atcoder.jp/contests/abc172/tasks/abc172_a
 * implementation
 * *)

let rec pow a b =
    if b == 0 then 1 else a * pow a (b - 1);;

Printf.printf "%d\n" @@
Scanf.scanf "%d" @@ fun a ->
    a + pow (a) (2) + pow (a) (3);



Measured memory_bytes: 3848
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

     
int main(void){
	ios::sync_with_stdio(false);
	string a;
	char day[10];
	
	cin >> a;
	
	for(int i = 0; i < 10; i++){
		if(i == 3){
			cout << "8";
		}else{
			cout << a[i];
		}
	}
	

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define eps 1e-9
#define oo 1e7+5

using namespace std;

typedef unsigned long long ull;
typedef vector<pair<int,pair<int,int>>> dirgraph;
typedef vector<vector<int>> graph;

vector<int> bfs(graph& g,vector<bool>& visit)
{
	int n=g.size();
	
	queue<int> q;
	vector<int>ans(n);
	q.push(0);
	
	while(!q.empty())
	{
		int temp=q.front();
		q.pop();
		visit[temp]=1;
		for(int u :g[temp])
		{
			if(!visit[u])
			{
				ans[u]=temp+1;
				visit[u]=1;
				q.push(u);
			}
		}
	}
	return ans;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	int n,m;
	cin>>n>>m;
	
	graph g(n);
	for (int i = 0; i < m; i++)
	{
		int x,y;
		cin>>x>>y;
		x--;y--;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	vector<bool>visit(n);
	vector<int> ans=bfs(g,visit);
	bool flag=0;
	for(int i=1;i<n;i++)
		{
			if(!visit[i])
			{
				flag=1;
				break;
				}
		}
	
	if(flag)cout<<"No"<<endl;	
	
	else{
	cout<<"Yes"<<endl;
	for(int i=1;i<n;i++)
		cout<<ans[i]<<endl;
}
	return 0;
}



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

using namespace std;

using ll = long long;

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

    ll n;
    cin >> n;
    vector<ll> a(3 * n);
    for (int i = 0; i < 3 * n; ++i) cin >> a[i];

    vector<ll> score(n + 1);
    ll sum_l = 0, sum_r = 0;
    priority_queue<ll, vector<ll>, greater<ll>> que_l;
    priority_queue<ll> que_r;
    for (int i = 0; i < n; ++i) {
        sum_l += a[i];
        que_l.push(a[i]);
        sum_r += a[3 * n - i - 1];
        que_r.push(a[3 * n - i - 1]);
    }
    score[0] = sum_l;
    score[n] -= sum_r;

    for (ll i = 1, sum2 = 0; i <= n; ++i) {
        que_l.push(a[n + i - 1]);
        sum_l += a[n + i - 1];
        sum2 += que_l.top(); que_l.pop();
        score[i] += sum_l - sum2;
    }
    for (ll i = n - 1, sum2 = 0; 0 <= i; --i) {
        que_r.push(a[n + i]);
        sum_r += a[n + i];
        sum2 += que_r.top(); que_r.pop();
        score[i] -= sum_r - sum2;
    }

    cout << *max_element(score.begin(), score.end()) << endl;

    return 0;
}


Measured memory_bytes: 5228
from collections import Counter
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]
INF = 10**9
N, M = map(int, input().split())
d = [[INF] * (N+1) for i in range(N+1)]
for i in range(N+1):
    d[i][i] = 0
es = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    d[a][b], d[b][a] = c, c
    es[i] = (a, b, c)
for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
ans = M
for k in range(M):
    i, j, c = es[k]
    for s in range(1, N+1):
        if d[s][i] + c == d[s][j]:
            ans -= 1
            break
print(ans)


Measured memory_bytes: 3812
#include<iostream>
#include<algorithm>
#include<limits.h>

using namespace std;

const long long MOD = 2019;

int main()
{
    long long l, r, lmod, rmod, minx;
    minx = LONG_MAX;
    cin>>l>>r;
    lmod = l % MOD;
    rmod = r % MOD;
    if(r-l>=MOD)
    {
        cout<<0;
        return 0;
    }
    if(rmod > lmod)
        for(int i=lmod;i<=rmod-1;i++)
            for(int j=i+1;j<=rmod;j++)
                minx = min(minx,(i*j)%MOD);

    cout<<minx;
    
}

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

int main() {
  int64_t n, a, b, ans;
  cin >> n >> a >> b;
  if (n == 1) {
    if (a == b) {
      ans = 1;
    } else {
      ans = 0;
    }
  } else if (a > b) {
    ans = 0;
  } else {
    ans = (b*(n-1)+a) - (b+a*(n-1)) + 1;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef double db;
int main () {
  int N, M;
  cin >> N >> M;
  vector<db>E(N + 1);
  vector<db>P(N + 1, 0);
  vector<vector<int>>dag(N + 1);
  for (int i = 0; i < M; i ++) {
    int s, t;
    cin >> s >> t;
    dag[s].push_back(t);
  }
  P[1] = 1;
  for (int i = 1; i < N; i ++) {
    int s = (int)dag[i].size();
    for (int j = 0; j < s; j ++) {
      P[dag[i][j]] += (P[i] / s);
    }
  }
  E[N] = 0;
  for (int i = N - 1; i >= 1; i --) {
    int s = (int)dag[i].size();
    db kj = 0;
    for (int j = 0; j < s; j ++) {
      kj += E[dag[i][j]];
    }
    kj /= s;
    E[i] = kj + 1;
  }
  db ans = E[1];
  //cout << ans << endl;
  for (int i = 1; i < N; i ++) {
    int s = dag[i].size();
    if (s == 1) continue;
    for (int j = 0; j < s; j ++) {
      db moto = (E[i] - 1) * s;
      db dis = ((moto - E[dag[i][j]]) / (s - 1) + 1) - E[i];
      db kj = E[1] + (dis * P[i]);
      //cout << ans << endl;
      if (ans > kj) ans = kj;
    }
  }
  cout << setprecision(10) << ans << endl;
}



Measured memory_bytes: 4944
n,m = gets.split.map(&:to_i)
s = []
c = []
m.times do |i|
    s[i],c[i] = gets.split.map(&:to_i)
end
result_f = Array.new(n,0)
result = Array.new(n)
for i in 0..(m-1)
    if result_f[s[i]-1] == 0 || result[s[i]-1] == c[i]
        result[s[i]-1] = c[i]
        result_f[s[i]-1] = 1
    else
        puts -1
        exit
    end
end
if n == 1
  if result[0] == nil
    result[0] = 0
  end
end
if n == 2
  if result[0] == nil
     result[0] = 1
  end
  if result[1] == nil
     result[1] = 0
  end
elsif n == 3
    if result[0] == nil
        result[0] = 1
    end
    if result[1] == nil
        result[1] = 0
    end
    if result[2] == nil
        result[2] = 0
    end
end
if (n == 2 && result[0] == 0) || (n == 3 && result[0] == 0)
  puts -1
  exit
end
puts result.join

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i,N) cin >> A[i];
  deque<int> d;

  rep(i,N){
    int p = lower_bound(d.begin(),d.end(),A[i]) - d.begin();
    if(p == 0){
      d.push_front(A[i]);
    } else d[p-1] = A[i];
  }
  int ans = d.size();
  cout << ans << endl;
}

Measured memory_bytes: 1024
#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 INF 1000000000000000000

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

    int N;
    cin >> N;
    vector<ll> A(N);
    ll cnt = 0;
    rep(i, N) {
        cin >> A[i];
        if (A[i] < 0)
            cnt++;
    }

    ll ans = 0;
    if (cnt % 2 == 0) {
        rep(i, N) { ans += abs(A[i]); }
    } else {
        ll mi = INF;
        rep(i, N) {
            mi = min(mi, abs(A[i]));
            ans += abs(A[i]);
        }

        ans -= (2 * abs(mi));
    }

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

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(void){
    string s, ans = "";
    cin >> s;
    for (int i=0;i<s.length();i++){
        if (s[i] == 'A'){
            ans += 'T';
        } else if (s[i] == 'T'){
            ans += 'A';
        } else if (s[i] == 'C'){
            ans += 'G';
        } else {
            ans += 'C';
        }
    }
    cout << ans << endl;
}

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

int main(){
  int n;
  double sum = 0;
  cin >> n;
  vector<double> a(n);
  for (int i = 0; i < n; i++){
    cin >> a.at(i);
  }
  for (int i = 0; i < a.size(); i++){
    sum += 1/a[i];
  }

  cout << fixed << setprecision(10) << 1/sum << endl;
  
}

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

int mat[100002][4];
int dp[100002][4];

int n;
int  func(int row,int pc)
{
    if(row==n){
    return 0;
    }
    if(dp[row][pc]!=-1)
    return dp[row][pc];
    int maxi=0;
    if(pc==0)
    {
       maxi=max(maxi,mat[row][1]+func(row+1,1));
       maxi=max(maxi,mat[row][2]+func(row+1,2));
       maxi=max(maxi,mat[row][3]+func(row+1,3));
    }
    else if(pc==1)
    {
        maxi=max(maxi,mat[row][2]+func(row+1,2));
        maxi=max(maxi,mat[row][3]+func(row+1,3));
    }
    else if(pc==2)
    {
        maxi=max(maxi,mat[row][1]+func(row+1,1));
        maxi=max(maxi,mat[row][3]+func(row+1,3));
    }
    else {
        maxi=max(maxi,mat[row][1]+func(row+1,1));
        maxi=max(maxi,mat[row][2]+func(row+1,2));
    }
    return dp[row][pc]=maxi;
    
}
int main() {
	
	cin>>n;
	
	for(int i=0;i<n;i++)
	{
	    for(int j=1;j<=3;j++)
	    cin>>mat[i][j];
	}
	int row=0;
	int pc=0;
	for(int i=0;i<n;i++)
	{
	    for(int j=0;j<=3;j++)
	    dp[i][j]=-1;
	}
	
	
	cout<<func(row,pc)<<"\n";
}


Measured memory_bytes: 14488
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')


def main():
	n,h=MI()
	li=[LI() for _ in range(n)]
	
	li.sort(key=lambda x:x[1])
	#print(li)
	li.sort(key=lambda x:x[0],reverse=True)
	#print(li)
	
	a=li[0][0]
	b=li[0][1]
	
	li=li[1:]
	li.sort(key=lambda x:x[1],reverse=True)
	
	A=[]
	#print(li)
	for i in range(n-1):
		if li[i][1]>a:
			A.append(li[i][1])
		else:
			break
	
	#print(A)
	ans=0
	
	for i in A:
		if h>0:
			ans+=1
			h-=i
		else:
			print(ans)
			exit()
	else:
		if h<=0:
			print(ans)
		elif h<=b:
			print(ans+1)
		else:
			print(ans+1-(b-h)//a)
		
	
	
	

if __name__=="__main__":
	main()


Measured memory_bytes: 28404
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <functional>
#include <set>
#include <map>
#include <cmath>
#include <string>
#define SIZE 131080
#define INF 100000000000000000LL

using namespace std;
typedef long long int ll;
typedef pair <ll,ll> P;

vector <int> vec[SIZE];
vector <int> cost[SIZE];
vector <P> dp[SIZE];
ll X;
bool vl;

void dfs(int v,ll d)
{
	dp[v].clear();
	if(vec[v].size()==0)
	{
		dp[v].push_back(P(d,d));
		return;
	}
	int l=vec[v][0],r=vec[v][1];
	dfs(l,d+cost[v][0]);dfs(r,d+cost[v][1]);
	if(dp[l].size()<dp[r].size()) swap(l,r);/*
	if(v==2)
	{
		for(int i=0;i<dp[l].size();i++) printf("[%lld %lld] ",dp[l][i].first,dp[l][i].second);puts("");
		for(int i=0;i<dp[r].size();i++) printf("[%lld %lld] ",dp[r][i].first,dp[r][i].second);puts("");
	}*/
	int to=0;
	vector <P> A,B;
	ll bef=INF;
	for(int i=0;i<dp[r].size();i++)
	{
		P p=dp[r][i];
		while(to<dp[l].size()&&dp[l][to].first+p.second<=X+2LL*d) to++;
		if(to>0)
		{
			to--;
			if(bef==dp[l][to].second) continue;
			bef=dp[l][to].second;
			A.push_back(P(p.first,bef));
			B.push_back(P(bef,p.first));
		}
	}
	reverse(B.begin(),B.end());
	int s=0,t=0;
	while(s<A.size()||t<B.size())
	{
		if(s==A.size()) dp[v].push_back(B[t++]);
		else if(t==B.size()) dp[v].push_back(A[s++]);
		else if(A[s]<=B[t])
		{
			while(t<B.size()&&B[t].second>=A[s].second) t++;
			dp[v].push_back(A[s++]);
		}
		else
		{
			while(s<A.size()&&A[s].second>=B[t].second) s++;
			dp[v].push_back(B[t++]);
		}
	}
}
void see(int v)
{
	printf("%d\n",v+1);
	for(int i=0;i<dp[v].size();i++) printf("[%lld %lld]\n",dp[v][i].first,dp[v][i].second);
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,v;
		scanf("%d %d",&a,&v);a--;
		vec[a].push_back(i);
		cost[a].push_back(v);
	}
	//X=15;
	//dfs(0,0);
	//for(int i=0;i<n;i++) see(i);
	//return 0;
	ll l=-1,r=INF;
	while(r-l>1)
	{
		X=(l+r)/2;
		dfs(0,0);
		//for(int i=0;i<n;i++) see(i);
		//return 0;
		if(dp[0].empty()) l=X;
		else r=X;
	}
	printf("%lld\n",r);
	return 0;
}


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

int main(){
    int n,k;
    cin>>n>>k;
    vector<ll> v(max(n,k)+1,0);
    for(int i=1;i<=n;i++){
        v[i%k]++;
    }
    ll ans=0;
    if(k%2==1){
        cout<<v[0]*v[0]*v[0]<<endl;
    }else{
        cout<<v[0]*v[0]*v[0]+v[k/2]*v[k/2]*v[k/2]<<endl;
    }
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <complex>
#include <cstdio>
using namespace std;
typedef complex<double> P;

double cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}
P outcircle(P a,P b,P c){
  return (norm(b-c)*(norm(c-a)+norm(a-b)-norm(b-c))*a+
	  norm(c-a)*(norm(a-b)+norm(b-c)-norm(c-a))*b+
	  norm(a-b)*(norm(b-c)+norm(c-a)-norm(a-b))*c)/(P)(4*cross(b-a,c-a)*cross(b-a,c-a));
}
int main(){
  int n;
  double x1,y1,x2,y2,x3,y3;
  P a,b,c;
  cin>>n;
  for(;n>0;n--){
    cin >>x1 >>y1 >>x2 >>y2 >>x3 >>y3;
    P a=P(x1,y1);
    P b=P(x2,y2);
    P c=P(x3,y3);
    P q = outcircle(a,b,c);
    printf("%.3f %.3f %.3f\n",q.real(),q.imag(),abs(a-q));
  }
  return 0;
}

Measured memory_bytes: 0
#include<cstdio>
#include<vector>
#include<algorithm>
typedef long long ll;
struct pr
{ll x,y;};
inline bool operator<(pr x,pr y)
{return x.x<y.x;}
int n;
int f[222222],s[222222][3],e[222222],d[222222][3];
using std::vector;
vector<pr>dat[222222];
inline void ins(int p,ll x,ll y)
{dat[p].push_back((pr){x,y});}
ll dep[222222];
inline bool jud(ll len,int p=1)
{
	dat[p].clear();
	if(!s[p][1]){ins(p,dep[p],dep[p]);return 1;}
	if(jud(len,s[p][1])&&jud(len,s[p][2]))
	{//printf("%lld %d\n",len,p);
		register int i=0,ii=0;
		for(;i<dat[s[p][1]].size();)
		{
			ll x1=dat[s[p][1]][i].x,x2=dat[s[p][2]][ii].x,
			y1=dat[s[p][1]][i].y,y2=dat[s[p][2]][ii].y;
			//printf("%lld %d %lld %lld %lld %lld\n",len,p,x1,x2,y1,y2);
			//if(x2+y1-dep[p]*2<=len)ins(p,x1,y2),ins(p,y2,x1);
			if(x1+y2-dep[p]*2<=len)i++,ins(p,x2,y1),ins(p,y1,x2);
			else ii++;
			if(ii>=dat[s[p][2]].size())break;
		}
		if(!dat[p].size())return 0;
		std::sort(dat[p].begin(),dat[p].end());
		return 1;
	}return 0;
}
ll l=1e9,r=0;
inline void dfs(int p=1,ll sum=0)
{
	dep[p]=sum;
	if(l>dep[p])l=dep[p];
	if(r<dep[p]*2)r=dep[p]*2;
	if(!s[p][1])return;
	dfs(s[p][1],d[p][1]+sum),dfs(s[p][2],d[p][2]+sum);
}
int main()
{
	scanf("%d",&n);
	register int i;
	for(i=2;i<=n;i++)
	{
		scanf("%d %d",&f[i],&e[i]);
		if(s[f[i]][1])s[f[i]][2]=i,d[f[i]][2]=e[i];
		else s[f[i]][1]=i,d[f[i]][1]=e[i];
	}dfs();
	for(;l+1<r;)
	{
		ll mid=(l+r)>>1;
		if(jud(mid))r=mid;
		else l=mid;
	}printf("%lld\n",r);
}

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

#define vec(v) vector<int>(v)
#define be(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define mapci(mp) map<char*,int>(mp)
#define mapcc(mp) map<char*,char*>(mp)
typedef long long ll;
using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, c, k, ans = 0, sum = 0;
    cin >> n >> c >> k;
    ll a = -1000000009, t[n];
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }
    sort(t, t + n);
    for (int i = 0; i < n; i++) {
        if (sum == c) {
            a = t[i];
            ans++;
            sum = 1;
        }
        else {
            if (a + k >= t[i]) {
                sum++;
            }
            else {
                a = t[i];
                ans++;
                sum = 1;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
int n, k;
string s;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n>>k>>s;
    int ans=0;
    int count=0;
    for(int i=0;i<s.size()-1;i++){
        if(s[i]==s[i+1]){
            ans++;
        }
        else{
            count++;
        }
    }
    while(k!=0&&count!=0){
        if(count>1){
            ans+=2;
            count-=2;
        }
        else{
            ans+=1;
            break;
        }
        k--;
    }
    cout << ans << "\n";
}


Measured memory_bytes: 512
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
]

puts a[gets.to_i - 1]

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
int main() {
  vector<int> vec(13);
  vec = {0, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1};
  int x, y;
  cin >> x >> y;
  if (vec.at(x) == vec.at(y)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


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

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

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

  int sum = 0;
  for (int i = 0; i < n; ++i) {
    sum += a[i] % 2;
  }

  if (sum > 0) {
    cout << "first" << endl;
  } else {
    cout << "second" << endl;
  }
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define LEN 300005
using namespace std;

typedef struct node{
	char name[100];
	int time;
}P;

P Q[LEN + 1];
int head, tail, n;

void enqueue(P x){
	Q[tail + 1] = x;
}

P dequeue(){
	return Q[head];
}

int main(int argc, char *argv[]) {
	int i, q;
	
	scanf("%d %d", &n, &q);
	
	for (i = 0;i < n;i++) {
		scanf("%s", Q[i].name);
		scanf("%d", &Q[i].time);
	}
	
	int elaps = 0;
	P u;
	head = 0, tail = n;
	while (head != tail) {
		u = Q[head++];
		if (u.time > q) {
			u.time -= q;
			Q[tail++] = u;
			elaps += q;
		}else {
			elaps = elaps + u.time;
			printf("%s %d\n", u.name, elaps);
		}

	}
	
	return 0;
}


Measured memory_bytes: 22392
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"
vector<int>sumws;
vector<int>sumts;
vector<int>maxcs;
vector<int>maxbs;
int memo[1 << 15];
int getans(bitset<15>&bs) {
	if (memo[bs.to_ulong()] != -1)return memo[bs.to_ulong()];
	if (bs.count() == 1) {
		for (int i = 0; i < 15; ++i) {
			if (bs[i]) {
				auto it = upper_bound(sumws.begin(), sumws.end(), maxcs[i]);
				auto jt = upper_bound(sumts.begin(), sumts.end(), maxbs[i]);
				return min(it - sumws.begin(), jt - sumts.begin()) - 1;
			}
		}
	}
	else {
		int ans = 0;
		for (int i = 0; i < 15; ++i) {
			if (bs[i]) {
				bs[i] = false;
				int preread=getans(bs);
				const int noww = sumws[preread];
				const int nowt = sumts[preread];

				auto it = upper_bound(sumws.begin(), sumws.end(), noww+maxcs[i]);
				auto jt = upper_bound(sumts.begin(), sumts.end(), nowt+maxbs[i]);
				const int nowread= min(it - sumws.begin(), jt - sumts.begin()) - 1;
				ans = max(ans, nowread);
				bs[i] = true;
			}
		}
		return memo[bs.to_ulong()] = ans;
	}
}
int main() {
	for (int i = 0; i < 1 << 15; ++i) {
		memo[i] = -1;
	}
	int M, N; cin >> M >> N;
	sumws.resize(M + 1);
	sumts.resize(M + 1);
	for (int i = 0; i < M; ++i) {
		int w, t; cin >> w >> t;
		sumws[i + 1] = sumws[i] + w;
		sumts[i + 1] = sumts[i] + t;
	}
	for (int i = 0; i < N; ++i) {
		int c, b; cin >> c >> b;
		maxcs.push_back(c);
		maxbs.push_back(b);
	}
	bitset<15>bs;
	for (int i = 0; i < N; ++i) {
		bs[i] = true;

	}
	int ans = getans(bs);
	cout << ans << endl;
	return 0;
}

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

using namespace std;

int main()
{
    string S;
    string S1, S2;

    cin >> S;

    S1 = S.substr(0, 2);
    S2 = S.substr(2, 2);

    int s1 = atoi(S1.c_str());
    int s2 = atoi(S2.c_str());

    if((1 <= s1 && s1 <= 12) &&  (s2 == 0 || s2 > 12)){
        cout << "MMYY" << endl;
    }
    else if((1 <= s2 && s2 <= 12) && (s1 == 0 || s1 > 12)){
        cout << "YYMM" << endl;
    }
    else if ((1 <= s1 && s1 <= 12) && (1 <= s2 && s2 <= 12)){
        cout << "AMBIGUOUS" << endl;
    }
    else{
        cout << "NA" << endl;
    }

    return 0;
}

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

int main(){
	int N,M;
	vector<double> A;
	cin >> N >> M;
	rep(i,N){double t; cin >> t; A.push_back(t); }

	double sum = accumulate(A.begin(),A.end(),0);
	double p = sum*1/(4*M);
	int cnt = 0;
	rep(i,N){ 
		if(A[i]<p){continue;}
		cnt++;
	}

	if(cnt>=M)cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

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

    int i = N;

    while (true)
    {
        if (i % 2 == 0 && i % N == 0)
        {
            cout << i << endl;
            break;
        }

        i++;
    }
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
int gcd(int A,int B) {if(!B)return A;return gcd(B,A%B);}
VII dp(3001,vector<ll>(3001,0));
int main()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	dp[a][b] = 1;
	for(int i=a;i<=c;i++){
		for(int j=b;j<=d;j++){
			if(i == a && j == b)continue;
			if(i > a)dp[i][j]+= dp[i-1][j]*j%MOD;
			if(j > b)dp[i][j]+= dp[i][j-1]*i%MOD;	
			if(i > a && j > b)dp[i][j] -= dp[i-1][j-1]*(j-1)*(i-1)%MOD;
			dp[i][j]+=MOD;
			dp[i][j]%=MOD;
		}
	}
	cout<<dp[c][d]%MOD;
	
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,N) for(ll i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

int a,b,c;

int main(){
    cin >> a >> b >> c;
    if(a < c && c < b)cout << "Yes" << endl;
    else if(b < c && c < a)cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}
void readA(T)(size_t n,ref T[]t){t=new T[](n);auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  int n; readV(n);
  int[] a; readA(n, a);

  auto m = 10^^9;
  foreach (x; a.reduce!min..a.reduce!max+1)
    m = min(m, a.map!(ai => (x-ai)^^2).sum);

  writeln(m);
}


Measured memory_bytes: 256
import heapq
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
f=a[:n]
heapq.heapify(f)
b=[-i for i in a[2*n:]]
heapq.heapify(b)
maxi=sum(f)
mini=-sum(b)
fmax=[0]*(n+1)
fmax[0]=maxi
bmin=[0]*(n+1)
bmin[n]=mini
for i in range(n):
  heapq.heappush(f,a[n+i])
  fa=heapq.heappop(f)
  maxi+=a[n+i]-fa
  fmax[i+1]=maxi
  heapq.heappush(b,-a[2*n-1-i])
  ba=-heapq.heappop(b)
  mini+=a[2*n-1-i]-ba
  bmin[n-i-1]=mini
ans=-float('inf')
for i in range(n+1):
  ans=max(ans,fmax[i]-bmin[i])
print(ans)

Measured memory_bytes: 39084
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    d = LI()
    d = sorted(d)
    ans = d[N//2] - d[N//2 - 1]
    print(ans)

main()



Measured memory_bytes: 16252
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
 
using _loop_int = int;
#define REP(i,n) for(_loop_int i=0; i<(_loop_int)(n); i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a); i<(_loop_int)(b); i++)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1; i>=(_loop_int)(a); i--)
 
#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))
#define ALL(v) (v).begin(),(v).end()
 
#define DEBUG(x) cerr<<#x<<": "<<(x)<<endl
#define DEBUG_VEC(v) cerr<<#v<<": ";REP(__i,(v).size())cerr<<((v)[__i])<<", ";cerr<<endl
 
const ll MOD = 1000000007ll;
 
int n;
int h[125252];
 
int main(){
    scanf("%d",&n);
    REP(i,n)scanf("%d",h+i);
    REP(i,n){
        if(i==0 || h[i-1] < h[i])h[i]--;
    }
    REP(i,n-1)if(h[i]>h[i+1]){
        puts("No");
        return 0;
    }
    puts("Yes");
    return 0;
}

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

using i64 = int64_t;

constexpr i64 MOD = 1e9 + 7;

i64 dp[1003][1003]={0};

int main(){
    string t, b;
    cin >> t >> b;
    dp[0][0] = 1;
    for(int i=1;i<=(int)t.size();++i){
        for(int j=0;j<=(int)b.size();++j){
            dp[i][j] += dp[i-1][j];
            dp[i][j] %= MOD;
            if(j > 0 && t[i-1] == b[j-1]){
                dp[i][j] += dp[i-1][j-1];
                dp[i][j] %= MOD;
            }
        }
    }

    cout << dp[(int)t.size()][(int)b.size()] << endl;

    return 0;
}



Measured memory_bytes: 11036
#![allow(unused_imports)]
#![allow(clippy::many_single_char_names)]

// language: Rust(1.42.0)
// check available crates on AtCoder at "https://atcoder.jp/contests/language-test-202001"
// My Library Repo' is at "https://github.com/Loptall/prcn_lib"

/*
    そう甘くはないんだな〜w
*/

// from std...
use std::cmp::{
    max, min,
    Ordering::{Equal, Greater, Less},
    Reverse,
};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::convert::TryInto;
use std::mem::swap;
use std::ops::*;
use std::process::exit;
use std::{f32, f64, i128, i16, i32, i64, i8, isize, u128, u16, u32, u64, u8, usize};

// Dep' crates are...
use itertools::*;
use itertools_num::*;
use lazy_static::lazy_static;
use maplit::{btreemap, btreeset, hashmap, hashset};
use num_bigint::{BigInt, BigUint};
use num_complex::Complex;
use num_integer::{binomial, gcd, lcm, Integer};
use num_rational::Rational;
use num_traits::{clamp, one, pow, zero, One, Pow, Zero};
use permutohedron::Heap;
use petgraph::unionfind::UnionFind;
use proconio::{fastout, input, is_stdin_empty, marker::*};
use rand::rngs::SmallRng;
use rand::{random, Rng, SeedableRng};

pub const MOD: usize = 1000000007;
pub const MAX: usize = 1usize << 63usize;
pub const MIN: i64 = i64::MIN;
pub const PI: f64 = f64::consts::PI;
pub const A: u8 = 'A' as u8;

use std::time::{Duration, Instant};

// code...
// #[fastout]
fn main() {
    input! {
        d: usize,
        c: [i64; 26],
        s: [[i64; 26]; d]
    }

    let start = Instant::now();

    let mut rng = SmallRng::from_entropy();

    let mut ans = Vec::new();
    for day in 0..d {
        let w = s[day].iter().enumerate().max_by_key(|x| x.1).unwrap().0 + 1;
        ans.push(w);
    }
    let mut scr = score(d, &c, &s, &ans);

    dbg!(scr);

    let mut count = 0usize;

    while start.elapsed().as_millis() < 1980 {
        let prev = ans.clone();
        ch(&mut ans, &c, &s, &mut rng);
        let new = score(d, &c, &s, &ans);
        if new <= scr {
            ans = prev;
        } else {
            scr = new;
        }
        count += 1;
    }

    dbg!(score(d, &c, &s, &ans));
    dbg!(count);

    for i in ans {
        println!("{}", i);
    }
}

fn score(d: usize, c: &Vec<i64>, s: &Vec<Vec<i64>>, ans: &Vec<usize>) -> i64 {
    let mut last = vec![0usize; 26];
    let mut a = 0i64;

    for day in 0..d {
        a += s[day][ans[day] - 1];
        last.iter_mut().for_each(|x| *x += 1);
        last[ans[day] - 1] = 0;
        a -= last
            .iter()
            .enumerate()
            .map(|(i, l)| c[i] * *l as i64)
            .sum::<i64>();
    }
    a
}

fn ch(ans: &mut Vec<usize>, c: &Vec<i64>, s: &Vec<Vec<i64>>, rng: &mut SmallRng) {
    for (d, i) in ans.iter_mut().enumerate() {
        if rng.gen_bool(0.01) {
            let g = s[d]
                .iter()
                .enumerate()
                .sorted_by(|a, b| b.1.cmp(a.1))
                .take(5)
                .collect_vec();
            *i = g[rng.gen_range(0, g.len())].0 + 1;
        }
    }
}


Measured memory_bytes: 2296
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
using ll = long long;

int main() {
    int n; cin >> n;
    vector<int> idx(n + 1, -1);
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        idx[a] = i;
    }

    set<int> ids;
    ids.insert(-1);
    ids.insert(n);

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int aim = idx[i];
        auto itr = ids.lower_bound(aim);
        int r = *itr;
        int l = *(--itr);
        ans += (ll)i * (aim - l) * (r - aim);
        ids.insert(aim);
    }
    cout << ans << endl;
    return 0;
}

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


int main(){
  int n,x,t;
  cin>>n>>x>>t;
  if(n%x==0) cout<<n/x*t<<endl;
  else cout<<(n/x+1)*t<<endl;
  return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,x,m[100];
	cin>>n>>x;
	for(int i=0;i<n;i++){
		cin>>m[i];
		x-=m[i];
	}
	sort(m,m+n);
	cout<<n+x/m[0]<<endl;
}


Measured memory_bytes: 256
A, B = map(int, input().split())

def gcd(x, y):
    if y== 0:
        return x
    else:
        return gcd(y, x % y)

X = gcd(A, B)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

temp = make_divisors(X)
ans = []
ans.append(temp[0])
if len(temp) >= 2:
    ans.append(temp[1])

for i in range(2, len(temp)):
    for a in ans:
        if gcd(temp[i], a) != 1:
            break
    else:
        ans.append(temp[i])

print(len(ans))

Measured memory_bytes: 3276
#include <bits/stdc++.h>
using namespace std;
#define reep(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) reep((i),0,(n))
int foo2(string s){
    int ret=0;
    stringstream ss;
    ss<<s;
    ss>>ret;
    char t;
    int tt;
    // cout<<s<<endl;
    while(ss>>t){
        ss>>tt;
        if(t=='+'){
            ret+=tt;
        }
        else{
            ret*=tt;
        }
    }
    return ret;
}
int foo1(string s){
    rep(i,s.size()){
        if(s[i]=='*'){
            int l=i-1;
            int r=i+1;
            while(isdigit(s[l])) l--;
            while(isdigit(s[r])) r++;
            l++;
            r--;
            stringstream ss;
            ss<<atoi(s.substr(l,i-l).c_str())*atoi(s.substr(i+1,r-i).c_str());
            string t;
            ss>>t;
            return foo1(s.substr(0,l)+t+s.substr(r+1));
        }
    }
    return foo2(s);
}
int main(){
    string s;
    int a;
    cin>>s>>a;
    // cout<<foo1(s)<<endl;
    // cout<<foo2(s)<<endl;
    bool f1=(a==foo1(s));
    bool f2=(a==foo2(s));
    if(f1&&f2) cout<<"U"<<endl;
    else if(f1) cout<<"M"<<endl;
    else if(f2) cout<<"L"<<endl;
    else  cout<<"I"<<endl;
}

Measured memory_bytes: 1252
function Main(input) {
  // input
  const inputArr = input.split(/\n| /);

  const x = parseInt(inputArr[0], 10);
  const n = parseInt(inputArr[1], 10);

  let pArr = [];
  for (let i = 0; i < n; i++) {
    pArr[i] = parseInt(inputArr[i + 2], 10);
  }

  // process
  const eX = pArr.find((e) => e === x);

  let a;

  if (eX) {
    for (let i = 1; i < 100; i++) {
      const lX = x - i;
      const mX = x + i;

      if (!pArr.find((e) => e === lX)) {
        a = lX;
        break;
      } else if (!pArr.find((e) => e === mX)) {
        a = mX;
        break;
      }
    }
  } else {
    a = x;
  }

  console.log(a);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 29684
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> P;
double eps = 1e-8;
double PI = acos(-1);
double equals(double a, double b){
  return (-eps<a-b&&a-b<eps);
}

double dot(P a,P b){
  return real(b*conj(a));
}
double cross(P a,P b){
  return imag(b*conj(a));
}
struct C{
  P p;
  double r;
  C(){}
  C(P p,double r) : p(p),r(r) {}
};

int ccw( P p, P a, P b ){
  a -= p;
  b -= p;
  if( cross( a, b ) > eps ) return 1; //ue
  if( cross( a, b ) < -eps ) return -1; //shita
  if( dot( a, b ) < -eps ) return 2;
  if( norm(b) - norm(a) > eps ) return -2;
  return 0;
}

int isIntersect(C a,C b){
  double x=a.p.real()-b.p.real();
  double y=a.p.imag()-b.p.imag();
  double s=a.r+b.r;
  double d=x*x+y*y;
  s *= s;
  if( equals(d, s))return 1;
  if(d>s)return 0;
  double r = abs(a.r-b.r);
  r *= r;
  if(equals(d, r))return -1;
  if(d > r)return 2;
  return -2;
}

vector<P> getCrossP(C c1,C c2){
  vector<P> v;
  int cp=isIntersect(c1,c2);
  if(cp==0||cp==-2)return v;
  
  double ll = norm(c1.p-c2.p);
  double A=(c1.r*c1.r-c2.r*c2.r + ll ) / (2.0*ll);
  P base = c2.p - c1.p;
  if(abs(cp)==1){
    v.push_back(c1.p+A*base);
  }else{
    P n(-base.imag(),base.real());
    n /= abs(n);
    double h=sqrt(abs( c1.r*c1.r - A*A*ll ));
    v.push_back(c1.p + A*base + h*n);
    v.push_back(c1.p + A*base - h*n);
  }
  return v;
}

int n;
C t[105];
typedef pair<double,double> Pair;

double solve(int id){
  P op=t[id].p;

  vector<Pair> vec;
  for(int i=0;i<n;i++){
    if(i==id)continue;
    vector<P> k=getCrossP(t[i],t[id]);
    if(k.size()<2)continue;
    P sp=k[0],tp=k[1];
    if( ccw(op, t[i].p, sp) == 1 ){
      swap(sp,tp);
    }
    double sarg=arg(sp-op);
    if(sarg<0)sarg+=2.0*PI;

    double targ=arg(tp-op);
    if(targ<0)targ+=2.0*PI;
    //    if( id == 0 )cout<<sarg/PI<<' '<<targ/PI<<'!'<<endl;

    if(sarg<targ){
      vec.push_back( Pair( sarg,targ  ) );
    }else{
      vec.push_back( Pair( 0 , targ ) );
      vec.push_back( Pair( sarg , 2.0*PI ) );
    }

  }
  sort(vec.begin(),vec.end());
  int size=vec.size();
  double sum=0;
  for(int i=0;i<size;i++){
    Pair e=vec[i];
    if(i+1==size ||  e.second < vec[i+1].first){
      sum+=(e.second-e.first);
    }else{
      vec[i+1].first=min(vec[i+1].first, e.first);
      vec[i+1].second=max(vec[i+1].second, e.second);
    }
  }

  return (2.0*PI-sum)*t[id].r;
}

int main(){
  while(1){
    cin>>n;
    if(n==0)break;
    for(int i=0;i<n;i++){
      double x,y,r;
      cin>>x>>y>>r;
      t[i]=C( P(x,y) , r );

      for(int j=0;j<i;j++){
        assert( t[i].r!=t[j].r || t[i].p!=t[j].p);
      }
    }
    
    double ans=0;
    for(int i=0;i<n;i++){
      bool flg=false;
      for(int j=0;j<n;j++){
        if(i==j)continue;
        if( isIntersect(t[i],t[j]) < 0 && t[i].r < t[j].r){
          flg=true;
        }
      }
      if(flg)continue;
      ans+=solve(i);
    }
    printf("%.10f\n",ans);
  }  
  return 0;
}

Measured memory_bytes: 1328