akhauriyash/Code-Regression huggingface dataset:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
n,m,k=map(int,input().split())
uf=UnionFind(n)
edge=[[] for _ in range(n)]
brock=[[] for _ in range(n)]
ans=[]
for _ in range(m):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    uf.union(a-1,b-1)
for _ in range(k):
    c,d=map(int,input().split())
    brock[c-1].append(d-1)
    brock[d-1].append(c-1)
for i in range(n):
    ans.append(uf.size(i)-len(edge[i])-sum([uf.same(i,j) for j in brock[i]])-1)
print(*ans)

Measured memory_bytes: 51624
#include <bits/stdc++.h>
using namespace std;
         
#define fast { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define pb push_back
#define ll long long
#define ld long double
#define vll vector<ll>
#define infl LONG_LONG_MAX
#define infd LDBL_MAX
#define F first
#define S second
#define pll pair<ll,ll> 
#define G(a,b) get<a>(b)
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define MT make_tuple
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fi(i,a,b) for(ll i=(b-1);i>=a;i--)    
#define endl "\n"
#define nl cout<<"\n";
#define pr(x) cout<<x;
#define pr1(x) cout<<x<<" ";
#define pr2(x,y) cout<<x<<" "<<y;
#define sz(x) (ll)x.size() 
#define ara cout<<"ara-ara\n"; 
 


void func()
{
   ll l,r,d;
   cin>>l>>r>>d;
   ll ans=0;
   f(i,l,r+1) if(i%d==0) ans++;
   cout<<ans<<endl;
}   
     
     
     
int main() 
{
    fast
    //#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //#endif // ONLINE_JUDGE
        
     
    ll ntc=1;
    //cin>>ntc;
     
    f(i,1,ntc+1)
    {
      //cout<<"Case #"<<i<<": ";
       func();
    }
     
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <queue>
#include <vector>

constexpr int MAX = 1e5 + 10;

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

std::vector<int> g[MAX];

int a[MAX];

std::queue<int> que;

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

    rep(i, m)
    {
        int a, b;
        std::cin >> a >> b;
        g[b].push_back(a);
        g[a].push_back(b);
    }

    que.emplace(1);

    while (!que.empty())
    {

        int x = que.front();
        que.pop();

        for (int y : g[x])
        {
            if (a[y] == 0)
            {
                a[y] = x;
                que.push(y);
            }
        }
    }

    std::cout << "Yes" << std::endl;

    rep(i, n - 1)
    {
        std::cout << a[i + 2] << std::endl;
    }

    return 0;
}

Measured memory_bytes: 10408
#include <stdio.h>
#include <string.h>
int array[50];
int main()
{
  for(;;){
    int n,p,t,e;
    scanf("%d %d",&n,&p);
    if(n == 0 || p == 0) break;
    memset(array,0,sizeof(array));
    t = p;
    e = 0;
    for(;;){
      int i;
      for(i=0; i<n; i++){
        if(p > 0) {
          p--;
          array[i]++;
        }else{
          p += array[i];
          array[i] = 0;
        }
        if(array[i] == t){
          printf("%d\n",i);
          e = 1;
          break;
        }
      }
      if(e) break;
    }
  }
  return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
#define start_routine cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int begtime = clock();
#define end_routine int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0;
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define int long long
#define mp make_pair
#define fr(i,a,b) for(i=a;i<b;i++)
#define mod 1000000007
#define FILEIO freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
using namespace std;

signed main()
{
	//FILEIO
 	//start_routine
	
	int tests = 1;
	//cin>>tests;

	while(tests--)
	{
		string s;
		cin>>s;

		string w = "AKIHABARA";
		int i, mask;
		fr(mask,0,(1<<9))
		{
			string p = "";
			bool ok = 1;
			fr(i,0,9)
			{
				if( (mask>>i)&1 ) p+=w[i];
				else ok &= (w[i] == 'A');
			}
			if(!ok) continue;
			if(p == s) return cout<<"YES\n",0;
		}
		return cout<<"NO\n",0;
	}

 	//end_routine
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int main(){
    int n,C;
    cin>>n>>C;
    vector<pair<int,int>> v[C];
    for(int i=0;i<n;i++){
        int s,t,c;
        cin>>s>>t>>c;
        v[c-1].push_back({s,t});
    }
    multiset<pair<int,int>> st;
    for(int i=0;i<C;i++){
        sort(v[i].begin(),v[i].end());
        for(int j=0;j<v[i].size();j++){
            int l=v[i][j].first;
            while(j+1<v[i].size()&&v[i][j].second==v[i][j+1].first)j++;
            int r=v[i][j].second;
            st.insert({l-1,r});
        }
    }
    int right=0,ans=1;
    while(st.size()){
        auto it=st.lower_bound({right,0});
        if(it==st.end()){
            right=0;
            ans++;
            continue;
        }
        right=it->second;
        st.erase(it);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 6016
char s[];main(){double*q=s,b;for(;~scanf("%s",s);getchar()<14&&printf("%f\n",*q))sscanf(s,"%lf",q+1)-1?b=*q--,*q=*s-47?*s-42?*s-45?*q+b:*q-b:*q*b:*q/b:*++q;}

Measured memory_bytes: 0
import java.util.Scanner;
     
    class Main{
    	public static void main(String arg[]) {
    		Scanner sc = new Scanner(System.in);
    		String s = sc.nextLine();
    		String[]S = s.split(" ");
    		int a = Integer.parseInt(S[0]);
    		int b = Integer.parseInt(S[1]);
    		int c = Integer.parseInt(S[2]);
    		sc.close();
    		
    		for(int i = 1; i <= b; i++) {
    			if(a*i%b == c) {
    				System.out.println("YES");
    				System.exit(0);
    			}
    		}
    		System.out.println("NO");
    	}
    }

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> a(N);

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

  if(N == 1) {
    for(int i=0;i<M;i++) {
      a[0] /= 2;
    }

    cout << a[0] << endl;
    return 0;
  }

  while(M > 0) {
    sort(a.begin(), a.end());
    a[N-1] = a[N-1] / 2;
    M--;
  
    int index = N-1;
    for(int i=0;i<N;i++) {
      if(a[i] > a[N-1]) {
        index = i;
        break;
      }
    }
    int alpha = N - (index + 1);

    if(alpha > M) {
      for(int i=N-2;i>N-M-2;i--) {
        a[i] = a[i] / 2;
      }
      break;
    } else {
      for(int i=N-2;i>=index;i--) {
        a[i] = a[i] / 2;
      }
      M -= alpha;
    }
  }

  long long int total = 0;

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

  cout << total << endl;

  return 0;
}

Measured memory_bytes: 640
import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {
	/**
	 * Main method.
	 */
	public static void main(String[] args) throws IOException {
		Scanner s = new Scanner(System.in);
		
		int N = s.nextInt();
		
		Map<String, Integer> nameMap = new HashMap<>();
 		for (int i = 0; i < N; i++) {
			String nameFirst = s.next().substring(0, 1);
			if (nameFirst.matches("[MARCH]")) {
				if (nameMap.containsKey(nameFirst)) {
					nameMap.put(nameFirst, nameMap.get(nameFirst) + 1);
				} else {
					nameMap.put(nameFirst, 1);
				}
			}
		}
		
 		Set<String> src = new HashSet<String>() {{
 			for (String nameFirst : nameMap.keySet()) {
 				add(nameFirst);
 			}
 		}};

 		long answer = 0;
 		
 		//System.out.println(combination(src, 3));
 		for (Set<String> setTmp : combination(src, 3)) {
 			long answerTmp = 1;
 			for (String nameFirst : setTmp) {
 				answerTmp *= nameMap.get(nameFirst);
 			}
 			answer += answerTmp;
 		}
 		
 		System.out.println(answer);
 
	}
	
	private enum Operation {add, remove};
    private static<T> Set<T> apply(Set<T> src, Operation operation, T item) {
        Set<T> result = new HashSet<T>(src);
        if (Operation.add == operation) result.add(item);
        if (Operation.remove == operation) result.remove(item);
        return result;
    }

    private static<T> Set<Set<T>> _combination(Set<T> selected, int depth, Set<T> pool) {
        if (depth == 0) return apply(new HashSet<>(), Operation.add, selected); 
        Set<Set<T>> result = new HashSet<Set<T>>();
        for (T item : pool) {
            result.addAll(
                    _combination(
                            apply(selected, Operation.add, item),
                            depth - 1, 
                            apply(pool, Operation.remove, item) 
                    )
            );
        }
        return result;
    }
    public static<T> Set<Set<T>> combination(Set<T> src, int k) {return _combination(new HashSet<T>(), k, src);}
}

Measured memory_bytes: 64072
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

ll length[100];
ll mypow10[100];

string itos(ll x) {
  char str[100];
  sprintf(str, "%lld", x);
  return (string)str;
}

int main() {
  length[0] = 0;
  mypow10[0] = 1;
  REP(i, 11) {
    mypow10[i + 1] = 10 * mypow10[i];
    length[i + 1] = length[i] + (mypow10[i + 1] - mypow10[i]) * (i + 1);
  }
  ll n, k;
  while (scanf("%lld %lld", &n, &k), n|k) {
    int index = 0;
    REP(i, 11) {
      if (length[i] >= n) { index = i; break; }
    }
    n--;
    ll start = n - length[index - 1];
    ll rest = start % index;
    start = start / index + mypow10[index - 1];
    string ans = itos(start);
    ans = ans.substr(rest, index);
    FOREQ(i, start + 1, i + k) {
      ans += itos(i);
      if ((int)ans.size() >= k) { break; }
    }
    ans.resize(k);
    cout << ans << endl;
  }
}

Measured memory_bytes: 0
from sys import stdin, setrecursionlimit


a_list = 'abcdefghijklmnopqrstuvwxyz'


def base_convert(nl, ibase, obase):
    o = []
    while any(nl):
        c = 0
        for i in range(len(nl)):
            c = c * ibase + nl[i]
            nl[i], c = divmod(c, obase)
        o.append(c)
    o.reverse()
    return o


def main():
    input = stdin.buffer.readline
    N = int(input())
    if N == 1:
        print('a')
    else:
        arr = [1]
        tmp = 1
        while arr[-1] <= 1000000000000001:
            tmp *= 26
            arr.append(tmp)
        k = 0
        while N >= arr[k]:
            N -= arr[k]
            k += 1
        n = [int(i) for i in list(str(N))]
        idx = base_convert(n, 10, 26)
        idx = [0] * (k - len(idx)) + idx
        print(*[a_list[i] for i in idx], sep='')


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


Measured memory_bytes: 61968
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(){
    string S_1,S_2,S_3;
    cin >> S_1 >> S_2 >> S_3;
    cout << S_1[0] << S_2[0] << S_3[0];
}

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n-1);
    int i;
    for(i = 0; i < n-1; i++){
        cin >> a.at(i);
    }
    map<int, int> mp;
    for(i = 1; i < n+1; i++){
        mp[i] = 0;
    }
    for(i = 0; i < n-1; i++){
        mp[a.at(i)]++;
    }
    for(auto p : mp){
        cout << p.second << endl;
    }
    return 0;   
}


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

int main(){
	long long a,b,c;
	cin >> a >> b >> c;
	if(a % 2 == 0 || b % 2 == 0 || c % 2 == 0){
		cout << 0 << endl;
	}
	else{
		long long d = min(a,b);
		if(d == a){
			cout << d * min(b,c) << endl;
		}
		else{
			cout << d * min(a,c) << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool s[10000000];
int main(){
  s[0]=s[1]=1;
  for(int i=2;i<10000000;i++)if(!s[i])
    for(int j=i+i;j<10000000;j+=i)s[j]=1;
  int n;
  while(cin>>n,n){
    int sum=0,c=0;
    for(int i=0;i<=n;i++){
      sum=0;
      if(!s[i])for(int j=i;j<n*10;j++){
        if(!s[j])sum+=j;
        if(sum==n)c++;
        if(sum>=n)break;
      }
    }
    cout<<c<<endl;
  }
}

Measured memory_bytes: 12844
#include <cstdio>
#include <set>

int main() {
  std::set<int> s;
  int q;
  scanf("%d", &q);

  for (int i=0; i<q; ++i) {
    int t;
    scanf("%d", &t);

    if (t == 0) {
      int x;
      scanf("%d", &x);
      s.insert(x);
      printf("%zu\n", s.size());
    } else if (t == 1) {
      int x;
      scanf("%d", &x);
      printf("%td\n", s.count(x));
    } else if (t == 2) {
      int x;
      scanf("%d", &x);
      s.erase(x);
    } else if (t == 3) {
      int l, r;
      scanf("%d %d", &l, &r);
      auto it=s.lower_bound(l);
      while (it != s.end() && *it <= r) {
        printf("%d\n", *it);
        ++it;
      }
    }
  }
}



Measured memory_bytes: 11992
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i, n) for(int i=0; i < n; ++i)
#define repe(i, n) for(int i=0; i <= n; ++i)
#define repr(i, n) for(int i=n-1; i > 0; --i)
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define eb(x,y) emplace_back(x,y)
#define PI 3.14159265359
#define vi vector<int>
#define vl vector<ll>
using namespace std;
template <class T> bool chmax(T &a, const T &b) {if (a<b) {a = b; return 1;} return 0;}
template <class T> bool chmin(T &a, const T &b) {if (b<a) {a = b; return 1;} return 0;}
template <class T> using V=vector<T>;
const int INF = 1e9;
const int MOD = 1000000007;
using Graph = vector<vector<int>>;
bool isPrime(int x) {
    if (x<2) return 0;
    else if (x==2) return 1;
    if (x%2==0) return 0;
    for(int i=3; i*i<=x; i+=2) if(x%i==0) return 0;
    return 1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vi a(n); rep(i,n) cin >> a[i];
    int cnt = 0;
    rep(i,n) {
        if (a[i]%2==1) {
            cnt++;
        }
    }
    if (cnt%2==1) {
        cout << "NO" << "\n";
    } else {
        cout << "YES" << "\n";
    }
}

Measured memory_bytes: 640
/// awoooooo

# include <bits/stdc++.h>
# define sz(x) (int)((x).size())

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;

const int N = (int)2e5 + 5;
const int inf = (int)1e9 + 7;

int n, k;
int a[N];

int main(){
  scanf("%d %d", &n, &k);
  int base = 0;
  for(int i = 1; i <= n; ++i){
    scanf("%d", a + i);
    for(int j = 1; j < i; ++j){
      base += a[j] > a[i];
    }
  }
  int ans = base * 1ll * k % inf;
  if(k == 1){
    printf("%d\n", ans);
    return 0;
  }
  --k;
  for(int i = 1; i <= n; ++i){
    int cnt = 0;
    for(int j = 1; j <= n; ++j){
      cnt += a[j] > a[i];
    }
    int val = (k * 1ll * (k + 1) / 2) % inf;
    val = val * 1ll * cnt % inf;
    (ans += val) %= inf;
  }
  printf("%d", ans);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n, k;

ll dc[110][10010];
ll ds[110][10010];
ll M = 1'000'000'007;

int main()
{
	read(n, k);
	dc[n+1][0] = 1;
	for(int i = n; 1 <= i; --i){
		for(int bef = 0; bef <= (n-i)*k; ++bef){
			for(int j = 0; j <= k; ++j){
				if(!dc[i+1][bef]) continue;
				int c = (j > i ? 0 : (j + bef) / i);
				(ds[i][bef + c] += ds[i+1][bef] +
								   dc[i+1][bef] * ((j - c + M)%M) % M) %= M;
				(dc[i][bef + c] += dc[i+1][bef]) %= M;
			}
		}
	}
	ll ans = 0;
	for(int i = 0; i <= n*k; ++i)
		(ans += ds[1][i]) %= M;
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 14848
#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
ll MOD=1e9+7;
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    if((n%2 && a[0]!=0) || (!n%2 && (a[0]!=0 || a[1]!=0))) {
        cout << '0' << endl;
        return 0;
    }

    int i=n%2;
    ll pow=0;
    while(i<n) {
        if(a[i]!=a[i+1]) {
            cout << '0' << endl;
            return 0;
        }
        pow+=1;
        i+=2;
    }

    ll ans=1;
    while(pow!=0) {
        ans = (ans*2)%MOD;
        pow--;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 1024
#include<bits/stdc++.h>
// #define int long long
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define repa(i, s, n) for(int i = s; i < (int)n; i++)
#define MOD 1000000007
using namespace std;
using ll = long long;
typedef vector<int> vi;
typedef pair<int, int> P;
#define rrep(i,a,b) for(int i=a;i>=b;i--)

string ss, T;

string solve(){
    int N = ss.length();
    int M = T.length();

    set<string> ans;
    /* N ~ Mまで */
    rrep(R, N, M){
        int L = R - M;

        int ok = 1;
        rep(i, M) if(ss[L+i] != '?' && ss[L+i] != T[i]) ok = 0;
        if(ok){
            string S;
            rep(i, N) S += ss[i];
            rep(i, M) S[L+i] = T[i];
            rep(i, N) if(S[i] == '?') S[i] = 'a';
            ans.insert(S);
        }
    }

    if(ans.size() == 0) return "UNRESTORABLE";
    return *(ans.begin());
}

signed main(){
    cin >> ss >> T;
    cout << solve() << endl;
}

Measured memory_bytes: 3628
#include <stdio.h>
#include <inttypes.h>

#define KI_MAX 512345

uint64_t ki[KI_MAX];

void ki_add(int idx, uint64_t value) {
	if (idx <= 0) return;
	for (; idx < KI_MAX; idx += idx & -idx) {
		ki[idx] += value;
	}
}

uint64_t ki_sum(int idx) {
	uint64_t sum = 0;
	for (; idx > 0; idx -= idx & -idx) {
		sum += ki[idx];
	}
	return sum;
}

int main(void) {
	int N, Q;
	int i;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 0; i < N; i++) {
		int a;
		if (scanf("%d", &a) != 1) return 1;
		ki_add(i + 1, a);
	}
	for (i = 0; i < Q; i++) {
		int q[3];
		if (scanf("%d%d%d", &q[0], &q[1], &q[2]) != 3) return 1;
		if (q[0] == 0) {
			ki_add(q[1] + 1, q[2]);
		} else if (q[0] == 1) {
			printf("%" PRIu64 "\n", ki_sum(q[2]) - ki_sum(q[1]));
		}
	}
	return 0;
}


Measured memory_bytes: 8104
#include<bits/stdc++.h>
using namespace std;
stack<int> s;

int main(){
  int tmp;
  while(scanf("%d", &tmp)!=EOF){
    if(tmp!=0) s.push(tmp);
    else{
      printf("%d\n", s.top());
      s.pop();
    }
  }
  return 0;
}

Measured memory_bytes: 1192
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

int n, m, a, b, vt[1005];
vector<int> gr[1005], tmp, ans;

void dfs(int p) {
	tmp.push_back(p);
	vt[p] = 1;
	for(int x:gr[p]) {
		if(x == tmp[0]) {
			if(ans.empty() || tmp.size() < ans.size()) ans = tmp;
		} else if (!vt[x]) {
			dfs(x);
		}
	}
	tmp.pop_back();
}

int main() {
	cin >> n >> m;
	while(m--) {
		cin >> a >> b;
		gr[a].push_back(b);
	}
	for(int i=1; i<=n; i++) {
		memset(vt, 0, sizeof(vt));
		tmp.clear();
		dfs(i);
	}
	if(ans.empty()) {puts("-1"); return 0;}
	cout << ans.size() << endl;
	for(auto x:ans) cout << x << endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
using namespace std ;


void ABC_175_C(){
    // X：初期点 K：移動回数 D:一回で移動出来る距離
    long long int X, K, D;
    cin >> X >> K >> D;
    X = abs(X);

    // 何回D距離を移動すればGoal(座標0)するかを割り算で算出
    long long int goalNum = X / D;
    
    // 移動回数とGoalする回数のうち、小さい数をmoveNumにセット
    long long int moveNum = min(K, goalNum);
    
    // 元々の移動回数からゴールまで進んだ移動回数を引く。
    K -= moveNum;
    // 元々の位置からゴールまで進んだ移動分を引く。
    X -= moveNum * D;
    
    // 偶数なら行ったり来たりするだけなので処理終了
    if (K % 2 == 0) {
        cout << X << endl;
    } else {
        cout << D - X << endl;
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    ABC_175_C();
    return 0;
}


Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define time_taken_start int begtime = clock();
#define time_taken_end int endtime = clock(); \
cerr << "\n\n" << "Time elapsed: " << \
(endtime - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n"; \
return 0;
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define mod 1000000007
#define inf 1000000000000000007
#define eps 0.0000000001
#define pi acosl(-1)
#define pii pair<int,int>
#define pdd pair<ld,ld>
#define pll pair<ll,ll>
#define ff first
#define ss second
#define vii vector<int>
#define vpl vector<pll>
#define vll vector<ll>
#define mseti multiset <ll>
#define msetd multiset <ll,greater<ll>>
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound 
#define stp fixed<<setprecision(20)
#define endl '\n'
ll ans[200009];
void solve()
{
    for(ll i=0;i<=9;i++)
        ans[i]=i;
    ll cnt=10;
    ll n;
    cin>>n;
    ll q=1;
    while(cnt<=n)
    {
        for(ll i=0;i<10;i++)
        {
            if((abs((ans[q]%10)-i))<2)
            {
                ll x=ans[q]*10;
                x+=i;
                ans[cnt]=x;
                cnt++;
            }
        }
        q++;
    }
    cout<<ans[n];
}
int main()
{
    FAST
    #ifdef ayk_16
    freopen("input.txt","rt",stdin);
    freopen("output.txt","wt",stdout);
    #endif
    ll t=1;
    //cin>>t;
    for(ll i=0;i<t;i++)
    {
        //cout<<"Case #"<<i+1<<": ";
        solve();
    }
}

Measured memory_bytes: 1024
import java.util.*;
 
public class Main {
 
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		double[] p = new double[N];
		for (int i = 0; i < N; i++) {
			double d = sc.nextDouble();
			p[i] = (d+1)/2;
		}
		double max = 0.0;
		double[] amounts = new double[N-K+1];
		for (int i = 0; i < K; i++) {
			max += p[i];
		}
		amounts[0] = max;
		for (int i = 0; i < N-K; i++) {
			amounts[i+1] = amounts[i] + p[i+K] - p[i];
			if (max < amounts[i+1]) {
				max = amounts[i+1];
			}		
		}
		System.out.println(max);
		
	}
}

Measured memory_bytes: 158808
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n,a[100005],sum=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int i=2;i<=n;i++)
	{
		if(a[i]==a[i-1])
		{
			sum++;
		}
	}	
	if(sum%2!=0)
	{
		sum++;
	}
	cout<<n-sum;
	return 0;
} 

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,a=2,b=1,ans;
    cin>>n;
    if(n==0) cout<<"2"<<endl;
    if(n==1) cout<<"1"<<endl;
    if(n>=2)
    {
        n=n-1;
        for(int i=1;i<=n;i++)
        {
            ans=a+b;
            a=b;
            b=ans;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int[] a;
	static boolean[] even = new boolean[7];
	static int[] evenV = new int[10];
	static int wildC = 0;
	static int ans = 0;

	public static void main(String[] args) {
		for (int i = 0; i < 10; ++i) {
			evenV[i] = i * 2;
			if (evenV[i] >= 10) {
				evenV[i] = evenV[i] - 9;
			}
		}
		int N = sc.nextInt();
		char[] ID = sc.next().toCharArray();
		int M = sc.nextInt();
		a = new int[M];
		for (int i = 0; i < M; ++i) {
			a[i] = sc.nextInt();
		}
		int sum = 0;
		for (int i = 0; i < N; ++i) {
			if (ID[N - 1 - i] != '*') {
				int v = ID[N - 1 - i] - '0';
				if (i % 2 != 0) {
					sum += evenV[v];
				} else {
					sum += v;
				}
			} else {
				even[wildC++] = i % 2 != 0;
			}
		}
		dfs(0, sum);
		System.out.println(ans);
	}

	static void dfs(int pos, int sum) {
		if (pos == wildC) {
			if (sum % 10 == 0) ++ans;
			return;
		}
		for (int i = 0; i < a.length; ++i) {
			dfs(pos + 1, sum + (even[pos] ? evenV[a[i]] : a[i]));
		}
	}

}

Measured memory_bytes: 12000
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

const ll INF=1e9+7;


int main(){
    vector<ll> ans(4);
    rep(i,3){
        ll a,b;
        cin >> a >> b;
        a--; b--;
        ans[a]++;
        ans[b]++;
    }
    ll cnt_one=0,cnt_two=0;
    rep(i,4){
        if(ans[i]==1) cnt_one++;
        if(ans[i]==2) cnt_two++;
    }
    if(cnt_one==2 && cnt_two==2) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 3536
#include<bits/stdc++.h>
using namespace std;
int read() {
	int x; scanf("%d", &x); return x;	
}
const int maxn = 2e5 + 10;
const int INF = 1e9;
int mod = 1e9 + 7;
using namespace std;

int L, R, d;
int main() {
	#ifdef LOCAL
		freopen("1.in", "r", stdin);
	#endif
	L = read(), R = read(), d = read();
	int ans = 0;
	for (int i = L; i <= R; ++i) if (i % d == 0) ans++;
	cout << ans << endl;
	return 0;	
}


Measured memory_bytes: 3652
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    //nextLineとnextを同時に使ったら死ぬ
    val sc = new Scanner(System.in)
    //標準入力
    val n, m, q = sc.nextInt()
    //[[1],[2]..[m]]なリストとmとnを引数に渡す
    val numArrays = bfs((1 to m).map(a => Array(a)).toArray, m, n)

    //q個分の(a,b,c,d)の入力を受け取る
    val nums = Array.fill(q) {
      val a, b, c = sc.nextInt()
      val d = sc.nextLong()
      (a, b, c, d)
    }

    //各数列についての得点を持つ配列
    val sumOfNumArrays =
      numArrays.map(numArray => {
        //ある数列numArrayについて、q個すべての条件を適用し、和を返す（和を基にしたリストにする）
        nums.map {
          case (a, b, c, d) =>
            if (numArray(b - 1) - numArray(a - 1) == c) d else 0
        }.sum
      })

    //各数列ごとの得点のうち最大のものを出力
    println(sumOfNumArrays.max)
  }

  //Array[Int]が一つの数列を表すので、arrは数列群
  @scala.annotation.tailrec
  def bfs(arr: Array[Array[Int]], m: Int, n: Int): Array[Array[Int]] = {
    //arrの各要素の長さがnに達していたら、arrを返す。ただし、この場合すべての数列の長さが同じであるので、
    //先頭の数列のみで判断している
    if (arr.head.length == n) {
      //returnを省略している
      arr
    } else {
      //各数列に対して、末尾に数字を追加した数列群を生成し、それらをフラットに一つの数列にする
      /*
       * 例えば、m=2のとき、arr=[[1,1,1],[1,1,2]]ならば（本当はあり得ないが）
       * [1,1,1]から[[1,1,1,1],[1,1,1,2]]を生成し、
       * [1,1,2]から[1,1,2,2]を生成する。
       * このままだと[[[1,1,1,1],[1,1,1,2]],[1,1,2,2]]と入り組んでいるので、
       * [[1,1,1,1],[1,1,1,2],[1,1,2,2]]とフラットにする
       * */
      bfs(arr.flatMap(ar => {
        for (i <- ar.last to m) yield {
          ar :+ i
        }
      }), m, n)
    }
  }

  def debug(args: Any*): Unit = {
    Console.err.println(args.mkString(" "))
  }
}


Measured memory_bytes: 69796
import itertools
import math
n = int(input())

x = [list(map(int, input().split())) for i in range(n)]

result = 0.0
sz = 0

for item in itertools.permutations(range(n)):
    sz += 1
    ct = 0
    for i in item:
        if ct == 0:
            prev = i
            ct += 1
            continue
        result += math.sqrt(math.pow(x[i][0]-x[prev][0], 2) + math.pow(x[i][1]-x[prev][1], 2))
        prev = i

print(result/sz)

Measured memory_bytes: 3064
n, m = map(int, input().split())
P = [0]*n
AC = [False]*n
correct = 0
penalty = 0
for i in range(m):
  ans = input().split()
  problem = int(ans[0])
  result = ans[1]
  if AC[problem-1] == False:
    if result == 'AC':
      AC[problem-1] = True
      correct += 1
      penalty += P[problem-1]
    else:
      P[problem-1] += 1
print(correct, penalty)

Measured memory_bytes: 10304
#include <bits/stdc++.h>
using namespace std;
//#include "testlib.h"
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define int long long
#define ll long long
#define M 1000000007
#define MM 998244353
#define inputarr(a,n) for(int i=0;i<n;++i) cin>>a[i]
#define GCD(m,n) __gcd(m,n)
#define LCM(m,n) m*(n/GCD(m,n))
#define mii  map<ll ,ll >
#define sz(a) (int)a.size()
#define msi  map<string,ll >
#define rep(a,b)    for(ll i=a;i<b;i++)
#define rep0(n)    for(ll i=0;i<n;i++)
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#define vi vector<ll>
#define vs vector<string>
#define ppb pop_back
#define endl '\n'
#define asdf ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define r0 return 0;
#define FORD(i, a, b) for (int i = (int) (a); i >= (int) (b); --i)
#define inputoutput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define Set(a, s) (a, s, sizeof (a))
#define FOR repi
#define pii pair<int,int>
#define REVERSE(v) reverse(all(v))
#define trav(a, x) for(auto& a : x)
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl
#define debug cerr<<"bhau"<<endl
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
template<typename T, typename U> static inline void amin(T &x, U y) 
{ 
    if (y < x) 
        x = y; 
}
template<typename T, typename U> static inline void amax(T &x, U y) 
{ 
    if (x < y) 
        x = y; 
}
 
ll max(ll a, ll b) { return (a > b)? a : b;}
int min(int a, int b) { return (a < b)? a : b;} 


int solve(){


	int a[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	int k;cin>>k;
	cout<<a[k-1];

    return 0;
}
signed main(){
    asdf
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


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

using namespace std;

typedef long long ll;

const ll maxn = 2e5;
const ll ZERO = 0;
const ll SADAT = 7.84e-17;
const ll INF = 1e9;
const ll mod = 1e9+7;

#define endl '\n'
#define dokme(x) cout << x ;  return(0);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_init freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);



int main(){
    migmig
    int n , a[maxn];
    cin >> n;
    for (int i =0  ;i < n ; i ++){
        cin >> a[i];
    }
    ll ans = 0;
    for (int i = 0 ; i < n ; i ++){
        for (int j = i+1 ; j < n ; j ++){
            ans += a[i]*a[j];
        }
    }
    cout << ans;

    return(0);
}



//When we hit our lowest point, we are open to the greatest change.
//If I try, I fail. If I don't try, I'm NEVER GOING TO GET IT.
//Sometimes, life is like this dark tunnel. You can't always see the light at the end of the tunnel. But if you just keep moving... you will come to a better place.
//It is important to draw wisdom from diffrent places. If you take it from only one place it becomes rigid and stale.


Measured memory_bytes: 256
n,x = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

ans = 0

for i in range(n):
  x -= A[i]
  if x >= 0:
    ans += 1
  else:
    break
    
if x > 0:
  print(ans-1)
else:
  print(ans)


Measured memory_bytes: 2940
#include <iostream>
#include <cmath>

using namespace std;

int main(int argc, char const* argv[])
{
	double x,y;
	x = 1;y = 0;

	int n;

	while( cin >> n && n != -1 ){
		x = 1;y = 0;
		for( int i = 0;i < n - 1;i++ ){
			double a = atan2( y, x ) + 3.14159265 / 2;
			x += cos( a );
			y += sin( a );
		}

		printf("%.2f\n",x);
		printf("%.2f\n",y);
	}

	return 0;
}

Measured memory_bytes: 0
c=(0..M=18).map{[0]*19}
p`sed 1d`.split.sum{|a|a=(a.to_r*10**9).to_i
i=j=0
i+=1while a[i]<1
i>M&&i=M
(j+=1;a/=5)while a%5<1
j>M&&j=M
s=c[M-i..].sum{_1[M-j..].sum}
c[i][j]+=1;s}

Measured memory_bytes: 33640
import java.util.Scanner;
public class Main
{
	public static void main(String[] args) 
	{
		Scanner in=new Scanner(System.in);
		for(;;)
		{
			double S1=0,S2=0;
			int angle1=0,angle2=0;
			int m1=in.nextInt();
			if(m1==0)
				return;
			for(int i=0;i<m1-1;i++)
			{
				double vi=in.nextInt();
				angle1+=vi;
				S1+=Math.sin(vi*Math.PI/180);
			}
			S1+=Math.sin((360-angle1)*Math.PI/180);
			int m2=in.nextInt();
			for(int i=0;i<m2-1;i++)
			{
				double vi=in.nextInt();
				angle2+=vi;
				S2+=Math.sin(vi*Math.PI/180);
			}
			S2+=Math.sin((360-angle2)*Math.PI/180);
			if(Math.abs(S1-S2)<1e-8)//1e-8=0.00000001
				System.out.println(0);
			else if(S1>S2)
				System.out.println(1);
			else if(S2>S1)
				System.out.println(2);
			
		}
	}
}

Measured memory_bytes: 12000
#include<cstdio>
int n,i,e,w,s=1e9,a[1<<19];char c[1<<19];main(){for(scanf("%d\n",&n);i<n;scanf("%c",c+i),a[i]=w,w+=c[i++]==87);for(;i>0;s=s<a[--i]+e?s:a[i]+e,e+=c[i]==69);printf("%d",s);}

Measured memory_bytes: 1664
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {
            int i = 0;
            double m = 0, sum = 0, a = 0, b = 0;
            double[] rem;

            int n = sc.nextInt();
            if(n==0)
                break;

            rem = new double[n];
            
            for (i = 0; i < n; i++) {
                int num = sc.nextInt();
                rem[i] = num;
                sum += num;
            }

            m = sum / n;

            for (i = 0; i < n; i++) {
                b += (rem[i] - m) * (rem[i] - m);
            }
            a = Math.sqrt(b / n);

            System.out.println(a);
        }
    }
}



Measured memory_bytes: 31112
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
#define INF 200000000000
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()

bool compare(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}
// 入力



int main() {
    ll K,X;
    cin >>K>>X;
    if(500*K>=X){
        cout <<"Yes" << endl;
    }else{
        cout <<"No" << endl;
    }
    


    return 0;
    

}

Measured memory_bytes: 3612
#include<iostream>
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
#define N 200020
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
deque<char> q;
int n,st;
char s[N],c[3];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++){
		q.push_back(s[i]);
	}
	n=read();
	for(int i=1;i<=n;i++){
		int opt=read();
		if(opt==1){
			st^=1;
		}
		else{
			int x=read()-1;
			scanf("%s",c+1);
			if(x^st){
				q.push_back(c[1]);
			}
			else{
				q.push_front(c[1]);
			}
		}
	}
	if(st){
		for(int i=q.size()-1;i>=0;i--){
			cout<<q[i];
		}
	}
	else{
		for(int i=0;i<q.size();++i){
			cout<<q[i];
		}
	}
	return 0;
}


Measured memory_bytes: 896
n,m = map(int,input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
asum= sum(a)
pop=0

for i in range(n):
  if a[i]>=asum/(4*m):
    pop = pop+1
    if pop == m:
      break
if pop==m:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#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)
const lint mod=1e9+7;

int main()
{
  lint n;
  cin >> n;
  lint cnt = 0;
  REP(i,n){
    if((i+1)%3 != 0 && (i+1)%5 != 0) cnt += i+1;
  }
  cout << cnt<< "\n";
  return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>
#include<map>
#include<deque>
#include<cstdio>
#include<cstdio>
#include<time.h>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define pd(a,n) for(int i=0;i<n;i++)cout<<a[i]<<((i==n-1)?"\n":" ")
#define pdd(a,n,m)for(int i=0;i<m;i++)pd(a,m)
#define mp make_pair
#define pb push_back
#define ll __int64
#define __int64 long long
#define P pair<int,int>
#define PP pair<P,int>

ll n,k;
ll a[222222];
///3 3 -4 -2
///-4 -2 3 3
bool func(ll x){
  ll cnt=0;

  rep(i,n){
    if(a[i]>0){
      ll ok=-1,ng=n;
      while(abs(ok-ng)>1){
        ll mid=(ok+ng)/2;
        ((a[i]*a[mid]<x)?ok:ng)=mid;
      }
      cnt+=ok+1;
    }
    else if(a[i]<0){
      ll ng=-1,ok=n;
      while(abs(ok-ng)>1){
        ll mid=(ok+ng)/2;
        ((a[i]*a[mid])<x?ok:ng)=mid;
      }
      cnt+=n-1-ng;
    }
    else{
      if(x>0)cnt+=n;
    }
    if(a[i]*a[i]<x)
      cnt--;
  }

  //cout<<x<<" "<<cnt/2<<endl;
  return (cnt/2<k);
}

int main(){
  cin>>n>>k;
  rep(i,n)cin>>a[i];
  sort(a,a+n);
  ll INF=3e18;
  ll ok=-INF,ng=INF,mid;
  while(abs(ok-ng)>1){
    mid=(ok+ng)/2;
    ((func(mid))?ok:ng)=mid;
  }
  cout<<ok<<endl;
  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
string s;
long long dfs(int x,long long cur,long long sum)
{
	if(x==s.size())
	{
		return sum;
	}
	int d=s[x]-'0';
	long long res=0;
	if(x+1!=s.size())
	{
		res+=dfs(x+1,cur*10+d,sum);
	}
	res+=dfs(x+1,0,sum+cur*10+d);
	return res;
}
int main()
{
	cin>>s;
	long long ans=dfs(0,0,0);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>

int n,q;
int m[51];
int cnt[101];

int main(void){
	while(1){
		scanf("%d %d",&n,&q);
		if(n+q==0)break;
		memset(cnt,0,sizeof(cnt));
		for(int i=0;i<n;i++){
			scanf("%d",&m[i]);
			for(int j=0;j<m[i];j++){
				int data;
				scanf("%d",&data);
				cnt[data]++;
			}
		}
		int res=0;
		for(int i=1;i<=100;i++){
			if(cnt[i]>=q && cnt[i]>cnt[res])res=i;
		}
		printf("%d\n",res);
	}
	return 0;
}

Measured memory_bytes: 1028
import java.math.BigInteger;
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        HashMap<Integer, Integer> h = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(sc.next());
            if (h.containsKey(a)) {
                h.put(a, h.get(a) + 1);
            } else {
                h.put(a, 1);
            }
        }
        sc.close();
        boolean f = true;
        for (int k : h.keySet()) {
            if (n % 2 == 1 && k == 0) {
                if (h.get(k) != 1) {
                    f = false;
                    break;
                }
            } else if (h.get(k) != 2) {
                f = false;
                break;
            }
        }
        BigInteger bn = new BigInteger("2");
        BigInteger bm = new BigInteger("1000000007");
        BigInteger bp = new BigInteger(Integer.toString(n / 2));
        System.out.println((f ? bn.modPow(bp, bm) : 0));
    }
}

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

int a[200020];

int main(){
    string s;
    cin>>s;
    int n=s.size();
    reverse(s.begin(),s.end());
    map<int,int>mp;
    mp[0]=1;
    int cnt=0,ten=1;
    rep(i,n){
        cnt=(cnt+(s[i]-'0')*ten)%2019;
        ten*=10;
        ten%=2019;
        mp[cnt]++;
    }
    ll ans=0;
    for(auto&p:mp){
        ans+=p.second*(p.second-1)/2;
    }
    cout<<ans<<endl;
}

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

int main(void) {
  string s;
  cin >> s;
  int ans = 0, head = 0, tail = (int)s.length() - 1;
  while (head < tail) {
    if (s[head] != s[tail]) {
      ans++;
    }
    head++;
    tail--;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

ll inf=1e9;

int main() {
  ll n,m;
  cin >> n >> m;
  vector<ll> c(m);
  for(ll i=0;i<m;i++) {
    cin >> c[i];
  }
  vector<ll> dp(n+1,inf);
  dp[0]=0;
  for(ll i=1;i<=n;i++) {
    for(ll j=0;j<m;j++) {
      if(i>=c[j]) {
        dp[i]=min(dp[i-c[j]]+1,dp[i]);
      }
    }
  }
  cout << dp[n] << endl;
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define int ll

signed main(){
    ios::sync_with_stdio(false);
    int n,w;
    cin >> n >> w;
    vector<vector<int>> items(4);
    int v1,w1;
    cin >> w1 >> v1;
    items[0].push_back(v1);
    rep(i,n-1) {
        int v,w;
        cin >> w >> v;
        items[w-w1].push_back(v);
    }
    vector<vector<int>> s(4);
    rep(i,4) {
        s[i].push_back(0);
        if(items[i].size() == 0) continue;
        sort(items[i].begin(), items[i].end(), greater<int>());
        rep(j, items[i].size()) s[i].push_back(s[i][j] + items[i][j]);
    }
    int val_max = 0;
    rep(i0,s[0].size())
    rep(i1,s[1].size()) 
    rep(i2,s[2].size()) 
    rep(i3,s[3].size()) {
        int w_sum = i0*w1 + i1*(w1+1) + i2*(w1+2) + i3*(w1+3);
        int val_sum = s[0][i0] + s[1][i1] + s[2][i2] + s[3][i3];
        if (w_sum > w) continue;
        chmax(val_max, val_sum);
    }
    cout << val_max << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

long dp[100000][2];


int main(){
    int N;
    cin >> N;
    vector<long> A(N);

    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    dp[0][0] = 0;
    dp[0][1] = -1000000;

    for(int i = 0; i < N; i++) {
        dp[i+1][0] = max(dp[i][0] + A[i], dp[i][1] - A[i]);
        dp[i+1][1] = max(dp[i][0] - A[i], dp[i][1] + A[i]);
    }
    
    cout << dp[N][0] << endl;;
    return 0;
}


Measured memory_bytes: 2560
#include <iostream>
using namespace std;
int main() {
	while(true){
	int n[1000],m[1000],a,b,c=1,d=0,e=-1;
	cin>>a>>b;
	if(a==0 and b==0)break;
	for(int i=0;i<a;i++){
		cin>>n[i];
	}
	for(int i=0;i<b;i++){
		cin>>m[i];
	}
	while(true){
		d=d+1;
		e=e+1;
		c=c+m[e];
		c=c+n[c-1];
		if(c>=a)break;
	}
	cout<<d<<endl;
	}
	return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <iomanip>

using namespace std;


int main() {
	int n, k;
	long double p = 0;

	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		int tmp = i;
		long double pt = 1;
		while (tmp < k) {
			tmp *= 2;
			pt /= 2;
		}
		p += pt;
	}


	cout << std::fixed << std::setprecision(12) << p/n << endl;
	
	return 0;
}




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


namespace ConsoleApp15
{
    class Class308
    {
        static void Main()
        {
            var r = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[][] pos = new int[4][];
            for (int i = 0; i < 4; i++) pos[i] = new int[2];
            pos[0] = new int[2] { r[0], r[1] };
            pos[1] = new int[2] { r[2], r[3] };
            pos[2] = new int[2] { pos[1][0] - (pos[1][1] - pos[0][1]), pos[1][1] + (pos[1][0] - pos[0][0]) };
            pos[3] = new int[2] { pos[2][0] - (pos[2][1] - pos[1][1]), pos[2][1] + (pos[2][0] - pos[1][0]) };
            Console.WriteLine($"{pos[2][0]} {pos[2][1]} {pos[3][0]} {pos[3][1]}");
        }
    }
}


Measured memory_bytes: 13268
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
#define node_num 100005
#define edge_num 400005
#define INF 100000000
class node {
public:
	//这里的dis并不是主要的dis，只是用来比较，完善pq的
	int id, dis;
	bool operator <(const node& a)const {
		return a.dis < dis;
	}
};
int pre[edge_num];
int to[edge_num];
int val[edge_num];
int ans[node_num];
int tot;   //从1开始
int last[node_num];
int ndis[node_num];
int used[node_num];
void add(int u, int v) {
	tot++;
	to[tot] = v;
	val[tot] = 1;
	pre[tot] = last[u];
	last[u] = tot;
}
int n, m;
int a, b, c;
int main() {
	priority_queue<node> qu;
	scanf("%d%d", &n, &m);
	fill(ndis, ndis + node_num, INF);
	ndis[1] = 0;
	/*数据输入*/
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		add(a, b);
		add(b, a);
	}
	qu.push(node{ 1,ndis[1] });
	/*主循环*/
	while (!qu.empty()) {
		/*弹出元素*/
		int x = qu.top().id;
		int ptr = last[x];
		qu.pop();
		/*判断终止*/
		if (used[x])continue;
		used[x] = 1;
		/*遍历松弛*/
		while (ptr) {
			int y = to[ptr];
			if (!used[y] && ndis[y] > ndis[x] + val[ptr]) {
				ndis[y] = ndis[x] + val[ptr];
				ans[y] = x;
				qu.push(node{ y,ndis[y] });
			}
			ptr = pre[ptr];
		}
	}
	bool flag = true;
	for (int i = 2; i <= n; i++) {
		if (ndis[i] == INF) {
			flag = false;
			break;
		}
	}
	if (flag) {
		printf("Yes\n");
		for (int i = 2; i <= n; i++) {
			printf("%d\n", ans[i]);
		}
	}
	else printf("No\n");
}

Measured memory_bytes: 10032