akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
#define pb push_back
#define ff first 
#define ss second  
typedef pair<int,int> pp;
bool com(pp x,pp y){
    return x.ff<y.ff;
} 
int N=1e5+9;
int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll x,k,d;
	cin>>x>>k>>d;
	ll y=(x/d);
	if(abs(y)>=k){
	    if(x>0) cout<<abs(x-k*d)<<"\n";
	    else cout<<abs(x+k*d)<<"\n";
	}
	else{
	    if(x>0){
	        ll p=x-y*d;
	        k-=y;
	        if(abs(p-d)<=abs(p+d)){
	            p-=d;
	            k--;
	        }
	        if(k&1) cout<<(abs(p-d)<=abs(p+d)?abs(p-d):abs(p+d))<<"\n";
	        else cout<<abs(p)<<"\n";
	    }
	    else if(x<0){
	        ll p=x-y*d;
	        k+=y;
	        if(abs(p+d)<=abs(p-d)){
	            p+=d;
	            k--;
	        }
	        if(k&1) cout<<(abs(p-d)<=abs(p+d)?abs(p-d):abs(p+d))<<"\n";
	        else cout<<abs(p)<<"\n";
	    }
	    else{
	        if(k&1) cout<<d<<"\n";
	        else cout<<"0\n";
	    }
	}
	return 0; 
	
}


Measured memory_bytes: 3592
import math
n,m,l = map(int, input().split())
A = []
for i in range(n):
    a = list(map(int, input().split()))
    A.append(a)
B = []
for j in range(m):
    b = list(map(int, input().split()))
    B.append(b)

C = []
for i in range(n):
    for k in range(l):
        for j in range(m):
            c = A[i][j]*B[j][k]
            C.append(c)
S = []
d = math.ceil(len(C)/(n*l))
r = [C[x: x+d] for x in range(0,len(C),d)]

for i in range(len(r)):
    s = sum(r[i])
    S.append(s)
    e = math.ceil(len(S)/n)
u = [S[y: y+e] for y in range(0,len(S),e)]
for i in range(len(u)):
    print(*u[i])


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

int main(){
  int A, B, C, D, E;
  cin >> A >> B >> C >> D >> E;
  if(A == 0){
    cout << 1 << endl;
  }
  else if(B == 0){
    cout << 2 << endl;
  }
  else if(C == 0){
    cout << 3 << endl;
  }
  else if(D == 0){
    cout << 4 << endl;
  }
  else{
    cout << 5 << endl;
  }
}

Measured memory_bytes: 3592
using System;
using System.Linq;

namespace atcoder_Beginner_Contest096_Question3
{
    class Program
    {
        static void Main(string[] args)
        {
            bool possible = true;
            var input1 = Console.ReadLine().Split().Select(int.Parse).ToArray();
            char[][] paint = new char[input1[0]][];
            for (int i = 0; i < input1[0]; i++)
            {
                paint[i] = Console.ReadLine().ToCharArray();
            }

            for (int i = 0; i < input1[0]; i++)
            {
                for (int j = 0; j < input1[1]; j++)
                {
                    if (paint[i][j] == '.') continue;

                    if (j + 1 < input1[1] && paint[i][j + 1] != '#')
                        if (j - 1 >= 0 && paint[i][j - 1] != '#')
                            if (i + 1 < input1[0] && paint[i + 1][j] != '#')
                                if (i - 1 >=0 && paint[i - 1][j] != '#')
                                    possible = false;
                    if (!possible) break;
                }
                if (!possible) break;
            }

            Console.WriteLine(possible ? "Yes" : "No");
        }
    }
}


Measured memory_bytes: 13396
#include <stdio.h>

using namespace std;

int main(){
        int a,b,c,count = 0;
        scanf("%d %d %d",&a,&b,&c);
        for(int i = a; i <= b; i++){
                if(c%i == 0) count++;
            }
        printf("%d\n",count);
}


Measured memory_bytes: 2688
N = int(input())
A = [ int(v) for v in input().split() ]

if N < 2 and 1e5 < N: raise()
for v in A:
    if v < -1e9 and v < 1e9: raise()

abs_list = [abs(v) for v in A]

total = sum( abs_list )
num_of_minus = sum([ True for v in A if v < 0 ])

if num_of_minus % 2 == 1:
    print(total - min( abs_list ) * 2)
else:
    print(total)


Measured memory_bytes: 14332
#include <iostream>
#include <cstdio>
using namespace std;
int main(){


  while(1){
    int a,b,d[101] = {0};

    while(1){
      if(scanf("%d%d",&a,&b)<2)return 0;
      if(a == 0)break;
      d[a]++;
      d[b]++;
    }
    int f = 1;
    if(!(d[1]%2 == 1 && d[2]%2 == 1))f = 0;
    for(int i = 3 ;f == 1 && i <= 100 ; i++ )
      {
	if(d[i]%2 == 1)f = 0;
      }
    if(f == 1)cout << "OK" << endl;
    else cout << "NG" << endl;
  }

  return 0;
}

Measured memory_bytes: 1204
// #ifdef DEBUG
// #define _GLIBCXX_DEBUG
// #endif
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>

// these require C++11
#include <unordered_set>
#include <unordered_map>
#include <random>
#include <thread>
#include <chrono>

using namespace std;

#define int long long

#define all(c) c.begin(), c.end()
#define repeat(i, n) for (int i = 0; i < static_cast<int>(n); i++)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x) 
#endif

template<typename A,typename B>
ostream &operator<<(ostream&os,const pair<A,B>& p){
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

typedef complex<double> point;



template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

struct Count{
    int left;
    int right;
    int sum;
};

struct Solved{
    vector<int> answer;
};

vector<int> dfs(vector<int>& v,int depth,const int X,
                vector<Count>& cnts){
    int n = v.size();
    if(depth == v.size()){
        vector<int> ss(n+1);
        for(int i=0;i<v.size();i++){
            ss[i+1] = ss[i] + v[i];
        }
        for(Count& c : cnts){
            int l = c.left;
            int r = c.right;
            // [l,r)
            int a = ss[r] - ss[l];
            if(a != c.sum){
                return vector<int>(n,-1);
            }
        }
        return v;
    }
    vector<int> maxi(n,-1);
    for(int i=0;i<=X;i++){
        v[depth] = i;
        vector<int> m = dfs(v,depth+1,X,cnts);
        int prev = accumulate(all(maxi),0);
        int cur = accumulate(all(m),0);
        if(prev < cur) maxi = m;
    }
    return maxi;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,x,m;
    cin >> n >> x >> m;

    vector<int> k(n,-1);
    vector<Count> cnts;
    for(int i=0;i<m;i++){
        int l,r,s;
        cin >> l >> r >> s;
        l--;
        cnts.push_back(Count{l,r,s});
    }
    vector<int> ans = dfs(k,0,x,cnts);
    if(ans[0] == -1){
        cout << -1 << endl;
    }else{
        for(int i=0;i<n;i++){
            cout << ans[i];
            if(i != n-1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 1216
#include <iostream>
//#include <iomanip>
//#include <algorithm>
//#include <numeric>
//#include <queue>
//#include <stack>
//#include <math.h>
//#include <vector>
//#include <unordered_map>
//#include <string>
//typedef long long LL;
//typedef long double LD;
using namespace std;

int main() {
    int a;
    int b;
    cin >> a >> b;
    if(a<=b){
        for(int i=0; i<b; i++){
            cout << a;
        }
    }else{
        for(int i=0; i<a; i++){
            cout << b;
        }
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PA;
#define INF (1<<30)
int suberi(PA a,PA b){
  return(a.second+b.second);
}
int yoko(PA a,PA b){
  return(abs(a.first-b.first));
}
int dp[151][10][80];
int main(){
  int n,m,k,x,d;
  while(scanf("%d %d",&n,&m),n!=0||m!=0){
    vector<PA> vec[151];
    fill_n(**dp,151*10*80,INF);
    for(int i=0;i<n;i++){
      scanf("%d",&k);
      for(int j=0;j<k;j++){
	scanf("%d %d",&x,&d);
	vec[i].push_back(PA(x,d));
	if(i == 0) dp[0][j][0] = 0;
	if(i == 1) dp[1][j][1] = 0;
      }
    }
    for(int i=0;i<n-1;i++){
      for(int j=0;j<vec[i].size();j++){
	for(int l=0;l<=m;l++){
	  for(int z=0;z<vec[i+1].size();z++){
	    dp[i+1][z][l] = min(dp[i+1][z][l],suberi(vec[i][j],vec[i+1][z]) * yoko(vec[i][j],vec[i+1][z]) + dp[i][j][l]);
	  }
	  if(l == m || i == n-2) continue;
	  for(int z=0;l<=m,z<vec[i+2].size();z++){
	    dp[i+2][z][l+1] = min(dp[i+2][z][l+1],suberi(vec[i][j],vec[i+2][z]) * yoko(vec[i][j],vec[i+2][z]) + dp[i][j][l]);
	  }
	}
      }
    }
    int ans = INF;
    for(int i=n-2;i<n;i++){
      for(int j=0;j<vec[i].size();j++){
	for(int l=0;l<=m;l++){
	  if(i!=n-2||l!=m) ans = min(ans,dp[i][j][l]);
	}
      }
    }
    printf("%d\n",ans);
  }
  return (0);
}



Measured memory_bytes: 3580
import java.io.BufferedReader;
//import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
//import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		//System.setIn(new FileInputStream("./ALDS1_4_B-in1.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		//int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		String[] l = br.readLine().split(" ");
		int[] s = new int[n];
		for(int i = 0; i < n; ++i) {
			s[i] = Integer.parseInt(l[i]);
		}
		
		int q = Integer.parseInt(br.readLine());
		//int[] t = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		l = br.readLine().split(" ");
		int[] t = new int[q];
		for(int i = 0; i < q; ++i) {
			t[i] = Integer.parseInt(l[i]);
		}
		
		//long start = System.nanoTime();
		int cnt = 0;
		for(int i = 0; i < q; ++i) {
			if(binarySearch(t[i], s)){
				cnt += 1;
			}
		}
		System.out.println(cnt);
		//System.out.println("Time:" + (System.nanoTime() - start) / 1000000f + " ms");

	}
	public static boolean binarySearch(int t, int[] s){
		int l = 0;
		int r = s.length;
		while(l <= r) {
			int mid = (l + r) / 2;
			if(s[mid] == t) {
				return true;
			}else if(s[mid] < t){
				l = mid + 1;
			}else{
				r = mid - 1;
			}
		}
		return false;
	}

}

Measured memory_bytes: 46460
#include<iostream>
#include<cstdio>

using namespace std;

int main(){
	int n, m;
	cin >> n >> m;
	int a[m];
	long int sum = 0;

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

	if (sum <= n)
		cout << n-sum << endl;
	else
		cout << "-1" << endl;
}


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

//Atcoder用


/*
 * BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] abc = br.readLine().split(" ");
		int a = Integer.parseInt(abc[0]);
		int b = Integer.parseInt(abc[1]);
		int c = Integer.parseInt(abc[2]);
 */
public class Main {
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] abc = br.readLine().split(" ");
		int a = Integer.parseInt(abc[0]);
		int b = Integer.parseInt(abc[1]);
		boolean flag = false;
		for(int c = 1;c<=3;c++){
			if ((a*b*c)%2 == 1){
				flag = true;
			}
		}

		if(flag){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}

}

Measured memory_bytes: 22228
#include<stdio.h>

int h,w;
int map[20][20];
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};

int ans;
int out(int y,int x){
	return y<0||h<=y||x<0||w<=x;
}
void search(int depth,int y,int x){
	int i,ny,nx;
	if(ans <= depth)return;
	for(i=0;i<4;i++){
		ny = y+dy[i];
		nx = x+dx[i];
		if(out(ny,nx) || map[ny][nx]==1)continue;
		do{
			if(map[ny][nx]==3){
				ans = depth;
				return;	
			}
			ny += dy[i];
			nx += dx[i];
		}while(!out(ny,nx) && map[ny][nx]!=1);
		if(!out(ny,nx) && map[ny][nx]==1){
			map[ny][nx]=0;
			search(depth+1,ny-dy[i],nx-dx[i]);
			map[ny][nx]=1;	
		}
	}
}
int main(){
	int i,j;
	int sy,sx;
	while(scanf("%d%d",&w,&h), w|h){
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				scanf("%d",&map[i][j]);
				if(map[i][j]==2){
					sy=i;sx=j;
				}
			}
		}
		ans=11;
		search(1,sy,sx);
		printf("%d\n",ans==11?-1:ans);
	}
}

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

int main() {
  string X;
  cin >> X;
  stack<char> st;
  rep(i, X.size()) {
    if (st.empty() || st.top() == 'T')
      st.push(X[i]);
    else {
      if (X[i] == 'T')
        st.pop();
      else
        st.push(X[i]);
    }
  }
  cout << st.size() << endl;
  return 0;
}


Measured memory_bytes: 644
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

#define LL long long
string S;

int main(){
    ios::sync_with_stdio(false);
    cin>>S;
    LL pos=S.size()-1,Ans=0;
    for(register LL i=S.size()-1;i>=0;--i)
        if(S[i]=='B'){Ans+=pos-i;--pos;}
    cout<<Ans<<endl;
    return 0;
}

Measured memory_bytes: 720
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
char s1[101],s2[101];
int main()
{
    gets(s1);
    gets(s2);
    int n=strlen(s1);
    int m=strlen(s2);
    sort(s1,s1+n);
    sort(s2,s2+m);
    for(int i=0;i<fmax(n,m);i++)
    {
        if(s1[i]<s2[m-i-1])
        {
            printf("Yes\n");
            return 0;
        }
        else if(s1[i]!=s2[m-i-1]) break;
    }
    printf("No\n");
    return 0;
} 

Measured memory_bytes: 256
import sys
n = int(input())
v = list(map(int, input().split()))

d1 = {}
d2 = {}
for i in range(n):
    if i % 2 == 0:
        if v[i] in d1:
            d1[v[i]] += 1
        else:
            d1[v[i]] = 1
    elif i % 2 == 1:
        if v[i] in d2:
            d2[v[i]] += 1
        else:
            d2[v[i]] = 1
l1 = list(d1.items())
l1 = sorted(l1, key=lambda x: x[1], reverse=True)
l2 = list(d2.items())
l2 = sorted(l2, key=lambda x: x[1], reverse=True)


if l1[0][0] != l2[0][0]:
    ans = n - l1[0][1] - l2[0][1]
    print(ans)
    sys.exit(0)
# 個々からの処理は奇数列と偶数列の最頻値が同じパターン
# 1種類の場合
if len(l1) == len(l2) == 1 and l1[0][0] == l2[0][0]:
    print(int(n/2))

# l1 2種類以上、l2 1種類
elif len(l1) >= 2 and len(l2) == 1:
    ans = n - l1[1][1] - l2[0][1]
    print(ans)

# l1 1種類、l2 2種類以上
elif len(l1) == 1 and len(l2) >= 2:
    ans = n - l1[0][1] - l2[1][1]
    print(ans)
elif len(l1) >= 2 and len(l2) >= 2:
    ans = min(n - l1[0][1] - l2[1][1], n - l1[1][1] - l2[0][1])
    print(ans)


Measured memory_bytes: 21276
#include<iostream>
#include<string>
using namespace std;
int main() {
	char a;
	char b;
	int c;
	int d;
	int e;
	std::cin >> a >> b;
	if (a == 'H' && b == 'H') {
		cout << 'H' << "\n";
	}
	else if (a == 'H' && b == 'D'){
		cout << 'D' << "\n";
	}
	else if (a == 'D' && b == 'H') {
		cout << 'D' << "\n";
	}
	else if (a == 'D' && b == 'D') {
		cout << 'H' << "\n";
	}
	std::cin >> e;
}

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

const bool DEBUG = false;

int main(int argc, char const *argv[]) {
  long long N;
  cin >> N;
  vector<long long> B(N - 1);
  for (size_t i = 0; i < N - 1; i++) cin >> B[i];

  long long total = B[0];
  for (size_t i = 1; i < N - 1; i++) total += min(B[i - 1], B[i]);
  total += B[N - 2];

  cout << total << endl;

  return 0;
}


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

int main() {
  int N; cin >> N;
  int A[N];
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  int max_value = *max_element(A,A+N);
  int min_value = *min_element(A,A+N);
  int answer = max_value-min_value;
  cout << answer << endl;
  return 0;
}


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

string n;
long long m = 0, w = 0, t = 0;

int main()
{
	cin >> n;
	
	long long j = n.size();

	for (long long i = j - 1; i >= 0; i--) {

		long long k = (long long)(n[i] - '0') + w;

		if (k < 5) {
			m += k - t;

			w = 0;
			t = 0;
		}
		else if (k == 5) {
			m += 5 - t;

			if (t == 0) {
				w = 1;
				t = 1;
			}
			else {
				w = 0;
				t = 0;
			}
		}
		else {
			m += 10 - k;
			w = 1;
			t = 0;
		}
	}

	if (n[j - 1] == '5' & t == 1)
		w = 0;

	cout << m + w << endl;

	return 0;
}

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


int main(){
  int n;
  cin >> n;
  vector<long long> A(n);
  for(int i=0;i<n;i++) cin >> A.at(i);
  vector<long long> sa(n+1,0);
  for(int i=0;i<n;i++) sa.at(i+1) = sa.at(i) + A.at(i);
  long long ans = 10000000000000000;
  for(int i=1;i<n-1;i++){
    long long left = sa.at(i+1);
    long long right = sa.at(n) - sa.at(i+1);
    
    int lsplit = min(int(upper_bound(sa.begin(),sa.end(),left/2) - sa.begin() - 2),i-1);
    int rsplit = min(int(upper_bound(sa.begin(),sa.end(),right/2 + left) - sa.begin() - 2),n-2);
    // cout << "rsplit = " << rsplit << endl;
    long long lM = min(max(sa.at(lsplit + 1),sa.at(i+1) - sa.at(lsplit + 1)),max(sa.at(lsplit + 2), sa.at(i+1) - sa.at(lsplit + 2)));
    long long rM = min(max(sa.at(rsplit + 1)-sa.at(i+1),sa.at(n)-sa.at(rsplit+1)) ,max(sa.at(rsplit+2)-sa.at(i+1),sa.at(n) - sa.at(rsplit+2)));
    // cout << "rM = " << rM << endl;
    long long M = max(lM,rM);
    long long m = min(sa.at(i+1) - lM,sa.at(n) - sa.at(i+1) - rM);
    // cout << i << ":" << M-m << " M = "<< M << " m = " << m << endl;
    ans = min(ans, M-m);
  }
  cout << ans << endl;
}


Measured memory_bytes: 6400
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
#define ceil(a, b) a / b + !!(a % b)

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


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

using namespace std;

int n;
int a[101];
int num[23];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]<=399)num[1]++;
		if(a[i]>399&&a[i]<=799)num[2]++;
		if(a[i]>799&&a[i]<=1199)num[3]++;
		if(a[i]>1199&&a[i]<=1599)num[4]++;
		if(a[i]>1599&&a[i]<=1999)num[5]++;
		if(a[i]>1999&&a[i]<=2399)num[6]++;
		if(a[i]>2399&&a[i]<=2799)num[7]++;
		if(a[i]>2799&&a[i]<=3199)num[8]++;
		if(a[i]>3199)num[9]++;
	}
	int ans=0;
	for(int i=1;i<=8;i++)
	{
		if(num[i])ans++;
	}
	if(ans==0)cout<<1<<" ";
	else cout<<ans<<" ";
	if(num[9]==0)
	{
		cout<<ans;
	}
	else
	{
	    cout<<num[9]+ans;
	}
	return 0;
 } 

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
N = int(input())
B = list(map(int,input().split()))

num = 0
for i in range(N):
    if i == 0:
        num += B[i]
    elif i == N - 1:
        num += B[i - 1]
    
    else:
        num += min(B[i - 1],B[i])

print(num)

Measured memory_bytes: 38464
use io::*;

fn main() {
    let input = read_string();
    let mut sc = Scanner::new(&input);
    let n: usize = sc.next();
    let m: usize = sc.next();
    let M = 1000000007;
    if n == m {
        println!("{}",2 * stair_m(n,M) * stair_m(m,M) % M);
    } else if n == m + 1 || n + 1 == m {
        println!("{}",stair_m(n,M) * stair_m(m,M) % M);
    } else {
        println!("0");
    }
}

fn stair_m(n: usize, m: usize) -> usize {
    (1..n+1).fold(1, |ac,x| ac * x % m)
}

pub mod io {
    use std;
    use std::str::FromStr;

    pub struct Scanner<'a> {
        iter: std::str::SplitWhitespace<'a>,
    }

    impl<'a> Scanner<'a> {
        pub fn new(s: &'a str) -> Scanner<'a> {
            Scanner {
                iter: s.split_whitespace(),
            }
        }

        pub fn next<T: FromStr>(&mut self) -> T {
            let s = self.iter.next().unwrap();
            if let Ok(v) = s.parse::<T>() {
                v
            } else {
                panic!("Parse error")
            }
        }

        pub fn next_vec_len<T: FromStr>(&mut self) -> Vec<T> {
            let n: usize = self.next();
            self.next_vec(n)
        }

        pub fn next_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.next()).collect()
        }

        pub fn next_mat<T: FromStr>(&mut self, w: usize, h: usize) -> Vec<Vec<T>> {
            (0..h).map(|_| self.next_vec(w)).collect()
        }

        pub fn next_vec_char(&mut self) -> Vec<char> {
            self.next::<String>().chars().collect()
        }

        pub fn next_mat_char(&mut self, n: usize) -> Vec<Vec<char>> {
            (0..n).map(|_| self.next_vec_char()).collect()
        }
    }

    pub fn read_string() -> String {
        use std::io::Read;

        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }

    pub fn read_line() -> String {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }
}


Measured memory_bytes: 4352
#include<stdio.h>
int main(){
  int n,m,i,j;
  while(1){
    scanf("%d %d",&n,&m);
    if(n==0&&m==0) break;
    for(i=0;i<n;i++){
      for(j=0;j<m;j++){
	printf("#");
      }
      printf("\n");
    }
    printf("\n");
  }
  return(0);
}

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

using namespace std;

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

    int a,b,c,cnt;
    cin >> a >> b >> c;
    for (int i = a; i <= b; i++) {
        if (c%i == 0) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}



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

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  for (int k = 0;;++k) {
    if (a * k - (k - 1) >= b) {
      cout << k;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 3552
h, w = map(int, input().split())
squares = [input() for i in range(h)]
squares_target = [[0 for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
      if squares[i][j] == '#':
          if not j - 1 < 0:
              squares_target[i][j-1] += 1
          if not j - 1 < 0 and not i - 1 < 0:
              squares_target[i-1][j-1] += 1
          if not i - 1 < 0:
              squares_target[i-1][j] += 1
          if not j + 1 > w -1 and not i - 1 < 0:
              squares_target[i-1][j+1] += 1
          if not j + 1 > w -1 :
              squares_target[i][j+1] += 1
          if not j + 1 > w -1 and not i + 1 > h -1:
              squares_target[i+1][j+1] += 1
          if not i + 1 > h - 1:
              squares_target[i+1][j] += 1
          if not j - 1 < 0 and not i + 1 > h - 1:
              squares_target[i+1][j-1] += 1

for i in range(h):
    for j in range(w):
        if squares[i][j] == '#':
            squares_target[i][j] = '#'
    print(''.join(map(str, squares_target[i])))

Measured memory_bytes: 3064
#4

N = int(input())
BList = []

for i in range(N):
	a,b = map(int,input().split())
	BList.append((b,a))
BList.sort()

sum = 0
for i in BList:
    sum += i[1]
    if (sum>i[0]):
        print("No")
        break

if(sum<=i[0]):
    print("Yes")

Measured memory_bytes: 29420
from bisect import bisect_right as br
from operator import itemgetter
from math import ceil
def main():
    N ,D ,A  = map(int,input().split())
    XH = [list(map(int,input().split())) for _ in range(N)]
    XH.sort(key = itemgetter(0))
    X = [x for x,h in XH]
    S = [0]*(N + 10)
    sm = 0
    for i in range(N):
        x,h = XH[i]
        right = br(X,x + 2*D) - 1
        h -= (sm - S[i-1])
        sm += max(0,ceil(h/A))*A
        S[right] += max(0,ceil(h/A))*A
        S[i] += S[i-1]
    print(sm // A)
    return

if __name__ == "__main__":
    main()

Measured memory_bytes: 62880
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define per(i,n) for (int i = n - 1; i >= 0; --i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline T intceil(T a, T b) { return (a + (b - 1)) / b; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const long long MOD = 1e9+7;
#define precout() cout << std::fixed << std::setprecision(20);
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const int dy[4] = { 0, 1, 0, -1 };
const int dx[4] = { 1, 0, -1, 0 };
static const double pi = 3.141592653589793;

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

  int n; cin >> n;
  vector<vector<int>> g(n);
  rep(i, n - 1) {
    int a,b; cin >> a >> b; --a,--b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<int> c(n);
  rep(i, n) cin >> c[i];
  sort(c.begin(), c.end(), greater<int>());

  int cIdx = 1;
  queue<P> q;
  q.push({0, c[0]});
  int score = 0;
  vector<int> ans(n, 0);
  vector<bool> visited(n, 0);
  ans[0] = c[0];
  visited[0] = 1;

  while(!q.empty()) {
    auto cur = q.front(); q.pop();

    for(auto next:g[cur.first]) {
      if(visited[next]) continue;

      visited[next] = 1;
      int nextC = c[cIdx++];
      ans[next] = nextC;
      q.push({next, nextC});
      score += min(cur.second, nextC);
    }
  }

  cout << score << endl;
  rep(i, n) {
    cout << ans[i];
    if(i != n - 1) cout << " ";
  }
  cout << endl;
}


Measured memory_bytes: 1024
while True:
    W, H = map(int, input().split())
    if W == 0 and H == 0:
        break
    maze = []
    for _ in range(H):
        maze.append(list(input()))
    visited = [[False] * W for _ in range(H)]
    dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    ans = 0


    def rec(x, y):
        global ans
        visited[x][y] = True
        ans += 1
        for (dx, dy) in dxy:  # 4方向の移動を試す
            x2 = x + dx
            y2 = y + dy
            if 0 <= x2 < H and 0 <= y2 < W:
                if maze[x2][y2] == '.':
                    if not visited[x2][y2]:
                        rec(x2, y2)  # 再帰呼び出し


    for h in range(H):
        for w in range(W):
            if maze[h][w] == '@':
                rec(h, w)
                break
        else:
            continue
        break

    print(ans)



Measured memory_bytes: 5760
# -*- coding: utf-8 -*-
N = int(input())
w = []
for i in range(N):
  w.append(input())

flag = 0
ss = set(w)
if(len(ss) != N):
  flag = 1
for i in range(N-1):
  if(w[i][-1] != w[i+1][0]):
    flag = 1
    break

if flag == 0:
  print('Yes')
else:
  print('No')


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

int main(){
    int n, d,x,a[100] = {};
    cin >> n >> d >> x;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }

    int ans = 0;

    for(int i = 0; i < n; ++i){
        ans += (d - 1)/a[i];
    }

    ans += n;

    ans += x;

    cout << ans << endl;
}

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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(auto i=0;i<(n);i++)
#define rep1(i,n) for(auto i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()

using namespace std;


struct init{ init(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); }; }aaaaaaa;



int main(){
  ll n, k;
  cin >> n >> k;

  double ans = 0.0;


  ll r = n;
  double l = k;
  
  
  double p = 1;
  for(double d = 0; d <= k; d += 1){
    for(ll i = ceil(l); i <= r; i++){
      if(n < r) break;
      ans += p;
    }
    r = min(r, (ll)ceil(l-1));
    p *= 0.5;
    l /= 2;
    if(l <= 0) break;
  }
  

  cout << ans/n << endl;

  
  return 0;
}



Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>

using namespace std; 

int n; 
int a[4020], c[4020]; 
int pw[2020], pb[2020]; 
int cw[2020][2020], cb[2020][2020], dp[2020][2020]; 

int main() {
    scanf("%d", &n); 
    for (int i = 1; i <= 2 * n; i++) {
        char s[2];
        scanf("%s %d", s, &a[i]); 
        if (s[0] == 'W') c[i] = 0, pw[a[i]] = i; 
        else c[i] = 1, pb[a[i]] = i; 
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (pw[i] < pw[j]) {
                cw[i][0]++; 
            }
        }
        for (int j = 1; j <= n; j++) {
            cw[i][j] = cw[i][j - 1]; 
            if (pw[i] < pb[j]) {
                cw[i][j]++; 
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (pb[i] < pb[j]) {
                cb[0][i]++;
            }
        }
        for (int j = 1; j <= n; j++) {
            cb[j][i] = cb[j - 1][i]; 
            if (pb[i] < pw[j]) {
                cb[j][i]++; 
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        dp[i][0] = dp[i - 1][0] + cw[i][0]; 
        dp[0][i] = dp[0][i - 1] + cb[0][i]; 
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = min(dp[i - 1][j] + cw[i][j], dp[i][j - 1] + cb[i][j]); 
        }
    }
    printf("%d\n", dp[n][n]); 
    return 0; 
}

Measured memory_bytes: 48000
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
#if DEBUG
            Solve(Console.In, Console.Out);
            Console.ReadLine();
#else
            Solve(Console.In, Console.Out);
#endif
        }

        public static void Solve(TextReader ci, TextWriter co)
        {
            int h, w, k;
            ReadInts(ci, out h, out w, out k);
            co.WriteLine(Solve(h, w, 0, k-1));
            co.Flush();
        }

        private static long Solve(int h, int w, int start, int goal)
        {
            int d = Math.Abs(start - goal);
            if (d > h) {
                return 0;
            }

            int key = (h << 16) | (start << 4) | (goal);
            long numTotalAns = 0;
            if (memo1.TryGetValue(key , out numTotalAns)) {
                return numTotalAns;
            }

            else if (h == 1) {
                int min = Math.Min(start, goal);
                int max = Math.Max(start, goal);
                return BarPattern(min - 1) * BarPattern(w - max - 2);
            }
            else {
                int h0 = h / 2;
                int h1 = h - h0;
                numTotalAns = 0;
                for (int mid = 0; mid < w; ++mid) {
                    long numAns =
                        Solve(h0, w, start, mid) *
                        Solve(h1, w, mid, goal);
                    numTotalAns = (numTotalAns + numAns) % 1000000007;
                }
                memo1.Add(key, numTotalAns);
                return numTotalAns;
            }
        }

        private static Dictionary<int, long> memo1 = new Dictionary<int, long>();


        private static long BarPattern(int n)
        {
            int numPattern;
            if (n <= 0) {
                return 1;
            }
            else if (memo2.TryGetValue(n, out numPattern)) {
                return numPattern;
            }
            else {
                numPattern = 0;
                int max = 1 << n;
                for (int i = 0; i < max; ++i) {
                    if ((i & (i << 1)) == 0) ++numPattern;
                }
                memo2.Add(n, numPattern);
                return numPattern;
            }
        }

        private static Dictionary<int, int> memo2 = new Dictionary<int, int>();

        public static int ReadInt(TextReader ci) => int.Parse(ci.ReadLine());

        public static void ReadInts(TextReader ci, out int a, out int b)
        {
            var array = IntArrayFrom(ci.ReadLine());
            a = array[0];
            b = array[1];
        }

        public static void ReadInts(TextReader ci, out int a, out int b, out int c)
        {
            var array = IntArrayFrom(ci.ReadLine());
            a = array[0];
            b = array[1];
            c = array[2];
        }

        public static int[] IntArrayFrom(string s)
            => s.Split(' ').Select(p => int.Parse(p)).ToArray();
    }
}


Measured memory_bytes: 13408
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        m: usize,
        k: i64,
        a: [i64; n],
        b: [i64; m],
    }

    let a: Vec<_> = (0..1i64)
        .chain(a.into_iter())
        .scan(0, |prev, a| {
            *prev += a;
            Some(*prev)
        })
        .collect();
    let b: Vec<_> = (0..1i64)
        .chain(b.into_iter())
        .scan(0, |prev, b| {
            *prev += b;
            Some(*prev)
        })
        .collect();

    let mut ans = 0;
    let mut j = m;

    for i in 0..=n {
        if a[i] > k {
            break;
        }
        while b[j] > k - a[i] {
            j -= 1;
        }
        ans = ans.max(i + j);
    }

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


Measured memory_bytes: 11932
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,t[20];
  for(int i=0;i<8;i++)t[i]=24-i*3;
  t[8]=2;
  t[9]=1;
  t[10]=-1;
  t[11]=-2;
  for(int i=1;i<9;i++)t[11+i]=-i*3;
  string p[20]={
    "yotta",
    "zetta",
    "exa",
    "peta",
    "tera",
    "giga",
    "mega",
    "kilo",
    "hecto",
    "deca",
    "deci",
    "centi",
    "milli",
    "micro",
    "nano",
    "pico",
    "femto",
    "ato",
    "zepto",
    "yocto"
  };
  
  cin>>n;
  while(n--){
    string a,b,c;
    cin>>a;
    cin>>b;
    bool f=0;
    for(int i=0;i<20;i++)if(b==p[i])f=1;
    if(f)cin>>c;
    else c=b;
    int cn=-1;
    if(a[0]=='0'){
      int i=2;
      while(i<a.size()&&a[i++]=='0')cn--;
      for(int j=i-1;j<a.size();j++){
	if(j==i)cout<<".";
	cout<<a[j];
      }
    }
    else{
      int i=0;
      while(i<a.size()&&a[i++]!='.')cn++;
      if(i==a.size())i++;
      for(int j=0;j<a.size();j++){
	if(j==i-1)continue;
	if(j==1)cout<<".";
	cout<<a[j];
      }
    }
    for(int i=0;i<20;i++)if(p[i]==b)cn+=t[i];
    cout<<" * 10^"<<cn<<" "<<c<<endl;
	
  }    
  return 0;
}

Measured memory_bytes: 1224
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main(){
	int h,n,s=0,x;
	cin>>h>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		s+=x;
	}
	if(h<=s)cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
N = int(input())
h = list(int(i) for i in input().split())
dp = [float("inf")]*N
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,N):
    dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[-1])

Measured memory_bytes: 13980
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,const pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,const vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}
template<typename T>vector<T> & cset(vector<T> &A,T e=T()){for(auto &I:A){I=e;} return A;}


int main(){
  ll a,b;
  cin>>a>>b;
  if(a>b){swap(a,b);}
  if((b-a)&1){cout<<"IMPOSSIBLE"<<endl;}
  else{cout<<(a+b)/2<<endl;}
  
  return 0;
}


Measured memory_bytes: 256
n = int(input())
h = list(map(int,input().split()))
dp = [10**7]*n
dp[0] = 0
for i in range(1,n):
  dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(3,i+1))])
print(dp[n-1])
  

Measured memory_bytes: 13924
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 998244353
using namespace std;
ll fn(ll n, ll p) { return n - n % p; }
int main() {
    ll k;
    cin >> k;
    vector<ll> a(k);
    for(int i = 0; i < k; i++) {
        cin >> a[i];
    }
    ll ans1, ans2;
    ll l = 0, r = LLONG_MAX / 2;
    while(l + 1 < r) {
        ll m = (l + r) / 2;
        ll mc = m;
        for(int i = 0; i < k; i++) {
            mc = fn(mc, a[i]);
        }
        if(mc <= 2) {
            l = m;
        } else {
            r = m;
        }
    }
    ans1 = l;
    l = 0, r = LLONG_MAX / 2;
    while(l + 1 < r) {
        ll m = (l + r) / 2;
        ll mc = m;
        for(int i = 0; i < k; i++) {
            mc = fn(mc, a[i]);
        }
        if(mc >= 2) {
            r = m;
        } else {
            l = m;
        }
    }
    ans2 = r;
    if(ans1 >= ans2) {
        cout << ans2 << " " << ans1 << endl;
    } else {
        cout << -1 << endl;
    }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
 //Compiler version g++ 6.3.0

 int main()
 {
 	int n,m;
 	cin >> n>>m;
 	ll ans=0;
 	priority_queue<ll> x;
 	for (int i = 0; i < n; i++){
 		ll y;
 		cin >> y;
 		ans+=y;
 		x.push(y);
 	}
 	for (int i = 0; i < m; i++){
 		ll y=x.top();
 		x.pop();
 		ans-=y-(y>>1);
 		x.push(y>>1);
 	}
 	cout << ans << endl;
 }


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

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 3e3 + 5;

int A[N], DP[N][N];

int Power(int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a = 1LL * a * a % MOD) if (b & 1) res = 1LL * res * a % MOD;
	return res;
}
int Inv = Power(2, MOD - 2);

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));
	
	int n, q; cin >> n >> q;
	for (int i = 0; i < n; i++) cin >> A[i];
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) DP[i][j] = (A[i] > A[j]);
	for (int t = 0; t < q; t++) {
		int x, y; cin >> x >> y; x--, y--;
		for (int i = 0; i < n; i++) if (i != x && i != y) {
			DP[i][x] = DP[i][y] = 1LL * (DP[i][x] + DP[i][y]) * Inv % MOD;
			DP[x][i] = DP[y][i] = 1LL * (DP[x][i] + DP[y][i]) * Inv % MOD;

		}
		DP[x][y] = DP[y][x] = 1LL * (DP[x][y] + DP[y][x]) * Inv % MOD;
	}
	int s = 0;
	for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) s = (s + DP[i][j]) % MOD;
	cout << 1LL * s * Power(2, q)  % MOD << endl;

	return 0;
}


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

int n, a, b;
bool nr[1000003];

int main(){
    cin >> n >> a >> b;
    while( n+a+b > 0 ){
        fill( nr+1, nr+n+1, 1 );
        for(int i = 0; i <= n; i++){
            if( !nr[i] ){
                if( i + a <= n ) nr[i+a] = 0;
                if( i + b <= n ) nr[i+b] = 0;
            }
        }
        int ans = 0;
        for(int i = 0; i < n+1; i++){
            ans += nr[i];
        }
        cout << ans << endl;
        cin >> n >> a >> b;
    }
    return 0;
}

Measured memory_bytes: 2136
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i = x; i < (int)(n); i++)
#define rep_ll(i,x,n) for(ll i = x; i < (ll)(n); i++)
using namespace std;
typedef long long ll;
typedef unsigned long long u_ll;
typedef pair<int, int> pair_;
const long double PI = (acos(-1));
const int INF = 1001001001;
const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1};
ll mod = 1000000007;
int main(){
    int n;
    cin >> n;
    vector<long double> a(n);
    rep(i, 0, n) cin >> a[i];

    long double total=0;
    rep(i, 0, n) total+=1/a[i];
    total=1/total;
    cout << fixed << setprecision(6) << total;
}

Measured memory_bytes: 3832
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")
 
#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";
#define INF 10000000000000000 //1e16
 
// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
 
 
// using namespace __gnu_pbds;
using namespace std;
 
using ll  = long long;
using vi  = vector<int>;
using pii = pair<int,int>;
using vii = vector<pii>;
using mi  = multiset<int>;
using mii = multiset<pii>;
 
int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}



void solve()
{
    int n,m,t,i,k,r,l,u,v,w,j,s,sum=0,pos,flag=0,count=0;
    string S,T,U; 
    // int a,b;
    cin>>n;
    vi a(n);
    map<int,int> occ;
    rep(i,0,n) cin>>a[i],occ[a[i]]++;
    rep(i,1,n+1)
    {
        count+=occ[i]*(occ[i]-1)/2;
    }
    // cout<<count;
    rep(i,0,n)
    {
        cout<<count-occ[a[i]]+1<<"\n";
    }
}
 
 
signed main()
{
    #ifndef ONLINE_JUDGE 
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}

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

#define each(i, c) for (auto& i : c)
#define mkp(a, b) make_pair(a, b)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> Pll;
const ll MOD = 1e9+7;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << ": " << p.second << ")"; return os; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ", "; os << ")"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; each (i, m) os << i << ", "; os << "}"; return os; }

bool sort_fn(Pll &a, Pll &b) {
  return a.second < b.second;
}

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

  vector<ll> x(n);
  for (ll i = 0; i < n; ++i) {
    cin >> x[i];
  }
  auto xx = x;
  sort(xx.begin(), xx.end());

  each (i, x) {
    ll idx = n/2;
    if (i < xx[idx]) {
      cout << xx[idx] << endl;
    } else {
      cout << xx[idx-1] << endl;
    }
  }

  return 0;
}

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

int main() {
    int N, M, X;
    cin >> N >> M >> X;
    const int INF = 1e9;
    int ans = INF;
    vector<int> C(N, 0);
    vector<vector<int>> A(N, vector<int> (M, 0));
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
        for (int j = 0; j < M; ++j) {
            cin >> A[i][j];
        }
    }
    for (int i = 0; i < (1 << N); ++i) {
        int cost = 0;
        vector<int> rikaido(M, 0);
        for (int j = 0; j < N; ++j) {
            if ((i >> j) & 1 == 1) {
                cost += C[j];
                for(int k = 0; k < M; ++k) {
                    rikaido[k] += A[j][k];
                }
            }
        }
        bool ok = [&]() {
            for (int k = 0; k < M; ++k) {
                if (rikaido[k] < X) return false;
            }
            return true;
        }();
        if (ok) ans = min(ans, cost);
    }
    cout << (ans == INF ? -1 : ans) << endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll MOD=1000000007;
const ll INF=1000000000LL;
const int MAX=100001;
const double EPS=1e-10;
struct edge{int to,cost;};
typedef pair<int,int> P;
int main(){
    int a[3];
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    int ans=a[2]-a[1];
    if((a[1]-a[0])%2==0){
        ans+=(a[1]-a[0])/2;
    }else{
        ans+=(a[1]-a[0])/2+2;
    }
    cout<<ans<<endl;
}

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

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define N 520

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n;

int use[N][N];
int res[N][N];

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

void dfs(int x, int y){
    int tr = use[x][y] + res[x][y];
    ff(i,0,3){
        int px = dx[i] + x;
        int py = dy[i] + y;
        if(px >= 0 && px <= n-1 && py >= 0 && py <= n-1){
            if(res[px][py] > tr){
                res[px][py] = tr;
                dfs(px, py);
            }
        }
    }
}


int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    ff(i,0,n - 1){
        ff(j,0,n - 1){
            res[i][j] = min(min(i,n-i-1), min(j,n-j-1));
            use[i][j] = 1;
        }
    }
    ll sol = 0;
    ff(i,0,n*n - 1){
        int x;
        cin >> x;
        x--;
        int px = x / n;
        int py = x % n;
        use[px][py] = 0;
        sol += res[px][py];
        dfs(px, py);
    }
    cout << sol << "\n";
    return 0;
}


Measured memory_bytes: 24600
#include <string>
#include <vector>
#include <map>
#include <deque>
#include <iostream>
#include <queue>
#include <math.h>
#include <algorithm>
#include <fstream>

using namespace std;
typedef long long ll;


int main(void) {
	int k, x,tmp;
	cin >> k >> x;

	for (int i = 0; i < k * 2 - 1; i++) {
		if (((x - (k - 1))+i) < -1000000 || ((x - (k - 1)) + i) >1000000){
		}
		else {
			cout << x - (k - 1) + i<<" ";
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
  int n,m,i,j,b,ans,a;
  string s;
int main()
{
  cin>>n;
  for (i=1;i<=n;i++)
    {
        cin>>a>>b;
        ans+=b-a+1;
    }
    
  cout<<ans;
}

Measured memory_bytes: 256