akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<vector>
#include<set>

using namespace std;

int main(){
	int n;
	scanf("%d", &n);
	vector<int> a(n), b(n);
	for(int i = 0; i < n; i++){
		scanf("%d", &a[i]);
		b[a[i] - 1] = i + 1;
	}
	long long ans = 0;
	set<int> s = {0, n + 1};
	for(int i = 0; i < n; i++){
		int t = b[i];
		s.insert(t);
		auto it = s.find(t);
		auto l = it, r = it;
		l--; r++;
		ans += (long long)(i + 1) * (t - *l) * (*r - t);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 11136
#include <atcoder/all>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

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

int main(){
  int N,D;
  scanf("%d%d",&N,&D);
  
  vector<int> x(N),y(N);
  rep(i,N){
    cin >> x[i] >> y[i];
  }
  
  two_sat ts(N);
  
  rep(i,N){
    rep(j,N){
      if(i>=j){
        continue;
      }
      if(abs(x[i]-x[j])<D){
        ts.add_clause(i,false,j,false);
      }      
      if(abs(x[i]-y[j])<D){
        ts.add_clause(i,false,j,true);
      }
      if(abs(y[i]-x[j])<D){
        ts.add_clause(i,true,j,false);
      }
      if(abs(y[i]-y[j])<D){
        ts.add_clause(i,true,j,true);
      }
    }
  }
  
  if(!ts.satisfiable()){
    printf("No\n");
  }
  else{
    printf("Yes\n");
    auto answer=ts.answer();
    rep(i,N){
      if(answer[i]){
        printf("%d\n",x[i]);
      }
      else{
        printf("%d\n",y[i]);
      }
    }
  }
  
  return 0;
}

Measured memory_bytes: 3844
#include<iostream>
#include<string>
using namespace std;
int main() {
	string a, b;
	cin >> a >> b;
	string ans = "NO";
	if (a.at(0) == b.at(2) && a.at(2) == b.at(0) && a.at(1) == b.at(1)) {
		ans = "YES";
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define L "\n"
#define S " "
#define ll long long
#define pb push_back
#define mp make_pair
#define vi std::vector<int>
#define si std::set<int>
#define vl std::vector<long long>
#define qi std::queue<int>
#define de(a) cout << #a << "  ------>  " << a << "\n"
#define SIZE 100002
#define INF INT_MAX
#define FOR(i, n) for (i = 1; i <= n; i++)
#define FASTIO                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)

using namespace std;
int dp[SIZE][3], N, h[SIZE][3];
bool flag[SIZE][3];

int hap(int i, int act)
{
    int a1, a2;
    if(i == N){
        flag[i][act] = 1;
        return dp[i][act] = h[i][act];
    }
    if (act == 0)
    {
        if (flag[i + 1][1])
            a1 = dp[i + 1][1];
        else
            a1 = hap(i + 1, 1);
        if (flag[i + 1][2])
            a2 = dp[i + 1][2];
        else
            a2 = hap(i + 1, 2);
    }

    else if (act == 1)
    {
        if (flag[i + 1][0])
            a1 = dp[i + 1][0];
        else
            a1 = hap(i + 1, 0);
        if (flag[i + 1][2])
            a2 = dp[i + 1][2];
        else
            a2 = hap(i + 1, 2);
    }
    else if (act == 2)
    {
        if (flag[i + 1][1])
            a1 = dp[i + 1][1];
        else
            a1 = hap(i + 1, 1);
        if (flag[i + 1][0])
            a2 = dp[i + 1][0];
        else
            a2 = hap(i + 1, 0);
    }
    flag[i][act] = 1;
    return dp[i][act] = h[i][act] + max(a1, a2);
}

void solve()
{
    int i;
    cin >> N;
    FOR(i, N)
    {
        cin >> h[i][0];
        cin >> h[i][1];
        cin >> h[i][2];
    }
    int res = max(hap(1, 0), max(hap(1, 1), hap(1, 2)));
    cout << res << L;
}
int main()
{
    FASTIO;
    // #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    // #endif
    int t;
    // cin >> t;
    // while (t--)
    solve();
    return 0;
}

Measured memory_bytes: 7552
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] fact2 = new int[N];
		int[] fact5 = new int[N];
		int L = 45;
		int[][] map = new int[L*2][L*2];
		int exclude = 0;
		for(int i=0; i<N; i++) {
			String A = sc.next();
			int shosu = 0;
			int dot = A.indexOf(".");
			if(dot >= 0) {
				shosu = A.length()-dot-1;
				A = A.substring(0, dot) + A.substring(dot+1);
			}
			long v = Long.valueOf(A);
			fact2[i] = -shosu;
			fact5[i] = -shosu;
			while(v%2==0) {
				fact2[i]++;
				v/=2;
			}
			while(v%5==0) {
				fact5[i]++;
				v/=5;
			}
			map[L+fact2[i]][L+fact5[i]]++;
			if(fact2[i]>=0 && fact5[i]>=0)
				exclude++;
		}
		
		int[][] sum = new int[L*2][L*2];
		for(int i=L*2-1; i>=0; i--) {
			for(int j=L*2-1; j>=0; j--) {
				sum[i][j] = map[i][j] + (i<L*2-1 ? sum[i+1][j] : 0 ) + (j<L*2-1 ? sum[i][j+1] : 0) - (i<L*2-1 && j<L*2-1 ? sum[i+1][j+1] : 0);
			}
		}
		long ans = 0;
		
		for(int i=0; i<N; i++) {
			ans += sum[L-fact2[i]][L-fact5[i]];
		}
		
		System.out.println((ans-exclude)/2);
		
		sc.close();
	}
}


Measured memory_bytes: 52900
#include<bits/stdc++.h>
using namespace std;
inline int gi()
{
	char c=getchar(); int x=0;
	for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';
	return x;
}
typedef pair<int,int> pr;
const int N=2019;
vector<int> e[N];
struct node
{
	int u,v;
}; vector<node> a;
int n,m,u[N],v[N],d[N],dep[N],fa[N],cov[N],ans;
void dfs(int u)
{
	for(auto v:e[u]) if(v!=fa[u])
		++d[u],dep[v]=dep[u]+1,fa[v]=u,dfs(v);
}
void apply(int u, int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(;dep[u]!=dep[v];u=fa[u]) ++cov[u];
	for(;u!=v;u=fa[u],v=fa[v]) ++cov[u],++cov[v];
}
queue<int> q;
bool flag;
vector<int> solve(vector<node> a)
{
	if(!a.size()||q.empty())
	{
		vector<int> tmp;
		tmp.resize(a.size());
		return tmp;
	}
	int u=q.front(); q.pop();
	for(auto v:e[u]) if(!(--d[v])) q.push(v);
	vector<int> b,c,g;
	vector<node> d;
	c.resize(a.size());
	for(int i=0;i<a.size();++i) if((a[i].u==u||a[i].v==u)&&a[i].u!=a[i].v) b.push_back(i);
	for(auto x:b) if(a[x].u!=u) swap(a[x].u,a[x].v),c[x]^=1;
	for(int i=1;i<b.size();i+=2) d.push_back((node){a[b[i-1]].v,a[b[i]].v}); 
	for(int i=0;i<a.size();++i) if(a[i].u!=u&&a[i].v!=u) d.push_back(a[i]);
	if(b.size()&1&&a[b.back()].u!=a[b.back()].v)
		d.push_back((node){fa[a[b.back()].u],a[b.back()].v});
	g=solve(d); int j=0;
	for(int i=1;i<b.size();i+=2,++j) c[b[i-1]]^=(g[j]^1),c[b[i]]^=g[j];
	for(int i=0;i<a.size();++i) if(a[i].u!=u&&a[i].v!=u) c[i]=g[j++];
	if(b.size()&1&&a[b.back()].u!=a[b.back()].v) c[b.back()]^=g.back();
	return c;
}
int main()
{
	n=gi(),m=gi();
	for(int i=1;i<n;++i)
	{
		int u=gi(),v=gi();
		e[u].push_back(v),e[v].push_back(u);
	}
	dfs(1);
	for(int i=1;i<=m;++i)
	{
		u[i]=gi(),v[i]=gi();
		apply(u[i],v[i]);
		a.push_back((node){u[i],v[i]});
	}
	for(int i=2;i<=n;++i) ans+=min(2,cov[i]);
	for(int i=1;i<=n;++i) if(!d[i]) q.push(i);
	vector<int> b=solve(a);
	printf("%d\n",ans);
	for(int i=1;i<=m;++i)
	{
		if(b[i-1]) swap(u[i],v[i]);
		printf("%d %d\n",u[i],v[i]);
	}
}

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

#define NIL -1

struct Point{
    int location;
    int x;
    int y;
};

bool asc_x(const Point& l, const Point& r) {
    return l.x < r.x;
}

bool asc_y(const Point& l, const Point& r) {
    return l.y < r.y;
}

struct Node{
    Point p;
    Node* left;
    Node* right;
};

class Tree{
private:
    Node* top;
    Node* AddNode(vector<Point>& P, int l, int r, int depth){
        if (l > r) return NULL;
        Node* N = new Node;
        int m = (l + r) / 2;
        if (depth % 2) {
            sort(P.begin() + l, P.begin() + r + 1, asc_y);
        } else {
            sort(P.begin() + l, P.begin() + r + 1, asc_x);
        }
        N->p = P[m];
        N->left  = AddNode(P, l    , m - 1, depth + 1);
        N->right = AddNode(P, m + 1, r    , depth + 1);
        return N;
    }
    void findNode(int s_x, int t_x, int s_y, int t_y,
                  Node* N, int depth, vector<int>& ans){
        if (N == NULL) return;
        if (s_x <= N->p.x && N->p.x <= t_x &&
            s_y <= N->p.y && N->p.y <= t_y) {
                ans.push_back(N->p.location);
            }
        if (depth % 2) {
            if (N->p.y <= t_y) {
                findNode(s_x, t_x, s_y, t_y, N->right, depth + 1, ans);
            }
            if (N->p.y >= s_y) {
                findNode(s_x, t_x, s_y, t_y, N->left , depth + 1, ans);
            }
        } else {
            if (N->p.x <= t_x) {
                findNode(s_x, t_x, s_y, t_y, N->right, depth + 1, ans);
            }
            if (N->p.x >= s_x) {
                findNode(s_x, t_x, s_y, t_y, N->left , depth + 1, ans);
            }
        }
    }
public:
    int MakeTree(vector<Point>& P){
        top = AddNode(P, 0, P.size() - 1, 0);
    }
    void find(int s_x, int t_x, int s_y, int t_y, vector<int>& ans){
        findNode(s_x, t_x, s_y, t_y, top, 0, ans);
    }
};

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

    int n;
    scanf("%d", &n);
    // cin >> n;
    vector<Point> P(n);

    for (int i = 0; i < n; i++) {
        // cin >> P[i].x >> P[i].y;
        scanf("%d %d", &P[i].x, &P[i].y);
        P[i].location = i;
    }
    Tree T;
    T.MakeTree(P);
    // T.display();
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int s_x, t_x, s_y, t_y;
        // cin >> s_x >> t_x >> s_y >> t_y;
        scanf("%d %d %d %d", &s_x, &t_x, &s_y, &t_y);
        vector<int> ans;
        T.find(s_x, t_x, s_y, t_y, ans);
        sort(ans.begin(), ans.end());
        for (int j = 0; j < ans.size(); j++) {
            // cout << ans[j] << endl;
            printf("%d\n", ans[j]);
        }
        // cout << endl;
        printf("\n");
    }
    return 0;
}

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

int main()
{
	string s;
	int a_min = 10000000;
	int z_max = 0;
	cin >> s;
	for (int i = 0; i < s.size(); ++i)
	{
		if (s[i] == 'A')
			a_min = min(a_min, i);
		if (s[i] == 'Z')
			z_max = max(z_max, i);
	}
	cout << z_max - a_min + 1 << endl;
}

Measured memory_bytes: 640
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a_list = list(map(int, input().split()))
flag = 1
for a in a_list:
    if a % 2 == 0:
        if a % 3 == 0 or a % 5 == 0:
            flag = 1
        else:
            flag = 0
            break
if flag == 1:
    print("APPROVED")
else:
    print("DENIED")

Measured memory_bytes: 3060
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional> 
#include <iomanip>
#include <unordered_map>
#include <memory.h>
#include <cstring>
#include <fstream>

using namespace std;

int h, w, n;
int sy, sx;
string s;
string t;

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

	cin >> h >> w >> n;
	cin >> sy >> sx;
	cin >> s;
	cin >> t;

	int y = sy;
	int x = sx;
	for (int i = 0; i < n; i++)
	{
		//cout << y << ' ' << x << '\n';
		if (s[i] == 'L')
		{
			x -= 1;
			if (x <= 0)
			{
				cout << "NO" << '\n';
				return 0;
			}
		}
		if (t[i] == 'R')
		{
			if (x + 1 <= w)
			{
				x += 1;
			}
		}
	}

	y = sy;
	x = sx;
	for (int i = 0; i < n; i++)
	{
		//cout << y << ' ' << x << '\n';
		if (s[i] == 'R')
		{
			x += 1;
			if (x > w)
			{
				cout << "NO" << '\n';
				return 0;
			}
		}
		if (t[i] == 'L')
		{
			if (x - 1 > 0)
			{
				x -= 1;
			}
		}
	}

	y = sy;
	x = sx;
	for (int i = 0; i < n; i++)
	{
		//cout << y << ' ' << x << '\n';
		if (s[i] == 'U')
		{
			y -= 1;
			if (y <= 0)
			{
				cout << "NO" << '\n';
				return 0;
			}
		}
		if (t[i] == 'D')
		{
			if (y + 1 <= h)
			{
				y += 1;
			}
		}
	}

	y = sy;
	x = sx;
	for (int i = 0; i < n; i++)
	{
		//cout << y << ' ' << x << '\n';
		if (s[i] == 'D')
		{
			y += 1;
			if (y > h)
			{
				cout << "NO" << '\n';
				return 0;
			}
		}
		if (t[i] == 'U')
		{
			if (y - 1 > 0)
			{
				y -= 1;
			}
		}
	}

	cout << "YES" << '\n';

	return 0;
}

Measured memory_bytes: 920
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
	int n ;
	cin >> n;
	vector<int> ar(n);
	map<int, int> mp;
	for(int i =0 ; i<n; i++)
	{
		cin>> ar[i];
		mp[ar[i]]++;
	}
	map<int, int> res;
	int sum =0;
	for(auto x : mp)
	{
		res[x.first] = (x.second * (x.second - 1))/2;
		sum += res[x.first];
	}
	for(auto x: ar)
	{
		int ans = (res[x] * (mp[x]-1) )/(mp[x]+1);
		cout<< (sum + ans - res[x]) << endl;
	}
}

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

int main()
{
  string S;
  cin >> S;

  if (S[2] == S[3] && S[4] == S[5])
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}

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

typedef long long ll;

using vi = vector<int>;
using vl = vector<long long int>;
using vii = vector<vector<int>>;
using vll = vector<vector<long long int>>;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
       const int INF=1e9+7;
       const double pi=6.28318530717958623200;
      
       double r;
       cin>>r;
       double ans=r*pi;
       cout<<fixed<<setprecision(9)<<ans<<endl;


return 0;

}




Measured memory_bytes: 3788
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<algorithm>
#include<queue>
#include<list>
#include<stack>
#include<cstdio>
#include<fstream>
#include<numeric>
#include<functional>
#include<utility>
#include<memory>
#include<cstring>
#include<bits/stdc++.h>
using namespace std; 
  
#define CLEAN(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;

ll n;

int main()
{
	cin>>n;
	if (n%2==0) cout<<n<<endl;
	else cout<<n*2<<endl;
    return 0;
}

Measured memory_bytes: 256
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    h, w, k = map(int, input().split())
    c = [list(input()) for i in range(h)]
    ans = 0
    sum_b = 0
    h_b = []
    w_b = [0] * w
    for i in range(len(c)):
        sum_b += c[i].count('#')
        h_b.append(c[i].count('#'))
    for i in range(w):
        for j in range(h):
            if c[j][i] == '#':
                w_b[i] += 1

    for bit_h in range((1 << h)):
        for bit_w in range((1 << w)):
            cnt = 0
            kk = []
            kkk = []
            for i in range(h):
                if bit_h & (1 << i):
                    cnt += h_b[i]
                    kk.append(i)
            for j in range(w):
                if bit_w & (1 << j):
                    cnt += w_b[j]
                    kkk.append(j)
            for i in kk:
                for j in kkk:
                    if c[i][j] == '#':
                        cnt -= 1
            if sum_b - cnt == k:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 68532
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef pair<double,int> PDI;
const double eps=1e-12;
const int INF=0x3f3f3f3f;
const LL inf=1e18;
const double pi=acos(-1.0);
const int mod=1e9+7;
//LL powmod(LL a,LL b) {LL res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int v[30];
int a[10000][30];
int b[10000];
int main(){
//    freopen("in.txt","r",stdin);
//    freopen("outt.txt","w",stdout);
    int n;
    string s,ss;
    cin>>s;
    ss=s;
    reverse(all(s));
    n=SZ(s);
    int cnt=0,l=0;
    for(int j=0;j<n;j++){
        auto i=s[j];
        a[l][i-'a']=j;
        if(!v[i-'a']){
            v[i-'a']=1;
            cnt++;
        }

        if(cnt==26){
            l++;
            b[l]=j;
            cnt=0;
            memset(v,0,sizeof v);
        }
    }
    string ans="";
    int g;
    for(int i=0;i<26;i++){
        if(!v[i]){
            ans.pb(i+'a');
            g=i;
            break;
        }
    }
    for(int i=l-1;i>=0;i--){
        int j=a[i][g]-1;
//        cout<<j<<" "<<b[i]<<endl;
        memset(v,0,sizeof v);
        while(j>b[i]){
            v[s[j]-'a']=1;
            j--;
        }
        for(int j=0;j<26;j++){
            if(!v[j]){
                ans.pb(j+'a');
                g=j;
                break;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 1668
#include <bits/stdc++.h>
using intl = long long;
using itnl = long long;
using itn = int;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define rrep(i, n) for(intl i = (intl)(n) - 1; i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define rrepi(i, a, b) for(intl i = (intl)(a); i > (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define itn int
#define double ld
#define pb push_back
#define mp make_pair
#define pii pair<intl,intl>
const intl INF = 1LL << 60;
const intl MOD = 1e9+7;
const ld EPS = 1.0e-14;//-9
const ld PI = 3.141592653589;
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) {a = b; return true;} return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) {a = b; return true;} return false; }
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){ if(!b)return a; return gcd(b, a % b); }
intl lcm(intl a,intl b){ return a / gcd(a, b) * b; }
intl digit10(intl a){
    intl b = 0;
    do{
        a /= 10;
        b++;
    }while(a);
    return b;
}

signed main(){
    cout << fixed << setprecision(10);
    intl n;
    cin >> n;
    intl h[n];
    cin(i,h);
    intl dp[n];
    rep(i,n)dp[i] = INF;
    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]);
    repi(i,2,n){
        chmin(dp[i],dp[i - 1] + abs(h[i] - h[i - 1]));
        chmin(dp[i],dp[i - 2] + abs(h[i] - h[i - 2]));
    }
    cout << dp[n - 1] << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include<vector>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main() {
  int a,b;
  char c;
  cin>>a>>b;
  rep(i,a){
    cin>>c;
    if(i==b-1)c=tolower(c);
    cout<<c;
  }
}

Measured memory_bytes: 384
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

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

using namespace std;

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

struct Puzzle{
  int field[9];
  int space;
  int turn;


  bool operator < (const Puzzle& a) const{
    rep(i,9){
      if(a.field[i] == field[i]) continue;
      return field[i] > a.field[i];
  }
    return false;
  }
};

bool check(Puzzle p){
  rep(i,9){
    if(p.field[i] != i+1) return false;
  }
  return true;
}

int solve(Puzzle in){
  queue<Puzzle> q;
  map<Puzzle, bool> mp;

  q.push(in);
  mp[in] = true;

  while(!q.empty()){
    Puzzle p = q.front(); q.pop();
    if(check(p)) return p.turn;
    int x = p.space % 3;
    int y = p.space / 3;
    rep(i, 4){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx < 0 || 2 < nx || ny < 0 || 2 < ny) continue;
      Puzzle tmp = p;
      swap(tmp.field[p.space], tmp.field[3 * ny + nx]);
      tmp.space = 3 * ny + nx;
      if(mp[tmp] == false){
    mp[tmp] = true;
    tmp.turn++;
    q.push(tmp);
      }
    }
  }
  return -1;
}



signed main(){
  Puzzle in;

  rep(i,9){
    cin >> in.field[i];
    if(in.field[i] == 0){
      in.field[i] = 9;
      in.space = i;
    }
  }

  in.turn = 0;
  cout << solve(in) << endl;
}



Measured memory_bytes: 20496
import sys
N = int(input())
D = list(map(int, input().split()))

Ans = 0
number = 1
n_count = 0
b_count = 1

newD = sorted(D)
if N == 1:
  Ans = 1
  print(Ans)
  sys.exit()

if D[0] != 0 or newD[1] != 1:
  print(Ans)
  sys.exit()
else:
  
  for i in range(1,N):
    if newD[i] == number:
      n_count = n_count + 1
    elif newD[i] == number + 1:

      if number == 1:
        Ans = 1
        #print(Ans)
      else:
        Ans = Ans * (b_count ** n_count)
        if Ans > 998244353:
          Ans = Ans % 998244353
        #print(Ans)
        
      number = number + 1
      b_count = n_count
      n_count = 1
    else:
      Ans = 0
      print(Ans)
      sys.exit()

  if number == 1:
    Ans = 1
  else:
    Ans = Ans * (b_count ** n_count)
    Ans = Ans % 998244353
  print(Ans)

Measured memory_bytes: 14396
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

struct Node {
	Node* ch[26];
	int cnt = 0;
};

const int pSize = 1000000;
Node *pool = nullptr; int pLast = pSize;

Node* alloc() {
	if (pLast == pSize) {
		pool = new Node[pSize];
		pLast = 0;
	}
	Node* ret = &(pool[pLast++]);
	for (int i = 0; i < 26; ++i) ret->ch[i] = nullptr;
	ret->cnt = 0;
	return ret;
}

int N;
string S[202020];
char buf[1010101];
Node* trie;
i64 ans = 0;

vector<int> visit(Node* nd) {
	vector<int> ret(27, 0);
	for (int i = 0; i < 26; ++i) if (nd->ch[i]) {
		Node* ch = nd->ch[i];
		auto tmp = visit(ch);
		for (int j = 0; j < 27; ++j) {
			if (i == j) ret[j] += tmp[26];
			else ret[j] += tmp[j];
		}
	}
	for (int i = 0; i < 26; ++i) if (nd->ch[i]) {
		Node* ch = nd->ch[i];
		ans += (i64)ret[i] * ch->cnt;
	}
	ret[26] += nd->cnt;
	return ret;
}

int main()
{
	scanf("%d", &N);
	trie = alloc();

	for (int i = 0; i < N; ++i) {
		scanf("%s", buf);
		S[i] = buf;

		Node* nd = trie;
		for (int j = S[i].size() - 1; j >= 0; --j) {
			int x = (S[i][j] - 'a');
			if (nd->ch[x] == nullptr) nd->ch[x] = alloc();
			nd = nd->ch[x];
		}
		++nd->cnt;
	}
	visit(trie);

	printf("%lld\n", ans - N);
	return 0;
}


Measured memory_bytes: 417524
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  lint a, b, c, d; cin >> a >> b >> c >> d;
  lint ans = -1e18;
  ans = max(ans, a * c);
  ans = max(ans, a * d);
  ans = max(ans, b * c);
  ans = max(ans, b * d);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3184
package main

import (
   "fmt"
   "os"
   "bufio"
   "strconv"
   "sort"
)

const MaxBuf = 200100
var buf []byte
var sc = bufio.NewScanner(os.Stdin)

func init() {
   sc.Split(bufio.ScanWords)
   sc.Buffer(buf,MaxBuf)
}

func readString() string {
   sc.Scan()
   return sc.Text()
}

func readInt64() int64 {
   sc.Scan()
   r,_ := strconv.ParseInt(sc.Text(),10,64)
   return r
}

func readInt() int {
   sc.Scan()
   r,_ := strconv.Atoi(sc.Text())
   return r
}

func main() {
	n := readInt()
	a := make([]int,n)
	for i := 0; i < n ; i++ {
		a[i] = readInt()
	}
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	ans := 0
	for i,v := range a {
		if (i % 2 == 0) {
			ans += v
		} else {
			ans -= v
		}
	}

	fmt.Println(ans)
	
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define watch(x) cerr <<"at line "<< __LINE__ <<", " << #x << " = " << x << "\n"
using namespace std;

int main()
{
    int n;
    cin >> n;
    int ara[] = {500, 5, 1};
    int i  = 0;
    long long ans = 0LL;

    while(n != 0) {
        if(ara[i] <= n) {
            n -= ara[i];
            ans += (ara[i] == 500)? 1000:((ara[i]/5)*5);
            //watch(ara[i]);
        }
        else i++;
    }

    cout << ans << "\n";
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
#include <string>
using namespace std;

int main() {
  int A, B;
  cin >> A >> B;
  int ans;
  if (B % A == 0) {
	  ans = A + B;
	} else {
	  ans = B - A;
	}
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
using System;

namespace paiza
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int A = int.Parse(s[0]);
            int B = int.Parse(s[1]);
            int ans = 0;
            ans += (B / 1000 - A / 1000 + 1) * 10;
            if (A % 100 > A / 10000 + ((A / 1000) % 10) * 10)
            {
                ans -= (A / 100) % 10+1;
            }
            else
            {
                ans -= (A / 100) % 10;
            }
            if (B % 100 >= B / 10000 + ((B / 1000) % 10) * 10)
            {
                ans -= 9 - (B / 100) % 10;
            }
            else
            {
                ans -= 10 - (B / 100) % 10;
            }
            Console.WriteLine(ans);
        }
    }
}


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

int main() {
  int N;
  cin >> N;
  
  int odd = 0;
  
  if (N % 2 == 1){
    odd = N / 2 + 1;
    cout << (double) odd / N << endl;
  }
  else {
    odd = N / 2;
    cout << (double) odd / N << endl;
  }
}

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

public class Hello {
  public static void Main() {
    //使わないのはコメントアウトしないとエラー
    var num = NumInput();
//    var text = StringInput();        
    int res = 0;
    for(int i = 0; i <= num[0]; i++){
      var sum = 0;
      var n = i;
      while(n > 0){
		sum += n % 10;
        n /= 10;
      }
      if (sum >= num[1] && sum <= num[2]) res += i;
//      Result(i +" " +sum);
    }
    Result(res);

  }
  
  
  static int[] NumInput(){
    var input_line = Console.ReadLine().Split(' ');
    return input_line.Select(int.Parse).ToArray();
  }
  static string[] StringInput(){
    return Console.ReadLine().Split(' ');
  }

  static void Result(string text){
    Console.WriteLine( text );
  }   
  static void Result(int num){
    Console.WriteLine( num );
  }
  static void Result(float num){
    Console.WriteLine( num );
  }
}

Measured memory_bytes: 13268
N = int(input())
a = list(map(int, input().split()))

ans = 0
while True:
    sub = [0] * N
    for i in range(N):
        sub[i] = (a[i] - (N - 1) - 1) // N + 1
    sum_sub = sum(sub)
    if sum_sub == 0:
        break
    ans += sum_sub
    for i in range(N):
        a[i] -= N * sub[i] - (sum_sub - sub[i])

print(ans)


Measured memory_bytes: 41580
let rec solve red green blue rest =
    match rest with
    | 0 -> if red < green && green < blue then "Yes" else "No"
    | rest ->
        if red >= green then solve red (green * 2) blue (rest - 1)
        else if green >= blue then solve red green (blue * 2) (rest - 1)
        else "Yes"

let [| red; green; blue |] =
    stdin.ReadLine().Split(" ") |> Array.map int

stdin.ReadLine()
|> int
|> solve red green blue
|> printfn "%s"

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

int main() {
  int a, b, x;
  cin >> a >> b;
  x = a + b;
  if (x % 2 == 0) {
    cout << x / 2 << endl;
  }
  else {
    cout << x / 2 + 1 << endl;
  }
}


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


int main() {
    string c;
    cin>>c;
    
    if(c[1]=='B'){
        cout<<"ARC"<<endl;
    }else{
        cout<<"ABC"<<endl;
    }


}


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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define FOR(NAME, START, NUM) for (ll NAME = START; NAME < (NUM); NAME++)
#define REP(NAME, NUM) for (ll NAME = 0; NAME < (NUM); NAME++)
#define BREP(NAME, NUM) for (ll NAME = (NUM)-1; NAME >= 0; NAME--)
#define ALL(NAME) (NAME).begin(), (NAME).end()
const ll INF =1000000000000000;

int main(){
  int a,p;
  cin>>a>>p;
  cout<<(3*a+p)/2<<endl;
}

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

public class Main {

	public static void main(String[] args) {
		BufferedReader inMsg = new BufferedReader(new InputStreamReader(System.in));
		String line = "";
		try {
			while ((line = inMsg.readLine()) != null) {
				String[] ab = line.split(" ");
				Integer a = 0;
				Integer b = 0;
				Integer sqr = 0;
				Integer liner = 0;
				
				a = Integer.parseInt(ab[0]);
				b = Integer.parseInt(ab[1]);
				sqr = a * b;
				liner = a * 2 + b *2;

				System.out.println(sqr + " " + liner);
				
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

Measured memory_bytes: 24196
N, = map(int, input().split())
X = list(map(int, input().split()))
A = X[:]
B = X[:]
for i in range(N):
    A[i] += i+1
    B[i] -= i+1
d = dict()
for i in range(N):
    x = -A[i]
    if x not in d:
        d[x] = 0
    d[x] += 1
r = 0
for b in B:
    if b in d:
        r += d[b]
print(r)
    


Measured memory_bytes: 114264
#include <bits/stdc++.h>
#include <stdio.h>
#include <numeric>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
#define INF 9223372036854775807
#define pairint pair<int,int>
int num[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
bool uru(int checkyear){if(checkyear%4==0){if(checkyear%100!=0||checkyear%400==0)return true;}return false;}
int gcd( int x, int y ){return y ? gcd(y, x%y) : x;}
bool pairCompare(const pairint& firstElof, const pairint& secondElof)
{
  if(firstElof.second!= secondElof.second)    return firstElof.second> secondElof.second;
  else return firstElof.first< secondElof.first;
}
signed main() {
int x=0,y=0,z=0,w=0,n=0,m=0;
string a,b;
std::cin >> x>>y;
if(y==1)std::cout << 0 << '\n';
else if(x>=y)std::cout << 1 << '\n';
else {
for(int i=1;;i++){
    if(y<=x*i-(i-1)){
      std::cout << i << '\n';
      break;
}
  }
}
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
 ll n,k;
 cin>>n>>k;
 vector<ll> a(n);
 ll mod=1e9+7;
 for(ll i=0;i<n;i++) cin>>a[i];
 vector<vector<ll>> dp(n+1,vector<ll>(k+1));
 dp[n][0]=1;
 vector<int> cur(k+1);
 cur[0]=1;
 for(int i=1;i<=k;i++){
  cur[i]+=cur[i-1];
 }
 for(ll i=n-1;i>=0;i--){
  for(ll j=0;j<=k;j++){
   dp[i][j]=cur[j];
   if(j>a[i]) dp[i][j]-=cur[j-a[i]-1];
   if(dp[i][j]<0) dp[i][j]+=mod;
  }
  cur[0]=dp[i][0];
  for(ll j=1;j<=k;j++){
   cur[j]=dp[i][j];
   cur[j]=(cur[j]+cur[j-1])%mod;
  }
 }
 cout<<dp[0][k]<<endl;
 return 0;
}

Measured memory_bytes: 80256
#include <cstdio>

int main(void)
{
    int n,a,b;

    //freopen("x.in","r",stdin);

    scanf("%d %d %d",&n,&a,&b);
    if(a > b)
        return puts("0"),0;
    if(n == 1)
        return (a == b ? puts("1") : puts("0")),0;
    n -= 2;
    printf("%lld\n",1ll * n * b - 1ll * n * a + 1);

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define boost ios::sync_with_stdio(false); cin.tie(0)
#define ll              long long int
#define ld              long double
#define mk              make_pair
#define pb              push_back
#define f               first
#define s               second
#define fo(i,a,b)       for(i=a;i<b;i++)
#define foe(i,a,b)      for(i=a;i<=b;i++)
#define all(x)          x.begin(),x.end()
#define vi              vector<int>
#define vl              vector <long long int>
#define pii             pair <int,int>
#define pll             pair <long long int, long long int>
#define vpii            vector< pair<int,int> >
#define vpll            vector < pair <long long int,long long int> >
#define MOD             1000000007
using namespace std;
const int inf = INT_MAX;
const ll inf64 = LLONG_MAX;
ll n;
char reVal(int num)
{
	if (num >= 0 && num <= 9)
		return (char)(num + '0');
	else
		return (char)(num - 10 + 'A');
}

string fromDeci(long long int inputNum, int base)
{
	string res = "";
	while (inputNum > 0)
	{
		res += reVal(inputNum % base);
		inputNum /= base;
	}
	reverse(res.begin(), res.end());
	res = string(n-res.length(),'0') + res;
	return res;
}

int main()
{
    boost;
    ll m,x;
    ll i,j,k;
    cin >> n >> m >> x;
    ll cost[n],arr[n][m];
    bool poss = false;

    fo(i,0,n)
    {
    	cin >> cost[i];
    	fo(j,0,m)
    	{
    		cin >> arr[i][j];
    	}
    }
    ll minn = inf64;
    fo(i,1,(1<<n))
    {
    	string s;
    	s = fromDeci(i,2);
    	// cout << s << '\n';
    	ll book[m];
    	fo(j,0,m)book[j] = 0;
    	ll sum = 0;
    	fo(j,0,s.length())
    	{
    		if(s[j] == '1')
    		{
    			sum += cost[j];
    			fo(k,0,m)
    			{
    				book[k] += arr[j][k];
    			}
    		}
    	}
    	bool temp = true;
    	fo(j,0,m)
    	{
    		if(book[j] < x)
    		{
    			temp = false;
    			break;
    		}
    	}
    	if(temp)
    	{
    		poss = true;
    		minn = min(minn,sum);
    	}
    }
    if(poss)
    {
    	cout << minn;
    }
    else cout << -1;



    
    return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <map>
#include <numeric>
#define ll long long
using namespace std;
using p = pair<ll, ll>;
ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0, 1, 0, -1};

int main(){
    ll n, w;
    cin >> n >> w;
    vector<p> vp;
    ll MIN = 1e+11, MAX = 0;
    for(ll i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        vp.push_back(p(a, b));
        MAX = max(MAX, a); MIN = min(MIN, a);
    }
    vector<ll> x, y, z, v;
    for(ll i = 0; i < n; i++){
        if(vp[i].first==MAX) v.push_back(vp[i].second);
        else if(vp[i].first==MIN) z.push_back(vp[i].second);
        else if(vp[i].first==MIN+1) y.push_back(vp[i].second);
        else if(vp[i].first==MIN+2) x.push_back(vp[i].second);
    }
    sort(v.begin(), v.end(), greater<ll>());
    sort(x.begin(), x.end(), greater<ll>());
    sort(y.begin(), y.end(), greater<ll>());
    sort(z.begin(), z.end(), greater<ll>());
    //cout << x.size() << " " << y.size() <<" " << z.size() << endl;
    vector<p> a, b, c, d;
    a.push_back(p(0,0)); b.push_back(p(0,0));
    c.push_back(p(0,0)); d.push_back(p(0,0));
    for(ll i = 0; i < v.size(); i++){
        if(i==0) a.push_back(p((i+1)*MAX, v[i]));
        else  a.push_back(p((i+1)*MAX, a[i].second+v[i]));
    }
    for(ll i = 0; i < x.size(); i++){
        if(i==0) b.push_back(p((i+1)*(MIN+2), x[i]));
        else  b.push_back(p((i+1)*(MIN+2), b[i].second+x[i]));
    }
    for(ll i = 0; i < y.size(); i++){
        if(i==0) c.push_back(p((i+1)*(MIN+1), y[i]));
        else  c.push_back(p((i+1)*(MIN+1), c[i].second+y[i]));
       // cout << b[i].first << " " << b[i].second << endl;
    }
    for(ll i = 0; i < z.size(); i++){
        if(i==0) d.push_back(p((i+1)*MIN, z[i]));
        else  d.push_back(p((i+1)*MIN, d[i].second+z[i]));
        //cout << c[i].first << " " << c[i].second << endl;
    }
    ll ans = 0;
    //cout << a.size() << " " << b.size() << " " << c.size() <<" " << d.size() << endl;
    for(ll i = 0; i < a.size(); i++){
        for(ll j = 0; j < b.size(); j++){
            for(ll k = 0; k < c.size(); k++){
                for(ll l = 0; l < d.size(); l++){
                //cout << i << " " << j << " " << k << " " <<  a[i].second+b[j].second+c[k].second << endl;
                if(a[i].first+b[j].first+c[k].first+d[l].first <= w)
                    ans = max(ans, a[i].second+b[j].second+c[k].second+d[l].second);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
//確認用
#pragma region header
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr ll inf = INT32_MAX/2;
constexpr ll INF = LLONG_MAX/2;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------テンプレート------------------ */
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */
#pragma endregion
int main() {
    int n;cin >> n;
    vi h(n);
    rep(i, n) cin >> h[i];
    for(int i=1;i<n ;i++){
		if(h[i]>h[i-1])
			h[i]--;
		else if(h[i]<h[i-1]){
			cout<<"No\n";
			return 0;
		}
	}
    cout << "Yes\n" << endl;
    return 0;
}

Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
using ll = long long;
ll com(ll n){
  return n*(n-1)/2;
}

int main(){
  ll n,ans=0;
  cin>>n;
  vector<ll> a(n);
  rep(i,n)cin>>a[i];
  vector<ll> coun(n);
  rep(i,n)coun[i]=0;
  rep(i,n)coun[a[i]-1]++;
  rep(i,n) ans += com(coun[i]);
  rep(i,n){
   ll m=0,o=0;
    m=com(coun[a[i]-1]-1);
    o=com(coun[a[i]-1]);
     cout<<ans-o+m<<endl;
  }
}


Measured memory_bytes: 5760
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
int n,a[101010],ans;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	for(int i=1;i<=a[n-1];i++)
	{
		int now=upper_bound(a,a+n,i)-a;
		if(now==n/2)
		{
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
// -----------------------------------
// Author     : MatsuTaku
// Country    : Japan
// Created    : 05/02/20 20:07:37
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  ll a,b,n; cin>>a>>b>>n;
  auto f = [&](ll x) {
    return (a*x)/b - a*(x/b);
  };
  cout << f(min(b-1,n)) << endl;

  return 0;
}


Measured memory_bytes: 3656
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	arr := strings.Split(sc.Text(), " ")
	x, _ := strconv.Atoi(arr[0])
	a, _ := strconv.Atoi(arr[1])
	b, _ := strconv.Atoi(arr[2])

	//fmt.Println(x, a, b)

	if b-a <= 0 {
		fmt.Println("delicious")
	} else if b-a <= x {
		fmt.Println("safe")
	} else {
		fmt.Println("dangerous")
	}

}


Measured memory_bytes: 640
#include<stdio.h>
using namespace std;
#include<algorithm>
int main(void)
{
	int A, B;
	scanf("%d%d", &A, &B);
	if (A <= 0 && B >= 0)
		printf("Zero");

	else if (A < 0 && B < 0) {
		if (-1 * (A + B) % 2 == 0) {
			printf("Negative");
		}
		else
			printf("Positive");
	}

	else
		printf("Positive");

	return 0;
}

Measured memory_bytes: 760
from itertools import product
n, m = map(int, input().split())
xyz = [list(map(int, input().split())) for _ in range(n)]
pm = (1, -1)
if m == 0:
    print(0)
else:
    ans = -1
    for a in product(*[pm] *3):
        xyz.sort(key=lambda y:sum(list(map(lambda x: x[0]*x[1], zip(a, y)))))
        x, y, z = zip(*xyz[:m])
        ans = max(ans, abs(sum(x)) + abs(sum(y)) + abs(sum(z)))
    print(ans)

Measured memory_bytes: 3476
#include<bits/stdc++.h>
  
#define lol long long
#define gcd(x,y) __gcd(x,y)
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define fixed fixed<<setprecision(14)
using namespace std;
using pii=pair<int,int>;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class A> inline lol abs(A &a) { return (a < 0 ? -a : a); }
bool inLine(int x,int y,int mx,int my){return (x>=0&&y>=0&&x<mx&&y<my);}
const lol inf=(1LL<<62);
const lol MOD=(1e9)+7;
const lol mod=998244353;
const int dx[]={1,0,-1,0,1,1,-1,-1};
const int dy[]={0,1,0,-1,1,-1,1,-1};
lol n,m,k,r;
int kaku[10000001];
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >>n;
  kaku[1]=1;
  lol ans=0;
  for(int i=1;i<=n;i++){
    lol tmp=(n/i);
    tmp=tmp*(tmp+1)/2;
    ans+=tmp*i;
  }
  cout <<ans<<'\n';
  return(0);
}

Measured memory_bytes: 3664
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
using namespace std;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    // cout << fixed << setprecision(20);

    int a,b,c;cin >> a >> b >> c;
    if(a + b + c <= 21)cout << "win" << '\n';
    else cout << "bust" << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
int main()
{
    string N;
    cin >> N;
    int t = N.size();
    int K;
    cin >> K;
    vector<vector<lint>> dp0(t+1, vector<lint>(K+2));
    vector<vector<lint>> dp1(t+1, vector<lint>(K+2));
    dp0[0][1] = 1;
    REP(i, t) {
        int x = N[i] - '0';
        REP(j, K+1) {
            dp0[i+1][j+1] = dp0[i][j] * (x != 0) + dp0[i][j+1] * (x == 0);
            dp1[i+1][j+1] = dp0[i][j] * max(0, x-1) + dp1[i][j] * 9 + dp0[i][j+1] * (x != 0) + dp1[i][j+1];
        }
    }
 
    cout << (dp0[t][K+1] + dp1[t][K+1]) << endl;
}

Measured memory_bytes: 256
from collections import defaultdict

N = int(input())
dic = defaultdict(int)
for l in map(int, input().split()):
  dic[l] += 1

if len(dic) < 3:
  print(0)
  exit()

dic = sorted(dic.items())

ans = 0
for i in range(len(dic)-2):
  Li = dic[i][0]
  cnt_i = dic[i][1]
  for j in range(i+1, len(dic)-1):
    Lj = dic[j][0]
    cnt_j = dic[j][1]
    for k in range(j+1, len(dic)):
      Lk = dic[k][0]
      cnt_k = dic[k][1]
      
      if ((Li+Lj) > Lk) and ((Li+Lk) > Lj):
        ans += cnt_i * cnt_j * cnt_k
print(ans)

Measured memory_bytes: 9488
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;
#define int ll

struct UnionFind{
    vector<int> par;
    vector<int> siz;
    
    UnionFind(int n){
        init(n);
    }
    
    //n要素で初期化
    void init(int n){
        par.resize(n);
        siz.resize(n);
        for(int i = 0; i < n; i++){
            par[i] = i;
            siz[i] = 1;
        }
    }
    
    //木の根を求める
    int root(int x){
        if(par[x] == x) return x;
        else return par[x] = root(par[x]);
    }
    
    //xとyの属する集合を併合
    void unite(int x, int y){
        x = root(x);
        y = root(y);
        if(x == y) return;
        if(siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
    }

    bool same(int x, int y){
        return root(x) == root(y);
    }

    int size(int x){
        return siz[root(x)];
    }
};

signed main(){
    int n,m;
    cin >> n >> m;
    int a[m],b[m];
    REP(i,m){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
    UnionFind uf(n);
    ll num = n * (n - 1) / 2;
    ll ans[m];
    for(int i = m - 1; i >= 0; i--){
        ans[i] = num;
        if(uf.same(a[i], b[i]) == false){
            num -= uf.size(a[i]) * uf.size(b[i]);
            uf.unite(a[i], b[i]);
        }
    }
    REP(i,m){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 5248
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

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

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    vector<ll> B(N);
    bool f = (N % 2 == 0) ? true: false;
    REP(i, N / 2) B[i] = A[N - 1 - 2 * i];
    if (!f) {
        B[N / 2] = A[0];
        rep(i, 0, N / 2) B[N / 2 + 1 + i] = A[2 * i + 1];
    }else{
        rep(i, 0, N / 2) B[N / 2 + i] = A[2 * i];
    }

    REP(i, N) cout << B[i] << " ";
    cout << endl; 
    return 0;
}

Measured memory_bytes: 5376