akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include<bits/stdc++.h>
#include <utility>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;
using ll = long long;
map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int a,b,h;
  cin >> a >> b >> h;
  cout << (a+b)*h/2 << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int a, b;
		ArrayList<Integer> li = new ArrayList<Integer>();
		a = in.nextInt();
		b = in.nextInt();
		int max = Math.max(a, b);
		for (int i = 0; i < max; i++) {
			if (Math.abs((a - i)) == Math.abs((b - i))) {
				li.add(i);
			}
		}
		if (li.size() != 0) {
			for (int i = 0; i < li.size(); i++) {
				if (i != li.size() - 1)
					System.out.print(li.get(i) + " ");
				else
					System.out.println(li.get(i));
			}
		} else
			System.out.println("IMPOSSIBLE");
		in.close();
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

int main()
{
  ll N;
  cin >> N;

  if(N%2==1||N==0){
    cout << 0 << endl;
  }else{
    ll x=10;
    ll sum=0;
    while(N/x!=0){
      sum+=N/x;
      x*=5;
    }
    cout << sum << endl;
  }
}

Measured memory_bytes: 256
INFTY = Float::INFINITY
$count = 0

def merge(a, left, mid, right)
    n1 = mid - left;
    n2 = right - mid;
    # l[0...n1], r[0...n2] ?????????
    l = (0...n1).to_a
    r = (0...n2).to_a
    (0...n1).each do |i|
        l[i] = a[left + i]
    end
    (0...n2).each do |i|
        r[i] = a[mid + i]
    end
    l[n1] = INFTY
    r[n2] = INFTY
    i = 0
    j = 0
    # for k = left to right-1
    for k in (left...right)
        $count += 1
        if l[i] <= r[j]
            a[k] = l[i]
            i = i + 1
        else
            a[k] = r[j]
            j = j + 1
        end
    end
end

def mergeSort(a, left, right)
    if left+1 < right
        mid = (left + right)/2;
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)
    end
    a
end

n = gets.to_i
a = gets.split(/ /).map(&:to_i)
puts mergeSort(a, 0, n).join(" "), $count
__END__
?????? 1
10
8 5 9 2 6 3 7 1 10 4
merge(a, left, mid, right)
n1 = mid - left;
n2 = right - mid;
l[0...n1], r[0...n2] ?????????
for i = 0 to n1-1
    l[i] = a[left + i]
    for i = 0 to n2-1
        r[i] = a[mid + i]
        l[n1] = INFTY
        r[n2] = INFTY
        i = 0
        j = 0
        for k = left to right-1
            if l[i] <= r[j]
                a[k] = l[i]
                i = i + 1
            else
                a[k] = r[j]
                j = j + 1

                mergeSort(a, left, right)
                if left+1 < right
                    mid = (left + right)/2;
                    mergeSort(a, left, mid)
                    mergeSort(a, mid, right)
                    merge(a, left, mid, right)

Measured memory_bytes: 69776
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define cvector vector<char>
#define svector vector<string>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll k,x;cin>>k>>x;
  ll l=x-k+1,r=x+k-1;
  for(ll i=l;i<r;++i) cout<<i<<' ';print(r);
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[]$){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    String t = sc.next();
    int a=sc.nextInt();
    int b=sc.nextInt();
    String u=sc.next();
    sc.close();
    Solve solve = new Solve(s, t, u, a, b);
  }
}

class Solve{
  public Solve(String s, String t, String u, int a, int b){
    System.out.println(s.equals(u)?--a+" "+b:a+" "+--b);
  }
}


Measured memory_bytes: 20692
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		
		Scanner scanner = new Scanner(System.in);
		String w = scanner.next();
		
		String[] W = w.split("");
		
		int i=0, j=0, cnt=0;
		for(i=0; i<W.length; i++ ){
			
			for(j=0; j<W.length; j++ ){
				if(W[i].equals(W[j])){
					cnt++;
				}
			}
			if(!((cnt%2)==0)){
				System.out.println("No");
				return;
			}
			cnt = 0;
		}
		System.out.println("Yes");
	}
}

Measured memory_bytes: 9680
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
#define MOD 1000000007
#define INF 1000000000000000007
#define MAXN 300005

// it's swapnil07 ;)


signed main(){
    fast
    #ifdef SWAPNIL07
        freopen("/home/swapnil/Desktop/c++/input.txt","r",stdin);
        freopen("/home/swapnil/Desktop/c++/output.txt","w",stdout);
    #endif
    int n; cin>>n;
    map<map<char, int>, int> m;
    int ans = 0;
    For(i, 0, n){
        string s; cin>>s;
        map<char, int> m1;
        For(j, 0, s.length()){
            m1[s[j]]++;
        }
        ans += m[m1];
        m[m1]++;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 62336
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

class Main {

    public static void main(String[] args) throws Exception {

        try {

            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            String input = br.readLine();
            Map<String, String> nextAlphabet = new HashMap<>();
            nextAlphabet.put("a", "b");
            nextAlphabet.put("b", "c");
            nextAlphabet.put("c", "d");
            nextAlphabet.put("d", "e");
            nextAlphabet.put("e", "f");
            nextAlphabet.put("f", "g");
            nextAlphabet.put("g", "h");
            nextAlphabet.put("h", "i");
            nextAlphabet.put("i", "j");
            nextAlphabet.put("j", "k");
            nextAlphabet.put("k", "l");
            nextAlphabet.put("l", "m");
            nextAlphabet.put("m", "n");
            nextAlphabet.put("n", "o");
            nextAlphabet.put("o", "p");
            nextAlphabet.put("p", "q");
            nextAlphabet.put("q", "r");
            nextAlphabet.put("r", "s");
            nextAlphabet.put("s", "t");
            nextAlphabet.put("t", "u");
            nextAlphabet.put("u", "v");
            nextAlphabet.put("v", "w");
            nextAlphabet.put("w", "x");
            nextAlphabet.put("x", "y");
            nextAlphabet.put("y", "z");
            nextAlphabet.put("z", "a");

            System.out.println(nextAlphabet.get(input).toString());
        } catch (IOException | NumberFormatException e) {
            e.printStackTrace();
            System.exit(0);
        } catch (final Exception e) {
            e.printStackTrace();
            System.exit(0);
        }
    }
}

Measured memory_bytes: 20948
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	string s;
	cin >> s;
	int a[4] = { 0 };
	for (int i = 0; i < s.length(); i++) {
			if (s[i] == 'E')a[0]=1;
			if (s[i] == 'W')a[1]=1;
			if (s[i] == 'S')a[2]=1;
			if (s[i] == 'N')a[3]=1;
	}
	if (a[0] == a[1] && a[2] == a[3]) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3636
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc077/tasks/arc084_a

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
input = stdin.readline


def main(args):
    N = int(input())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    A.sort()
#    B.sort()
    C.sort()

#    lut_A = {}
#    lut_C = {}
#    for b in B:
#        i = bisect_left(A, b)
#        lut_A[b] = i
#        j = bisect_right(C, b)
#        lut_C[b] = N - j
    lut_A = {b:bisect_left(A, b) for b in B}
    lut_C = {b:(N - bisect_right(C, b)) for b in B}

    ans = 0
    for b in B:
        i = lut_A[b]
        j = lut_C[b]
        ans += i * j

    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 39916
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pii>
#define read(FILE)  freopen(FILE, "r", stdin);
#define out(FILE) freopen(FILE, "w", stdout);
#define clr(x, y) memset(x,y,sizeof(x));
#define IO ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define rep(i, m, n) for(int i=m ; i<n ; i++)
#define forr(i, m, n) for(int i=m ; i<=n ; i++)
#define endl '\n'
#define pb push_back
#define re return
const int N = 1e5 + 5;
const ll OO = LLONG_MIN;
using namespace std;
struct point {
    ll a, b, c;
} arr[N];
ll n, dp[N][4];
ll solve(ll i, ll pre) {
    if (i == n)
        re 0;
    ll &ret = dp[i][pre];
    if (~ret) re ret;
    ret=OO;
    ret=max(ret,solve(i+1,3));
    if(pre!=0){
        ret=max(ret,solve(i+1,0)+arr[i].a);
    }
    if(pre!=1){
        ret=max(ret,solve(i+1,1)+arr[i].b);
    }
    if(pre!=2){
        ret=max(ret,solve(i+1,2)+arr[i].c);
    }

    re ret;
}

int main() {
    IO;
    cin >> n;
    rep(i, 0, n) {
        cin >> arr[i].a >> arr[i].b >> arr[i].c;
    }
    memset(dp, -1, sizeof(dp));
    cout << solve(0, 3);
}

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

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#define dumpv(...)
#endif

#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

ll dp[105][100005];

void solve() {
  int N, W;
  cin >> N >> W;
  vector<int> w(N), v(N);
  rep(i, N) cin >> w[i] >> v[i];
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= W; j++) {
      dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
      if (0 <= j - w[i])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i]);
    }
  }
  cout << dp[N][W] << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  // freopen("temp.1", "r", stdin);
  solve();
  return 0;
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int main(){
	int n;cin>>n;
	vector<int>a(n);
	rep(i,n)cin>>a[i];
	vector<int>v;
	rep(i,n)v.push_back(i);
	sort(v.begin(),v.end(),[&](int l,int r){return a[l]<a[r];});
	for(int i:v){
		cout<<i+1<<' ';
	}
	cout<<endl;
}

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

int main() {
    int N; cin >> N;
    vector<int> P(N); 
    for (int i = 0; i < N; i++) cin >> P[i];
    vector<int> Q(N);
    for (int i = 0; i < N; i++) cin >> Q[i];
    vector<int> perm(N);
    for (int i = 0; i < N; i++) perm[i] = i + 1;
    int k = 1;
    int ip, iq;
    do {
        bool f = true;
        for(int i = 0; i < N; i++) {
            if (perm[i] != P[i]) {
                f = false;
                break;
            }
        }
        if (f) ip = k;
        f = true;
        for(int i = 0; i < N; i++) {
            if (perm[i] != Q[i]) {
                f = false;
                break;
            }
        }
        if (f) iq = k;
        k++;
    } while( next_permutation(perm.begin(), perm.end()) );  
    cout << abs(ip - iq) << endl;
}

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

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int tmp = 0;
        for (int j = 0, d = i; j < 5; j++) tmp += d % 10, d /= 10;
        if (a <= tmp && tmp <= b) ans += i;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
string s[10005];
vector<string> a,b,c;
int main(){
	int n,num=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		int len=s[i].length()-1;
		if(s[i][0]!='B'&&s[i][len]=='A') a.push_back(s[i]);
		if(s[i][0]=='B'&&s[i][len]=='A') b.push_back(s[i]);
		if(s[i][0]=='B'&&s[i][len]!='A') c.push_back(s[i]);
		for(int j=1;j<=len;j++){
			if(s[i][j]=='B'&&s[i][j-1]=='A') num++;
		}
	}
	int lena=a.size(),lenb=b.size(),lenc=c.size();
	int x=min(lena,1),y=min(lenc,1);
	lena-=x;lenc-=y;
	cout<<min(lena,lenc)+max(0,x+y+lenb-1)+num<<endl;
}

Measured memory_bytes: 1408
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};

void solve(ll x) {
  cout << (x < 1200 ? "ABC" : "ARC") << endl;
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	ll x;
	scanf("%lld", &x);
	solve(x);
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    int n;
    cin >> n;
    vector<int>a(n),hist(100100);
    int answer = 0;
    REP(i,100100)hist[i] = 0;
    REP(i,n){
        cin >> a[i];
        hist[a[i]]++;
    }

    if(n == 1){
        cout << 1 << endl;
        return 0;
    }
    else if(n == 2){
        if(abs(a[0]-a[1])<=2){
            cout << 2 << endl;
        }
        else{
            cout << 1 << endl;
        }
        return 0;
    }

    FOR(i,1,n-1){
        answer = max(answer,hist[i-1]+hist[i]+hist[i+1]);
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<numeric>
#include<map>
#include<set>
#include<bitset>
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define LL long long
template<class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> inline void chmin(T& a, T b) { if (a > b) { a = b; } }
const long long LLINF = 1LL << 62;
const int INF = 1LL << 30;
using namespace std;

int main(void) {
	LL N;
	cin >> N;

	vector<map<char, LL> > grid(N);
	map<map<char, LL>, LL> distance_table;

	rep(i, N) {
		cin >> grid[i]['x'] >> grid[i]['y'];
	}

	//全ての点同士の距離を計算する
	for (int i = 0; i < N; i++){//注目している点
		for (int j = 0; j < N; j++)
		{
			if (i == j) {
				continue;
			}

			map<char, LL> tmp;
			map<map<char, LL>, LL> this_loop_map;
			tmp['x'] = grid[j]['x'] - grid[i]['x'];
			tmp['y'] = grid[j]['y'] - grid[i]['y'];
			distance_table[tmp] += 1;
		}
	}

	//最大値をdistance_tableから取得する
	LL max_value = 0;
	for (auto &kv:distance_table)
	{
		chmax(max_value,kv.second);
	}

	cout << 1 + (N - 1) - max_value << endl;

	return 0;
}

Measured memory_bytes: 768
s = input()

ans = 0

if s == "SSS":
    ans = 0
elif s == "SSR":
    ans = 1
elif s == "SRS":
    ans = 1
elif s == "SRR":
    ans = 2
elif s == "RSS":
    ans = 1
elif s == "RSR":
    ans = 1
elif s == "RRS":
    ans = 2
elif s == "RRR":
    ans = 3

print(ans)



Measured memory_bytes: 9048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
string dir = "RDLU";

int h, w;
string field[505];
vector<P> pos, tmp;
bool visited[1005][1005];
int mrg = 500;

// 位置の候補を消しながら移動
void move(int k, bool f){
    tmp.clear();
    for(auto p : pos){
        int ni = p.first+di[k], nj = p.second+dj[k];
        if((field[ni][nj]=='#') == f){
            if(f) tmp.push_back({ni,nj});
            else tmp.push_back(p);
        }
    }
    pos = tmp;
}

bool dfs(int i, int j){
    visited[i+mrg][j+mrg] = true;
    for(int k=0;k<4;k++){
        int ni = i+di[k], nj = j+dj[k];
        if(visited[ni+mrg][nj+mrg]) continue;
        string res;
        cout << "? " << dir[k] << endl;
        cin >> res;
        bool ok = res == "YES";
        move(k, ok);
        if(ok){
            if(dfs(ni, nj)) return true;
            cout << "? " << dir[(k+2)%4] << endl;
            cin >> res;
            move((k+2)%4, true);
        }
    }
    if(pos.size() == 1){
        cout << "! " << pos.front().first-i << " " << pos.front().second-j << endl;
        return true;
    }
    return false;
}

int main() {
    cin >> h >> w;
    for(int i=0;i<h;i++){
        cin >> field[i];
        for(int j=0;j<w;j++){
            if(field[i][j] == '#'){
                pos.push_back({i,j});
            }
        }
    }
    dfs(0,0);
    return 0;
}



Measured memory_bytes: 19756
#include<bits/stdc++.h>
#define XX first
#define YY second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

int T;
int N;
using V = vector<LL>;

LL Reduce(LL v, V &bs) {
  for (LL b : bs) {
    MN(v, v^b);
  }
  return v;
}

void Append(V &bs, LL v) {
  v = Reduce(v, bs);
  if (v > 0) bs.eb(v);
}

void Solve() {
  cin >> N;
  V A(N);
  rep(i, N) cin >> A[i];
  
  string S;
  cin >> S;
 
  vector<LL> bs; 
  rrep(i, N) {
    if (S[i] == '1') {
      LL r = Reduce(A[i], bs);
      if (r) {
        cout << "1\n";
        return;
      }
    } else if (S[i] == '0') {
      Append(bs, A[i]);
    } else assert(0);
  }
  cout << "0\n";
}

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);

  cin >> T;
  while (T--) {
    Solve();
  }
}


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

typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9+7;

#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define REPR(i,n) for(int (i)=(n-1);(i)>=0;i--)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);i++)
#define FORR(i,m,n) for(int (i)=(m-1);(i)>=(n);i--)
#define PRINT(x) {cout << (x) << endl;}

int main(){
    int n;
    cin >> n;
    vector<int> L;
    REP(i, n){
        int a;
        cin >> a;
        L.push_back(a);
    }
    sort(L.begin(), L.end());
    int ans = 0;
    REP(i, n-2){
        FOR(j, i+1, n-1){
            FOR(k, j+1, n){
                int a = L[i], b = L[j], c = L[k];
                if (a < b + c and b < a + c and c < a + b)
                    ans++;
            }
        }
    }
    PRINT(ans)
}

Measured memory_bytes: 384
import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int x = sc.nextInt();
		TreeSet<Integer> set = new TreeSet<>();
		set.add(1);
		for (int i=2; i<=33; i++) {
			for (int j=2; j<=100; j++) {
				if (Math.pow(i,j) > x) break;
				set.add((int)Math.pow(i,j));
			}
		}
		
		int ans = 1;
		for (Integer n: set) {
			if (n > x) break;
			ans = n;
		}
		out.println(ans);
	}
}

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

int main()
{
	int a;
	cin >> a;
	char b[256];
	for (int i = 0; i < a; i++){
		cin >> b[i];
	}
	for (auto i : b){
		if (i == 'Y'){
			cout << "Four" << endl;
			return 0;
		}
	}
	cout << "Three" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define ll long long
#define ld long double
#define MOD 1000000007
#define nl cout << bl
#define rt ll Q[100005] = {0}
#define mp make_pair
#define test() \
    ull t;     \
    cin >> t;  \
    while (t--)
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define s(ar, n) sort(ar, ar + n)
#define rs(ar, n) sort(ar, ar + n, greater<ll>())
#define oa(a, n)               \
    for (ll i = 0; i < n; i++) \
        cout << a[i] << " ";
#define cn(a, n)               \
    for (ll i = 0; i < n; i++) \
        cin >> a[i];
#define ov(a, n)                    \
    for (ll i = n - 1; i >= 0; i--) \
        cout << a[i] << " ";        \
    nl
#define ovp(a, n)              \
    for (ll i = 0; i < n; i++) \
        cout << a[i].ff << " " << a[i].ss << bl;
#define maxa(ar, N) *max_element(ar, ar + N)
#define mina(ar, N) *min_element(ar, ar + N)
#define present(c, x) ((c).find(x) != (c).end())
#define fastio()                  \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)
typedef pair<int, int> pii;
ll fast_exp(ll base, ll exp)
{
    ll res = 1;
    while (exp > 0)
    {
        if (exp % 2 == 1)
            res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res % MOD;
}
ll fib(ll n)
{
    if (n < 2)
        return n;
    ll a = 0, b = 1, pre;
    int i = 1;
    while (i < n)
    {
        pre = (a + b) % MOD;
        a = b;
        b = pre;
        i++;
    }
    return pre;
}
ll fac(ll n)
{
    if (n % 2 == 0)
        return 2;

    for (ll i = 3; i * i <= n; i += 2)
    {
        if (n % i == 0)
            return i;
    }

    return n;
}
ll fact(ll n)
{
    if (n > 1)
        return n * fact(n - 1);
    else
        return 1;
}
bool sortbysec(const tuple<int, int, int> &a,
               const tuple<int, int, int> &b)
{
    return (get<1>(a) < get<1>(b));
}

int main()
{
    int n;
    cin >> n;
    ll ans = fast_exp(n, 1) + fast_exp(n, 2) + fast_exp(n, 3);
    cout << ans;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
typedef long long ll;
#define _GLIBCXX_DEBUG
#define int long long
using namespace std;
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPR(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= (ll)(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= (ll)(b); i--)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MAXIN(x) max_element(ALL(x)) - x.begin();
#define MIN(x) *min_element(ALL(x))
#define MININ(x) min_element(ALL(x)) - x.begin();
#define INF 1000000000000
#define MOD 100000070

#define MAXR 100000
#define PI 3.14159265358979323846

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

signed main() {
    // 頂点数と辺数
    int N, M;
    cin >> N >> M;

    // グラフ入力受取 (ここでは無向グラフを想定)
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }

    // BFS のためのデータ構造
    vector<int> dist(N, -1);  // 全頂点を「未訪問」に初期化
    queue<int> que;

    vector<int> MAE(N,-1) ;

    // 初期条件 (頂点 0 を初期ノードとする)
    dist[0] = 0;
    que.push(0);  // 0 を橙色頂点にする

    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front();  // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (dist[nv] != -1) continue;  // すでに発見済みの頂点は探索しない
            MAE[nv] = v;

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            dist[nv] = dist[v] + 1;
            que.push(nv);
        }
    }

    // 結果出力 (各頂点の頂点 0 からの距離を見る)
    for (int i = 1; i < N; i++) {
        if(MAE[i]==-1){
            cout << "No" <<endl ;
            return 0;
        }
    }
    cout << "Yes" <<endl ;
    for (int v = 1; v < N; ++v) cout <<MAE[v]+1<< endl;

    return 0;
}

Measured memory_bytes: 13640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] friendliness = new int[n];
        String[] s = br.readLine().split(" ");
        long answer = 0L;
        for(int i=0;i<n;i++){
            friendliness[i] = Integer.parseInt(s[i]);
        }
        Arrays.sort(friendliness);
        int secondMax = friendliness[n-2];

        answer += friendliness[n-1];
        int maxIdx = n-2;
        int counter = 0;

        for (int i = n-3;i>=0;i--){
            if(counter == 2){
                --maxIdx;
                secondMax = friendliness[maxIdx];
                counter = 0;
            }
            answer += secondMax;
            ++counter;

        }

        System.out.println(answer);
    }
}

Measured memory_bytes: 63892
import java.util.*;
import java.io.*;
import java.math.BigInteger;

 
class Main implements Runnable {
  // static Scanner in;
  static FastReader in;
  static PrintWriter out;
  static int[][] dirs8 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1}};
  static int[][] dirs = {{0, -1}, {1, 0}, {0, +1}, {-1, 0}};
 
  static int[][] E;
  // static List<int[]>[] adj;
  static List<Integer>[] adj;
  static int[] vis;
 
  static long INFL = (long) 1e15 + 7;
  static int INF = (int) 1e9 + 7;
  static int mod = 998244353;
  
  static int T, n, m, k, count, cur, w;
  static boolean flag;
  static int[] a, b;
  static int[][] map;

  static int[] par;
  static long[] dp;

  static void solve() throws Exception {
    n = in.nextInt();
    w = in.nextInt();
    dp = new long[w + 1];
    for (int i = 0; i < n; i++) {
      int ww = in.nextInt();
      int vv = in.nextInt();

      for (int j = w; j >= ww; j--) {
        dp[j] = Math.max(dp[j], dp[j - ww] + vv);
      }
    }

    out.println(dp[w]);

  }

 

  public static void main(String[] args) throws Exception {
 
    // in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    in = new FastReader();
    out = new PrintWriter(System.out);
 
    // int numOfTests = in.nextInt();
    // for (int caseNum = 1; caseNum <= numOfTests; caseNum++) {
    //   // Thread t = new Thread(null, new Main(), "Main", 1 << 28);
    //   // t.start();
    //   // t.join();
    //   solve();
    // }
 
    // // Thread t = new Thread(null, new Main(), "Main", 1 << 28);
    // // t.start();
    // // t.join();
    solve();
 
    out.flush();
    out.close();
  }
 
  @Override
  public void run() {
    try {
      solve();
    } catch (Exception e) {
      e.printStackTrace(); 
    }
  }
 
  static class FastReader {
    public BufferedReader br; 
    StringTokenizer st; 
    public FastReader() {br = new BufferedReader(new InputStreamReader(System.in));} 
    String next() { 
      while (st == null || !st.hasMoreElements()) { 
          try {st = new StringTokenizer(br.readLine());} 
          catch (IOException e) {e.printStackTrace();} 
      } 
      return st.nextToken(); 
    } 
    int nextInt() {return Integer.parseInt(next());} 
    long nextLong() {return Long.parseLong(next());} 
    double nextDouble() {return Double.parseDouble(next());} 
    String nextLine() {
      String str = ""; 
        try {str = br.readLine();} 
        catch (IOException e) {e.printStackTrace();} 
        return str; 
    }
  }

  static void as(boolean result) throws Exception {
    if (!result) {
      throw new Exception();
    }
  }

  static int modInverse(int a, int m) { 
    int m0 = m; 
    int y = 0, x = 1; 
    if (m == 1) {return 0;} 
    while (a > 1) { 
      // q is quotient 
      int q = a / m; 
      int t = m; 
      // m is remainder now, process 
      // same as Euclid's algo 
      m = a % m; 
      a = t; 
      t = y; 
      // Update x and y 
      y = x - q * y; 
      x = t; 
    } 
    // Make x positive 
    if (x < 0) 
      x += m0; 
    return x; 
  } 
} 

Measured memory_bytes: 21332
a,b=map(int, input().split())

def primes(m):
    pf={}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    return pf

A=list(primes(a).keys())
B=list(primes(b).keys())
ans=1
for i in A:
    if i in B:
        ans+=1
print(ans)

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

#define int long long
#define rep(i, n) for (int i = 0; i < (int) (n); i++)
#define reps(i, n) for (int i = 1; i <= (int) (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), (x).end())
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr double PI = 3.1415926535897932384626433832795028;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int N;
vint A;
signed main() {
    cin >> N;
    rep(i, N) {
        int a;
        cin >> a;
        A.push_back(a), A.push_back(a);
    }
    sort(all(A)), reverse(all(A));
    int ans = 0;
    reps(i, N - 1) { ans += A[i]; }
    cout << ans << endl;
}

Measured memory_bytes: 7400
#include<stdio.h>
#include<string.h>
int main()
{
	char n[102];
	scanf("%s", n);
	int k;
	scanf("%d", &k);
	int m = strlen(n);
	int ans;
	int i;
	int a, b;
	if (k == 1)
		ans = 9 * (m - 1) + (int)(n[0] - '0');
	else if (k == 2)
	{
		a = -1;
		for (i = 1; i < m; i++)
		{
			if (n[i] > '0')
			{
				a = i;
				break;
			}
		}
		ans = 81 * (m - 1) * (m - 2) / 2;
		ans += 9 * (m - 1) * (int)(n[0] - '1');
		if (a > 0)
		{
			ans += (int)(n[a] - '0');
			ans += 9 * (m - a - 1);
		}
	}
	else
	{
		a = b = -1;
		for (i = 1; i < m; i++)
		{
			if (n[i] > '0')
			{
				if (a < 0)
					a = i;
				else if (b < 0)
					b = i;
			}
		}
		ans = 729 * (m - 1) * (m - 2) * (m - 3) / 6;
		ans += 81 * (m - 1) * (m - 2) / 2 * (int)(n[0] - '1');
		if (a > 0)
		{
			ans += (int)(n[a] - '1') * 9 * (m - a - 1);
			ans += 81 * (m - a - 1) * (m - a - 2) / 2;
			if (b > 0)
			{
				ans += (int)(n[b] - '0');
				ans += 9 * (m - b - 1);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <ctime>
#define ll long long int
#define MOD 1000000007
using namespace std;
#define pb push_back
#define rep(i, x, n) for (ll i = x; i < n; i++)
#define rev(i, n, x) for (ll i = n; i > x; i--)
clock_t start;

void FAST(int argc)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    start = clock();
    if (argc == 2)
        freopen("std.in", "r", stdin);
}
/*vector<ll> v;
void seive()
{
    v.pb(2);
    for (int i = 3; i < 100000; i += 2)
    {
        for (int j = 0; j < v.size(); j++)
        {
            if (i % v[j] == 0)
                break;
            if (v[j] * v[j] > i)
            {
                v.pb(i);
                break;
            }
        }
    }
}
/*
void prime_factor(ll x, vector<ll> &r)
{
    ll sqrt_x = sqrt(x);

    for (ll i : v)
    {
        if (i > sqrt_x)
            break;

        if (x % i == 0)
            r.pb(i);

        while (x % i == 0)
        {
            x /= i;
        }
    }

    if (x >= 2)
        r.pb(x);
}
*/
/*
ll power(ll x, ll y)
{
    ll res = 1;
    x = x % MOD;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % MOD;
        y = y >> 1;
        x = (x * x) % MOD;
    }
    return res;
}
*/
/*
inline void dfs(long long int curr, long long int prev)
{

    for (long long int i : a[curr])
        if (i != prev)
            dfs(i, curr);
}
*/
/*
ll multi(ll a, ll b)
{
    return ((a * b) % MOD);
}
*/
//---------------------CODE STARTS HERE---------------------

int main(int argc, char *argv[])
{
    FAST(argc);

    ll testcase = 1;
    //cin >> testcase;

    while (testcase--)
    {
        int n;
        cin >> n;

        int k;
        cin >> k;
        int h[n + k];
        rep(i, k, n + k)
                cin >>
            h[i];
        int ans[n + k] = {0};
        // ans[0] = 0;

        // if (n > 1)
        //     ans[1] = abs(h[1] - h[0]);
        rep(i, 0, k)
        {
            h[i] = h[k];
        }

        rep(i, k, n + k)
        {
            ans[i] = abs(h[i] - h[i - 1]) + ans[i - 1];
            rep(j, 0, k)
            {
                int ar = abs(h[i] - h[i - j - 1]) + ans[i - j - 1];
                ans[i] = min(ans[i], ar);
            }
        }
        // rep(i, 0, n + k)
        cout << ans[n + k - 1] << endl;
        //--------??--------CLEAR VECTORS--------??--------
    }

    //v.clear();
    //cout << "time: " << (clock() - start) / (double)CLOCKS_PER_SEC << '\n';
    return 0;
}
//vector <pair <int,int> > vect;


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <complex>

using namespace std;
using ll = long long;

int main() {
    string s;
    cin >> s;
    char b = s[0];
    int maxL = s.size();
    for (auto i = 1; i < s.size(); i++) {
        if (s[i] != b) {
            auto l = max(i, int(s.size() - i));
            maxL = min(maxL, l);
            b = s[i];
        }
    }
    cout << maxL << endl;
}



Measured memory_bytes: 512
from collections import Counter
# ABC159 D

N=int(input())
A=list(map(int,input().split()))

c=Counter(A)
res=[]
for p,r in c.items():
    res.append((r*(r-1))//2)
sum_res=sum(res)
for k in range(N):
    r=c[A[k]]
    print(sum_res-(r*(r-1))//2+((r-1)*(r-2))//2)

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


int main(int argc, char const* argv[])
{
  int a, b, c;
  cin >> a >> b >> c;
  if (a+b+c > 21) {
    cout << "bust" << endl;
  } else {
    cout << "win" << endl;
  }
  return 0;
}


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

int main(){
    int n,k;
    string s;
    cin >> n >> k;
    cin >> s;
    char cur = s.at(0);
    vector<int> cnts;
    int cnt = 0;
    rep(i, s.size()){
        if(s.at(i) == cur){
            cnt++;
        }
        else{
            cnts.push_back(cnt);
            cnt = 1;
        }
        cur = s.at(i);
    }
    cnts.push_back(cnt);

    // for(int c:cnts){
    //     cout << c << " ";
    // }
    // cout << endl;

    int hp = 0;
    for(int c : cnts) hp += c-1;
    int kind = cnts.size();
    int opmx = kind/2;
    if(opmx <= k){
        hp += kind-1;
    }else{
        hp += k*2;
    }
    cout << hp << endl;
    return 0;
}

Measured memory_bytes: 1020
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
edges = [[] for _ in range(n)]

for _ in range(n-1):
    u,v,w = LI()
    edges[u-1].append((v-1,w))
    edges[v-1].append((u-1,w))

ans = [None]*n
ans[0] = 0

que = deque()
que.append(0)
while que:
    v = que.popleft()
    for u,c in edges[v]:
        if ans[u] != None:
            continue
        if c % 2 == 0:
            ans[u] = ans[v]
        else:
            ans[u] = (ans[v]+1) % 2
        que.append(u)
print(*ans)

Measured memory_bytes: 66464
#include <iostream>
#include <vector>

void selection(std::vector<int> a, int n) {
    int minj;
    int change_count = 0;
    int temp; // use to swap two elements in vector
    bool change_check;
    for (int i = 0; i < n - 1; i++) {
        minj = i;    
        change_check = false;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minj]) {
                minj = j;
                change_check = true;
            }
        }
        if (change_check == true) {
            temp = a[minj]; 
            a[minj] = a[i]; 
            a[i] = temp;
            change_count++;
        }
    }
    for (int i = 0; i < n - 1; i++) {
        std::cout << a[i] << " ";
    }
    std::cout << a[n - 1] << std::endl;;
    std::cout << change_count << std::endl;;
    return;
}

int main(void) {
    int n;
    std::cin >> n;
    std::vector<int> a(n, 0);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    selection(a, n);
    return 0;
}

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

int main(){
	int H, W;
	while (1){
		cin >> H >> W;
		if (H == 0 && W == 0)break;
		for (int i = 0; i < H; i++){
			for (int j = 0; j < W; j++){
				cout << '#';
			}
			cout << endl;
		}
		cout << endl;
	}
	return 0;
}

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

int main(){
  int n,i,j,v,A[1001];
  cin >> n;
  for(i = 0; i < n; i++){
    cin >> A[i];
  }
  for(i = 1; i < n; i++){
    for(int k = 0; k < n; k++){
      if(k == n-1)cout << A[k];
      else cout << A[k] << " ";
    }
    cout << endl;
    v = A[i];
    j = i - 1;
    while(j >=0 && A[j] > v){
      A[j+1] = A[j];
      j--;
      A[j+1] = v;
	
    }
  }
 
    for(int k = 0; k < n; k++){
      if(k == n-1)cout << A[k];
      else cout << A[k] << " ";
    }
    cout << endl;
  return 0;
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define endl "\n"
#define sz(u) (int)(u.size())
typedef long long ll;
using namespace std;
void solve(){
    int n;
    cin>>n;
    set<string> t;
    for(int i=0;i<n;i++){
        string k;
        cin>>k;
        t.insert(k);
    }
    cout<<t.size();
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();

}


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

public class Program
{
    private int N;

    public void Solve()
    {
        N = int.Parse(Console.ReadLine());
        /* f(i) = [i,i+N)でどっちが多いか
         * f(i) != f(i+1) なら [i+1,i+N)の赤青の数は同じ
         * かつS[i] = f(i),S[i+N] = f(i+1)
         * f(i) != f(i+N)なので境目はどこかにある
         *　
         * にぶたん ①
         * if f(L) = f(M) L:=M
         * else R:=M
         * log N回 <= 9回
         *  
         * [i+1,i+N)とWを聞けばS[W]が確定する N-1回 ②
         * 
         * N+1個が赤青同数で確定しているのでN-1個の赤青同数のを構成して[i+1,i+N)を聞く ②で確定したの使えば楽かも
         * N-1回 ③
         */


        Color[] ans = new Color[N * 2];

        #region ①

        int l = 0, r = N;
        Color fL = F(l);
        Color fR = F(r);
        while (r - l > 1)
        {
            int m = (l + r) / 2;
            if (F(m) == fL)
            {
                l = m;
            }
            else
            {
                r = m;
            }
        }

        ans[l] = fL;
        ans[l + N] = fR;

        // [i+1 i+N) = [tL, tR)
        int tL = l + 1;
        int tR = l + N;

        int[] tmp = new int[N - 1];
        for (int i = 0; i < N - 1; i++)
        {
            tmp[i] = tL + i + 1;
        }

        string t = string.Join(" ", tmp);

        #endregion

        #region ②

        List<int> tmp2 = new List<int>();

        for (int i = 0; i < N * 2; i++)
        {
            if (ans[i] == Color.Unknown && (i < tL || tR <= i))
            {
                tmp2.Add(i + 1);
                ans[i] = Ask2(t, i + 1);
            }
        }

        string t2 = string.Join(" ", tmp2);

        #endregion

        #region ③

        for (int i = 0; i < N * 2; i++)
        {
            if (ans[i] == Color.Unknown)
            {
                ans[i] = Ask2(t2, i + 1);
            }
        }

        #endregion

        Console.WriteLine($"! {string.Join("", ans)}");
    }

    private Color F(int i)
    {
        var a = new int[N];
        for (int j = 0; j < N; j++)
        {
            a[j] = i + j + 1;
        }

        return Ask(string.Join(" ", a));
    }

    private Color Ask2(string t, int w)
    {
        Console.WriteLine($"? {t} {w}");
        return Anser();
    }


    private Color Ask(string a)
    {
        Console.WriteLine($"? {a}");
        return Anser();
    }

    private Color Anser()
    {
        string t = Console.ReadLine();
        if (t == "Red") return Color.R;
        if (t == "Blue") return Color.B;
        throw new Exception();
    }

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

public enum Color
{
    Unknown = 0,
    R,
    B
}

Measured memory_bytes: 13736
N, X = map(int, input().split())
table = [None] * (N + 1)
table[0] = (1, 1)


def check_X(x, p):
    if x >= X:
        print(p)
        exit()


def dfs(n, x, p):
    check_X(x, p)
    if table[n] is None or x + table[n][0] > X:
        # バン
        new_x, new_p = x + 1, p

        # L-1バーガー
        new_x, new_p = dfs(n - 1, new_x, new_p)
        check_X(new_x, new_p)

        # パティ
        new_x += 1
        new_p += 1

        # L-1バーガー
        new_x, new_p = dfs(n - 1, new_x, new_p)

        # バン
        new_x += 1
        check_X(new_x, new_p)

        table[n] = (new_x - x, new_p - p)
        return new_x, new_p
    else:
        dx, dp = table[n]
        return x + dx, p + dp


dfs(N, 0, 0)


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

void calcAllShortest(vector<vector<pair<int, ll>>>& G, vector<vector<ll>>& d)
{
	auto numV = (int)G.size();
	for (auto i = 0; i < numV; ++i)
	{
		d.push_back(vector<ll>(numV, LLONG_MAX));

		for (auto v : G[i])
		{
			d[i][v.first] = v.second;
		}
		d[i][i] = 0;
	}

	for (auto k = 0; k < numV; ++k)
	{
		for (auto i = 0; i < numV; ++i)
		{
			for (auto j = 0; j < numV; ++j)
			{
				if (d[i][k] >= LLONG_MAX || d[k][j] >= LLONG_MAX)
				{
					continue;
				}
				auto kd = d[i][k] + d[k][j];
				if (d[i][j] > kd)
				{
					d[i][j] = kd;
				}
			}
		}
	}
}

int main()
{
	int H, W;
	cin >> H >> W;
	vector<string> S(H);
	for (auto i = 0; i < H; ++i)
	{
		cin >> S[i];
	}

	int offset[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
	vector<vector<pair<int, ll>>> G(H * W);
	for (auto y = 0; y < H; ++y)
	{
		for (auto x = 0; x < W; ++x)
		{
			if (S[y][x] == '#')
			{
				continue;
			}

			auto& temp = G[y * W + x];
			for (auto i = 0; i < 4; ++i)
			{
				auto ny = y + offset[i][0];
				auto nx = x + offset[i][1];
				if (ny < 0 || ny >= H || nx < 0 || nx >= W)
				{
					continue;
				}
				if (S[ny][nx] == '#')
				{
					continue;
				}

				temp.push_back({ ny * W + nx, 1 });
			}
		}
	}

	vector<vector<ll>> d;
	calcAllShortest(G, d);

	auto result = 0ll;
	for (auto y = 0; y < H; ++y)
	{
		for (auto x = 0; x < W; ++x)
		{
			for (auto gy = 0; gy < H; ++gy)
			{
				for (auto gx = 0; gx < W; ++gx)
				{
					auto temp = d[y * W + x][gy * W + gx];
					if (temp <= H * W)
					{
						result = max(result, temp);
					}
				}
			}
		}
	}

	cout << result << endl;

	return 0;
}

Measured memory_bytes: 1536
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();sc.nextLine();
  for(int i=0;i<m+2;i++)System.out.print("#");
  System.out.println();
  for(int i=0;i<n;i++){
  System.out.print("#");
    System.out.print(sc.nextLine());
    System.out.println("#");
  }
  for(int i=0;i<m+2;i++)System.out.print("#");
  System.out.println();
}
}


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

int main() {
    int n, c, k;
    cin >> n >> c >> k;
    vector<int> t(n);
    rep(i,n) cin >> t.at(i);

    sort(t.begin(), t.end());
    int ans = 0, top = 0;
    queue<int> q;
    rep(i,n) {
        if (!q.empty()) {
            while (!q.empty() && q.front() + k < t.at(i)) {
                ans++;
                for (int i = 0; !q.empty() && i < c; ++i) {
                    q.pop();
                }
            }
        }
        q.push(t.at(i));
    }

    while (!q.empty()) {
        ans++;
        for (int i = 0; !q.empty() && i < c; ++i) {
            q.pop();
        }
    }

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

Measured memory_bytes: 3736