akhauriyash/Code-Regression huggingface dataset:
fun main(args: Array<String>) {
    val s = readLine()!!
    var (x, y) = readLine()!!.split(" ").map{it.toInt()}

    if (Math.max(Math.abs(x), Math.abs(y)) > s.length) {
        println(":(")
        return
    }

    val ss = s.split("T").map{ it.length }
    x -= ss[0]
    val l = ss.drop(1)

    fun canCreate(a: Int, l: List<Int>): Boolean {
        val t = Math.abs(a)
        var curr = BooleanArray(t * 2 + 1) { false }
        var next = BooleanArray(t * 2 + 1) { false }
        curr[t] = true

        for (b in l) {
            for (i in curr.indices) {
                if (i + b < next.size) {
                    next[i + b] = curr[i] || next[i + b]
                }
                if (i - b >= 0) {
                    next[i - b] = curr[i] || next[i - b]
                }
            }

            val tmp = next
            next = curr
            curr = tmp
            next.fill(false)
        }

        return curr[t + a]
    }

    fun judge(a: Int, b: Int): Boolean {
        return canCreate(a, l.filterIndexed { index, c -> index % 2 == 0}) &&
                canCreate(b, l.filterIndexed { index, c -> index % 2 == 1})
    }

    if (judge(y, x)) {
        println("Yes")
    } else {
        println("No")
    }
}


Measured memory_bytes: 40624
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/
const int MAXN = 120000;


int n;
int a[MAXN];

map<int, int> mm[2];

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		++mm[i % 2][a[i]];
	}
	vector<pair<int, int>> vv[2];
	for (int i = 0; i < 2; ++i) {
		for (auto j: mm[i])
			vv[i].emplace_back(n / 2 - j.second, j.first);
		sort(ALL(vv[i]));
		vv[i].emplace_back(n / 2, -i);
	}
	if (vv[0][0].second == vv[1][0].second) {
		cout << min(vv[0][0].first + vv[1][1].first, vv[0][1].first + vv[1][0].first) << "\n";
	}
	else {
		cout << vv[0][0].first + vv[1][0].first << "\n";
	}
	return 0;
}




Measured memory_bytes: 6524
### SNIPPET
  # n = gets.split.map(&:to_i)
  # array = n.times.map { gets.split.map(&:to_i) }
  # [].all?(&:even?)
  # a = [*1..m].repeated_combination(n).to_a
  # [1,2,3,4,5].select { |num| num.even? }  # => [2, 4]
  # ["a","a","b"].group_by(&:itself).map{|k,v| [k, v.count]}.to_h #=> {"a"=>2, "b"=>1}
  # 切り捨て: .floor(2).to_f ,切り上げ： .ceil(2).to_f,四捨五入: round(2)
  # 3.upto(6) do |i|, 6.downto(3) do |i|
  # 公約数125.gcd(100)、公倍数125.lcm(100)
  # PI = Math::PI
  # 高さ = a * Math.sin(w / 180.0 * Math::PI), 底辺 = a * Math.cos(w / 180.0 * Math::PI)
  # def chmax(a, b) a > b ? a : b end
  # INF = Float::INFINITY
  # def chmin(a, b) a < b ? a : b end

def dfs(s)
  ret = 0
  list = ["3","7","5"]
  if s.size() != 0
    return ret if s.to_i > @n
    ret += 1 if list.all?{|x| s.include?(x)}
  end

  list.each do |ele|
    ret += dfs(s + ele)
  end

  return ret
end

@n = gets.to_i
s = ""
puts dfs(s)



Measured memory_bytes: 14260
#include <iostream>

int main(){
  int A = 0;
  int B = 0;
  int C = 0;
  std::cin >> A >> B >> C;
  
  std::swap(A,B);
  std::swap(A,C);
  
  std::cout << A << ' '<< B << ' ' << C << std::endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	string s, a;
	int n;
	cin >> s >> n;
	rep(i, s.size()) if(i % n == 0) a += s[i];
	cout << a << endl;
	
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
		int count = 0;
		String check = sc.next();
		while(true) {
        String str = sc.next();
        	if(str.equals("END_OF_TEXT")) {
        		break;
        	}
        	if(str.toLowerCase().equals(check)) {
        		count++;
        	}
		}
		System.out.println(count);
    }
}


Measured memory_bytes: 26208
#include <iostream>
using namespace std;
int main()
{
	int N,Y,x,y,z;
	cin>>N>>Y;
    for (x=0; x<=Y/10000; x++)
    for (y=0; y<=Y/5000; y++)
	{
	  	z = N - x - y;
	    if (z>=0 && x*10000+y*5000+z*1000==Y)
	    {
	    	cout<<x<<" "<<y<<" "<<z;
	    	return 0;
	    }
	}
	cout << "-1 -1 -1";
	return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
C = [0]*N
for a in A:
  C[a] += 1
isOk = True
if N % 2 == 0:
  if C[0] != 0:
    isOk = False
  i = 1
  while i < N:
    if C[i] != 2:
      isOk = False
    i += 2
  i = 2
  while i < N:
    if C[i] != 0:
      isOk = False
    i += 2
else:
  if C[0] != 1:
    isOk = False
  i = 1
  while i < N:
    if C[i] != 0:
      isOk = False
    i += 2
  i = 2
  while i < N:
    if C[i] != 2:
      isOk = False
    i += 2
if isOk:
  print((2**(N//2))%(10**9+7))
else:
  print(0)

Measured memory_bytes: 53228
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N, d = map(int, input().split())
    ans = 0
    for _ in range(N):
        x, y = map(int, input().split())
        if x * x + y * y <= d * d:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 68992
import std.algorithm;
import std.bigint;
import std.concurrency;
import std.container;
import std.conv;
import std.functional;
import std.format;
import std.math;
import std.meta;
import std.random;
import std.range;
import std.stdio;
import std.string;
import std.traits;
import std.typecons;


auto solve(long N, long[] A) {
    auto negs = A.filter!"a < 0".array;
    auto abss = A.map!abs.array.sort();
    
    if (negs.length % 2 == 0)
        return abss.sum;
    
    return abss.sum - 2 * abss.front;
}


void main() {
    auto input = stdin.byLine.map!split.joiner;

    long N;
    N = input.front.to!long;
    input.popFront;

    long[] A = new long[](cast(size_t) (N));
    foreach (i; 0 .. cast(size_t) (N)) {
        A[i] = input.front.to!long;
        input.popFront;
    }

    static if (is(ReturnType!solve == void))
        solve(N, A);
    else
        solve(N, A).writeln;
}


Measured memory_bytes: 10728
N, M = map(int, input().split())
p = []
for _ in range(N):
    a, b = map(int, input().split())
    p.append((a, b))
p = sorted(p, key=lambda x: x[0])
ans = 0
for a, b in p:
    if b < M:
        ans += a * b
        M -= b
    else:
        ans += a * M
        print(ans)
        exit()


Measured memory_bytes: 18948
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)


typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    int N; cin >> N;
    vector<ll> A(N); repp(i, 0, N) cin >> A[i];
    map<ll, ll> m;
    ll sumA = 0;
    m[sumA] = 1;
    repp(i, 0, N) {
        sumA += A[i];
        ++m[sumA];
    }
    ll res = 0;
    for(auto x: m) {res += x.second * (x.second - 1) / 2;}
    cout << res << endl;
}

Measured memory_bytes: 14336
import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)])
S = np.where(S==".", 1, 0)

L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)

for i in range(H):
    D[-i-1] = (D[-i]+1)*S[-i-1]
    U[i] = (U[i-1]+1)*S[i]
    
for i in range(W):
    L[:, i] = (L[:, i-1]+1)*S[:, i]
    R[:, -i-1] = (R[:, -i]+1)*S[:, -i-1]
    
print (np.max(L+R+D+U)-3)

Measured memory_bytes: 248584
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 21

struct data{
  int num;
  int point;
};

int comp(const void *p1,const void *p2);


int main(void){
  char scorestr[128],*ch;
  int i,j,k,l;
  int score[MAX];
  int set,throw,frame;
  int id,sum;
  struct data *result;

  while(scanf("%d",&set)&&set!=0){
    result=(struct data *)calloc(set,sizeof(struct data));
    for(i=0;i<set;i++){
      scanf("%d%*c",&result[i].num);
      fgets(scorestr,sizeof(scorestr)/sizeof(char),stdin);
      for(j=0;(ch=strtok(j?NULL:scorestr," \n"))!=NULL;j++){
	score[j]=atoi(ch);
      }
      throw=j;
      sum=0;
      k=0;
      frame=1;
      for(j=0;j<throw;j++){
	sum+=score[j];
	if(frame<=9){
	  if(k==0 && score[j]==10){
	    sum+=score[j+1]+score[j+2];
	    frame++;
	    continue;
	  }else if(k==1 && score[j]+score[j-1]==10) sum+=score[j+1];
	  if(++k==2) frame++,k=0;
	}
      }
      result[i].point=sum;
    }
    qsort(result,set,sizeof(struct data),comp);
    for(j=0;j<set;j++){
      printf("%d %d\n",result[j].num,result[j].point);
    }
    free(result);
  }	
  return 0;
}
   
int comp(const void *p1,const void *p2){
  struct data *d1,*d2;
  d1=(struct data *)p1;
  d2=(struct data *)p2;
  if(d1->point==d2->point){
    return d1->num - d2->num;
  }else{
    return d2->point - d1->point;
  }
}   

Measured memory_bytes: 0
/*****/

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <iomanip>	//cout << fixed << setprecision(桁数);
#include <stdexcept>

//#define int long long

using namespace std;
using ll = long long;
using ld = long double;
using vecll = vector<ll>;

#define nextline() (std::cerr << "\n")
#define debug(x) (#x " : " + (x))
#define debug_cout(x) (std::cerr << #x << " : " <<  (x) << "\n")
#define debug_tabcout(n, x) (std::cerr << strMulti("\t",n) << #x << " : " <<  (x) << "\n")
#define debug_headcout(h, x) (std::cerr << h << " : " <<  (x) << "\n")
#define debug_tabheadcout(n, h, x) (std::cerr << strMulti("\t",n) << h << " : " <<  (x) << "\n")

#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; i++)
#define rep1(i, n) for(int i=1, i##_len=(n); i<=i##_len; i++)
#define rrep(i, n) for(int i=(n)-1; i >= 0; i--)
#define rrep1(i, n) for(int i=(n); i > 0; i--)
#define all(x) (x).begin(), (x).end()
#define pair(a, b) make_pair(a, b);
constexpr int INF = 2000000100;
constexpr ll DIV = 1000000007;	// 10e9+7
template<class T> bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
//template<class T> T divup(T a, T b) { if (a % b == 0) { return a / b; } return a / b + 1; }
#define diup(a, b) (a % b == 0 ? a / b : a / b + 1)
#define exist_in(list, value) (list.end() != std::find(all(list),value))
std::string strMulti(std::string t, int n) { std::string out = ""; for (int i = 0; i < n; i++) { out += t; } return out; }
//template<class T> T math_P(T m, T n) { T ret = 1; for (T i = m; i > m - n; i--) { ret *= i; } return ret; }
//template<class T> T math_C(T m, T n) { T ret = mathP(m, n); for (T i = 2; i <= n; i++) { ret /= i; } return ret; }
//template<class T> bool compare_by_b(pair<T, T> a, pair<T, T> b) { if (a.second != b.second) { return a.second < b.second; } return a.first < b.first; }
//template<class T> T math_gcd(T a, T b) { a = abs(a); b = abs(b); if (a < b) { std::swap(a, b); } T tmp; while (b != 0) { tmp = b; b = a % b; a = tmp; } return a; }
//template<class T> T math_lcm(T a, T b) { a = abs(a); b = abs(b); if (a > b) { std::swap(a, b); } if (a == 1) { return b; } T i = a; while (i % b != 0) { i += a; } return i; }
//template<class T1, class T2> bool exist_in(const T1& list, const T2& v) { return (list.end() != std::find(list.begin(), list.end(), v)); }
//template<class T> bool exist_in(const T& c, const typename T::value_type& v) {	return (c.end() != std::find(c.begin(), c.end(), v));}

/*****/

void Main()
{
	int x, a, b;
	cin >> x >> a >> b;
	if (abs(x - a) > abs(x - b))
		cout << "B";
	else
		cout << "A";
}

/*****/

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

	std::cout << std::fixed << std::setprecision(10);


	/*
	while (true)
	{
		Main();
		cout << endl;
	}
	//*/


	Main();

	return 0;
}


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

vector<long long> l;
vector<long long> p;

long long f(int n, long long x) {
  if (n == 0) {
    if (x > 0) return 1;
    else return 0;
  }
  else if (x <= 1 + l[n - 1]) return f(n - 1, x - 1);
  else return p[n - 1] + 1 + f(n - 1, x - 2 - l[n - 1]);
}

void Main() {
  int n;
  long long x;
  cin >> n >> x;

  l.push_back(1);
  p.push_back(1);

  for (int i = 0; i < n; i++) {
    l.push_back(l[i] * 2 + 3);
    p.push_back(p[i] * 2 + 1);
  }

  cout << f(n, x)<< endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}



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

int main(){
	long long a,b,x,c;
	cin >> a >> b >> x;
	
	if(a%x==0){
		c=1;
	}else{
		c=0;
	}
	cout << b/x - a/x +c<< endl;
//	cout << waru(b,x) - (a-1)/x << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int[] num = new int[9];
		boolean key = false;
		for (int i = 0; i < 9; i++) num[i] = sc.nextInt();
		for (int a1 = 0; a1 <= 100 ; a1++) {
			int b1 = num[0] - a1;
			int b2 = num[1] - a1;
			int b3 = num[2] - a1;
			int a2 = num[3] - b1;
			int a3 = num[6] - b1;
			if (a2 + b2 == num[4] 
					&& a2 + b3 == num[5] 
					&& a3 + b2 == num[7] 
					&& a3 + b3 == num[8]) {
				key = true;
				break;
			}
		}
		System.out.println(key?"Yes":"No");
	}
}


Measured memory_bytes: 21844
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
using namespace std;
#define LL long long

int a[305][305];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    LL sum=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int f=0;
            for(int k=1;k<=n;k++)
            {
                if(a[i][j]>a[i][k]+a[k][j])
                {
                    cout<<-1<<endl;
                    return 0;
                }
                if(k!=i&&k!=j&&a[i][j]==a[i][k]+a[k][j]&&!f)f=1;
            }
            if(!f){
                sum+=a[i][j];
            }
        }
    }
    cout<<sum/2<<endl;
}


Measured memory_bytes: 640
import qualified Control.Arrow         as Arrow
    import qualified Data.ByteString.Char8 as BSC8
    import qualified Data.Vector.Unboxed   as VU
    import qualified Data.List             as List
    import qualified Data.Ord              as Ord
     
    main :: IO ()
    main = do
      (x, n) <- getAB
      ps     <- getAN n
      print $ if n == 0 then x else solver x ps
     
    solver :: Int -> VU.Vector Int -> Int
    solver x ps = (\(a, b) -> a) . List.minimumBy (Ord.comparing snd) . map (id Arrow.&&& (abs . flip (-) x)) $ [ i | i <- [0..101], VU.notElem i ps]
     
    getI :: BSC8.ByteString -> Maybe (Int, BSC8.ByteString)
    getI = fmap (Arrow.second BSC8.tail) . BSC8.readInt
    getAB :: IO (Int, Int)
    getAB = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 getI <$> BSC8.getLine
    getAN :: Int -> IO (VU.Vector Int)
    getAN n = VU.unfoldrN n getI <$> BSC8.getLine

Measured memory_bytes: 4992
#include <iostream>
#include <cmath>
#define rad(x) (x*3.14159265359/180)
 
using namespace std;
 
int main() {
        double a,b,C;
    
    cin >> a;
    cin >> b;
    cin >> C;
    
    cout.precision(4); // ????????? 4????????????????????????
    cout.setf(ios::fixed); // ?属???属??即?????????????????即?????????
    
    cout << 1.0 / 2.0 * a * b * sin(rad(C)) << endl;
    cout << a+b+ sqrt(a*a+b*b-2.0*a*b*cos(rad(C))) << endl;
    cout << b*sin(rad(C)) << endl;
    
        return 0;
}
 

Measured memory_bytes: 1312
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int factorial(int n){
  if(n == 0) return 1;
  return n * factorial(n-1);
}

int main(){
  int N;
  cin >> N;
  vector<int> xy[N];
  for(int i=0; i<N; i++){
    int x, y;
    cin >> x >> y;
    xy[i].push_back(x);
    xy[i].push_back(y);
  }

  vector<int> v;
  for(int i=0; i<N; i++){
    v.push_back(i);
  }
  double ans = 0;
  // double ans = 0;
  // double tmp = 0;
  do {
    double tmp = 0;
    for(int i = 0; i<N-1; i++){
      int x1 = xy[v[i]][0];
      int x2 = xy[v[i+1]][0];
      int y1 = xy[v[i]][1];
      int y2 = xy[v[i+1]][1];
      tmp += sqrt(((x1-x2) * (x1-x2)) + ((y1-y2) * (y1-y2)));
      // cout << "i is " << i << endl;
      // tmp += 1;
      // cout << v[i];
    }
    ans += tmp;
    // cout << "tmp is " << tmp << endl;
  } while (next_permutation(v.begin(), v.end()));

  ans /= factorial(N);
  cout << fixed << setprecision(10) << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

#define MAX 100
#define NIL -1

struct node{
  int parent;
  int left;
  int right;
  int sib;
};

struct node T[MAX];
int Deg[MAX];

int setD(int);
int setH(int);

int main(){
  int n;
  int id, l, r;
  int i;

  scanf("%d", &n);

  for(i=0; i<n; i++){
    T[i].parent = T[i].left = T[i].right = T[i].sib = NIL;
    Deg[i] = 0;
  }

  for(i=0; i<n; i++){
    scanf("%d%d%d", &id, &l, &r);

    T[id].left = l;
    T[id].right = r;
    
    T[l].parent = id;
    T[r].parent = id;

    T[l].sib = r;
    T[r].sib = l;

    if(l!=NIL)
      Deg[id]++;

    if(r!=NIL)
      Deg[id]++;
  }

  

  for(i=0; i<n; i++){
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, "
	   , i, T[i].parent, T[i].sib, Deg[i], setD(i), setH(i));

    if(T[i].parent == NIL)
      printf("root\n");

    else if(Deg[i]>0)
      printf("internal node\n");

    else
      printf("leaf\n");
  }
  
  return 0;
}

int setD(int u){
  int dpt=0;
  int par = T[u].parent;
  
  while(par != NIL){
    dpt++;
    par = T[par].parent;
  }

  return dpt;
}

int setH(int u){
  int h1=0, h2=0;

  if(T[u].right != NIL)
    h1 = setH(T[u].right) + 1;
  if(T[u].left != NIL)
    h2 = setH(T[u].left) + 1;

  return (h1>h2) ? h1 : h2;
}



Measured memory_bytes: 2104
#include <cstdio>
#include <algorithm>
#include <map>
#include <atcoder/all>

using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

using mint = atcoder::modint998244353;

i32 bucket[100000];

auto main() -> i32 {
	i32 n;
	scanf("%d", &n);
	for (i32 i = 0; i < 2 * n; ++i) {
		i32 h;
		scanf("%d", &h);
		bucket[h] += 1;
	}

	std::vector<mint> poly;
	std::vector<mint> poly2;
	poly.emplace_back(1);
	poly2.emplace_back(1);
	i32 p = 0;
	for (i32 i = 0; i < 100000; ++i) {
		if (i64 k = bucket[i]; k >= 2) {
			p += bucket[i] / 2;
			std::vector<mint> b;
			b.emplace_back(1);
			mint x = mint(1);
			for (i64 i = 2; i <= k; i += 2) {
				x *= mint((k - i + 2) * (k - i + 1) / 2) / mint(i / 2);
				b.emplace_back(x);
			}
			if (poly.size() <= n / 2) {
				poly = atcoder::convolution(poly, b);
			} else {
				poly2 = atcoder::convolution(poly2, b);
			}
		}
	}
	poly = atcoder::convolution(poly, poly2);
	std::vector<mint> table;
	table.emplace_back(1);
	for (i32 i = 1; i <= n; ++i) {
		mint x = table[i - 1] * mint(2 * i - 1);
		table.emplace_back(x);
	}
	mint ans = mint(0);
	for (i32 i = 0; i <= p; ++i) {
		ans = ans + (i % 2 == 0 ? poly[i] : -poly[i]) * table[n - i];
	}
	printf("%d\n", ans.val());
	return 0;
}


Measured memory_bytes: 4960
N = int(input())
K = int(input())
n = list(map(int, str(N)))
dp = [[[0] * 5 for __ in range(2)] for _ in range(101)]
l = len(n)
dp[0][0][0] = 1
for i in range(l):
    for smaller in range(2):
        for j in range(4):
            for x in range((9 if smaller else n[i]) + 1):
                dp[i + 1][smaller or x < n[i]][j + 1 if x != 0 else j] += dp[i][smaller][j]
print(dp[l][0][K] + dp[l][1][K])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

inline int gi()
{
	int f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

inline LL gl()
{
	LL f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int N = 200003, M = N << 1;

int n, k;
int a[N], b[N];
int s[N]/*i+a_i*/, t[N]/*i-a_i*/;
int ton[M];
LL ans;

int main()
{
    n = gi();
    for (int i = 1; i <= n; i+=1) 
        a[i] = gi(), s[i] = i + a[i], t[i] = i - a[i];
    for (int i = 1; i <= n; i+=1)
        if (s[i] <= 200000) ++ton[s[i]];
    for (int i = n; i >= 1; i-=1)
    {
        if (t[i] <= 0) continue;
        if (t[i] > 200000) continue;
        ans += ton[t[i]];
        if (s[i] <= 200000) --ton[s[i]];
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 6864
import sys
import functools


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return list(map(int, input().split()))


def main():
    input()  # n
    aa = input_ints()

    x = functools.reduce(lambda a, b: a ^ b, aa)

    print(" ".join([str(x^a) for a in aa]))


main()


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

int n;
int ans ;

void f(){
	ans = 0 ;
	for( int i=1 ; i<n ; i++ ){
		for( int j=i+1 ; j<n ; j++ ){
			int m = (j-i+1) * (i+j) / 2 ;
			if( m > n ) break ;
			if( m == n ) ans++ ;
		}
	}
}

int main(){
	
	while( cin >> n , n ){
		f() ;
		cout << ans << endl ;
	}
	
return 0;
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (a + b > c + d) {
    cout << "Left" << endl;
  }
  else if (a + b < c + d) {
    cout << " Right" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
  return 0;
}
    

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

int main(){
  int n,u,d;
  cin >> n;
  u = n/10;
  d = n%1000;
  if(u%111 == 0 || d%111 == 0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

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

using namespace std;
using ll =long long;
using db = double;
using vll = vector<long long>;

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; }
#define che(a,string) cout<<"//"<<string <<"=="<<(a)<<"//" <<endl;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define leftunique(a) {SORT(a);(a).erase(unique((a).begin(),(a).end()),(a).end());}
//leftuniqueは配列から同じ要素のものを取り除く 例 4 6 2 1 3 4 1 2 なら 1 2 3 4 6 になる
#define debug(x)  cout << #x << " = " << (x) << endl;
bool IsInt(double a){int b = a/1;if(a==b){return true;}else {return false;}}
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}
const int mod = 1e9 + 7;
const ll INF = 1LL << 60;
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
//グラフ用
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};	
//ここから書き始める

int main()
{
	cout <<setprecision(10);
	ll n ; 
	cin >> n;
	map<ll,ll> number;
	ll ans = 0;
	rep(i,n){
		ll a;
		cin>>a;

		if(number.count(a)){
			number.at(a)+= 1;
		}else number[a] = 1;

	}
	for(auto x : number){
		//x.first ga key
		//x.second ga value
		if(x.first > x.second){
			ans += x.second;
		}else if(x.second >= x.first){
			ans += x.second - x.first ;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 6272
#include <iostream>
#include<bits/stdc++.h>
#define ll long long int
#define lld long double
#define F first
#define S second
#define f(i,a,b) for(int i=a;i<=b;i++)
#define g(i,a,b) for(int i=a;i>=b;i--)
#define mp make_pair
#define pb push_back
#define mh make_heap
#define ph push_heap
#define pq priority_queue
#define bits(x) __builtin_popcountll(x)
#define op(x) cout<<"Case #"<<x<<": "
using namespace std;
ll mod = 1000000007;
ll INF = 1000000000000000000;

void solve(int t)
{
	ll n, m;
	cin >> n >> m;;
	string s[n];
	ll dp[n + 1][m + 1];
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
	}

	dp[1][1] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (s[i - 1][j - 1] == '.')
			{
				dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
				dp[i][j] %= mod;

			}
		}
	}


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

}

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




	int t = 1;
	//cin >> t;

	for (int i = 1; i <= t; i++)
	{
		solve(i);
	}
}


Measured memory_bytes: 9216
program ABC_079_D_Wall
   implicit none
   integer H, W, d(0:9, 0:9), c(0:9, 0:9), i, j, k, countN
   integer, allocatable :: A(:, :)
   read(*, *) H, W
   do i = 0, 9
      read(*, *) c(i, 0:9)
   end do
   allocate(A(1:H, 1:W))
   do i = 1, H
      read(*, *) A(i, 1:W)
   end do
   do k = 0, 9
       do j = 0, 9
	       do i = 0, 9
               c(i, j) = min(c(i, j), c(i, k) + c(k, j))
		   end do
       end do
   end do
   countN = 0
   do j = 1, W
       do i = 1, H
	       if (A(i, j) /= - 1) then
		       countN = countN + c(A(i, j), 1)
           end if
	   end do
   end do
   write(*, *) countN
end program ABC_079_D_Wall

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ITP1
{
    class ITP1_3_B
    {
        static void Main(string[] args)
        {
            int i = 1;
            while (true)
            {
                int x = int.Parse(Console.ReadLine());
                
                if (x == 0)
                {
                    break;
                }
                else
                {
                    Console.WriteLine($"Case {i}: {x}");
                }
                i++;
            }
        }
    }
}



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

#define INF INT_MAX
#define UINF UINT_MAX
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef std::pair<int,int> pii;

using namespace std;

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

    double a,b;
    cin >> a >> b;

    ll ans = -1;
    ll g_a = (ll)(a*(100.0/8.0));
    ll g_b = (ll)(a*(100.0/10.0));
    // cout << g_a << " " << g_b << endl;
    
    ll aa = 0,bb = 0;
    for(double i = 10;i <= 1250;i+=1.0){
        aa = i * 0.08;
        bb = i * 0.10;
        // cout << aa << " " << bb << endl;
        if(aa == a && bb == b){
            ans = i;
            break;
        }
    }

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

Measured memory_bytes: 256
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include<numeric>

using namespace std;

long long gcd(long long a,long long b){
    if(b==0)return a;
    return gcd(b,a%b);
}

long long lcm(long long a,long long b){
    return (a/gcd(a,b))*b;
}

int main() {
    long long N,T[1000],ans=0;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>T[i];
    }
    ans=T[0];
    for(int i=1;i<N;i++){
        ans=lcm(ans,T[i]);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
N,C,K=map(int,input().split())
T=[int(input()) for _ in range(N)]
T.sort()
t=T[0]
cnt=0
mem=0
for i in range(N):
    if (t+K<T[i])or(mem==C):
        cnt=cnt+1
        t=T[i]
        mem=1
    else:
        mem=mem+1
print(cnt+1)

Measured memory_bytes: 7384
list = []
while True:
  line = raw_input().split(" ")
  if line[0] == "0" and line[1] == "0":
    break
  line = map(int, line)
  #print line
  if line[0] > line[1]:
    temp = line[0]
    line[0] = line[1]
    line[1] = temp
  print " ".join(map(str, line))

Measured memory_bytes: 6452
#include <algorithm>
#include <iostream>
#include <map>

using namespace std;
using ll = long long;

ll N, A, B, C, D, T;
map<ll, ll> m;

ll d(ll n) {
  if (!n)
    return 0;
  else if (m[n])
    return m[n];
  ll ret = min({
      A + n % 2 * D + d(n / 2),
      A + (2 - n % 2) % 2 * D + d((n + 1) / 2),
      B + n % 3 * D + d(n / 3),
      B + (3 - n % 3) % 3 * D + d((n + 2) / 3),
      C + n % 5 * D + d(n / 5),
      C + (5 - n % 5) % 5 * D + d((n + 4) / 5)
    });
  if ((double)D * n < 1e18) ret = min(D * n, ret);
  return m[n] = ret;
}

int main() {
  cin >> T;
  for (int i = 0; i != T; ++i) {
    cin >> N >> A >> B >> C >> D;
    m.clear();
    m[0] = 0;
    m[1] = D;
    cout << d(N) << endl;
  }
}


Measured memory_bytes: 4408
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ab = sorted([[a[i], b[i]] for i in range(n)], key=lambda x: x[1])

    #セグ木の要素数（num）および階層（fl）を計算
    num = 1
    fl = 1
    while num < n:
        num *= 2
        fl+=1
    num -= 1

    #上限（inf）を決定(下限とかに適宜変える)
    inf = 10 ** 9 + 1

    #関数（モノイド、今回はmin）を設定
    monoid=min

    #セグ木を構築
    m=num+n
    segtree = [None] * m
    #segtree[m]以降に代入したい配列を入力していく
    for i in range(num, m):
        segtree[i] = ab[i - num][0]
    #segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
    for i in range(num - 1, -1, -1):
        j=2*i+1
        if j>=m:
            segtree[i]=inf
        else:
            segtree[i] = monoid(segtree[j], segtree[min(j + 1, m - 1)])

    #条件を満たす(サンプルの条件はs以下になること)最大のインデックスを返す関数
    def max_index(s):
        #条件の定義
        func = lambda x: x <= s
        #探していく
        i=0
        while i < num:
            k = 2 * i + 1
            if k + 1 < m:
                if func(segtree[k + 1]):
                    i = k + 1
                    continue
            if k < m:
                if func(segtree[k]):
                    i = k
                    continue
            return - 1
        return i - num
            
    #半開区間[lower,upper)の最小値（とか）を探す関数
    def search_new(lower, upper):
        q = [[0, 1]]  #インデックス、階層
        #返り値を初期化
        ret = inf      
        while q:
            i, f = q.pop()
            #popしたインデックスと階層から、求める下限と上限を算出する
            #幅
            width = pow(2, fl - f)
            #下限と中央と上限
            kagen = (i - pow(2, f - 1) + 1) * width
            chuo = kagen + width // 2
            jogen = kagen + width
            k = 2 * i + 1
            if lower <= kagen and jogen <= upper:
                ret = monoid(ret, segtree[i])
                continue
            if k < m:
                if lower <= kagen and chuo <= upper:
                    ret = monoid(ret, segtree[k])
                elif lower <= chuo:
                    q.append([k, f + 1])
            if k + 1 < m:
                if lower <= chuo and jogen <= upper:
                    ret = monoid(ret, segtree[k + 1])
                elif chuo <= upper:
                    q.append([k + 1, f + 1])
        return ret

    #segtree[i]をsに更新したときにセグ木全体を更新する関数
    def update(i, s):
        segtree[i] = s
        temp = s
        while i!=0:
            k = (i - 1) // 2
            if i % 2 == 1:
                temp = monoid(segtree[min(i + 1, m - 1)], temp)
            else:
                temp = monoid(segtree[i - 1], temp)
            if segtree[k]!=temp:
                segtree[k] = temp
                i = k
                continue
            break

    cnt = 0
    for i in range(n):
        a,b=ab[i][0],ab[i][1]
        if a > b:
            t = max_index(b)
            if t <= i:
                print("No")
                return 0
            update(num + i, a)
            update(num + t, a)
            ab[i][0], ab[t][0] = ab[t][0], a
            cnt+=1
    if cnt <= n - 2:
        print("Yes")
    else:
        print("No")
    
main()

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

int main() {
    //input
    string res,str;
    cin >> str;
    res += str.at(0);
    cin >> str;
    res += str.at(0);
    cin >> str;
    res += str.at(0);
    cout << res;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define N 1000000007
long long a[10000000];
long long m[20000000];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		
		cin>>a[i];
		m[i]=(m[i-1]+a[i]);
	}
	long long sum=0;
	for(int i=2;i<n;i++)
	{
		sum+=(a[i]%N)*(m[i-1]%N)%N;
		sum%=N;
	}
	sum+=(a[0]%N)*(a[1]%N);
	sum%=N;
	cout<<sum;
}

Measured memory_bytes: 6684
#include <bits/stdc++.h>
#define il inline
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define mid ((l+r)>>1)
#define MAXN 3050
#define MAXM 
#define mod
#define inf (1<<30)
#define eps (1e-6)
#define alpha 0.75
#define rep(i, x, y) for(register int i = x; i <= y; ++i)
#define repd(i, x, y) for(register int i = x; i >= y; --i)
#define file(s) freopen(s".in", "r", stdin), freopen(s".my", "w", stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, int> pli;
typedef pair <int, ll> pil;
typedef pair <ll, ll> pll;
template <typename T> il bool chkmin(T &x, T y) {return x > y ? x = y, 1 : 0;}
template <typename T> il bool chkmax(T &x, T y) {return x < y ? x = y, 1 : 0;}
template <typename T> il void read(T &x) {
	char ch = getchar(); int f = 1; x = 0;
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') x = x*10+ch-'0', ch = getchar();
	x *= f;
}
template <typename T, typename... Args> il void read(T &x, Args &...args) {
	read(x), read(args...);
}
int n, b[MAXN << 2], x[MAXN], y[MAXN], tot;
int f[MAXN << 2][MAXN << 2];
int main() {
	read(n);
	rep(i, 1, n) read(x[i], y[i]);
	rep(i, 1, n)
		rep(j, 1, n)
			b[++tot] = x[i] - x[j], b[++tot] = y[i] - y[j];
	sort(b+1, b+tot+1), tot = unique(b+1, b+tot+1) - b - 1;
	#define get(x) (lower_bound(b+1, b+tot+1, x) - b)
	rep(i, 1, n)
		rep(j, 1, n)
			if(i != j) f[get(x[i]-x[j])][get(y[i]-y[j])]++;
	int ans = 0;
	rep(i, 1, tot)
		rep(j, 1, tot)
			chkmax(ans, f[i][j]);
	cout << n - ans << endl;
	return 0;
}

Measured memory_bytes: 233856
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<pair<pair<string, int>, int>> v;
    for (int i = 0; i < N; i++)
    {
        string s;
        int x;
        cin >> s >> x;
        v.push_back(pair<pair<string, int>, int>(pair<string, int>(s, -x), i + 1));
    }

    sort(v.begin(), v.end());
    for (int i = 0; i < N; i++)
    {
        cout << v[i].second << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
  cin >> s;
  if(s[0]=='R' && s[1]=='R' && s[2]=='R')
    cout << 3 << "\n";
  else if (s[0]==s[1] && s[1]=='R')
    cout << 2 << "\n";
  else if(s[1]==s[2] && s[2]=='R')
    cout << 2 << "\n";
  else if(s[0]=='R'|| s[1]=='R' || s[2]=='R')
    cout << 1 << "\n";
  else
    cout << 0 << "\n";
  return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    ll a, b, c;
    cin >> a >> b >> c;
    if(c-(a+b)<0)
    {
        cout<<"No";
    }
    else if ((a + b - c) * (a + b - c) > 4 * a * b)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }

    return 0;
}

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


#define ONSPEED ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define f(i,x,n) for(i=x;i<n;i++)
#define rf(i,x,n) for(i=n;i>x;i--)
#define ll long long
#define GCD(a,b) __gcd(a,b)
#define ff first
#define ss second
#define adios return 0;

/*
tacet aquilae
*/

int main()
{
    ONSPEED;
    ll t,n,k,a,b,c,d,s=0,i,j,flag;
    string x,y;
    cin>>n>>a>>b;
    c= abs(b-a-1);
    if(c & 1) cout<<"Alice\n";
    else cout<<"Borys\n";







    adios;
}
	


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

int n;
int a[100010];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin); 
    freopen("out","w",stdout);
#endif
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  int ans=0;
  for(int i=0;i<n-1;i++){
    if(a[i]==i+1){
      swap(a[i],a[i+1]);
      ans++;
    }
  }
  if(a[n-1]==n)ans++;
  cout<<ans<<endl;
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

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


// 最大公約数
ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}

void solve()
{
  ll N; cin >> N;
  vector<ll> a(N); rep(i, N) cin >> a[i];
  ll ans = 0;
  ll cnt = 0;
  sort(a.begin(), a.end());
  rep(i, N - 1) {
    if(a[i] == a[i + 1]) cnt++;
  }
  ans  = N - ((cnt + 1) / 2) * 2;

  cout << ans << endl;
}


int main(void)
{
  // ll t; cin >> t; rep(i, t)
  solve();
}


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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(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)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}

#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
using ll = long long;

struct Graph {
    struct Edge {
        int from;
        int to;
        ll cost;
        Edge(int a, ll b) : to(a), cost(b) {}
        Edge(int a, int b, ll c) : from(a), to(b), cost(c) {}
    };

    int N;  //頂点数
    std::vector<std::vector<Edge>> edges;   //隣接リスト
    std::vector<ll> dist;   //ノードの深さ
    std::vector<int> deg;   //入次数

    Graph(int n) : N(n), edges(n), dist(n, INF), deg(n, 0) {}

    void connect(int a, int b, ll c) {   //辺を追加
        edges[a].emplace_back(Edge(a, b, c));
        deg[b]++;
    }

    bool visited(int v) {
        return dist[v] < INF;
    }

    void resetDist() {
        for(int i=0; i<N; i++) {
            dist[i] = INF;
        }
    }

    void dfs(int p, int v, ll d) {    //深さ優先探索
        if(visited(v)) return;

        dist[v] = d;

        for(const Edge& e : edges[v]) {
            if(e.to == p) continue;
            dfs(v, e.to, d + e.cost);
        }
    }

    int makeStar(int n) {
        static int id = 0;
        int root = id;
        id++;
        for (int i = 0; i < n - 1; i++) {
            int next = makeStar(1);
            connect(root, next, 1);
            connect(next, root, 1);
        }
        return root;
    }

    int makeTree(int n, const vector<int>& v) {
        if(v[n] == 1) {
            return makeStar(1);
        }
        int x = makeTree(n+1, v);
        int y = makeStar(v[n] - v[n+1]);
        connect(x, y, 1);
        connect(y, x, 1);
        return y;
    }
};

void ng() {
    cout << -1 << endl;
    exit(0);
}

signed main(){
    string s;
    cin >> s;
    int n = s.length();

    if(s.front() == '0' || s.back() == '1'){
        ng();
    }

    vector<int> v{n};

    RREP(i, n/2){
        int a = i + 1, b = n - a;
        if(s[a-1] != s[b-1]) ng();
        if(s[a-1] == '1') v.push_back(a);
    }

    Graph G(n);
    G.makeTree(0, v);

    REP(i, n){
        for(const auto& e : G.edges[i]){
            if(e.from > e.to) continue;
            cout << e.from + 1 << " " << e.to + 1 << '\n';
        }
    }

    return 0;
}


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

int main() {
  int W;
  cin >> W >> W;
  map<int, int> X;
  multiset<int> Y;
  for (int i = 0; i < W; i++) X[i] = i, Y.insert(0);
  for (int h = 1, A, B, C, D; cin >> A >> B;  ) {
    C = -1;
    for(auto j = X.lower_bound(--A);j != X.end() && j -> first <= B; X.erase(j++)){
      D = j -> first;
      C = max(C, X[D]);
      Y.erase(Y.find(D - X[D]));
    }
    if (C + 1 && B < W) X[B] = C, Y.insert(B - C);
    cout << ((Y.size()) ? *Y.begin() + h++ : -1) << "\n";
  }
}


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

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

int main(){

ll N,M,X;
ll tot = 0;
ll ans = INF;

cin >> N >> M >> X;

vector<vector<ll>> A(N,vector<ll>(M));
vector<ll> C(N);

for(ll i = 0;i < N;++i){
    cin >> C[i];
    for(ll j = 0;j < M;++j) cin >> A[i][j];
}

for(ll i = 0;i < (1<<N);++i){

    tot = 0;
    vector<ll> a(M);

    for(ll j = 0;j < N;++j){

        if((i>>j)&1){

            tot = tot + C[j]; 
            for(ll k = 0;k < M;++k) a[k] += A[j][k];
            
        }
        
    }

    bool flg = true;

    for(ll j = 0;j < M;++j) if(a[j] < X) flg = false;
    if(flg) ans = std::min(ans,tot);
    
}

if(ans == INF) cout << "-1" << endl;
else cout << ans << endl;

return 0;

}   


Measured memory_bytes: 3644
import sys
from math import log10

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    
    ans = 0
    for n in range(1, N+1):
        if int(log10(n)) % 2 == 0:
            ans += 1
    
    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9208
#include<iostream>
#include<cstring> 
#include<cstdio>
#define S 0
#define T 201
#define INF 2000000000
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
char s[T+5][T+5];
int px,py,Px,Py,n,m,head[T+5],cnt=1,q[T+5],top,d[T+5],ans,c[T+5];
struct edge{int to,next,w;}e[T*T*10+5];
inline void ins(int f,int t,int w)
{
	e[++cnt]=(edge){t,head[f],w};head[f]=cnt;
	e[++cnt]=(edge){f,head[t],0};head[t]=cnt; 
}
bool bfs()
{
	memset(d,0,sizeof(d));int i,j;
	for(d[q[top=i=1]=S]=1;i<=top;++i)
		for(j=c[q[i]]=head[q[i]];j;j=e[j].next)
			if(e[j].w&&!d[e[j].to]) d[q[++top]=e[j].to]=d[q[i]]+1;
	return d[T];
}
int dfs(int x,int f)
{
	if(x==T) return f;int used=0;
	for(int&i=c[x];i;i=e[i].next)
		if(e[i].w&&d[e[i].to]==d[x]+1)
		{
			int w=dfs(e[i].to,min(f-used,e[i].w));
			used+=w;e[i].w-=w;e[i^1].w+=w;
			if(used==f) return f;
		}
	return d[x]=-1,used;
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
	{
		if(s[i][j]!='.') ins(i,j+n,1),ins(j+n,i,1);
		if(s[i][j]=='S') px=i,py=j,ins(S,i,INF),ins(S,j+n,INF);
		if(s[i][j]=='T') Px=i,Py=j,ins(i,T,INF),ins(j+n,T,INF);
	}
	if(Px==px||Py==py) return 0*puts("-1");
	while(bfs()) ans+=dfs(S,INF);
	printf("%d",ans);
	return 0;
}



Measured memory_bytes: 768
#include <stdio.h>
#include <iostream>
#include <cmath>
using namespace std;

int main(){
  int N;
  cin >> N;
  char c[N];
  for(int i=0;i<N;i++){
    cin >> c[i];
  }
  int count1_W = 0;
  int count_R = 0;
  for(int i=0;i<N;i++){
    if(c[i]=='R') count_R++;
  }
  for(int i=0;i<N;i++){
    if(i<count_R){
      if(c[i]=='W') count1_W++;
    }
  }
  int answer = count1_W;
  printf("%d\n",answer);
  
  return 0;
}

Measured memory_bytes: 3944