akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
const int INF=100000000;

int main(){
	LL n,k;
	cin>>n>>k;
	
	cout<<min(n%k,k-(n%k))<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main
{
	public static void main(String[] args) 
	{
		Scanner in=new Scanner(System.in);
		for(;;)
		{
			int n=in.nextInt();
			if(n==0)
				return;
			Point p[]=new Point[n];
			boolean exist[][]=new boolean[5001][5001];
			int max=0;
			for(int i=0;i<n;i++)
			{
				int x=in.nextInt(),y=in.nextInt();
				p[i]=new Point(x,y);
				exist[x][y]=true;
			}
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
				{
					if(i==j)
						continue;
					int x1=p[i].x,y1=p[i].y;
					int x2=p[j].x,y2=p[j].y;
					if(x2-y2+y1>=0&&y2+x2-x1>=0&&x1+y1-y2>=0&&y1+x2-x1>=0)
						if(x2-y2+y1<=5000&&y2+x2-x1<=5000&&x1+y1-y2<=5000&&y1+x2-x1<=5000)
							if(exist[x2-y2+y1][y2+x2-x1]&&exist[x1+y1-y2][y1+x2-x1])
								max=Math.max(max,(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
				}
			System.out.println(max);
		}
	}
	static public void debug(Object... o)
	{
		System.err.println(Arrays.deepToString(o));
	}
}
class Point
{
	int x;
	int y;
	Point(int x,int y)
	{
		this.x=x;
		this.y=y;
	}
}

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

int main(){
    int r;
    cin >> r;
    if(r>=2800) cout << "AGC" << endl;
    else if(r>=1200) cout << "ARC" << endl;
    else cout << "ABC" << endl;

    return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<stack>
 
using namespace std;
 
struct Node{
 Node *right;
 Node *left;
 Node *parent;
 int key;
public:
 Node(Node *r,Node *l,Node *p,int k) : right(r), left(l), parent(p), key(k){};
};
 
class Tree{
 Node *root;
public:
 Tree(){root = 0;}
 
 
 void insert(int v){
  Node *z = new Node(0,0,0,v);
  Node *y = 0;
  Node *x = root;
  while(x != 0){
   y = x;
   if(z->key < x->key){
    x = x->left;
   }else{
    x = x->right;
   }
  }
  z->parent = y;
  if( y == 0){
   root = z;
  }else if(z->key < y->key){
   y->left = z;
  }else{
   y->right = z;
  }
 } 
 
 void mainoutput(Tree tree){
  outputInorder(tree);
  outputPreorder(tree);
 }
 
 void outputPreorder(Tree tree){
  stack<Node*> pre;
  pre.push(tree.root);
  while(!pre.empty()){
   Node *buf = pre.top(); pre.pop();
   cout <<" "<< buf->key;
   if(buf->right != 0) pre.push(buf->right);
   if(buf->left != 0) pre.push(buf->left);
  }
  cout << '\n';
 }
 
 void outputInorder(Tree tree){
 
  if(tree.root == 0) return ;
 
  Node* cur = tree.root;
  Node* prev = cur->parent;
  while(cur != 0){
   if(cur->parent == prev){
 
    //Preorder
    //cout << " " << cur->key;
 
    if(cur->left != 0){
     prev = cur;
     cur = cur->left;
     continue;
    }else{
     prev = cur->left;
    }
   }
 
   if(prev == cur->left){
    //inorder
    cout << " " << cur->key;
 
    if(cur->right != 0){
     prev = cur;
     cur = cur->right;
     continue;
    }else{
     prev = cur->right;
    }
   }
 
   if(prev == cur->right){
    //postorder
    //cout << " " << cur->key;
 
    prev = cur;
    cur = cur->parent;
   }
  }
 cout << endl;
 }
};
 
int main(){
 std::ios::sync_with_stdio(false);
 std::cin.tie(0); 
 
 Tree tree;
 
 int n = 0;
 cin >> n;
 
 for(int i=0; i < n; i++){
  string str = "";
  int num = -1;
  cin >> str;
  if(str == "insert"){
   cin >> num;
   tree.insert(num); 
  }else if(str == "print"){
   tree.mainoutput(tree); 
  }
 }
 
  
 return 0;
}

Measured memory_bytes: 24668
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define PI 3.141592653589793238
int main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("/home/pushkar/cpp/input.txt", "r", stdin);
    // freopen("/home/pushkar/cpp/output.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    string s;
    map <string, ll> mp;
    while (n--)
    {
        cin >> s;
        mp[s]++;
    }
    cout << "AC x " << mp["AC"] << "\n";
    cout << "WA x " << mp["WA"] << "\n";
    cout << "TLE x " << mp["TLE"] << "\n";
    cout << "RE x " << mp["RE"] << "\n";
    return 0;
}

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

int main() {
	int n, m;
	cin >> n >> m;
	string s[n];
	for(int i = 0; i < n; i++) {
		cin >> s[i];
	}
	int dp[n][m];
	memset(dp, 0, sizeof dp);

	dp[0][0] = 1;	
	const int md = 1e9 + 7;

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(s[i][j] == '.') {
				if(i > 0) {
					dp[i][j] = (dp[i][j] + dp[i - 1][j]) % md;
				}
				if(j > 0) {
					dp[i][j] = (dp[i][j] + dp[i][j - 1]) % md;
				}
			}
		}
	}
	cout << dp[n - 1][m - 1];
}

Measured memory_bytes: 5248
import java.util.Scanner;

public class Main{
  static final long INF = Long.MAX_VALUE;
  static int n;
  static long[] a;

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

    n = sc.nextInt();
    a = new long[n];
    for(int i = 0; i < n; i++){
      a[i] = sc.nextInt();
    }

    long sum = 0;
    for(int i = 0; i < n; i++){
      sum += a[i];
    }

    long min = INF;
    long x = 0;
    for(int i = 0; i < n - 1; i++){
      x += a[i];
      long y = sum - x;
      min = Math.min(min, Math.abs(x - y));
    }

    System.out.println(min);
  }
}

Measured memory_bytes: 65572
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = str(input())

point = [0] * n
for i in range(n):
    if t[i] == 'r':
        point[i] = p
    elif t[i] == 's':
        point[i] = r
    elif t[i] == 'p':
        point[i] = s

for i in range(k, n):
    if (t[i-k] == t[i]) and point[i-k]>0:
        point[i] = 0
print(sum(point))


Measured memory_bytes: 4084
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, T: int, c: "List[int]", t: "List[int]"):
    try:
        print(min(ci for ci, ti in zip(c, t) if ti <= T))
    except ValueError:
        print("TLE")


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    c = [int()] * (N)  # type: "List[int]"
    t = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        c[i] = int(next(tokens))
        t[i] = int(next(tokens))
    solve(N, T, c, t)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<iostream>
#include<string>
using namespace std;
int main(void) {
    int i;
    string  str;
    cin >> str;
    for (i = 0; i < str.size(); i++)
    {
        if (str[i] < 'D')
            str[i] = str[i] + 23;
        else
            str[i] = str[i] - 3;
    }
        cout << str<< endl;
    return 0;
}

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

using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x) ((int) x.size())
#define all(x) (x).begin(), (x).end()
#define re return
#define mp make_pair
#define makeunique(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define endl '\n'

typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<string> vs;

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }

const double pi = acos(-1.);
const int mod = 1e9 + 7;
const int N = 3e5 + 17;

int n, m;
ll f[N];

ll power(ll x, ll y) {
	ll ans = 1;
	while (y) {
		if (y & 1) ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}

ll cnk(int n, int k) {
//	cout << n << " " << k << endl;
	auto den = f[k] * f[n - k] % mod;
	auto ans = f[n] * power(den, mod - 2) % mod;
	re ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int a, b;
	cin >> n >> m >> a >> b;
	f[0] = 1;
	for (int i = 1; i < N; i++)
		f[i] = i * f[i - 1] % mod;
	ll ans = 0;	
	for (int i = b + 1; i <= m; i++) {
		auto l = cnk(n - a - 1 + i - 1, i - 1);
		auto r = cnk(a - 1 + m - i, a - 1);
//		cout << i << " " << l << " " << r << endl;
		ans += l * r % mod;		
	}
	cout << ans % mod;	
}


Measured memory_bytes: 5968
import java.util.Scanner;

class Main {

  private static int D, G;
  private static int[] p, c;

  private static int INF = Integer.MAX_VALUE / 4;

  public static int rec(int i, int sum, int s) {

    if (sum >= G) {
      return 0;
    }

    if (i == D + 1) {
      int cnt = 0;
      for (int j = D; j > 0; j--) {
        if ((s >> j - 1 & 1) == 1) {
          if (sum + j * (p[j - 1] - 1) < G) {
            continue;
          }
          while (sum < G) {
            sum += j;
            cnt++;
          }
          return cnt;
        }
      }
      return INF;
    }

    int res0 = rec(i + 1, sum + i * p[i - 1] + c[i - 1], s - (1 << i - 1)) + p[i - 1];
    int res1 = rec(i + 1, sum, s);

    return Math.min(res0, res1);

  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    D = scanner.nextInt();
    G = scanner.nextInt() / 100;
    p = new int[D];
    c = new int[D];
    for (int i = 0; i < D; i++) {
      p[i] = scanner.nextInt();
      c[i] = scanner.nextInt() / 100;
    }
    System.out.println(rec(1, 0, (1 << D) - 1));
  }

}


Measured memory_bytes: 23252
n,a,b = map(int,input().split())
ans = 0

def sum_digit(n):
    sum = 0
    while True:
        sum += n%10
        if n//10 > 0:
            n //= 10
        else:
             break
    return sum

for i in range(1,n+1):
    sum = sum_digit(i)
    if a <= sum and sum <= b:
        ans += i

print(ans)


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

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

  sort(a, a+n);

  int ans = 0;
  while(x - a[ans] >= 0){
    x -= a[ans];
    ans++;
    if(ans == n-1){
      if(x == a[ans]){
        ans++;
      }
      break;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
using namespace std;
int main() {
  long long N;
  cin >> N;
  long long s = sqrt(N);
  long long r = 0;
  vector<pair<long long, long long>> a;
  
  for (long long i = 2; i <= s; ++i) {
    if ((N % i) == 0) {
      r = 0;
      do {
        r++;
        N = N / i;
      } while ((N % i) == 0);
      a.push_back(make_pair(i, r));
    } 
  }

  if (N > s) {
    a.push_back(make_pair(N, 1));
  }
  
  long long ans = 0;
  for (auto &x : a) {
    long long &n = x.second;
    for (int i = 1; n - i >= 0; ++i) {
      ++ans;
      n -= i;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3724
#入力
N, M = map(int, input().split())

#入力: 電球iについての情報
lst = []
for i in range(M):
    a = list(map(int, input().split()))
    lst += [a]
#入力: どのような情報であればOKかのリスト
p = list(map(int, input().split()))

# print ('lst', lst)

#計算部分
ans = 0 #全探索用の答え
for i in range(2 ** N): #1をon, 0をoffとする2bit
    #最大でもスイッチは10桁＋2進数であることを表す部分2桁
    a = format(i, '012b')
    #2進数をリストとして保存, 前2桁は2進数であることを表す部分のため不要 
    lst2 = list(a[2:]) #右からスイッチ1, 2, ... Nと逆順になっていることに注意
    # print ('lst2', lst2)
    #あるスイッチの付け方が題意を満たしているか判断するフラグ
    flag = True 
    l = 0 #電球番号-1(リストのため)
    for j in lst: #i番目のスイッチの繋がっていることの情報
        # print ('j[1:]', j[1:])
        count = 0 #ONのスイッチの個数を数える
        for k in j[1:]: #s_i番目のスイッチの状態を読み出す、最初の一桁はスイッチの数
            # print ('k', k)
            if lst2[9-k+1] == '1': #ONの時、カウントを増やす
                count += 1
                # print ('B')
        # print ('count', count)
        # print ('p[l]', p[l])
        if count%2 != p[l]: #ONになっているスイッチの数//2が題意を満たしているかを判断
            flag = False #題意を満たしていなかったらフラグをFalseにする
            # print ('C')
        l += 1 #電球番号を一つ増やす
    if flag: #全ての電球を確認して、フラグがまだTrueなら答えを+1
        ans += 1
        # print ('A')

print (ans)

Measured memory_bytes: 41200
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main(){
    double a, b, h, m, c;
    cin >> a >> b >> h >> m;
    h = h*30.0 + m/2.0;
    m = m*6.0;
    double angle;
    angle = abs(h-m);
    angle = angle * 3.14159265359 / 180.0;
    if(angle==0){
        c = abs(a-b);
    }else{
        c = a*a + b*b - 2.0*a*b*cos(angle);
        c = sqrt(c);
    }
    cout << fixed << setprecision(10) << c;

    return 0;
}

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

int main(){
                                                                     

    int a, b;

    int m = 0;

    
    cin >> a >> b;


    m = max( a + b, a - b );

    m = max( m, a * b );


    cout << m << endl;

    return 0;

    }

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(void){
	double s, h, x;
	while (1){
		scanf("%lf%lf", &x, &h);
		if (x == 0 && h == 0)break;
		s = x*x;
		h = sqrt(h*h+x*x/4);
		s += 2*x*h;
		printf("%.9f\n", s);
	}
	return 0;
}

Measured memory_bytes: 648
n,k=map(int,input().split())

ans=0
A=[i for i in range(n+1)]
for i in range(1,n+1):
    A[i]+=A[i-1]

B=[i for i in range(n+1)]
for i in reversed(range(n)):
    B[i]+=B[i+1]

for i in range(k,n+2):
    ans+=B[-i]-A[i-1]+1
print(ans%(10**9+7))

Measured memory_bytes: 30076
using System;

class AGC_035_A
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        string[] input = Console.ReadLine().Split(' ');

        int p0 = -1;
        int p1 = -1;
        int p2 = -1;
        int c0 = 0;
        int c1 = 0;
        int c2 = 0;

        for (int i = 0; i < N; i++)
        {
            int a = int.Parse(input[i]);

            if (p0 == a) { c0++; continue; }
            if (p1 == a) { c1++; continue; }
            if (p2 == a) { c2++; continue; }

            if (p0 < 0)
            {
                p0 = a;
                c0++;
            }
            else if (p1 < 0)
            {
                p1 = a;
                c1++;
            }
            else if (p2 < 0)
            {
                p2 = a;
                c2++;
            }
            else
            {
                Console.WriteLine("No");
                return;
            }
        }

        if(p1<0)
        {
            if(p0==0)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
        else if(p2<0)
        {
            if (p0 == 0)
            {
                if (c0*2 == c1)
                { 
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("No");
                }
            }
            else if (p1 == 0)
            {
                if (c0 == c1*2)
                {
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("No");
                }
            }
            else
            {
                Console.WriteLine("No");
            }
        }
        else
        {
            if (c0 == c1 && c0 == c2)
            {
                if ((p0 ^ p1) == p2)
                {
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("No");
                }
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}

Measured memory_bytes: 17632
n=int(input())
x=[]
for i in range(26):
	x.append(chr(ord('a')+i))

s=""
while(n>0):
	a=n%26
	if(a==0):
		a=26
		n=n//26-1
	else:
		n=n//26
	s=x[a-1]+s
print(s)

Measured memory_bytes: 61776
from decimal import Decimal
from math import floor
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    A,B = readline().split()
    A = int(A)
    B = Decimal(B)

    print(floor(A * B))


if __name__ == "__main__":
    main()


Measured memory_bytes: 10084
from collections import deque


s = str(input().rstrip())
ans = deque(list(s))

f = True
q = int(input())
for i in range(q):
    q = list(map(str, input().split()))
    if int(q[0]) == 1:
        if f:
            f = False
        else:
            f = True
    else:
        f_i = int(q[1])
        if f_i == 1:
            if f:
                ans.appendleft(q[2])
            else:
                ans.append(q[2])
        else:
            if f:
                ans.append(q[2])
            else:
                ans.appendleft(q[2])
ans = list(ans)
if f:
    print("".join(ans))
else:
    print("".join(ans[::-1]))


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

int main() {
  int n;
  cin >> n;
  int a[n];

  for(int i = 0; i < n; ++i){
    cin >> a[i];
  }
  
  bool ok = true;
  
  for(int i = 0; i < n; i++){
    if(a[i]%2 == 0){
      if(a[i]%3 != 0 && a[i] % 5 != 0){
        ok = false;
      }
    }
  }
  if(ok){
    cout << "APPROVED" << endl;
  }else{
    cout << "DENIED" << endl;
  }
}

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

typedef long long LL;

template<typename T>
void printmatrix(vector<vector<T> > ar){
    for (int i = 0; i < (int)ar.size(); i++) {
        for (int j = 0; j < (int)ar.size(); j++) {
            cout << ar[i][j];
        }
        cout << endl;
    }
}

template<typename T>
void printvector(vector<T> vec){
    for (int i = 0; i < (int)vec.size(); i++) {
        cout << vec[i] << endl;
    }
}

template<typename T>
void unique(vector<T>& vec){
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

template<typename T>
vector<T> cumsum(vector<T> vec){
    vector<T> newvec((T)vec.size());
    int tmp = 0;
    for (int i = 0; i < (int)vec.size(); i++) {
        tmp += vec[i];
        newvec[i] = tmp;
    }

    return newvec;
}


int main(int argc, char const* argv[])
{
    int n,a;
    cin >> n >> a;
    cout << n*n - a << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<int> A, ans;
int main()
{
    int N;
    cin >> N;
    for (int i = 0; i < N - 1;i++)
    {
        int temp;
        cin >> temp;
        A.push_back(temp);
        ans.push_back(0);
    }
    ans.push_back(0);
    for (int i = 0; i < N - 1;i++)
    {
        ans[A[i] - 1] += 1;
    }
    for (int i = 0; i < N;i++)
    {
        cout << ans[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 5020
#include <iostream>
#include <bits/stdc++.h>
#include <string>
using namespace std;
int main()
{
    int n,m,anum=0,wnum=0;
    cin>>n>>m;
    int wa[n+1];
    bool ac[n+1];
    for(int i=0;i<=n;i++)
      {
          ac[i]=false;
          wa[i]=0;
      }
    
    while(m--)
     {
         int p;string s;
         cin>>p>>s;
         if (s=="WA"&& ac[p]==false)
               ++wa[p];
         else if(s=="AC"&& ac[p]==false)
             ac[p]=true;
          else  
          continue;
     }
     
     for(int j=1;j<=n;j++)
       {
             if(ac[j])
               {
                   wnum+=wa[j];
                   anum++;
               }
       }
    
    cout<<anum<<" "<<wnum;
    return 0;
}

Measured memory_bytes: 768
#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
 
#define mod 1000000007
#define ll long long int
#define ld long double
#define gch(ch) scanf("%c",&ch)
#define gcharr(arr,n) FOR(i,0,n) gch(arr[i])
 
#define gi(x) scanf("%d",&x)
#define gi2(x,y) scanf("%d %d",&x,&y)
#define gi3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define pi(x) printf("%d ",x)
 
#define gll(x) scanf("%lld",&x)
#define gll2(x,y) scanf("%lld %lld",&x,&y)
#define gll3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define pll(x) printf("%lld ",x)
 
#define gld(x) scanf("%lf",&x)
#define pld(x) printf("%ld ",x)
 
#define pline printf("\n")
#define fori(i,a,b,c) for(ll i=a;i<b;i+=c)
#define ford(i,a,b,c) for(ll i=a;i>=b;i-=c)
#define mst(a,b) memset(a,b,sizeof a)
#define deb(x) cout<<#x<<" : "<<x<<endl;
#define debug(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<endl;
#define SYNC ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
ll gcd (ll a,ll b)
{
    if(b!=0)
        return gcd(b,a%b);
    else
        return a;
}
 
ll power(ll a,ll b)
{
    if(b==0)
    return 1;
    if(b==1)
    return a;
    if(b%2==0)
    {
        ll t=power(a,b/2);
        return t*t;
 
    }
    else
    {
        ll t=power(a,b/2);
        return a*t*t;
    }
}
ll powin(ll a,ll b)
{
    if(b==0)
        return 1;
    else if(b==1)
    return a;
    else if(b%2==0)
    {
        ll t=powin(a,b/2);
        return (t*t)%mod;
    }
    else
    {
        ll t=powin(a,b/2);
        return (((t*t)%mod)*a)%mod;
    }
}
#define N 100009
vector<int> v[N];
int a[N];
set<int> st;
int vis[N];
void dfs(int x)
{
    vis[x]=1;
    st.insert(x);
    for(int i=0;i<v[x].size();i++)
    {
        if(vis[v[x][i]]==0)
        {
            dfs(v[x][i]);
        }
    }
}
 
int main()
{
    SYNC
    int n,m;
    cin>>n>>m;
    int  ans=0;
    memset(vis,0,sizeof vis);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<m;i++)
    {
        static int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    set<int>:: iterator it; 
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            st.clear();
            dfs(i);
            for(it=st.begin();it!=st.end();it++)
            {
                int t=*it;
                if(st.find(a[t])!=st.end())
                {
                    ans++;
                }
                
            }
            
        }
        
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 14208
#include<iostream>

using namespace std;

int main(void){

	std::ios_base::sync_with_stdio();

	int dp[31]={0};
	int n;

	dp[0]=1;
	for(int i=1;i<=30;i++){
		if(i>=1) dp[i]+=dp[i-1];
		if(i>=2) dp[i]+=dp[i-2];
		if(i>=3) dp[i]+=dp[i-3];
	}

	while(1){
		cin>>n;
		if(n==0) break;
		cout<<dp[n]/365/10+1<<endl;
	}

	return 0;
}

Measured memory_bytes: 1160
/**
DufauX-XuafuD
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define reset(x) memset(x,-1,sizeof(x))
#define CheckBit(a,b) (a&(1ll<<b))
#define SetBit(a,b) a=(a|(1ll<<b))
#define UnSetBit(a,b) a=(a&(~(1ll<<b)))
#define maxx 10000006
#define PI 2*acos(0.0)
const long long INF = 2000000000000000000LL;	// 2e18
const int inf = 0x3f3f3f3f;	// 1061109567
const long double EPS = 1e-9;
//bitset<maxx/2>vis;
//bitset<maxx>pr;
//int mobi[maxx+10];
//vector<ll>prime;
//void sieve(){
//    ll x=maxx/2, y=sqrt(maxx)/2;
//    for(ll i=1;i<=y;i++){
//        if(vis[i]==0){
//            for(ll j=(i*(i+1)*2);j<x;j+=(2*i)+1)
//                vis[j]=1;
//        }
//    }
//    prime.push_back(2);
//    for(ll i=3;i<maxx;i+=2)
//        if(vis[i/2]==0)
//        prime.push_back(i);
//}
//void generate_mobius()
//{
//    for(int i=0;i<maxx;i++)mobi[i]=1;
//    for(int i=2;i<maxx;i++){
//        if(!pr[i]){
//            mobi[i]*=-1;
//            for(int j=i+i;j<maxx;j+=i){
//                pr[j]=1;
//                mobi[j]*=(j%(i*i)?-1:0);
//            }
//        }
//    }
//}
//bool isprime(ll a)
//{
//    if(a==1)return false;
//    if(a==2)return true;
//    if(a%2==0)return false;
//    for(ll i=0;i<prime.size() && prime[i]*prime[i]<=a;i++)
//        if(a%prime[i]==0)return false;
//    return true;
//}
/* Calculate ( a*b ) %c */
inline ll mulmod(ll a, ll b, ll c) {
    ll ret = 0 , cur = a % c ;
    while(b) { if(b%2) ret=(ret+cur)%c; cur=(cur<<1)%c; b=b>>1; }
    return ret%c;
}
//Calculate (b^p)%m || modular inverse: b^-1 = bigmod(b, m-2, m)
inline ll bigmod(ll b, ll p, ll m){
    ll ret = 1, cur = b % m;
    while(p) { if(p&1) ret=(ret*cur)%m; cur=(cur*cur)%m; p=p>>1; }
    return ret;
}
inline ll modulo(ll a,ll b,ll c) { //Same as big mod, use for numbers over 1e10
    ll ret = 1 , cur = a%c ;
    while(b) { if(b%2) ret=mulmod(ret,cur,c); cur=mulmod(cur,cur,c); b=b>>1; }
    return ret%c ;
}
inline ll power(ll b, ll p){
    ll ret = 1, cur = b;
    while(p) { if(p&1) ret=(ret*cur); cur=(cur*cur); p=p>>1; }
    return ret;
}
ll lcm(ll a,ll b)
{
    return (a/__gcd(a,b))*b;
}
ll gcd(ll a,ll b)
{
    return __gcd(a,b);
}
pll arr[100005];
void Dufaux()
{
    ll n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>arr[i].ff>>arr[i].ss;
    }
    sort(arr,arr+n);
    for(int i=0;i<n;i++){
        if(arr[i].ss>=m){
            cout<<arr[i].ff<<endl;
            return;
        }
        m-=arr[i].ss;
    }
}
int main()
{
    FastIO;
	///sieve();
	///generate_mobius();
	int test=1;
	while(test--){
        Dufaux();
	}
	return 0;
}






Measured memory_bytes: 5184
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
using ll = long long;

int main() {
	string S;
	cin >> S;
	int ss = S.size();
	int C = 0;
	for (int i = 0;i < ss;i++) {
		if (i % 2) {
			if (S[i] == 'g')
				C++;
		}
		else {
			if (S[i] == 'p')
				C--;
		}
	}
	cout << C << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#include <cmath>
using namespace std;
#define ll long long
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define deb(x) cout<<#x<<" : "<<x<<"\n";
#define debug(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\n";
#define deb_arr(a,n) {cout<<#a<<":";for(int i=0;i<n;i++) {cout<<a[i]<<" ";} cout<<'\n';}
#define deb_mat(dist,n,m) {cout<<#dist<<"\n";for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<dist[i][j]<<" ";}cout<<'\n';}}
#define ff first
#define ss second
#define ub upper_bound
#define lb lower_bound
#define all(a) (a).begin(),(a).end()
#define bs binary_search
#define sz size()
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ld long double
#define clr fflush(stdout);
//#define clr cout.flush();
#define N 200001
#define fpr(i,a,b) for(int i=a;i<b;i++)
#define fdr(i,a,b) for(int i=a;i>b;i--)
#define repp(i,a,b,d) for(int i=a;i<b;i+=d)
#define repd(i,a,b,d) for(int i=a;i>b;i-=d)
#define LLMIN LLONG_MIN
#define LLMAX LLONG_MAX
#define AKASH_PATEL ios_base::sync_with_stdio(false);
#define SVNIT_SURAT cin.tie(NULL);cout.tie(NULL);
#define mset(x,a) memset(x,a,sizeof(x));
#define nl cout<<'\n';
#define print(c) cout<<c<<'\n';
#define setp(n) cout << fixed << setprecision(n)
#define take_arr(a,n) fpr(i,0,n) cin>>a[i];
#define print_arr(a,n) for(int i=0;i<n;i++) {cout<<a[i]<<" ";} cout<<'\n';
#define take_mat(mat,n,m) fpr(i,0,n) fpr(j,0,m) cin>>mat[i][j];
#define set_mat(mat,n,m,k) fpr(i,0,n) fpr(j,0,m) mat[i][j]=k;
#define print_mat(dist,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<dist[i][j]<<" ";}cout<<'\n';}
template< class T > bool inside(T a, T b, T c) { return a<=b && b<=c; }
template< class T > bool odd(T a) { return a&1; }
template< class T > bool even(T a) { return !(a&1); }
#define pi 
int main()
{
//#ifndef ONLINE_JUDGE
//    freopen("../ip.txt", "r", stdin);
//    freopen("../op.txt", "w", stdout);
//#endif
    AKASH_PATEL;
    SVNIT_SURAT;
    int t=1;
    //cin>>t;
    while(t--)
    {
        double r;
        cin>>r;
        setp(6)<<2*M_PI*r<<'\n';
    }
    return 0;
}





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

namespace AtCoder.Abc173
{
    class E
    {
        static long mod = 1000000007;

        public static void Main()
        {
            var nk = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var n = nk[0];
            var k = nk[1];

            long ans = 1;
            var a = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();

            if (n == k)
            {
                Console.WriteLine(a.Aggregate(1L, (acc, x) => acc = acc * (mod + x) % mod));
                return;
            }

            if (a.All(x => x <= 0))
            {
                if (k % 2 == 1)
                    a = a.OrderByDescending(x => x).ToArray();
                else
                    a = a.OrderByDescending(x => Math.Abs(x)).ToArray();
                Console.WriteLine(a.Take(k).Aggregate(1L, (acc, x) => acc = acc * (mod + x) % mod));
                return;
            }

            a = a.OrderByDescending(x => Math.Abs(x)).ToArray();

            bool positive = true;
            int nlast = 0;
            int plast = -1;
            for (int i = 0; i < k; i++)
            {
                if (a[i] < 0)
                {
                    positive = !positive;
                    nlast = i;
                }
                else
                    plast = i;
            }

            // 上位K個の積が正なら
            if (positive)
            {
                for (int i = 0; i < k; i++)
                    ans = ans * (a[i] > 0 ? a[i] : (mod + a[i])) % mod;
                Console.WriteLine(ans);
                return;
            }

            int nalt = -1;
            for (int i = k; i < a.Length; i++)
            {
                if (a[i] >= 0)
                {
                    nalt = i;
                    break;
                }
            }

            int palt = -1;
            for (int i = k; i < a.Length; i++)
            {
                if (a[i] < 0)
                {
                    palt = i;
                    break;
                }
            }

            if (plast >= 0 && palt >= 0)
            {
                if (nlast >= 0 && nalt >= 0)
                {
                    if (a[palt] * a[nlast] > a[nalt] * a[plast])
                        ans = Prod(a, k, plast, palt);
                    else
                        ans = Prod(a, k, nlast, nalt);
                }
                else
                    ans = Prod(a, k, plast, palt);
            }
            else if (nlast >= 0 && nalt >= 0)
                ans = Prod(a, k, nlast, nalt);
            else
                ans = 0;
            Console.WriteLine(ans);
        }

        static long Prod(long[] a, int k, int skip, int alt)
        {
            long ans = (mod + a[alt]) % mod;
            for (int i = 0; i < k; i++)
                if (i != skip)
                    ans = ans * (mod + a[i]) % mod;
            return ans;
        }
    }
}


Measured memory_bytes: 53660
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tupiii;
typedef tuple<ll, ll, ll> tuplll;

const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const int MOD = 1000000007;

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; }
inline void swap(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
inline void swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }


typedef pair<ll, int> P;

int n, m;
vector<vector<P>> g;
vll d; // init INF!!
ll INF;
vector<bool> negative;


void init()
{
	cin >> n >> m;

	g.resize(n);
	d.resize(n);

	INF = 200000000000000;

	REP(i, m)
	{
		int a, b; ll c;
		cin >> a >> b >> c;
		--a; --b;
		g[a].emplace_back(MP(-c, b));
	}
}

bool Bellman_Ford(int src)
{
	REP(i, n)
		d[i] = INF;
	d[src] = 0LL;

	REP(i, n - 1)
		REP(v, n)
		REP(i, SZ(g[v]))
	{
		int adj = g[v][i].second;
		ll c = g[v][i].first;
		chmin(d[adj], d[v] + c);
	}

	REP(v, n)
		REP(i, SZ(g[v]))
	{
		if (d[g[v][i].second] > d[v] + g[v][i].first)
			return true;
	}

	return false;
}

void check()
{
	negative.resize(n, false);

	REP(i, n)
		REP(v, SZ(g))
		REP(i, SZ(g[v]))
	{
		int adj = g[v][i].second;
		ll c = g[v][i].first;
		if (chmin(d[adj], d[v] + c))
			negative[adj] = true;

		if (negative[v])
			negative[adj] = true;
	}

}

int main()
{
	init();

	Bellman_Ford(0);
	check();
	
	if (negative[n - 1])
	{
		cout << "inf" << endl;
		return 0;
	}

	cout << -d[n - 1] << endl;

}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define pb  push_back
using namespace std;
typedef long long ll;
int ans[200005];
int main(){
    int n; cin >> n;
    int a[n];
    for(int i=0;i<n;i++) cin >> a[i];
    
    int l=0,r=n-1;
    bool f = 1;
    
    for(int i=n-1;i>-1;i--){
    	if(!f) ans[r] = a[i],r--;
    	else ans[l] = a[i],l++;
    	f^=1;
	}
	
	for(int i=0;i<n;i++) cout << ans[i] <<" ";
	
	return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
#include <stdio.h>
 
using namespace std;
 
#define int long long
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(i, a) for (auto &i: (a))
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()

void solve();

signed main () {
    cout.precision(10);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif
    int t = 1; 
    cin >> t;   
      if(t==0)
      cout<<"1"<<endl;
      else
      {
          cout<<"0"<<endl;
      }
      
    return 0;
}

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

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

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    
    if(abs(a - c) <= d or (abs(a - b) <= d and abs(b - c) <= d)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
s = list(input())

if s[-1] == "?":
    s[-1] = "D"
    
for n in range(len(s)-1):
    if s[n] == "?":
        if s[n-1]=="P" and n!=0:
            s[n] = "D"
        elif s[n+1]=="D" or s[n+1]=="?":
            s[n] = "P"
        else:
            s[n] = "D"
print("".join(s))

Measured memory_bytes: 10856
#include <stdio.h>

int main(void)
{
    long S;
    int h, m, s;

    scanf("%ld", &S);
    s = S % 60;
    m = S / 60 % 60;
    h = S / 60 / 60;
    printf("%d:%d:%d\n", h, m, s);
    return 0;
}

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

int main() {
	  string s;
      cin>>s;
      
     if(s[0]==s[1]&&s[1]==s[2])
     {
         cout<<s;
         return 0;
     }
     if(s[0]>=s[1]&&s[0]>=s[2])
     {
         cout<<s[0]<<s[0]<<s[0];
         return 0;
     }
    
    cout<<(s[0]-'0')+1<<(s[0]-'0')+1<<(s[0]-'0')+1;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[3];
int main()
{
    int x;
    while(~scanf("%d",&x))
    {
        a[0]=x;
        for(int i=1;i<3;i++)
        scanf("%d",&a[i]);
        int d,b,c;
        d=a[0]+a[1];
        b=a[1]+a[2];
        c=a[0]+a[2];
        int temp;
        if(d<b)
        {
            temp=b;
            b=d;
            d=temp;
        }
        if(b>c)
        {
            temp=b;
            b=c;
            c=temp;
        }
        printf("%d\n",b);
    }




    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

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

ll gcd(ll a, ll b) {return (!b ? a : gcd(b, a % b));}
ll lcm(ll a, ll b) {return ((a*b)/gcd(a,b));}
bool cmp(int a,int b){return a>b;}

const ll mod = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const ld pi = 3.141592653589793;
const int N = 1e6 + 10;

long long modpow(long long n, long long k, long long mod)
{
if (k == 0) return 1;
long long r = modpow(n * n % mod, k >> 1, mod);
if (k & 1) r = r * n % mod;
return r;
}

void solve(){
    int n;cin >> n;
    vector<int>a(n);
    for(int i = 0;i<n;i++) cin >> a[i];
    sort(a.begin(),a.end());
    int cnt = 0;
    for(int i = 0;i<n-2;i++){
        for(int j = i+1;j<n-1;j++){
            for(int k = j+1;k<n;k++){
                if(a[i]==a[j]||a[j]==a[k]) continue;
                if(a[i]+a[j]>a[k]) cnt++;
            }
        }
    }
    cout << cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 3648
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let a: usize = itr.next().unwrap().parse().unwrap();
    let b: usize = itr.next().unwrap().parse().unwrap();
    println!("{}", (a + b) % 24);
}


Measured memory_bytes: 2128
// {{{
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
// }}}

using ll = long long;

int N, K, X[101010],Y[101010];
char C[101010];

int bb[2020][2020], ww[2020][2020];

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

int main() {
    cin >> N >> K;
    for (int j = 0; j < N; ++j) {
        cin >> X[j] >> Y[j] >> C[j];
        X[j] %= 2*K;
        Y[j] %= 2*K;
        X[j]++; Y[j]++;
    }

    for (int j = 0; j <= 2*K; ++j) fill(bb[j], bb[j]+2*K+2, 0);
    for (int j = 0; j <= 2*K; ++j) fill(ww[j], ww[j]+2*K+2, 0);

    for (int j = 0; j < N; ++j) {
        (C[j] == 'B' ? bb : ww)[X[j]][Y[j]]++;
    }

    for (int j = 1; j <= 2*K; ++j) {
        for (int k = 1; k <= 2*K; ++k) {
            bb[j][k] += bb[j-1][k] + bb[j][k-1] - bb[j-1][k-1];
            ww[j][k] += ww[j-1][k] + ww[j][k-1] - ww[j-1][k-1];
        }
    }


    int ans = 0;
    for (int j = 0; j <= 2*K; ++j) {
        for (int k = 0; k <= 2*K; ++k) {
            int v = 0;
            for (int dx = -2; dx <= 2; ++dx) {
                for (int dy = -2; dy <= 2; ++dy) {
                    int xl = min(2*K, max(0, j + dx * K));
                    int xr = min(2*K, max(0, j + dx * K + K));
                    int yl = min(2*K, max(0, k + dy * K));
                    int yr = min(2*K, max(0, k + dy * K + K));

                    if ((abs(dx)+abs(dy)) % 2 == 0) {
                        v += bb[xr][yr] - bb[xl][yr] - bb[xr][yl] + bb[xl][yl];
                    } else {
                        v += ww[xr][yr] - ww[xl][yr] - ww[xr][yl] + ww[xl][yl];
                    }
                }
            }

            ans = max(ans, v);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 33152
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using VI = vector<int>;
#define REP(i, n) for (int i = 0; i < (n); ++i)

int main() {
  int n; cin >> n;
  VI d(n);
  REP(i, n) cin >> d[i];
  sort(d.begin(), d.end());
  int ans = 0;
  REP(i, n) {
    if (not i or d[i] != d[i - 1]) ans++;
  }
  cout << ans << endl;
  return 0;
}

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

int count[42];

int main() {
  int c = getchar();
  int n = 0;
  while (c <= 32) c = getchar();
  while (c > 32) {
    count[c - 'a']++;
    ++n;
    c = getchar();
  }
  long long bad = 0;
  for (int i = 0; i < 26; i++) {
    bad += (long long) count[i] * (count[i] + 1) / 2;
  }
  printf("%lld\n", (long long) n * (n + 1) / 2 - bad + 1);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int MAX = 1000000;
const int MOD = 1e9+7;
long long fac[MAX], finv[MAX], inv[MAX];
#define ll long long int

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    int a,b; cin >> a >> b;
  COMinit();
    for(int i=1; i<=b;i++){
    cout << (COM(a-b+1,i)*COM(b-1,i-1))%MOD << endl;
    }
}

Measured memory_bytes: 23680
import math
 
x, y ,angle = 0, 0, 90
while True:
  line = map(int, raw_input().split(','))
  if line[0] == 0 and line[1] == 0: break
  radian = math.radians(angle)
  x += math.cos(radian) * line[0]
  y += math.sin(radian) * line[0]
  angle -= line[1]
 
print(int(x))
print(int(y))

Measured memory_bytes: 6720
import time
start = time.time()
import random
D = int(input())
*c, = map(int, input().split())
S = []
for _ in [None] * D:
    *s, = map(int, input().split())
    S += s,
INF = float("inf")

def Tread(D):
    return [int(input()) for i in [None] * D]

def check(T):
    M = 0
    MM = []
    last = [-1] * 26
    for d, t in enumerate(T):
        M += S[d][t] - sum((d - last[i]) * c[i] for i in range(26) if i != t)
        last[t] = d
        # MM += M,
    return M # MM

def 貪欲():
    M = 0
    T = []
    last = [-1] * 26
    for d in range(D):
        m = -INF
        for j in range(26):
            Q = S[d][j] - sum((d - last[i]) * c[i] for i in range(26) if i != j)
            if m < Q:
                t, m = j, Q
        T += t,
        last[t] = d
        M += m
        # print(M)
    return T, M

def 局所探索():
    T, M = 貪欲()
    # print(T, M)
    while time.time() - start < 1.9:
        d, q = random.randrange(D), random.randrange(26)
        Check = T[:]
        Check[d] = q
        C = check(Check)
        if C > M:
            M, T = C, Check
    for s in T:print(s + 1)
    # print(M)

def C():
    T = Tread(D)
    for i in range(int(input())):
        d, q = map(int, input().split())
        T[d - 1] = q - 1
        print(check(T))
局所探索()

Measured memory_bytes: 85436
import java.util.*;
import java.util.stream.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int a = scanner.nextInt(), b = scanner.nextInt(), c = scanner.nextInt();
        System.out.println(a == b && b == c ? a % 2 == 1 ? 0 : -1 : Math.min(Math.min(Integer.numberOfTrailingZeros(Math.abs(a - b)), Integer.numberOfTrailingZeros(Math.abs(b - c))), Integer.numberOfTrailingZeros(Math.abs(c - a))));
    }
}

Measured memory_bytes: 21716
/*
*/

#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd

#define eps 1e-11
#define M_PI 3.141592653589793
#define bsize 512

#define ldouble long double
using namespace std;

#define bs 1000000007
const int N = 501031;

string A,B;

int to_left[N],to_right[N];
int cnt;
int n;
vector<int> exactly_this[N];

int solver()
{
	// local
	int ans=1e9;

	n=A.size();
	for (int i=0;i<A.size();i++)
	{
		for (int j=i;;j++)
		{
			if (B[j%n]=='1')
			{
				to_right[i]=j-i;
				break;
			}
		}
		int cnt=0;
		for (int j=i;;--j)
		{
			int q=j;
			while (q<0)
				q+=n;
			if (B[q]=='1')
			{
				to_left[i]=cnt;
				break;
			}
			++cnt;
		}
	}

	for (int r_shift=0;r_shift<n;r_shift++)
	{
		int cnt_dif=0;
		vector<int> dif;
		for (int i=0;i<n;i++)
		{
			exactly_this[i].clear();
		}

		int max_left=0;

		for (int i=0;i<A.size();i++)
		{
			if (A[i]!=B[(i+r_shift)%n])
			{
				dif.push_back(i);
				exactly_this[to_right[i]].push_back(i);
				cnt_dif++;
			}
		}

		for (int i=n-1;i>=r_shift;--i)
		{
			// L R
			ans=min(ans,cnt_dif+max_left*2+i+(i-r_shift));
			// R L - no need

			for (int j=0;j<exactly_this[i].size();j++)
			{
				int ps=exactly_this[i][j];
				max_left=max(max_left,to_left[ps]);
			}
		}
	}

	return ans;
}

int main(){
	//freopen("tree.in","r",stdin);
	//freopen("tree.out","w",stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	//cin.tie(0);

	cin>>A;
	cin>>B;
	int z=1;
	for (int i=0;i<B.size();i++)
	{
		if (B[i]=='1')
			z=0;
	}

	if (z==1)
	{
		int ok=1;
		for (int i=0;i<A.size();i++)
		{
			if (A[i]!='0')
				ok=0;
		}
		if (ok)
			cout<<0<<endl;
		else
			cout<<-1<<endl;
		return 0;
	}

	// nonzero B
	int ans=solver();
	reverse(A.begin(),A.end());
	reverse(B.begin(),B.end());
	ans=min(ans,solver());
	cout<<ans<<endl;

	cin.get(); cin.get();
	return 0;
}


Measured memory_bytes: 14720
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

// https://emtubasa.hateblo.jp/entry/2019/03/18/172356

int main() {
    int N, M;
    cin >> N;
    set<tuple<int,int,bool>> RB;
    rep(i, 2 * N) {
        int x, y;
        cin >> x >> y;
        RB.insert(make_tuple(x,y,i<N));
    }

/*
    for (auto x : R) {
        printf("%d,%d\n", x.first, x.second);
    }
    cout << endl;
    for (auto x : B) {
        printf("%d,%d\n", x.first, x.second);
    }
*/

   int res = 0;
   set<pair<int,int>> R;
   for (auto a : RB) { 
       if (get<2>(a)) {
           R.insert({get<1>(a),get<0>(a)}); // Push <y,x>
           continue;
       } else {
           for (auto r = R.rbegin(); r != R.rend(); r++) {
               if (get<1>(a) > r->first) {
                   //printf("HIT: (%d,%d)-(%d,%d)\n", get<0>(a), get<1>(a), r->second, r->first);
                   res++;
                   R.erase(*r);
                   break;
               }
           }
       }
   }
   cout << res << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e6+5;
int a[maxn],b[maxn];
void down(int all,int times)
{
    if(times==0)
    {
        for(int i=1;i<all;i++)
            a[i]=abs(a[i]-a[i+1]);
        return;
    }
    int val=(1<<times);
    int one=0;
    for(int i=0;i<=val;i++)
        one+=(a[i]==1);
    for(int i=1;i+val<=all;i++)
    {
        int x=a[i],z=a[i+val];
        one-=(a[i-1]==1);
        one+=(a[i+val]==1);
        if(abs(x-z)!=2) b[i]=abs(x-z);
        else b[i]=(one?0:2);
    }
    for(int i=1;i<=all-val;i++)
        a[i]=b[i];
    return;
}
int main()
{
    int n;
    scanf("%d",&n);
    char c;
    scanf("%c",&c);
    for(int i=1;i<=n;i++)
    {
        scanf("%c",&c);
        a[i]=c-'0';
    }
    for(int i=1;i<=n-1;i++)
        a[i]=abs(a[i]-a[i+1]);
    n--;
    int tot=n,times=n-1;
    for(int lg=0;lg<=log2(times);lg++)
        if(times&(1<<lg))
        {
            down(tot,lg);
            tot-=(1<<lg);
        }
    int ans=a[1];
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 8192