akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

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

int main(){
    int d,t,s;
    cin >> d >> t >> s;
    if(s*t >= d){
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }
    return 0;
}

Measured memory_bytes: 3124
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define rep(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SORT(x) sort(rng(x))
#define RSORT(x) sort(rrng(x))
#define SUM(x) accumulate(rng(x),0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main () {
  int n, m;
  cin >> n >> m;
  vi a(n);
  rep(i,n) cin >> a[i];
  vi b(m), c(m);
  rep(i,m) cin >> b[i] >> c[i];

  priority_queue<pii> pq;
  rep(i,n) pq.push(pii(a[i],1));
  rep(i,m) pq.push(pii(c[i],b[i]));

  ll ans = 0;
  rep(i,n) {
    auto p = pq.top(); pq.pop();
    ans += p.fi;
    if (p.se > 1) {
      p.se--;
      pq.push(p);
    }
  }
  cout << ans << endl;
  return 0;
}

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

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

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

    int main(){
        int a,b ; cin >> a >> b;
        if(a*b & 1) cout << "Odd" << endl;
        else cout << "Even" << endl;

        return 0;
    }




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int, int>
#define vi vector<int>
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define x first
#define y second
#define rep(i, j, k) for(i=j; i<k; i++)
#define sep(i, j, k) for(i=j; i>k; i--)
const int N = 2e4+5, inf = 1e9+7;
int n, k, i, j;
struct nd{int w, s, v;};
nd v[N];
int dp[N];
bool cmp(nd&a, nd&b){ return a.w+a.s<b.w+b.s; }
signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int i, j, a, b, ans = 0;
    cin>>n;
    rep(i, 1, n+1) cin>>v[i].w>>v[i].s>>v[i].v;
    sort(v+1, v+n+1, cmp);
    rep(i, 1, n+1)
        for(int w = v[i].s; w >= 0; w--)
            dp[w+v[i].w] = max(dp[w+v[i].w], dp[w]+v[i].v);
    cout<<*max_element(dp, dp+N);
}

Measured memory_bytes: 384
a,b,h,m = map(int, input().split())

totalM = 60*h + m

aDegree = 30 / 60 * totalM

bDegree = 360 / 60 * totalM

import math

ax = a * math.cos(math.radians(aDegree))
ay = a * math.sin(math.radians(aDegree))

bx = b * math.cos(math.radians(bDegree))
by = b * math.sin(math.radians(bDegree))

print(math.sqrt((bx - ax)**2 + (by - ay)**2))

Measured memory_bytes: 9520
def merge(a, l, m, r):
  global count
  Left = a[l:m]
  Left.append(1e10)
  Right = a[m:r]
  Right.append(1e10)
  i, j = 0, 0
  for k in range(l, r):
    count += 1
    if Left[i] <= Right[j]:
      a[k] = Left[i]
      i += 1
    else:
      a[k] = Right[j]
      j += 1

def sort(a, l, r):
  if r-l > 1:
    m = (l+r)//2
    sort(a, l, m)
    sort(a, m, r)
    merge(a, l, m, r)
       
       
count=0
n=int(input())
a=[int(i) for i in input().split()]
sort(a, 0, n)
print(*a)
print(count)


Measured memory_bytes: 63448
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds; 
using namespace std;
#define int long long
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mll map<ll,ll>
#define mii map<int,int>
#define mp make_pair
#define pb push_back
#define rep(i,b) for(ll (i)=0;i<(b);i++)
#define all(c) (c).begin(), (c).end()
#define F first
#define S second
#define CLR(p) memset(p, 0, sizeof(p))
#define SET(p) memset(p, -1, sizeof(p))
#define DEBUG true
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
//typedef long long int ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, 
tree_order_statistics_node_update> new_data_set; 
const int MAX=200005;
#define MOD 1000000007
/*std::cout << std::fixed;
std::cout << std::setprecision(6);*/
//(a%mod-b%mod+mod)%mod



/************************************


 
*************************************/

vector<vector<ll>>v;
ll T=0;
ll cnt1=0,cnt0=0;
vector<ll>dep;
bool visited[MAX];
vector<ll>par;
vector<ll>tin,tout;
vector<ll>col;
ll f=0,k=1;
map<pll,ll>m;
ll dp1[MAX],dp2[MAX];
ll red,blue;
ll ans;
ll dp[MAX];

ll lca(ll u,ll v){
	while(u!=v){
		ll l1,l2;
		l1 = log2(u);
		l2 = log2(v);
		//cout<<l1<<"$$"<<l2<<endl;
		if(l1<l2)
			swap(u,v);
		u /=2;
	}
	return u;
}





signed main(){
	boost;
	int t=1;
	// cin>>t;
	while(t--){
		int n;
		cin>>n;
		int a[n+1];
		rep(i,n)
			cin>>a[i+1];
		int dp[n+1];
		CLR(dp);
		int prefix[n];
		CLR(prefix);
		prefix[1]=a[1];
		for(int i=3;i<=n;i+=2){
			prefix[i]=prefix[i-2]+a[i];
		}
		dp[1]=a[1];

		for(int i=2;i<=n;i++){
			if(i==3){
				dp[i] = max(dp[i-1],a[i]);
				continue;
			}
			if(i%2==0){
				dp[i] = max(prefix[i-1],dp[i-2]+a[i]);
			}
			else{
				dp[i] = max(dp[i-1],dp[i-2]+a[i]);
			}
		}
		cout<<dp[n]<<endl;
	}

	return 0;
}

Measured memory_bytes: 8340
from collections import deque

N=int(input())
G=[[] for n in range(N)]
E=[]
for n in range(N-1):
    a,b=map(int,input().split())
    E.append((a-1,b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
K=max([len(v) for v in G])

P=[-1]*N
Q=[0]
X=[]
count=0
while Q:
    v=Q.pop()
    X.append(v)
    for u in G[v]:
        if u==P[v]:
            continue
        P[u]=v
        Q.append(u)

C={}
for v in X:
    color=0
    try:
        p_color=C[tuple(sorted((v,P[v])))]
    except:
        p_color=-1
    for u in G[v]:
        if u==P[v]:
            continue
        if color==p_color:
            color+=1
        C[tuple(sorted((u,v)))]=color
        color+=1

print(K)
for e in E:
    print(C[e]+1)


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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
    int N; cin >> N;
    vector<ll> a(N);
    int teven = 0, feven = 0, odd = 0;
    for(int i = 0; i < N; i++) {
        cin >> a[i];
        if(a[i] % 4 == 0) feven++;
        else if(a[i] % 2 == 0) teven++;
        else odd++;
    }
    string ans;
    if(teven != 0) {
        if(feven >= odd) ans = "Yes";
        else ans = "No";
    }
    else {
        if(feven >= odd - 1) ans = "Yes";
        else ans = "No";
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4032
#include<iostream>
#include<string>
#include <numeric>
using namespace std;
string str;
int main() {
    cin >> str;
    int c=0, f=0;
    int n=str.size();
    for(int i=0; i<n; ++i){
        if(str[i] == 'C') c=i+1;
        if(str[i] == 'F') f=i+1;
    }
    if(c<f && c>=1 && f>=1) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int num = 0;
		num = N % 10;
		if((num == 2)||(num == 4)||(num == 5)||(num == 7)||(num == 9) ) {
			System.out.println("hon");
		}else if((num == 0)||(num == 1)||(num == 6)||(num == 8)) {
			System.out.println("pon");
		}else if(num == 3) {
			System.out.println("bon");
		}
	}

}


Measured memory_bytes: 35752
n = int(input())
A = [int(i) for i in input().split()]

k=max(A)

C = [0] * (k+1)

for a in A:
  C[a] = C[a] + 1

for i in range(1, k+1):
  C[i] = C[i] + C[i-1]


B = [0] * n
for a in A:
  rank = C[a]
  B[rank  - 1] = a
  C[a] = C[a] - 1

print(*B)



Measured memory_bytes: 224244
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

vector<vector<ll> > table;
vector<P> roads;
vector<P> qs;

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

  ll ans = 0;
  ans += A - 1;
  if (A <= B) ans++;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
def main():
    s = input()
    k = int(input())
    d = len(s)
    m = set()
    if k >= d:
        for i in range(d + 1):
            for j in range(1, d - i + 1):
                m.add(s[i:i + j])
    else:
        for i in range(d):
            for j in range(1, k + 1):
                m.add(s[i:i + j])

    m = list(m)
    m.sort()
    print(m[k - 1])


if __name__ == '__main__':
    main()


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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};


signed main()
{   
  gearup;
  string s; cin >> s;
  deque<char> ans;
  rep(i,s.size())ans.push_back(s[i]);
  ll res = 0;
  while(1){
      if(ans.size() == 0 || ans.size() == 1)break;
      char f = ans.front();
      ans.pop_front();
      char b = ans.back();
      ans.pop_back();
      if(f == b)continue;
      else if(f == 'x')ans.push_back(b);
      else if(b == 'x')ans.push_front(f);
      else{
          out(-1); //fとbが'x'以外なら
          return 0;
      }
      res++;
  }
  out(res);
}


Measured memory_bytes: 512
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
#define INF 0x7fffffff
#define Max 200000
#define eps 1e-10

int arr[21];

double dp[22][Max];

double getval(double a, double b)
{
	double temp = (b - a) / a;
	if (temp < eps)
		return -temp;
	else
		return temp;
}

double MIN(double a, double b)
{return a < b ? a : b;}

int main()
{
	int n, i, j, k;
	while (scanf("%d", &n) == 1)
	{
		for (i = 1; i <= n; ++i)
			scanf("%d", &arr[i]);


		for (i = 1;i <= Max;i ++)
				dp[0][i] = INF;
		dp[0][1] = 0.0;
		for (i = 1; i <= n; ++i)
		{
			for (k = 1;k <= Max;k ++) dp[i][k] = INF;
			for (j = 1; j <= Max; ++j)
			{
				for (k = 1; j * k <= Max; ++k)
				{
					double temp = max(getval(arr[i], j * k), dp[i - 1][j]);
					dp[i][j * k] = min(temp, dp[i][j * k]);
				}
			}
		}

		double ans = INF;
		for (i = 1; i <= Max; ++i)
			ans = min(ans, dp[n][i]);
		printf("%.12lf\n", ans);
	}
}
/*
3
6 11 12
3
6 11 24
3
6 11 30
*/

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

template<typename T>
istream& operator >> (istream& istr, vector<T>& vec){
    for(T& x: vec) istr >> x;
    return istr;
}

template<typename T>
ostream& operator << (ostream& ostr, vector<T>& vec){
    if(!vec.empty()){
        ostr << vec.front();
        for(auto itr = ++vec.begin(); itr != vec.end(); itr++)
            ostr << " " << *itr;
    }
    return ostr;
}

template<typename T>
ostream& operator << (ostream& ostr, vector<vector<T>>& mat){
    if(!mat.empty()){
        ostr << mat.front();
        for(auto itr = ++mat.begin(); itr != mat.end(); itr++)
            ostr << endl << *itr;
    }
    return ostr;
}

template<typename T, typename U>
ostream& operator << (ostream& ostr, pair<T,U>& p){
    ostr << p.first << " " << p.second;
    return ostr;
}

template<typename T, typename U>
ostream& operator << (ostream& ostr, vector<pair<T,U>>& mat){
    if(!mat.empty()){
        ostr << mat.front();
        for(auto itr = ++mat.begin(); itr != mat.end(); itr++)
            ostr << endl << *itr;
    }
    return ostr;
}

typedef long long ll;
typedef vector<ll> vll;
// vll x(n); x[i]=a;
typedef vector<pair<ll,ll>> vpll;
// vpll x(n); x[i]={a,b}; x[i].first/second;
typedef vector<vector<ll>> vvll;
// vvll x(m,vi(n)); x[i][j]=a;

#define REP(i,n) for(ll i=0; i<(n); i++)
#define RREP(i,n) for(ll i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(ll i=(a); i<(b); i++)
#define FORR(i,a,b) for(ll i=(b)-1; i>=(a); i--)
#define dump(x) cout << #x << " = " << (x) << endl
#define all(x) (x).begin(),(x).end()
// sort(all(x));

int main(){
    ll n, ans;
    cin >> n;
    ans = (n-1)*n/2;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
// Ver19.03
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF (1 << 29) * 2
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

int main()
{
  int i, sum = 0, n, l, min = INF;
  scanf("%d%d", &n, &l);
  for (i = 1; i <= n; i++)
  {
    sum += (l + i - 1);
    if (abs(l + i - 1) < abs(min))
    {
      min = i + l - 1;
    }
  }
  printf("%d\n", sum - min);
  return 0;
}
		

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
ll gcd(ll a, ll b){
  if(b==0) return a;
  else gcd(b,a%b);
}
ll lcm(ll a, ll b){
  return a/gcd(a,b)*b;
}
int main(){
  string s,t,ns,nt;
  cin >> s >> t;
  vector<char>cs;
  vector<char>ct;
  rep(i,s.size()){
    cs.push_back(s[i]);
  }
  rep(i,t.size()){
    ct.push_back(t[i]);
  }
  sort(cs.begin(),cs.end());
  sort(ct.begin(),ct.end(),greater<char>());
  
  ns="";
  nt="";
  rep(i,s.size()){
    ns+=cs[i];
  }
  rep(i,t.size()){
    nt+=ct[i];
  }
  if(ns<nt) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}


Measured memory_bytes: 256
(function(input) {
    var p = input.split('\n');
    var n = Number(p.shift());
    var A = p.shift().split(' ').map(Number);

    var B = coutingSort(A, 10000);
    console.log(B.join(' '));
})(require('fs').readFileSync('/dev/stdin', 'utf8'));

function coutingSort(A, k) {
    var C = [];
    for (var i = 0; i <= k; i++) {
        C[i] = 0;
    }
    for (var i = 0; i < A.length; i++) {
        C[A[i]]++;
    }
    //console.log(C);
    for (var i = 1; i <= k; i++) {
        C[i] = C[i] + C[i - 1];
    }
    //console.log(C);
    var B = [];
    for (var i = A.length - 1; i >= 0; i--) {
        //console.log(B);
        B[C[A[i]]] = A[i];
        C[A[i]]--;
        //console.log(B);
    }
    var D = [];
    for (var i = 0; i < B.length; i++) {
        var n = B[i];
        if (typeof(n) !== 'undefined') {
            D.push(n);
        }
    }
    return D;
}

Measured memory_bytes: 201936
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */
#define mt make_tuple
#define ll long long
#define ld long double
#define eb emplace_back
#define fi first
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin >> vec[i];}
#define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";}
#define mod(a,b) ((a%b +b)%b)
#define bit(x,i) (x&(1<<i))  //select the bit of position i of x
#define lowbit(x) ((x)&((x)^((x)-1))) //get the lowest bit of x
#define hBit(msb,n) asm("bsrl %1,%0" : "=r"(msb) : "r"(n)) //get the highest bit of x, maybe the fastest
#define max(a,b) (a<b?b:a)
#define min(a,b) (a>b?b:a) 
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define IN(i,l,r) (l<i&&i<r)
#define LINR(i,l,r) (l<=i&&i<=r)
#define LIN(i,l,r) (l<=i&&i<r)
#define INR(i,l,r) (l<i&&i<=r)
#define lastEle(vec) vec[vec.size()-1] 
#define SZ(x) ((int)((x).size()))
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) 
#define ll long long 
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define INF 1001001001
#define PI 3.1415926535897932384626
 
using namespace std;
 using namespace __gnu_pbds;
 template <typename T>
 using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
 
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}
 
//----------------------------------------------------------------------------------------------------------------------
  
void swap(int & a, int & b){
    auto temp = a;
    a = b;
    b = temp;
}
 
const ll MOD = 1e9 + 7;
 
ll inf = 1LL*1e11;
 
void no(){
    cout <<"NO" << endl;exit(0);
}
void yes(){
    cout <<"YES" << endl; exit(0);
}

void solve(){
   ll x; cin >> x;
   ll ans = (x/500LL)*1000LL;
    x%=500;
    ans += (x/5LL)*5LL;
    cout << ans;
}       
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t = 1;
    while(t--) solve();
    return 0;
} 


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int l = sc.nextInt();
        
        int[] taste = new int[n];
        int min = 1000;
        int eat = 0;
        
        for(int i = 1; i <= n; i++){
            if(Math.abs(l + i - 1) < min){
                min = Math.abs(l + i - 1);
                eat = i - 1;
            }
            taste[i-1] = l + i -1;
        }
        
        int ans = 0;
        for(int i = 0; i < n; i++){
            if(i != eat){
                ans += taste[i];
            }
        }
        
        System.out.println(ans);
    }
}

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

using namespace std;

typedef long long ll;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

const int inf = 1e9 + 7;
const int mod = 1e9 + 7;

inline void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
}

inline int mul(int a, int b) {
  return (a * (ll) b) % mod;
}

inline int pw(int x, int n) {
  int res = 1;
  while (n > 0) {
    if (n % 2) {
      res = mul(res, x);
      n--; 
    } else {
      x = mul(x, x);
      n /= 2;
    }
  }
  return res;
}

const int N = 107;
const int K = 1e5 + 7;

int dp[K];
int p[K];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector <int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  dp[0] = 1;
  for (int i = 0; i <= k; i++) {
    p[i] = 1;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= k; j++) {
      dp[j] = 0;
      int val = p[j];
      if (j - a[i] - 1 >= 0) {
        add(val, -p[j - a[i] - 1]);
      }
      dp[j] = val;
    }
    for (int j = 0; j <= k; j++) {
      p[j] = dp[j];
      if (j != 0) {
        add(p[j], p[j - 1]);
      }
    }
  }
  cout << dp[k] << '\n';
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>

using namespace std;

int main() {
  string a, b;
  cin >> a >> b;

  string s = a + b;
  int num = stoi(s);

  for(int i = 2; i*i <= num; i++) {
    if(i*i == num) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;

}


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

typedef long long int ll;
#define size 100005
ll a[size],dp[size],n,k;

ll func(ll i)
{
	if(i==0)
	{
		dp[i]=0;
		return 0;
	}
	if(dp[i]!=-1)
		return dp[i];
	ll ma=1e18;
	for(ll j=1;j<=k;j++)
	{
		if(i-j>=0)
			ma = min(ma, func(i-j)+abs(a[i]-a[i-j]));
	}
	dp[i]=ma;
	return dp[i];
}

int main()
{
	ios::sync_with_stdio(0);
	cin >> n >> k;
	ll i,j;
	for(i=0;i<n;i++)
	{
		cin >> a[i];	
		dp[i]=-1;
	}
	ll ans = func(n-1);
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 6528
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
	int i,j,dp[4001]={0},s;
	scanf("%d",&s);
	dp[0]=1;
	for(i=0;i<s;i++){
		if(dp[i]!=0){
			for(j=3;j<=s;j++){
				if(i+j<=s){
					dp[i+j]=dp[i]+dp[i+j];
					dp[i+j]=dp[i+j]%1000000007;
				}
			}
		}
	}
	printf("%d\n",dp[s]);
	return 0;
}

Measured memory_bytes: 1720
import java.util.Scanner;

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

		char[] work = new char[str.length()];

		for(int i = 0; i < str.length(); i++){
			work[i] = str.charAt(i);
		}
		
		if(work[2] == work[3] && work[4] == work[5]){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 24148
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;

enum inf = 1_001_001_001;
enum inf6 = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;


void main() {
    int N, K;
    scan(N, K);
    auto A = readln.split.to!(int[]);

    auto S = A.sum(0);
    int[] div;
    for (int d = 1; d*d <= S; d++) {
        if (S % d == 0) {
            div ~= d;
            div ~= S / d;
        }
    }
    div.sort();

    bool ok(int d) {
        auto rems = new int[](N);
        foreach (i ; 0 .. N) {
            rems[i] = A[i] % d;
        }
        auto t = rems.sum() / d;
        if (t > N) return false;
        rems.sort();
        return rems.take(N - t).sum() <= K;
    }

    int ans = 1;
    foreach (d ; div) {
        if (ok(d)) ans = d;
    }

    writeln(ans);
}







void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


Measured memory_bytes: 3324
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
#include<utility>
#include<algorithm>
#include<functional>
#include<deque>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<iomanip>
using namespace std;

int main(){
   int n, m;
   cin >> n >> m;
   long long x[n], y[n], z[n], w[n], tmpmax = 0;
   for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> z[i];

   for (int i = 0; i < 2; i++){
      for (int j = 0; j < 2; j++){
         for (int k = 0; k < 2; k++){
            for (int l = 0; l < n; l++){
               w[l] = (long long)(pow(-1, i)*x[l] + pow(-1, j)*y[l] + pow(-1, k)*z[l]);
            }
            sort(w, w+n);
            long long ss = 0;  int cnt = n-1;
            for (int l = 0; l < m; l++) ss += w[cnt--];
            if (tmpmax < ss) tmpmax = ss;
         }
      }
   }
   cout << tmpmax << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 20;
vector<int> g[N];
vector<int> vis(N);
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        int x, y;
        cin >> x >> y;
        if(abs(x - y) <= 1){
            cout << "Brown\n";
        }else{
            cout << "Alice\n";
        }
    }
}

Measured memory_bytes: 31488
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
int pn(int a[],int n){
  int i,j;
  a[0]=a[1]=0;
  for(i=2;i<n;i++)
    a[i]=i;
  for(i=2;i*i<n;i++){
    if(a[i]){
      for(j=i*i;j<n;j+=i)
        a[j]=0;
    }
  }
  j=2;
  for(i=0;j<n;i++){
    a[i]=a[j];
    for(j++;j<n&&a[j]==0;j++);
  }
  return i;
}
int a[42];
vector<pair<long long,double> > c;
void fn(int p,long long q,long long r){
  c.push_back(make_pair(q,(double)r/q));
  if(p<13){
    long long sm=1,pi=a[p];
    while(a[p]<=1000000000000000ll/q){
      q*=a[p];
      sm+=pi;
      pi*=a[p];
      fn(p+1,q,r*sm);
    }
  }
  return;
}
int main(){
  int i;
  pn(a,42);
  c.reserve(254000);
  fn(0,1,1);
  sort(c.begin(),c.end());
  double mx=0;
  for(i=0;i<(int)c.size();i++){
    if(mx<c[i].second){
      mx=c[i].second;
    }else{
      c[i]=make_pair(0,0);
    }
  }
  c.push_back(make_pair(1000000000000001ll,0));
  remove(c.begin(),c.end(),pair<long long,double>(0,0)),c.end();
  long long n;
  while(cin>>n,n){
    int mn=0,mx=87;
    for(;;){
      if(0){
      }else if(c[(mn+mx)/2].first>n){
	mx=(mn+mx)/2-1;
      }else if(c[(mn+mx)/2+1].first<=n){
	mn=(mn+mx)/2+1;
      }else{
	break;
      }
    }
    printf("%.6lf\n",c[(mn+mx)/2].second);
  }
  return 0;
}

Measured memory_bytes: 4808
#include<bits/stdc++.h>
#define ll long long int
#define mk make_pair
#define pb push_back
#define INF (ll)1e18
#define pii pair<ll,ll>
#define mod 1000000007 //998244353
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fb(i,a,b) for(ll i=a;i>b;i--)
#define ff first
#define ss second
#define PI 3.141592653589793238
#define pq priority_queue<ll>
#define pqr priority_queue<ll,vector<ll>,greater<ll>()>
using namespace std;
ll pow_mod(ll a,ll b)
{
	ll res=1;
	while(b!=0)
	{
		if(b&1)
		{
			res=(res*a)%mod;
		}
		a=(a*a)%mod;
		b/=2;
	}
	return res;
}
void solve()
{
   ll n,k;
   
   cin>>n>>k;
   
   ll r,s,p;
   
   cin>>r>>s>>p;
   
   string st;
   cin>>st;
   
   
   /*
        However, in the i
        -th round, the player cannot use the hand he/she used in the 
        (i−K)-th round. (In the first K rounds, the player can use any hand.)
   */
   
    for(ll i=0;i<n;i++)
    if(st[i]=='r')
    st[i]='p';
    else if(st[i]=='p')
    st[i]='s';
    else
    st[i]='r';
    
    
    bool mark[n+1];
    memset(mark,false,sizeof(mark));
    ll ans=0;
    for(ll i=0;i<n;i++){
        ll j=i;
        
        ll cnt=0;
        char x=st[i];
        
        if(!mark[i])
        {
          while(j<n&&st[j]==x){
              mark[j]=true;
            cnt++;
            j+=k;
          }
         ll val;
         
         if(x=='p')val=p;
         else if(x=='s')val=s;
         else val=r;
         
         ans+=((cnt+1)/2)*val;
        }
    }
    
    cout<<ans<<endl;
}
int32_t main()
{    ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);
     
//Start from Here.

  ll t;
  t=1;
 // cin>>t;
  while(t--)
  solve();
  
//Good Bye!
    return 0;
}

Measured memory_bytes: 3832
#include <iostream>
using namespace std;
int n,a[100];

void print(){
	int i=0;
	while(true){
		cout<<a[i];
		i++;
		if(i<n){
			cout<<" ";
		}else{
			break;
		}
	}
	cout<<endl;
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int cont=0;
	for(int i=0;i<n;i++){
		int minj=i;
		for(int j=i;j<n;j++){
			if(a[j]<a[minj]){
				minj=j;
			}
		}
		if(i!=minj){
			const int tmp=a[i];
			a[i]=a[minj];
			a[minj]=tmp;
			cont++;
		}
	}
	print();
	cout<<cont<<endl;
	return 0;
}


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

#define int long long

#define pb push_back
#define fi first
#define se second
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define low(a,b) lower_bound(all(a),(b))
#define upp(a,b) upper_bound(all(a),(b))
#define fill(i,n) memset(i,n,sizeof(i))
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<vint> vvint;
typedef vector<pint>vpint;
typedef pair<pint,int> P1;
typedef pair<int,pint> P2;
typedef pair<pint,pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007;
const ll INF=1e18;

int N,K,M,A,B,C;
string s,t;
int a[100010],b[100010],c[100010];

signed main() {
    IOS();
    cin>>N;
    if(N==25)cout<<"Christmas"<<endl;
    else if(N==24)cout<<"Christmas Eve"<<endl;
    else if(N==23)cout<<"Christmas Eve Eve"<<endl;
    else cout<<"Christmas Eve Eve Eve"<<endl;
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    




















































    return 0;
}

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

namespace ts{
  const int tsv=101000,tse=5202333;
  int n,ans[tsv];
  struct R{
    int to,nex;
  }r[tse];
  int hea[tsv<<1],cnt,bel[tsv<<1],blt,st[tsv<<1],top,dfn[tsv<<1],dft,low[tsv<<1];
      
  void RE(){
    memset(hea,0,sizeof hea);cnt=0;
    memset(bel,0,sizeof bel);blt=0;
    memset(dfn,0,sizeof dfn);dft=0;
  }
  void A(int u,int v){
    r[++cnt]=(R){v,hea[u]};hea[u]=cnt;
  }
  void must(int x,int x2,int y,int y2){
    A(x<<1|x2,y<<1|y2);
  }
  void XX(int x,int x2,int y,int y2){ // can't be together
    //printf("XX::%d %d %d %d\n",x,x2,y,y2);
    must(x,x2,y,y2^1);
    must(y,y2,x,x2^1);
  }
  void dfs(int x){
    low[x]=dfn[x]=++dft;
    st[++top]=x;
    int y;
    for (int i=hea[x];i>0;i=r[i].nex){
      y=r[i].to;
      if (!dfn[y]){
	dfs(y);
	low[x]=min(low[x],low[y]);
      }else{
	if (!bel[y]){
	  low[x]=min(low[x],dfn[y]);
	}
      }
    }
    if (low[x]==dfn[x]){
      bel[x]=++blt;
      while (st[top]!=x){
	bel[st[top]]=blt;
	top--;
      }
      top--;
    }
  }
  bool realmain(int n_){ // [1,n]
    n=n_;
    int u,v;
    for (int i=2;i<=(n<<1|1);i++){
      if (!bel[i]){
	top=0;
	dfs(i);
      }
    }
    for (int i=1;i<=n;i++){
      if (bel[i<<1|0]==bel[i<<1|1]) return 0;
      ans[i]=bel[i<<1|0]>bel[i<<1|1]?1:0;
    }
    return 1;
  }
}

int n, m, rt, cnt, lc[101000], rc[101000];
#define pii pair<int,int>
#define fi first
#define se second
vector<int>wei[10100];
pii p[20200];

void build(int &x,int l,int r){
  if (l==r){
    x=l; return;
  }
  x=++cnt;
  int mid=l+r>>1;
  build(lc[x],l,mid); ts::XX(x,0,lc[x],1);
  build(rc[x],mid+1,r); ts::XX(x,0,rc[x],1);
}

void gao(int &l,int &r,pii s,pii t){
  l=lower_bound(p+1,p+m+1,s)-p;
  r=lower_bound(p+1,p+m+1,t)-p-1;
}

void add(int x,int l,int r,int st,int en,int who){
  st=max(st,l); en=min(en,r);
  if (st>en) return;
  if (st==l&&en==r){
    ts::XX(x,1,who,1);
    return;
  }
  int mid=l+r>>1;
  add(lc[x],l,mid,st,en,who);
  add(rc[x],mid+1,r,st,en,who);
}

bool chk(int now){
  ts::RE();
  cnt=m; build(rt,1,m);
  for (int i=1;i<=n;++i)
    ts::XX(wei[i][0],0,wei[i][1],0);

  for (int i=1;i<=m;++i){
    int l, r;
    gao(l,r,(pii){p[i].fi-now+1,-1},p[i]);
    add(rt,1,m,l,r,i);
    gao(l,r,(pii){p[i].fi,p[i].se+1},(pii){p[i].fi+now-1,1e9});
    add(rt,1,m,l,r,i);
  }
  return ts::realmain(cnt);
}

int main(){
  
  cin>>n; int x;
  for (int i=1;i<=n;++i){
    cin>>x; p[++m]=(pii){x,i};
    cin>>x; p[++m]=(pii){x,i};
  }
  sort(p+1,p+m+1);
  for (int i=1;i<=m;++i)
    wei[p[i].se].push_back(i);

  int l=0, r=(1e9+7)/max(n/2-1,1)+3, mid, ans=0;
  for (;l<=r;){
    mid=l+r>>1;
    if (chk(mid)){
      ans=mid; l=mid+1;
    }else{
      r=mid-1;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 20992
while True:
    n, m = (int(s) for s in input().split())
    if not n:
        break

    sections = sorted(([int(s) for s in input().split()] for i in range(n)),
                      key=lambda x: x[1], reverse=True)

    for i, (d, p) in enumerate(sections):
        m -= d
        if m <= 0:
            print(sum(s[0] * s[1] for s in sections[i+1:]) - p * m)
            break
    else:
        print(0)

Measured memory_bytes: 8292
n = int(input())
t, x, y = 0, 0, 0
ans = "Yes"
for i in range(1, n+1):
  ti, xi, yi = map(int, input().split())
  displacements = (xi - x) + (yi - y)
  dist = abs(displacements)
  dt = ti - t
  if dt >= dist and (dt - dist) % 2 == 0:
    t, x, y = ti, xi, yi
  else:
    ans = "No"
  
  if ans == "No":
    break
 
print(ans)

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

int main () {
  int A, B, C;
  cin >> A >> B >> C;
  
  if (A == B) {
    cout << C << endl;
  }
  if (B == C) {
    cout << A << endl;
  }
  if (C == A) {
    cout << B << endl;
  }
}

Measured memory_bytes: 256
//                          VIVEK UPADHYAY
//                         MANIT, BHOPAL(M.P)
/**********************************************************************************************/
/**********************************************************************************************/
//                        $$ JAB-TAK TODEGA NHI,
//                           TAB -TAK CHODEGA NHI :D
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<cstdlib>
#include<unistd.h>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<utility>
#include<cmath>
#include<set>
#include<unordered_map>
#include<cstdio>
#include<map>
#include<numeric>
using namespace std;
#define F first
#define S second
#define mk(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define LINE cout<<endl ;
#define ok cout<<"ok\n" ;
typedef long long ll;
const int MAXN = 1e5 + 10 ;
const int MAX = 1e6 ;
double pi = 3.1415926535897932384626433832795;
const ll inf=1e18 ;
ll mod = 1e9 + 7 ;
vector<ll> p[MAXN] ;

void print(int N){
    int d=0 ;
    int t = N ;
    while(t > 0){
        d++ ;
        t/=10 ;
    }
    while(6-d > 0){
        cout<<"0";
        d++;
    }
    cout<<N;
}
int main() {
    int N , M ;
    cin >> N >> M ;
    pair<int,ll> a[M] ;
    for(int i=0;i<M;i++) cin >> a[i].F >> a[i].S ;

    for(int i=0;i<M;i++)
        p[a[i].F].pb(a[i].S) ;
    for(int i=0;i<=N;i++)
        sort(p[i].begin(),p[i].end());
    for(int i=0;i<M;i++){
        int index = upper_bound(p[a[i].F].begin(),p[a[i].F].end(),a[i].S) - p[a[i].F].begin();
        print(a[i].F);
        print(index);
        LINE ;
    }
    return 0 ;
}


Measured memory_bytes: 8576
#include <bits/stdc++.h>
#define R register
#define mp make_pair
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
const int mod = 998244353, N = 210;

int t, n;
ll a[N];
char s[N];

struct linearBasis {
//
ll base[N];

inline void init() {
	for (R int i = 0; i <= 60; ++i) base[i] = 0;
	return;
}

inline int insrt(ll x) {
	for (R int i = 60; ~i; --i) {
		if (~x & (1ll << i)) continue;
		if (!base[i]) return base[i] = x, 1;
		x ^= base[i];
	}
	return 0;
}
//
} bs;

inline int addMod(int a, int b) {
	return (a += b) >= mod ? a - mod : a;
}

inline ll quickpow(ll base, ll pw) {
	ll ret = 1;
	while (pw) {
		if (pw & 1) ret = ret * base % mod;
		base = base * base % mod, pw >>= 1;
	}
	return ret;
}

template <class T>
inline void read(T &x) {
	x = 0;
	char ch = getchar(), w = 0;
	while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	x = w ? -x : x;
	return;
}

int main() {
	read(t);
	while (t--) {
		bs.init();
		read(n);
		for (R int i = 1; i <= n; ++i) read(a[i]);
		scanf("%s", s + 1);
		int flag = 1;
		for (R int i = n; flag && i; --i)
			if (bs.insrt(a[i]) && s[i] == '1')
				flag = 0;
		cout << "10"[flag] << '\n';
	}
	return 0;
}

Measured memory_bytes: 3656
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
#define all(c)  c.begin(), c.end()
#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define vp vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define lb "\n"
#define rep(i,a,b) for(ll i = a;i<b;i++)
#define INF 998244353
#define MAX LLONG_MAX
using namespace std;
vll a[100001];
vb vis(100001);
vll length(100001);
void dfs(ll s) {
    vis[s]=true;
     for (auto u : a[s])
        {
            if(vis[u])
            {
                 length[s]=max(length[s],length[u]+1);
                continue;
            }
        dfs(u);
        length[s]=max(length[s],length[u]+1);
        }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifdef LOCAL
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w", stdout);
    #endif
ll i,j,k,n,m,ans=0;
cin>>n>>m;
rep(i,0,m)
{
    cin>>j>>k;
    a[j].pb(k);
}
rep(i,1,n+1)
    if(!vis[i])
    {
        dfs(i);
        ans=max(ans,length[i]);
    }
    cout<<ans;
return 0;
}


Measured memory_bytes: 8576
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

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

const long long INF = 1LL << 60;

/* bがa以上のとき、置き換え */
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b;}else{return false;}return true;}

/* bがa以下のとき、置き換え */
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b;}else{return false;}return true;}


// テーブルの用意
std::vector<long long> dp(100005, INF);	//dp[i] = 足場iまで飛ぶための最小コスト	
std::vector<long long> h(100005);

int main()
{
	int N;
	std::cin >> N;
	rep(i, N)	std::cin >> h[i];

	// 見ていく 
	rep(i, N)
	{
		if(i==0)
		{
			dp[i] = 0;
			continue;
		}
		else if(i==1)
		{
			dp[i] = dp[i-1] + abs(h[i] - h[i-1]);
			continue;
		}

		// 1つ前から 
		dp[i] = dp[i-1] + abs(h[i] - h[i-1]);

		// 2つ前はどう?
		chmin( dp[i], dp[i-2] + abs(h[i] - h[i-2]));
	}

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

//	printf("===dp[]===\n");
//	rep(i, N)
//	{
//		printf("dp[%d]:%lld\n", i, dp[i]);
//	}

	return 0;
}


Measured memory_bytes: 4624
#include <stdio.h>
int main(){
  int n,l,k;
  int m[32];
  scanf("%d",&l);
  
  for(n=2;n<=32;n++){
    m[n-1]=0;
    for(k=2;k*2-1<n;k++){
      if(n%k==0){
        m[n-1]+=1;
      }
    }
    if(m[n-1]==0||n==12||n==18||n==20){
      m[n-1]+=1;
    }
    if(n==8||n==27){
      m[n-1]+=3;
    }
    if(n==15){
      m[n-1]-=1;
    }
    if(n==4||n==9||n==25){
      m[n-1]+=1;
    }
    if(n==16){
      m[n-1]+=11;
    }
    if(n==24){
      m[n-1]+=9;
    }
    if(n==30){
      m[n-1]-=2;
    }
    if(n==32){
      m[n-1]+=47;
    }
  }
  m[0]=1;
  printf("%d",m[l-1]);
  return 0;
}
  

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

int main()
{
	long num, i,dif;
	cin >> num;
	num *= 3;
	int a[num];
	for (i = 0; i < num; i++) cin >> a[i];
	sort(a, a + num, greater<int>());
	dif = 0;
	/*for (i = 0; i < num*2/3; i++) {
		if (i % 2 == 1) dif += a[i];
	}*/
	for (i = 0; i < num / 3; i++) {
		dif += a[2 * i + 1];
	}
	cout << dif;
	return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <cmath>
#include <bits/stdc++.h>
#include <numeric>
#include <vector>
#include <iterator>
using namespace std;
typedef long long int ll;



const int N=1e5+10;
const int mod=1e9+7;
int f[N][13],n;
string s;
int main()
{
	cin>>s;
	n=s.size();
	f[0][0]=1;
	for(int i=1;i<=n;i++)
		if(s[i-1]>='0'&&s[i-1]<='9')
		{
			for(int j=0;j<13;j++)
				f[i][(j*10+s[i-1]-'0')%13]=(f[i][(j*10+s[i-1]-'0')%13]+f[i-1][j])%mod;
		}
		else
		{
			for(int k=0;k<10;k++)
				for(int j=0;j<13;j++)
					f[i][(j*10+k)%13]=(f[i-1][j]+f[i][(j*10+k)%13])%mod;
		}
	cout<<f[n][5]<<endl;
	return 0;
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
using namespace std;
int p[51],r[51];
void init(){for(int i=0;i<50;i++)p[i]=i,r[i]=0;}
int find(int x){return (p[x]==x)?x:(p[x]=find(p[x]));}
void unite(int x,int y) {
  x=find(x),y=find(y);
  if(x==y)return;
  if(r[x]<r[y])p[x]=y;
  else{p[y]=x;if(r[x]==r[y])r[x]++;}
}
bool same(int x,int y){return find(x)==find(y);}
vector<string> s,ans;
set<string> se[50];
int n,m;
 
void dfs(int k,int t) {
  bool f=1;
  for(int i=1; i<m; i++) if(!same(0,i)) {f=0;break;}
  if(f) {
    if(!ans.size()||ans.size()>__builtin_popcount(t)) {
      ans.clear();
      for(int i=0; i<n; i++) if(t&(1<<i)) ans.push_back(s[i]);
    }
    return;
  }
  if(k>=n) return;
  for(int i=k; i<n; i++) {
    if(__builtin_popcount(t|(1<<i))>5) continue;
    int l=0;
    while(l<m&&!se[l].count(s[i])) l++;
    if(l==m) continue;
    int pp[m],rr[m];
    for(int j=0; j<m; j++) pp[j]=p[j],rr[j]=r[j];
    for(int j=l+1; j<m; j++) {
      if(se[j].count(s[i])) unite(l,j);
    }
    dfs(i+1,t|(1<<i));
    for(int j=0; j<m; j++) p[j]=pp[j],r[j]=rr[j];
  }
}
 
int main() {
  int f=0;
  while(cin>>n>>m&&n) {
    if(f) cout<<endl;
    f=1;
    init();
    ans.clear();
    s.clear();
    for(int i=0; i<n; i++) {
      string t;cin>>t;
      s.push_back(t);
    }
    for(int i=0; i<m; i++) {
      se[i].clear();
      int k;cin>>k;
      for(int j=0; j<k; j++) {
        string t;cin>>t;
        se[i].insert(t);
      }
    }
    dfs(0,0);
    if(ans.size()) {
      cout<<ans.size()<<endl;
      for(int i=0; i<ans.size(); i++)cout<<ans[i]<<endl;
    } else cout<<"Impossible"<<endl;
  }
  return 0;
}


Measured memory_bytes: 3088
n = int(input())

cnt = 0
a_flag = 0
b_flag = 0
ab_flag = 0

s = [0]*n
for i in range(n):
    s[i] = input()

    for j in range(len(s[i])-1):
        if s[i][j:j+2] == 'AB':
            cnt += 1

    if s[i][0] == 'B' and s[i][-1] != 'A':
        b_flag += 1
    elif s[i][-1] == 'A' and s[i][0] != 'B':
        a_flag += 1
    elif s[i][0] == 'B' and s[i][-1] == 'A':
        ab_flag += 1

if ab_flag != 0:
    if a_flag == 0 and b_flag == 0:
        print(cnt + ab_flag - 1)
    elif a_flag>=1 and b_flag >= 1:
        print(cnt + ab_flag + 1 + min(a_flag - 1, b_flag - 1))
    else:
        print(cnt + ab_flag) 
else:
    print(cnt + min(a_flag, b_flag))

Measured memory_bytes: 3700
#include <math.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <iomanip>
#include <iostream>
#include <queue>
#include <sstream>
#include <vector>

using namespace std;
using Graph = vector<vector<int>>;

using ll = long long;
typedef pair<int, int> P;

const int INF = 1e8;

int main() {
  int N, W;
  cin >> N >> W;
  vector<vector<int>> vw(N, vector<int>(2));
  for (int i = 0; i < N; i++) {
    cin >> vw[i][0] >> vw[i][1];
  }
  vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
  for (int i = N - 1; i >= 0; i--) {
    for (int j = 0; j <= W; j++) {
      if (j < vw[i][1]) {
        dp[i][j] = dp[i + 1][j];
      } else {
        dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - vw[i][1]] + vw[i][0]);
      }
    }
  }
  cout << dp[0][W] << endl;

  return 0;
}


Measured memory_bytes: 6764