akhauriyash/Code-Regression huggingface dataset:
Sd = input()
T = input()


# S'よりTが大きかったら無理
if len(Sd) < len(T):
    print("UNRESTORABLE")
    exit()

head_list = []
# 部分文字列の頭のindex
for i in range(len(Sd) - len(T) + 1):
    sdd = Sd[i:i + len(T)]
    f = True
    for j, sddj in enumerate(sdd):
        if sddj == "?":
            continue
        elif sddj != T[j]:
            f = False
            break
    if f:
        head_list.append(i)

# 候補が見つからなかったら無理
if not head_list:
    print("UNRESTORABLE")
    exit()
else:
    ans_list = []
    for head in head_list:
        ans_list.append((Sd[:head] + T + Sd[head + len(T):]).replace("?", "a"))

    ans_list.sort()
    print(ans_list[0])


Measured memory_bytes: 9140
N = int(input())
if N == 1:
    print(0)
    exit()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

K = factorization(N)
cnt = 0
for k in K:
    x = k[1]
    i = 1
    while True:
        if i * (i - 1) // 2 <= x < i * (i + 1) // 2:

            cnt += i-1
            break
        i += 1
print(cnt)

Measured memory_bytes: 9496
from collections import *
from math import *
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
b = [0 for i in range(n+1)]
cnt = 0
for i in range(k):
	b = [0 for i in range(n+1)]
	for i in range(n):
		ub = min(n,i+a[i]+1)
		lb = max(0,i-a[i])
		b[lb] += 1
		b[ub] -= 1
	for i in range(1,n):
		b[i] += b[i-1]
	a = b[::]
	a.pop()
	if(sum(a) == n*n):
		break
print(*a)

Measured memory_bytes: 172888
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr);
#endif
#define ff first
#define ss second
#define endl '\n'
#define all(c) c.begin(),c.end()
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" "; cout<<endl;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve(){
  int a,b,x;
  cin>>a>>b>>x;
  cout<<(a>x or a+b<x?"NO":"YES")<<endl;	
}
int32_t main(){
  IOS;
  solve();
  //debug();
 #ifdef LOCAL_DEFINE
 cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
 #endif	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){

    long long int a,b,i,count = 0;

    cin >> a >> b;

    for(i = a; i <= b; i++) {
        if (i < 0) {
            count++;
        } else if (i == 0) {
            cout << "Zero" << endl;
            return 0;
        }
    }
        if (count % 2 == 0) {
            cout << "Positive" << endl;
        } else {
            cout << "Negative" << endl;
        }
        return 0;
    }


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

int main()
{
	int n,b,t,maxNO,i;
	double y,r,money,max;

	scanf("%d",&n);
	while(n != 0){
		max = 0;

		scanf("%lf",&y);
		for(i = 0; i < n; i++){
			scanf("%d%lf%d",&b,&r,&t);
			if(t == 1){
				money = 1.0 + y * (r/100);
				//printf("%lf\n",money);
			}
			else{
				money = pow((1.0 + r/100.0),y);
				//printf("%lf\n",money);
			}
			if(money > max){
				max = money;
				maxNO = b;
			}
		}

		printf("%d\n",maxNO);

		scanf("%d",&n);
	}

	return 0;
}

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

int sum_keta(int n){
  int ans = 0;
  while(n > 0){
    ans += n % 10;
    n /= 10;
  }
  return ans;
}

signed main(){
  int n, a, b;
  cin >> n >> a >> b;
  int ans = 0;
  for(int i = 1; i <= n; i++){
    if(sum_keta(i) >= a && sum_keta(i) <= b) ans += i;
  }
  cout << ans << endl;
}

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


def main():
    K = int(input())
    
    if K%2==0:
        print(-1)
        return
    
    if K % 7:
        L = 9*K
    else:
        L = 9*K//7
    a = 1
    for i in range(1,L+1):
        a = (a * 10) % L
        if a == 1:
            print(i)
            return
    print(-1)
main()

Measured memory_bytes: 9196
import math

class Vector(object):
    def __init__(self, arr):
        self.arr = arr

    def sub(self, vec):
        return Vector([self.arr[i] - vec.arr[i] for i in range(len(self.arr))])
    
    def p_norm(self, p):
        return sum([abs(e) ** p for e in self.arr]) ** (1 / p)
    
    def inf_norm(self):
        return max([abs(e) for e in self.arr])


n = int(input())
x = Vector([int(e) for e in input().split()])
y = Vector([int(e) for e in input().split()])
z = x.sub(y)

print(z.p_norm(1))
print(z.p_norm(2))
print(z.p_norm(3))
print(z.inf_norm())



Measured memory_bytes: 5704
#include<iostream>
#include<math.h>
#include <string>
#include <stack>
#include<stdio.h>
#include <queue> 
#include <functional>
#define rep(i,n) for ( i=0; i < n; i++)

int i,j,k,l,num;

using namespace std;

int maisuu(){
	
	int atf,c=0;
	
	atf = 500*l + 100*k + 50*j + 10*i - num;
	
	if(atf < 0 ) return 100;
	
	
	while( atf >= 500) {
		atf = atf - 500;
		 c++;
	}
	while( atf >= 100) {
		atf = atf - 100;
		 c++;
	}
	while( atf >= 50) {
		atf = atf - 50;
		 c++;
	}
	while( atf >= 10) {
		atf = atf - 10;
		 c++;
	}
	
	
	return c;
}



int main(){
	
	stack<int> st; // スタックを宣言＋初期化
	
	int a,b,c,d,e=0,sum,min;
	int a1=0,b1=0,c1=0,d1=0;
	int arr[100];
	int arr2[100][100];
	int arr4[20][20][20][20];
	char crr[100];
	char crr2[100][100];
	string str;
	stack<int> istk; // 整数値を格納するスタックを宣言
    stack<string> sstk; // 文字列を格納するスタックを宣言	
	queue<int> ique; // 整数値を格納するキューを宣言
    queue<string> sque; // 文字列を格納するキューを宣言

	while (1){
		
		
		min =100 ;
		i =0 ;
		j=0;
		k=0;
		l=0;
		
	
	cin >> num; 
	
	if(num == 0) break;
	
	if(e!=0) cout << endl;
		e++;
	
	
	cin >> a >> b >> c >>d;
	
	rep(i,a+1){
		rep(j,b+1){
			rep(k,c+1){
				rep(l,d+1){
					
					
					sum = maisuu();
					
	//				cout << min << endl;
					
					sum = a+b+c+d-i-j-k-l+sum;
					
					if(sum < min) {
						a1 = i;
						b1 = j;
						c1 = k;
						d1 = l;
						min = sum;
					}
						
						 
				}
			}
		}
	}
	
	if(a1>0) cout << "10 " << a1 <<endl;
	if(b1>0) cout << "50 " << b1 <<endl;
	if(c1>0) cout << "100 " << c1 <<endl;
	if(d1>0) cout << "500 " << d1 <<endl;
	
	
	}
	
	
		
	return 0;
		
}


	

Measured memory_bytes: 908
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n;
    ll z = 0;
    pii a[200005] = {}, b[200005] = {};
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
    for (int i = 1; i <= n; i++) if (a[i].first > a[i].second) swap(a[i].first, a[i].second);
    for (int i = 1; i <= n; i++) b[i].first = a[i].second, b[i].second = a[i].first;
    sort(a + 1, a + n + 1); sort(b + 1, b + n + 1);
    z = 1ll * (a[n].first - a[1].first) * (b[n].first - b[1].first);
    if (a[1].second == b[n].first && a[1].second != b[n - 1].first) {
        cout << z << '\n';
        return 0;
    }
    int x = 0;
    for (int i = 1; i <= n; i++) {
        if (b[i].second >= b[1].first) x = max(x, b[i].second);
        else x = max(x, b[i].first);
    }
    z = min(z, 1ll * (b[n].first - a[1].first) * (x - b[1].first));
    int c = a[1].second, d = a[1].second;
    for (int i = 2; i <= n; i++) {
        if (c >= a[i].first) {
            z = min(z, 1ll * (b[n].first - a[1].first) * (max(d, a[n].first) - a[i].first));
        }
        c = min(c, a[i].second);
        d = max(d, a[i].second);
    }
    cout << z << '\n';
}


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

int main()
{
	int a,b,c;
	cin >> a >> b >> c;
	cout << ((b-a == c-b) ? "YES" : "NO") << endl;
	return 0;
}

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

int main(){
    string S, T;
	long long int res = 0;

	cin >> S;
	cin >> T;

	rep(i, S.size()){
		if(S[i] != T[i]){
			res++;
		}
	}
	
	cout << res;
 
	return 0;
}

Measured memory_bytes: 3912
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
constexpr int kMod = 1000000007;
typedef long long LL;

int main() {
  int sx, sy, tx, ty; std::cin >> sx >> sy >> tx >> ty;

  char xp = (sx < tx) ? 'R' : 'L';
  char xn = (sx < tx) ? 'L' : 'R';
  char yp = (sy < ty) ? 'U' : 'D';
  char yn = (sy < ty) ? 'D' : 'U';

  // Step1
  for (int i = 0; i < std::abs(sy - ty); ++i) {
    std::cout << yp;
  }
  for (int i = 0; i < std::abs(sx - tx); ++i) {
    std::cout << xp;
  }
  // Back step1
  for (int i = 0; i < std::abs(sy - ty); ++i) {
    std::cout << yn;
  }
  for (int i = 0; i < std::abs(sx - tx); ++i) {
    std::cout << xn;
  }
  // Step2
  std::cout << xn;
  for (int i = 0; i <= std::abs(sy - ty); ++i) {
    std::cout << yp;
  }
  for (int i = 0; i <= std::abs(sx - tx); ++i) {
    std::cout << xp;
  }
  // Back step2
  std::cout << yn << xp;
  for (int i = 0; i <= std::abs(sy - ty); ++i) {
    std::cout << yn;
  }
  for (int i = 0; i <= std::abs(sx - tx); ++i) {
    std::cout << xn;
  }
  std::cout << yp << std::endl;
}


Measured memory_bytes: 256
n, x = map(int, input().split())
A = [int(i) for i in input().split()]
D = []

for i in range(n):
    dist = abs(x - A[i])
    D.append(dist)
    
def gcd(x, y):
    while y != 0:
        x, y = y, x%y
    return x

for i in range(n - 1):
    D[i + 1] = gcd(D[i], D[i + 1])
    
print(D[-1])

Measured memory_bytes: 14252
func readInt() -> Int {
    return Int(readLine()!)!
}

func readTwoInts(separator: String.Element = " ") -> (a: Int, b: Int) {
    let ints = readLine()!.split(separator: separator).map { Int($0)! }
    return (a: ints[0], b: ints[1])
}

func readInts(separator: String.Element = " ") -> [Int] {
    return readLine()!.split(separator: separator).map { Int($0)! }
}

// 普通にやるとTLE
// どの要素がどれだけあるかを持っておいて、差分更新をする
func mainD() {
    let N = readInt()
    var numbers = readInts()
    let Q = readInt()
    let pairs = (0..<Q).map { _ in readTwoInts() }

    var counts: [Int] = .init(repeating: 0, count: 1_000_00 + 1)

    for number in numbers {
        counts[number] += 1
    }

    var sum = 0
    for pair in pairs {
        let changed = counts[pair.a]
        counts[pair.b] += counts[pair.a]
        counts[pair.a] = 0

        if sum == 0 {
            sum = counts.enumerated().reduce(0) { $0 + ($1.offset * $1.element) }
            print(sum)
        } else {
            sum += (pair.b - pair.a) * changed
            print(sum)
        }
    }

//    var sums: [Int] = .init(repeating: 0, count: Q)
//    var index = 0
//    for pair in pairs {
//        numbers = numbers.map { number in
//            let newNumber = number == pair.a ? pair.b : number
//            sums[index] += newNumber
//            return newNumber
//        }
//
//        index += 1
//    }
//
//    for sum in sums {
//        print(sum)
//    }
}
mainD()


Measured memory_bytes: 12672
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		int num = 105;
		
		if(n < 105) {
			System.out.println(0);
		} else {
			int ans = 0;
			int count = 0;
			for(int i=num; i<=n; i+=2) {
				for(int j=1; j<=i; j++) {
					if(i%j == 0) {
						count++;
					}
				}
				if(count == 8) {
					ans++;
				}
				count = 0;
			}
			System.out.println(ans);
		}
	}

}

Measured memory_bytes: 23892
#include<iostream>

using namespace std;

int main(){
  int a[4],b[4];
  int hit,blow;
  while(cin>>a[0]>>a[1]>>a[2]>>a[3]>>b[0]>>b[1]>>b[2]>>b[3]){
    hit=0;
    blow=0;
    for(int i=0;i<4;i++){
      if(a[i]==b[i]){
	hit++;
      }
    }
    for(int i=0;i<4;i++){
      for(int j=0;j<4;j++){
	if(b[i]==a[j]){
	  blow++;
	}
      }
    }
    blow-=hit;
    cout<<hit<<" "<<blow<<"\n";
  }
  return 0;
}

Measured memory_bytes: 0
#include "iostream"

using namespace std;

int main() {

	int N = 0;
	int K = 0;

	int i;
	int sum = 1;

	cin >> N >> K;

	for (i = 1; i < K; i++) {
		sum = sum + 2;
	}

	if (sum <= N) {
		cout << "YES";
	}
	else {
		cout << "NO";
	}

	return 0;
}

Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception {
        solve(System.in, System.out);
    }

    static void solve(InputStream is, PrintStream os) {
        // Your code here!
        Scanner scan = new Scanner(is);
        int N = scan.nextInt();
        int M = scan.nextInt();
        int allPattern = (int)Math.pow(2.0, N);
        long dp[] = new long[allPattern];
        Arrays.fill(dp, 0);

        Map<Integer, Integer> acMap = new TreeMap<Integer, Integer>();

        for(int i = 0 ; i < M; i++) {

            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = 0;
            for(int j = 0; j < b ; j++) {
                c += Math.pow(2.0, scan.nextInt()-1);
            }
            if (!acMap.containsKey(c))
                acMap.put(c, a);
            else {
                Integer prevA = (Integer)acMap.get(c);
                if (a < prevA)
                    acMap.put(c, a);
            }
        }


        for (int s = 0 ; s < allPattern; s++) {
            for (Entry<Integer, Integer> entry : acMap.entrySet()) {
                int t = s | entry.getKey();
                if(dp[s] != 0 || s == 0) {
                    if (dp[t] == 0 || (dp[t] != 0 && dp[t] > dp[s] + entry.getValue()))
                        dp[t] = dp[s] + entry.getValue();
                }
            }
        }

        if(dp[allPattern-1] != 0)
            os.println(dp[allPattern-1]);
        else
            os.println("-1");
    }
}

Measured memory_bytes: 31464
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int inf = 1001001001;
int n,m,c,d;
vector<int> a(2000);
vector<int> b(2000);
int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> a[i] >> c;
        for(int j = 1; j <= c; j++){
            cin >> d;
            b[i] += (1 << (d - 1));
        }
    }
vector<int> dp(10000,inf);
dp[0] = 0;
    for(int i = 0; i < (1 << n); i++){
        for(int j = 1; j <= m; j++){
            dp[i | b[j]] = min(dp[i | b[j]], dp[i] + a[j]);
        }
    }
    int ans;
    if(dp[(1 << n) - 1] == inf) {ans = -1;}
    else {
        ans = dp[(1 << n) - 1];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <functional>
#include <map>
#include <set>
#define Rep(i, n) for(int i=0;i<n;++i)
#define rep(i, n) for(int i=1;i<=n;++i)
#define ll long long
#define INF 10e9

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

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;
}

int N;

int main () {
  cin >> N;

  ll int ans = 0;

  rep(i, N-1) {
    ans += i;
  }

  printf("%lld", ans);
}

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

int main(){
  string sa,sb,sc;
  cin>>sa>>sb>>sc;

  int i=0;
  int j=-1;
  int k=-1;
  int na=sa.size(),nb=sb.size(),nc=sc.size();
  char ans = 'A';
  string cur = sa;
  int cnt = i;

  while(i<na&&j<nb&&k<nc){
    if(cur[cnt]=='a'){
      i++;
      ans='A';
      cur=sa;
      cnt = i;
    }else if(cur[cnt]=='b'){
      j++;
      ans='B';
      cur=sb;
      cnt=j;
    }else{
      k++;
      ans='C';
      cur=sc;
      cnt=k;
    }
  }

  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int main() {
  ll n;
  cin >> n;
  vec h(n);
  for(ll i=0;i<n;i++) cin >> h[i];
  for(ll i=n-1;i;i--) {
    if(h[i]<h[i-1]) h[i-1]--;
  }
  ll f=1;
  for(ll i=0;i<n-1;i++) {
    if(h[i]>h[i+1]) f=0;
  }
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 1024
class Integer
  def divisor
    res = []
    1.upto((self**0.5)) do |i|
      if self % i == 0
        res.push i
        res.push self / i if i != self / i
      end
    end
    res.sort
  end
end

def answer_if_valid(x, a, d)
  b = a - d
  if x == a ** 5 - b ** 5
    puts "#{a} #{b}"
    exit
  end
end

x = gets.to_s.to_i

r = x % 5

x.divisor.select{|t| r == t % 5}.each do |d|
  
  left = (( x / d - d ** 4 ) / 5).abs
  
  if left == 0
    answer_if_valid(x,0,d)
    (d ** 3).divisor.each do |a|
      answer_if_valid(x, a, d)
    end
  end
  
  left.divisor.each do |a|
    answer_if_valid(x,  a, d)
    answer_if_valid(x, -a, d)
  end
end

Measured memory_bytes: 14688
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define RFOR(i, start, end) for (int i = start; end <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1000000007
using ll = long long;
using namespace std;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

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

    int N, M;
    cin >> N >> M;
    vector<vector<ll>> x(N, vector<ll>(3));
    REP(i, N) cin >> x[i][0] >> x[i][1] >> x[i][2];

    ll ans = 0;
    REP(bit, (1 << 3)) {
        vector<ll> sum(N);
        REP(i, 3) {
            if (bit & (1 << i)) {
                REP(ii, N) { sum[ii] += x[ii][i]; }
            } else {
                REP(ii, N) { sum[ii] -= x[ii][i]; }
            }
        }
        RSORT(sum);
        ll mx = 0;
        REP(i, M) mx += sum[i];
        chmax(ans, mx);
    }

    std::cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 384
from collections import deque
import time

start = time.time() # なにこれ

n = int(input())
target_num = n*(n-1)//2

all_set = set()
a = [deque(list(map(int, input().split()))) for i in range(n)]
ans = 0

while True:
  cur_set = set()
  flag = False
  for i in range(n):
    if len(a[i]):
      tup = (min(i+1, a[i][0]), max(i+1, a[i][0]))
    else:
      continue
    if tup not in cur_set:
      cur_set.add(tup)
    elif tup in cur_set:
      all_set.add(tup)
      t1, t2 = tup
      a[t1-1].popleft()
      a[t2-1].popleft()
      flag = True
  ans += 1
  if len(all_set)==target_num:
    break
  if time.time()-start>1.8:
    print(1000*999//2)
    exit()
  if not flag:
    print(-1)
    exit()

print(ans)

Measured memory_bytes: 84252
#include<bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,ans=0;
  cin >> a>> b;
  if(a>b){
    ans += a;
    a--;
  }else{
    ans += b;
    b--;
  }
  ans += max(a,b);
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>  // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>     // bitset
#include <cctype>     // isupper, islower, isdigit, toupper, tolower
#include <cstdint>    // int64_t, int*_t
#include <cstdio>     // printf
#include <deque>      // deque
#include <iomanip>    // fixed, setprecision
#include <iostream>   // cout, endl, cin
#include <map>        // map
#include <queue>      // queue, priority_queue
#include <set>        // set
#include <stack>      // stack
#include <string>     // string, to_string, stoi
#include <tuple>      // tuple, make_tuple
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <utility>        // pair, make_pair
#include <vector>         // vector
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main() {
  ll N, K, k;
  double sumrate = 0, rate = 0;
  cin >> N >> K;
  for (ll i = 1; i <= N; i++) {
    rate = 1;
    k = i;
    while (k < K) {
      rate /= 2;
      k *= 2;
    }
    sumrate += rate;
  }
  cout << fixed << setprecision(10) << sumrate / N << endl;
}


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

int main(void){
	int a[101],max=0,mod=0,x,i;
	for(i=0;i<101;i++)a[i]=0;
	while(scanf("%d",&x)!=EOF){
		if(x>max)max=x;
		a[x]++;
		if(a[x]>mod)mod=a[x];
	}

	for(i=0;i<=max;i++){
		if(a[i]==mod)printf("%d\n",i);
	}
	return 0;
}

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

int main()
{
	int N;
	cin >> N;
	ll sum = 0;
	ll sa = 1e16, sb = 1e16;
	bool ok = true;
	for (int i = 0; i < N; i++) {
		ll A, B;
		cin >> A >> B;
		sum += A;
		if (A != B) {
			ok = false;
		}
		if (A <= B) {
			sb += B - A;
		}
		else {
			sa = min(sa, B);
		}
	}
	if (ok) {
		cout << 0 << endl;
		return 0;
	}
	cout << sum - min(sa, sb) << endl;
	return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
int main(void){
int x, y, s;
	for(;;){scanf("%d %d", &x, &y);
		if(x == 0 && y == 0){
			break;
		}
		if(y<x){
			s=x;
			x=y;
			y=s;
		}
	printf("%d %d\n",x, y);
	}
return 0;
}


Measured memory_bytes: 1928
#include<iostream>
using namespace std;
int main(){
  int a,result;
  char op;
  cin >> a ;
  result=a;
  while(1){
    cin >> op;
     if(op=='='){
    break;}
   
    
    cin >> a;
  if(op=='+'){
    result+=a;}
  else if(op=='-'){
    result-=a;}
  else if(op=='*'){
    result*=a;}
  else if(op=='/'){
    result/=a;}
   
  }
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define print(v,r) f(i,0,r) cout<<v[i]<<" "; cout<<endl;
#define Get(x,y) scanf("%I64d%I64d",&x,&y);
#define is_bit(x,y) (x%(1<<(y+1))>=(1<<y))
#define eror(x) cout<<#x<<'='<<(x)<<endl;
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define Gett(x,y) scanf("%d%d",&x,&y);
#define f(i,a,b) for(int i=a;i<b;i++)
#define get(x) scanf("%I64d",&x);
#define All(x) x.begin(),x.end()
#define Add(x,y) x=(x+y)%mod;
#define gett(x) scanf("%d",&x);
#define maxm(a,b) a=max(a,b);
#define minm(a,b) a=min(a,b);
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=2002,mod=924844033;

int n,k,res,fac[N],dp[N][N][4],ans[N],pd[N];

void calc(int x){
	f(i,0,N) f(j,0,N) f(mask,0,4) dp[i][j][mask]=pd[i]=0;
	dp[0][0][0]=1;
	f(i,0,x+1)
	    f(j,0,i+1)
	       f(mask,0,4){
	           Add(dp[i+1][j][mask/2],dp[i][j][mask]);
	           if(mask%2==0 && i)
	               Add(dp[i+1][j+1][mask/2],dp[i][j][mask]);
	           Add(dp[i+1][j+1][mask/2+2],dp[i][j][mask]);
            }
    f(i,0,x+1){
    	f(mask,0,2)
    		Add(pd[i],dp[x][i][mask]);
    }
}
void add(int x){
	ans[0]=1;
	f_(i,n,0)
		f(j,1,min(i,x)+1)
			Add(ans[i],1ll*ans[i-j]*pd[j]%mod);
}
void solve(){
	fac[0]=1;
	f(i,1,N) fac[i]=1ll*fac[i-1]*i%mod;
	f(i,0,n+1){
		if(i&1) Add(res,mod-1ll*ans[i]*fac[n-i]%mod)
		else Add(res,1ll*ans[i]*fac[n-i]%mod);
	}
	cout<<res;
}

int main(){
	cin>>n>>k;
	calc((n+k-1)/k);
	f(i,0,n%k) 
	    add((n+k-1)/k);
	calc(n/k);
	f(i,0,k-(n%k))
	    add(n/k);
	solve();
}

Measured memory_bytes: 66260
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;

int main(){
    while(true){
	string s;
	char a[] = {'r','g','b'};
	set<string> u;
	queue< pair<string,int> > q;
	cin >> s;
	if(s == "0") break;
	u.insert(s);
	q.push( pair<string,int>(s,0));
	int ans = 0;
	while(!q.empty()){
	    s = q.front().first;
	    int v = q.front().second;
	    q.pop();
	    REP(i,s.size()-1){
		if(s[i] != s[i+1]){
		    string s1 = s;
		    char key;
		    REP(j,3){
			if(s[i] != a[j] && s[i+1] != a[j]){
			    key = a[j];
			}
		    }
		    s1[i] = key;
		    s1[i+1] = key;
		    if(u.find(s1) == u.end()){
			u.insert(s1);
			q.push(pair<string,int>(s1,v+1));
		    }
		}
	    }
	    bool flg = true;
	    REP(i,s.size()-1){
		if(s[i] != s[i+1] ) flg = false;
	    }
	    if(flg){
		cout << v << endl;
		break;
	    }else if(q.empty()){
		cout << "NA" << endl;
		break;
	    }
	}
    }
    return 0;
}

Measured memory_bytes: 2664
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#define rep(i, n) for(int i=0; i<n; i++)
#define rep_one(i, n) for(int i=1; i<n; i++)
using namespace std;
typedef long long ll;


int main(){ 
    int n; cin >> n;
    ll ans[10001]={};
    for(ll i=1; i*i<n; i++){
        for(ll j=1; j*j<n; j++){
            if(i*i+j*j+i*j > n) continue;
            for(ll k=1; k*k<n; k++){
                ll f = i*i+j*j+k*k+i*j+j*k+k*i;
                if(f < n+1) ans[f]++;
            }
        }
    }
    rep_one(i, n+1){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 3600
a, b, c, d = map(int, input().split())
    
if a == 0:
    if c >= 0:
        print(b * d)
    elif c < 0:
        if d >= 0:
            print(b * d)
        elif d < 0:
            print(0)
elif a > 0:
    if c >= 0:
        print(b * d)
    elif c < 0:
        if d >= 0:
            print(b * d)
        elif d < 0:
            print(a * d)
            
elif a < 0:
    if b >= 0:
        if c >= 0:
            print(b * d)
        elif c < 0:
            if d >= 0:
                if a * c > b * d:
                    print(a * c)
                else:
                    print(b * d)
            elif d < 0:
                print(a * c)
        
    elif b < 0:
        if c >= 0:
            print(b * c)
        elif c < 0:
            print(a * c)

Measured memory_bytes: 9176
def main():
    book_index = {}
    while True:
        try:
            word, page = input().split(' ')
            page = int(page)
            page_list = book_index.get(word)
            if page_list:
                page_list.append(page)
            else:
                book_index[word] = [page]
        except Exception:
            break

    for k in sorted(book_index.keys()):
        print(k)
        print(' '.join(map(str, (sorted(book_index.get(k))))))


if __name__ == '__main__':
    main()

Measured memory_bytes: 7624
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

fact = [1]
for i in range(1, N+10):
    fact.append(fact[-1] * i % MOD)
def rev(x):
    return pow(x, MOD-2, MOD)
def cmb(i, k):
    if(i < k): return 0
    return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

for i in range(1, K+1):
    if N-K+1<i:
        print(0)
    else:
        print((cmb(N-K+1, i) * cmb(K-1, i-1))%MOD)



Measured memory_bytes: 42992
n,m=map(int,input().split())
arr=[int(i) for i in input().split()]
hashmap=dict()
count=dict()
visited=dict()
for key in range(1,n+1):
  hashmap[key]=arr[key-1]

result=n
for i in range(m):
  a,b=map(int,input().split())
  if hashmap[a]<hashmap[b]:
    if visited.get(a)==None:
        result-=1
        visited[a]=1
  elif hashmap[b]<hashmap[a]:
    if visited.get(b)==None:
        result-=1
        visited[b]=1
  else:
      if visited.get(a)==None:
          result-=1
          visited[a]=1
      if visited.get(b)==None:
          result-=1          
          visited[b]=1
    
print(result)    

Measured memory_bytes: 27980
#include <iostream>
#include <numeric>

inline int gcd(int a, int b){
  if(b<a) std::swap(a, b);
  int r = a % b;
  if(r==0) return b;
  while(r!=0) r = a % b, a = b, b = r;
  return a;
}

inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	return x*f;
}

int cnt[1000001];

int main(){
  int n = read(), num = read(), g = num, ex = (n-1)/8;
  cnt[num] = 1;
  for(int i=0;i<ex;i++){
    num = read();
    g = gcd(g, num);
    cnt[num]++;
    num = read();
    g = gcd(g, num);
    cnt[num]++;
    num = read();
    g = gcd(g, num);
    cnt[num]++;
    num = read();
    g = gcd(g, num);
    cnt[num]++;
    num = read();
    g = gcd(g, num);
    cnt[num]++;
    num = read();
    g = gcd(g, num);
    cnt[num]++;
    num = read();
    g = gcd(g, num);
    cnt[num]++;
    num = read();
    g = gcd(g, num);
    cnt[num]++;
  }

  for(int i=0;i<(n-1)%8;i++){
    num = read();
    g = gcd(g, num);
    cnt[num]++;
  }

  if(n - cnt[1] > 80000){
    if(g==1) printf("setwise coprime\n");
    else printf("not coprime\n");
    return 0;
  }

  if(g!=1){
    printf("not coprime\n");
    return 0;
  }

  int use[1000001];
  int max_S = 0;
  for(int i=2;i<=1000000;i++){
    if(use[i]==-1) continue;
    int S = 0;
    for(int j=i;j<=1000000;j+=i) {
      S += cnt[j];
      use[j] = -1;
    }
    if(max_S<S) max_S = S;
  }
  if(max_S<2) printf("pairwise coprime\n");
  else printf("setwise coprime\n");
}


Measured memory_bytes: 11452
#include<bits/stdc++.h> 
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define fi first
#define se second
#define PB push_back
#define uint unsigned
#define ull unsigned ll 
using namespace std;
char s[200005];
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	int len=1,ans=1,p=1;
	for (;;){
		if (p==n) break;
		if (len==2)	ans++,p++,len=1;
		else if (s[p+1]!=s[p]) ans++,p++,len=1;
		else if (p==n-1) break;
		else ans++,p+=2,len=2;
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 384
{-# LANGUAGE BangPatterns, OverloadedStrings #-}

import Control.Monad
import Data.Array.Unboxed
import Data.Bits
import Data.Char
import Data.Coerce
import Data.Function
import Data.Int 
import Data.IORef
import Data.List
import Data.Maybe
import qualified Data.Map.Strict as M
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as MV
import qualified Data.ByteString.Char8 as BS

main :: IO ()
main = do
  n <- getInt
  let pats = ["AC", "WA", "TLE", "RE"]
  let m = M.fromList $ zip pats [0, 0..]
  ws <- replicateM n BS.getLine
  let m' = foldr (M.update (Just . (1+))) m ws
  forM_ pats $ \w -> do
    let n = m' M.! w
    BS.putStrLn (w `BS.append` " x " `BS.append` BS.pack (show n))

-- Input

getInt :: IO Int
getInt = readLn

second :: (b -> c) -> (a, b) -> (a, c)
second f (a, b) = (a, f b)

readInt :: BS.ByteString -> Maybe (Int, BS.ByteString)
readInt = fmap (second BS.tail) . BS.readInt

getIntVec :: Int -> IO (V.Vector Int)
getIntVec n = V.unfoldrN n readInt <$> BS.getLine

getIntList :: IO [Int]
getIntList = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

getIntegerList :: IO [Integer]
getIntegerList = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

getIntPair :: IO (Int, Int)
getIntPair = do
  v <- getIntVec 2
  return (v V.! 0, v V.! 1)

-- Search

bisearch :: (Int -> Bool) -> (Int, Int) -> (Int, Int)
bisearch check = bis
  where
    bis (l, r)
      | l + 1 == r = (l, r)
      | check mid  = bis (mid, r)
      | otherwise  = bis (l, mid)
      where
        mid = l + (r - l) `div` 2

-- Modular Arithmetic
--
 
modulo :: Int64
modulo = 10^9+7
addMod, subMod, mulMod :: Int64 -> Int64 -> Int64
addMod !x !y | x + y >= modulo = x + y - modulo
             | otherwise = x + y
subMod !x !y | x >= y = x - y
             | otherwise = x - y + modulo
mulMod !x !y = (x * y) `rem` modulo

newtype N = N { unwrapN :: Int64 } deriving (Eq)
instance Show N where
  show (N x) = show x
instance Num N where
  (+) = coerce addMod
  (-) = coerce subMod
  (*) = coerce mulMod
  fromInteger n = N (fromInteger (n `mod` fromIntegral modulo))
  abs = undefined; signum = undefined
---
 
exEuclid :: (Eq a, Integral a) => a -> a -> (a, a, a)
exEuclid !f !g = loop 1 0 0 1 f g
  where loop !u0 !u1 !v0 !v1 !f 0 = (f, u0, v0)
        loop !u0 !u1 !v0 !v1 !f g =
          case divMod f g of
            (q,r) -> loop u1 (u0 - q * u1) v1 (v0 - q * v1) g r
 
recipM :: Int64 -> Int64
recipM !x = case exEuclid x modulo of
             (1,a,_) -> a `mod` modulo
             (-1,a,_) -> (-a) `mod` modulo
divM :: Int64 -> Int64 -> Int64
divM !x !y = x `mulMod` recipM y
 
instance Fractional N where
  (/) = coerce divM
  recip = coerce recipM
  fromRational = undefined

Measured memory_bytes: 22388
#include <iostream>
#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昇順

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

Measured memory_bytes: 256
N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7

S=[[1]*N]
KDIG=[0]*70

for i in range(1,61):
    if K%(1<<i):
        KDIG[i-1]=1
        K-=K%(1<<i)

def prod(A,B,k,l,m):#A:k*l,B:l*m

    C=[[None for i in range(m)] for j in range(k)]

    for i in range(k):
        for j in range(m):
            ANS=0
            for pl in range(l):
                ANS=(ANS+A[i][pl]*B[pl][j])%mod

            C[i][j]=ANS

    return C

for i in range(60):
    if KDIG[i]==1:
        S=prod(S,A,1,N,N)
    
    A=prod(A,A,N,N,N)

print(sum(S[0])%mod)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,l;
  cin>>n>>l;
  string s[n];
  string list="";
  for(int i=0;i<n;i++){
    cin>>s[i];
  }
  sort(s,s+n);
  for(int i=0;i<n;i++){
    list.append(s[i]);
  }
  cout<<list<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstdio>
#define N 5100
#define M 230
using namespace std;
typedef long long ll;

int n, m, stk[N], top, L[N], R[N];
ll d[N], a[N][M], sum[N][N];

int main() {
    cin >> n >> m;
    for (int i = 2; i <= n; ++i)
        scanf("%lld", d + i), d[i] += d[i - 1];

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%lld", a[i] + j);

    for (int j = 1; j <= m; ++j) {
        stk[top = 1] = 0, a[0][j] = 2e9;
        for (int i = 1; i <= n; ++i) {
            while (top && a[stk[top]][j] < a[i][j]) --top;
            L[i] = stk[top], stk[++top] = i;
        }
        stk[top = 1] = n + 1, a[n + 1][j] = 2e9;
        for (int i = n; i >= 1; --i) {
            while (top && a[stk[top]][j] < a[i][j]) --top;
            R[i] = stk[top], stk[++top] = i;
        }
        for (int i = 1; i <= n; ++i) {
            //cout << j << "  #  " << i << " " << L[i] << " " << R[i] << endl;
            sum[L[i] + 1][i] += a[i][j];
            sum[L[i] + 1][R[i]] -= a[i][j];
            sum[i + 1][i] -= a[i][j];
            sum[i + 1][R[i]] += a[i][j];
        }
    }

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
            ans = max(ans, sum[i][j] - d[j] + d[i]);

    cout << ans << endl;

    return 0;
}


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

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int a[1 << 20];
int cmp(int x, int y)
{
	return a[x] < a[y];
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int n;cin >> n;
	
	FOR(i, 0, n) cin >> a[i];
	VI p(n);
	iota(ALL(p), 0);
	sort(ALL(p), cmp);
	for(auto i: p) cout << i + 1 << ' ';
	
	cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
}



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

using ll=long long;
using vll=vector<ll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;

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

    int n;
    cin >> n;
    int g = 0;
    vi xs(n);
    for(auto& xi: xs) {
        cin >> xi;
        g = __gcd(g, xi);
    }
    cout << g << "\n";
}


Measured memory_bytes: 640
#include<math.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 100009;
long long n, A, B, h[maxn];
long long l = 0, r = 9e18, mid;

bool check(long long x)
{
    long long res = 0;
    for (long long i=1; i<=n; i++)
        if (h[i] > B*x)
            res+= (int)ceil(h[i]-B*x+A-B-1)/(A-B);
    return res <= x;
}
int main()
{
    scanf("%lld%lld%lld", &n, &A, &B);
    for (long long i=1; i<=n; i++) scanf("%lld", &h[i]);
    while (l < r)
    {
        mid = (l+r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%lld\n", l);
    return 0;
}



Measured memory_bytes: 896
#include<stdio.h>

#define N 500000
#define INF 1000000000

int c;

void merge( int *, int , int , int );
void mergeSort( int *, int , int );

int main(){

  int n, i, arr[N];

  scanf("%d", &n);

  for( i = 0; i < n; i++){
    scanf("%d", &arr[i]);
  }

  mergeSort( arr, 0, n);

  for( i = 0; i < n; i++){

    printf("%d", arr[i]);

    if( i != n-1)printf(" ");

  }

  printf("\n%d\n", c);

  return 0;
}

void merge(int *arr, int l, int m, int r){

  int le, ri, i, j, k;
  int L[N], R[N];
  le = m - l;
  ri = r - m;
  // ?´°??????
  for( i = 0; i < le; i++){

    L[i] = arr[l + i];

  }

  for( i = 0; i < ri; i++){

    R[i] = arr[m + i];

  }

  L[le] = INF;
  R[ri] = INF;

  i = j = 0;
  //??????
  for( k = l; k < r; k++){
    c++;
    if(L[i] <= R[j]){

      arr[k] = L[i];
      i++;

    }
    else{
 
      arr[k] = R[j];
      j++;

    }
  }
}

void mergeSort( int *arr, int l, int r){

  int m;

  if(l + 1 < r){
    m = (l + r) / 2;

    mergeSort( arr, l, m);
    mergeSort( arr, m, r);
    merge( arr, l, m, r);
  }
}

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

using i64 = int64_t;

class KMP{
private:
    string pattern;
    vector<int> table;

public:
    KMP(string pattern): pattern(pattern) {
        table.resize(pattern.size() + 1);
    }

    /*void print_table(){
        for(int i=0;i<pattern.size();++i){
            cout << pattern[i] << ": " << table[i] << endl;
        }
    }*/

    void build() {
        int m = pattern.size();
        table[0] = -1;
        for(int i=0,j=-1;i<m;++i){
            while(j >= 0 && pattern[i] != pattern[j])
                j = table[j];
            //table[k+1] = ++j;
            j++;
            if(pattern[i+1] == pattern[j]) table[i+1] = table[j];
            else table[i+1] = j;
        }
    }

    /*vector<int> search(const string &text) {
        int n = text.size(), m = pattern.size();
        vector<int> res;
        for(int k=0,i=0;k+i<n;){
            if(text[k+i] == pattern[i]){
                i++;
                if(i == m){
                    res.push_back(k);
                    k += i - table[i];
                    i = table[i];
                }
            }else{
                k += i - table[i];
                if(i > 0)
                    i = table[i];
            }
        }

        return res;
    }*/

    vector<int> search(const string &text) {
        int n = text.size(), m = pattern.size();
        vector<int> res;
        for(int i=0,j=0;j<n;){
            while(i > -1 && pattern[i] != text[j])
                i = table[i];
            i++; j++;
            if(i >= m) {
                res.push_back(j - i);
                i = table[i];
            }
        }
        return res;
    }
};

int main(){
    string t, p;
    cin >> t >> p;
    KMP kmp(p);
    kmp.build();
    //kmp.print_table();
    auto ans = kmp.search(t);
    for(auto e: ans){
        cout << e << endl;
    }

    return 0;
}



Measured memory_bytes: 8448
#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 <ctime>
#include <cstring>
 
using namespace std;

int main(){
	int mountain[10];
	for(int i=0;i<10;i++){
		cin>>mountain[i];
	}
	sort(mountain,mountain+10,greater<int>());
	for(int i=0;i<3;i++){
		cout<<mountain[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
	int n, m;
	cin >> n >> m;
	if (n == m) {cout << "Yes" << endl;}
	else {cout << "No" << endl;}
}

Measured memory_bytes: 256
n=int(input())
s=input()
l=len(s)
ans=[]
for i in range(l):
    if ord(s[i])+n<=90:
        ans.append(chr(ord(s[i])+n))
    else:
        ans.append(chr(ord(s[i])+n-26))
print(''.join(ans))

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>

int c[3][3];

int main(void) {
	int i, j;
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			if (scanf("%d", &c[i][j]) != 1) return 1;
		}
	}
	puts(
		c[0][0] - c[0][1] != c[1][0] - c[1][1] || c[0][0] - c[0][1] != c[2][0] - c[2][1] ||
		c[0][0] - c[0][2] != c[1][0] - c[1][2] || c[0][0] - c[0][2] != c[2][0] - c[2][2] ||
		c[0][1] - c[0][2] != c[1][1] - c[1][2] || c[0][1] - c[0][2] != c[2][1] - c[2][2] ||
		c[0][0] - c[1][0] != c[0][1] - c[1][1] || c[0][0] - c[1][0] != c[0][2] - c[1][2] ||
		c[0][0] - c[2][0] != c[0][1] - c[2][1] || c[0][0] - c[2][0] != c[0][2] - c[2][2] ||
		c[1][0] - c[2][0] != c[1][1] - c[2][1] || c[1][0] - c[2][0] != c[1][2] - c[2][2]
		? "No" : "Yes");
	return 0;
}


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


#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define pii pair<int,int>
#define pli pair<long long,int>
#define pil pair<int,long long>
#define ll long long
#define el '\n'

using namespace std;

const int N = 2e5 + 10;
const ll INF = 1e18;

ll k, n;
ll ar[N];
ll ans;

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

    cin >> k >> n;
    for (int i=1;i<=n;i++){
        cin >> ar[i];
    }

    ans = INF;
    for (int i=1;i<=n;i++){
        int fin = i - 1;
        if (fin == 0) fin = n;
        if (ar[fin] < ar[i]){
            ans = min(ans, k - ar[i] + ar[fin]);
        } else{
            ans = min(ans, ar[fin] - ar[i]);
        }
    }
    cout << ans << el;

    return 0;
}

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

int main() {
	int n;
	cin >> n;
	int a[n];
	for (int i = 0;i < n;i++)cin >> a[i];
	
	set<int>res;
	for (int i = 0;i < n;i++) {
		res.insert(a[i]);
	}
	cout << res.size() << endl;	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string a;
int cnt=0; 
int main()
{
    ios::sync_with_stdio(0);
    cin>>a;
    for(int i=0;i<a.size();i++){
        if(a[i]=='C'){
            cnt=1;
        }
        if(a[i]=='F'&&cnt==1){
            cout<<"Yes";
            return 0;
        }
    }
    cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;

int main() {
    int n,a=0,b=0;cin>>n;
    vector<int> vec(n);rep(i,n)cin>>vec.at(i);
    sort(all(vec));reverse(all(vec));
    rep(i,n) {
        if(i%2==0) a+=vec.at(i);
        else b+=vec.at(i);
    }
    cout<<a-b<<endl;
}

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

int main(void) {
    int n;
    cin >> n;
    map<string, int> cnt;
    rep(i,n){
        string s;
        cin >> s;
        cnt[s]++;
    }
    vector<string> result = {"AC", "WA", "TLE", "RE"};
    for (string r : result) {
        cout << r << " x " << cnt[r] << endl;
    }
    return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAX = 1000001;
const int MOD = 1000000007;

int fac[MAX], finv[MAX], inv[MAX];

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;
    }
}

int 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;
}

signed main(){
    int x, y; cin >> x >> y;
    if(((x + y) % 3 != 0) || (x > 2 * y) || (y > 2 * x)){
        cout << 0 << endl;
        return 0;
    }
    int a = (2 * y - x)/3;
    int b = (x + y)/3;

    COMinit();
    cout << COM(b, a) << endl;
}

Measured memory_bytes: 23680
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include<iomanip>

//#include<bits/stdc++.h>


using namespace std;

int t[100005];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> t[i];
	int r = 0;
	for (int i = 1; i <= n; i++) {
		if (!t[i])continue;
		if (t[t[i]] == i) {
			r++;
			t[t[i]] = 0;
		}
	}
	cout << r << endl;

	return 0;

}


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

using namespace std;


int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int cn = 0;
    string st;
    char c, c1;
    for (int i = 0; i < n; i++) {
        cin >> c;
        if (i != 0 && c != c1 && c == '(') {/*
            if (cn > 0)
                for (int j = 0; j < cn; j++) {
                    st += ")";
                }
            else*/ if(cn < 0) {
                for (int j = 0; j < -1 * cn; j++) {
                    st = "(" + st;
                }
                cn = 0;
            }

        }
        st += c;
        c1 = c;
        if (c == '(') cn++;
        else cn--;
    }
    if (cn > 0)
        for (int j = 0; j < cn; j++) {
            st += ")";
        }
    else if(cn < 0)
        for (int j = 0; j < -cn; j++) {
            st =  "(" + st;
        }
    cout << st << endl;
}


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

using namespace std;

int main(void) {
    int A, B, K;
    
    cin >> A >> B >> K;
    
    for (int i = min(A, B); i >= 1; i--) {
        if (A % i == 0 && B % i == 0) K--;
        if (K == 0) {
            cout << i << endl;
            break;
        }
    }

}

Measured memory_bytes: 256