akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
typedef long long lint;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

lint tikaiRight(vector<lint>& v, lint pos) {
    auto itr = lower_bound(v.begin(), v.end(), pos);
    if (itr == v.end()) return 99999999999;
    return *itr;
}
lint tikaiLeft(vector<lint>& v, lint pos) {
    auto itr = lower_bound(v.begin(), v.end(), pos);
    if (itr == v.begin()) return 99999999999;
    return *--itr;
}
lint tikai(vector<lint>& v, lint pos) {
    auto left = tikaiLeft(v,pos);
    auto right = tikaiRight(v,pos);
    if (abs(pos - left) < abs(pos - right)) return left;
    return right;
}

int main() {
    int a,b,q; cin >> a >> b >> q;
    vector<lint> s(a); rep(i,a) cin >> s[i];
    vector<lint> t(b); rep(i,b) cin >> t[i];
    vector<lint> x(q); rep(i,q) cin >> x[i];
    rep(i, q) {
        lint ans = 999999999999999;
        lint cost = 0;
        lint pos;
        lint next;
        pos = x[i];
        next = tikaiLeft(s,x[i]);
        cost = abs(pos - next);
        pos = next;
        cost += abs(pos - tikai(t, pos));
        ans = min(ans,cost);

        pos = x[i];
        next = tikaiRight(s,x[i]);
        cost = abs(pos - next);
        pos = next;
        cost += abs(pos - tikai(t, pos));
        ans = min(ans,cost);
        
        pos = x[i];
        next = tikaiLeft(t,x[i]);
        cost = abs(pos - next);
        pos = next;
        cost += abs(pos - tikai(s, pos));
        ans = min(ans,cost);

        pos = x[i];
        next = tikaiRight(t,x[i]);
        cost = abs(pos - next);
        pos = next;
        cost += abs(pos - tikai(s, pos));
        ans = min(ans,cost);
        
        cout << ans << endl;
    }

}

Measured memory_bytes: 5552
#include <iostream> // C++の入出力
#include <stdio.h> // C の入出力
#include <algorithm> // sort などのアルゴリズム
#include <string.h> // C の文字列用
#include <ctype.h> // C の文字種用
#include <string> // C++の文字列
#include <math.h>
#include <sstream>
#include <cstdio>
#include <queue>
using namespace std;
char fel[20][20];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void dfs(int i,int x,int y);
int h,w,sx,sy,cnt=1;
int main(void){
    while(true){
        cin>>w>>h;
        if(h+w==0)break;
        for(int s=0;s<h;s++){
            string in;
            cin>>in;
            for(int i=0;i<w;i++){
                fel[s][i]=in[i];
                if(fel[s][i]=='@'){
                    sx=i;
                    sy=s;
                }
            }
        }
        dfs(0,sx,sy);
        cout<<cnt<<endl;
        cnt=1;
    }
    return 0;
}

void dfs(int i,int x,int y){
    fel[y][x]='#';
    for(int s=0;s<4;s++){
        int nx=x+dx[s];
        int ny=y+dy[s];
        if(nx>=0&&nx<w&&ny>=0&&ny<h&&fel[ny][nx]=='.'){
            cnt++;
            dfs(i+1,nx,ny);
        }  
    }
    return;
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using std::cout;
using std::endl;
using std::cin;

int main(){
	std::string s; cin >> s;
	
	std::stack<char> st; int count = 0;
	for(int i = 0; i < s.size(); i++){
		if(st.empty()) st.push(s[i]);
		else if(st.top() == 'S' and s[i] == 'T'){
			st.pop();
			count += 2;
		}else{
			st.push(s[i]);
		}
	}
	
	cout << s.size() - count << endl;
	return 0;
}


Measured memory_bytes: 644
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a[3];
	int k;
	cin>>a[0]>>a[1]>>a[2]>>k;
	sort(a,a+3);
	for(int i=0;i<k;i++)a[2]*=2;
	cout<<a[0]+a[1]+a[2]<<endl;
}

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

int main(){
	string n; cin >> n;
	n[0] == '7' || n[1] == '7' || n[2] == '7' ? cout << "Yes" << endl : cout << "No" << endl;
}


Measured memory_bytes: 3596
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
    ll N,K;
    cin >> N >> K;
    ll ans=K;
    for(ll i=1;i<N;i++){
      ans*=K-1;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define MAXN 3005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef long double db;
int n;
db p[MAXN];
db dp[MAXN][MAXN];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%Lf",&p[i]);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++) dp[i][j]=p[i]*(dp[i-1][j-1])+(1-p[i])*dp[i-1][j];
    }
    db ans=0.0;
    for(int j=1;j<=n;j++) if(j>n-j) ans+=dp[n][j];
    printf("%.15Lf\n",ans);
    return 0;
}



Measured memory_bytes: 139264
#include <stdio.h>

int main(){
	char c[2][2];
	int w,h;	
	for(h = 0;h < 3;h++){
		for(w = 0;w < 3;w++){
				scanf("%s",&c[w][h]);
			}
		}
	printf("%c%c%c",c[0][0],c[1][1],c[2][2]);
	return 0;
}

Measured memory_bytes: 128
import sys
import itertools
import copy
H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

h_cnt=[]
for s in S:
    cnt=0
    for x in s:
        if x=="#":
            cnt+=1
    h_cnt.append(cnt)

T=sum(h_cnt)

w_cnt=[]
w=0
for w in range(W):
    cnt=0
    for h in range(H):
        if S[h][w]=="#":
            cnt+=1
    w_cnt.append(cnt)

HL=list( itertools.product(range(2), repeat=H) )
WL=list( itertools.product(range(2), repeat=W) )

ans=0
for hl in HL:
    for wl in WL:
        total=copy.deepcopy(T)
        for i,h in enumerate(hl):
            if h==1:
                total-=h_cnt[i]
        for j,w in enumerate(wl):
            if w==1:
                total-=w_cnt[j]

        for i,h in enumerate(hl):
            for j,w in enumerate(wl):
                if h&w==1:
                    if S[i][j]=="#":
                        total+=1

        if total==K:
            ans+=1
print ans


Measured memory_bytes: 73892
#include<iostream> 
#include<algorithm> 
using namespace std;
 int main(){ 
int A,B,K,i,j=0; 
cin>>A>>B>>K; 
int a[200]={0}; 
for(i=A;i<A+K;i++){
 a[j]=i; j++; 
if(i==B)break; } 
for(i=B;i>B-K;i--){
 a[j]=i; j++; 
if(i==A)break; } 
sort(a,a+(2*K));
 for(i=0;i<2*K;i++){
 if((i!=0&&a[i]==a[i-1])||a[i]==0)continue; cout<<a[i]<<endl; }
 return 0; } 


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	N, K := ReadInt(), ReadInt()
	xs := ReadInts(N)

	ans := 0
	for i := 0; i < N; i++ {
		ans += 2 * Min(xs[i], Abs(xs[i]-K))
	}

	fmt.Println(ans)
}

func Abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func Min(xs ...int) int {
	min := xs[0]
	for _, x := range xs[1:] {
		if min > x {
			min = x
		}
	}
	return min
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }

func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 1844
n,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
if a[0]>x:
  ans+=a[0]-x
  a[0]=x
for i in range(1,n):
  if a[i]+a[i-1]>x:
    ans+=a[i]+a[i-1]-x
    a[i]-=a[i]+a[i-1]-x
print(ans)

Measured memory_bytes: 85760
s = input()
for i in range(len(s)):
    if i%2 == 0:
        if not(s[i] in ['R', 'U', 'D']):
            print('No')
            exit()
    else:
        if not(s[i] in ['L', 'U', 'D']):
            print('No')
            exit()
print('Yes')

Measured memory_bytes: 3060
using System.Linq;
using static System.Math;
using static System.Console;
class Z
{
	static void Main()
	{
		var I = ReadLine().Split().Select(int.Parse).ToArray();
		WriteLine(Abs(I[0] - I[1]) < Abs(I[0] - I[2]) ? "A" : "B");
	}
}


Measured memory_bytes: 11348
//----------------------------templates
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("tune=native")
    #pragma GCC target ("avx")
    //----------------------------
    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll

    #define FOR(i,j,n) for (int i=(int)(j);i<(n);i++)
    #define REP(i,n) for (int i=0;i<(int)(n);i++)
    #define REPS(i,n) for (int i=1;i<=(int)(n);i++)
    #define REPN(i,n) for (int i=(int)(n)-1;i>=0;i--)
    #define REPNS(i,n) for (int i=(int)(n);i>0;i--)

    #define I(n) scanf("%lld", &(n))
    #define LL(n) scanf("%lld", &(n))
    #define pb(n) push_back((n))
    #define mp(i,j) make_pair((i),(j))
    #define eb(i,j) emplace_back((i),(j))
    #define y0 y3487465
    #define y1 y8687969
    #define j0 j1347829
    #define j1 j234892
    #define uniq(v) v.erase( unique(v.begin(), v.end()), v.end() )

    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())

    typedef vector<int> vi;
    typedef pair<int,int> pi;
    typedef vector<pi> vpi;
    typedef vector<vi> vvi;
    typedef vector<vpi> vvpi;
    typedef vector<vvi> vvvi;

    const int mod = 1000000007;

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

int k;

void op(vi& a){
    REP(i,sz(a)) a[i]++;
    auto it = max_element(all(a));
    *it -= sz(a)+1;

    for(auto v:a) cerr << v << " ";
    cerr << endl;
}

signed main(){
    I(k);
    int n = 50;

    int nmv = (n - k%n);
    int val = k/n + (50);
    vi a = vi(n,val);
    REP(i,nmv) op(a);

    cout << n << endl;
    for(auto v:a) cout << v << " ";
    cout << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
static const int INF (1<<30);

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

  string ans;
  if (s == "Sunny") ans = "Cloudy";
  else if (s == "Cloudy") ans = "Rainy";
  else ans = "Sunny";

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
from collections import deque
import bisect

N = int(input())
table = deque()
for n in range(N):
    a = int(input())
    if n == 0:
        table.append(a)
    else:
        if a <= table[0]:
            table.appendleft(a)
        else:
            table[bisect.bisect_left(table, a)-1] = a
            
print(len(table))

Measured memory_bytes: 76840
#include <bits/stdc++.h>
using std::cerr;using std::cin;using std::cout;using std::abs;using std::min;using std::max;using std::swap;using std::map;using std::unordered_map;using std::unordered_set;using std::bitset;using std::pair;using std::set;using std::string;using std::vector;using std::sort;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _dbg(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _dbg(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_dbg(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
struct init{init(){cin.tie(0);std::iostream::sync_with_stdio(0);cout<<std::fixed<<std::setprecision(10);cerr<<std::fixed<<std::setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}

string s;
int n,a,b,c,d;
bool ok(int i){
    return i>=0&&i<n&&s[i]=='.';
}
void no(){
    cout<<"No\n";
    exit(0);
}
bool go(int x,int y){
    for(int i=x;i<y;++i)
        if(!ok(i)&&!ok(i+1))
            return 0;
    return 1;
}
int32_t main() {

    cin>>n>>a>>b>>c>>d>>s;
    --a,--b,--c,--d;
    if(c>d){
        int w=-1;
        for(int i=b;i<=d;++i){
            if(ok(i)&&ok(i-1)&&ok(i+1)){
                w=i;
                break;
            }
        }
        if(w==-1)no();
    }
    if(go(a,c)&&go(b,d))cout<<"Yes\n";
    else cout<<"No\n";


    return 0;
}


Measured memory_bytes: 592
n = input()
d = int(input())
t = len(n)
mod = 10**9 + 7
dp1 = [[0 for i in range(d)] for j in range(t)]
dp2 = [[0 for i in range(d)] for j in range(t)]

dp1[0][int(n[0])%d] += 1
for i in range(int(n[0])):
    dp2[0][i%d] += 1
    
for i in range(1,t):
    now = int(n[i])
    for j in range(10):
        if j == now:
            for k in range(d):
                dp1[i][(k+j)%d] += dp1[i-1][k]
                dp2[i][(k+j)%d] += dp2[i-1][k]
                dp1[i][(k+j)%d] %= mod
                dp2[i][(k+j)%d] %= mod
        elif j < now:
            for k in range(d):
                dp2[i][(k+j)%d] += dp1[i-1][k]
                dp2[i][(k+j)%d] += dp2[i-1][k]
                dp2[i][(k+j)%d] %= mod
        else:
            for k in range(d):
                dp2[i][(k+j)%d] += dp2[i-1][k]
                dp2[i][(k+j)%d] %= mod

print((dp1[-1][0]+dp2[-1][0]-1)%mod)

Measured memory_bytes: 93012
n,k = map(int,input().split())
l1 = list(map(int,input().split()))
l = list(i-1 for i in l1)
bit = list(0 for i in range(n))
bit[0] =1
mi = [0]
m = l[0]
er = 0
while er ==0:
  if bit[m]==1:
    a = mi.index(m)
    r = mi[a:]
    er  =1
  else:
    bit[m] = 1
    mi.append(m)
    m = l[m]
 # print(bit)
be = mi[:a]+r
#print(be,r)
if k< len(be):
  print(be[k]+1)
else:
  w = k-len(be)+1
  u = (w%len(r))-1
  print(r[u]+1)

Measured memory_bytes: 32388
#define REP(a) for(i = 0; i <= a; i++)

int compare(const void *a,const void *b) {
    return *(int*)a - *(int*)b;
}

int main(void) {
    int a,b,i,count = 0;
    scanf("%d%d",&a,&b);
    char s[a][b + 1];
    REP(a) {
        scanf("%s",s[i]);
    }
    REP(a - 1) {
        for (int j = 0; j < b; ++j) {
            if (s[i][j] == '#') {
                printf("#");
            } else {
                for (int k = -1; k < 2; k++) {
                    if (j + k < 0 || i == 0 || j + k > b - 1) {
                        continue;
                    } else if (s[i - 1][j + k] == '#') {
                        count++;
                    }
                }
                for (int k = -1; k < 2; k++) {
                    if (k == 0 || j + k < 0 || j + k > b - 1) {
                        continue;
                    } else if (s[i][j + k] == '#') {
                        count++;
                    }
                }
                for (int k = -1; k < 2; k++) {
                    if (j + k < 0 || i == a - 1 || j + k > b - 1) {
                        continue;
                    } else if (s[i + 1][j + k] == '#') {
                        count++;
                    }
                }
                printf("%d",count);
                count = 0;
            }
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long a,b,c,d;
    vector<long long> answer(4);
    cin >> a >> b >> c >> d;

    answer.at(0) = a * c;
    answer.at(1) = a * d;
    answer.at(2) = b * c;
    answer.at(3) = b * d;
    
    sort(answer.rbegin(), answer.rend());
    cout << answer.at(0) << endl;
}

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

using namespace std;

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

    cin >> n >> m;

    int s, c;
    vector<int> d(n, -1);

    if(n == 1) {
        if(m == 0) {
            printf("0\n");
            return 0;
        }
        for(int i = 0; i < m; ++i) {
            cin >> s >> c;
            if(d.at(0) == -1 || d.at(0) == c) d.at(0) = c;
            else {
                printf("-1\n");
                return 0;
            }
        }
        printf("%d\n", d.at(0));
        return 0;
    }

    for(int i = 0; i < m; ++i) {
        cin >> s >> c;
        if((d.at(s - 1) == -1 || d.at(s - 1) == c) && !(s == 1 && c == 0)) d.at(s - 1) = c;
        else {
            printf("-1\n");
            return 0;
        }
    }

    if(d.at(0) == -1) printf("1");
    else printf("%d", d.at(0));
    for(int i = 1; i < n; ++i) {
        if(d.at(i) == -1) printf("0");
        else printf("%d", d.at(i));
    }
    printf("\n");

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdint>
#include <deque>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;
using f32 = float;
using f64 = double;
using i8 = int_fast8_t;
using u8 = uint_fast8_t;
using i16 = int_fast16_t;
using u16 = uint_fast16_t;
using i32 = int_fast32_t;
using u32 = uint_fast32_t;
using i64 = int_fast64_t;
using u64 = uint_fast64_t;
inline void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main(int argc, char *argv[]) {
    fast_io();

    i32 n, m;
    cin >> n >> m;
    i32 ans = n * (n - 1) / 2;
    ans += m * (m - 1) / 2;
    cout << ans;

    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N,Q = map(int,input().split())

A = [[] for _ in range(N)]

for _ in range(Q):
    q = list(map(int,input().split()))
    if q[0] == 0:
        A[q[1]].append(q[2])
    elif q[0] == 1:
        if A[q[1]]:
            print(' '.join(map(str,A[q[1]])))
        else:
            print()
    else:
        A[q[1]] = []


Measured memory_bytes: 60480
#include<iostream>
using namespace std;
int main() {
    int n, a;
    int b[1000];
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        b[n - 1 - i] = a;
    }
    for (int i = 0; i < n; i++) {
        cout << b[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 3080
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
using namespace std;

#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(ll (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define opf(i) cout<<fixed<<setprecision(10)<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define matC(name,fnum,snum); vector<vector<char>> name((fnum),vector<char>((snum),0));
#define debugP int debug_point; cin>>debug_point;
#define FI first
#define SE second
const ll MOD= 1e9 + 7;

//
void solve(long long N, long long K, std::string S){
  /*
  ll ans=0;
  ll cnt=0;
  ll flag=0;
  ll ft=1;
  char pre=S[0];
  repf(i,1,N){
    if(S[i]==pre){
      if(flag==0){
        ans++;
        flag=1;
      }else{
        ans++;
      }
    }else{
      pre=S[i];
      if(flag==1&&ft==0){
        cnt++;
        flag=0;
      }
      ft=0;
    }
  }
  op(ans);
  op(cnt)
  ans+=min(K,cnt)*2;
  ans+=max((K-cnt),(ll)0);
  op(ans)
  */
  ll ans=0;
  char pre=S[0];
  ll cnt=0;
  repf(i,1,N){
    if(pre!=S[i])cnt++;
    pre=S[i];
  }
  ans+=(N-1-cnt);
  ans+=min(K*2,cnt);
  op(ans)
}

// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::string S;
    std::cin >> S;
    solve(N, K, S);
    return 0;
}


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

int check(int h , int a)
{
  if(h < 1)
    return 0;
  return 1+check(h-a, a);
}

int main()
{
  int h , a;
  cin >> h >> a;
  cout << check(h , a);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    ll N;
    cin >> N;
    ll cur = N;
    while(N){
        if(cur * (cur - 1) / 2 < N){
            cout << cur << endl;
            N -= (cur);
        }
        cur--;
        
    }
    
    return 0;
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
d = LIST()

d = sorted(d)

if d[len(d)//2] - d[len(d)//2 - 1] == 0:
	print(0)
else:
	print(d[len(d)//2] - d[len(d)//2 - 1])

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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

const int MAX_N = 1 << 17;
const ll INT_MA = pow(2,31) - 1;

// セグメント木を持つグローバル変数
int n, dat[2*MAX_N - 1];

// 初期化
void init(int n_){
    // 簡単のため要素数を2のべき乗に
    n = 1;
    while(n < n_) n *= 2;
    // 全ての値をINT_MAXに
    rep(i,2*n-1) dat[i] = INT_MA;
}

// k番目の値をaに変更
void update(int k, int a){
    // 葉の節点
    k += n-1;   // 根をインデックス0になるように並べ替えた時の葉の節点のインデックスはこのようになる
    dat[k] = a; // 葉の節点の値を指定のものに変更する
    // 登りながら更新(根にたどり着いたところで終了する)
    while(k > 0){
        k = (k-1) / 2;
        dat[k] = min(dat[k*2 + 1], dat[k*2 + 2]);
    }
}

// k: 節点の番号、l r: その節点が[l,r)に近づいていることを示す
// min[l,r)
int query(int a, int b, int k, int l, int r){
    // [a,b)と[l,r)が交差しなければ、INT_MAX
    if(r<=a || b<=l){
        return INT_MA;
    }
    // [a,b)が[l,r)を完全に含んでいれば、この節点の値を返す
    if(a <= l && r <= b){
        return dat[k];
    }else{
        // そうでなければ2つの子の最小値
        int vl = query(a, b, k*2+1, l, (l+r) / 2);  // 検索範囲を前半分にする
        int vr = query(a, b, k*2+2, (l+r)/2, r);    // 検索範囲を後半分にする
        return min(vl, vr);
    }
}

// min[l,r]
int query(int l, int r){
    return query(l,r+1, 0, 0, n);
}

int main()
{
    cin >> n; int q; cin >> q;
    init(n);    // セグメント木を表す配列の構築
    rep(_,q){
        int com; cin >> com;
        if(com == 0){
            int x, y; cin >> x >> y;
            update(x,y);
        }else if(com == 1){
            int x,y; cin >> x >> y;
            cout << query(x,y) << endl;
        }
    }
}


Measured memory_bytes: 4120
import math
dis_sum =0
ans =0
root_num =0

n = int(input())
now =n
distance_list=[]
for i in range(n):
    distance_list.append(list(map(int, input().split())))

#距離を計算する
for i in range(n-1):
    for j in range(i+1,n):
   
        x_dis = (distance_list[i][0] - distance_list[j][0]) **2
        y_dis = (distance_list[i][1] - distance_list[j][1]) **2
        city_dis = math.sqrt(x_dis + y_dis)
        dis_sum += city_dis


ans = 2/n * dis_sum
print(ans)
    

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define N 1000000
vector<pair<ll,ll> >g[N];
typedef pair<ll,ll> P;
priority_queue<P,vector<P>,greater<P> >Q;
ll d[N];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    ll n,m;
    cin>>n>>m;
    for(int i=1;i<n;i++){
	g[i+1].push_back(make_pair(i,0));
    }
    for(int i=0;i<m;i++){
	ll a,b,c;
	cin>>a>>b>>c;
	g[a].push_back(make_pair(b,c));
    }
    for(int i=1;i<=n;i++)d[i]=1e17;
    Q.push(make_pair(0,1));
    while(!Q.empty()){
	ll x=Q.top().second;
	ll cost=Q.top().first;
	Q.pop();
	if(d[x]<=cost)continue;
	d[x]=cost;
	for(auto y:g[x]){
	    Q.push(make_pair(cost+y.second,y.first));
	}
    }
    if(d[n]==1e17)d[n]=-1;
    cout<<d[n]<<endl;
}



Measured memory_bytes: 33784
#include<iostream>

using namespace std;

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

    int x[n];
    int y[n];
    int z[n];

    for(int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i] >> z[i];
    }

    for(int j = 0; j < n; j++)
    {
        if(x[j] * x[j] == y[j] * y[j] + z[j] * z[j]
        || y[j] * y[j] == z[j] * z[j] + x[j] * x[j] 
        || z[j] * z[j] == x[j] * x[j] + y[j] * y[j])
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
} 

Measured memory_bytes: 1160
N = int(input())
ans = 0

def dfs(n, f1, f2, f3):
    if n > N:
        return
    if f1 and f2 and f3:
        global ans
        ans += 1

    dfs(n*10+7, True, f2, f3)
    dfs(n*10+5, f1, True, f3)
    dfs(n*10+3, f1, f2, True) 

dfs(0, False, False, False)
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
 
using namespace std;
 
int n, m, k;
vector<int> friends[100000];
unordered_set<int> blocks[100000];
bool visited[100000];
unordered_set<int> comp;
int ans[100000];
 
void dfs(int v)
{
    visited[v - 1] = 1;
    comp.insert(v);
 
    for (auto a : friends[v - 1])
    {
        if (!visited[a - 1])
            dfs(a);
    }
}
 
int main()
{
  	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
 
	cin >> n >> m >> k;
 
	for (int i = 0; i < n; i++)
    {
        visited[i] = 0;
        ans[i] = 0;
    }
 
	for (int i = 0; i < m; i++)
    {
        int t1, t2;
        cin >> t1 >> t2;
        friends[t1 - 1].push_back(t2);
        friends[t2 - 1].push_back(t1);
    }
 
    for (int i = 0; i < k; i++)
    {
        int t1, t2;
        cin >> t1 >> t2;
        blocks[t1 - 1].insert(t2);
        blocks[t2 - 1].insert(t1);
    }
 
    for (int i = 0; i < n; i++)
    {
        if (comp.size() != 0)
            comp.clear();
        if (!visited[i])
            dfs(i + 1);
 
        for (auto a : comp)
        {
            int b = 0;
            if (comp.size() <= blocks[a - 1].size())
            {
                for (const auto& x : comp)
                {
                    if (blocks[a - 1].count(x) != 0)
                        b++;
                }
            }
            else
            {
                for (const auto& x : blocks[a - 1])
                {
                    if (comp.count(x) != 0)
                        b++;
                }
            }
            ans[a - 1] = comp.size() - 1 - b - friends[a - 1].size();
        }
    }
 
    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";
 
	return 0;
}

Measured memory_bytes: 27172
use std::io;
use std::cmp;


fn main() {
    let (a, mut b, k) = {
        let i = read::<isize>();
        (i[0], i[1], i[2])
    };

    let ka: isize = cmp::max(0, a - k);
    b -= k + ka - a;
    println!("{} {}", ka, cmp::max(0, b));
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 4352
/**
 *  author: MOOONI
 *  hackers are welcome!
**/
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define db double
#define ld long double
#define str string
#define pi pair
#define tup tuple
#define vec vector
#define temp template
#define tn typename

#define ff first
#define ss second
#define SZ(x) (ll) x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define rsz resize
#define ins insert
#define fr front 
#define bc back
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define mk make_pair

#define FOR(i, a, b) for (ll i = (a); i <= (b); i++) 
#define ROF(i, a, b) for (ll i = (a); i >= (b); i--)
#define trav(a, x) for (auto &a : x)
#define popcount __builtin_popcount
#define ctz __builtin_ctz
#define clz __builtin_clz
#define gcd __gcd

// DEBUG
#define ts to_string
temp<tn A, tn B> str ts(pi<A, B> p);
temp<tn A, tn B, tn C> str ts(tup<A, B, C> p);
str ts(const str& s) { return '"' + s + '"'; }
str ts(const char* s) { return ts((str) s); }
str ts(bool b) { return (b ? "true" : "false"); }
str ts(vec<bool> v) { bool f = true; str res = "{";
FOR(i, 0, static_cast<ll>(v.size()) - 1) 
{ if (!f) res += ", "; res += ts(v[i]);
f = false; } res += "}"; return res; }
temp<size_t N> str ts(bitset<N> v) { str res = "";
trav(a, v) { res += (char) ('0' + a); } return res; }
temp<tn A> str ts(A v) { bool f = true; str res = "{";
trav(x, v) { if (!f) res += ", "; res += ts(x);
f = false; } res += "}"; return res; }
temp<tn A, tn B> str ts(pi<A, B> p) { 
  return "(" + ts(p.ff) + ", " + ts(p.ss) + ")"; }
temp<tn A, tn B, tn C> str ts(tup<A, B, C> t) {
  return "(" + ts(get<0>(t)) + ", " + ts(get<1>(t)) + ", " + ts(get<2>(t)) + ")"; }
void DBG() { cerr << endl; }
temp<tn H, tn... T> void DBG(H h, T... t) { cerr << " " << ts(h); DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", DBG(__VA_ARGS__);

// INPUT AND OUTPUT
temp<tn T> void re(T& x) { cin >> x; };
temp<tn H, tn... T> void re(H& h, T&... t) { re(h); re(t...); }
temp<tn T> void pr(T x) { cout << x; };
temp<tn H, tn... T> void pr(H h, T... t) { pr(h); pr(t...); }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n, k;
  re(n, k);
  vec<bool> ok(n, false);
  FOR(i, 0, k - 1) {
    ll m;
    re(m);
    FOR(j, 0, m - 1) {
      ll x;
      re(x);
      --x;
      ok[x] = true;
    }
  } 
  ll ans = 0;
  FOR(i, 0, n - 1) {
    if (ok[i] == false) {
      ++ans;
    } 
  }
  pr(ans, '\n');
  return 0;
}

Measured memory_bytes: 3652
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <sstream>
#include <stack>
#include <time.h>
#include <vector>
#include <complex>
using namespace std;
int main(){
  int n,d,x;
  cin>>n>>d>>x;
  for (int i=0;i<n;i++){
    int l;
    cin>>l;
    x += (d-1) / l + 1;
  }
  cout<<x;
  system ("pause");
  return 0;
}

Measured memory_bytes: 504
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

def main():
    n, k = [int(e) for e in input().split(" ")]
    # S = [0 for _ in range(n)]
    # for i in range(n):
    #     S[i] = 1/n if i == 0 else S[i-1] * 1/n
    #
    total_p = 0.0
    for i in range(1, n+1):
        total = i
        p = 1/n
        while True:
            if total >= k:
                total_p += p
                break
            p *= 1/2
            total *= 2

    print(total_p)


main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

ll mod = 1e9+7;

const int N = 5000000;
ll f[N], inv_f[N];

ll mod_pow(ll x, ll n)
{
    ll r = 1;
    while(n)
    {
        if(n&1) (r*=x)%=mod;
        (x*=x)%=mod;
        n>>=1;
    }
    return r;
}

ll mod_inv(ll x)
{
    return mod_pow(x,mod-2);
}


ll C(int n, int r)
{
    if(n<0 || r<0 || n-r<0) return 0;
    ll ret = f[n];
    (ret*=inv_f[r])%=mod;
    (ret*=inv_f[n-r])%=mod;
    return ret;
}

ll H(int n, int r)
{
    if(n==0 && r==0) return 1;
    return C(n+r-1,r);
}

int main()
{
    f[0]=1;
    for(int i=1; i<N; ++i) f[i]=(f[i-1]*i)%mod;

    inv_f[N-1] = mod_inv(f[N-1]);
    for(int i=N-2; i>=0; --i) inv_f[i] = (inv_f[i+1]*(i+1))%mod;

    int a,b,c,sx,sy;
    while(cin >>a >>b >>c >>sx >>sy)
    {
        if(a+b+c+sx+sy==0) break;
        ll ans = 0;
        rep(i,sx+1)
        {
            ll add = 1;
            int j = sy-sx+i;
            (add*=H(a,i-a))%=mod;
            (add*=H(b,j-b))%=mod;
            (add*=H(a+b+c,sx-i))%=mod;

            (ans += add)%=mod;
        }
        (ans*=C(a+b+c,a))%=mod;
        (ans*=C(b+c,b))%=mod;
        printf("%lld\n", ans);
    }
    return 0;
}

Measured memory_bytes: 81128
#pragma region
#pragma GCC target("avx2")
#pragma GCC optimize("03")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std; typedef long double ld; typedef long long ll;
typedef unsigned long long ull;
#define endl "\n"
#define MP make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORR(x,arr) for(auto& x:arr)
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define VPII vector<PII>
#define VPLL vector<PLL>
#define FI first 
#define SE second
#define ALL(x) (x).begin(), (x).end()
constexpr int INF=1<<30; constexpr ll LINF=1LL<<60; constexpr ll mod=1e9+7; constexpr int NIL = -1;
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
#pragma endregion
//-------------------

int main(){
    cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(15);
    int l,r , d; cin >> l >> r>> d;
    int cnt = 0;
    FOR(i,l,r) {
        if(i%d==0)cnt ++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3608
#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int W, H;
    int x, y, r;
 
    scanf("%d%d%d%d%d", &W, &H, &x, &y, &r);
    W -= r, H -= r;
    if (r <= x && x <= W && r <= y && y <= H) printf("Yes\n");
    else printf("No\n");
    return 0;
}



Measured memory_bytes: 2140
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, K;
  cin >> A >> B >> K;
  for (int i = 0; i < K; i++) {
    if (i % 2 == 0) {
      if (A % 2 == 0) {
      } else {
        A--;
      }
      A /= 2;
      B += A;
    } else {
      if (B % 2 == 0) {
      } else {
        B--;
      }
      B /= 2;
      A += B;
    }
  }
  cout << A << " " << B;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

using namespace std;
const int MM = 2e5+5;

int n, k, c;
char s[MM];
bool vis[MM];
int dp[MM];

int go(int i){
    if(i > n)
        return 0;
    if(vis[i])
        return dp[i];
    vis[i] = 1;
    if(s[i] == 'x')
        return dp[i] = go(i+1);
    return dp[i] = max(go(i+1), 1+go(i+c+1));
}
bool vis2[MM];
int dp2[MM];
int go2(int i){
    if(i < 1)
        return 0;
    if(vis2[i])
        return dp2[i];
    vis2[i] = 1;
    if(s[i] == 'x')
        return dp2[i] = go2(i-1);
    return dp2[i] = max(go2(i-1), 1+go2(i-c-1));
}

set<int> ans;

int main(){
    scanf("%d %d %d %s", &n, &k, &c, s+1);
    for(int i = 1; i <= n; i++){
//        print(i, go(i+c+1) + go2(i-c-1) + 1, go(i+1) + go2(i-1));
        if(go(i+c+1) + go2(i-c-1) + 1 >= k and go(i+1) + go2(i-1) < k){
            ans.insert(i);
        }
    }
    for(int i: ans)
        print(i);
    
    return 0;
}

Measured memory_bytes: 19328
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

#define int long long

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

const int INF = (1LL << 60);

struct Edge{
	int to;
	int cost;
	Edge(int to, int cost) : to(to), cost(cost) {}
};

struct Node{
	int dis;
	bool used;
	Node() : dis(INF), used(false) { }
	Node(int d, bool f) : dis(d), used(f) { }
};

typedef vector<vector<Edge>> graph;

vector<Node> dijkstra(graph g, int s, int n){
	vector<Node> node(n);
	priority_queue<int, vector<pair<int, int>>, greater<pair<int, int>>> q;

	q.push(make_pair(0, s));
	node[s] = Node{0, true};

	while(not q.empty()){
		int dis, pos;
		tie(dis, pos) = q.top(); q.pop();
		node[pos].used = true;

		for(auto e : g[pos]){
			if(node[e.to].used == true) continue;
			if(node[e.to].dis > dis + e.cost){
				node[e.to].dis = dis + e.cost;
				q.emplace(node[e.to].dis, e.to);
			}
		}
	}
	return node;
}

void addEdge(graph& g, int from, int to, int cost){
	g[from].emplace_back(Edge{to, cost});
	g[to].emplace_back(Edge{from, cost});
}

signed main(){
	int n, m, s, t;
	cin >> n >> m >> s >> t;
	s--; t--;

	graph ga(n), gb(n);
	rep(i,m){
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		a--; b--;
		addEdge(ga, a, b, c);
		addEdge(gb, a, b, d);
	}

	vector<Node> anode = dijkstra(ga, s, n);
	vector<Node> bnode = dijkstra(gb, t, n);

	priority_queue<pair<int, int>> q;
	rep(i,n){
		int sum = anode[i].dis + bnode[i].dis;
		//cout << anode[i].dis << ' ' << bnode[i].dis << endl;
		assert(sum <= static_cast<long long>(1e15));
		q.emplace(1e15 - sum, i);
	}

	rep(i,n){
		while(i > q.top().second) q.pop();
		cout << q.top().first << endl;
	}
}


Measured memory_bytes: 28220
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>

using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define deb(n) cout<<#n<<' '<<n<<endl
#define darr(arr,n) rep(i,n){cout<<arr<<' ';}cout<<endl;

int main() {

    int N, T[101], M, P[101], X[101];
    cin >> N;
    rep(i, N) {
        cin >> T[i];
    }
    cin >> M;
    rep(i, M) {
        cin >> P[i];
        cin >> X[i];
    }
    int Tcopy[101];
    rep(i, N) {
        Tcopy[i] = T[i];
    }
    rep(i, M) {
        T[P[i]-1] = X[i];
        cout << accumulate(T, T + N, 0) << endl;
        T[P[i]-1] = Tcopy[P[i]-1];
    }
}

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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';
#define N 1000000007 // prime modulo value 
  
typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll , ll> 			pll;
typedef pair<ld, ld> 			pld;
typedef unordered_map<ll, ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5 + 7;
const ll 	MAX7 	= 	1e+7 + 7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e9 + 7;


// <------------- Declare Variables Here ------------> //

ll T = 1;
ll n, x, k, p;
string s, t;
ld w;

// <------------- Implement Functions Here ----------> //



// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> n;
	map<string,ll> val; 
	ll ans = 0;
	for(ll i=0;i<n;i++) {
		cin >> s;
		sort(all(s));
		val[s]++;
	}

	for(auto it : val) {
		ans += (it.s)*(it.s - 1)/2;
	}

	cout<<ans;
}

int main() {
	fastio; randomINT;
	//cin >> T;
	while (T--) {
		MAIN();
	}
	return 0;
}

Measured memory_bytes: 11436
//D
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxp = 1e6+10;
const int maxn = 2e5+10;
int cnt[maxp],raw[maxn],vis[maxp];
bool n_prime[maxp];
const int INF = 1e9;
int m,n;
int main(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> raw[i];
		cnt[raw[i]]++;
	}
	sort(raw+1,raw+n+1);
	vector<int>qwq = {};
	for(int i = 1;i <= n;i++)if(raw[i] != raw[i-1])qwq.push_back(raw[i]);
	if(n == 1){
		cout << 1;
		return 0;
	}
	ll ans = 0;
	for(int u:qwq){
		if(cnt[u] > 1)vis[u] = 1;
		for(int j = u+u;j < maxp;j += u)vis[j] = 1;
	}
	for(int i = 1;i <= n;i++)if(!vis[raw[i]])ans++;
	cout << ans;
	return 0;
}


Measured memory_bytes: 12696
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#define ll long long
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define loop(i,start, stop) for(int i = start; i < (stop); i++)
using namespace std;

int main(){
  
  int A,B,C,K;
  cin >> A >> B >> C >> K;

  int ans=0;

  if(K <= A) ans += 1 * K; 
  else if(A < K) {
    if (K-A <= B) ans += 1 * A + 0;
    else if (B < K-A) ans += 1 * A + 0 + (-1 * (K-A-B));
  }

  cout << ans << endl;

  return 0;
}


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

int main(){
    string A, B, C; cin >> A >> B >> C;
    if(A[A.length()-1] == B[0] && B[B.length()-1] == C[0]) cout << "YES";
    else cout << "NO";
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
 
public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(in.readLine());
    StringTokenizer stk = new StringTokenizer(in.readLine());
    in.close();
    int a[] = new int[n];
    boolean flg = true;
    for(int cnt = 0; cnt<n; cnt++){
      a[cnt] = Integer.parseInt(stk.nextToken());
      if(a[cnt]%2==0){
        if(a[cnt]%3!=0 && a[cnt]%5!=0)
          flg = false;
      }
    }
    if(flg == true)
      System.out.println("APPROVED");
    else
      System.out.println("DENIED");
  }
}

Measured memory_bytes: 23124
unittest
{
	assert( [ "6", "3 1 2 4 2 1" ].parse.expand.solve == 2 );
	assert( [ "4", "1 2 3 4" ].parse.expand.solve == 0 );
	assert( [ "10", "3 3 3 3 4 4 4 5 5 5" ].parse.expand.solve == 20 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.strip.to!( long );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	return tuple( as );
}

auto solve( long[] as )
{
	auto gs = as.sort!( ( a, b ) => b < a ).group;
	
	auto a = 0L;
	auto b = 0L;
	foreach( g; gs )
	{
		if( a == 0 && 4 <= g[ 1 ] )
		{
			a = g[ 0 ];
			b = g[ 0 ];
			break;
		}
		if( 2 <= g[ 1 ] )
		{
			if( a == 0 )
			{
				a = g[ 0 ];
				// まだ片方の辺しか決まってないので続行
			}
			else
			{
				b = g[ 0 ];
				break;
			}
		}
	}
	
	return a * b;
}


Measured memory_bytes: 6572
a_arr = []
a_arr.append(int(input()))
a_arr.append(int(input()))
a_arr.append(int(input()))
a_arr.append(int(input()))
a_arr.append(int(input()))
k = int(input())

d = a_arr[4]-a_arr[0]

if d<=k:
    print("Yay!")
else:
    print(":(")



Measured memory_bytes: 3060
n=int(input())
dam=[int(x) for x in input().split()]
yama=[0]*n
dam_sum=sum(dam)//2
diff=0
if n in (1,2):
    for j in range(n):
        diff=0
        for i in range(n):
            if i%2==0:
                continue
            diff+=dam[(i+j)%n]
        yama[j]=dam_sum - diff
        yama[j]*=2
else:
    diff_same=0
    for i in range(n):
            if i%2==0:
                continue
            diff_same+=dam[(i)%n]
    yama[0]=dam_sum - diff_same
    yama[0]*=2
    diff_odd=0
    for i in range(n):
            if i%2==0:
                continue
            diff_odd+=dam[(i+1)%n]
    yama[1]=dam_sum - diff_odd
    yama[1]*=2
    for j in range(2,n):
        if j%2==0:
            diff_same-=dam[(j-1)%n]
            diff_same+=dam[(j-2)%n]
            yama[j]=dam_sum - diff_same
        else:
            diff_odd-=dam[(j-1)%n]
            diff_odd+=dam[(j-2)%n]
            yama[j]=dam_sum - diff_odd
        yama[j]*=2
print(" ".join([str(x) for x in yama]))

Measured memory_bytes: 76132
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
L = [a,b,c,d,e]
flag = True
for i in range(4):
  for j in range(i,5):
    if abs(L[i]-L[j]) > k:
      flag = False
      break
if flag:
  print('Yay!')
else:
  print(':(')

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

using namespace std;

int main()
{
	long N,R,K;
	cin >> N >>R; 
	if(N>=10){
		K=R;
	}else{
		K=R+100*(10-N);
	}		
	cout<<K<<endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <utility>
using namespace std;
#define INF 100000000
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define rep(i, n) for(int (i)=1; (i)<=(n); (i)++)
typedef pair<int, int> P;
typedef long long ll;

const int N = 1e5 + 10;
int n, k, x, F[N], a[N], pre[N];

void upd(int x){
    for(; x<N; x += (x&-x)){
        F[x]++;
    }
}

int que(int x){
    int ans = 0;
    for(; x>0; x-=(x&-x))
        ans += F[x];
    return ans;
}

ll get(int x){
    REP(i, N) pre[i] = 0;
    for(int i=1; i<n+1; i++){
        if(a[i]>x) pre[i] = -1;
        else pre[i] = 1;
        pre[i] += pre[i-1];
    }
    int T = min(*min_element(pre+1, pre+n+1), 0);
    REP(i, n+1) pre[i] -= T-1;
    REP(i, N) F[i] = 0;
    ll cur = 0;
    upd(pre[0]);
    for(int i=1; i<n+1; i++){
        cur += que(pre[i]-1);
        upd(pre[i]);
    }
    return cur;
}

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

    int bas = 1, son = 1e9;
    ll look = n*(ll)(n+1) / 2 / 2 + 1;
    while(bas < son){
        int mid = (bas+son)/2;
        if(get(mid) >= look) son = mid;
        else bas = mid + 1;
    }
    cout << bas << endl;
    return 0;
}

Measured memory_bytes: 1408
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
using namespace std;
int main(){
    int A,B,K,X,Y,Z;
    cin >> A >> B >> K;
    X=0;
    for (int i = min(A,B);i >0;i--) {
        if (A % i == 0 && B % i == 0){
            X++;
            Y = i;
            //cout << X << "," << Y << endl;
            if(X==K){
                Z=i;
            }
        }
    }
    cout << Z << endl;
}

Measured memory_bytes: 256