akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;

using namespace std;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define SP(a) setprecision(a)
#define SQRT(a) sqrt((long double)(a))
#define DPOW(a, b) pow((long double)(a), (long double)(b))

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll N;
  cin >> N;
  vl A(N, 0);
  REP(i, N) cin >> A[i];
  ll m = MIN(A);
  ll M = MAX(A);
  if (M + m >= 0) {
    ll Mi = ARGMAX(A);
    cout << 2 * (N - 1) << endl;
    REP(i, N) {
      if (i != Mi)
        cout << Mi + 1 << " " << i + 1 << endl;
    }
    REP(i, N) {
      if (i != 0)
        cout << i << " " << i + 1 << endl;
    }
  } else {
    ll mi = ARGMIN(A);
    cout << 2 * (N - 1) << endl;
    REP(i, N) {
      if (i != mi)
        cout << mi + 1 << " " << i + 1 << endl;
    }
    RREP(i, N) {
      if (i != N - 1)
        cout << i + 2 << " " << i + 1 << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 888
//  s.at(0) = toupper(s.at(0));//小文字なら大文字へ//大文字の場合はそのまま
//  s.at(i) = tolower(s.at(i));//大文字なら小文字へ//小文字の場合はそのまま
//s配列に格納した単語を、辞書順にソートする
//getline(cin, s);
//  sort(s.begin(), s.end());
//  string t = "keyence";//で文字列入力ができる
//s.empty() //emptyなら1を出力 入っていれば0を出力
/*//ABC018-B 部分的にreverseをかける解法
int main() {
  string s;
  cin >> s;
  int n;
  cin >> n;
  vector<int>a(n);
  vector<int>b(n);
  rep(i,n) cin>>a.at(i)>>b.at(i);
  rep(i,n)a.at(i)--;
  rep(i,n)b.at(i)--;
  string t;
  rep(i,n){
    t = s;
    for(int k=0;k<=b.at(i)-a.at(i);k++){
      t.at(a.at(i)+k) = s.at(b.at(i)-k);
    }
    s = t;
  }
  cout << s << endl;
}
*///ABC018-B
//  string s;
//  cin >> s;
//  cout << s.at(0) <<endl;
//  cout << s.at(0)-'0' <<endl;
//  Aが16？
//  cout << char(i+48) << endl;//なぜかaは47と得る時がある。+48で出力もaにできる。
//  cout << char(97) << endl;//アスキーコードでaを出力
// sort(b.begin(), b.end());//bという配列を小さい方からソート
// reverse(b.begin(), b.end());//bという配列をリターン
// 10桁でdouble出力するパターン１ 
// printf("%.10f\n", ma);
// 10桁でdouble出力するパターン２
//cout << fixed << setprecision(10);
//  cout << ma << endl;

/*01 02 03 12 13 23　と６回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*///vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
    */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(ll a, ll b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

ll lcm(ll a, ll b)
{
   return a * b / gcd(a, b);
}
int kan_hyaku(int n){
  int kurai = 0;
  for(int i=0;i<3;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int kan_ju(int n){
  int kurai = 0;
  for(int i=0;i<2;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int kan_ichi(int n){
  int kurai = 0;
  for(int i=0;i<1;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int keta(int n){
  int wa = 1;
  while(n>0){
    wa *=10;
    n--;
  }
  return wa;
}
int main() {
  ll n,m;
  cin >> n >> m;
  if(2*n<=m){
    cout << n + (m-2*n) / 4 << endl;
  }
  else{
    cout << m / 2 << endl;
  }
}


Measured memory_bytes: 3608
#include <stdio.h>
#include <stdlib.h>
#include <vector>

int main(){
    int N, M;

    scanf("%d%d", &N, &M);

    char *S = (char *) malloc(sizeof(char) * (N + 2));

    scanf("%s", S);

    int cur_pos = N;
    std::vector<int> inv_eye{};

    while(1){
        int eye;
        int eye_max = 0;

        for(eye = 1; eye <= M; eye ++){
            if(cur_pos - eye == 0){
                // goal
                inv_eye.push_back(eye);
                break;
            }else if(S[cur_pos - eye] == '0'){
                if(eye > eye_max){
                    eye_max = eye;
                }
            }
        }
        if(eye <= M){
            // goal
            for(int i = inv_eye.size() - 1; i >= 0; i --){
                printf("%d ", inv_eye[i]);
            }
            printf("\n");

            return 0;
        }else if(eye_max == 0){
            printf("-1\n");

            return 0;
        }
        inv_eye.push_back(eye_max);
        cur_pos -= eye_max;
    }
}

Measured memory_bytes: 1020
#include <iostream>
#include <algorithm>
#define N 2000000
using namespace std;
main () {
	int n, k, b, a[N] = {};
	cin >> n >> k;
	for(int i=0; i<n; i++) {
		cin >> b;
		a[b-1]++;
	}
	sort(a, a+N, greater<int>());
	int ans = 0;
	for(int i=k; i<n; i++) ans += a[i];
	cout << ans << endl;
}


Measured memory_bytes: 8064
// ConsoleApplication1.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
using namespace std;

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

	int ans = 0;
	for (int i = 0; i < n - 2; i++) {
		if (s.at(i) == 'A' && s.at(i + 1) == 'B' && s.at(i + 2) == 'C') ans++;
	}

	cout << ans << endl;
	return 0;

}

// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント: 
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します 
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこのプロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します


Measured memory_bytes: 3580
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    ll n,m; cin>>n>>m;
    vector<vector<ll>>a(m,vector<ll>(100));
    vector<ll>p(n);
    rep(i,m){
        ll k; cin>>k;
        a[i].resize(k);
        rep(j,k){
            cin>>a[i][j];
        }
    }
    rep(i,m)cin>>p[i];

    ll ans=0;
    bool jud;
    for(ll tmp=0;tmp<(1<<n);tmp++){
        bitset<10>b(tmp);
        jud=true;
        rep(i,m){
            ll cnt=0;
            rep(j,a[i].size()){
                if(b.test(a[i][j]-1))cnt++;
            }
            if(cnt%2!=p[i])jud=false;
        }
        if(jud)ans++;
    }
    cout<<ans<<endl;
}



















































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

int main(){
    int n;
    cin >> n;
    int a[n],b[n];
    priority_queue<P> que;
    rep(i,n){
        int a,b;
        cin >>a >> b;
        que.push(make_pair(-b,a));
    }
    int time=0;
    while(!que.empty()){
        P p = que.top();
        que.pop();
        time+=p.second;
        if(time>-p.first){
            printf("No\n");
            return 0;
        }
    }

    printf("Yes\n");
    

}

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

using namespace std;
int n,q,ans=1;
const int maxn=1e5+5;
char b[maxn];
int main()
{
    scanf("%d%d",&n,&q);
    scanf("%s",b);
    for(int i=1;i<n;i++)
    {
        if(b[i]!=b[i-1])
            ans++;
    }
    int res=max(1,ans-2*q);
    printf("%d",n-res);
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define   ll          long long int
#define   sz          200010
#define   sc(a)       scanf("%lld",&a)
#define   sc2(a,b)    scanf("%lld %lld",&a,&b)
#define   py          printf("Yes\n")
#define   pn          printf("No\n")
using namespace std;


ll num[sz];

int main()
{

    ll n,m,c,a,b,x,i,j,p=0,s;

    cin>>n>>m>>c;

    for(i=1;i<=m;i++)cin>>num[i];

    while(n--)
    {
        s=0;

        for(i=1;i<=m;i++)
        {
            cin>>a;
            s+=(a*num[i]);
        }
        s+=c;
        if(s>0)p++;
    }

    cout<<p<<endl;


    return 0;
}


Measured memory_bytes: 256
#pragma warning (disable:4996)
#include<stdio.h>

int main(void) {
	int n;
	int a[20];
	int b[20];
	int c[19];
	int ans = 0;

	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < n; ++i) {
		scanf("%d", &b[i]);
	}
	for (int i = 0; i < n - 1; ++i) {
		scanf("%d", &c[i]);
	}

	for (int i = 0; i < n; ++i) {
		int j = a[i]-1;
		ans += b[j];
		if (a[i] - 1 == a[i - 1]) {
			ans += c[a[i] - 2];
		}
	}

	printf("%d\n", ans);
}


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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_K = (int)(1e3 + 5);

int n, k;

int field[2 * MAX_K][2 * MAX_K];

int get_size(int x, int y, int i, int j) {
  return field[i][j] - field[i][y] - field[x][j] + field[x][y];
}

int calc(int i, int j) {
  int black = 0;

  black += get_size(0, 0, i, j);                  // current
  black += get_size(i, j, i + k, j + k);          // top right
  black += get_size(i + k, j + k, 2 * k, 2 * k);  // top ritht top right
  black += get_size(i + k, 0, 2 * k, j);          // top
  black += get_size(0, j + k, i, 2 * k);          // right

  int white = n - black;
  int ret = max(black, white);

  return ret;
}

int main(void) {
  // Here your code !
  scanf("%d %d", &n, &k);

  for (int i = 0; i < n; ++i) {
    ll x, y;
    char c;

    scanf("%lld %lld %c", &x, &y, &c);

    if (c == 'W') x += (ll)(k);

    x %= (ll)(2 * k);
    y %= (ll)(2 * k);

    x += 1;
    y += 1;

    field[x][y] += 1;
  }

  for (int i = 1; i <= 2 * k; ++i) {
    for (int j = 1; j <= 2 * k; ++j) {
      field[i][j] += field[i][j - 1];
      field[i][j] += field[i - 1][j];
      field[i][j] -= field[i - 1][j - 1];
    }
  }

  int ans = -1;

  for (int i = 1; i <= k; ++i) {
    for (int j = 1; j <= k; ++j) {
      ans = max(ans, calc(i, j));
    }
  }

  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 16000
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()

p_array = list(map(float, stdin.readline().split()))

dp = [0] * (N+1)
dp[0] = 1

for p in p_array:
    for i in range(N, 0, -1):
        dp[i] = dp[i] * (1-p) + dp[i-1] * p
    dp[0] *= (1-p)


print(sum(dp[(N+1)//2:]))


Measured memory_bytes: 70384
use std::io::*;
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::iter::*;
#[allow(unused_imports)]
use std::cmp::*;

struct Scanner<R: Read> {
    reader: R,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(reader: R) -> Scanner<R> {
        Scanner { reader: reader }
    }

    fn safe_read<T: FromStr>(&mut self) -> Option<T> {
        let token = self.reader.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            token.parse::<T>().ok()
        }
    }

    fn read<T: FromStr>(&mut self) -> T {
        if let Some(s) = self.safe_read() {
            s
        } else {
            writeln!(std::io::stderr(), "Terminated with EOF").unwrap();
            std::process::exit(0);
        }
    }

    fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.read()).collect()
    }

    fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }
}

fn main() {
    std::thread::Builder::new()
        .stack_size(104_857_600)
        .spawn(solve)
        .unwrap()
        .join()
        .unwrap();
}

fn gcd(x: u32, y: u32) -> u32 {
    if x == 0 {
        y
    } else {
        gcd(y % x, x)
    }
}

fn solve() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let x = sc.read();
    let y = sc.read();
    println!("{}", gcd(x, y));
}



Measured memory_bytes: 9076
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
//                       _oo0oo_                         //
//                      o8888888o                        //
//                      88" . "88      ------ hzt1       //
//                      (| -_- |)                        //
//                      0\  =  /0                        //
//                    ___/`---'\___                      //
//                  .' \|     |// '.                     //
//                 / \|||  :  |||// \                    //
//                / _||||| -:- |||||- \                  //
//               |   | \  -  /// |     |                 //
//               | \_|  ''\---/''  |_/ |                 //
//               \  .-\__  '-'  ___/-. /                 //
//             ___'. .'  /--.--\  `. .'___               //
//          ."" '<  `.___\_<|>_/___.' >' "".             //
//         | | :  `- \`.;`\ _ /`;.`/ - ` : | |           //
//         \  \ `_.   \_ __\ /__ _/   .-` /  /           //
//     =====`-.____`.___ \_____/___.-`___.-'=====        //
//                       `=---='                         //
//                                                       //
//                                                       //
//     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~       //
//                                                       //
//                 God-He Bless All.                     //
//           This Code Will Never Explode.               //
//                                                       //
//                                                       //
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
const int Size=1<<16;
char buffer[Size],*head,*tail;
inline char Getchar() {
    if(head==tail) {
        int l=fread(buffer,1,Size,stdin);
        tail=(head=buffer)+l;
    }
    if(head==tail) return -1;
    return *head++;
}
inline int read() {
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=3010;
int n,A[maxn],first[maxn],nxt[maxn<<1],to[maxn<<1],e;
void AddEdge(int v,int u) {
	to[++e]=v;nxt[e]=first[u];first[u]=e;
	to[++e]=u;nxt[e]=first[v];first[v]=e;
}
int work(int x) {
	int ok=1;
	for(int i=first[x];i;i=nxt[i]) if(A[to[i]]<A[x]&&(!work(to[i]))) return 1;
	return 0;
}
int main() {
	n=read();
	rep(i,1,n) A[i]=read();
	rep(i,1,n-1) AddEdge(read(),read());
	rep(i,1,n) if(work(i)) printf("%d ",i);
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(){
 char S[10];
 scanf("%s",S);
 char T[strlen(S)+1];
 scanf("%s",T);
 if(strncmp(S,T,strlen(S))==0){
  if(strlen(T)==strlen(S)+1)printf("Yes");
   else printf("No");
 }else{
 printf("No");
 }
 return 0;
}

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

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


Measured memory_bytes: 256
n=int(input())
import collections
d=collections.defaultdict(int)

def luca(n):
    if n in d:
        return d[n]
    
    if n==0:
        return 2
    elif n==1:
        return 1
    else:
        tmp=luca(n-1)+luca(n-2)
        d[n]=tmp
        return tmp

print(luca(n))

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const ll INF=0x3f3f3f3f;
string in;
void solve(int T){
	cin>>in;
	if(in=="RRR")puts("3");
	else if(in=="RRS")puts("2");
	else if(in=="RSR")puts("1");
	else if(in=="SRR")puts("2");
	else if(in=="RSS")puts("1");
	else if(in=="SRS")puts("1");
	else if(in=="SSR")puts("1");
	else if(in=="SSS")puts("0");
}
signed main(){
	int t=1;
	//scanf("%d",&t);
	for(int i=1;i<=t;i++){
		solve(i);
	}
}

Measured memory_bytes: 3508
import java.io.*
import java.util.*
import kotlin.math.*

fun main(){
	val f = BufferedReader(InputStreamReader(System.`in`))

	val (n,m) = f.readLine().split(" ").map{it.toInt()}

	val max = n*4
	val min = n*2

	if(m%2 == 0 && m >= min && m <= max){
		println("Yes")
	} else {
		println("No")
	}
}


Measured memory_bytes: 36288
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var scanner = bufio.NewScanner(os.Stdin)

func scanInt() int {
	scanner.Scan()
	a, err := strconv.Atoi(scanner.Text())
	if err != nil {
		fmt.Println(err)
	}
	return a
}

func main() {
	scanner.Split(bufio.ScanWords)

	h := scanInt()
	n := scanInt()

	a := make([]int, n)
	b := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = scanInt()
		b[i] = scanInt()
	}

	dp := make([]int, h+1)
	dp[0] = 0

	for i := 1; i <= h; i++ {
		min := math.MaxInt32
		for j := 0; j < n; j++ {
			if a[j] <= i {
				v := b[j] + dp[i-a[j]]
				if v < min {
					min = v
				}
			} else {
				if b[j] < min {
					min = b[j]
				}
			}
		}
		dp[i] = min
	}
	fmt.Println(dp[h])
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(rng(v),x)!=v.end()
#define incls(s,c) s.find(c)!=string::npos
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bit(n,k) ((n>>k)&1) // nのk bit目
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using vt = vector<T>;
const int mod = 1000000007;
const long double EPS = 1e-15;
const int INF = (1<<30)-1;
//const ll INF = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
//inline int in() { int x; scanf("%d",&x); return x;}
template<class T = int> inline T in() { T x; cin >> x; return (x);}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main () {
  long double a, b, c;
  cin >> a >> b >> c;
  if (sqrt(a) + sqrt(b) + EPS < sqrt(c)) yn;
  return 0;
}

Measured memory_bytes: 256
#include <map>
#include <algorithm>
#include <cassert>
#include <climits>
#include <complex>
#include <cstdio>
#include <string>
#include <iostream>
#include <queue>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using ll = long long;
using ld = long double;

template<class T> bool chmin(T &a, T b) { return a>b?(a=b,true):false; }
template<class T> bool chmax(T &a,T  b) { return a<b?(a=b,true):false; }
#define forn(i,x,y) for(int i=(x);i<(int)(y);i++)
#define rep(i,y) for(int i=0;i<(int)(y);i++)
#define repb(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)

template<int M, bool IsPrime = false>
class Modulo {
  using ll = long long;
  int n;
  static enable_if_t<IsPrime, ll> inv(ll a, ll p) {
    return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
  }
public:
  Modulo () : n(0) {;}
  Modulo (int m) : n(m) {
    if (n >= M) n %= M;
    else if (n < 0) n = (n % M + M) % M;
  }
  Modulo (ll m) {
    if (m >= M) m %= M;
    else if (m < 0) m = (m % M + M) % M;
    n = m;
  }
  explicit operator int() const { return n; }
  explicit operator ll() const { return n; }
  bool operator==(const Modulo &a) const { return n == a.n; }
  Modulo operator+=(const Modulo &a) { n += a.n; if (n >= M) n -= M; return *this; }
  Modulo operator-=(const Modulo &a) { n -= a.n; if (n < 0) n += M; return *this; }
  Modulo operator*=(const Modulo &a) { n = (ll(n) * a.n) % M; return *this; }
  Modulo operator+(const Modulo &a) const { Modulo res = *this; return res += a; }
  Modulo operator-(const Modulo &a) const { Modulo res = *this; return res -= a; }
  Modulo operator*(const Modulo &a) const { Modulo res = *this; return res *= a; }
  Modulo operator^(int n) const {
    if (n == 0) return Modulo(1);
    const Modulo a = *this;
    Modulo res = (a * a) ^ (n / 2);
    return n % 2 ? res * a : res;
  }
  enable_if_t<IsPrime, Modulo> operator/(const Modulo &a) const {
    return *this * inv(ll(a), M);
  }
};

const int mod = 1000000007;
using Mod = Modulo<mod, true>;

int main() {
    ll N; cin >> N;
    Mod ten(10);
    Mod eig(8);
    Mod two(2);
    Mod nine(9);
    cout << (int) ((ten ^ N) - (two * (nine ^ N)) + (eig ^ N)) << endl;
}

Measured memory_bytes: 3192
import Control.Monad
import Control.Applicative
import Data.List
import qualified Data.Map as Map
import Data.Array
import qualified Data.ByteString.Char8 as BC
import Data.Maybe
import qualified Data.Set as Set
import qualified Data.Sequence as Sq
import Data.Sequence (ViewL(..),ViewR(..),(><),(<|),(|>),Seq)

bsreadInt :: BC.ByteString -> Int
bsreadInt = fst . fromJust . BC.readInt
--グラフの２頂点の結合を幅探索で調べて出力．

main = do
    [n,m] <- map bsreadInt . BC.words <$> BC.getLine --n頂点，m本の辺
    ab <- map ((map bsreadInt . BC.words)) <$> replicateM m BC.getLine -- a-->b :path のリスト
    let q = Sq.singleton [1]
    let chk = Set.singleton 1

    print $ length $ filter (==False) [connectchk q n (Set.union (Set.fromList (ab \\ [ab!!(k-1)] ) ) (Set.fromList (map reverse (ab \\ [ab!!(k-1)] )) )) chk | k <- [1..m]]

connectchk :: Sq.Seq [Int] -> Int -> Set.Set [Int] -> Set.Set Int -> Bool
connectchk q n adjs chk = foldr (&&) True [ (bsearch q n g adjs chk) /= [] | g <- [2..n] ]
         
adjset :: Int -> Int -> Set.Set [Int] ->  Set.Set Int -> [Int]
adjset x n adjs chk  = [l | l<-[1..n] , Set.member [x,l] adjs == True , Set.member l chk == False]

bsearch :: Sq.Seq [Int] -> Int -> Int -> Set.Set [Int] -> Set.Set Int -> [Int]
bsearch q n g adjs chk = if Sq.length q == 0
                         then []
                         else if head (sqleft q) == g
                              then reverse $ sqleft q
                              else bsearch q2 n g adjs chk2
                                where qa = sqleft q
                                      q2 = (Sq.drop 1 q) >< (Sq.fromList add)
                                      add = [x : qa | x <- adjset (head qa) n adjs chk]
                                      chk2 = Set.union chk (Set.fromList (adjset (head qa) n adjs chk))
                                      
sqleft :: Seq a -> a
sqleft q = sqleft_(Sq.viewl q)
sqleft_ :: ViewL a -> a
sqleft_ (x :< xs) = x
sqright :: Seq a -> a
sqright q = sqright_(Sq.viewr q)
sqright_ :: ViewR a -> a
sqright_ (xs :> x) = x

    

Measured memory_bytes: 1276
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(obj) (obj).begin(),(obj).end() 
#define dump(x)  cout << #x << " = " << (x) << endl;
typedef long long lint;
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	cout<<max({a,b,c})*9+a+b+c<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
int b[110000];
int c[110000];
int segtree[2][262144];
int query(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return 999999999;
	if(c<=a&&b<=d)return segtree[f][e];
	return min(query(a,(a+b)/2,c,d,e*2,f),query((a+b)/2+1,b,c,d,e*2+1,f));
}
void update(int a,int b,int c){
	b+=131072;
	while(b){
		segtree[a][b]=min(segtree[a][b],c);
		b/=2;
	}
}
int L[110000];
int R[110000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",b+i);
	int ret=0;
	for(int i=0;i<262144;i++)segtree[0][i]=segtree[1][i]=999999999;
	int at=-1;
	for(int i=0;i<a;i++){
		if(b[i]==0)at=i;
		L[i]=at;
	}
	at=-1;
	for(int i=a-1;i>=0;i--){
		if(b[i]==0)at=i;
		R[i]=at;
	}
	for(int i=0;i<a;i++){
		if(b[i]<0){
			update(0,i,-b[i]+i);
			update(1,i,-b[i]-i);
		}
	}
	for(int i=0;i<a;i++){
		if(b[i]>0){
			int t=0;
			if(~L[i]){
				int val=query(0,131071,L[i],i,1,0);
		//		printf("%d ",val-i);
				t=max(t,val-i);
			}
			if(~R[i]){
				int val=query(0,131071,i,R[i],1,1);
		//		printf("%d ",val+i);
				t=max(t,val+i);
			}
		//	printf("%d\n",min(t,b[i]));
			ret+=min(t,b[i]);
		}
	}
	printf("%d\n",ret);
}

Measured memory_bytes: 4264
#include <iostream>

int main() {
  int N, T;
  std::cin >> N >> T;

  int minc = 2000;
  for (int i = 0; i < N; i++) {
    int c, t;
    std::cin >> c >> t;
    if (t <= T && minc > c) {
      minc = c;
    }
  }

  if (minc > 1000) {
    std::cout << "TLE" << std::endl;

  } else {
    std::cout << minc << std::endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int DP[50][500][500];

int main() {
  for(int i=0;i<50;++i) {
    for(int j=0;j<500;++j) {
      for(int k=0;k<500;++k) {
        DP[i][j][k] = inf;
      }
    }
  }
  int N, Ma, Mb;
  cin>>N>>Ma>>Mb;
  int a[N], b[N], c[N];
  for(int i=0;i<N;++i) cin>>a[i]>>b[i]>>c[i];
  DP[0][0][0] = 0;
  DP[0][a[0]][b[0]] = c[0];
  for(int i=0;i<N-1;++i) {
    for(int j=0;j<500;++j) {
      for(int k=0;k<500;++k) {
        if(DP[i][j][k]<inf) {
          DP[i+1][j+a[i+1]][k+b[i+1]] = min(DP[i+1][j+a[i+1]][k+b[i+1]], DP[i][j][k]+c[i+1]);
          DP[i+1][j][k] = min(DP[i+1][j][k], DP[i][j][k]);
        }
      }
    }
  }
  int ans = inf;
  for(int i=1;(i*Ma<500) && (i*Mb<500);++i) {
    ans = min(ans, DP[N-1][i*Ma][i*Mb]);
  }
  if(ans==inf) cout<<-1<<endl;
  else cout<<ans<<endl;
}



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

int main(){
	int n, a, b, c;
	int d[101];
	
	cin >> n >> a >> b >> c ;
	for(int i=0 ; i < n ; i++ ){
		cin >> d[i];
	}
	sort( d , d+n );
	
	double ans = 0;
	int price, cal, now_price, now_cal;
	price = now_price = a;
	cal = now_cal = c;
	for(int i=n-1 ; i >= 0 ; i-- ){
		now_price += b;
		now_cal += d[i];
		if( (double)cal / price < (double)now_cal / now_price ){
			cal = now_cal;
			price = now_price;
		}
	}
	cout << cal / price << endl;
}

Measured memory_bytes: 0
def main():
    a,b,c,d=map(int,input().split(' '))
    ans = 0
    alice=[1 if a<=i<b else 0 for i in range(100)]
    bob=[1 if c<=i<d else 0 for i in range(100)]
    for i,j in zip(alice,bob):
        if i+j ==2:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()


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

struct UF {
	UL N;
	vector<UL> V;
	void init(UL n) {
		N = n; V.resize(N);
		rep(i, N) V[i] = i;
	}
	UL root(UL a) {
		if (V[a] == a) return a;
		return V[a] = root(V[a]);
	}
	void unite(UL r, UL s) {
		V[root(s)] = root(r);
	}
};

UL N, M;
deque<UL> E[10000];
pair<UL, UL> J[100000];
UF G;
UL F[10000] = {};

void unite(UL r, UL s) {
	if (E[r].size() < E[s].size()) {
		swap(E[r], E[s]);
		for (auto i = E[s].rbegin(); i != E[s].rend(); i++)
			E[r].push_front(*i);
	}
	else {
		for (auto i = E[s].begin(); i != E[s].end(); i++)
			E[r].push_back(*i);
	}
	E[s].clear();
	G.unite(r, s);
}

bool DFS(UL p, UL pre = ~0u) {
	F[p] |= 3;
	rep(i, E[p].size()) {
		UL e = G.root(E[p][i]);
		if (e == p) continue;
		if (F[e] & 2) {
			unite(e, p);
			F[p] &= ~2u; return true;
		}
		if (F[e] & 1) continue;
		bool res = DFS(e, p);
		e = G.root(e);
		if (e == p) res = false;
		if (res) {
			unite(e, p);
			F[p] &= ~2u; return true;
		}
	}
	F[p] &= ~2u; return false;
}

int main() {
	scanf("%u%u", &N, &M);
	G.init(N);
	rep(i, M) {
		UL u, v; scanf("%u%u", &u, &v);
		J[i] = { u,v };
		E[u].push_back(v);
	}
	rep(i, N) {
		if (F[i]) continue;
		DFS(i);
	}
	rep(i, N) F[i] = 0;
	rep(i, N) {
		E[i].clear();
		F[G.root(i)] |= 0b11;
	}
	rep(i, M) {
		J[i].first = G.root(J[i].first);
		J[i].second = G.root(J[i].second);
		if (J[i].first == J[i].second) continue;
		F[G.root(J[i].first)] &= ~1u;
		F[G.root(J[i].second)] &= ~2u;
	}
	UL C[4] = {};
	rep(i, N) {
		C[F[i]]++;
	}
	UL ans = max(C[1], C[2]) + C[3];
	if (max(C[1], C[2]) == 0 && C[3] == 1) ans = 0;
	printf("%u\n", ans);
	return 0;
}



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

bool check(int i,vector<int> &p){
    int flag=1;
    for(int k=0;k<p.size();k++){
        if(i==p.at(k)){
            flag=0;
        }
    }
    return flag;
}

int main(){
    int X,N;
    cin >> X >> N;

    vector<int> p(N,0);
    rep(i,N){
        cin >> p.at(i);
    }

    int mint=100000000;
    int ans=0;
    int temp=0;
    rep(i,1000){
        if(check(i,p)){
            if(i<X){
                temp=mint;
                mint=min(mint,X-i);
                if(mint<temp){
                    ans=i;
                }
                
            }else if(i>X){
                temp=mint;
                mint=min(mint,i-X);
                if(mint<temp){
                    ans=i;
                }
            }else{
                ans=i;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int n, l;
    vector<int> a;
    cin >> n >> l;
    a.assign(n, 0);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }

    for(int i=1;i<n;i++){
        if(a[i]+a[i-1] >= l){
            puts("Possible");
            for(int j=1;j<i;j++){
                cout << j << endl;
            }
            for(int j=n-1;j>=i;j--){
                cout << j << endl;
            }
            break;
        }else if(i == n-1){
            puts("Impossible");
            return 0;
        }
    }
}


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

int main() {
  int n; cin >> n;
  double ans = 0;
  while (n--) {
    double x; string u; cin >> x >> u;
    ans += u == "JPY" ? x : x * 380000;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <string>
#include <string.h>
#include <sstream>
#include <ctime>

using namespace std;

#define eps 1e-12
#define pi 3.14159265358979323846
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define bgn begin
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair<ll,ll>







ll n,sum,t;
char s[20];






void solve()
{
	cin>>(s+1);
	n=strlen(s+1);
	sum=0;
	for(int i=0;i<(1<<(n-1));i++)
	{
		t=s[1]-'0';
		for(int j=1,k=2;j<(1<<(n-1));j<<=1,k++)
		{
			if(i&j)
			{
				sum+=t;
				t=s[k]-'0';
			}
			else
			{
				t=(t*10)+s[k]-'0';
			}
		}
		sum+=t;
	}
	cout<<sum<<"\n";
}

int main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef localProject
	freopen("in.txt","r",stdin);
#endif
	solve();
	return 0;
}

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

typedef long long ll;

using namespace std;

const ll inf=1000000007;

ll n, m, x[500005], y[500005], kx[500005], ky[500005], jx=0, jy=0, q;
map<ll,ll> ma;

int main()
{
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    memset(kx,0,sizeof(kx));
    memset(ky,0,sizeof(ky));
    cin >> n >> m >> q;
    while(q--)
    {
        ll u, v;
        cin >> u >> v;
        x[u]++;
        y[v]++;
        ma[u*1000000+v]=1;
    }
    ll x2=0;
    for(int i=1;i<=300005;i++)
    {
        x2=max(x[i],x2);
    }
    for(int i=1;i<=300005;i++)
    {
        if(x[i]==x2)
        {
            kx[jx]=i;
            jx++;
        }
    }
    ll y2=0;
    for(int i=1;i<=300005;i++)
    {
        y2=max(y[i],y2);
    }
    for(int i=1;i<=300005;i++)
    {
        if(y[i]==y2)
        {
            ky[jy]=i;
            jy++;
        }
    }
    ll ans=0;
    for(int i=0;i<jx;i++)
    {
        for(int j=0;j<jy;j++)
        {
            if(ma[kx[i]*1000000+ky[j]]!=1)
            {
                ans=y2+x2;
                break;
            }
        }
        if(ans!=0)
        {
            break;
        }
    }
    ans=max(ans,x2+y2-1);
    cout<< ans << endl;
    return 0;
}


Measured memory_bytes: 38016
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<50;
const double pi=acos(-1);
const double eps=1e-6;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,-0};
const int DX[8]={-1,-1,-1,0,1,1,1,0},DY[8]={1,0,-1,-1,-1,0,1,1};

ll n;
vpll a;

int main(){
	cin>>n;
	a=vpll(n);
	ll R_max=0,R_min=INF,B_max=0,B_min=INF,im,IM,res;
	for(int i=0;i<n;i++){
		ll x,y;
		cin>>x>>y;
		if(x>y) swap(x,y);
		a[i]={x,y};
		R_min=min(R_min,x);
		B_max=max(B_max,y);
	}
	for(int i=0;i<n;i++){
		if(a[i].first==R_min) im=i;
		if(a[i].second==B_max) IM=i;
	}
	for(int i=0;i<n;i++){
		R_max=max(R_max,a[i].first);
		B_min=min(B_min,a[i].second);
	}
	res=(R_max-R_min)*(B_max-B_min);
	if(im!=IM&&n==2){
		res=min(res,(B_max-R_min)*abs(R_max-B_min));
	}
	else if(im!=IM){
		R_max=B_max;
		vpll b;
		for(int i=0;i<n;i++) if(i!=im&&i!=IM) b.push_back(a[i]);
		sort(b.begin(),b.end());
		vl bm(n-1),BM(n-1);
		bm[0]=min(a[im].second,a[IM].first);
		BM[0]=max(a[im].second,a[IM].first);
		for(int i=1;i<n-1;i++){
			bm[i]=min(bm[i-1],b[i-1].second);
			BM[i]=max(BM[i-1],b[i-1].second);
		}
		for(int i=0;i<=n-2;i++){
			B_max=max((i==n-2?-1:b[n-3].first),BM[i]);
			B_min=min((i==n-2?INF:b[i].first),bm[i]);
			res=min(res,(R_max-R_min)*(B_max-B_min));
		}
	}
	cout<<res<<endl;
}

Measured memory_bytes: 10476
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef vector<pair<ll,ll> > vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>(b);--i)
const int MOD = 1000000007;
const int MAX = 510000;

int main(){
  string s;cin>>s;
  if(s=="ABC"){cout<<"ARC"<<endl;}
  else{cout<<"ABC"<<endl;}
}




Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct UnionFind{
  vector<int> r,p;
  UnionFind(){}
  UnionFind(int size){init(size);}
  void init(int size){
    r.resize(size,0);
    p.resize(size,0);
    for(int i=0;i<size;i++) r[i]=1,p[i]=i;
  }
  int find(int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
  }
};

signed main(){
  int n,q;
  cin>>n>>q;
  UnionFind uf(n);
  for(int i=0;i<q;i++){
    int c,x,y;
    cin>>c>>x>>y;
    if(c) cout<<uf.same(x,y)<<endl;
    else uf.unite(x,y);
  }
  return 0;
}


Measured memory_bytes: 3228
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n, m, x;
    cin >> n >> m >> x;
    vector<int> v(n);
    for (auto &&i : v) scanf("%d", &i);
    using P = pair<int, int>;
    int N = n*2*(x+1);
    vector<vector<P>> G(N);
    for (int i = 0; i < m; ++i) {
        int a, b, d;
        scanf("%d %d %d", &a, &b, &d);
        a--; b--;
        G[a].emplace_back(b, d);
        G[b].emplace_back(a, d);
    }
    auto f = [&x](int i, int j, int k){
        return i*2*(x+1) + j*(x+1) + k;
    };

    vector<int> d(N, INF<int>);
    priority_queue<P, vector<P>, greater<>> Q;
    d[f(0, 0, x)] = 0;
    Q.emplace(0, f(0, 0, x));
    while(!Q.empty()){
        int cost, i;
        tie(cost, i) = Q.top(); Q.pop();
        int a = i/(2*(x+1)), b = (i/(x+1)) & 1, c = i % (x+1);
        if(d[i] < cost) continue;
        auto update = [&](int x, int p) -> void{
            if(d[x] <= p) return;
            d[x] = p;
            Q.emplace(d[x], x);
        };
        for (auto &&e : G[a]) {
            int to, val; tie(to, val) = e;
            if(v[to] == 1){
                update(f(to, b, max(0, c-val)), cost+val);
            }else if(v[to] == 0) {
                if(b == 0 || max(0, c-val) == 0) update(f(to, 0, x), cost+val);
            }else {
                if(b == 1 || max(0, c-val) == 0) update(f(to, 1, x), cost+val);
            }
        }
    }
    int ans = INF<int>;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j <= x; ++j) {
            ans = min(ans, d[f(n-1, i, j)]);
        }
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 113416
package main

import "fmt"

var (
	a, b  int
	count int
)

func main() {
	fmt.Scan(&a, &b)
	for i := a; i <= b; i++ {
		if isPalindorome(i) {
			count++
		}
	}

	fmt.Println(count)
}

func isPalindorome(x int) bool {
	if x/10000 == x%10 {
		y := (x - ((x / 10000) * 10000)) / 10
		if y/100 == y%10 {
			return true
		}
	}

	return false
}


Measured memory_bytes: 512
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
    int a, d, i;
    int[] b = new int[3];
    int[] c = new int[3];
    c[0] = 1000; c[1] = 500; c[2] = 100;
    for(;;){
      a = sc.nextInt(); d = sc.nextInt();
      if(a == 0 && d == 0)break;
      a = d - a;
      for(i = 0;i < 3;i++){
        b[i] = a / c[i];
        a -= b[i] * c[i];
      }
      out.printf("%d %d %d%n", b[2], b[1], b[0]);
    }

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

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

void mkvec(vector<int>&v,int base,int limit){
	int i=base;
	while(i<=limit){
		v.emplace_back(i);
		i*=base;
	}
}

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<int>num(1,1);
	mkvec(num,6,n),mkvec(num,9,n);
	vector<vector<int>>dp(num.size()+1,vector<int>(n+1,1e9)); dp.front().front()=0;
	for(int i=0;i<num.size();++i){
		for(int j=0;j<=n;++j){
			if(j<num.at(i))dp.at(i+1).at(j)=dp.at(i).at(j);
			else dp.at(i+1).at(j)=min(dp.at(i).at(j),dp.at(i+1).at(j-num.at(i))+1);
		}
	}
	cout<<dp.back().back()<<"\n"s;
}


Measured memory_bytes: 8704
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    S = input().rstrip()
    counter = defaultdict(int)
    mod = 2019
    counter[0] += 1
    num = 0
    d = 1
    for c in S[::-1]:
        num += int(c) * d
        num %= mod
        counter[num] += 1
        d *= 10
        d %= mod
    ans = 0
    for v in counter.values():
        ans += (v * (v-1)) // 2
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9724
// AOJ 2431: House Moving
// 2017.12.30 bal4u@uu

#include <stdio.h>

long long seg[262145]; int sz;		// 2^18 = 262144
char buf[600000], *p;

int in()
{
	int n = 0;
	while (*p >= '0') n = 10*n + (*p++ & 0xf);
	p++;
	return n;
}

// update kth value to v
void update(int k, long long v)
{
	int t;
	k += sz-1;
	seg[k] = v;
	while (k > 0) {
		if (!(k & 1)) k--;
		t = k, k >>= 1;
		v = seg[t++]; if (v < seg[t]) v = seg[t];
		seg[k] = v;
	}
}

// get max value in [a, b)
long long query(int a, int b, long long k, int l, int r) 
{
	int m;
	long long lmax, rmax;

	if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return seg[k];
	k <<= 1, m = (l + r) >> 1;
    lmax = query(a, b, ++k, l, m);
    rmax = query(a, b, ++k, m, r);
    if (lmax < rmax) lmax = rmax; 
    return lmax;
}

int main()
{
	int n, x, i;
	long long ans;

	fgets(p=buf, 10, stdin), n = in();

	sz = 1; while (sz < n) sz <<= 1;

	fgets(p=buf, sizeof(buf), stdin);
	for (i = 0; i < n; i++) {
		x = in();
		update(x, (long long)x + query(1, x, 0, 0, sz));
	}

	ans = (((long long)n*(n+1)) >> 1) - query(1, n+1, 0, 0, sz);
	printf("%lld\n", ans);
	return 0;
}

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

using ll = long long;

void max_self(ll& a, ll b) {
    a = max(a, b);
}
//~ const int INF = 1e9 + 5;

int main() {
    int n,W;
    scanf("%d%d", &n,&W);
    vector<ll> dp(W+1);
    for(int item=0;item<n;++item){
        int weight,value;
        scanf("%d%d",&weight,&value);
            // dp[0] -> dp[3] -> dp[6]
        for(int weight_already = W - weight; weight_already >= 0; --weight_already) {
            max_self(dp[weight_already+weight], dp[weight_already] + value);
        }
         // for(int i = 0; i <= W; ++i) cout<<dp[i]<<" ";
          //cout<<endl;
    }
    ll answer = 0;
    for(int i = 0; i <= W; ++i) {
        max_self(answer, dp[i]);
    }
    printf("%lld\n", answer);
}




Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,m) for(long long i=0; i<m; i++)
#define per(i,m) for(long long i=m-1; i>=0; i--)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define ROF(i,n,m) for(long long i=n-1; i>=m; i--)
#define SORT(v,n) do{sort(v,v+n);reverse(v,v+n);}while(0)
#define all(x) (x).begin(),(x).end()
#define EPS (1e-7)
#define INF (1e18)
#define PI (acos(-1))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
typedef pair<ll, ll> LP;

ll POW(ll x,ll n){
  if(n==0)return 1;
  if(n%2==0)return POW(x*x%MOD,n/2);
  return x*POW(x,n-1)%MOD;
}

ll gcd(ll u, ll v) {
  ll r;
  while (0 != v) {
    r = u % v; u = v; v = r;
  }
  return u;
}
 
ll KAI(ll m)
{
  if(m<0) return 0;
  if(m==0) return 1;
  return m*KAI(m-1)%MOD;
}
 
ll extGCD(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extGCD(b, a%b, y, x);
    y -= a / b * x;
    return d;
}
 
inline ll mod(ll a, ll m) {
    return (a % m + m) % m;
}
 
ll modinv(ll a) {
    ll x, y;
    extGCD(a, MOD, x, y);
    return mod(x, MOD);
}
 
ll COM(ll m,ll n)
{
  if(m<n) return 0;
  if(n<0) return 0;
  if(n==0) return 1;
  if(m==n) return 1;
  return KAI(m)%MOD*modinv(KAI(n)%MOD*KAI(m-n)%MOD)%MOD;
}

ll DEC(ll x,ll m,ll n)
{
  return x%POW(m,n+1)/POW(m,n);
}

ll keta(ll x,ll n)
{
  if(x==0)return 0;
  return keta(x/n,n)+1;
}

ll DIV(ll x,ll n)
{
  if(x==0)return 0;
  return x/n+DIV(x/n,n);
}

ll ORD(ll x,ll n)
{
  if(x==0)return INF;
  if(x%n!=0)return 0;
  return 1+ORD(x/n,n);
}

int main()
{
  ll n,t[1000],m,p[1000],x[1000],c;
  cin >> n;
  c=0;
  rep(i,n)cin >> t[i];
  cin >> m;
  rep(i,m)cin >> p[i] >> x[i];
  rep(i,n)c+=t[i];
  rep(i,m)printf("%lld\n",c-t[p[i]-1]+x[i]);
}

Measured memory_bytes: 256
from itertools import combinations

n=int(input())
lst=list(map(int,input().split()))
count=0
for x in combinations(lst,3):
    work=sorted(x)
    if work[0]==work[1] : continue
    if work[1]==work[2] : continue
    if work[2]>=work[0]+work[1] : continue
    count+=1

print(count)

Measured memory_bytes: 9184