akhauriyash/Code-Regression huggingface dataset:
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define endl '\n'
#define mem(i,j) memset(i,j,sizeof (i));
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define bit(s,i) (((s)>>(i))&1LL)
#define lowbit(x) ((x)&(-(x)))
#define siz(v) (long long)(v).size()
typedef int64_t ll;
typedef uint64_t ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const int MOD     = 1e9+7;
const int MAXN    = 2e5+9;
/*-----------------------------------------------------------------------------------------------------*/

signed main() {
	EmiliaMyWife

	int  n;
	cin >> n;
	cout << (n/2+n%2);

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define arep(i,x,n) for(int i=int(x);i<(int)(n);i++)
#define rep(i,n) for(long long i = 0;i < n;++i)
#define pi 3.141592653589793
#define eps 0.00000001
#define INF 1e9+7  
using ll = long long; 
using P=pair<int,int>;
using lP=pair<ll,ll>;
using fP=pair<double,double>;

vector<ll>ans;
int main(){
    int k;
    cin>>k;
    queue<ll>q;
    rep(i,9){
        q.push(i+1);
        ans.push_back(i+1);
    }
    while(ans.size()<k){
        ll now=q.front();q.pop();
        int r=now%10;
        if(r>0){
            ans.push_back(now*10+r-1);
            q.push(now*10+r-1);
        }
        ans.push_back(now*10+r);
        q.push(now*10+r);
        if(r<9){
            ans.push_back(now*10+r+1);
            q.push(now*10+r+1);
        }
    }
    cout<<ans[k-1]<<endl;
    return 0;
}

Measured memory_bytes: 1620
//Yattazo! Watashiha-Yosen-tsuukashita! It's 460points/600points! OHO!!!!!
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int x[21000][256],n,m,y[64000],z[64000],d,minx;
int main(){
	while(true){
		minx=2000000000;
		for(int i=0;i<21000;i++){for(int j=0;j<256;j++){x[i][j]=2000000000;}}
		cin>>n>>m;if(!n){break;}
		for(int i=0;i<m;i++){cin>>y[i];}
		for(int i=1;i<=n;i++){cin>>z[i];}
		x[0][128]=0;
		for(int i=1;i<=n;i++){
			for(int j=0;j<256;j++){
				if(x[i-1][j]<1000000000){
					for(int k=0;k<m;k++){
						d=y[k]+j;
						if(d<0){d=0;}
						if(d>255){d=255;}
						x[i][d]=min(x[i][d],x[i-1][j]+(int)pow(1.0*(z[i]-d),2));
					}
				}
			}
		}
		for(int i=0;i<256;i++){minx=min(minx,x[n][i]);}
		cout<<minx<<endl;
	}
}

Measured memory_bytes: 22244
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] l = sc.nextLine().split(" ");
        int N = Integer.parseInt(l[0]);
        int[] R = new int[N];
        boolean[] inputed = new boolean[N];
        for (int i = 0; i < N; i++) {
            R[i] = 0;
        }
        if (N != 1) {
            R[0] = 1;
        }
        int M = Integer.parseInt(l[1]);
        for (int i = 0; i < M; i++) {
            String[] lsc = sc.nextLine().split(" ");
            int S = Integer.parseInt(lsc[0]) - 1;
            int C = Integer.parseInt(lsc[1]);
            // 重複条件ちぇっく
            if (inputed[S] && R[S] != C) {
                System.out.println(-1);
                return;
            }
            R[S] = C;
            inputed[S] = true;
        }
        if (N != 1 && inputed[0] == true && R[0] == 0) {
            System.out.println(-1);
            return;
        }
        for (int r : R) {
            System.out.print(r);
        }
        System.out.print("\n");
    }
}


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

int main(){
    string S;
    cin >> S;
    int ned = 700;
    if(S[0] == 'o') ned += 100;
    if(S[1] == 'o') ned += 100;
    if(S[2] == 'o') ned += 100;
    cout << ned << endl;
    return 0;
}

Measured memory_bytes: 256
from math import gcd # Python3.6以降
# --------------------------------------------------------------

# n以下の素数列挙: O-nlogn
def primes(n):
    prs = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            prs.append(i)
    return prs

n    = int(input())
lis  = list(map(int,input().split()))
A    = 10**6
nlis = [0]*A
flg_pairwise = True

for i in range(n):
    nlis[lis[i]-1] += 1

for i in primes(A):
    cnt = 0
    for j in range(i-1,A,i):
        cnt += nlis[j]
    if cnt > 1:
        flg_pairwise = False
        break

if flg_pairwise:
    print('pairwise coprime')
else:
    for i in range(n-1):
        if i==0:
            tmp = gcd(lis[i],lis[i+1])
        else:
            tmp = gcd(tmp,lis[i+1])

    if tmp==1:
        print('setwise coprime')
    else:
        print('not coprime')

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

int main(){
  string S;
  cin >> S;
  
  char f = '0';
  int sb = 0;
  int sw = 0;
  for(int i =0;i < S.size();i++){
    if(f == S.at(i)) sb++;
    else sw++;
    f = f == '0' ? '1' : '0' ;
  }
  
  cout << min(sb,sw) ;
  
  return 0; 
}

Measured memory_bytes: 512
using System;
using System.Collections;
using System.Collections.Generic;

namespace ABC126 {
  class ProblemC {
    static void Main(string[] args) {
      int[] input = Input.nums;
      double pow = 0;
      double ans = 0;
      for (int i = 1; i <= input[0]; i++) {
        if (i >= input[1]) {
          pow = 0;
        } else {
          pow = Math.Ceiling(Math.Log((double)input[1] / i, 2));
        }
        ans += 1.0 / (input[0] * 1 << (int)pow);
      }
      System.Console.WriteLine(ans);
    }
    static int foo(int n) {
      switch (n) {
        case 1:
          return 4;
        case 2:
          return 3;
        case 3:
        case 4:
          return 2;
        case 5:
        case 6:
        case 7:
        case 8:
        case 9:
          return 1;
        default:
          return 0;
      }
    }
  }
  public class Input {
    public static string str => System.Console.ReadLine();
    public static string[] strs => str.Split(' ');
    public static char[] charArr => str.ToCharArray();
    public static int num => int.Parse(str);
    public static int[] nums => Array.ConvertAll(strs, int.Parse);
    public static long numL => long.Parse(str);
    public static long[] numLs => Array.ConvertAll(strs, long.Parse);
  }
}

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

int main(){
  int n;
  long long t, a;
  cin >> n >> t >> a;

  t = t * 1000;
  int ans = -1;
  a *= 1000;
  int h;
  long long tmp = INT_MAX;
  for(int i = 0;i < n;i++){
    cin >> h;
    long long tt = abs(a-(t-h*6));
    if(tmp > tt){
      tmp = tt;
      ans = i+1;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
/*{{{*/
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define mset(x,c) memset(x, c, sizeof(x))
#define mem0(x) mset(x,0)
#define mem1(x) mset(x,-1)
#define memc(x,y) memcpy(x, y, sizeof(x));
#define P(a,n) FOR(_,0,n) _W(a),printf("%c", " \n"[_==n-1])
#define print(a,n) cout << #a << " = ";FOR(_,0,n) _W(a),printf("%c", " \n"[_==n-1])
using namespace std;

template<class T> void _R(T &x) { cin >> x; }
void _R(signed &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const signed &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.fi); putchar(' '); _W(x.se);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef LOCAL
 #define debug(...) {printf(" [" #__VA_ARGS__ "]: ");W(__VA_ARGS__);}
#else
 #define debug(...)
#endif

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
/*}}}*/
//#define int long long

const int P = 1e9+7;

signed main() {
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int n;
	R(n);
	vector<ll> a(n+1);
	ll ans = 0;
	FOR(i,1,n+1) {
		R(a[i]);
		ans = (ans+a[i]*a[i-1])%P;
		a[i] = (a[i]+a[i-1])%P;
	}
	W(ans);
}


Measured memory_bytes: 4864
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

	    Scanner sc = new Scanner(System.in);
	    int A11 = sc.nextInt();
	    int A12 = sc.nextInt();
	    int A13 = sc.nextInt();
	    int A21 = sc.nextInt();
	    int A22 = sc.nextInt();
	    int A23 = sc.nextInt();
	    int A31 = sc.nextInt();
	    int A32 = sc.nextInt();
	    int A33 = sc.nextInt();

	    HashMap<Integer, Integer> map = new HashMap<>();
	    map.put(A11, 0);
	    map.put(A12, 0);
	    map.put(A13, 0);
	    map.put(A21, 0);
	    map.put(A22, 0);
	    map.put(A23, 0);
	    map.put(A31, 0);
	    map.put(A32, 0);
	    map.put(A33, 0);


	    int N = sc.nextInt();
	    for(int i = 0; i < N; i++) {
	    	int b = sc.nextInt();
	    	map.get(b);
	    	map.put(b, 1);
	    }


	    boolean flg = false;
	    // 縦
	    if(map.get(A11)==1 && map.get(A21)==1 && map.get(A31)==1) {flg = true;}
	    if(map.get(A12)==1 && map.get(A22)==1 && map.get(A32)==1) {flg = true;}
	    if(map.get(A13)==1 && map.get(A23)==1 && map.get(A33)==1) {flg = true;}

	    // 横
	    if(map.get(A11)==1 && map.get(A12)==1 && map.get(A13)==1) {flg = true;}
	    if(map.get(A21)==1 && map.get(A22)==1 && map.get(A23)==1) {flg = true;}
	    if(map.get(A31)==1 && map.get(A32)==1 && map.get(A33)==1) {flg = true;}

	    // 斜め
	    if(map.get(A11)==1 && map.get(A22)==1 && map.get(A33)==1) {flg = true;}
	    if(map.get(A31)==1 && map.get(A22)==1 && map.get(A13)==1) {flg = true;}

	    if (flg) {
	    	System.out.println("Yes");
	    } else {
	    	System.out.println("No");
	    }
	    
	}
}

Measured memory_bytes: 22868
from heapq import *
from collections import defaultdict
N, M = map(int, input().split())
data = defaultdict(list)
for _ in range(N):
    A, B = map(int, input().split())
    data[A].append(-B)

res = 0
temp = []
for i in range(1,M+1):
    for a in data[i]:
        heappush(temp,a)
    if temp:
        res -= heappop(temp)
print(res)


Measured memory_bytes: 96732
#include <iostream>

using namespace std;

int main()
{
	int r, g, b, total;
	cin >> r >> g >> b;
	total = r * 100 + g * 10 + b;
	if (total % 4 == 0) cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 256
H, W, N = [int(_) for _ in input().split()]
R, C = [int(_) for _ in input().split()]
S = input()
T = input()

imin = 1
imax = H
jmin = 1
jmax = W

for n in range(N - 1, -1, -1):
    s = S[n]
    t = T[n]
    if t == 'U':
        imax = min(imax + 1, H)
    elif t == 'D':
        imin = max(imin - 1, 1)
    elif t == 'L':
        jmax = min(jmax + 1, W)
    elif t == 'R':
        jmin = max(jmin - 1, 1)
    if s == 'U':
        imin += 1
    elif s == 'D':
        imax -= 1
    elif s == 'L':
        jmin += 1
    elif s == 'R':
        jmax -= 1
    if imax < imin or jmax < jmin:
        print('NO')
        exit()
if imin <= R <= imax and jmin <= C <= jmax:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 3784
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		PriorityQueue<Bridge> queue = new PriorityQueue<>();
		for (int i = 0; i < m; i++) {
		    queue.add(new Bridge(sc.nextInt(), sc.nextInt()));
		}
		int count = 0;
		while (queue.size() > 0) {
		    count++;
		    Bridge b = queue.poll();
		    while (queue.size() > 0 && b.right > queue.peek().left) {
		        queue.poll();
		    }
		}
		System.out.println(count);
    }
    
    static class Bridge implements Comparable<Bridge> {
        int left;
        int right;
        
        public Bridge (int left, int right) {
            this.left = left;
            this.right = right;
        }
        
        public int compareTo(Bridge another) {
            if (right == another.right) {
                return left - another.left;
            } else {
                return right - another.right;
            }
        }
    }
}



Measured memory_bytes: 88332
N=list(input())
K=int(input())

OK=[[0 for k in range(5)]for i in range(len(N))]
OK[0][0]=1
OK[0][1]=int(N[0])-1
D=1
#print(OK)
for i in range(1,len(N)):
    OK[i][0]=OK[i-1][0]
    OK[i][1]+=OK[i-1][0]*9+OK[i-1][1]
    OK[i][2]+=OK[i-1][1]*9+OK[i-1][2]
    OK[i][3]+=OK[i-1][2]*9+OK[i-1][3]
    if D<=K and int(N[i])!=0:
        OK[i][D]+=1
        OK[i][D+1]+=int(N[i])-1
        D+=1
if D==K:
    print(OK[-1][K]+1)
else:
    print(OK[-1][K])


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        String a;
        Scanner sc = new Scanner(System.in);
        a = sc.next();
        //a = "ABC" ? System.out.println("ARC") : System.out.println("ABC");
        System.out.println(a.equals("ABC") ? "ARC" : "ABC");
    }
}


Measured memory_bytes: 35424
import java.io.*;
import java.util.*;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Scanner sc = new Scanner(System.in);
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    int maxn;
    long[] frac,inv;
    long mod = 1000000000+7;
    public static void main(String[] args) throws IOException {
        Main main = new Main();
//        main.solve();
        System.out.println(main.solve());
    }
    long solve() throws IOException {
        int n = sc.nextInt();
        return (n+1)/2;
    }
}



Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (const string& e_) { return "\"" + e_ + "\""; }
string to_string (char e_) { return "\'" + string(1, e_) + "\'"; }
string to_string (bool e_) { return e_ ? "true" : "false"; }
template <typename T> string to_string (T e_) {
	string s_ = "[ ";
	for (const auto& x_ : e_) s_ += to_string(x_) + " ";
	return s_ + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e_) {
	return "(" + to_string(e_.first) + ", " + to_string(e_.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */
int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	ll a, b, c, d;
	cin >> a >> b >> c >> d;

	ll g = (c/__gcd(c,d))*d;
	ll fc = b/c - (a-1)/c;
	ll fd = b/d - (a-1)/d;
	ll fg = b/g - (a-1)/g;

	ll ans = b - a + 1 - fc - fd + fg;
	cout << ans;
}

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

d = [0]*(n)

for i in range(n):
    if i == 0:
        d[i] = abs((abs(a[0])+abs(a[1]-a[0]))-abs(a[1]))
    elif i<n-1:
        d[i] = abs((abs(a[i+1]-a[i])+abs(a[i]-a[i-1]))-abs(a[i+1]-a[i-1]))
    else:
        d[i] = abs((abs(a[n-1]-a[n-2])+abs(a[n-1]))-abs(a[n-2]))

sum = 0
for i in range(n):
    if i == 0:
        sum += abs(a[i])
    else:
        sum += abs(a[i]-a[i-1])
sum += abs(a[n-1])

for i in range(n):
    print(sum-d[i])

Measured memory_bytes: 14176
#include <bits/stdc++.h>
#include <stdlib.h>
#include <cmath>
using namespace std;
typedef long long ll;
ll mod=1000000007;
ll BIG=1e9;

ll d[301][301];
bool use[301][301];
int main(){
    int N; cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++) cin>>d[i][j];
    }

    for(int i=0;i<N;i++){
        for(int j=i;j<N;j++) use[i][j]=true;
    }

    bool able=true;

    for(int k=0;k<N;k++){
        for(int i=0;i<N;i++){
            for(int j=i;j<N;j++){
                if(d[i][j]>d[i][k]+d[k][j]) able=false;
                if(d[i][j]==d[i][k]+d[k][j] && k!=i && k!=j) use[i][j]=false;
            }
        }
    }

    ll ans=0;
    if(!able) cout<<-1<<endl;

    else{
        for(int i=0;i<N;i++){
            for(int j=i;j<N;j++) if(use[i][j]) ans+=d[i][j];
        }
        cout<<ans<<endl;
    }

}

Measured memory_bytes: 1024
//author : raghav_0901

#include <bits/stdc++.h>
using namespace std;

void _main();
signed main(void){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1,i=0;
//cin>>t;
while (t--){
//cout<<"Case #"<<(++i)<<": ";

	_main();

}return 0;}

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


void _main(){
    int n;cin>>n;
    map<string,int> mp;
    for(int i=0;i<n;i++)
    {
        string s;cin>>s;
        mp[s]=1;
    }
    cout<<mp.size()<<endl;
    return;
}


Measured memory_bytes: 19280
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<iomanip>
#define pi 3.14159265358979323846
#define ll long long
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
int main(){
  int n;
  cin >> n;
  cout << n + n * n + n * n * n << "\n";
}

Measured memory_bytes: 3604
#include<iostream>
#include<algorithm>

using namespace std;

const int INF = 1e9 + 1;
int N, K;

int main(){
    cin >> N;
    cin >> K;
    int h[N];

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

    sort(h, h + N);

    int ans = INF;


    for(int i = 0; i <= N - K; i++){
        if((h[i+K-1] - h[i]) < ans){
            ans = h[i+K-1] - h[i];
        }
    }

    cout << ans << endl;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define pb push_back
#define pint pair<int,int>
using namespace std;

int ans[3000][3000];
string s1,s2;
int make(int x, int y){
	if(x>=s1.length() || y>=s2.length())	return 0;
	if(ans[x][y]!=-1)	return ans[x][y];
	ans[x][y]=max(make(x+1,y),make(x,y+1));
	if(s1[x]==s2[y])	ans[x][y]=max(ans[x][y],make(x+1,y+1)+1);
	return ans[x][y];
}

void print(int x, int y){
	if(x>=s1.length() || y>=s2.length())	return;
	if(ans[x][y]==make(x+1,y))	return print(x+1,y);
	if(ans[x][y]==make(x,y+1))	return print(x,y+1);
	if(ans[x][y]==make(x+1,y+1)+1){
		cout<<s1[x];	return print(x+1,y+1);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>s1>>s2;
	int i,j;
	for(i=0;i<3000;i++){
		for(j=0;j<3000;j++){
			ans[i][j]=-1;
		}
	}
	make(0,0);
	print(0,0);
	return 0;
}

Measured memory_bytes: 35840
K, N = map(int, input().split())
A = list(map(int, input().split()))
B = [0 for i in range(N)]

for i in range(N-1):
	B[i] = A[i+1] - A[i]

B[N-1] = K - (A[N-1] - A[0])
B_max = max(B)
print(K - B_max)


Measured memory_bytes: 26420
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i< (n); i++)
using ll = long long;
using namespace std;
ll gcd(ll a, ll b) {
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

int main(){
	int N;
	cin >> N;
	int h[N];
	int tot = 0;
	rep(i,N) {
		int x;
		cin >> x;
		h[i] = -x;
		tot += x;
	}

	int ans = 0;
	while (tot > 0) {
		int l = 0;
		while (l < N) {
			if (h[l] < 0) {ans++; break;}
			l++;
		}
		int r = l;
		while (r < N) {
			if (h[r] < 0) {tot--; h[r]++;}
			else break;
			r++;
		}
	}
	cout << abs(ans) << endl;
return 0;
}


Measured memory_bytes: 3628
#include <iostream>

using namespace std;
int main(){
    int N, a[110]={},b[110]={}, c[110]={};
    cin >> N;
    for(int i=0; i<N; ++i){
        cin >> b[i];
        c[i] = b[i];
    }
    bool t=1;
    for(int i=N; i>0; --i){
        for(int j=i; j>0; --j){
            if(j==c[j-1]){
                a[i-1]=j;
                // cout << a[i-1] << endl;        
                for(int k=j; k<=N; ++k){
                    c[k-1] = c[k];    
                }
                t=1;
                break;       
            }
            else t=0;    
        }    
    }
    if(t==1){
        for(int i=0; i<N; ++i){
            cout << a[i] << endl;        
        }
    }
    else cout << -1 << endl;

}


Measured memory_bytes: 256
n, m = map(int, input().split())
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p, q = q, p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
par = [-1 for i in range(n + m)]
for i in range(n):
    l = list(map(int, input().split()))
    for j in l[1:]:
        unite(i, n + j - 1)
for i in range(n - 1):
    if not same(i, i + 1):
        exit(print("NO"))
print("YES")

Measured memory_bytes: 15764
#include<bits/stdc++.h>
using namespace   std;
#define ff        first
#define ss        second
#define ll        long long
#define int       long long
#define inf       ((ll)1e18)
#define double    long double
#define ull       unsigned long long
#define mod       1000000007
#define vi        vector<ll>
#define extreme   inline
#define ppi       pair<ll,pair<ll,ll>>
#define pb        push_back
#define mp        make_pair
#define str       string
#define pi        2*acos(0.0)
#define pr(a,x,n) for(int i=x;i<n;i++){cout<<a[i]<<" ";}
#define p(a)      cout<<a;
#define sp(x,y)   fixed<<setprecision(y)<<x
#define w(x)      ll x; cin>>x; while(x--)
#define all(v)    v.begin(), v.end()
#define test      cout<<"THIS_AND_THIS"<<endl;
void kehsihba(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	/*#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif*/
}
void solve(){
	char a;
	cin>>a;
	if(a>='a' and a<='z'){cout<<"a";}
	else{cout<<"A";}
}
int32_t main(){
	kehsihba();
	ll t=1;
	//cin>>t;
	while(t--){
		solve();
	}
}

Measured memory_bytes: 3644
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<numeric>
#include<math.h>
#include<deque>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    deque<ll> deq;
    rep(i, n) {
        if ( i % 2 == 0 ) deq.push_back(a[i]);
        else              deq.push_front(a[i]);
    }
    rep(i, n) {
        if ( i != 0 ) cout << " ";
        if ( n % 2 == 0 ) {
            cout << deq.front();
            deq.pop_front();
        }
        else {
            cout << deq.back();
            deq.pop_back();
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 5376
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int lim = 20;
const vector<int> bx = { 0, 4, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3 };
const vector<int> by = { 2, 2, 1, 2, 3, 0, 1, 2, 3, 4, 1, 2, 3 };
struct state {
	vector<int> px, py;
	int cost, rem, last1, last2;
};
bool operator<(const state& s1, const state& s2) {
	return s1.cost + s1.rem != s2.cost + s2.rem ? s1.cost + s1.rem > s2.cost + s2.rem : s1.rem > s2.rem;
}
int eval(vector<int> px, vector<int> py) {
	int ret = 0;
	for (int i = 2; i < 13; ++i) {
		ret += abs(px[i] - bx[i]) + abs(py[i] - by[i]);
	}
	return ret;
}
int main() {
	int x;
	while (cin >> x, x != -1) {
		vector<int> vx(13), vy(13);
		int zc = 0;
		vx[x == 0 ? zc : x + 1] = bx[0];
		vy[x == 0 ? zc : x + 1] = by[0];
		if (x == 0) ++zc;
		for (int i = 1; i < 13; ++i) {
			cin >> x;
			vx[x == 0 ? zc : x + 1] = bx[i == 12 ? 1 : i + 1];
			vy[x == 0 ? zc : x + 1] = by[i == 12 ? 1 : i + 1];
			if (x == 0) ++zc;
		}
		priority_queue<state> que;
		que.push(state{ vx, vy, 0, eval(vx, vy), -1, -1 });
		int ans = -1;
		while (!que.empty()) {
			state u = que.top();
			que.pop();
			if (u.rem == 0) {
				ans = u.cost;
				break;
			}
			for (int i = 0; i < 2; ++i) {
				for (int j = 2; j < 13; ++j) {
					if (i == u.last1 && j == u.last2) continue;
					if (abs(u.px[i] - u.px[j]) + abs(u.py[i] - u.py[j]) == 1) {
						swap(u.px[i], u.px[j]);
						swap(u.py[i], u.py[j]);
						int ev = eval(u.px, u.py);
						if (u.cost + ev + 1 <= lim) {
							que.push(state{ u.px, u.py, u.cost + 1, eval(u.px, u.py), i, j });
						}
						swap(u.px[i], u.px[j]);
						swap(u.py[i], u.py[j]);
					}
				}
			}
		}
		if (ans != -1) cout << ans << endl;
		else cout << "NA" << endl;
	}
	return 0;
}


Measured memory_bytes: 3948
using static System.Math;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System;

namespace AtCoder
{
    class Program
    {
        private static long mod = 1000000007;
        static void Main(string[] args)
        {
            //var k = int.Parse(ReadLine());
            //var line = ReadLine().Split(' ').Select(value => long.Parse(value)).ToArray();

            var n = ReadLine();
            var sum = 0;
            foreach(var c in n)
            {
                sum += int.Parse(c.ToString());
            }

            WriteLine(sum % 9 == 0 ? "Yes" : "No");
        }
    }
}

Measured memory_bytes: 32608
#include <iostream>

int getIndex(int age)
{
	if (age<10) return 0;
	else if (age<20) return 1;
	else if (age<30) return 2;
	else if (age<40) return 3;
	else if (age<50) return 4;
	else if (age<60) return 5;
	else return 6;
}

int main()
{
	int n;
	while (true) {
		std::cin >> n;
		if (n == 0) break;
		int a[7] = {0,0,0,0,0,0,0};
		for (int i=0; i<n; i++) {
			int age;
			std::cin >> age;
			a[getIndex(age)]++;
		}
		for (int i=0; i<7; i++) std::cout << a[i] << std::endl;
	}
	return 0;
}



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

int main() {
	vector<int> a(5);
	for (int i = 0; i < 5; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < 5; i++) {
		if (a[i] == 0) {
			cout << i + 1 << "\n";
			return 0;
		}
	}
}


Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <functional>
#include <array>

using namespace std;

using P = pair<int, int>;

int main(){
    int N, M;
    while(true){
        cin >> N >> M;
        if(N == 0 && M == 0) break;

        vector<P> vec(N);
        for(int i = 0; i < N; ++i){
            cin >> vec[i].second >> vec[i].first;
        }

        sort(vec.begin(), vec.end());
        for(int i = N-1; i >= 0; --i){
            if(M >= vec[i].second){
                M -= vec[i].second;
                vec[i].second = 0;
            } else {
                vec[i].second -= M;
                M = 0;
            }
        }

        int64_t ans = 0;
        for(int i = 0; i < N; ++i){
            ans += vec[i].first * vec[i].second;
        }
        cout << ans << endl;
    }
}


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

int main() {
    int n;
    int a,b;
    double c;
    cin >> n;

    a = n/2;
    b = n%2; 

    if (b==0)
    {
        c=a/double(n);
    }
    else
    {
        c=(a+1)/double(n);
    }
    cout << c << endl;
    


    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

ll N, n,m , M, K,a;

vector<ll> v,w;
int main(){
    cin >> N >> M;
    if(500*N < M) cout << "No";
    else cout<< "Yes";
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>

#define FOR_LT(i, beg, end) for (int i = (int)(beg); i < (int)(end); i++)
#define FOR_LE(i, beg, end) for (int i = (int)(beg); i <= (int)(end); i++)
#define FOR_DW(i, beg, end) for (int i = (int)(beg); (int)(end) <= i; i--)
#define REP(n)              for (int repeat_index = 0; repeat_index < (int)n; repeat_index++)


using namespace std;

int64_t gcd(int64_t a, int64_t b) {
	/*static unordered_map<int64_t, int64_t> memo;
	int64_t idx = a * 400 + b;
	auto it = memo.find(idx);
	if (it != memo.end()) {
		return it->second;
	}*/

	if (a < b) swap(a, b);
	if (a % b == 0) return b;

	int64_t ans = gcd(b, a % b);
	//memo[idx] = ans;
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int n; cin >> n;

	int64_t ans = 0;
	FOR_LE(i, 1, n) {
		FOR_LE(j, 1, n) {
			FOR_LE(k, 1, n) {
				ans += gcd(gcd(i, j), k);
			}
		}
	}
	cout << ans << endl;

	return 0;
}

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

int main(){
  int N ,A, B;
  cin >> N >> A >> B;
  int cnt = 0;
  for (int i = 0; i < N; i++) {
    int t;
    cin >> t;
    if(t < A || B <= t) cnt++;
  }
  cout << cnt << endl;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reprv(i, n) for (int i = n - 1; i >= 0; i--)
#define ll long long
using namespace std;

struct edge {
    vector<int> to;
};

ll height[100001] = {};
bool isgood[100001] = {};
ll max[100001] = {};
edge e[100001] = {};

int main() {
    int n, m;

    cin >> n >> m;

    isgood[0] = false;
    for(int i = 1; i < n + 1 ; i++) {
        cin >> height[i];
        isgood[i] = true;
    }


    rep(j,m) {
        int from,to;
        cin >> from >> to;
        e[from].to.push_back(to);
        e[to].to.push_back(from);
    }

    for(int i = 1; i < n + 1 ; i++) {
        if (isgood[i] == false) continue;
        rep(j, e[i].to.size()) {
            int checking_idx = e[i].to[j];
            if (height[i] > height[checking_idx]) {
                isgood[checking_idx] = false;
            } else {
                isgood[i] = false;
                break; // もう可能性がないので...
            }
        }
    }


    int total = 0;
    rep(i,n + 1) {
        if(isgood[i] == true) {
            total++;
        }
    }

    cout << total << endl;


    return 0;
}


Measured memory_bytes: 9640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;


int main(){
    ll n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    bool f = 1;

    ll g = __gcd(m,n);
    ll l = m * n / g;

    map<ll,char> good;

    rep(i, n){
        good[(l/n)*i] = s[i];
    }
    rep(i, m) {
        if(good[(l/m)*i] == 0) continue;
        f &= (good[(l/m)*i] == t[i]);
    }

    if (f) cout << l << endl;
    else cout << -1 << endl;

    return 0;
}


Measured memory_bytes: 14116
n, x, m = map(int, input().split())
A = [0, x]
d = {x:1}
for i in range(2, n+1):
    A.append(A[i-1]**2 % m)
    if A[i] in d:
        j = d[A[i]]
        q, r = divmod(n-j+1, i-j)
        print(sum(A[:j]) + q*sum(A[j:i]) + sum(A[j:j+r]))
        break
    else:
        d[A[i]] = i
else:
    print(sum(A))

Measured memory_bytes: 15544
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 922337203685477580LL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}



//head



int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, x, t;
	cin >> n >> x >> t;
	int a, b;
	a = (n+x-1)/x;
	b = t;
	ll c = a*b;

	cout << c << endl;
}

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

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

    int l = s.size();
    char last = s[l-1];
    if (last == 's'){
        cout << s + "es" << endl;
    } else {
        cout << s + "s" << endl;
    }

}

Measured memory_bytes: 3600
using System;
using System.Collections;
using System.Linq;

public class Program
{
    private int N;
    private int[] A;
    private const int Max = 100000;

    public void Solve()
    {
        var sc = new Scanner();
        int N = sc.NextInt();
        A = sc.IntArray();
        int sum = A.Sum();
        var dp = new bool[Max];
        dp[0] = true;
        foreach (var i in A)
        {
            var tmp = new bool[Max];
            for (int j = 0; j < Max; j++)
            {
                if (dp[j])
                {
                    int p = j + i;
                    int m = Math.Abs(j - i);

                    if (p < Max)
                    {
                        tmp[p] = true;
                    }

                    if (m < Max)
                    {
                        tmp[m] = true;
                    }
                }
            }

            dp = tmp;
        }

        for (int i = 0; i < Max; i++)
        {
            if (dp[i])
            {
                // ΣQ - ΣP = i

                Console.WriteLine((sum + i) / 2);
                return;
            }
        }
    }

    public static void Main(string[] args)
    {
        new Program().Solve();
    }
}

class Scanner
{
    public Scanner()
    {
        _pos = 0;
        _line = new string[0];
    }

    const char Separator = ' ';
    private int _pos;
    private string[] _line;

    #region スペース区切りで取得

    public string Next()
    {
        if (_pos >= _line.Length)
        {
            _line = Console.ReadLine().Split(Separator);
            _pos = 0;
        }

        return _line[_pos++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    #endregion

    #region 型変換

    private int[] ToIntArray(string[] array)
    {
        var result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = int.Parse(array[i]);
        }

        return result;
    }

    private long[] ToLongArray(string[] array)
    {
        var result = new long[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = long.Parse(array[i]);
        }

        return result;
    }

    private double[] ToDoubleArray(string[] array)
    {
        var result = new double[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = double.Parse(array[i]);
        }

        return result;
    }

    #endregion

    #region 配列取得

    public string[] Array()
    {
        if (_pos >= _line.Length)
            _line = Console.ReadLine().Split(Separator);

        _pos = _line.Length;
        return _line;
    }

    public int[] IntArray()
    {
        return ToIntArray(Array());
    }

    public long[] LongArray()
    {
        return ToLongArray(Array());
    }

    public double[] DoubleArray()
    {
        return ToDoubleArray(Array());
    }

    #endregion
}

Measured memory_bytes: 30280
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define F first
#define S second
#define PII pair<LL, LL>
typedef long long LL;

using namespace std;

string s;

int main() {
  //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '9')
      s[i] = '1';
    else
      s[i] = '9';
  }
  cout << s;
  return 0;
}


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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define l_l pair<ll, ll>
#define vll vector<ll>
#define mll map<ll, ll>

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

ll dp[110][100005];

int main() {
  ll N, W;
  scanf("%lld %lld", &N, &W);

  fill(dp[0], dp[105], -1);
  dp[0][W] = 0;

  vll w_list;
  vll v_list;

  for (ll i = 0; i < N; i++) {
    ll w, v;
    scanf("%lld %lld", &w, &v);

    w_list.emplace_back(w);
    v_list.emplace_back(v);
  }

  for (ll i = 0; i < N; i++) {
    ll w = w_list[i];
    ll v = v_list[i];

    for (ll rest = 0; rest <= W; rest++) {
      if (dp[i][rest] == -1) continue;

      dp[i + 1][rest] = max(dp[i + 1][rest], dp[i][rest]);

      if (rest >= w) {
        dp[i + 1][rest - w] = max(dp[i + 1][rest - w], dp[i][rest] + v);
      }
    }
  }

  ll ans = 0;
  for (ll i = 0; i <= W; i++) {
    ll a = dp[N][i];
    if (a == -1) continue;

    ans = max(ans, a);
  }
  cout << (ans) << endl;
}


Measured memory_bytes: 85728
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define loop(i, a, b) for(li i=a; i<=b; i++)
#define stuff ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long li;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<li, li> lii;
typedef vector<int> vi;
typedef vector<li> vli;
typedef vector<ii> vii;
typedef vector<lii> vlii;
li mod = 1e9+7;
li expo(li base, li exponent)
{
	li ans=1;
	while(exponent)
	{
		if(exponent&1) ans = (ans*base)%mod;
		base = (base*base)%mod;
		exponent >>= 1;
	}
	return ans;
}
li gcd(li x, li y)
{
	if(y==0) return x;
	return gcd(y, x%y);
}


typedef tree<li, null_type, less<li>,
rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const li N = 2001;
li dp[N][N];
li n;
vector<lii> ar;
li calc(li i, li j)
{
	li ind = i+j;
	if(ind==n) return 0;
	if(dp[i][j]!=-1) return dp[i][j];
	li pos = ar[ind].se, val = ar[ind].fi;
	// cout << val*(abs(pos-i-1)) << endl;
	li ans = max(val*(abs(pos-i-1))+calc(i+1, j), val*(abs(pos-(n-j)))+calc(i, j+1));
	return dp[i][j] = ans;
}
int main()
{
	stuff;
	// #ifndef ONLINE_JUDGE 
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	// freopen("error.txt", "w", stderr);
	// #endif

	// memset(dp, -1, sizeof(dp));
	// li n;
	cin >> n; 
	ar.resize(n);
	// vector<lii> ar(n);
	loop(i, 0, n-1)
	{
		cin >> ar[i].fi;
		ar[i].se = i+1;
	}
	// 0 
	sort(ar.begin(), ar.end(), greater<lii>());
	for(int i=0; i<=n; i++)
	{
		// cout << i << endl;
		for(int j=0; i+j<=n; j++)
		{
			if(i==0 && j==0) continue;
			int ind = (i+j-1);
			li pos = ar[ind].se, val = ar[ind].fi;
			li l = (i-1>=0 ? dp[i-1][j]+val*(abs(pos-i)) : 0);
			li r = (j-1>=0 ? dp[i][j-1]+val*(abs(pos-(n-j+1))) : 0);
			// cout << "l:" << l << " r:" << r << " i" << i << " " << j <<endl;
			dp[i][j] = max(l, r);
		}
	}
	li ans=0;
	for(li i=0; i<=n; i++)
	{
		ans = max(ans, dp[i][n-i]);
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 26428
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < int(n); i++)
#define rep1(i,n) for (int i = 1; i <= int(n); i++)
#define repR(i,n) for (int i = int(n)-1; i >= 0; i--)
#define rep1R(i,n) for (int i = int(n); i >= 1; i--)
#define loop(i,a,B) for (int i = a; i B; i++)
#define loopR(i,a,B) for (int i = a; i B; i--)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#ifdef LOCAL
#define dump(...) cerr << "[" << __LINE__ << ":" << __FUNCTION__ << "] ", my_dmp(#__VA_ARGS__, __VA_ARGS__)
void my_dmp(const char*) { cerr << endl; }
template <class T, class... U> void my_dmp(const char *s, T const& x, U const& ...y) { const char *o = "({[", *e = "]})"; for (int i = 0; *s != '\0'; cerr << *s++) { if (count(o,o+3,*s)) i++; if (count(e,e+3,*s)) i--; if (!i && *s == ',') break; } cerr << " = " << x; if (*s == ',') cerr << ", ", s++; my_dmp(s, y...); }
#else
#define dump(...)
#endif
using ll = long long;
using ld = long double;
#define int ll
#define double ld
template <class T> using pque_max = priority_queue<T>;
template <class T> using pque_min = priority_queue<T, vector<T>, greater<T> >;
template <class T, class = typename T::iterator, class = typename enable_if<!is_same<T, string>::value>::type>
ostream& operator<<(ostream& os, T const& v) { os << "{"; for (auto const& x : v) os << " " << x; return os << " }"; }
template <class T> istream& operator>>(istream& is, vector<T>& v) { for (auto& x : v) is >> x; return is; }
template <class T, class S> ostream& operator<<(ostream& os, pair<T,S> const& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template <class T, class S> istream& operator>>(istream& is, pair<T,S>& p) { return is >> p.first >> p.second; }
struct my_Init { my_Init() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } my_init;

template <class T, size_t d, class = typename enable_if<(d == 0)>::type> constexpr auto make_v(T const& x = {}) { return x; }
template <class T, size_t d, class... U, class = typename enable_if<(d > 0)>::type> constexpr auto make_v(size_t n, U... x) { auto val = make_v<T,d-1>(x...); return vector<decltype(val)>(n, move(val)); }
template <class T> void quit(T const& x) { cout << x << endl; exit(0); }
template <class T> constexpr bool chmin(T& x, T const& y) { if (x > y) { x = y; return true; } return false; }
template <class T> constexpr bool chmax(T& x, T const& y) { if (x < y) { x = y; return true; } return false; }
template <class It> constexpr auto sumof(It b, It e) { return accumulate(b,e,typename iterator_traits<It>::value_type{}); }
const ll INF = (1LL<<62)-1; // ~ 4.6e18
////////////////////////////////

int32_t main() {
    int n; cin >> n;
    vector<double> p(n); cin >> p;
    auto dp = make_v<double,2>(n+1,n+1);
    dp[0][0] = 1;
    rep (i,n) loop (j,0,<=i) {
        dp[i+1][j+1] += dp[i][j]*p[i];
        dp[i+1][j] += dp[i][j]*(1-p[i]);
    }
    double sum = 0;
    loop (j,(n+1)/2,<=n) sum += dp[n][j];
    cout << sum << endl;
}


Measured memory_bytes: 141056
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n,a;
  cin>>n>>a;
  
  if(n%500>a) cout<<"No"<<endl;
  else cout<<"Yes"<<endl;
  
  return 0;
}

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

using namespace std;

template< typename T >
struct SkewHeap
{
  struct Node
  {
    T key, lazy;
    Node *l, *r;
  } *root = nullptr;

  Node *propagate(Node *t)
  {
    if(t->lazy != 0) {
      if(t->l) t->l->lazy += t->lazy;
      if(t->r) t->r->lazy += t->lazy;
      t->key += t->lazy;
      t->lazy = 0;
    }
    return t;
  }

  Node *merge(Node *x, Node *y)
  {
    if(!x || !y) return x ? x : y;
    propagate(x), propagate(y);
    if(x->key > y->key) swap(x, y);
    x->r = merge(y, x->r);
    swap(x->l, x->r);
    return x;
  }

  Node *push(const T &key)
  {
    auto t = new Node({key, 0, nullptr, nullptr});
    root = merge(root, t);
  }

  T top()
  {
    return propagate(root)->key;
  }

  void pop()
  {
    propagate(root);
    auto *temp = root;
    root = merge(root->l, root->r);
    delete temp;
  }

  bool empty() const
  {
    return !root;
  }

  void add(const T &lazy)
  {
    if(root) {
      root->lazy += lazy;
      propagate(root);
    }
  }

  void merge(SkewHeap< T > &p)
  {
    root = merge(root, p.root);
  }
};

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};


using int64 = long long;

int main()
{
  int n, m;
  cin >> n >> m;
  vector< int > a(n);
  for(int i = 0; i < n; i++) cin >> a[i];

  vector< SkewHeap< int64 > > heap(n);
  for(int i = 0; i < n; i++) {
    heap[i].push(a[i]);
  }

  UnionFind uf(n);
  for(int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x = uf.find(x);
    y = uf.find(y);
    uf.unite(x, y);
    if(uf.find(x) != x) swap(x, y);
    heap[x].merge(heap[y]);
  }
  if(m == n - 1) {
    cout << 0 << endl;
    return 0;
  }

  SkewHeap< int64 > base;
  int64 ans = 0, cnt = 0;
  for(int i = 0; i < n; i++) {
    if(uf.find(i) == i) {
      ans += heap[i].top();
      heap[i].pop();
      base.merge(heap[i]);
      cnt++;
    }
  }

  while(m * 2 + cnt < (n - 1) * 2) {
    if(base.empty()) {
      cout << "Impossible" << endl;
      return 0;
    }
    ans += base.top();
    base.pop();
    cnt++;
  }

  cout << ans << endl;
}

Measured memory_bytes: 6528
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <cmath>

using namespace std;

void b_minor_change(void) {
	string s, t;
	cin >> s >> t;

	int diff = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != t[i])diff++;
	}

	cout << diff << endl;;
}

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


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

S = input()[:-1]
T = input()[:-1]
d = {}

for i in range(len(S)):
    if S[i] not in d:
        d[S[i]] = T[i]
    else:
        if d[S[i]]!=T[i]:
            print('No')
            exit()

d = {}

for i in range(len(T)):
    if T[i] not in d:
        d[T[i]] = S[i]
    else:
        if d[T[i]]!=S[i]:
            print('No')
            exit()

print('Yes')

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

int n,m;

void rec(int a, int b, string s){
  if(a>n || b>m)return;
  if(a==n && b==m){
    cout << s << endl;
    return;
  }
  if( (a<=3 && b==5) || (a==5 && b<=3) )return;
  if( (a==4 && b==6) || (a==6 && b==4) )return;
  if( a==5 && b==5 )return;

  rec(a+1,b,s+"A");
  rec(a,b+1,s+"B");
}
  
int main(){
  cin >> n >> m;
  rec(0,0,"");
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
using namespace std;
string s[200001];
int main(){
	int n,sum=1;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	sort(s+1,s+n+1);
	for(int i=1;i<n;i++){
		if(s[i]!=s[i+1]) sum++;
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 9880