akhauriyash/Code-Regression huggingface dataset:
//! ----------------------------------------------
//! Framework <https://github.com/vain0x/procon>
//!
//! See the bottom of file for solution.
//! ----------------------------------------------

#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Display, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

/// Print values to standard error if debug mode.
#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), stderr());
            writeln!(err, "\x1B[33m{}\x1B[0m = {:?}", e, $e).unwrap()
        })*
    };
}

/// Read from standard input and parse each word.
/// - `read!(T, U, ..)` parses a line as a tuple of words.
/// - `read![[T]]` parses a line as an array of words.
/// - `read![..; N]` parses `N` lines, using `read!(..)` repeatedly.
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

/// Read a line from standard input.
#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();

    #[allow(deprecated)]
    buf.trim_right().to_owned()
}

// -----------------------------------------------
// Solution
// -----------------------------------------------

fn sq(x: usize) -> i64 {
    (x * x) as i64
}

fn main() {
    let (N, K) = read!(usize, usize);
    let mut T = read![usize, i64; N];

    T.sort_by_key(|&(_, d)| -d);

    let mut dup = vec![];
    let mut kind = BTreeSet::new();
    let mut sum = 0;

    for i in 0..K {
        let (t, d) = T[i];
        if !kind.insert(t) {
            dup.push(d);
        }
        sum += d;
    }

    debug!(sum, dup, kind);

    let mut max_score = sum + sq(kind.len());

    for i in K..N {
        let (t, d) = T[i];
        if !kind.insert(t) {
            debug!((t, d), "skip");
            continue;
        }

        if let Some(vomit) = dup.pop() {
            debug!((t, d, vomit));
            sum += d - vomit;
            max_score = max(max_score, sum + sq(kind.len()));
            debug!((sum, max_score));
        } else {
            break;
        }
    }

    println!("{}", max_score)
}


Measured memory_bytes: 8444
import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)
ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur] 
      dfs(chl, cur)
dfs(0, -1)
print(*ans)

Measured memory_bytes: 230932
#include<bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define FORR(i,a,b) for (int i = b - 1; i >= a; --i)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) FORR(i,0,n)

int N, i;

int main() {
  scanf("%d%d", &N, &i);
  printf("%d\n", N - i + 1);
  return 0;
}


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

int main() {
  int apple = 0;
  int piece = 0;
  int pieceSum = 0;
  int result = 0;
  cin >> apple >> piece;
  pieceSum = apple * 3 + piece;
  result = pieceSum / 2;
  cout << result;
  
  return 0;
}

Measured memory_bytes: 256
s=input()[::-1]
a=["dreamer"[::-1],"eraser"[::-1],"dream"[::-1],"erase"[::-1]]
st=1
en=0
while st>en:
  st=len(s)
  for m in a:
    
    if s.find(m)==0:
      s=s[len(m):]
    
  en=len(s)
  
print("YES" if s=="" else "NO")

Measured memory_bytes: 9148
# abc127_b.py
# https://atcoder.jp/contests/abc127/tasks/abc127_b

# B - Algae /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 200点

# 問題文
# ある池に生えている藻類は、以下のように成長します。
# 西暦 i年になる瞬間に生えている重さの合計を xi グラムとすると、 i≥2000に対して、以下の式が成り立ちます:
#     xi+1=rxi−D
#     r, D, x2000 が与えられます。x2001, ..., x2010を計算し、順に出力してください。

# 制約
#     2≤r≤5
#     1≤D≤100
#     D<x2000≤200
#     入力はすべて整数

# 入力
# 入力は以下の形式で標準入力から与えられる。
# r D x2000

# 出力
# 10行出力せよ。i 行目 (1≤i≤10) には x2000+iを整数で出力せよ。

# 入力例 1
# 2 10 20

# 出力例 1
# 30
# 50
# 90
# 170
# 330
# 650
# 1290
# 2570
# 5130
# 10250

# 例えば、x2001=rx2000−D=2×20−10=30、 x2002=rx2001−D=2×30−10=50です。

# 入力例 2
# 4 40 60

# 出力例 2
# 200
# 760
# 3000
# 11960
# 47800
# 191160
# 764600
# 3058360
# 12233400
# 48933560


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    r, D, x = list(map(int, lines[0].split()))
    # values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(6):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(Q):
    #     valueses.append(list(map(int, lines[i+1].split())))

    results = list()

    for i in range(10):
        result = r * x - D
        results.append(result)
        x = result

    return results


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['2 10 20']
        lines_export = [30, 50, 90, 170, 330, 650, 1290, 2570, 5130, 10250]
    if pattern == 2:
        lines_input = ['4 40 60']
        lines_export = [200, 760, 3000, 11960, 47800, 191160, 764600, 3058360, 12233400, 48933560]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(1)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9276
n = int(raw_input())
S = map(int, raw_input().strip().split(' '))
q = int(raw_input())
T = map(int, raw_input().strip().split(' '))

def binary_search(S,k):
    left = 0
    right = len(S) - 1
    while left <= right:
        mid = (left+right)/2
        if S[mid] == k: return True
        elif S[mid] > k:
            right = mid-1
        else:
            left = mid+1

c = 0
for t in T:
    if binary_search(S,t): c += 1
print c

Measured memory_bytes: 14908
#include<iostream>
 
using namespace std;
int main()
 
{
int a,b,c,d;
cin>>a>>b>>c>>d;
 
 
if(a*b>c*d){
    cout<<a*b<<endl;
}
 
else if(c*d>a*b){
    cout<<c*d<<endl;
}
 
else {
    cout<<a*b<<endl;
}
 
 
return 0;
 
}

Measured memory_bytes: 256
using DataStructures
const double = Float64
const int = Int64

parseint(x) = parse(int, x)
readint() = map(parseint, split(readline()))

function main()
  H,W = readint()
  S = String[]
  for _ in 1:H
    s = readline()
    append!(S,[s])
  end

  Lmax = H*W + 1
  d = Array{int,4}(undef, H,W,H,W)
  d .= H*W + 1

  mat = Array{int,4}(undef,H,W,H,W)
  mat .= 0

  for i in 1:H, j in 1:W
    S[i][j] == '#' && continue
    

    if i+1 <=H && S[i+1][j] == '.'
      mat[i,j,i+1,j] = 1
      mat[i+1,j,i,j] = 1
    end
    if j+1 <= W &&S[i][j+1] == '.'
      mat[i,j,i,j+1] = 1
      mat[i,j+1,i,j] = 1
    end
  end

  for i1 in 1:H, j1 in 1:W
    for i2 in 1:H, j2 in 1:W
      i1 == i2 && j1 == j2 && (d[i1,j1,i2,j2]=0)
      if mat[i1,j1, i2, j2] == 1
        d[i1,j1,i2,j2] = 1
      end
    end
  end
  for i1 in 1:H, j1 in 1:W
    for i2 in 1:H, j2 in 1:W
      for i3 in 1:H, j3 in 1:W
        d[i2,j2,i3,j3] = min(d[i2,j2,i3,j3] , d[i2,j2,i1,j1] + d[i3,j3,i1,j1])
      end
    end
  end

  s = 0
  for i in 1:H, j in 1:W
    for i2 in 1:H, j2 in 1:W
      if d[i,j,i2,j2] > s && d[i,j,i2,j2]<Lmax
        s = d[i,j,i2,j2]
      end
    end
  end
  println(s)
  #println(S[2][4])
  #println(S)
end



main()

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

int main (){
  int A,B,C,X;
  cin >> A >> B >> C >>X;
  //int n = x/50;
  
  int cnt =0;
//input
  for(int i =0;i<=A;i++){
   for(int j=0;j<=B;j++){
     for(int k=0;k<=C;k++){
       if(500*i+100*j+50*k ==X)cnt++;
     }
   }
  }
  
  cout <<cnt<<endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdlib>
#include <cmath> 
using ll = long long;
using namespace std;
 
int main() {
  ll W;cin>>W;
  ll H;cin>>H;
  ll x;cin>>x;
  ll y;cin>>y;
  double ans;ans=(W*H);
  ans=ans/2;
  cout<<ans<<" ";
  if(x+x==W&&y+y==H){
    cout<<1<<endl;
  }else{
    cout<<0<<endl;
  }
 
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>

#define INF 100000

using namespace std;

int cntstr(string s1,string s2){
  int cnt = 0;
  for(int i=0;i < s1.size();i++){
    if(s1[i] != s2[i]) cnt++;
  }
  return cnt;
}

int main(){
  string s,t,sub;
  cin >> s >> t;
  int ans = INF;
  
    for(int i=0;i < s.size()-t.size()+1;i++){
      //for(int j=i;j < t.size();j++){
        //if(s[i+j] == t[j]){
          sub = s.substr(i,t.size());
          ans = min(ans,cntstr(sub,t));
        //}
    //}
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3616
N = int(input())

a_li = list(map(int, input().split()))

num_0, num_2, num_4 = 0, 0, 0

for i in a_li:
    if i % 4 == 0:
        num_4 += 1
    elif i % 2 == 0:
        num_2 += 1
    else:
        num_0 += 1

if num_0 <= num_4 or (num_0 == num_4 + 1 and num_2 == 0):
    print("Yes")
else:
    print("No")


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

int main(){
    int n, a, x, y, count = 0, max = 0;

    cin >> n;
    vector<vector<pair<int,bool>>> A(n);

    for(int i=0;i<n;i++){
        cin >> a;
        for(int j=0;j<a;j++){
            cin >> x >> y;
            A[i].push_back(make_pair(x, y));
        }
    }
    for(int i=0; i<(1<<n);i++){
        bool flag = true;
        count = 0;
        //cout << i << endl;
        for(int j=0;j<n;j++){
            int check = i&(1<<j);
            if(check){
                for(auto iter = A[j].begin();iter!=A[j].end();iter++){
                    //int check2 = (i>>(iter->first-1))&1;
                    //cout << iter->first << " " << check << endl;
                    if( ((i>>(iter->first-1))&1) != iter->second ){
                        flag = false;
                        //cout << "false" << endl;
                    }  
                }
            }
        }
        if(flag){
            for(int k=0;k<n;k++){
                if(i & (1<<k)){
                    count++;
                }
            }
            if(max<count){
                max=count;
            }
        }
    }

    cout << max << endl;
    return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <set>
using namespace std;
const int MAXN = 105;
int standard[] = {2, 4, 14, 24, 74};
int cnt[MAXN], tot[5];
int main(void)
{
    memset(cnt, 0, sizeof(cnt));

    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; i++)
    {
        int temp = i;
        for(int j = 2; j <= i; j++)
        {
            while(temp % j == 0)
            {
                cnt[j]++;
                temp /= j;
            }
        }
    }

    for(int i = 1; i <= 100; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            if(cnt[i] >= standard[j])
                ++tot[j];
        }
    }

    long long answer = 0;


    answer += max(0, tot[1]) * max(0, tot[1] - 1) * max(0, tot[0] - 2) / 2;
    answer += max(0, tot[3]) * max(0, tot[0] - 1);
    answer += max(0, tot[2]) * max(0, tot[1] - 1);
    answer += max(0, tot[4]);

    printf("%lld\n", answer);

    return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::*;
use std::str::FromStr;

#[allow(unused_macros)]
macro_rules! debug {($($a:expr),*) => {println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);}}
#[allow(unused_macros)]
macro_rules! input {(source=$s:expr,$($r:tt)*) => {let mut iter=$s.split_whitespace(); let mut next=||{iter.next().unwrap()}; input_inner! {next,$($r)*}};($($r:tt)*) => {let stdin=std::io::stdin();let mut bytes=std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next=move||->String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()}; input_inner! {next,$($r)*}};}
#[allow(unused_macros)]
macro_rules! input_inner {($next:expr) => {}; ($next:expr,) => {}; ($next:expr,$var:ident:$t:tt$($r:tt)*) => {let $var=read_value!($next,$t); input_inner! {$next$($r)*}};}
#[allow(unused_macros)]
macro_rules! read_value {($next:expr,($($t:tt),*)) => {($(read_value! ($next,$t)),*)}; ($next:expr, [$t:tt; $len:expr]) => {(0..$len).map(|_|read_value! ($next,$t)).collect::<Vec<_>>()}; ($next:expr,chars) => {read_value! ($next,String).chars().collect::<Vec<char>>()}; ($next:expr,usize1) => {read_value! ($next,usize)-1}; ($next:expr,$t:ty) => {$next().parse::<$t>().expect("Parse error")};}

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);
impl<T: PartialEq> Eq for Total<T> {}
impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

#[allow(dead_code)]
const MAX: usize = 100006;
#[allow(dead_code)]
const INF_U32: u32 = 1 << 31;
#[allow(dead_code)]
const INF_I32: i32 = 1 << 30;
#[allow(dead_code)]
const INF_U64: u64 = 1 << 63;
#[allow(dead_code)]
const INF_I64: i64 = 1 << 62;
#[allow(dead_code)]
const MOD: i64 = 1e9 as i64 + 7;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(unused_imports)]
use std::f64;


fn main() {
    input!{n:usize, a:[i64;n]};
    let mut map = HashMap::new();

    for el in a {
        let count = map.entry(el).or_insert(0i64);
        *count += 1;
    }
    let mut ans = 0i64;
    for (k,v) in map {
        ans += if v < k {v} else {v-k};
    }
    println!("{}", ans);

}


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

using namespace std;

const int N = 105, MAX_W = 1e5 + 5;
const long long inf = 1e18 + 123;
int n, W;
long long dp[2][MAX_W];

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

    for (int i = 0; i < MAX_W; ++i) dp[0][i] = dp[1][i] = inf; dp[1][0] = 0;
    for (int i = 1; i <= n; ++i) {
        int w, v; scanf("%d %d", &w, &v);
        int lst = i & 1, nxt = lst ^ 1;
        for (int j = 0; j < MAX_W; ++j) {
            dp[nxt][j] = dp[lst][j];
            if (j >= v) dp[nxt][j] = min(dp[nxt][j], dp[lst][j - v] + w);
        }
    }

    long long ans = 0;
    for (int i = 0; i < MAX_W; ++i) if (dp[n & 1 ^ 1][i] <= W) ans = i;

    cout << ans;

    return 0;
}


Measured memory_bytes: 1792
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.sise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
//const ll INF = 1LL << 60;
//typedef pair<ll,ll> P;
typedef pair<int, int> P;
bool chmx(int &a, int b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

bool chmn(int &a, int b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

int main(){
    int a,b,c,d;
    cin >> a>>b>>c>>d;
    int T=(c-1)/b+1;
    int A=(a-1)/d+1;
    if(A>=T){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}



Measured memory_bytes: 3604
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>

// Remove GCC optimizer for codechef
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define endl "\n"
#define int long long
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int INF = 3e18 + 8;
const double PI = acos(-1);
const int N = 1e6 + 7;
int mod = 1e9;

const int maxn = 1e5 + 7;

int32_t main()
{
    IOS;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int n, m;
    cin >> n >> m;
    int sum = 0;
    for(int i = 1; i <= m; i++)
    {
        int a;
        cin >> a;
        sum += a;
    }
    if(sum > n)
        cout << -1;
    else
        cout << (n - sum);
    
    return 0;
}


Measured memory_bytes: 3644
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <stack>
#define N_MAX 500000
#define INFTY 2000000000//Sの要素の最大値が10^9なのでそれより大きく設定
using namespace std;
//常に心してかかれ
//簡単なことを簡単にできるように練習する
//びっくりするくらいつまらないことで詰まってることも多い

int n;
int S[N_MAX+1];
int n_cmpr=0;//比較回数

//すでに整列済みの二つの数列からそれらを合わせた数列を整列させる関数
void merge(int A[],int left,int mid,int right){int n1,n2;
	
	n1 = mid -left;
	n2 = right - mid;
	//n2-n1=right-left

	int L[N_MAX];//n1
	int R[N_MAX];//n2

	for(int i=0;i<n1;i++){
		L[i] = A[left + i];
	}

	for(int i=0;i<n2;i++){
		R[i] = A[mid + i];
	}

	L[n1] = INFTY;
	R[n2] = INFTY;

	int i_L=0;
	int i_R=0;
	for(int k=left;k < right;k++){//整列後の数列のk番目の値を決める
		if(L[i_L] <= R[i_R]){
			A[k] = L[i_L];//昇順なので小さい方が採用される
			i_L++;
		}else{
			A[k] = R[i_R];//昇順なので小さい方が採用される
			i_R++;
		}
		n_cmpr++;
	}
}

//0オリジンでleftは最初の添え字，rightは最後の添え字+1
void mergeSort(int A[],int left,int right){
	int mid;
	if(left+1 < right){
		mid = (left + right)/2;
		mergeSort(A,left,mid);
		mergeSort(A,mid,right);
		merge(A,left,mid,right);
	}
}

int main(){
	scanf("%d",&n);

	//確認用
	//printf("%d\n",n);
	
	for(int i=0;i<n;i++){
		scanf("%d",&S[i]);

		//確認用
		//printf("%d ",S[i]);
	}

	mergeSort(S,0,n);

	printf("%d",S[0]);//Presentation error対策
	for(int i=1;i<n;i++){
		printf(" %d",S[i]);
	}
	printf("\n");
	printf("%d\n",n_cmpr);

	return 0;
}

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

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

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

const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

ll llfloor(ll a, ll b) {
    if (a < 0) {
        return (a-b+1)/b;
    } else {
        return a/b;
    }
}

ll llceil(ll a, ll b) {
    if (a >= 0) {
        return (a+b-1)/b;
    } else {
        return a/b;
    }
}


int main() {
    ll n, k; cin >> n >> k;
    vector<ll> a(n); rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());

    ll r = 1e18 + 1;
    ll l = -1e18 - 1;
    ll mid;
    while (r-l>1) {
        mid = (r+l) / 2;
        ll cnt = 0;
        rep(i, n) {
            if (a[i] > 0) {
                cnt += upper_bound(a.begin(), a.begin()+i, llfloor(mid, a[i])) - a.begin();
            } else if (a[i] == 0) {
                if (mid >= 0) cnt += i;
            } else {
                cnt += a.begin()+i - lower_bound(a.begin(), a.begin()+i, llceil(-mid, -a[i]));
            }
        }
        if (cnt < k) l = mid;
        else r = mid;
    }
    
    cout << r << endl;



    return 0;
}


    


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<math.h>
#include <stdio.h>
#include<vector>
#include<deque>
#include<stdlib.h>
//#include <algorithm>
#include <limits>
#include<string>
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
#define llMAX numeric_limits<long long>::max()
#define intMAX numeric_limits<int>::max()
#define ll long long
#define d_5 100000
struct edge{
  struct treev* to;
  ll length;
};
struct treev{
  ll num;
  vector<edge> nexts;
};
struct input{
  int u;
  int v;
  ll w;
};
  treev* root1=NULL;
  treev* root2=NULL;
bool cmp(const input &a, const input &b)//ソート用
{
  if(a.u!=b.u){
    return a.u<b.u;
  }else{
    return a.v<b.v;

  }
}
int* result;
vector<treev*> vs;
treev* createtreenode(ll num){
  treev* newt=new treev;
  if(newt==NULL){
    cout << "memory error" << endl;
    while(1){
      num=1;//メモリエラー対策
    }
  }
  newt->num=num;
  newt->nexts={};
  //cout << "fff" << endl;
  return newt;
}
void insertree(ll len,ll Va,ll Vb){//結ぶ頂点を
  vs[Va]->nexts.push_back({vs[Vb],len});
  vs[Vb]->nexts.push_back({vs[Va],len});
  return;
}
int* score1;
int* score2;
void search1(treev* root,ll depth,treev* pre){
  score1[root->num]=depth;
  //cout << "eee" << endl;
  for(auto i:root->nexts){
    if(pre==i.to){
      continue;
    }
    search1(i.to,depth+i.length,root);
  }
  return;
}
void search2(treev* root,ll depth,treev* pre){
  score2[root->num]=depth;
  //cout << "eee" << endl;
  for(auto i:root->nexts){
    if(pre==i.to){
      continue;
    }
    search2(i.to,depth+i.length,root);
  }
  return;
}
int main(void){
  ll N;
  cin >> N;
  ll tw ;
  ll tu;
  ll tv;
  rep(i,N){
    vs.push_back(createtreenode(i));
  }
  root1=vs[0];//根の位置 fennec
  root2=vs[N-1];//根の位置
  score1 = (int*)malloc(sizeof(int)*N);
  score2 = (int*)malloc(sizeof(int)*N);
  rep(i,N-1){
    cin >> tu >> tv;
    tu--;tv--;
    insertree(1,tu,tv);
  }
  //cout << "e";
  search1(root1,0,NULL);
  search2(root2,0,NULL);
  int fc =0;
  int sc =0;
  rep(i,N){
    if(score1[i]<=score2[i]){
      fc++;
    }else{
      sc++;
    }
  }
  //cout << fc << " " << sc << endl;
  if(fc>sc){
    cout << "Fennec" << endl;
  }else{
    cout << "Snuke" << endl;
  }
	return 0;
}

Measured memory_bytes: 15860
#include <bits/stdc++.h>
using namespace std;
//make_tuple emplace_back next_permutation push_back make_pair second first setprecision

#if MYDEBUG
#include "lib/cp_debug.h"
#else
#define DBG(...) ;
#endif

using LL = long long;
constexpr LL LINF=334ll<<53;
constexpr int INF=15<<26;
constexpr LL  MOD=1E9+7;

struct Problem{
    int n;
    vector<LL> a,sum;
    Problem(LL n):n(n),a(n+1),sum(n+1){};

    void solve(){
        for(int i=1; i<=n; ++i){
            cin >>a[i];
        }
        sort(a.begin(),a.end());
        for(int i=1; i<=n; ++i){
            sum[i]=sum[i-1]+a[i];
        }
        int pos=n-1;
        for(;;--pos){
            if(sum[pos]*2<a[pos+1])break;
        }
        cout << n-pos <<"\n";
    }
};

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    long long n=0;
    cin >> n;
    Problem p(n);
    p.solve();
    return 0;
}



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

int main() {
    int n;
    cin >> n;
    vector<int> array;
    long long int sum = 0;
    for(int i = 0; i < n; i++) {
        int num;
        cin >> num;
        sum += num;
        array.push_back(num);
    }
    sort(array.begin(), array.end());
    cout << array[0] << " " << array[n-1] << " " << sum << endl;

}


Measured memory_bytes: 3268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
const ll INF = 1LL<<60;
const ll M = 1000000007;
ll mpow(ll a,ll b){ll res=1;while(b!=0){if(b&1)res=res*a%M;a=a*a%M;b=b>>1;}return res;}
ll mcomb(ll n,ll k){if(k>n/2)return mcomb(n,n-k);ll res=1;for(ll i=0;i<k;i++){res=res*(n-i)%M;res=res*mpow(k-i,M-2)%M;}return res;}
/*template*/

int main()
{
  ll a,b;cin>>a>>b;
  ll ans;
  if(a+b==3)ans=3;
  if(a+b==4)ans=2;
  if(a+b==5)ans=1;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
program main
	implicit none
    integer::a,b,c
    read(*,*) a,b,c
    if(a==b .and. a/=c)then
    	write(*,*) 'Yes'
    else if(a==c .and. a/=b)then
    	write(*,*) 'Yes'
    else if(b==c .and. b/=a)then
    	write(*,*) 'Yes'
    else
    	write(*,*)'No'
    end if
    stop
end program main

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

int main()
{
  int t;
  cin >> t;
  
  uint64_t a = 2LL;
  uint64_t b = 1LL;
  uint64_t tmp = 0LL;
  
  for(int i = 2; i <= t; i++){
    tmp = a + b;
    a = b;
    b = tmp;
  }
   cout << b << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long int
#define pb push_back
#define mp make_pair
#define ld long double
#define sz(a) (ll)(a).size()

typedef tree<pair<ll,ll> ,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//K-th smallest
//cout << k << "kth smallest: " << *A.find_by_order(k-1) << endl;
//NO OF ELEMENTS < X
//cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;

const int MAXN = 3005;

ll n;
ld a[MAXN], dp[MAXN][MAXN], res = 0.00;                 // Probability of getting exactly val heads from coins of indices ind to n

ld rec(ll ind, ll val)
{
	if(val < 0 || (ind == n && val != 0)) return 0;
	if(ind == n && val == 0) return 1;
	if(dp[ind][val] != -1) return dp[ind][val];
	ld ans = 0;
	if(val > 0)
		ans = (ans + a[ind] * rec(ind + 1, val - 1));
	ans = (ans + (1.00 - a[ind]) * rec(ind + 1, val));
	return dp[ind][val] = ans;
}

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

    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    memset(dp, -1, sizeof(dp));
	ll temp = n / 2 + 1;
	for(int i=temp;i<=n;i++) res = res + rec(0, i);
	printf("%.10Lf\n", res);
    return 0;
}

Measured memory_bytes: 141568
N = input()
for x in range(int(N)):
    B = map(int, input().split())
    a = b = 0
    for y in B:
        if y > a:
            a = y
        elif y > b:
            b = y
        else:
            print('NO')
            a = -1
            break
        if a < b:
            a, b = b, a
    if a == -1:
        continue
    else:
        print('YES')

Measured memory_bytes: 7660
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        int[] inpt = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();

        string ans = "No";
        if(inpt[0]<=inpt[2]&&inpt[2]<=inpt[1]) {
            ans = "Yes";
        }
        Console.WriteLine(ans);



    }




	public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"


1 3 2



";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}


Measured memory_bytes: 13396
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using std::cin;
using std::string;

int main(){
  long int x;
  cin >> x;
  long int money=100;
  for(long int i=1;;i++){
    money*=1.01;
    if(x<=money){
      cout << i << endl;
      break;
    }
  }
}


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

int main()
{
  std::string S; std::cin >> S;
  int K; std::cin >> K;

  std::set<std::string> res{};
  for(int i = 0; i < S.size(); ++i){
    for(int len = 1; len <= K; ++len){
      if(i + len > S.size())
        break;
      auto t = S.substr(i, len);
      res.emplace(std::move(t));
    }
  }
  while(--K){
    res.erase(res.begin());
  }
  std::cout << *res.begin() << std::endl;
  return 0;
}


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

int main()
{
	int kal[200];
	int kal_per_dollar[200];
	int N, A, B, C;
	
	scanf("%d %d %d %d", &N, &A, &B, &C);
	for (int i = 0; i < N; i++){
		scanf("%d", &kal[i]);
	}
	
	sort(kal, kal + N);
	reverse(kal, kal + N);
	
	for (int i = 0, sum = C; i < N; i++){
		sum += kal[i];
		kal_per_dollar[i] = sum / (A + B * (i + 1));
//		printf("%d\n", kal_per_dollar[i]);
	}
	
	sort(kal_per_dollar, kal_per_dollar + N);
	reverse(kal_per_dollar, kal_per_dollar + N);
	
	if (C / A > kal_per_dollar[0]){
		printf("%d\n", C / A);
	}
	else {
		printf("%d\n", kal_per_dollar[0]);
	}
	
	return (0);
}

Measured memory_bytes: 1040
x,n=map(int,input().split())
Ps=list(map(int,input().split()))
Ps.sort()

table=[0]*102

for i in Ps:
    table[i]=1

ans=0
min=101
for i in range(0,102):
   if table[i]==0:
       temp=abs(x-i)
       if temp<min:
           min=temp
           ans=i

print(ans)






Measured memory_bytes: 9192
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

const int mod = 998244353;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x=0):x((x%mod+mod)%mod){}
	mint operator-() const { return mint(-x);}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
	mint operator+(const mint a) const { return mint(*this) += a;}
	mint operator-(const mint a) const { return mint(*this) -= a;}
	mint operator*(const mint a) const { return mint(*this) *= a;}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if (t&1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const { return pow(mod-2);}
	mint& operator/=(const mint a) { return *this *= a.inv();}
	mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

static mint m[3001][3001];

int main(){
	int a, b, c, d;
	cin>>a>>b>>c>>d;
	int e=min(c-a, d-b);
	for(int i=a; i<=c; i++){
		for(int j=b; j<=d; j++){
			if(i==a && j==b) m[i][j]=1;
			else if(i==a) m[i][j]=m[i][j-1]*i;
			else if(j==b) m[i][j]=m[i-1][j]*j;
			else{
				m[i][j]=m[i-1][j-1]*((mint)(i-1)*(j-1)+(i-1)+(j-1));
				m[i][j]+=(m[i-1][j]-m[i-1][j-1]*(i-1))*j;
				m[i][j]+=(m[i][j-1]-m[i-1][j-1]*(j-1))*i;
			}
		}
	}
	cout<<m[c][d]<<endl;
	return 0;
}


Measured memory_bytes: 73944
use text_io::*;

fn main() {
    let a: isize = read!();
    let b: isize = read!();
    let c: isize = read!();
    let k: isize = read!();
    
    let ans = if a + b >= k { k.min(a) } else { a - (k - a - b) };
    println!("{}", ans);
}




Measured memory_bytes: 2172
#include <stdio.h>
#include <math.h>
int main(){
  int a[3],K,sum,max=0;
  scanf("%d %d %d",&a[0],&a[1],&a[2]);
  scanf("%d",&K);
  sum=a[0]+a[1]+a[2];
  for(int i=0;i<3;i++){
    if(a[i]>max){
      max=a[i];
    }
  }
  sum=sum+pow(2,K)*max-max;
  printf("%d",sum);
  return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;


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

	string s;
	cin >> s;

	for(int i=0; i<s.size(); i++){
		char c = s[i];
		if((i % 2) == 0){
			printf("%c", c);
		}
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 3696
#include <iostream>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <iomanip>
#include <cstdio>
#include <new>
#include <vector>
#include <cstdlib>
#include <string>
#include <set>
#include <tuple>
#include<map>
#include<queue>

using namespace std;


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

	cout << int64_t( pow((K - 1), (N - 1)) * K) << endl;;
}

Measured memory_bytes: 4060
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-9;
const long double INF=1e+10;
const long double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	inline long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		// if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
int p[110];
long long dp[52][110][110];
int main(){
	long long a,b;
	scanf("%lld%lld",&a,&b);
	a%=b;
	printf("%lld\n",min(a,b-a));
}

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

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	string s;
	cin >> s;
	int n = s.length();
	int ans[n] = {};
	int curo = 0, cure = 0;
	for(int i = 0;i < s.length(); ++i){
		if(s[i] == 'R'){
			++cure;
		}
		else{
			ans[i-1] += curo;
			ans[i] += cure;
			curo = 0;
			cure = 0;
		}
		swap(curo,cure);
	}
	for(int i = n-1;i >= 0; --i){
		if(s[i] == 'L'){
			++cure;
		}
		else{
			ans[i] += cure;
			ans[i+1] += curo;
			curo = 0;
			cure = 0;
		}
		swap(curo,cure);
	}
	for(int i = 0;i < n; ++i){
		cout << ans[i] << ' ';
	}
	cout << '\n';
}


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

using namespace std;

int main()
{
    int n, k;
    string s;
    cin >> n >> s >> k;

    for (size_t i = 0; i < n; i++)
    {
        if (s[i] != s[k - 1])
        {
            s[i] = '*';
        }
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
import math
l = [int(input()) for _ in range(5)]
l_1st = [int(str(10 - int(str(i)[-1]))[-1]) for i in l]
l_rm_i = l_1st.index(max(l_1st))
l_rm = l[l_rm_i]
del l[l_rm_i]

l = [math.ceil(i/10)*10 for i in l]
ans = int((sum(l) + l_rm))
print(ans)

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

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

    if(n){
      int a[10000];
      int b[10000];

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

      int ap=0,bp=0;
      
      for(int i=0;i<n;i++){
		if(a[i]>b[i]){ap+=a[i]+b[i];}
		else if(a[i]<b[i]){bp+=a[i]+b[i];}
		else{ap+=a[i];bp+=b[i];}
      }
      
      cout<<ap<<" "<<bp<<endl;
    }
    else{break;}
  }
  return 0;
}

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

int main(int argc, char const *argv[]) {
    int n, x;
    cin >> n >> x;
    vector<int> l(n);
    for (size_t i = 0; i < n; i++) cin >> l[i];

    int ans = 0;
    int d = 0;
    for (size_t i = 0; i < n; i++) {
        if (d <= x) ans++;
        d += l[i];
    }
    if (d <= x) ans++;

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


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll n; cin >> n;
    vll a(n);
    vll v(n + 10, 0);
    rep(i, n) {
        ll j; cin >> j;
        a[i] = j;
        v[j]++;
    }

    ll total = 0;
    rep(i, n + 10) {
        total += v[i] * (v[i] - 1) / 2;
    }

    rep(i, n) {
        ll _total = total - v[a[i]] * (v[a[i]] - 1) / 2;
        _total += (v[a[i]] - 1) * (v[a[i]] - 2) / 2;
        cout << _total << endl;
    }
    return 0;
}

Measured memory_bytes: 5760
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def ints(): return list(map(int, readline().split()))


def read_map_as(H, replace={'#': 1, '.': 0}, pad=None):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            # 内包表記はpypyでは若干遅いことに注意
            # #numpy使うだろうからこれを残しておくけど
    else:  # paddingする
        ret = [[pad] * (W + 2)]  # Wはどっかで定義しておくことに注意
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7

import numpy as np
H, W = ints()
A = np.array(read_map_as(H))


from numba import njit


@njit('(i8,i8,i8[:,:])', cache=True)
def solve(H, W, A):
    dp = np.zeros((H, W), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(H):
        for j in range(W):
            if A[i, j] == 1:
                dp[i, j] = 0
                continue
            if i > 0:
                dp[i, j] += dp[i - 1, j]
            if j > 0:
                dp[i, j] += dp[i, j - 1]
            dp[i, j] %= MOD
    print(dp[H - 1, W - 1])


solve(H, W, A)


Measured memory_bytes: 127628
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n , k, q;
    cin>>n>>k>>q;
    ll* a = new ll[n]();
    for(int i=0;i<q;i++)
    {
        int temp ;
        cin>>temp;
        temp--;
        a[temp] ++;
    }

    for(int i=0;i<n;i++)
    {
        if( a[i] + k -q >0   )
            cout<<"Yes\n";
        else cout<<"No\n";
    }
}

Measured memory_bytes: 4412
#include<iostream>
#include<string>
using namespace std;
int main() {
	string str, search;
	int n, count = 0, check = 0;
	cin >> search;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str;
		str = str + str;
		check = str.find(search);
		if (check != -1) {
			count++;
		}
	}
	cout << count << endl;
}

Measured memory_bytes: 3176
#include<stdio.h>
#include<stdlib.h>
#define roop(i,n) for(int i = 0;i < n;i++)


int main(void){

	int n;
	double *list, temp, sum = 0.0;

	scanf("%d",&n);

	list = malloc(sizeof(double *) * n);

	roop(i,n){
		scanf("%lf", list + i);
	}

	//ソート
	roop(i,n){
		roop(j,n-1){
			if(list[i] <= list[j]){
				temp = list[i];
				list[i] = list[j];
				list[j] = temp;
			}
		}
	}


	roop(i, n){
		if(i == 0){
			sum = (list[0] + list[1])/2;
		}else if(i == 1){
		}else{
			sum = (sum+list[i])/2;
		}
	}

	printf("%lf", sum);

	return 0;
}


Measured memory_bytes: 128
#include<stdio.h>

int main()
{
    int s,p,q,r,a,b;
    scanf("%d %d %d",&p,&q,&r);
    if(p<q)
    {
        a=p;
        b=q;
    }
    else
    {
       b=p;
        a=q;
    }
    if(r<b)
        b=r;
    else
        b=b;
    s=a+b;
    printf("%d",s);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <iomanip>
#include <set>
#include <sstream>
#include <queue>
using namespace std;
typedef long long ll;

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

  vector<int> l(m);
  vector<int> r(m);

  for (int i = 0; i < m; i++) {
    cin >> l[i] >> r[i];
  }
  int max_l = 1;
  int min_r = n;
  for (int i = 0; i < m; i++) {
    max_l = max(max_l, l[i]);
    min_r = min(min_r, r[i]);
  }

  int ans = min_r - max_l + 1;
  ans = max(ans, 0);

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

Measured memory_bytes: 3676
n = int(input())
a = list(map(int, input().split()))
a_sum = [0]
a_ = 0
for i in range(n):
    a_ = a_ + a[i]
    a_sum.append(a_)
count = {}
for i in range(n + 1):
    if a_sum[i] not in count:
        count[a_sum[i]] = 1
    else:
        count[a_sum[i]] = count[a_sum[i]] + 1
count2 = 0
for i in count:
    count2 = count2 + int(count[i] * (count[i] - 1) / 2)
print(count2)

Measured memory_bytes: 41460
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}



int main(void) {
    FAST_IO;
    
    ll h, w;

    cin >> h >> w;
    
    if (h == 1 || w == 1) {
        cout << 1 << endl;
    } else {
        cout << h * w / 2 + h * w % 2 << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}


bool TopologicalSort(vector<vector<pair<int,int>>> &graph, vector<int> &sorted){
	vector<int> count(graph.size());
	stack<int> currentNode;
	
	for(int i = 0; i < graph.size(); i++){
		for(pair<int,int> next : graph[i]){
			count[next.first]++;
		}
	}
	
	for(int i = 0; i < graph.size(); i++){
		if(!count[i]){
			currentNode.push(i);
		}
	}
	
	while(!currentNode.empty()){
		int node = currentNode.top(); currentNode.pop();
		sorted.push_back(node);
		for(pair<int,int> next : graph[node]){
			count[next.first]--;
			if(count[next.first] == 0) currentNode.push(next.first);
		}
	}
	
	if(sorted.size() == graph.size()) return true;
	else return false;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	vector<vector<pair<int,int>>> graph;
	vector<int> sorted;
	int V, E;
	
	cin>>V>>E;
	
	graph.resize(V);
	
	for(int i = 0; i < E; i++){
		int s, t;
		
		cin>>s>>t;
		
		graph[s].push_back(make_pair(t,0));
	}
	
	if(TopologicalSort(graph, sorted)){
		for(int y : sorted){
			cout<<y<<endl;
		}
	} else {
		
	}
	
	return 0;
}


Measured memory_bytes: 4376
#include<bits/stdc++.h>
using namespace std;
// 関節点、橋、lowlink
// lowlink
typedef pair<int,int> mypair;
void dfs(int v,int p,int &k,vector<int> &ord,vector<int> &low,vector<bool> &used,vector<vector<int> > &g,vector<mypair> &bridge,vector<int> &articulation){
	used[v] = true;
	ord[v] = k++;
	low[v] = ord[v];
	bool isarticulation = false;
	int cnt = 0;
	for(int i=0;i<g[v].size();i++){
		if(!used[g[v][i]]){
			cnt++;
			dfs(g[v][i],v,k,ord,low,used,g,bridge,articulation);
			low[v] = min(low[v],low[g[v][i]]);
			if(~p&&ord[v]<=low[g[v][i]])isarticulation = true;
			if(ord[v]<low[g[v][i]])bridge.push_back( mypair( min(v,g[v][i]), max(v,g[v][i]) ) ) ;
		}
		else if(g[v][i] != p){
			low[v] = min(low[v],ord[g[v][i]]);
		}
	}
	if(p==-1 &&cnt>1)isarticulation=true;
	if(isarticulation)articulation.push_back(v);
}

int main(){
	int v,e;
	cin>>v>>e;
	vector<vector<int> >g(v);
	vector<int> ord(v),low(v);
	vector<int> art;
	vector<mypair> bridge;
	vector<bool> used(v,false);
	int k=0;

	for(int i=0;i<e;i++){
	int s,t;
	cin>>s>>t;
	g[s].push_back(t);
	g[t].push_back(s);
	}

	for(int i=0;i<v;i++)if(!used[i])dfs(i,-1,k,ord,low,used,g,bridge,art);
	sort(art.begin(),art.end());
	sort(bridge.begin(),bridge.end());

	for(int i=0;i<art.size();i++)cout<<art[i]<<endl;	

	return 0;
}



Measured memory_bytes: 5184