akhauriyash/Code-Regression huggingface dataset:
nk = [int(s) for s in input().split()]
n, k = nk[0], nk[1]
cities = [int(s) for s in input().split()]
curr_city = 1
F = {1 : [0]}
round = 1
loop = 0
while True:
    curr_city = cities[curr_city-1]
    if curr_city in F:
        F[curr_city].append(round)
        if len(F[curr_city]) >= 3:
            break
    else:
        F[curr_city] = [round]
    round += 1
round = 1
curr_city = 1
while len(F[curr_city]) < 3:
    curr_city = cities[curr_city-1]
    round += 1
    k -= 1
    if k == 0:
        print(curr_city)
        break
    
if k > 0:
    loop = F[curr_city][1]-F[curr_city][0]
    k = k%loop
    while k > 0:
        curr_city = cities[curr_city-1]
        k -= 1
    print(curr_city)

Measured memory_bytes: 60184
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll pow(ll x, ll y) {
  ll ans = 1;
  if(y > 0) {
    for(ll i = 0; i < y; i++)
      ans *= x;
  }
  return ans;
}
int main() {
  ll a;
  cin >> a;
  cout << a + pow(a, 2) + pow(a, 3) << endl;
}

Measured memory_bytes: 4220
def calc_median(X):
    #中央値計算
    Xl = len(X)
    if Xl % 2:
        #ret = X[(Xl + 1) // 2 - 1]
        ret = X[Xl // 2]
    else:
        ret = (X[Xl // 2 - 1] + X[Xl // 2]) / 2

    return ret


N, *AB = map(int, open(0).read().split())

A = sorted(AB[::2])
B = sorted(AB[1::2])

AM = calc_median(A)
BM = calc_median(B)

if N % 2:
    ans = BM - AM + 1
else:
    ans = int((BM - AM) * 2 + 1)

print(ans)


Measured memory_bytes: 55364
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(void){
  string a,b; cin >> a >> b;
  int c,d; cin >> c >> d;
  string e; cin >> e;
  if(a==e) --c;
  else --d;
  cout << c << " " << d << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main
{
  public static void main(String []args)
  {
    Scanner sc = new Scanner(System.in);
    String s = sc.nextLine();
    String t = sc.nextLine();
   
    int min = Integer.MAX_VALUE;
    for(int i = 0 ; i < s.length() ; i++)
    {
      if(i+t.length() <= s.length())
      {
        int tot = 0;
         for(int j = 0 ; j < t.length(); j++)
         {
           if(s.charAt(i+j) != t.charAt(j))
             tot++;
         }
        min = Math.min(min , tot);
      }
    }
    System.out.println(min);
  }
  }


Measured memory_bytes: 36556
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main() {
	int i, a;
	int a_array[20000], b_array[20000];
	char op_array[20000];

	for (i = 0; i < 20000; i++) {
		scanf("%d %c %d", &a_array[i], &op_array[i], &b_array[i]);
		if (op_array[i] == '?') {
			break;
		}
	}
	for (i = 0; i < 20000; i++) {
		if (op_array[i] == '?') {
			break;
		}
		switch (op_array[i]){
		case'+':
			printf("%d\n", a_array[i] + b_array[i]);
			break;
		case'-':
			printf("%d\n", a_array[i] - b_array[i]);
			break;
		case'*':
			printf("%d\n", a_array[i] * b_array[i]);
			break;
		case'/':
			printf("%d\n", a_array[i] / b_array[i]);
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 2124
def main():
    import sys
    buf = sys.stdin.buffer

    class SegmentTree:
        def __init__(self, target, no_effect):
            target_size = len(target)
            leaves_size = 1
            while leaves_size < target_size:
                leaves_size *= 2
            self.tree_size = leaves_size * 2 - 1
            self.tree = [no_effect] * self.tree_size
            self.no_effect = no_effect
            self.initialize_tree(target)

        @classmethod
        def initialize_func(cls, value):
            return 1 << (ord(value) - ord('a'))

        @classmethod
        def merge_func(cls, a, b):
            return a | b

        def merge_child_data(self, node):
            child1 = node * 2 + 1
            child2 = node * 2 + 2
            merged = self.merge_func(self.tree[child1], self.tree[child2])
            return merged

        def initialize_tree(self, target):
            initial_leaf = self.tree_size // 2
            leaves = range(initial_leaf, initial_leaf+len(target))
            for value, leaf in zip(target, leaves):
                self.tree[leaf] = self.initialize_func(value)

            for parent in range(initial_leaf-1, -1, -1):
                self.tree[parent] = self.merge_child_data(parent)

        def update(self, new_value, index):
            leaf = self.tree_size//2 + index
            new_data = self.initialize_func(new_value)
            if self.tree[leaf] == new_data:
                return
            self.tree[leaf] = new_data

            parent = (leaf-1) // 2
            while parent >= 0:
                new_data = self.merge_child_data(parent)
                if self.tree[parent] == new_data:
                    break
                self.tree[parent] = new_data
                parent = (parent-1) // 2

        def resolve_query(self, _from, to):
            result = self.no_effect
            left, right = _from + self.tree_size//2, to + self.tree_size//2
            while left <= right:
                result = self.merge_func(result, self.tree[left])
                result = self.merge_func(result, self.tree[right])
                left //= 2
                right = right//2 - 1

            return bin(result).count('1')

    n, S, _, *queries = buf.read().split()
    S = S.decode()
    seg_tree = SegmentTree(target=S, no_effect=0)

    for type, a, b in zip(*[iter(queries)]*3):
        if type == b'1':
            index, new = int(a)-1, b
            seg_tree.update(new, index)

        elif type == b'2':
            _from, to = int(a)-1, int(b)-1
            print(seg_tree.resolve_query(_from, to))


if __name__ == '__main__':
    main()

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

int main() {
  int N;
  cin>>N;
  int n=0;
  int t=N;
  while(t>0){
    n+=t%10;
    t/=10;
  }
  if(N%n==0){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}


Measured memory_bytes: 3528
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

   private static final String INPUT_FILE_PATH = "";

   static void solve(InputReader in, PrintWriter out) {
      int d = in.nextInt(), t = in.nextInt(), s = in.nextInt();
      out.println(t * s >= d ? "Yes" : "No");
   }

   public static void main(String[] args) throws Exception {
      InputStream inputStream = INPUT_FILE_PATH.isEmpty()
         ? System.in
         : new FileInputStream(new File(INPUT_FILE_PATH));
      OutputStream outputStream = System.out;

      InputReader inputReader = new InputReader(inputStream);
      PrintWriter printWriter = new PrintWriter(outputStream);

      solve(inputReader, printWriter);

      printWriter.close();
   }

   private static class InputReader {
      private BufferedReader br;
      private StringTokenizer st;

      public InputReader(InputStream inputStream) {
         this.br = new BufferedReader(new InputStreamReader(inputStream), 32768);
         this.st = null;
      }

      public String nextToken() {
         while (st == null || !st.hasMoreTokens()) {
            try {
               st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
               throw new RuntimeException(e);
            }
         }
         return st.nextToken();
      }

      public int nextInt() {
         return Integer.parseInt(nextToken());
      }

      public long nextLong() {
         return Long.parseLong(nextToken());
      }

      public double nextDouble() {
         return Double.parseDouble(nextToken());
      }
   }

}


Measured memory_bytes: 32756
N = int(input())
T, A = map(int, input().split())

H = list(map(int, input().split()))

ave_dis = None
num = 0

for i in range(1, N+1):
    ave = T - H[i-1]*0.006

    ave_dis_tmp = abs(A - ave)

    if ave_dis == None or ave_dis > ave_dis_tmp:
        num = i
        ave_dis = ave_dis_tmp

print(num)

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

vector<int> par;
vector<int> RA;
int root(int a){
  if(a==par.at(a)){
    return a;
  }
  else{
    return par.at(a)=root(par.at(a));
  }
}
void UN(int a,int b){
  a=root(a);
  b=root(b);
  if(a==b){
    return;
  }
  else if(RA.at(a)<RA.at(b)){
    par.at(a)=b;
  }
  else{
    par.at(b)=a;
  }
  if(RA.at(a)==RA.at(b)){
    RA.at(a)++;
  }
}

int main() {
  int N;
  cin>>N;
  par.resize(N);
  RA.resize(N);
  for(int i=0;i<N;i++){
    par.at(i)=i;
  }
  
  vector<tuple<int,int,int>> p(N);
  vector<tuple<int,int,int>> q(N);
  for(int i=0;i<N;i++){
    int a,b;
    cin>>a>>b;
    p.at(i)=make_tuple(a,b,i);
    q.at(i)=make_tuple(b,a,i);
  }
  sort(p.begin(), p.end());
  sort(q.begin(), q.end());
  vector<tuple<int,int,int>> r;
  for(int i=1;i<N;i++){
    int a,b,c,d,e,f;
    tie(a,b,c)=p.at(i-1);
    tie(d,e,f)=p.at(i);
    r.push_back(make_tuple(min(abs(a-d),abs(b-e)),c,f));
  }
  for(int i=1;i<N;i++){
    int a,b,c,d,e,f;
    tie(a,b,c)=q.at(i-1);
    tie(d,e,f)=q.at(i);
    r.push_back(make_tuple(min(abs(a-d),abs(b-e)),c,f));
  }
  sort(r.begin(), r.end());
  int64_t Z=0;
  int A=1;
  int K=0;
  while(A<N){
    int a,b,c;
    tie(a,b,c)=r.at(K);
    if(root(b)!=root(c)){
      UN(c,b);
      Z+=a;
      A++;
    }
    K++;
  }
  cout<<Z<<endl;

}




Measured memory_bytes: 8052
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  while(~scanf("%d%d",&a,&b)){
     if (a<=9 && b<=9){
        printf("%d\n",a*b);
     }else{
        printf("-1\n");
     }
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;


int min(int a, int b)
{
	return (a < b ? a : b);
}
int max(int a, int b)
{
	return (a > b ? a : b);
}
int abso(int x)
{
	return (x >= 0 ? x : -x);
}
static const int INF = 1e9;
int MEMO[100010][3];
int H[100010][3];
int N;
int dp(int i, int j)
{
	if (MEMO[i][j] != -1)return MEMO[i][j];
	int ans = H[i][j];
	if (i + 1 < N)
	{
		for (int k = 0; k < 3; k++)
		{
			if (k != j)
			{
				ans = max(ans, H[i][j] + dp(i + 1, k));
			}
		}
	}
	return MEMO[i][j] = ans;
}
int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)for (int j = 0; j < 3; j++)cin >> H[i][j];
	memset(MEMO, -1, sizeof MEMO);
	cout << max(dp(0, 0), max(dp(0, 1), dp(0, 2))) << endl;
}

Measured memory_bytes: 10368
p = int(input())
a = [int(item) for item in input().split()]

fac = [1] + [0] * (p - 1)
facinv = [1] + [0] * (p - 1)
for i in range(1, p):
    fac[i] = fac[i-1] * i % p
    facinv[i] = facinv[i-1] * pow(i, p-2, p) % p

# print(fac)
# print(facinv)
comb = [0] * p
for i in range(p):
    comb[i] = fac[p-1] * facinv[i] * facinv[p-1-i] % p

# print(comb)
ans = [0] * p
ppowp = [[0] * (p + 1) for _ in range(p + 1)]
for i in range(p+1):
    val = 1
    for j in range(p+1):
        ppowp[i][j] = val
        val *= i
        val %= p

for i, item in enumerate(a):
    if item == 1:
        ans[0] += 1
        # Calc (i - x)**(p - 1) 
        for j in range(p):
            # ans[j] -= pow(i, p-1-j, p) * pow(-1, j, p) * comb[j] % p
            if j % 2 == 1:
                ans[j] -= ppowp[i][p-1-j] * -1 * comb[j] % p
            else:
                ans[j] -= ppowp[i][p-1-j] * comb[j] % p
            ans[j] %= p
print(" ".join([str(item) for item in ans]))

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

int main()
{
  int N;

  cin >> N;

  vector<int> vec(N);

  int sum = 0;

  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
    sum += vec.at(i);
  }

  int S1 = 0;
  int S2 = sum;
  int ans = S2 - S1;

  for (int i = 0; i < N; i++) {
    S1 += vec.at(i);
    S2 = sum - S1;

    if (S1 <= S2) {
      ans = min(ans, S2 - S1);
    }
    else {
      ans = min(ans, S1 - S2);
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;

void debug_out() { cout << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cout << "debug: "; debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define Rep(i, n) for (long long i = 0; i< (long long)(n); i++)
#define RRep(i,n) for (long long i = ((long long)(n)-1); i>=0; i--)
#define all(v) (v).begin(),(v).end()

struct Edge{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w){ }
};

struct edge{
    int from;
    int to;
    int weight;
    edge(int f,int t,int w) : from(f), to(t), weight(w){ }
};

using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;
using edges = vector<edge>;

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

template <class T>
T gcd(T a, T b){
    if( b==0 ) return a;
    return gcd(b, a%b);
}

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

bool isPalindrome(string s){
    string t = s;
    reverse(all(t));
    return s==t;
}

constexpr int INF = 1e9+7;

vector<int> dx = {-1,0,1,0};
vector<int> dy = {0,-1,0,1};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m,x;
    cin >> n >> m >> x;
    vector<int> a(m);
    rep(i,m) cin >> a[i];
    auto index = lower_bound(all(a),x);
    int ans = min(index-a.begin(),a.end()-index);
    cout << ans<< endl;
}

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

using namespace std;
typedef long long ll;

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

bool srt(int a , int b){
    return a > b ;
}
int a[3][3];

void calc(int i,int j,int k){
    int b[3][3];
    for(int p=0;p<3;p++){
        for(int o=0;o<3;o++){
            b[p][o]=a[p][o];
            if(p==0)b[p][o]-=i;
            else if(p==1)b[p][o]-=j;
            else b[p][o]-=k;
        }
    }
    if(b[0][0]==b[1][0]&&b[1][0]==b[2][0]){
        if(b[0][1]==b[1][1]&&b[1][1]==b[2][1]){
            if(b[0][2]==b[1][2]&&b[1][2]==b[2][2]){
                puts("Yes");
                exit(0);
            }
        }
    }
}
int main(){
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>a[i][j];
    for(int i=0;i<=100;i++){
        for(int j=0;j<=100;j++){
            for(int k=0;k<=100;k++){
                calc(i,j,k);
            }
        }
    }
    puts("No");
    return 0;
}


Measured memory_bytes: 256
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
def x(i):
    return -(-i//10)*10
def y(i):
    return -i%10

print(x(a) + x(b) + x(c) + x(d) + x(e) - max([y(a), y(b), y(c), y(d), y(e)]))


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

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

  if (A < C && C < B) cout << "Yes" << endl;
  else if (B < C &&  C < A) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

#define REP(i ,n) for(int i=0 ;i < n; i++)
#define REPB(i ,n) for(int i=n; i >= 0; i--)
#define FOR(i ,m ,n) for(int i=m; i < n; i++)
#define FORB(i, m, n) for(int i=m; i>= n; i--)
#define ll long long
#define pb push_back
#define popb pop_back
#define debug(i) cout<< #i<< "= "<< i << endl
using namespace std;
bool isnotprime[120001] = {};
void primecheck();
int main(){
    int n;
    cin >> n;
    primecheck();
    FOR(i,n,120000){
        if(isnotprime[i] == false){
            cout << i << endl;
            return 0;
        }
    }
}

void primecheck(){
    isnotprime[1] = true;
    int k = sqrt(120000);
    FOR(i,2,k){
        if(isnotprime[i] == true) continue;
        for(int j=i*2;j<=120000;j+=i){
            isnotprime[j] = true;
        }
    }
}

Measured memory_bytes: 384
n = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
z = []
for i in range(n):
  z.append([x[i],y[i]])
z.sort(key = lambda x:x[1])
a = []
b = []
for i in range(n):
  a.append(z[i][0])
  b.append(z[i][1])
#print(a)
#print(b)
A = sorted(a)
B = sorted(b)
#print(A)
#print(B)
check = 1
for i in range(n):
  if A[i] > B[i]:
    check = 0
    break
for i in range(n-1):
  if A[i+1] <= B[i]:
    check *= 2
    #print(A[i],B[i+1])
    break
#print(check)
for i in range(n-1):
  if A[i] == A[i+1]:
    check *= 2
    break
  if B[i] == B[i+1]:
    check *= 2
    break
c = []
for i in range(n):
  c.append([a[i],i])
c.sort()
#print(c)
d = [-1 for _ in range(n)]
for i in range(n):
  d[c[i][1]] = i
#print(d)
count = 0
now = 0
while True:
  count += 1
  now = d[now]
  if now == 0:
    break
#print(check,count)
if check == 0:
  print('No')
elif check > 1:
  print('Yes')
elif count == n:
  print('No')
else:
  print('Yes')

Measured memory_bytes: 104336
#include <stdio.h>

int
main(int argc, char *argv[])
{
  long long n, m;
  scanf("%lld %lld", &n, &m);

  long long ans;

  if(n > m / 2) ans = m / 2;
  else ans = (m - 2*n)/4 + n;

  printf("%lld\n", ans);

  return 0;
}

Measured memory_bytes: 128
#include <iostream>

using namespace std;

void a();

int main()
{
	a();
    return 0;
}

void a()
{
	int A, B;
	cin >> A >> B;
	if (A + B >= 10)
	{
		cout << "error" << endl;
	}
	else {
		cout << A + B << endl;
	}
	return;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define se second
#define fi first
#define ll long long
#define ld long double
#define pll pair<ll ,ll >
#define plll pair<ll,pll>
#define ppll pair<pll, pll>
#define pii pair<int, int> 
#define pb push_back
#define mod 1000000007
#define N 2000007
ll power(ll a,ll b){
    ll res=1ll;
    while(b>0){
        if(b%2!=0) res=(res*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return res%mod;
}
ll ncr(ll n,ll k){
    if(k>n-k) k=n-k;
    ll pro=1;
    for(ll i=0;i<k;i++){
        pro=(pro*(n-i))%mod;
        pro/=(i+1);
    }
    return (pro)%mod;
}

void swap(ll *a,ll *b) {
    ll temp=*a;
    *a=*b;
    *b=temp;
}
vector<ll> prime;
void seive(){
    vector<bool > isprime(1000001,true);
    for(int i=2;i*i<=1000000;i++){
        if(isprime[i]){
            for(int j=i*i;j<=1000000;j+=i){
                isprime[j]=false;
            }
        }
    }
    for(int i=2;i<=1000000;i++){
        if(isprime[i]) prime.push_back(i);
    }
}
vector<ll> parent;
ll find(ll p) {
    if(parent[p]==p) return parent[p];
    return parent[p]=find(parent[p]); 
}
void unun(ll a,ll b) {
    ll r1=find(a);
    ll r2=find(b);
    if(r1!=r2) parent[r2]=r1;
}
void solve() {
    ll n;
    cin>>n;
    vector<ll> arr(n);
    map<ll,ll> mp;
    for(int i=0;i<n;i++) {
        cin>>arr[i];
        mp[arr[i]]++;
    }
    ll sum=0;
    for(auto itr: mp) {
        ll val=itr.se;
        sum+=(val*(val-1))/2;    
    }
    for(int i=0;i<n;i++) {
        ll val1=mp[arr[i]]-1;
        ll val2=mp[arr[i]];
        ll ans=(sum-(val2*(val2-1))/2)+(val1*(val1-1))/2;
        cout<<ans<<"\n";
    }
}   


int main(void){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    t=1;
    // cin>>t;
    while(t--) {
        solve();
        // cout<<endl;
    }
    return 0; 

}


Measured memory_bytes: 11136
N,x=map(int,input().split())
A=list(map(int,input().split()))

ans=0
if A[0]>x:
  ans+=A[0]-x
  A[0]=x
  
SA=[A[i]+A[i+1] for i in range(N-1)]

for i in range(N-2):
  if SA[i]>x:
    ans+=SA[i]-x
    SA[i+1]-=SA[i]-x
    SA[i]=x

if SA[N-2]>x:
  ans+=SA[N-2]-x
print(ans)

Measured memory_bytes: 14548
#include<bits/stdc++.h>
using namespace std;
int main(){
  int r,n;
  while(cin>>r>>n,r){
    int h[50][2]={};
    for(int i=0,a,b,y;i<n;i++){
      cin>>a>>b>>y;
      h[a+20][0]=max(h[a+20][0],y);
      h[b+20][1]=max(h[b+20][1],y);
      for(int x=a+1;x<b;x++){
	h[x+20][0]=max(h[x+20][0],y);
	h[x+20][1]=max(h[x+20][1],y);
      }
    }
    double ans=1e9;
    for(int x=-r+1;x<r;x++)
      ans=min(ans,min(h[x+20][0],h[x+20][1])-sqrt(r*r-x*x)+r);
    cout<<ans<<endl;
  }
  return 0;
}


Measured memory_bytes: 3252
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(){
        srand(time(NULL));
        int n;
        cin >> n;
        vector<string> mat(n);
        vector<int> accept;
        int fixed = -1;
        for(int i = 0; i < n; ++i){
                cin >> mat[i];
                if(mat[i].find('x') == string::npos){ fixed = i; }
                if(mat[i].find('o') != string::npos){ accept.push_back(i); }
        }
        for(int i = 0; i < 1000; ++i){
                if(fixed < 0){
                        cout << (accept[rand() % accept.size()] + 1) << endl << flush;
                }else{
                        cout << (fixed + 1) << endl << flush;
                }
                int opposite;
                cin >> opposite;
        }
        return 0;
}

Measured memory_bytes: 0
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input=input.split("\n");
	tmp = input[0].split(" ");
	//文字列から10進数に変換するときはparseIntを使います
	var a = parseInt(tmp[0], 10);
	var b = parseInt(tmp[1], 10);
	var add=a+b;
	var sub=a-b;
	var mul=a*b;
	//出力
	var ans=Math.max(add,sub,mul);
  	if(ans === -0) ans = 0;
	console.log(ans);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main() {
  int N; cin >> N;
  int P[N]; for (int i = 0; i < N; i++) cin >> P[i];
  int count = 0;
  for (int i = 1; i < N-1; i++) {
    if ((P[i-1] - P[i]) * (P[i] - P[i+1]) >= 0) count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int main(){
  int a, b, c, x,count = 0;
  cin >> a >> b >> c >> x;
  for (int i = 0; i <= a;i++){
    for (int j = 0; j <= b;j++){
      for (int k = 0; k <= c;k++){
        if((500*i+100*j+50*k)== x)
          count++;
      }
    }
  }
  cout << count << endl;
  return 0;
}


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

int main() {
    double  PI=3.14159265358979323846;
    double r;
    cin >> r ;
    cout << fixed << setprecision(6) <<(double) r*r*PI << " ";
    cout << fixed << setprecision(6) <<(double) 2*PI*r << endl;
}


Measured memory_bytes: 3300
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL


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

    s64 n;
    cin >> n;
    vs64 A(n);
    rep (i, n) cin >> A[i];

    s64 ans = 0;
    s64 now = 1;
    int i = 0;
    while (i < n)
    {
        while (A[i] != now && i < n)
        {
            ++i;
            ++ans;
        }
        if (A[i] == now && i < n)
        {
            ++now;
        }
        else
        {
            break;
        }
        ++i;
    }

    cout  << (now != 1 ? ans : -1) << "\n";
    return 0;
}



Measured memory_bytes: 1792
#include <stdio.h>

int main(){
  int N, o=0;
  
  scanf("%d", &N);
  if(N%2 == 0){
    o = N/2;
  }else{
    o = N/2 + 1;
  }
  
  printf("%f", (double)o/N);
  
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 200000;
int n;
ll dpl[N + 2], dpr[N + 2], x[N + 1];

struct S{
	ll l, r, fr;
	S(ll x):l(x), r(x), fr(1) {}
	ll operator +=(S const &o){
		ll t = o.l, an = 0, nr = o.r;
		while (r > t)t <<= 2, nr <<= 2, an += o.fr << 1;
		fr += o.fr;
		r = nr;
		return an;
	}
};

void go(ll dp[]){
	ll an = 0;
	deque<S> dq;
	f(i, 1, n + 1){
		S c(x[i]);
		while (!dq.empty() && dq.front().l < c.r)an += (c += dq.front()), dq.pop_front();
		dq.push_front(c);
		dp[i] = an;
	}
}

int main(){
	scanf("%d", &n);
	f(i, 1, n + 1)scanf("%lld", x + i);
	reverse(x + 1, x + n + 1);
	go(dpr);
	reverse(dpr + 1, dpr + n + 1);
	reverse(x + 1, x + n + 1);
	f(i, 1, n + 1)x[i] <<= 1;
	go(dpl);
	f(i, 1, n + 1)dpl[i] += i;
	ll an = 1e18;
	f(i, 0, n + 1)an = min(an, dpl[i] + dpr[i + 1]);
	printf("%lld\n", an);
}

Measured memory_bytes: 9728
package main

import (
	"fmt"
	"math"
	"strings"
)

var n int
var t string

func main() {
	fmt.Scan(&n)
	S := make([][]string, n)

	for i := 0; i < n; i++ {
		S[i] = make([]string, 0, n)
		fmt.Scan(&t)
		S[i] = strings.Split(t, "")
	}

	ans := make(map[string]int)

	for i := 0; i < n; i++ {
		cnt := make(map[string]int)
		for j := 0; j < len(S[i]); j++ {
			cnt[S[i][j]]++
		}
		if i == 0 {
			ans = cnt
		}
		for key, _ := range ans {
			ans[key] = min(ans[key], cnt[key])
		}
	}
	var str string
	for _, x := range "abcdefghijklmnopqrstuvwxyz" {
		if ans[string(x)] != 0 {
			for i := 0; i < ans[string(x)]; i++ {
				str += string(x)
			}
		}
	}
	fmt.Println(str)
}

/*  ----------------------------------------  */

func gcd(x, y uint64) uint64 {
	if x%y == 0 {
		return y
	} else {
		r := x % y
		return gcd(y, r)
	}
}

func combination(x, y int) int {
	return permutation(x, y) / permutation(y, y)
}

func permutation(x, y int) int {
	var ans int = 1
	for i := x - y; 0 < i; i-- {
		ans *= i
	}
	return ans
}

func max(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Max(float64(x[i]), float64(res)))
	}
	return res
}

func min(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Min(float64(x[i]), float64(res)))
	}
	return res
}

func pow(x, y int) uint64 { return uint64(math.Pow(float64(x), float64(y))) }
func abs(x int) int       { return int(math.Abs(float64(x))) }
func floor(x int) int     { return int(math.Floor(float64(x))) }

type si struct {
	s int
	i int
}

type SortBy []si

func (a SortBy) Len() int           { return len(a) }
func (a SortBy) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a SortBy) Less(i, j int) bool { return a[i].s < a[j].s }


Measured memory_bytes: 768
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
 
using namespace std;
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;

	cin >> N;

	int check = 1;
	int count = 0;

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

		if(a == check) {
			check++;
		} else {
			count++;
		}
	}

	if(check == 1) {
		cout << -1 << endl;
	} else {
		cout << count << endl;
	}
}


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

const int INF = 1e9;

int main() {
    int N;
    cin >> N;
    vector<int> h(N);
    for(auto &e : h) cin >> e;

    vector<int> dp(N+1, INF);
    dp[0] = 0;
    for(int i = 0; i < N; i++) {
        if (i + 1 < N) dp[i+1] = min(dp[i+1], dp[i] + abs(h[i+1] - h[i]));
        if (i + 2 < N) dp[i+2] = min(dp[i+2], dp[i] + abs(h[i+2] - h[i]));
    }

    cout << dp[N-1] << endl;

    return 0;
}


Measured memory_bytes: 1024
n, m = map(int, input().split())
b = [tuple(map(int, input().split())) for _ in range(n)]
b.sort()
num = m
ans = 0
for i in b:
    if num > 0:
        ans += i[0] * min(i[1], num)
        num -= min(i[1], num)
    else:
        break
print(ans)

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

int main(void)
{
  int a, b;
  cin >> a >> b;
  int ans = 0;
  int outlet = 1;
  while (outlet < b) {
  	--outlet;
    outlet += a;
    ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
    using namespace std;
    #define IOS ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; cout.tie(NULL);
    #define int long long
    #define pi pair<int,int>
    #define ff first
    #define ss second
    #define pb push_back
    #define mod 1000000007
    #define vi vector<int >

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

    string s;
    int a=0,b=0,c=0,d=0;
    while(n--){
        cin>>s;
        if(s=="AC") a++;
        else if(s == "WA") b++;
        else if(s == "TLE") c++;
        else d++;

    }
    cout<<"AC x "<<a<<endl;
    cout<<"WA x "<<b<<endl;
    cout << "TLE x " <<c << endl;
    cout << "RE x " << d<< endl;
    }

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

int main() {
  ll x;
  cin >> x;
  ll ans = 0;
  ll kane = 100;
  while (kane < x) {
    kane = kane + (ll)(kane * 0.01);
    ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>
#include <cmath>
#include <stack>
#include <random>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

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

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

constexpr ll mod = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

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

  string s; cin >> s;
  int cnt = 0;
  int ans = 0;
  for(auto c: s) {
    if (c=='A' || c=='C' || c=='G' || c=='T') {
      cnt++;
      chmax(ans, cnt);
    } else {
      cnt = 0;
    }
  }
  cout << ans << endl;

}


Measured memory_bytes: 256
///supercalifragilisticexpialidocious.
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define PB pop_back
#define pb push_back
#define mp make_pair
#define int long long
#define sz(s) (int)s.size()
#define seper(n) setprecision(n)
#define all(sum) sum.begin(),sum.end()
#define mem(a,b) memset(a,b,sizeof a)
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef map<int , int> mii;
typedef pair<int , int> pii;
typedef map<string , int> msi;
typedef pair<int , string> pis;
const int MAXN = 1e5 + 10;
int n , a , b , ans , sum2 , sum[MAXN];
int32_t main()
{
	cin >> n;
	for(int i = 0 ; i < n ; i ++)
		cin >> a >> b , sum2 += b , sum[i] = a + b;
	sort(sum , sum + n) , reverse(sum , sum + n);
	for(int i = 0 ; i < n ; i += 2)
		ans += sum[i];
	return cout << ans - sum2 << endl , 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int sq = 0;
		for(int i = 1; i*i <= N; i++) sq = i*i; 
		System.out.println(sq);
	}
}

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

int main(){
    while (true){
        int h, w;
        cin >> h >> w;
        if (h == 0 && w == 0) break;
        for (int i = 0; i < h; i++){
            for (int j = 0; j < w; j++){
                cout << "#";
            }
            cout << endl;
        }

    cout << endl;

    }
    return 0;
}


Measured memory_bytes: 3092
#include <iostream>
#include <string.h>
using namespace std;
int main(void) {
	char x, y;
	cin >> x >> y;
	int n = strcmp(&x, &y);
	char ans;
	if (x == y) {
		ans = '=';
	}
	else if (n > 0) {
		ans = '>';
	}
	else {
		ans = '<';
	}
	cout << ans << endl;
	return 0;
}

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

typedef long long int ll;
typedef long double ld;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define MOD (ll)(1e9 + 7)
#define vi vector<int>
#define vii vector<vector<int> >
#define vl vector<ll>
#define vll vector<vector<ll> >
#define vc(T, nm) vector<T> nm
#define pb push_back
#define popb pop_back
#define si set<int>
#define sl set<ll>
#define F first
#define S second
#define pii pair<int, int>
#define mp make_pair
#define insert ins
#define ers erase
#define FORA(x, s, e, inc) for(ll x = s; x != e; x += inc)
#define ROFA(x, s, e, inc) for(ll x = s; x != e; x -= inc)
#define FOR(x, s, e) FORA(x, s, e, 1)
#define ROF(x, s, e) ROFA(x, s, e, 1)
#define loop(x, n) FOR(x, 0, n)
#define rd1(t, a) 					t a; cin >> a;
#define rd2(t, a, b) 				rd1(t, a); rd1(t, b); 
#define rd3(t, a, b, c) 			rd2(t, a, b); rd1(t, c);
#define rd4(t, a, b, c, d) 			rd3(t, a, b, c); rd1(t, d);
#define rd5(t, a, b, c, d, e) 		rd4(t, a, b, c, d); rd1(t, e);
#define rd6(t, a, b, c, d, e, f) 	rd5(t, a, b, c, d, e); rd1(t, f);
#define rdA(t, nm, len)				t nm[len]; loop(i, len) {cin >> nm[i];}
#ifdef DEBUG
	#define deb(v) cout << endl << #v << ": " << v << endl
	#define db1(v) cout << endl << #v << ": " << "[ "; for(auto x: v) {cout << x << " ";}; cout << "]" << endl;
	#define db2(v) cout << endl << #v << ": " << endl; for(auto r: v) {cout << "[ "; for(auto x: r) {cout << x << " ";}; cout << "]" << endl;};
	#define dbl cout << "-------------------------------" << endl
#else
	#define deb(v)
	#define db1(v)
	#define db2(v)
	#define dbl
#endif

int main() {
	
	fastio;

    rd1(ll, n);
    rdA(ll, a, n);
    
    ll mnm = a[0];
    vl ans;
    ans.pb(a[0]);
    FOR(i, 1, n) {
        if(a[i]  < mnm)
            ans.pb(a[i]);
        mnm = min(mnm, a[i]);
        
    }
    
    cout << ans.size();
    cout << endl;
    
	return 0;
}

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

int main(void){
    int h, w;
    cin >> h >> w;
    vector<vector<char>> a(h, vector<char>(w));
    vector<bool> d_h(h), d_w(w);
    rep(i, h){
        rep(j, w){
            cin >> a.at(i).at(j);
            if(a.at(i).at(j) == '#'){
                d_h.at(i) = true;
                d_w.at(j) = true;
            }
        }
    }

    rep(i, h){
        if(!d_h.at(i)) continue;
        rep(j, w){
            if(!d_w.at(j)) continue;
            cout << a.at(i).at(j);
        }
        cout << endl;
    }
    return 0;
}

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

ll solve() {
    ll M;
    cin >> M;
    vector<ll> D(M), C(M);
    for ( int i = 0; i < M; i++ ) {
        cin >> D[i] >> C[i];
    }
    ll s = 0, c = 0;
    for ( int i = 0; i < M; i++ ) {
        s += C[i] * D[i];
        c += C[i];
    }
    ll s0 = s;
    ll d = s/10;
    while ( d > 0 ) {
        ll s1 = s0 + d;
        d = s1/10 - s0/10;
        s0 = s1;
    }
    
    ll ans = c-1+s0/10;
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3328
(function main() {
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());

  const adjLists = Array.from(Array(n), () => []);
  lines.forEach((l, i) => l.split(' ').splice(2).forEach(e => adjLists[i].push(e-1)));

  const d = [], f = [];
  dfs(adjLists, d, f);
  for (let i = 0; i < n; i++) {
    console.log(i + 1, d[i], f[i]);
  }
})();

function dfs(adjLists, d, f) {
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const size = adjLists.length;
  const color = Array.from(adjLists, () => WHITE);

  let time = 0;
  function visit(u) {
    color[u] = GRAY;
    d[u] = ++time;
    adjLists[u].forEach(v => {
      if (color[v] === WHITE) {
        visit(v);
      }
    });
    color[u] = BLACK;
    f[u] = ++time;
  }
  adjLists.forEach((u, i) => {
    if (color[i] === WHITE) visit(i);
  });
}



Measured memory_bytes: 16800
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,X;
  cin>>N>>X;
  vector<int> A(N);
  for(int i=0;i<N;i++){
      cin >> A[i];
  }
  int H=0;
  sort(A.begin(), A.end());
  for(int i=0;i<N;i++) {
    if(X-A[i]<0){ 
        break;
    }
    if(i==N-1&&X-A[i]!=0) {
        break;
    }
      X-=A[i];
      H++;
}
  cout << H;
  return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
#define MAXN 500005

//<>>><<><<<<<>>><
string S;
int N;
int Left[MAXN], Right[MAXN];
ll ans;

int main(void){
    //cout<<"AGC 040 a\n";
    cin>>S;
    N=S.length()+1;
    
    for(int i=0; i<N-1; i++){
        if(S[i]=='<'){
            Left[i+1]=Left[i]+1;
        }else{
            Left[i+1]=0;
        }
    }
    
    for(int i=N-2; i>=0; i--){
        if(S[i]=='>'){
            Right[i]=Right[i+1]+1;
        }else{
            Right[i]=0;
        }
    }
    
    for(int i=0; i<N; i++){
        ans += max(Left[i], Right[i]);
    }
    cout<<ans;
    
    return 0;
}


Measured memory_bytes: 7276
#include <iostream>

using namespace std;

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	int m2 = 0;
	int m1 = 0;
	int m3 = 0;
	if (a > b) {
		if (a > c) {
			m1 = a;
			m2 = b;
			m3 = c;
		}
		else {
			m1 = c;
			m2 = b;
			m3 = a;
		}
	}
	else {
		if (b > c) {
			m1 = b;
			m2 = a;
			m3 = c;
		}
		else {
			m1 = c;
			m2 = a;
			m3 = b;
		}
	}
	cout << m1 * 10 + m2 + m3 << endl;
	return 0;
}

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

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		var D = new Dictionary<long,int>();
		for(int i=0;i<N;i++){
			if(D.ContainsKey(A[i]) == false) D.Add(A[i],0);
			D[A[i]]++;
		}
		
		var L = D.Keys.ToList();
		L.Sort();
		L.Reverse();
		long h = 0;
		long w = 0;
		for(int i=0;i<L.Count;i++){
			if(D[L[i]] >= 2){
				h = L[i];
				D[L[i]] -= 2;
				break;
			}
		}
		//foreach(var kvp in D) Console.WriteLine(kvp);
		for(int i=0;i<L.Count;i++){
			if(D[L[i]] >= 2){
				w = L[i];
				D[L[i]] -= 2;
				break;
			}
		}
		//foreach(var kvp in D) Console.WriteLine(kvp);
		
		Console.WriteLine(w*h);
	}
	int N;
	long[] A;
	public Sol(){
		N = ri();
		A = rla();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 25312
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>

using namespace std;

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

#define PRINT(str) printf(#str "\n")
#define yOUT PRINT(Yes)
#define nOUT PRINT(No)
#define YOUT PRINT(YES)
#define NOUT PRINT(NO)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
    int n;
    cin >> n;
    vector<pair<string, int>> a(n);
    map<int, int> mp;
    REP(i, n){
        cin >> a[i].first >> a[i].second;
        mp[a[i].second] = i+1;
    }

    sort(all(a));
    
    int s = 0, cnt = 0;
    FOR(i, 1, n){
        cnt++;
        if(a[s].first != a[i].first){
            if(cnt > 1) reverse(a.begin() + s, a.begin() + s + cnt);
            s = i;
            cnt = 0;
        }
        else if(i == n-1){
            cnt++;
            if(cnt > 1) reverse(a.begin() + s, a.begin() + s + cnt);
        }
    }

    cout << endl;
    REP(i, n){
        cout << mp[a[i].second] << endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<vector>

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define all(x)  (x).begin(), (x).end()
#define MAX 100000
using namespace std;

int main(){
  int n, i; cin >> n >> i;
  cout << (n-i+1) << endl;
  return 0;
}

Measured memory_bytes: 256
n = int(input())
h = list(map(int,input().split()))
now = h[0]
cnt = 0
ans = 0
for i in range(1,n):
    if h[i]<=now:
        now = h[i]
        cnt+=1
    else:
        now = h[i]
        ans = max(ans,cnt)
        cnt = 0
ans = max(ans,cnt)
print(ans)

Measured memory_bytes: 14224
#include <bits/stdc++.h>
#define ll long long
#define MAX 100000
ll mod = pow(10,9) + 7;

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<char> > grid(n+1,vector<char>(m+1));
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++) cin >> grid[i][j];
    }

    ll dp[n+1][m+1];

    dp[1][1] = 1;

    for(int i=2; i<=n; i++){
        if(grid[i][1] == '.') dp[i][1] = dp[i-1][1];
        else dp[i][1] = 0;
    }

    for(int i=2; i<=m; i++){
        if(grid[1][i] == '.') dp[1][i] = dp[1][i-1];
        else dp[1][i] = 0;
    }

    for(int i=2; i<=n; i++){
        for(int j=2; j<=m; j++){
            if(grid[i][j] == '.') dp[i][j] = (dp[i-1][j]%mod + dp[i][j-1]%mod)%mod;
            else dp[i][j] = 0;
        }
    }

    cout << dp[n][m]%mod;

    return 0;
}


Measured memory_bytes: 9088
import sys
A=" ',-.?ABCDEFGHIJKLMNOPQRSTUVWXYZ"
B="101 000000 000011 10010001 010001 000001 100101 10011010 "\
  "0101 0001 110 01001 10011011 010000 0111 10011000 "\
  "0110 00100 10011001 10011110 00101 111 10011111 1000 "\
  "00110 00111 10011100 10011101 000010 10010010 10010011 10010000".split()
C="ABCDEFGHIJKLMNOPQRSTUVWXYZ .,-'?"
d1={}
for i in range(32):d1[A[i]]=B[i]
for s in sys.stdin:
  x=""
  for c in s[:-1]:x+=d1[c]
  x+="0"*(-len(x)%5)
  s=""
  for i in range(0,len(x),5):s+=C[int(x[i:i+5],2)]
  print s

Measured memory_bytes: 4236
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int a, b;
int main(){
	scanf("%d%d", &a, &b);
	if(a > 8 || b > 8) printf(":(\n");
	else printf("Yay!\n");
	return 0;
}

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

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

  int ans = 0;

  if (C >= B  || A >= D) {
    ans = 0;
  } else {
    if (A <= C) {
      if (B >= C && B <= D)
        ans = B - C;
      else
        ans = D - C;
    } else {
      if (D >= A && D <= B)
        ans = D - A;
      else
        ans = B - A;
    }
  }

  cout << ans << endl;

  return 0;
}


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    int N; string s;
    cin >> N >> s;
    vec bn(N+1, 0), wn(N+1, 0);
    rep(i, N){
        if(s[i] == '#'){
            bn[i+1] = bn[i]+1;
        }else{
            bn[i+1] = bn[i];
        }
        if(s[N-1-i] == '.'){
            wn[N-1-i] = wn[N-i]+1;
        }else{
            wn[N-1-i] = wn[N-i];
        }
    }
    ll res = INF;
    rep(i, N+1){
        res = min(res, (ll)bn[i]+wn[i]);
    }
    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 9240
#include<iostream>
#include<algorithm>
#include<list>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
#define chmin(a,b) (a>(b)?a=(b),1:0)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
typedef long int li;


int main(){
  string s,t; cin >>s >>t;
  int n=t.size(),m=s.size();
  int flag=0;
  vector<string> vec;
  auto check
    =[&](int a){
       rep(i,n){
         if(s[i+a]!=t[i] and s[i+a]!='?') return;
       }
       string str;
       rep(i,m) str.push_back((s[i]=='?')?'a':s[i]);
       rep(i,n) str[i+a]=t[i];
       vec.push_back(str);
       if(df){printf("match\n"); cout << str;}
     };
  
  for(int i=s.size()-t.size(); i>=0; i--){
    check(i);
  }
  if(df){
    for(auto x:vec) cout << x << "\n";
  }
  sort(vec.begin(),vec.end());
  
  if(vec.size()>0) cout << vec[0] << "\n";
  else cout << "UNRESTORABLE\n";
}


Measured memory_bytes: 256