akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define N 100002
using namespace std;
struct node{
	int u,v,w;
}e[200002];
struct node1{
	int x,d;
	node1(int _x,int _d){
		x=_x,d=_d;
	}
};
vector<int> id[N];
int head[2000002],ver[2000002],nxt[2000002],edge[2000002],l;
int n,m,i,j,cnt[N],now[N],dis[2000002],num;
bool vis[2000002];
int read()
{
	char c=getchar();
	int w=0;
	while(c<'0'||c>'9') c=getchar();
	while(c<='9'&&c>='0'){
		w=w*10+c-'0';
		c=getchar();
	}
	return w;
}
int my_comp(const node &x,const node &y)
{
	return x.w<y.w;
}
void insert(int x,int y,double z)
{
	l++;
	ver[l]=y;
	edge[l]=z;
	nxt[l]=head[x];
	head[x]=l;
}
int bfs(int s)
{
	deque<node1> q;
	q.push_front(node1(s,0));
	vis[s]=1;
	while(!q.empty()){
		int x=q.front().x,d=q.front().d;
		q.pop_front();
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i];
			if(!vis[y]){
				vis[y]=1;
				if(y==num+n) return d+edge[i];
				if(edge[i]==1) q.push_back(node1(y,d+1));
				else q.push_front(node1(y,d));
			}
		}
	}
	return -1;
}
int main()
{
	n=read(),m=read();
	for(i=1;i<=m;i++) e[i].u=read(),e[i].v=read(),e[i].w=read();
	sort(e+1,e+m+1,my_comp);
	for(i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(now[u]!=w) cnt[u]++,now[u]=w,id[u].push_back(++num);
		if(now[v]!=w) cnt[v]++,now[v]=w,id[v].push_back(++num);
		insert(id[u][cnt[u]-1],id[v][cnt[v]-1],0);
		insert(id[v][cnt[v]-1],id[u][cnt[u]-1],0);
	}
	for(i=1;i<=n;i++){
		for(j=0;j<cnt[i];j++){
			insert(num+i,id[i][j],1);
			insert(id[i][j],num+i,1);
		}
	}
	int ans=bfs(num+1);
	if(ans==-1) cout<<ans<<endl;
	else cout<<ans/2<<endl;
	return 0;
}


Measured memory_bytes: 40064
#include <bits/stdc++.h>
using namespace std;
// マクロ
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
// 型エイリアス
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvs = vector<vs>;

int main() {
    int n;
    cin >>n;
    map<int, int> stu;
    rep(i,n) {
        int a;
        cin >> a;
        stu[a] = i+1;
    }
    rep(i,n) {
        cout << stu[i+1] << ' ';
    }
}

Measured memory_bytes: 5504
N, A, B = list(map(int, input().split()))

if (B - A) % 2 == 0:
  print((B - A) // 2)
else:
  if max(N - A, N - B) < max(A - 1, B - 1):
    print(N - B + 1 + (B - A - 1) // 2)
  else:
    print(A + (B - A - 1) // 2)

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<queue>
#include<algorithm>
typedef long long ll;
int main() {
	int n,dig = 0;
	int a = 0, b = 0;
	int ak = 0, bk = 0;
	int sum = 999999999;
	std::cin >> n;
	if (n >= 11) {
		for (int i = 1; i < n / 2; i++) {
			dig = 0;
			a = i;
			while (a) {
				dig = a % 10;
				ak = ak + dig;
				a = a / 10;
			}
			b = n - i;
			dig = 0;
			while (b) {
				dig = b % 10;
				bk = bk + dig;
				b = b / 10;
			}
			sum = std::min(ak + bk, sum);
			ak = 0;
			bk = 0;
		}
	}
	else {
		std::cout << n << std::endl;
		return 0;
	}
	std::cout << sum << std::endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<string>
#include<math.h>
using namespace std;


void insertSort(double a[], int size) {

	int i, j;
	for (i = 1; i < size; i++) {
		j = i;
		while ((j > 0) && (a[j - 1] > a[j])) {
			swap(a[j - 1], a[j]);
			j--;
		}
	
	}
}



int main() {


	int n,k;
	cin >> n;
	cin >> k;
	
	int score = k;
	int count;

	
	double ans[100001];

	int i;
	for (i=1;i<=n;i++){
		score = i;
		count = 0;
		while (1) {
			if (score < k) {
				score *= 2;
				count++;
			}
			else
				break;
		}
		//p += pow(0.5, count) / (double)n;
		ans[i] = pow(0.5, count) / (double)n;
		//insertSort(ans, i);

		
	}
	double p = 0;
	for (i = 1; i <=n ; i++) {

		p += ans[i];
	}


	printf("%0.11lf\n", p);

	
	return 0;
}



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

using namespace std;

#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

// thanks kactl

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) { x->p = inf; return false; }
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

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

    int n;
    ll c;
    cin >> n >> c;
    // (hj - hi)^2 + C
    // hj^2 - 2hj hi + hi^2 + C
    // Each hi creates a line of the form -2 hi x + hi^2 + C
    vector<ll> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    
    // returns max, so negate the lines
    // negation of ax + b is -ax - b
    LineContainer lc;
    lc.add(2LL * h[0], -h[0] * h[0] - c);

    constexpr ll INF = 1e18;
    vector<ll> dp(n, INF);
    dp[0] = 0;

    for (int i = 1; i < n; ++i) {
        dp[i] = -lc.query(h[i]) + h[i] * h[i];
        lc.add(2LL * h[i], - h[i] * h[i] - c - dp[i]);
        
        // cout << "dp[" << i << "] = " << dp[i] << '\n';
    }

    cout << dp[n - 1] << '\n';

    return 0;
}


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

int main() {
  int n;
  cin>>n;
  vector<int> a(n);
  vector<int> b(n);
  vector<int> sum(n);
  for(int i=0;i<n;i++){
    cin>>a.at(i);
  }
  for(int i=0;i<n;i++){
    cin>>b.at(i);
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(j<=i){
        sum.at(i)+=a.at(j);
      }
      if(j>=i){
        sum.at(i)+=b.at(j);
      }
    }
  }
    sort(sum.begin(),sum.end());
    cout<<sum.at(n-1)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define for_tests(t, tt) int t; scanf("%d", &t); for(int tt = 1; tt <= t; tt++)
#ifndef ONLINE_JUDGE
#define debug(args...) fprintf(stderr,args)
#else
#define debug(args...)
#endif //ONLINE_JUDGE
template<typename T> inline T abs(T t) { return t < 0? -t : t; }
const ll modn = 1000000007;
inline ll mod(ll x) { return x % modn; }

const int MAXN = 212345;

int n[3], m, k[2];
ll s[3][MAXN];

int main (){
	scanf("%d%d%d%d%d", k, k+1, n, n+1, n+2);
    for(int t=0;t<3;t++){
        for(int a=0;a<n[t];a++){
            scanf("%lld", &s[t][a]);
        }
        sort(s[t], s[t]+n[t], greater<ll>());
    }
    multiset<int> app;
    ll som = 0;
    for(int t=0;t<2;t++){
        for(int a=0;a<k[t];a++){
            app.insert(s[t][a]); 
            som += s[t][a];
        }
    }
    for(int i=0;i<n[2];i++){
        if(s[2][i] > *app.begin()){
            som -= *app.begin();
            app.erase(app.begin());
            app.insert(s[2][i]);
            som += s[2][i];
        }
    }
    printf("%lld\n", som);
}



Measured memory_bytes: 11904
#include <stdio.h>
#include <iostream>

using namespace std;

int main() {
	int n;
	int hyou[50100] = {1};
	for (int i = 1; i < 50100; i++) {
		if (hyou[i] == 0) {
			for (int j = 2; (i+1) * j < 50100; j++) {
				hyou[(i+1)*j-1] = 1;
			}
		}
	}
	while (cin >> n) {
		for(int i = n-2; i >= 0; i--) {
			if (hyou[i] == 0) {
				cout << i+1 << " ";
				break;
			}
		}
		for (int i = n; i < 50100; i++) {
			if (hyou[i] == 0) {
				cout << i+1 << endl;
				break;
			}
		}
	}
	return 0;

}

Measured memory_bytes: 1360
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

void execute()
{
	int N;
	cin >> N;
	vector<int> a(8, 0);
	vector<int> b(8, 0);

	lint count_a = 0;
	lint count_b = 0;

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

	for (int i = 0; i < N; i++)
	{
		int min_a = a[i] - 1;
		int min_b = b[i] - 1;
		for (int j = i - 1; 0 <= j; j--)
		{
			if (a[j] < a[i])
				min_a--;
			if (b[j] < b[i])
				min_b--;
		}

		for (int j = 1; j < N - i; j++)
		{
			min_a *= j;

			min_b *= j;
		}
		count_a += min_a;
		count_b += min_b;
	}

	cout << abs(count_a - count_b) << endl;
	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define TMAX 100001
#define THALF 50000

void fill(int *p, int T, int d)
{
	int i;
	for(i=0; i<T; i++){
		*(p+i) = d;
	}
}
void stak(int *p, int head, int end, int d)
{
	int i;
	for(i=head; i<end; i++){
		*(p+i) += d;
	}
}

int main(void)
{
    int N, T, t[TMAX], in, out, d, sw, max=0, i, j;
    scanf("%d%d", &N, &T);
	scanf("%d%d", &in, &out);
	sw = (THALF > out - in ? 1 : 2);
	switch(sw){
		case 1:
			fill(t, T, 0);
			stak(t, in, out, 1);
			for(i=1; i<N; i++){
				scanf("%d%d", &in, &out);
				stak(t, in, out, 1);
    		}
		    for(j=0; j<T; j++){
		        max = (max < *(t+j) ? *(t+j) : max);
		    }
			break;
		case 2:
			fill(t, T, N);
			stak(t, 0, in, -1);
			stak(t, out, T, -1);
			for(i=1; i<N; i++){
				scanf("%d%d", &in, &out);
				stak(t, 0, in, -1);
				stak(t, out, T, -1);
			}
			for(j=0; j<T; j++){
				max = (max < *(t+j) ? *(t+j) : max);
			}
			break;
		default:
			break;
	}
    printf("%d\n", max);
    return 0;
}

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
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 {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=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 {
        mint res(*this);
        return res/=a;
    }
};

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    unordered_map<int, int> c;
    c[0] = 3;
    mint ans = 1;
    rep(i, N) {
        if (!c[A[i]]) {
            puts("0");
            return 0;
        }
        ans *= c[A[i]];
        --c[A[i]];
        ++c[A[i]+1];
    }
    cout << ans.x << endl;
}


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

typedef long long ll;
typedef pair<int, int> P;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

struct edge {int to, cost;};

int n, r;
vector<edge> g[1501];
int d[1501][1501];
int mp[1501];
int mmp[1501][1501];

inline void dijkstra(int s) {
  priority_queue<P, vector<P>, greater<P> > que;
  fill(d[s], d[s] + n + 1, 1145141919);
  d[s][s] = 0;
  que.push(P(0, s));

  while(!que.empty()) {
    P p = que.top(); que.pop();
    int v = p.second;
    if(d[s][v] < p.first) continue;
    rep(i, 0, g[v].size()) {
      if(d[s][g[v][i].to] > d[s][v] + g[v][i].cost) {
        d[s][g[v][i].to] = d[s][v] + g[v][i].cost;
        que.push(P(d[s][g[v][i].to], g[v][i].to));
      }
    }
  }
}

inline void solve(int i, int j) {
  stack<int> st;
  st.push(j);
  while(!st.empty()) {
    int tp = st.top(); st.pop();
    mmp[i][tp] = 1;
    rep(k, 0, g[tp].size()) {
      if(d[i][tp] == d[i][g[tp][k].to] + g[tp][k].cost && !mmp[i][g[tp][k].to]) {
        st.push(g[tp][k].to);
      }
    }
  }
}

int main() {
  cin >> n >> r;
  rep(i, 0, r) {
    int a, b, c;
    cin >> a >> b >> c;
    edge e;
    e.to = b, e.cost = c;
    g[a].pb(e);
    e.to = a;
    g[b].pb(e);
  }
  rep(i, 1, n + 1) {
    dijkstra(i);
  }
  int mas = 0;
  rep(i, 1, n + 1) {
    rep(j, 1, n + 1) {
      mas = max(mas, d[i][j]);
    }
  }
  rep(i, 1, n + 1) {
    rep(j, i + 1, n + 1) {
      if(mas == d[i][j]) {
        mp[i] = 1;
        solve(i, j);
      }
    }
  }
  rep(i, 0, n + 1) {
    rep(j, 0, n + 1) {
      if(mmp[i][j]) mp[j] = 1;
    }
  }
  int count = 0;
  rep(i, 1, n + 1) {
    if(!mp[i]) count++;
  }
  cout << count << endl;
  rep(i, 1, n + 1) {
    if(!mp[i]) cout << i << endl;
  }
}

Measured memory_bytes: 20572
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
vector<ll> node[200005];
bool used[200005];
P d1(ll pos){
  P res=P(0,pos);
  for(int i=0;i<node[pos].size();i++){
    int to=node[pos][i];
    if(used[to]) continue;
    used[to]=true;
    P dans=d1(to);
    if(dans>res) res=dans;
  }
  res.first++;
  return res;
}
int main(){
  ll n;
  cin>>n;
  for(int i=1;i<n;i++){
    ll s,t;
    cin>>s>>t;
    node[s].push_back(t);
    node[t].push_back(s);
  }
  for(int i=1;i<=n;i++) used[i]=false;
  used[1]=true;
  ll ds=d1(1).second;
  for(int i=1;i<=n;i++) used[i]=false;
  used[ds]=true;
  cout<<((d1(ds).first-2)%3==0?"Second":"First")<<endl;
}


Measured memory_bytes: 20736
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()
}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let line = read_as_vec::<usize>();
    println!("{}", line[0]*line[1]);

}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
int n,m,k;
int a[100010],b[100010];
int res;
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for (int i=0;i<n;i++) scanf("%d",&a[i]);
	for (int i=0;i<m;i++) scanf("%d",&b[i]);
	res=*min_element(a,a+n)+*min_element(b,b+m);
	for (int i=0;i<k;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		x--,y--;
		res=min(res,a[x]+b[y]-z);
	}
	printf("%d",res);
	return 0;
}

Measured memory_bytes: 1024
import math  # noqa: F401
from typing import Dict, List, Optional, Tuple, Union  # noqa: F401


def sum_xor(A: List[int]) -> int:
    sum_ = 0
    for a in A:
        sum_ ^= a
    return sum_


def main(N: int, A: List[int]):
    sum_ = sum_xor(A)
    for a in A:
        print(a ^ sum_, end=" ")
    print()


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    main(N, A)


Measured memory_bytes: 34276
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(12);
  int n;
  cin>>n;
  string s;
  double m;
  double ans;
  rep(i,n){
    cin>>m>>s;
    if(s=="JPY") ans+=m;
    else ans+=m*(double)380000;
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
n,q = map(int, raw_input().split())
que = [map(str, raw_input().split()) for i in range(n)]
for i in range(n):que[i][1] = int(que[i][1])
mxt = sum([y for x,y in que])
t = 0
i = 0
while t < mxt:
    if i >= n: i %= n
    if que[i][1] <= q:
        t += que[i][1]
        print que[i][0],t
        que.pop(i)
        n -= 1
    else:
        t += q
        que[i][1] -= q
        i += 1

Measured memory_bytes: 14020
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>

using namespace std;
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()
// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return;std::cout << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class X> void DEBUG(X d, T e){if(DEBUG_OUT == false)return;std::cout <<d<<" ";DEBUG(e);};
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

  // vector<vector<vector<int> > > DP =  vector<vector<vector<int> > >(100001,vector<vector<int> >(2,vector<int>(2,0)));
void solve(void)
{
   int N;
   cin>>N;
   vector<int> vec(N);
   map<int,int> mp;
   for (int i = 0; i < N; i++)
   {
     int A;
     cin>>A;
     vec[i] = A;
     auto itr = mp.find(A);
     if(itr == mp.end())
     {
       mp[A] = 1;
     }
     else
     {
       itr->second++;
     }
   }
   auto itr = mp.begin();
   int SUM = 0;
   for (int i = 0; i < mp.size(); i++)
   {
     int X = itr->second;
     SUM += (X)*(X-1)/2;
     itr++;
   }
  //  DEBUG(SUM);
   
   
   for (int i = 0; i < N; i++)
   {
     int X = vec[i];
     int K = mp[X];
     K--;
     cout<<SUM + (K)*(K-1)/2 - (K+1)*K/2<<endl;
   }
   
   
  return;
}

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

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

  return 0;
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 40) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr double eps = 1e-9;
constexpr ll MOD = 1000000007LL;
template <typename T>
bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for(int i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 == v.size() ? "\n" : " ");
    }
    return os;
}
template <typename T>
vector<T> make_v(size_t a) {
    return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {
    t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {
    for(auto& e : t) {
        fill_v(e, v);
    }
};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            vector<ll> v;
            int c = 0;
            for(int l = 0; l < i; l++) {
                v.push_back(a[l]);
                c++;
            }
            for(int l = j + 1; l < n; l++) {
                v.push_back(a[l]);
                c++;
            }
            if(c > k) {
                continue;
            }
            sort(all(v));
            ll s = 0;
            for(int l = 0; l < (int)v.size(); l++) {
                if(c + l >= k || v[l] >= 0) {
                    s += v[l];
                }
            }
            chmax(ans, s);
        }
    }
    sort(all(a));
    ll s = 0;
    if(n <= k) {
        for(int l = 0; l < n; l++) {
            if(n + l >= k || a[l] >= 0) {
                s += a[l];
            }
        }
        chmax(ans, s);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  int H,W,D;
  cin >> H >> W >> D;
  int A[H][W];
  vector<P> point((H*W)+1);
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> A[i][j];
      point[A[i][j]].first = i;
      point[A[i][j]].second = j;
    }
  }
  vector<int> dist[D];
  // distは累積和で表現
  for (int i = 0; i < D; i++) {
    for (int j = 0; (D * j) + i <= H * W; j++) {
      if (j == 0) {
        dist[i].push_back(0);
      } else {
        int num = (D * j) + i;
        int res = 0;
        res += abs(point[num].first - point[num-D].first);
        res += abs(point[num].second - point[num-D].second);
        dist[i].push_back(dist[i][j-1] + res);
      }
    }
  }
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int l,r;
    cin >> l >> r;
    int s = l % D;
    l = (l - s) / D;
    r = (r - s) / D;
    int ans = dist[s][r] - dist[s][l];
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 6400
#include <iostream>
#include <vector>
#include <algorithm>

int q;
std::string s;

int main() {
    std::cin >> s
             >> q;
    for ( int i=0; i<q; ++i ) {
        std::string t;
        int a, b;
        std::cin >> t;
        std::cin >> a >> b;
        if ( t == "print" ) {
            std::cout << s.substr(a, b-a+1) << std::endl;
        } else if ( t == "reverse" ) {
            std::reverse( s.begin()+a, s.begin()+b+1 );
        } else if ( t == "replace" ) {
            std::string r;
            std::cin >> r;
            if ( a > 0 ) {
                s = s.substr( 0, a ) +  r + s.substr( b+1, s.size()-a );
            } else {
                s = r + s.substr( b+1, s.size()-a );
            }
        }
    }

    return 0;
}



Measured memory_bytes: 3236
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
# import math
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(int(pow(10, 2)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]





# @lru_cache(None)


n,m=l()
if(m<2*n):
    print(m//2)
elif(m==2*n):
    print(n)
else:
    print(n+(m-2*n)//4)

Measured memory_bytes: 5120
INF=10*10
H,W=map(int, input().split())
s=[list(input()) for _ in range(H)]
wall=sum(map(lambda x: x.count("#"), s))
d=[[INF for _ in range(W)] for _ in range(H)]
def bfs(h, w, c):
	if d[h][w] <= c:
		return
	d[h][w] = c
	for dh,dw in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
		if h+dh >= 0 and w+dw >= 0 and h+dh < H and w+dw < W and s[h+dh][w+dw] == ".":
			bfs(h+dh, w+dw, c+1)
bfs(0, 0, 1)
print(-1 if d[H-1][W-1] == INF else H*W - d[H-1][W-1] - wall)


Measured memory_bytes: 3064
#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n, l, ans=0;
    string f, s[100]={};
    cin>>f>>n;
    l=f.size();
    for (int i=0; i<n; i++)
    {
        cin>>s[i];
        s[i]+=s[i];
    }
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<=s[i].size()-l; j++)
        {
            if (f==s[i].substr(j,l)) {ans++; j=50; }
        }
    }
    cout<<ans<<'\n';
    return 0;
}



Measured memory_bytes: 3160
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int N, A, B;
	cin >> N >> A >> B;
	int Contestant = 0, foreign = 1;
	char ch;
	for (int i = 0; i < N; i++) {
		cin >> ch;
		if (ch == 'a') {
			if (Contestant < (A + B)) {
				cout << "Yes" << endl;
				Contestant++;
			}
			else cout << "No" << endl;
		}
		else if (ch == 'b') {
			if (Contestant < (A + B) && foreign <= B) {
				cout << "Yes" << endl;
				Contestant++;
				foreign++;
			}
			else cout << "No" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int a[3050];
    int sum = 0;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    cout << sum - n << endl;
    return 0;
}


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

const ll INF = 100000000000;

int main() {
  ll n; cin >> n;
  vector<ll> flog(n),dp(n+2);
  for(ll i=0;i<n;++i) cin >> flog[i];
  for(ll i=0;i<n;++i) dp[i] = INF;
  auto a = [](ll a, ll b){ return (a<b)? a:b; };

  dp[0] = 0;
  for(ll i=0;i<n-1;++i) {
    dp[i+1] = a(dp[i+1],dp[i] + abs(flog[i + 1] - flog[i]));
    dp[i+2] = a(dp[i+2],dp[i] + abs(flog[i + 2] - flog[i]));
  }
  cout << dp[n-1] << endl;
  return 0;
}

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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const ll INF = 1LL<<60;
//int INF = numeric_limits<int>::max();

int main(int, char**) {
	int n; cin >> n;
	string s; cin >> s;
	string ret = s;
	int cnt = 0;
	for (int i=0; i<n; i++) {
		char now = s[i];
		if (now=='(') cnt++;
		else if (cnt==0) ret = '(' + ret;
		else cnt--;
	}
	for (int i=0; i<cnt; i++) {
		ret = ret + ')';
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
#include <deque>
#include <functional>
#include <sstream>
using namespace std;

// 정답이 ll 이상일 경우 INF를 98765432100000 정도까지 크게 해야함
// 입력받는 값이 10^9 이고 답이 뭔가 그것들을 더하는 연산이라면 답은 ll 일수 있다
// priority_queue 는 기본적으로 내림차순 정렬이다. 오름차순으로 하고 싶다면 priority_queue<int, vector<int>, greater<int>>
// queue에서 pop하기 전에는 반드시 empty인 경우를 체크하고 예외처리 해줘라


#define INF 9876543210
#define mod 1000000007
#define mt make_tuple
#define mp make_pair
typedef long long ll;

char str[100010];
int K;

int main() {

	scanf("%s", str);
	scanf("%d", &K);

	int MAX = 'z' + 1;
	int len = strlen(str);
	for (int i = 0; i < len; i++) {
		if (str[i] == 'a') continue;
		int d = MAX - str[i];
		if (d <= K) {
			str[i] = 'a';
			K -= d;
		}
	}
	for (int i = 0; i < len; i++) {
		int d = MAX - str[i];
		if (d <= K) {
			str[i] = 'a';
			K -= d;
		}
	}
	if (K != 0) {
		int t = str[len - 1] - 'a';
		t = (t + K) % 26;
		str[len - 1] = 'a' + t;
	}
	printf("%s\n", str);

	return 0;
}

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

int main(void){
    int A, B, C;
    cin >> A >> B >> C;
    for(int k=0;k<B;k++){
        if(k*A % B == C) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define in insert
#define all(x) (x).begin(), (x).end()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int main(){
    int n, k;
    cin >> n >> k;
    map<int, int> m;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        m[x]++;
    }
    if(m.size() <= k){
        cout << 0;
        return 0;
    }
    int cnt = 0;
    vector<pii> v;
    for(map<int, int>::iterator it = m.begin(); it != m.end(); it++){
        v.pb(mp((*it).s, (*it).f));
    }
    sort(all(v));
    for(int i = 0; i < v.size() - k; i++){
        cnt += v[i].f;
    }
    cout << cnt;
}

Measured memory_bytes: 11768
def ceil(d, n)
  (d+n-1)/n
end
def ok(x)
  return false if N*(N-1) < A.inject(:+)-x
  A.map{|a|[0, ceil(a+x+1-N, N+1)].max}.inject(:+) <= x
end
N=gets.to_i
A=gets.split.map &:to_i
l, h = -1, 10**18
until l+1==h
  m=(l+h)/2
  ok(m) ? h=m : l=m
end
([0,h-N*N].max .. h).each{|x|
  next unless ok(x)
  p x
  break
}


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

const int INF = 1000000000;

std::string ten_to_n(int ten,int base){
    if(ten == 0)return "0";
    std::string s;
    while(ten){
        int amari = ten % base;
        char c = '0' + amari;
        s.push_back(c);
        ten /= base;
    }
    std::reverse(s.begin(),s.end());

    return s;
}

long long powe(long long base,long long exp){
    long long res = 1;
    while(exp>0){
        if(exp & 1)res = res * base;
        base = base * base;
        exp >>= 1;
    }
    return res;
}


int main()
{
    int n,m;
    cin >> n >> m;
    vector<int> keta(6, -1);
    bool res = true;

    for(int i = 0; i < m; i++){
        int s, c;
        cin >> s >> c;
        s--;
        if(keta[s] != c && keta[s] != -1)res = false;
        keta[s] = c;
    }
    string ans(10,'A');
    for(int i = powe(10,n - 1); i < powe(10,n); i++){
        string s = ten_to_n(i,10);
        bool f = false;
        for(int j = 0; j < n; j++){
            if(keta[j] + '0' != s[j] && keta[j] != -1)f = true;
        }

        if(!f){
            for(int j = 0; j < n; j++){
                ans[j] = (keta[j] == -1 ? '0':  keta[j] + '0');
            }
            break;
        }
    }
    if(n == 1){
        if(keta[0] == -1 || keta[0] == 0){
            cout << 0 << endl;
            return 0;
        }
    }
    if(ans[0] == '0' && n != 1)ans[0] = '1';
    if(ans[0] == 'A' || !res)cout << -1;
    else{
        for(int i = 0; i < n; i++)cout << ans[i];
    }
    cout << endl;

}

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

int main() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    int maxOfABC = max({a, b, c});
    int ans = maxOfABC;
    while (k > 0) {
        ans *= 2;
        k--;
    }
    cout << ans + a + b + c - maxOfABC << endl;
}

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

#define BUF_SIZE 256
#define DICT_SIZE  8000009
#define OFFSET      312349
#define TRY_NUM 20
#define MAX_STR_LEN 12

char* dict[DICT_SIZE];

size_t char_hash(char ch)
{
  switch(ch) {
    case 'A':
      return 1;
    case 'C':
      return 2;
    case 'G':
      return 3;
    case 'T':
      return 4;
    default:
      fprintf(stderr, "Unknown char found: %c\n", ch);
      exit(1);
  }
}

size_t power(size_t x, size_t n)
{
  size_t result = 1;
  for(size_t i = 0; i < n; i++) {
    result = result * x;
  }
  return result;
}

size_t compute_str_hash(const char* str, size_t offset)
{
  size_t hash = offset;
  for(size_t i = 0; i < strlen(str); i++) {
    hash += char_hash(str[i]) * power(5, i);
  }
  return hash % DICT_SIZE;
}

void dict_add(const char* str)
{
  size_t offset = 0;
  size_t hash;
  while(1) {
    hash = compute_str_hash(str, offset);
    if(dict[hash]) {
      offset += OFFSET;
      continue;
    } else {
      break;
    }
  }
  dict[hash] = calloc(MAX_STR_LEN + 1, 1);
  if(!dict[hash]) {
    perror("calloc");
    exit(1);
  }
  strncpy(dict[hash], str, MAX_STR_LEN);
}

bool dict_search(const char* str)
{
  size_t offset = 0;
  size_t hash;
  for(int i = 0; i < TRY_NUM; i++) {
    hash = compute_str_hash(str, offset);
    if(dict[hash] && strcmp(dict[hash], str) == 0) {
      return true;
    } else {
      offset += OFFSET;
      continue;
    }
  }
  return false;
}

void read_cmd()
{
  char buf[BUF_SIZE];
  fgets(buf, sizeof(buf), stdin);
  char* lf_addr = strchr(buf, '\n');
  if(lf_addr) {
    *lf_addr = '\0';
  } else {
    fprintf(stderr, "LF not found: %s\n", buf);
    exit(1);
  }
  char* space_addr = strchr(buf, ' ');
  char* arg;
  if(space_addr) {
    *space_addr = '\0';
    arg = space_addr + 1;
  } else {
    fprintf(stderr, "space not found: %s\n", buf);
    exit(1);
  }
  char* cmd = buf;
  if(strcmp(cmd, "insert") == 0) {
    dict_add(arg);
  } else if(strcmp(cmd, "find") == 0) {
    if(dict_search(arg)) {
      puts("yes");
    } else {
      puts("no");
    }
  } else {
    fprintf(stderr, "Invalid command: %s\n", cmd);
    exit(1);
  }
}

int main()
{
  memset(dict, 0, sizeof(dict));
  int num_cmd;
  scanf("%d\n", &num_cmd);
  for(int i = 0; i < num_cmd; i++) {
    read_cmd();
  }
  return 0;
}



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

typedef long long ll;

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

//--------------------

int n;
ll k;
vector<int> a;

int main() {

  cin >> n >> k;
  a.resize(n);
  rep(i, n) cin >> a[i];

  vector<int> q;
  vector<int> ord(n+1, -1);

  int v = 1;
  while(ord[v]==-1) {
    ord[v] = q.size();
    q.push_back(v);
    v = a[v-1];
  }

  int c = q.size()-ord[v];
  int l = ord[v];

  if(k<l) cout << q[k] << endl;
  else {
    k -= l;
    k %= c;
    cout << q[l+k] << endl;
  }

  return 0;
}


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

public class Main {
	static int mod = (int) 1e9 + 7;
	static int DX[] = { -1, 0, 1, 0 }, DY[] = { 0, -1, 0, 1 };

	public static void main(String[] args) {
		FastScanner fs = new FastScanner(System.in);
		int n = fs.nextInt(), m = fs.nextInt(), d = fs.nextInt();
		double ans = 0;
		if(d==0) ans = (double) (m-1) / n;
		else ans = (double)2 * (n-d)*(m-1) / ((double) n * n);
		System.out.println(ans);

	}
	//MOD culculations
	static long plus(long x, long y) {
		x %= mod;
		y %= mod;
		long res = (x + y) % mod;
		return res;
	}

	static long suv(long x, long y) {
		x %= mod;
		y %= mod;
		long res = (x - y + mod) % mod;
		return res;
	}

	static long mul(long x, long y) {
		x %= mod;
		y %= mod;
		long res = x * y % mod;
		return res;
	}

	static long div(long x, long y) {
		x %= mod;
		y %= mod;
		long res = x * modpow(y, mod - 2) % mod;
		return res;
	}

	//modの元での高速pow()
	static long modpow(long a, long p) {
		if (p == 0)
			return 1;
		if (p % 2 == 0) {
			long halfP = p / 2;
			long root = modpow(a, halfP);
			return root * root % mod;
		} else
			return a * modpow(a, p - 1) % mod;
	}

}

//高速なScanner
class FastScanner {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public FastScanner(InputStream in) {
		reader = new BufferedReader(new InputStreamReader(in));
		tokenizer = null;
	}

	public String next() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public String nextLine() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken("\n");
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
long long p = 1000000007;
long long modsub(long long a, long long b){
	if (a >= b){
		return (a - b) % p;
	} else {
		return p - (b - a) % p;
	}
}
long long modpow(long long a, long long b){
	long long res = 1;
	while (b > 0){
		if (b % 2 == 1) res = res * a % p;
		a = a * a % p;
		b = b / 2;
	}
	return res;
}
long long modinv(long long a){
	return modpow(a,p - 2);
}
vector<long long> mf;
long long modfact(long long n){
	if (n < mf.size()){
		return mf[n];
	} else {
		if (mf.empty()) mf.push_back(1);
		long long res = mf.back();
		for (int i = mf.size(); i <= n; i++){
			res = res * i % p;
			mf.push_back(res);
		}
		return res;
	}
}
long long modbinom(long long n, long long r){
	long long res;
	res = modfact(n);
	res = res * modinv(modfact(r)) % p;
	res = res * modinv(modfact(n - r)) % p;
	return res;
}
int main(){
  long long n,k;
  cin >> n >> k;
  if (k >= n - 1){
    cout << modbinom(2 * n - 1,n);
  } else {
    int ans = 0;
    for (int i = 0; i <= k; i++){
      ans += modbinom(n - 1, i) * modbinom(n, i) % p;
      ans %= p;
    }
    cout << ans;
  }
}

Measured memory_bytes: 6000
n, q = map(int, input().split())
s = input()

m = []
total = 0
b = False

for c in s:
    if c == 'A':
        b = True
    elif c == 'C' and b:
        total += 1
        b = False
    else:
        b = False
    m.append(total)

for _ in range(q):
    l, r = map(int, input().split())
    print(m[r-1] - m[l-1])


Measured memory_bytes: 6152
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int pcnt(int x) {
  return __builtin_popcount(x);
}
int f(int x) {
  if (x == 0) return 0;
  return f(x%pcnt(x))+1;
}
 
int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> x(n);
  rep(i,n) x[i] = s[i]-'0';
  int pc = 0;
  rep(i,n) pc += x[i];
  vector<int> ans(n);
  rep(b,2) {
    int npc = pc;
    if (b == 0) npc++; else npc--;
    if (npc <= 0) continue;
    int r0 = 0;
    rep(i,n) {
      r0 = (r0*2)%npc;
      r0 += x[i];
    }
    int k = 1;
    for (int i = n-1; i >= 0; --i) {
      if (x[i] == b) {
        int r = r0;
        if (b == 0) r = (r+k)%npc;
        else r = (r-k+npc)%npc;
        ans[i] = f(r)+1;
      }
      k = (k*2)%npc;
    }
  }
 
  rep(i,n) cout << ans[i] << endl;
  return 0;
}

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

int factorial(int k) {
    int ans = 1;
    for (int i = 1; i <= k; i++) {
        ans *= i;
    }
    return ans;
}

int main() {
    int N; cin >> N;
    vector<vector<int>> var(N, vector<int>(2));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 2; j++) {
            cin >> var.at(i).at(j);
        }
    }
    double num = 2 * factorial(N-1);
    long double sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            sum += sqrt((var.at(i).at(0) - var.at(j).at(0)) * (var.at(i).at(0) - var.at(j).at(0)) + (var.at(i).at(1) - var.at(j).at(1)) * (var.at(i).at(1) - var.at(j).at(1))) * num;
        }
    }
    double ans = factorial(N);
    cout << setprecision(15);
    cout << sum / ans << endl;
}

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
int n;
const int MAXN = 100010;
int bit[MAXN];
void update(int pos, int val){
	while(pos <= n) {
		bit[pos] += val;
		pos += pos & -pos;
	}
}
long long get(int pos){
	long long ret = 0;
	while(pos){
		ret += bit[pos];
		pos -= pos & -pos;
	}
	return ret;
}
int main(){
	int q;
	scanf("%d %d", &n, &q);
	while(q--){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if(a == 0) update(b, c);
		else printf("%lld\n", get(c) - get(b - 1));
	}
	return 0;
}

Measured memory_bytes: 3584
#include <iostream>
using namespace std;
int dp[2000 + 1];

int main(void){
    int n;
    long sum = 0;
    int MOD = 1e9+7;
    
    cin >> n;
    
    dp[0] = 1;
    for (int i = 1; i < n; i++) dp[i] = 0;
    
    for (int i = 1; i <= n; i++){
        if (i >= 3){
            sum += dp[i - 3];
            sum %= MOD;
        }
        dp[i] = sum;
    }
    
    cout << dp[n] << endl;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100+5;
const int mod = 1e9+7;
const int maxnum = 10000;
ll qpow(ll a,ll b){ll res=1;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int head[maxn],tot;
int n,m,s;
struct EDGE
{
    int st,ed,costm,costt,next;
}edge[maxn*10];
void addedge(int st,int ed,int costm,int costt)
{
    edge[++tot].st=st,edge[tot].ed=ed,edge[tot].next=head[st];
    edge[tot].costm=costm,edge[tot].costt=costt;
    head[st]=tot;
}
ll dist[maxn][10005];
ll vis[maxn][10005];
struct node
{
    int now,res;
    ll cost;
    node(int n,int r,ll c):now(n),res(r),cost(c){}
    friend bool operator < (node a,node b){
        return a.cost>b.cost;
    }
};
void cal()
{
    memset(vis,0,sizeof(vis));
    memset(dist,0x3f,sizeof(dist));
    if(s>maxnum)s=maxnum;
    dist[1][s]=0;
    priority_queue<node>q;
    q.push(node(1,s,0));
    while(!q.empty()){
        node now = q.top();
        q.pop();
        if(dist[now.now][now.res]<now.cost)continue;
        // cout<<now.now<<' '<<now.res<<' '<<now.cost<<endl;
        // system("pause");         
        vis[now.now][now.res]=1;
        for(int i = head[now.now];i;i = edge[i].next){
            int to = edge[i].ed;
            int res = now.res-edge[i].costm;
            if(res<0)continue;
            if(res>maxnum)res=maxnum;
            if(dist[to][res]>now.cost+edge[i].costt){
                dist[to][res]=now.cost+edge[i].costt;
                if(!vis[to][res]){
                    q.push(node(to,res,dist[to][res]));
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i = 1;i <= m;++i){
        int s,t,a,b;
        scanf("%d%d%d%d",&s,&t,&a,&b);
        addedge(s,t,a,b);
        addedge(t,s,a,b);
    }
    for(int i = 1;i <= n;++i){
        int a,b;
        scanf("%d%d",&a,&b);
        addedge(i,i,-a,b);
    }
    cal();
    for(int i = 2;i <= n;++i){
        ll ans = 1e18;
        for(int j = 0;j <= maxnum;++j)ans=min(ans,dist[i][j]);
        printf("%lld\n",ans);
    }
    return 0;
}


Measured memory_bytes: 27964
N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
sumpre = 0
sumans = 0
for i in range(N-1):
    sumpre += A[i]
    sumans += A[i+1]*sumpre%mod
    sumans =sumans%mod
print(sumans)

Measured memory_bytes: 94156
//
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vvi vector< vi >
#define vii vector< ii >
#define mp make_pair
#define pb push_back
int A[10005];
int B[10005];
void fail()
{
    puts("No");
    exit(0);
}
void succ()
{
    puts("Yes");
    exit(0);
}
int main()
{
    //#ifndef atom freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif
    int N; scanf("%d", &N);
    for(int i = 1; i<= N; i++) scanf("%d", A+i);
    for(int i = 1; i<= N; i++) scanf("%d", B+i);
    ll sm = 0;
    for(int i = 1; i<= N; i++) sm -= A[i];
    for(int i = 1; i<= N; i++) sm += B[i];
    if(sm< 0) fail();
    bool eq = 1;
    for(int i = 1; i<= N; i++) if(A[i] != B[i]) eq = 0;
    if(sm == 0)
    {
        if(eq) succ();
        else fail();
    }
    ll use = 0;
    for(int i = 1; i<= N; i++)
    {
        if(A[i]< B[i]) use += (B[i]-A[i]+1)/2;
    }
    if(use<= sm) succ();
    else fail();
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define LL long long
using namespace std;
inline int gi () {
	int x=0, w=0; char ch=0;
	while (! (ch>='0' && ch<='9') ) {
		if (ch=='-') w=1;
		ch=getchar ();
	}
	while (ch>='0' && ch<='9') {
		x= (x<<3) + (x<<1) +  (ch^48);
		ch=getchar ();
	}
	return w?-x:x;
}

const int N=2e5+10;
int n,K,L,fas[N],far[N]; 
map < pair <int , int > , int > Map;

int Get_fa (int x, int *fa) {
	return x==fa[x]?x:fa[x]=Get_fa (fa[x], fa);
}

int main ()
{
	n=gi (), K=gi (), L=gi ();
	for (int i=1;i<=n;++i) 
		fas[i]=far[i]=i;
	for (int i=1, x, y;i<=K;++i) {
		x=gi () ,y=gi ();
		int fax=Get_fa (x, fas), fay=Get_fa (y, fas);
		if (fax==fay) continue;
		fas[fax]=fay;
	}
	for (int i=1, x, y;i<=L;++i) {
		x=gi (), y=gi ();
		int fax=Get_fa (x, far), fay=Get_fa (y, far);
		if (fax==fay) continue;
		far[fax]=fay;
	}
	for (int i=1;i<=n;++i) 
		Map[make_pair (Get_fa (i, fas), Get_fa (i, far) )]++;
	for (int i=1;i<=n;++i)
		printf ("%d\n", Map[make_pair (fas[i], far[i])]);
	return 0;
}


Measured memory_bytes: 13568