akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e+9+7;

ll mpow(ll x, ll n){
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % MOD;
        x = x*x % MOD;
        n = n >> 1;
    }
    return ans;
}

ll n_mod(ll x){
    ll ans=1;
    while(x>0){
        ans*=(x%MOD);
        ans%=MOD;
        x--;
    }
    return ans;
}
int main(){
    int X,Y;
    cin >> X >> Y;
    ll a,b,ans;
    if((2*X-Y)%3==0){
        if((2*X-Y>=0)&&(2*Y-X>=0)){
            a=(2*Y-X)/3;
            b=(2*X-Y)/3;
            ans=n_mod(a+b)%MOD;
            ll ans_a=n_mod(a)%MOD;
            ll ans_b=n_mod(b)%MOD;
            ans*=mpow(ans_a,MOD-2);
            ans%=MOD;
            ans*=mpow(ans_b,MOD-2);
            ans%=MOD;
            
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, c) for (int i = 0; i < (int)c; i++)
int main()
{
	int n;
	scanf("%d", &n);
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	bool ans = true;
	rep(i, n)
	{
		if (a[i] % 2 == 0)
		{
			if (a[i] % 3 != 0 && a[i] % 5 != 0)
			{
				ans = false;
			}
		}
	}
	if(ans) printf("APPROVED\n");
	else printf("DENIED\n");
	return 0;
}

Measured memory_bytes: 3676
using System;
using System.Linq;

namespace AtCoder {
    class Program {
        static void Main() {
            long[] args = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            long a = args[0], b = args[1], _ = args[2], k = args[3];
            if(a >= k) {
                Console.WriteLine(k);
            } else if(a + b >= k) {
                Console.WriteLine(a);
            } else {
                Console.WriteLine(a - (k - a - b));
            }
        }
    }
}

Measured memory_bytes: 28236
n,k= map(int,input().split())
kasi = {}
for i in range(k):
    _=int(input())
    for c in list(map(int,input().split())):kasi[c]=kasi.get(c,[])+[i]
print(sum([1 if not i in kasi.keys() else 0 for i in range(1,n+1)]))

Measured memory_bytes: 9212
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m1(x) memset(x,-1,sizeof(x))
const int INF = 1e9 + 1;
const ll MOD = 1e9 + 7;
const double PI = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799;

int n, m;

int main(){
  cin >> n >> m;
  int h[100000];
  rep(i, n) cin >> h[i];
  vector<int> to[100000];
  rep(i, m){
    int a, b;
    cin >> a >> b;
    a--;b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  int ans = 0;
  for(int i = 0; i < n; i++){
    bool flag = true;
    for(int x:to[i]){
      if(h[x] >= h[i]) flag = false;
    }
    if(flag) ans++;
  }
  cout << ans <<endl;
}

Measured memory_bytes: 9084
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in Actual solution is at the top
 */

public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}

	static class Task {
		public void solve(int testNumber, InputReader in, PrintWriter out) {	
			int A = in.nextInt();
			int B = in.nextInt();
			int K = in.nextInt();
			int count = 1;
			for(int i = A; i <= B; i++) {
				if(count <= K) {
					out.println(i);
					count++;
				}else if(B - K < i ) {
					out.println(i);
				}
			}
		}
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}


Measured memory_bytes: 23124
import java.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // Scanner scan = new Scanner(System.in);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(bf.readLine());
        if(n == 3) {
          out.println("2 5 63");
        }
        else if(n == 4) {
          out.println("2 5 20 63");
        }
        else {
          Set<Integer> s = new HashSet<Integer>();
          for(int i=2; i<=n/4*6; i+=2) s.add(i);
          for(int i=3; i<=n/4*6; i+=3) s.add(i);
          if(n % 4 == 0) {
            if(n/4 % 2 == 1) {
              s.add(29997);
              s.remove(6);
            }
          }
          if(n % 4 == 1) {
            if(n/4 % 2 == 1) {
              s.add(29997);
            }
            else {
              s.add(30000);
            }
          }
          else if(n % 4 == 2) {
            if(n/4 % 2 == 1) {
              s.add(29997);
              s.add(30000);
            }
            else {
              s.add(29996);
              s.add(29998);
            }
          }
          else if(n % 4 == 3) {
            if(n/4 % 2 == 1) {
              s.add(29997);
              s.add(29996);
              s.add(29998);
            }
            else {
              s.add(29996);
              s.add(29998);
              s.add(30000);
            }
          }
          long sum = 0;
          StringBuilder sb = new StringBuilder();
          for(int i : s) {
            sb.append(i + " ");
            sum += i;
            sum %= 6;
          }
          out.println(sb.toString());
          if((s.size() != n)  || (sum % 6 != 0)) {
            //out.println(1/0);
          }
        }
        // StringTokenizer st = new StringTokenizer(bf.readLine());
        // int[] a = new int[n];
        // for(int i=0; i<n; i++) a[i] =  Integer.parseInt(st.nextToken());

        out.close(); System.exit(0);
    }


}


Measured memory_bytes: 28756
while true
  n = gets.chomp.to_i
  break if n == 0

  msq = n.times.map{n.times.map{0}}

  x = (n - 1) / 2
  y = (n + 1) / 2
  k = 1
  msq[y][x] = k

  while k < n * n
    x += 1
    x = 0 if x >= n
    y += 1
    y = 0 if y >= n

    while msq[y][x] > 0
      x -= 1
      x = n - 1 if x < 0
      y += 1
      y = 0 if y >= n
    end

    k += 1
    msq[y][x] = k
  end

  puts msq.map{|hl| hl.map{|k| sprintf("%4d", k)}.join("")}.join("\n")
end

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

ll dp[1000][1000];

ll ncr(ll n, ll r){
    if (n < r) return 0;
    if (n == r) return dp[n][r] = 1;
    if (r == 0) return dp[n][r] = 1;
    if (r == 1) return dp[n][r] = n;
    if (dp[n][r]!=-INF) return dp[n][r];
    return dp[n][r] = ncr(n - 1, r) + ncr(n - 1, r - 1);
}

void solv() {
    ll N, M;
    cin >> N >> M;
    rep(i, 1000) {
        rep(j, 1000) {
            dp[i][j] = -INF;
        }
    }
   
    ll buf = ncr(N,2) + ncr(M,2);
    cout << buf << endl;
}

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

Measured memory_bytes: 8064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	map<ll,ll> m;
	m[0] ++;
	ll a,b,temp;
	scanf("%lld%lld",&a,&b);
	ll sum = 0;
	ll ans = 0;
	for(int i = 0;i < a;i ++)
	{
		scanf("%lld",&temp);
		sum = (temp+sum)%b;
		ans += m[sum]++;
	}
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 4224
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K, T;
    cin >> K >> T;
    int a[110];
    rep(i, T) cin >> a[i];
    if (T == 1) {
        cout << a[0] - 1 << endl;
        return 0;
    }
    int sum = 0;
    sort(a, a + T);
    rep(i, T - 1) sum += a[i];
    cout << max(0, a[T - 1] - 1 - sum) << endl;
    

    return 0;
}


Measured memory_bytes: 256
// Original: https://github.com/tanakh/competitive-rs
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::HashMap;

fn main() {
    input!(_n: usize, m: usize, mut ab: [(usize, usize); m]);

    // 隣り合う点しかないグラフは、木ではなく区間で考える。
    // 区間スケジューリング
    // 区間の被覆は終端で昇順ソートして考える。
    // 区間 [a_i, b_i), [a_j, b_j) (i < j) の2つの区間を同時に切断したいとき、
    // b_iの直前の区間を含むように切断するのが最適。
    // a_j < b_i であれば同時に切断できる。
    // a_j >= b_i なら、どうあがいても同時に切断できないので、串刺しと現在の終端を更新。
    ab.sort_by(|x, y| x.1.cmp(&y.1));
    let mut count = 0;
    let mut end = 0;

    for i in 0..m {
        if ab[i].0 >= end {
            end = ab[i].1;
            count += 1;
        }
    }
    println!("{}", count);
}


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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;
const ll DIV = 10;
const ll MAX = 100001;

int dp[2LL << DIV][MAX + 5];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    vector<pll> A(N);
    REP(i, N) {
        cin >> A[i].first >> A[i].second;
    }
    memset(dp, 0, sizeof(dp));
    ll bit = pow(2LL, DIV);
    REP(b, std::min(N, bit)) {
        vector<ll> v;
        ll n = b + 1;
        while (n > 0) {
            v.push_back(n - 1);
            n >>= 1;
        }

        REP(i, (1LL << v.size())) {
            int w = 0, t = 0;
            REP(j, v.size()) {
                if (((i >> j) & 1) == 1) {
                    w += A[v[j]].second;
                    t += A[v[j]].first;
                }
            }
            if (w > MAX)
                continue;
            dp[b][w] = std::max(dp[b][w], t);
        }
        REP(i, MAX) {
            dp[b][i + 1] = std::max(dp[b][i], dp[b][i + 1]);
        }
    }

    ll Q;
    cin >>
        Q;
    REP(_, Q) {
        ll V, L;
        cin >> V >>
            L;
        if (V <= bit) {
            cout << dp[V - 1][L] <<
                 endl;
            continue;
        }

        vector<ll> v;
        while (V > bit) {
            v.
                    push_back(V
                              - 1);
            V >>= 1;
        }

        ll ret = 0;
        REP(b, (1LL << v.size())) {
            ll w = 0, t = 0;
            REP(j, v.size()) {
                if (((b >> j) & 1) == 1) {
                    w += A[v[j]].
                            second;
                    t += A[v[j]].
                            first;
                }
                if (w > L)
                    break;
            }
            if (w > L)
                continue;
            ret = std::max(ret, t + dp[V - 1][L - w]);
        }
        cout << ret <<
             endl;
    }
    return 0;
}

Measured memory_bytes: 807352
/*
[m-solutions2019] F - Random Tournament
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int MAX_N = 2000;

int N;
bitset<MAX_N> A[MAX_N];

bitset<MAX_N> dpl[MAX_N], dpr[MAX_N];

ll solve() {
    for (int i = 0; i < N; i++) {
        dpl[i][i] = dpr[i][i] = true;
    }
    for (int l = 1; l < N; l++) {
        for (int i = 0; i + l < N; i++) {
            int j = i + l;
            dpl[j][i] = (A[i] & dpl[j] & dpr[i + 1]).any();
        }
        for (int j = l; j < N; j++) {
            int i = j - l;
            dpr[i][j] = (A[j] & dpr[i] & dpl[j - 1]).any();
        }
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (dpr[0][i] && dpl[N - 1][i]) {
            ans++;
        }
    }
    return ans;
}

int main() {
    cin >> N;
    for (int i = 1; i < N; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < i; j++) {
            A[i][j] = s[j] == '1';
            A[j][i] = !A[i][j];
        }
    }

    cout << solve() << endl;

    return 0;
}


Measured memory_bytes: 1792
#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 ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
using namespace std;

int main(){
    int h,n,total=0;
    cin>>h>>n;
    vector<int> a(n);
    rep(i,n){
        cin>>a[i];
        total += a[i];
    }
    cout<<(total>=h ? "Yes":"No")<<endl;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define takeline cin.ignore();
#define sc second
#define N 3000005
#define endl "\n"
#define mod 1000000007
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
int main(){
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,k,l,n;
	cin>>n;
	k=(n+1)/2;
	if(n==1){
		cout<<"0"<<endl;
		return 0;
	}
	ll an=0;
	for(i=1;i<=k;i++){
		l=(n-i);
		if(k!=l) an++;
	}
	cout<<an;
	return 0;
}

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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int d = 100 * a + 10 * b + c;
    if (d % 4 == 0) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

int main()
{
    int N, a;
    cin >> N;
    REP(_, N)
    {
        cin >> a;
        if (a & 1)
        {
            puts("first");
            return 0;
        }
    }
    puts("second");
}


Measured memory_bytes: 256
A, B, C, X, Y = map(int, input().split())

ans = 10**18
for c in range(max(X, Y) * 2 + 1):
    x = max(0, X - c // 2)
    y = max(0, Y - c // 2)
    ans = min(ans, x * A + y * B + c * C)
print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;
int dx[3]={-1,0,1};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  map<pair<int,int>,int>ma;
  int h,w,n;
  cin>>h>>w>>n;
  rep(i,n)
  {
    int a,b;
    cin>>a>>b;
    a--;b--;
    rep(j,3)rep(k,3)
    {
      int ny=a+dx[j],nx=b+dx[k];
      if(ny<0||ny>=h||nx<0||nx>=w)continue;
      ma[{ny,nx}]++;
    }
  }
  vector<ll>ans(10,0);
  ans[0]=(ll)(h-2)*(w-2);
  for(auto p:ma)
  {
    auto tp=p.first;
    if(tp.first==0||tp.first==h-1||tp.second==0||tp.second==w-1)continue;
    //cout<<tp.first<<" "<<tp.second<<" "<<p.second<<endl;
    ans[p.second]++;
    ans[0]--;

  }
  rep(i,10)cout<<ans[i]<<endl;
  return 0;

}


Measured memory_bytes: 56576
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
#define REP(i,a,n) for(int (i)=(a); (i)<(int)(n); (i)++)
#define rep(i,n) REP(i,0,n)
#define vec vector 
 
 
int main(){
  string S;
  ll Q;  
  cin >> S >> Q;
  
  int T = 1;
  int F = 1;
  char C = 'a';
  bool rev = false;
  
  rep(i, Q){
    cin >> T;
    if(T==1){
      rev = !rev;
    }else{
      cin >> F >> C;
      if((rev == false && F == 2) || (rev == true && F == 1)){
        S.push_back(C);
      }else{
        S.insert(S.begin(), 1, C);
      }    
    }
  }
  
  if (rev == true){
    reverse(S.begin(), S.end());
  }
    
    cout << S;
}

Measured memory_bytes: 900
import sys
sys.setrecursionlimit(10**7)
 
n=int(input())
l=[list(input()) for i in range(n)]
connection=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      connection[i].append(j)
 
colors = [0]*n
def dfs(v,color):
    colors[v] = color
    for to in connection[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()
 
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=[]
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.append(connection[next[i]][j])
    next=next2
    next2=[]
    
  return distance
 
ans=[]
for i in range(n):
  ans.append(max(bfs(i)))
print(max(ans)+1)

Measured memory_bytes: 45552
#include <bits/stdc++.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;

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

#ifdef LOCAL
	#define eprintf(...) printf(__VA_ARGS__)
#else
	#define eprintf(...) 1
#endif

#define ROUNDUP(a, b) 		( ((a) + ((b) - 1) ) / b)
#define SET_ZERO(a)	 		( memset((a), 0, sizeof(a)))
#define SET_NUM_ARRAY(a,b)	( memset((a), b, sizeof(a)))
//#define int long long int //dont forget to change int to signed
int count16bit(unsigned short v) {
	unsigned short count = (v & 0x5555) + ((v >> 1) & 0x5555);
	count = (count & 0x3333) + ((count >> 2) & 0x3333);
	count = (count & 0x0f0f) + ((count >> 4) & 0x0f0f);
	return (count & 0x00ff) + ((count >> 8) & 0x00ff);
}

int main() {
	int N, M;
	vector<int> vv[8];
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		vv[a-1].push_back(b-1);
		vv[b-1].push_back(a-1);
	}

	stack<ii> st;
	st.push(ii(0,1));
	int ans = 0;
	while (!st.empty()) {
		ii p = st.top(); 
		int v = p.first, bit = p.second;
		st.pop();
		eprintf("v = %d bit = %d\n", v, bit);
		if (count16bit(bit) == N) {
			ans++;
			continue;
		}
		for (vector<int>::iterator it = vv[v].begin(); it != vv[v].end(); ++it) {
		// for (auto it: vv[v]) {
			int s = *it;
			if (!(bit & (1<<s))) {
				st.push(ii(s,bit | (1<<s) ));
			}
		}
	}
	printf("%d \n", ans);
	return 0;
}


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

int main(){

int N;
while(1){
cin>>N;if(N==0)break;
int M;
bool n[103][103]={};
for(int i=1;i<=N;i++){
cin>>M;
for(int j=0;j<M;j++)
{int x;cin>>x;n[i][x]=true;}
}

bool R[101]={};
cin>>M;
for(int i=0;i<M;i++)
{int x;cin>>x;R[x]=true;}
int c=0,k=0;

for(int i=1;i<=N;i++){bool f=true;
for(int j=1;j<=N;j++)
{
if(n[i][j]!=R[j]&&R[j]==true)f=false;
}
if(f==true){c++;k=i;}
}

if(c==1)cout<<k<<endl;
else{cout<<"-1"<<endl;}
}
return 0;
}

Measured memory_bytes: 1176
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")

//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")

// -------------------</optimizations>--------------------
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define d long double
#define pii pair<int,int>
#define pb push_back
#define pf push_front
#define cases int tc;cin>>tc;while(tc--)
#define N 100003
#define M 103
#define inf LLONG_MAX
#define SPEED ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//int mod=1e9+7;
//int mod=998244353;

bool compare(pair<pair<string,int>,int> a,pair<pair<string,int>,int> b)
{
    if(a.first.first==b.first.first)
        return a.first.second>b.first.second;
    return a.first.first<b.first.first;
}   

signed main()
{
    SPEED

    int n;
    cin>>n;
    int p1,i;
    string s;
    map<int,int> mapp;
    pair<pair<string,int>,int> p[n+1];
    int ans[n+1];
    for(i=1;i<=n;++i)
        cin>>s>>p1,mapp[p1]=i,p[i]={{s,p1},i};
    
    sort(p+1,p+n+1,compare);
    for(i=1;i<=n;++i)
        ans[i]=mapp[p[i].first.second];
    
    for(i=1;i<=n;++i)
        cout<<ans[i]<<'\n';
    
    return 0;
}


Measured memory_bytes: 256
import sys
import re
import math
import collections
import decimal
import bisect
import itertools

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    # p1
    if sum(a) == 0:
        print("Yes")
        exit(0)

    # p2
    c = collections.Counter(a)
    if n % 3 == 0:
        if 0 in c.keys() and len(c) == 2:
            if n // 3 == c[0]:
                print("Yes")
                exit(0)

    # p3

    t_key=[]
    t_value=[]
    if len(c) == 3:
        for k,v in c.items():
            t_key.append(k)
            t_value.append(v)
    else:
        print("No")
        exit(0)


    if t_key[0] ^ t_key[1] ^ t_key[2] == 0 and t_value[0]==t_value[1]==t_value[2]==n//3:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 16184
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))

ans = [0] * n
for i in range(n):
    ans[i] = (p[i] + 1) / 2

ruiseki = [0] * (n + 1)
for i in range(n):
    ruiseki[i + 1] = ruiseki[i] + ans[i]
    
res = 0
for i in range(n):
    if k+i > n:
        break
    res = max(res, ruiseki[k + i] - ruiseki[i])
print(res)
    

Measured memory_bytes: 78088
using System;
class ProgramA
    {
        static void Main(string[] args)
        {
            
            string input = Console.ReadLine();
            int a = int.Parse(input);
            double b = (double)(a/2 + 1)/(double)a;

            if(a % 2 == 0)
                Console.WriteLine("0.5");
            else
                Console.WriteLine(b);
    
        }
    }

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

using namespace std;

int main() {
    int n, l;
    cin >> n >> l;
    int r = l + n - 1;

    int eat;
    if (r <= 0) {
        eat = r;
    } else if (l >= 0) {
        eat = l;
    } else {
        eat = 0;
    }

    cout << (l + r) * (r - l + 1) / 2 - eat << endl;
    return 0;
}


Measured memory_bytes: 256
n,k = map(int,input().split())
s = str(input())
if k ==1:
  x = s[0].lower() + s[1:]
elif k == n:
  x = s[0:n-1] + s[n-1].lower()
else:
  x = s[0:k-1] + s[k-1].lower() + s[k:]
print(x)

Measured memory_bytes: 3060
#include<iostream>
#include<cmath>
using namespace std;
int main(){
	int H,W,i,j,tot;
	char map[100][100];
	int ans[100][100];
	cin>>H>>W;
	for(i=1;i<=H;i++){
		for(j=1;j<=W;j++){
			cin>>map[i][j];
		}
	}
	for(i=1;i<=H;i++){
		for(j=1;j<=W;j++){
			if(map[i][j]=='#') ans[i][j]=35;
			else{
				tot=0;
				if(map[i-1][j-1]=='#') tot++;
				if(map[i-1][j]=='#') tot++;
				if(map[i-1][j+1]=='#') tot++;
				if(map[i][j-1]=='#') tot++;
				if(map[i][j+1]=='#') tot++;
				if(map[i+1][j-1]=='#') tot++;
				if(map[i+1][j]=='#') tot++;
				if(map[i+1][j+1]=='#') tot++;
				ans[i][j]=tot;
			}
		}
	}
	for(i=1;i<=H;i++){
		for(j=1;j<=W;j++){
			if(ans[i][j]==35) cout<<'#'; 
			else cout<<ans[i][j];
		}
		cout<<endl;
	}
	return 0;
} 

Measured memory_bytes: 256
X=int(input())
dp=[False]*(X+1)
dp[1]=True
for p in range(2,int(1000**0.5)+1):
    n=p*p
    while n<=X:
        dp[n]=True
        n*=p
for ans in range(X,0,-1):
    if dp[ans]==True:
        print(ans)
        break

Measured memory_bytes: 3060
use std::cmp::max;

fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let a: i32 = read(&mut stdin_lock, &mut buf, b' ');
    let b: i32 = read(&mut stdin_lock, &mut buf, b' ');
    let c: i32 = read(&mut stdin_lock, &mut buf, b'\n');

    let ans = max(0, c - (a - b));
    println!("{}", ans);
}


Measured memory_bytes: 4352
import Control.Monad
import Data.List

main = do
  n<-readLn
  sps<-replicateM n$(\[a,b]->(a,read b)).words<$>getLine
  putStr $ solve sps

solve sps = unlines $ map (show.(\(i,(_,_))->i)) ans
  where
  tmp = sortOn (\(_,(_,a))-> -a) isps
  ans = sortOn (\(_,(a,_))-> a) tmp
  isps = zip [1..] sps
  sortOn f = sortBy (\a b->compare(f a)(f b))

Measured memory_bytes: 1020
#include<cstdio>
#include<cmath>

int main(void)
{
	int t, s=0, h,n;
	scanf("%d%d", &h, &n);
	while (n--)
	{
		scanf("%d", &t);
		s += t;
	}
	if (s >= h)
		printf("Yes");
	else
		printf("No");
}

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

int N, M;
string S[55555], R[55555];
int search(string T)
{
    int l, r;
    int len = T.size();
    if(T[len - 1] == '*') {
        T = T.substr(0, len - 1);
        string C = T;
        C += ('z' + 1);
        r = lower_bound(S, S + N, C) - S;
        l = lower_bound(S, S + N, T) - S;
        return (r - l);
    } else if(T[0] == '*') {
        string C;
        T = T.substr(1);
        reverse(T.begin(), T.end());
        C = T;
        C += ('z' + 1);
        r = lower_bound(R, R + N, C) - R;
        l = lower_bound(R, R + N, T) - R;
        return (r - l);
    } else {
        if(binary_search(S, S + N, T)) {
            return (1);
        } else {
            return (0);
        }
    }
}

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

    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        cin >> S[i];
        R[i] = S[i];
        reverse(R[i].begin(), R[i].end());
    }

    sort(S, S + N); sort(R, R + N);

    while(M--) {
        string T;
        int pos = -1, sum = 0;
        cin >> T;
        for(int i = 0; i < (int)T.size(); i++) {
            if(T[i] == '?') pos = i;
        }
        if(pos == -1) {
            cout << search(T) << endl;
        } else {
            for(char i = 'a'; i <= 'z'; i++) {
                T[pos] = i;
                sum += search(T);
            }
            cout << sum << endl;
        }
    }

    return (0);
}



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

int X, Y, A, B, C;
int red[100005], green[100005], color[100005];
vector<int> best;
long long ans;

int32_t main() {
    scanf("%lld %lld %lld %lld %lld", &X, &Y, &A, &B, &C);
    for(int i = 0; i < A; i++) {
        scanf("%lld", &red[i]);
    }
    sort(red, red + A, greater<int>());
    for(int i = 0; i < B; i++) {
        scanf("%lld", &green[i]);
    }
    sort(green, green + B, greater<int>());
    for(int i = 0; i < C; i++) {
        scanf("%lld", &color[i]);
    }
    sort(color, color + C, greater<int>());
    for(int i = 0; i < max(X, Y); i++) {
        if(i < X) {
            best.push_back(red[i]);
            ans += red[i];
        }
        if(i < Y) {
            best.push_back(green[i]);
            ans += green[i];
        }
    }
    sort(best.begin(), best.end());
    for(int i = 0; i < min(C, X + Y) && color[i] > best[i]; i++) {
        ans += color[i] - best[i];
    }
    cout << ans << "\n";
}


Measured memory_bytes: 4724
//ll n_kai[pow(10.0, 5.0)]; なんでだめなの？


#include<iostream>
#include<queue>
#include<vector>

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

using namespace std;
using ll = long long;

const int INF = 1001001001;
const int MOD = 1000000007;

struct UnionFind {
	vector<int> val;
	UnionFind(int n) : val(n, -1) {
	}

	void unite(int a, int b){
		a = find(a);
		b = find(b);

		if (a == b){
			return;
		}

		if (val[a] > val[b]){
			swap(a, b);
		}
		val[a] += val[b];
		val[b] = a;
	}

	int find(int x){
		if (val[x] < 0) return x;
		return val[x] = find(val[x]);
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}

	int size(int x){
		return -val[find(x)];
	}
	
	~UnionFind(){
	}
};

int main(){
	int n, m, k;cin >> n >> m >> k;
	UnionFind uf(n);
	int fri[n] = {0};
	rep(i,m){
		int a, b;
		cin >> a >> b;
		--a;--b;
		uf.unite(a, b);
		++fri[a];
		++fri[b];
	}
	vector<vector<int>> block(n);
	rep(i,k){
		int a, b;
		cin >> a >> b;
		--a;--b;
		block[a].push_back(b);
		block[b].push_back(a);
	}
	rep(i,n){
		int ans = uf.size(i);
		for (auto a : block[i]){
			if (uf.same(i, a)){
				--ans;
			}
		}
		--ans;
		ans = ans - fri[i];
		cout << ans << " ";
	}
	
	cout << endl;
}


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

int main(){
    int p,q,r,v[3];
    cin>>p>>q>>r;
    v[0]=p;
    v[1]=q;
    v[2]=r;
    sort(v,v+3);
    cout<<v[0]+v[1]<<endl;
       
}

Measured memory_bytes: 3628
package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func min(nums ...int) int {
	ret := nums[0]
	for _, v := range nums {
		if v < ret {
			ret = v
		}
	}
	return ret
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n, s := nextInt(), next()

	white, black := make([]int, n), make([]int, n)
	if s[0] == '.' {
		white[0] = 1
	} else {
		black[0] = 1
	}
	for i := 1; i < n; i++ {
		white[i], black[i] = white[i-1], black[i-1]
		if s[i] == '.' {
			white[i]++
		} else {
			black[i]++
		}
	}

	// 全部白または黒
	ans := min(white[n-1], black[n-1])

	// i番目以降の石を黒にする
	for i := 1; i < n; i++ {
		ans = min(ans, black[i-1]+white[n-1]-white[i-1])
	}

	puts(ans)
}


Measured memory_bytes: 4608
#include<stdio.h>
#include<math.h>

int main(void)
{
	int a,b,c,d;
  	scanf("%d %d",&a,&b);
  	scanf("%d %d",&c,&d);
  	if(a==c)
    {
        printf("0");
    	return 0;
    }
	if(a+1==c)
    {
     if(d==1)
     {
       printf("1");
		return 0;
     }
 	}
    else
	{
    	printf("0");
    }
	return 0;
}

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

using namespace std;
const int INF = numeric_limits<int>::max() / 2;
typedef vector<int> VI;
typedef vector<VI> VVI;

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

    int n, m, k;
    cin >> n >> m >> k;
    std::vector<int> d(m + 1);
    for (int i = 0; i < m; i++)
    {
        cin >> d[i];
        d[i]--;
    }
    VVI v(n + 1, vector<int>(k + 1));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++)
        {
            cin >> v[i][j];
            v[i][j]--;
        }
    std::vector<int> dp((1 << m) + 1, INF);
    dp[(1 << m) - 1] = 0;
    queue<int> que;
    que.push((1 << m) - 1);
    while (!que.empty())
    {
        for (int i = 0; i < k; i++)
        {
            int tmp = que.front(), next = 0;
            for (int j = 0; j < m; j++)
            {
                if (tmp % 2)
                {
                    int mv = v[d[j]][i];
                    for (int p = 0; p < m; p++)
                    {
                        if (d[p] == mv)
                            next |= (1 << p);
                    }
                }
                tmp /= 2;
            }
            //cout<<next<<endl;
            //cout<<"*"<<dp[next]<<endl;
            if (dp[next] == INF)
            {
                que.push(next);
            }
            dp[next] = min(dp[next], dp[que.front()] + 1);
        }
        que.pop();
    }
    cout << dp[0] << endl;
    return 0;
}


Measured memory_bytes: 3516
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
struct node
{
	int tag,h,s;
}A,B;
void solve(){
	
}	
int main(){
	// debug;
	
	int a,b,c,d;read(a,b,c,d);
	A = {1,a,b};
	B = {2,c,d};
	while(A.h>0){
		B.h -= A.s;
		swap(A,B);
	}
	if(A.tag == 1) puts("No");
	else puts("Yes");
	return 0;
}


Measured memory_bytes: 3636
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, K = inm()


def solve():
    ans = 0
    for i in range(1, N + 1):
        x = i
        cnt = 0
        while x < K:
            x *= 2
            cnt += 1
        ans += 0.5 ** cnt
    return ans / N


print(solve())


Measured memory_bytes: 9480
//B - Picture Frame: 
//Assunto:
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define loop(i, a, b) for(int i = a; i < b; i++)
#define loopBack(i, a, b) for(int i = a; i >= b; i--)
#define INF INT_MAX
#define LINF LLONG_MAX
#define DINF DBL_MAX
#define MAX 100050
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int h, w, aux;
    cin >> h >> w;
    vector<string> image(h);
    loop(i, 0, h) cin >> image[i];
    aux = w+2;
    while(aux--) cout << '#';
    cout << "\n";
    loop(i, 0, h) {
        cout << '#';
        cout << image[i];
        cout << "#\n";
    }
    aux = w+2;
    while(aux--) cout << '#';
    cout << "\n";

}

Measured memory_bytes: 256
import math
n, a, b = map(int, input().split())
mod = 10**9 + 7
s = pow(2, n, mod) - 1
def cal(n, r):
  p = 1
  q = 1
  for i in range(r):
    p = p*(n-i)%mod
    q = q*(i+1)%mod
  return p*pow(q, mod-2, mod)%mod
print((s - cal(n, a) - cal(n, b))%mod)

Measured memory_bytes: 9200
#include<bits/stdc++.h>
using namespace std;
using ul = unsigned long;
using ull = unsigned long long;
#define vec vector
#define rep(_i,_n) for(ull _i = 0; _i < _n; _i++)
#define rep2(_i,_s,_n) for(ull _i = _s; _i < _n; _i++)
#define elif else if
#define push(_a) push_back(_a)
#define fullSort(_a) sort(_a.begin(), _a.end())
#define inputVecI(_name, _n) vec<int> _name(_n);rep(_i, _n)cin >> _name[_i];
#define inputVecUL(_name, _n) vec<ul> _name(_n);rep(_i, _n)cin >> _name[_i];
#define inputVecULL(_name, _n) vec<ull> _name(_n);rep(_i, _n)cin >> _name[_i];
#define inputVecS(_name, _n) vec<string> _name(_n);rep(_i, _n)cin >> _name[_i];
#define printVec(_vec) cout << "{";rep(i, _vec.size()-1)cout << _vec[i] << ",";cout << _vec[_vec.size()-1];cout << "}\n";
#define append(_x) push_back(_x)
#define mapLoop(_i, _name) for(auto i = _name.begin(); i != _name.end(); i++)

int main()
{
    ul r, D, x;
    cin >> r >> D >> x;
    rep(i, 10){
      x = r * x - D;
      cout << x << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import sys

input = sys.stdin.buffer.readline


class FenwickTree:
    """FenwickTree (Binary Indexed Tree, 0-index)

    Queries:
        1. add(i, val): add val to i-th value
        2. sum(n): sum(bit[0] + ... + bit[n-1])

    complexity: O(log n)

    See: http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, a_list):
        self.N = len(a_list)
        self.bit = a_list[:]
        for _ in range(self.N, 1 << (self.N - 1).bit_length()):
            self.bit.append(0)
        for i in range(self.N-1):
            self.bit[i | (i+1)] += self.bit[i]

    def add(self, i, val):
        while i < self.N:
            self.bit[i] += val
            i |= i + 1

    def sum(self, n):
        ret = 0
        while n >= 0:
            ret += self.bit[n]
            n = (n & (n + 1)) - 1
        return ret

    def query(self, low, high):
        return self.sum(high) - self.sum(low)


def yosupo():
    # https://judge.yosupo.jp/problem/point_add_range_sum
    _, Q = map(int, input().split())
    fwt = FenwickTree([int(x) for x in input().split()])
    ans = []
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        if type_ == 0:
            fwt.add(l, r)
        else:
            ans.append(fwt.query(l-1, r-1))
    print(*ans, sep="\n")


def aoj():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B
    N, Q = map(int, input().split())
    fwt = FenwickTree([0] * N)
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        if type_ == 0:
            fwt.add(l-1, r)
        else:
            print(fwt.query(l-2, r-1))


if __name__ == "__main__":
    yosupo()
    # aoj()


Measured memory_bytes: 58940
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

void use_io_optimizations()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main()
{
    use_io_optimizations();

    vector<vector<long long>> bin(100, vector<long long>(100, 0));
    for (int i = 0; i < 100; ++i) {
        bin[i][0] = 1;
    }
    for (int i = 1; i < 100; ++i) {
        for (int j = 1; j < 100; ++j) {
            bin[i][j] = bin[i - 1][j - 1] + bin[i - 1][j];
        }
    }
    int n, a, b;
    cin >> n >> a >> b;
    vector<long long> v(n);
    map<long long, int> count;
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        ++count[v[i]];
    }
    sort(v.begin(), v.end());
    long long sum = 0;
    map<long long, int> res;
    for (int i = 0; i < a; ++i) {
        sum += v[n - 1 - i];
        ++res[v[n - 1 - i]];
    }
    cout << fixed << setprecision(12) << double(sum) / a << '\n';
    long long bla = 1;
    if (res.size() == 1) {
        bla = 0;
        auto x = res.begin()->first;
        auto y = res.begin()->second;
        for (int i = y; i <= min(count[x], b); ++i) {
            bla += bin[count[x]][i];
        }
    }
    else {
        for (auto& p : res) {
            bla *= bin[count[p.first]][p.second];
        }
    }
    cout << bla << '\n';

    return 0;
}


Measured memory_bytes: 1016
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


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


#define ARRAY_MAX 100005
const int INF = 1e9;
const ll MOD = 1e9 + 7;

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




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


int main() {

	
	ll n, k, q;
	cin >> n >> k >> q;
	vector<ll> a(100005), cnt(100005 + 10, k);
	for (int i = 0; i < q; i++)
	{
		cin >> a[i];
		a[i]--;
		cnt[a[i]]++;
		//cout << "i= " << i << endl;
	}
	for (int i = 0; i < n; i++)
	{
		if (cnt[i]-q <= 0) {
			cout << "No" << endl;
		}
		else
		{
			cout << "Yes" << endl;
		}
	}



	


	return 0;
}


Measured memory_bytes: 2176
use std::cmp::*;
use std::collections::{BTreeSet, VecDeque};
use std::f64::consts::PI;
use std::io::*;
use std::str::FromStr;
//portable utility
#[allow(dead_code)]
fn switch<T>(flag: bool, true_value: T, false_value: T) -> T {
    if flag {
        true_value
    } else {
        false_value
    }
}
#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
#[allow(dead_code)]
fn read_string() -> Vec<char> {
    read::<String>().chars().collect()
}
#[allow(dead_code)]
fn read_vector<T: FromStr>(number: usize) -> Vec<T> {
    (0..number).map(|_| read()).collect()
}

fn main() {
    let (n, m): (usize, usize) = (read(), read());
    let mut route: Vec<BTreeSet<usize>> = vec![BTreeSet::new(); n + 1]; //0は欠番
    for _ in 0..m {
        let (a, b): (usize, usize) = (read(), read());
        route[a].insert(b);
        route[b].insert(a);
    }

    //幅優先探索
    let mut results = vec![None; n + 1];
    let mut queue = VecDeque::new();
    queue.push_back(1);
    results[1] = Some(0);
    while let Some(now) = queue.pop_front() {
        for next in route[now].iter() {
            if results[*next] == None {
                //let n: u32 = results[now].unwrap();
                results[*next] = Some(now);
                queue.push_back(*next);
            }
        }
    }

    if results[2..=n].iter().all(|x: &Option<_>| x.is_some()) {
        println!("Yes");
        for i in 2..=n {
            println!("{}", results[i].unwrap());
        }
    } else {
        println!("No");
    }
}


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

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

const int MAX = 2e5 + 5;
char buf[MAX];
int type[MAX];
set<int> adj[MAX][2];
int n, m;

int main() {
    scanf("%d %d", &n, &m);
    scanf("%s", buf);
    fori(i, 0, n) {
        type[i + 1] = buf[i] == 'A';
    }
    fori(i, 0, m) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u][type[v]].insert(v);
        adj[v][type[u]].insert(u);
    }
    set<ii> pq;
    fori(i, 1, n + 1) {
        pq.emplace(min((int) adj[i][0].size(), (int) adj[i][1].size()), i);
    }
    while(!pq.empty() && pq.begin()->first == 0) {
        ii top = *pq.begin(); pq.erase(pq.begin());
        int id = top.second;
        set<int> v = adj[id][0].empty() ? adj[id][1] : adj[id][0];
        for(auto &each : v) {
            if(adj[each][type[id]].count(id)) {
                int score = min((int) adj[each][0].size(), (int) adj[each][1].size());
                pq.erase(ii(score, each));
                adj[each][type[id]].erase(id);
                int new_score = min((int) adj[each][0].size(), (int) adj[each][1].size());
                pq.emplace(new_score, each);
            }
        }
    }
    puts(pq.empty() ? "No" : "Yes");
    return 0;
}


Measured memory_bytes: 46592
/* 
 * Project: AtCoder Beginners Contest 053 A - ABC/ARC
 * Author: toms74209200 <https://github.com/toms74209200>
 *
 * Created on 2020/06/11
 * Copyright (c) 2020 toms74209200
 * 
 * This software is released under the MIT License.
 * http://opensource.org/licenses/mit-license.php
 */
#include <cstdio>
using namespace std;

int x;

void solve() {

    if (x < 1200) {
        printf("ABC\n");
        return;
     } else {
        printf("ARC\n");
        return;
     }

}

int main() {

    scanf("%d", &x);

    solve();

}

Measured memory_bytes: 888