akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	int w,h,x,y;
	cin>>w>>h>>x>>y;
	int a2=0;
	if(x==(1.0*w)/2&&y==(1.0*h)/2){
		a2=1;
	}
	cout<<(1.0*w*h)/2<<" "<<a2;







	
	
return 0;	
}


Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	var n int
	fmt.Scan(&n)
	if n%2 == 1 {
		yesOrNo(false)
		return
	}
	s := nextLine()
	for i, j := 0, n/2; j < n; i, j = i+1, j+1 {
		if s[i] != s[j] {
			yesOrNo(false)
			return
		}
	}
	yesOrNo(true)
}

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

func nextSlice() []string {
	sc.Scan()
	return strings.Split(sc.Text(), " ")
}

func atoi(a []string) (b []int) {
	b = make([]int, len(a))
	for i := range a {
		b[i], _ = strconv.Atoi(a[i])
	}
	return
}

func atof(a []string) (b []float64) {
	b = make([]float64, len(a))
	for i := range a {
		b[i], _ = strconv.ParseFloat(a[i], 64)
	}
	return
}

func scanSlice2(n int) (a []int, b []int) {
	a = make([]int, n)
	b = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i], &b[i])
	}
	return
}

func scanFloatSlice2(n int) (a []float64, b []float64) {
	a = make([]float64, n)
	b = make([]float64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i], &b[i])
	}
	return
}

// ---------------------------------------------------

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func larger(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func largest(a, b, c int) (lgst int) {
	if a > b {
		lgst = a
	} else {
		lgst = b
	}
	if c > lgst {
		lgst = c
	}
	return
}

func smaller(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func smallest(a, b, c int) (slst int) {
	if a < b {
		slst = a
	} else {
		slst = b
	}
	if c < slst {
		slst = c
	}
	return
}

func sum(a []int) (ans int) {
	for i := range a {
		ans += a[i]
	}
	return
}

// ---------------------------------------------------

func yesOrNo(b bool) {
	if b {
		fmt.Println("Yes")
		return
	}
	fmt.Println("No")
}

func yesorNO(b bool) {
	if b {
		fmt.Println("YES")
		return
	}
	fmt.Println("NO")
}

Measured memory_bytes: 640
N, M = map(int,input().split())
side = [[]for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    side[a-1].append([b-1,c])
node = [-float('inf')]*N
node[0] = 0
for _ in range(N):
    for i in range(N):
        for b,c in side[i]:
            node[b] = max(node[b],node[i]+c)


for _ in range(N):
    for i in range(N):
        for b,c in side[i]:
            if node[b] < node[i]+c:
                node[b] = float('inf')
print(node[-1])

Measured memory_bytes: 50904
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
#include <atcoder/all>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define ALL(v) v.begin(),v.end()
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; }
#define DEBUG_VLL(vec) for(int sz=0;sz<int(vec.size());sz++) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

using modi = atcoder::modint998244353;

V<modi> one;

struct S {
    modi x;
    ll size;
};

S e() { return S{0, 0}; }

S op(S a, S b) {
    return S{a.x * modi(10).pow(b.size) + b.x, a.size + b.size};
}

using F = modi;

S mapping(F f, S x) {
    if (f == 0) return x;
    else return S{f * one[x.size], x.size};
}

F composition(F f, F g) {
    if (f == 0) return g;
    else return f;
}

F id() { return 0; }

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q; cin >> n >> q;
    one.resize(n + 1, 0);
    for (int i = 1; i <= n; i++) one[i] = one[i - 1] * 10 + 1;
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> lseg(n);
    for (int i = 0; i < n; i++) lseg.set(i, S{1, 1});
    for (int i = 0; i < q; i++) {
        int l, r, d; cin >> l >> r >> d;
        l--;
        lseg.apply(l, r, d);
        cout << lseg.all_prod().x.val() << '\n';
    }
    return 0;
}


Measured memory_bytes: 16392
#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;
ll solve(ll n, ll x){
	if(x<=n || n<0) return 0;
	if(x<=(ll)pow(2,n+1)-2) return solve(n - 1,x - 1);
	else return solve(n - 1,x - (ll)pow(2,n+1) + 1) + (ll)pow(2,n);
}

int main(){
	ll n,x;
	cin >> n >> x;
	cout << solve(n,x) << endl;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

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;
    vector<pll> B(N);
    REP(i, N){
    	B[i].second = A[i].first - A[i].second;
    	B[i].first = A[i].first + A[i].second;
    }

    sort(B.begin(), B.end());
    ll now;
    ll cnt = 0;
    REP(i, N){
    	//dump(B[i])
    	if(i==0){
    		now = B[i].first;
    		cnt++;
    	}else{
    		if(now<=B[i].second){
    			now = B[i].first;
    			cnt++;
    		}
    	}
    }
    cout << cnt << endl;
    return 0;
}

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

typedef struct
{
  double x;
  double y;
  
} Point;

void koch(int n,Point a,Point b){
  Point s,t,u;
  double th;
  if(n==0)return;
  th = M_PI*60.0/180.0;

  s.x=(2.0*a.x+1.0*b.x)/3.0;
  s.y=(2.0*a.y+1.0*b.y)/3.0;
  t.x=(1.0*a.x+2.0*b.x)/3.0;
  t.y=(1.0*a.y+2.0*b.y)/3.0;
  u.x=(t.x-s.x)*cos(th)-(t.y-s.y)*sin(th)+s.x;
  u.y=(t.x-s.x)*sin(th)+(t.y-s.y)*cos(th)+s.y;

  koch(n-1,a,s);
  printf("%.8f %.8f\n",s.x,s.y);
  koch(n-1,s,u);
  printf("%.8f %.8f\n",u.x,u.y);
  koch(n-1,u,t);
  printf("%.8f %.8f\n",t.x,t.y);
  koch(n-1,t,b);
}

int main(){
  Point a,b;
  int n;
  scanf("%d",&n);
  a.x=0;
  a.y=0;
  b.x=100;
  b.y=0;

  printf("%.8f %.8f\n",a.x, a.y);
  koch(n,a,b);
  printf("%.8f %.8f\n",b.x, b.y);
  return 0;
    }



Measured memory_bytes: 2108
//#include <tourist>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <iomanip>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
struct edge {
    int to, cost;
};
ll n, q;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n>>q;
    vector<pair<ll,p> > a;
    set<pair<ll,p> > s;
    for (int i = 0; i < n; i++)
    {
        ll temps, tempt, tempx;
        cin >> temps>>tempt>>tempx;
        a.push_back(make_pair(temps-tempx,make_pair(tempt-tempx,tempx)));
        s.insert(make_pair(temps-tempx,make_pair(tempt-tempx,tempx)));
    }
    sort(ALL(a));
    vector<ll> ans;
    priority_queue<pair<ll,p> > que;
    for(int i=0;i<q;i++){
        ll t;
        cin>>t;
        while(true){
            auto iter=s.begin();
            if(s.empty()) break;
            if(iter->first>t) break;
            que.push(make_pair(-1*iter->second.second,make_pair(iter->first,iter->second.first)));
            //閉じ始めたものを座標が小さい順につめる
            s.erase(iter);
        }
        while(true){
            if(que.empty()){
                ans.push_back(-1);break;
            }
            if(que.top().second.second<=t) que.pop();
            //解放されたものにはもう引っ掛からないので除外する
            else{
                ans.push_back(que.top().first*-1);
                break;
            }
        }

        /*
        while(true){
            auto iter=s.begin();
            if(s.empty()) {ans.push_back(-1);break;}
            if(iter->first>t) {ans.push_back(-1);break;}
            if(iter->second.first<t) s.erase(iter);
            else{
                ans.push_back(iter->second.second);
                break;
            }
        }
        */
    }
    for(int i=0;i<q;i++)
    cout << ans[i] << "\n";
}



Measured memory_bytes: 27692
#include<bits/stdc++.h>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+5;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(x) memset(x,0,sizeof(x))
#define sca(x) scanf("%d",&x)
#define scall(x) scanf("%lld",&x)
#define eps 1e-6
int main()
{
	string s;cin>>s;
	int sum=0;
	for(int i=0;i<s.size();i++)
	sum+=(s[i]-'0');
	if(sum%9==0)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl; 
}

Measured memory_bytes: 3724
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
int dp[5500][5500];
signed main(){
	int n;cin >> n;
	string s;cin >> s;

	int ret = 0;
	rep(i,n+1){
		for(int j = i+1;j <=n ;j++){
			if(i && j &&s[i-1] != s[j-1])dp[i][j] = 0;
			else{
				if(i && j && s[i-1] == s[j-1])dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1);
			}
			
			// if(ret < dp[i][j])trace(i,j,ret,dp[i][j]);
			ret = max(ret,min(dp[i][j],j-i));
		}
		
	}
	cout << ret << endl;
	return 0;
}


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

using namespace std;

int main() {
  vector<vector<int>> tb(9, vector<int>(9));
  int n, o = 0;
  cin >> n;
  for(int i = 1; i <= n; i++) {
    if(i % 10 == 0)
      continue;
    for(int j = 100000; j > 0; j /= 10) {
      if(i >= j) {
        int t = i / j, b = i % 10;
        tb.at(t - 1).at(b - 1)++;
        break;
      }
    }
  }
  for(int i = 0; i < 9; i++)
    for(int j = 0; j < 9; j++)
      o += tb.at(i).at(j) * tb.at(j).at(i);
  cout << o << endl;
}

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

public class Main {

  public static void main(String[] args) {
    // TODO 自動生成されたメソッド・スタブ
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int a[] = new int[n];
    for (int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }

    Arrays.sort(a);

    for (int i = 1; i < n; i++) {
      if (a[i] == a[i - 1]) {
        System.out.println("NO");
        return;
      }
    }

    System.out.println("YES");
  }
}


Measured memory_bytes: 64764
N = int(input())
A = [0] * N
xy = [0] * N
for i in range(N):
  A[i] = int(input())
  xy[i] = [0] * A[i]
  for j in range(A[i]):
    xy[i][j] = [int(k) for k in input().split()]

ans = 0
for bit in range(2**N):
  # 正直者と不親切者の組み合わせ決定
  a = [0] * N
  for i in range(N):
    a[i] = (bit >> i) & 1
  # 正直者の証言の整合性確認
  are_correct = True
  for i in range(N):
    if a[i] == 0:
      continue
    for j in xy[i]:
      if a[j[0]-1] != j[1]:
        are_correct = False
  # 整合性の確認が取れた場合，正直者の最大人数を更新
  if are_correct:
    if ans < sum(a):
      ans = sum(a)

print(ans)


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

    if(c[0][0]&&c[0][1]&&c[0][2])cout <<"Yes"<<endl;
    else if(c[1][0]&&c[1][1]&&c[1][2])cout <<"Yes"<<endl;
    else if(c[2][0]&&c[2][1]&&c[2][2])cout <<"Yes"<<endl;
    else if(c[0][0]&&c[1][0]&&c[2][0])cout <<"Yes"<<endl;
    else if(c[0][1]&&c[1][1]&&c[2][1])cout <<"Yes"<<endl;
    else if(c[0][2]&&c[1][2]&&c[2][2])cout <<"Yes"<<endl;
    else if(c[0][0]&&c[1][1]&&c[2][2])cout <<"Yes"<<endl;
    else if(c[0][2]&&c[1][1]&&c[2][0])cout <<"Yes"<<endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 2000000
#define INFITY (1<<30)

int H, A[MAX+1];

void maxHeapify(int i) // sink(int i)
{
    int l, r, largest;
    l = 2 * i;
    r = 2 * i + 1;

    if (l <= H && A[l] > A[i]) largest = l;
    else largest = i;
    if (r <= H && A[r] > A[largest]) largest = r;

    if (largest != i) {
        swap(A[i], A[largest]);
        maxHeapify(largest);
    }
}

int extract()
{
    int maxv;
    if (H < 1) return -INFITY;
    maxv = A[1];
    A[1] = A[H--];
    maxHeapify(1);
    return maxv;
}

void increaseKey(int i, int key) // swim(int i)
{
    if (key < A[i]) return;
    A[i] = key;
    while (i > 1 && A[i/2] < A[i]) {
        swap(A[i], A[i/2]);
        i = i / 2;
    }
}

void insert(int key)
{
    H++;
    A[H] = -INFITY;
    increaseKey(H, key);
}

int main(int argc, char const *argv[])
{
    int key;
    char com[10];
    while (1) {
        scanf("%s", &com);
        if (com[0] == 'e' && com[1] == 'n') break;
        if (com[0] == 'i') {
            scanf("%d", &key);
            insert(key);
        } else {
            printf("%d\n", extract());
        }
    }

    return 0;
}



Measured memory_bytes: 6508
#include <stdio.h>
 
int
main (
  int   argc,
  char *argv[ ]
  )
{
  for ( ; ; )
  {
    int m, f, r;
    int sum;
 
    scanf ( "%d%d%d", &m, &f, &r );
    if ( m == -1
      && f == -1
      && r == -1 ) break ;
 
    sum = m + f;
    if ( m == -1 || f == -1 )
    {
      sum = 0;
    }
    if ( 30 <= sum && sum < 50
      && r >= 50 )
    {
      sum = 50;
    }
 
    puts ( sum >= 80 ? "A"
         : sum >= 65 ? "B"
         : sum >= 50 ? "C"
         : sum >= 30 ? "D"
         :             "F" );
  }
 
  return ( 0 );
}


Measured memory_bytes: 2104
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

int main(){
	int N,T,E;
	int x,ans=-1;
	cin>>N>>T>>E;
	rep(i,N){
		cin>>x;
		int t=T;
		t%=x;
		if(t<=E || x-t<=E){
			ans=i+1;
			break;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 0
#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>
#include <stack>
#include <cstdint>



#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rrep(i, n) for(ll i = (ll)(n-1); i >= 0; i--)
#define repi(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rrepi(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);i--)

#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  u64 &value() noexcept { return a; }
  u64 &value() const noexcept { return a; }
  modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  modint pow(u64 exp){
    modint res=1,rhs=*this;
    while (exp) {
      if (exp % 2) {
        res *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return res;
  }

  friend ostream& operator<<(ostream& os,modint& rhs){
    os << rhs.value();
    return os;
  }

  friend istream& operator>>(istream &is,modint &rhs){
      is>>rhs.value();
      rhs.value()%=Modulus;
      return is;
  }

};
using mint=modint<(ll)1e9+7>;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;cin>>n;
  string s;cin>>s;
  rep(i,2*n){
    if(i%2==0)continue;
    if(s[i]=='B')s[i]='W';
    else s[i]='B';
  }
  mint res=1;
  ll d=0;
  rep(i,2*n){
    if(s[i]=='B')d++;
    else res*=d--;
  }
  if(d!=0)res=0;
  rep(i,n)res*=i+1;
  cout<<res<<endl;


  return 0;

}


Measured memory_bytes: 764
n = int(input())
a = list(map(int,input().split()))
x = [0]*max(a)
for i in a:
    x[i-1]+=1
# print(x)
count = 0
# x_ = [(k*(k-1))/2 for k in x if k>=2]
# count = sum(x_)
for j in x:
    if j>=2:
        count += int((j*(j-1)/2))
for i in range(n):
    if x[a[i]-1]>=2:
        print(count-x[a[i]-1]+1)
    else:
        print(count)

Measured memory_bytes: 24744
package main

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

func main() {
	sc := NewScanner(os.Stdin)
	r := sc.NextInt()
	D := sc.NextInt()
	x := sc.NextInt()

	for i := 2001; i <= 2010; i++ {
		x = r*x - D
		fmt.Println(x)
	}
}

func vmin(v []int) int {
	mn := math.MaxInt32
	for i := 0; i < len(v); i++ {
		mn = min(mn, v[i])
	}
	return mn
}

func gcd(x, y int) int {
	if y > 0 {
		return gcd(y, x%y)
	}
	return x
}

func lcm(x, y int) int {
	return x / gcd(x, y) * y
}

func max64(x, y float64) float64 {
	if x > y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func min64(x, y float64) float64 {
	if x < y {
		return x
	}
	return y
}

// scanner
type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner(r io.Reader) *Scanner {
	rdr := bufio.NewReaderSize(r, 1024)
	return &Scanner{r: rdr}
}

func (s *Scanner) ReadLine() {
	s.buf = make([]byte, 0)
	for {
		line, isp, err := s.r.ReadLine()
		if err != nil {
			os.Exit(1)
		}
		s.buf = append(s.buf, line...)
		if !isp {
			break
		}
	}
}

func (s *Scanner) NextInt64() int64 {
	i, err := strconv.ParseInt(s.Next(), 10, 64)
	if err != nil {
		os.Exit(1)
	}
	return i
}

func (s *Scanner) NextInt() int {
	i, err := strconv.Atoi(s.Next())
	if err != nil {
		os.Exit(1)
	}
	return i
}

func (s *Scanner) NextFloat64() float64 {
	i, err := strconv.ParseFloat(s.Next(), 64)
	if err != nil {
		os.Exit(1)
	}
	return i
}

func (s *Scanner) Next() string {
	s.Pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	next := string(s.buf[start:s.p])
	s.p++
	return next
}

func (s *Scanner) Pre() {
	if s.p >= len(s.buf) {
		s.ReadLine()
		s.p = 0
	}
}


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

int main()
{
	int n, l;
	vector<string> v;
	cin >> n >> l;
	string aux;
	for (int i = 0; i < n; i++)
	{
		cin >> aux;
		v.push_back(aux);
	}
	sort(v.begin(), v.end());
	for(int i = 0; i < n; i++)
	{
		cout << v[i];
	}
	return 0;	
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <math.h>
#include <string>
#include <iomanip>
#include <locale>
#include <list>
#include <bitset>
using namespace std;
#define FORN(i,m,n) for(ll i=(m); i<ll(n); i++)
#define PRINTVEC(v) FORN(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define PRINTMAT(m) FORN(j,0,m.size()) {PRINTVEC(m[j]);}
#define PB(x) push_back(x)
#define MP(a,b) make_pair(a,b)
typedef long long ll;

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

int main(){
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  ll n,m;
  cin>>n>>m;
  vector<ll> v(n);
  FORN(i,0,n) cin>>v[i];
  sort(v.begin(),v.end());
  FORN(i,0,n) v[i] >>= 1;
  ll ans = v[0];
  FORN(i,1,n){
    ans = (ans * v[i]) / gcd(ans,v[i]);
    if(ans > m){
      cout<<0<<endl;
      return 0;
    }
  }
  bool ok = true;
  FORN(i,0,n) if(ans % (v[i] * 2) == 0) ok = false;
  cout<<(ok ? ((m / ans - 1) / 2 + 1) : 0)<<endl;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

#define int long long
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define MAX_L 22
int N;
vector<P> G[100000];
int U[MAX_L][100000], R[100000];
long long L[100000];

void dfs(int x, int p, int r, long long l) {
  U[0][x] = p;
  R[x] = r;
  L[x] = l;
  for (P pp : G[x]) {
    int t = pp._1;
    if (t == p) continue;
    dfs(t, x, r+1, l+pp._2);
  }
}

int lca(int a, int b) {
  if (R[a] > R[b]) swap(a, b);
  for (int k=0; k<MAX_L; k++) {
    if ((R[a] - R[b]) >> k & 1) b = U[k][b];
  }
  if (a == b) return a;
  for (int k=MAX_L-1; k>=0; k--) {
    if (U[k][a] != U[k][b]) {
      a = U[k][a];
      b = U[k][b];
    }
  }
  return U[0][a];
}
long long dist(int x, int y) {
  int g = lca(x, y);
  return L[x] + L[y] - 2LL*L[g];
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  rep(i, N-1) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    G[a].pb(P(b, c));
    G[b].pb(P(a, c));
  }
  rep(i, MAX_L) rep(j, N) U[i][j] = -1;
  dfs(0, -1, 0, 0);
  for (int i=0; i<MAX_L-1; i++) {
    for (int v=0; v<N; v++) {
      if (U[i][v] == -1) U[i+1][v] = -1;
      U[i+1][v] = U[i][U[i][v]];
    }
  }
  int Q, K;
  cin >> Q >> K;
  K--;
  rep(i, Q) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    cout << dist(x, K) + dist(K, y) << "\n";
  }
  return 0;
}


Measured memory_bytes: 33792
#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD 998244353
#define INF 93193111451418101
#define bitcnt(a) (ll) __builtin_popcount((a))
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

ll n, m;
vector<ll> a, imos;
int main() {
  cin >> n >> m;
  ll ret = 0;
  REP(i, n) {
    ll h;
    cin >> h;
    a.pb(h);
  }
  imos.pb(a[0] % m);
  REP(i, n) {
    if (i) {
      imos.pb(imos[i - 1] + a[i]);
      imos[i] %= m;
    }
  }
  sort(imos.begin(), imos.end());
  ll cnt = 0, mae = -114;
  REP(i, n) {
    if (imos[i] == 0) {
      ret++;
    }
    if (mae != imos[i]) {
      ret += ((cnt - 1) * cnt) / 2;
      cnt = 0;
      mae = imos[i];
    }
    cnt++;
  }
  ret += ((cnt - 1) * cnt) / 2;

  cout << ret << endl;
}


Measured memory_bytes: 2548
use std::error::Error;
use std::io::{self, BufReader};
use std::io::prelude::*;
use std::str::{self, FromStr};

fn exec() {
    let mut sc = Scanner::new(io::stdin());
    let (n, k): (usize, i64) = (sc.ne(), sc.ne());
    let a: Vec<i64> = (0..n).map(|_| sc.ne()).collect();
    type Int = i64;
    fn __gcd(a: Int, b: Int) -> Int {
        match b {
            0 => a,
            _ => __gcd(b, a % b),
        }
    }
    let gcd = a.iter().fold(0, |acc, &x| __gcd(x, acc));
    let ma = *a.iter().max().unwrap();
    if k > ma || k % gcd != 0 {
        print!("IM");
    }
    println!("POSSIBLE");
}

fn main() {
    const STACK: usize = 16 * 1024 * 1024;
    let _ = std::thread::Builder::new()
        .stack_size(STACK)
        .spawn(|| { exec(); })
        .unwrap()
        .join()
        .unwrap();
}

#[allow(dead_code)]
pub struct Scanner<R> {
    bufread: BufReader<R>,
    id: usize,
    buf: Vec<u8>,
}
impl<R: Read> Scanner<R> {
    pub fn new(resource: R) -> Scanner<R> {
        Scanner {
            bufread: BufReader::new(resource),
            id: 0,
            buf: Vec::new(),
        }
    }
    fn next_line(&mut self) -> Option<String> {
        let mut res = String::new();
        match self.bufread.read_line(&mut res) {
            Ok(0) => None,
            Ok(_) => Some(res),
            Err(why) => panic!("error in read_line: {}", why.description()),
        }
    }
    pub fn next<T: FromStr>(&mut self) -> Option<T> {
        while self.buf.is_empty() {
            self.buf = match self.next_line() {
                Some(r) => {
                    self.id = 0;
                    r.trim().as_bytes().to_owned()
                }
                None => return None,
            };
        }
        let l = self.id;
        assert_ne!(self.buf[l], b' ');
        let n = self.buf.len();
        let mut r = l;
        while r < n && self.buf[r] != b' ' {
            r += 1;
        }
        let res = match str::from_utf8(&self.buf[l..r]).ok().unwrap().parse::<T>() {
            Ok(s) => Some(s),
            Err(_) => {
                panic!(
                    "parse error, {:?}",
                    String::from_utf8(self.buf[l..r].to_owned())
                )
            }
        };
        while r < n && self.buf[r] == b' ' {
            r += 1;
        }
        if r == n {
            self.buf.clear();
        } else {
            self.id = r;
        }
        res
    }
    pub fn ne<T: FromStr>(&mut self) -> T {
        self.next::<T>().unwrap()
    }
}



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

int main(){
  int N, M;
  while(cin >> N >> M, N){
    vector<int> S(M);
    vector<int> P(N,0), PM(N,0);
    for(int i = 0; i < M; ++i){
      int k;
      cin >> S[i] >> k;
      for(int j = 0; j < k; ++j){
        int c;
        cin >> c;
        PM[c-1] += S[i];
        if(k == 1){
          P[c-1] += S[i];
        }
      }
    }
    vector<int> F(N+1,1e9), B(N+1,1e9);
    for(int i = 0; i < N; ++i){
      F[i+1] = min(F[i],P[i]);
    }
    for(int i = N-2; i >= 0; --i){
      B[i] = min(B[i+1],P[i+1]);
    }
    int ans = 0;
    for(int i = 0; i < N; ++i){
      int mi = min(F[i],B[i]);
      ans = max(ans,PM[i]-mi+1);
    }
    cout << ans << endl;
  }
}



Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int x,y;
  cin >> x >> y;
  int a[]={0,2,0,1,0,1,0,0,1,0,1,0};
  if(a[x-1]==a[y-1]){cout << "Yes" << endl;}
  else{cout << "No" << endl;}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int N, A[15], x[15][15], y[15][15];
bool check(int X){
for(int i=0;i<N;i++){ if(X&(1<<i)){ 
    for(int j=0; j<A[i]; j++){ int z=1<<(x[i][j])-1;
      if(X&z && y[i][j]==1){}else if(!(X&z) && y[i][j]==0){}
      else{ return false; }
    } 
  } }
return true;
}
int keta(int X){
int c=0;
for(int i=0;i<N;i++){ if(X&(1<<i)){c++;} }
return c;
}
int main(){
cin >> N; int i, j, ans=0;
for(i=0; i<N; i++){ 
  cin >> A[i];
  for(j=0; j<A[i]; j++){ cin >> x[i][j] >> y[i][j]; }                
}
for(i=pow(2,N)-1; i>=0; i--){
if(check(i)){ ans=max(ans,keta(i)); }
}
cout << ans << "\n";
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())

if N%2 == 0:
    ans = 0
    for i in range(1, 20):
        ans += (N//(10**i))
    for i in range(1, 40):
        A = (N//((5**i)*(10)))
        B = N//(10**(i+1))
        ans += A - B
    print(ans)
else:
    print(0)


Measured memory_bytes: 3060
from heapq import heapify, heappop, heappush

# 次の桁の生成ルール ex. 1 -> 10, 11, 12
def next_int(n):
    nums = {0: [0, 1],
            1: [0, 1, 2],
            2: [1, 2, 3],
            3: [2, 3, 4],
            4: [3, 4, 5],
            5: [4, 5, 6],
            6: [5, 6, 7],
            7: [6, 7, 8],
            8: [7, 8, 9],
            9: [8, 9]}
    return nums[n]

K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # とりあえず 1 桁目を初期値にとる
heapify(queue)

for _ in range(K-1):
    now = heappop(queue)  # 最小値を取り出す
    # 取り出した値を使って次の桁を生成し queue に投げる
    for next_i in next_int(now%10):
        heappush(queue, now*10 + next_i)

print(heappop(queue))  # K 回目に取り出す最小値


Measured memory_bytes: 12228
N = int(input())
A = list(map(int, input().split()))

A.sort()
c = 0
for a in A:
    if a <= 0:
        c += 1

if c == N or c == N-1:
    ans = A[-1] - sum(A[:-1])
    print(ans)
    a, b = A[-1], A[0]
    for i in range(1, N):
        print(a, b)
        a, b = a-b, A[i]
elif c == 0 or c == 1:
    ans = sum(A[1:]) - A[0]
    print(ans)
    a, b = A[0], 0
    for i in range(1, N-1):
        a, b = a-b, A[i]
        print(a, b)
    a, b = A[-1], a-b
    print(a, b)
else:
    ans = sum(A[c:]) - sum(A[:c])
    print(ans)
    a, b = A[0], 0
    for i in range(N-c-1):
        a, b = a-b, A[c+i]
        print(a, b)
    a, b = A[-1], a-b
    print(a, b)
    for i in range(c-1):
        a, b = a-b, A[i+1]
        print(a, b)
    

Measured memory_bytes: 14020
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int second = sc.nextInt();
        int h = second / 3600;
        int m = (second % 3600) / 60;
        int s = second % 60;
        System.out.println(h+":"+m+":"+s);
    }
}


Measured memory_bytes: 26352
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<x<<endl
const int maxn=(int)1e6+5;
typedef long long ll;

struct edge{
    ll to,a,b;
};
struct Data{
    ll v,s,t;
    bool operator < (const Data & a)const{return t>a.t;}
};

const ll  MAXN=50,MAXS=MAXN*50,INF=1e18;
ll dp[MAXN+1][MAXS+1];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n,m,s;cin>>n>>m>>s;
    vector<edge> E[MAXN+1];
    rep(i,1,m){
        int u,v,a,b;
        cin>>u>>v>>a>>b;
        E[u].push_back((edge){v,a,b});
        E[v].push_back((edge){u,a,b});
    }
    vector<int> c(n+1),d(n+1);
    rep(i,1,n){
        cin>>c[i]>>d[i];
    }
    s=min(s,MAXS);
    rep(i,1,n)rep(j,0,MAXS)dp[i][j]=INF;dp[1][s]=0;
    priority_queue<Data> Q;
    Q.push((Data){1,s,0});
    while(!Q.empty()){
        Data dt=Q.top();Q.pop();
        //debug(dt.v),debug(dt.s),debug(dt.t);
        //if(dt.s<0)continue;
        if(dt.t>dp[dt.v][dt.s])continue;
        //change
        ll ns=min(dt.s+c[dt.v],MAXS);
        ll nt=dt.t+d[dt.v];//?dp[dt.v][dt.s]+d[dt.v]
        if(dp[dt.v][ns]>nt){
            dp[dt.v][ns]=nt;
            Q.push((Data){dt.v,ns,nt});
        }
        // trans
       
        for(auto e:E[dt.v]){
            ns=dt.s-e.a;
            nt=dp[dt.v][dt.s]+e.b;//?dt.t+e.b
            if(ns>=0 and dp[e.to][ns]>nt){
                dp[e.to][ns]=nt;
                Q.push((Data){e.to,ns,nt});
            }
        }
    }
    rep(i,2,n){
        ll ans=INF;
        rep(j,0,MAXS){
            ans=min(ans,dp[i][j]);
            
        }
        cout<<ans<<endl;
    }
}
/* 
dp[i][j] min time takes from 1 to node i, have j coin with me.
dp[i][j]=dp[k][j-cost]
wr: 更新出错
 */

Measured memory_bytes: 7248
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string> //文字列
#include <iomanip> //doubleの桁数指定 setprecision()
#include <list> //前後に数値を入れれる配列
#include <map> //map
#include <vector> //vecror

#define REP(i,m,n) for(ll i = (ll) (m);i < (ll) (n);i++) //forの短縮
#define rep(i,n) REP(i,0,n) //REPが0の時
#define ll long long int

using namespace std;

double PI = acos(-1); //円周率
ll mod = 1e9 + 7;




//提出コード
long double a, b, h, m;
long double ax, ay, bx, by, arad, brad, ans;

//degree → radian
long double chg_DegRad(long double deg) {
	return deg * PI / 180.0;
}



int main() {
	cin >> a >> b >> h >> m;
	
	arad = chg_DegRad(30 * h + (long double)(m / 2));
	brad = chg_DegRad(6 * m);

	ax = a * sin(arad);
	ay = a * cos(arad);
	bx = b * sin(brad);
	by = b * cos(brad);

	ans = sqrt(pow(abs(ax - bx), 2) + pow(abs(ay - by),2));
	cout << setprecision(10) << ans << endl;



	return 0;
}



Measured memory_bytes: 4148
#include <algorithm>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

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

    if ((B - A) % 2 == 0)
        cout << "Alice\n";
    else
        cout << "Borys\n";

    return 0;
}


Measured memory_bytes: 256
let cnt = ref 0

let merge a l m r =
  let ai = Array.make (m - l + 1) max_int in
  for i = 0 to m - l - 1 do
    ai.(i) <- a.(l + i)
  done;
  let aj = Array.make (r - m + 1) max_int in
  for i = 0 to r - m - 1 do
    aj.(i) <- a.(m + i)
  done;
  let i = ref 0 in
  let j = ref 0 in
  for k = l to r - 1 do
    incr cnt;
    if ai.(!i) <= aj.(!j) then begin
      a.(k) <- ai.(!i);
      incr i;
    end else begin
      a.(k) <- aj.(!j);
      incr j;
    end
  done

let rec merge_sort a l r =
  if (l + 1) < r then begin
    let m = (l + r) / 2 in
    merge_sort a l m;
    merge_sort a m r;
    merge a l m r
  end

let () =
  let n = read_int () in
  let a = Array.init n (fun _ -> Scanf.scanf "%d " (fun i -> i)) in
  merge_sort a 0 n;
  print_int a.(0);
  for i = 1 to n - 1 do
    Printf.printf " %d" a.(i)
  done;
  print_newline ();
  Printf.printf "%d\n" !cnt

Measured memory_bytes: 22152
N, M = map(int, input().split())

tp_list = list()
for i in range(N):
    a, b = map(int, input().split())
    tp_list.append((a, b))

tp_list.sort()

cnt = 0
cost = 0
flg = False
for a, b in tp_list:
    for i in range(b):
        cnt += 1
        cost += a

        if cnt == M:
            flg = True
            break
    
    if flg:
        break

print(cost)

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

#define mp make_pair
#define mt make_tuple
#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 forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef double ld;
int main()
{ 
ios_base::sync_with_stdio(false);

cin.tie(NULL);
//freopen("input.txt", "r", stdin);
//reopen("output.txt","w",stdout);
ll n;
cin>>n;
ll a=n/1000;
char c=a+'A'+2;
cout<<"AB"<<c;
return 0;
}		


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int n,m;long k;
int x[1<<17],d[1<<17],a[1<<17];
int t[1<<17],s[1<<17],b[1<<17];
main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x[i];
		if(i)d[i-1]=x[i]-x[i-1];
		s[i]=i;
		t[i]=i;
	}
	cin>>m>>k;
	for(int i=0;i<m;i++)
	{
		cin>>a[i];
		a[i]-=2;
		t[a[i]]^=t[a[i]+1]^=t[a[i]]^=t[a[i]+1];
	}
	while(k)
	{
		if(k&1)
		{
			for(int i=0;i<n-1;i++)s[i]=t[s[i]];
		}
		for(int i=0;i<n-1;i++)b[i]=t[t[i]];
		for(int i=0;i<n-1;i++)t[i]=b[i];
		k>>=1;
	}
	long now=x[0];
	cout<<now<<endl;
	for(int i=0;i<n-1;i++)
	{
		now+=d[s[i]];
		cout<<now<<endl;
	}
}

Measured memory_bytes: 3584
// 2019.9.15 bal4u
// Template for Online Contest

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef long long ll;

#define gc() getchar()
#define pc(c) putchar(c)

int in() {  // 整数の入力
	int n = 0, c = gc();
	if (c == '-') {	c = gc();
		do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
		return -n;
	}
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

ll inL() {  // long long 整数の入力
	ll n = 0; int c = gc();
	if (c == '-') {	c = gc();
		do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
		return -n;
	}
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void out(int n) { // 整数の表示
	int i; char b[30];
	if (!n) pc('0');
	else {
		if (n < 0) pc('-'), n = -n;
		i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(b[i]);
	}
	pc('\n');
}

void outL(ll n) { // 整数の表示
	int i; char b[30];
	if (!n) pc('0');
	else {
		if (n < 0) pc('-'), n = -n;
		i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(b[i]);
	}
	pc('\n');
}

int ins(char *s) { // 文字列の入力
	char *p = s--;
	do *++s = gc();
	while (*s > ' ');
	*s = 0;
	return s - p;
}

void outs(char *s) {  // 文字列の表示
	while (*s) pc(*s++);
}

#define MIN(a,b)  ((a)<=(b)?(a):(b))
#define MAX(a,b)  ((a)>=(b)?(a):(b))
#define ABS(a)    ((a)>=0?(a):-(a))
inline static int chmax(int *a, int b) { if (*a < b) *a = b; }
inline static ll  chmaxL(ll *a, int b) { if (*a < b) *a = b; }
inline static int chmin(int *a, int b) { if (*a > b) *a = b; }
inline static ll  chminL(ll *a, int b) { if (*a > b) *a = b; }

int cmp_int(const void *u, const void *v) { return *(int *)u - *(int *)v; }

char S[105]; int w;

int main()
{
	int i;
	w = ins(S);
	for (i = 0; i < w; i++) {
		if (i & 1) {
			if (S[i] == 'L' || S[i] == 'U' || S[i] == 'D');
			else goto No;
		} else {
			if (S[i] == 'R' || S[i] == 'U' || S[i] == 'D');
			else goto No;
		}
	}
	puts("Yes"); return 0;
No: puts("No"); return 0;
}



Measured memory_bytes: 128
#B問題
N=int(input())
Msum=int(N*(N-1)/2)
subedge=[]
if N%2==0:
    for i in range(int(N/2)):
        subedge.append([i+1,N-i])
    M=Msum-len(subedge)
else:
    for i in range(int((N-1)/2)):
        subedge.append([i+1,N-i-1])
    M=Msum-len(subedge)
print(M)
for i in range(N-1):
    j=0
    for j in range(N-i-1):
        I=i+1
        J=I+j+1
        edge=[I,J]
        if edge not in subedge:
            print(I,J)
        else:
            pass

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = a; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int MOD = 2;
const int INF = 2e18;

signed main() {
    int N, M;
    cin >> N >> M;
    vector<int> temp;
    for (int i = 0; i < N; i++) {
        temp.push_back(2);
    }
    for (int i = 0; i < M; i++) {
        temp.push_back(1);
    }
    int ans = 0;
    for (int i = 0; i < temp.size(); i++) {
        for (int j = i + 1; j < temp.size(); j++) {
            int base = temp[i] + temp[j];
            if (base % 2 == 0) ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#define clr(x,y) memset(x,y,sizeof x)
#define ll long long
using namespace std;

const int maxn=200010;

struct Edge
{
    int to,next;
    ll w;
}edge[maxn];
int head[maxn];
ll f[maxn],cnt;
void init()
{
    cnt=0;
    clr(head,-1);
    clr(f,0);

}

void add(int u,int v,int w)
{
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

void dfs(int u,ll dist,int fa)
{
    f[u] = dist;
    for (int i=head[u];~i;i=edge[i].next)
    {
       int v=edge[i].to;
       if (v==fa) continue;
       dfs(v,dist + edge[i].w,u);
    }
}


int u,v,w,q,k;
int main()
{
    int n;
    scanf("%d",&n);
    init();
    for (int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    scanf("%d%d",&q,&k);
    dfs(k,0,-1);
    for (int i=1;i<=q;i++)
    {
        scanf("%d%d",&u,&v);
        printf("%lld\n",f[u] + f[v]);
    }
    return 0;
}


Measured memory_bytes: 11904
S = str(input())
N = len(S)
if S == S[::-1] and S[:(N-1)//2] == S[(N-1)//2-1::-1] and S[(N+3)//2-1:N] == S[-1:(N+3)//2-2:-1]:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long

const int MXN = 1e6 + 7;

using namespace std;

ll n, a[MXN], cnt, ans, m;

int main() {
  cin >>n;
  for(int i = 1; i <= n; i ++) cin >>a[i];
  sort(a + 1, a + n + 1);
  reverse (a + 1, a + n + 1);
  for(int i = 1; i <= n; i ++) {
    if(i % 2 == 1) cnt += a[i];
    else cnt -= a[i];
  } cout <<cnt;
}


Measured memory_bytes: 256
//in the name of god
//if you read this code please search about imam hussain
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define endl "\n";
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);

const int maxn=1e5+5;
const int mod=1000000007;
const int inf=1e9;
const int del=728729;
ll arr[maxn],dp[maxn];
int main(){
	migmig;
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		arr[x]=-1;
	}
	if(arr[1]==-1){
		dp[1]=0;
	}else dp[1]=1;
	if(arr[2]==-1){
		dp[2]=0;
	}else dp[2]=1+dp[1];
	for(int i=3;i<=n;i++){
		dp[i]=dp[i-1]%mod+dp[i-2]%mod;
		dp[i]=dp[i]%mod;
		if(arr[i]==-1){
			dp[i]=0;
		}
	}
	cout<<dp[n]%mod;
	return 0;
}



Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pint;

int main(){
  int n;
  cin>>n;
  vector<pint> a(n),b(n);
  for(int i=0;i<n;++i)cin>>a[i].first>>a[i].second;
  for(int i=0;i<n;++i)cin>>b[i].first>>b[i].second;
  
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  int ans=0;
  multiset<int> st;
  int j=0;
  for(int i=0;i<n;++i){
    while(a[j].first<b[i].first&&j<n)st.insert(a[j++].second);
    auto it=st.lower_bound(b[i].second);
    if(it!=st.begin()){
      ans++;
      st.erase(--it);
    }
  }
  cout<<ans<<endl;
}


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

int main(){
    ll n,a,b;
    cin>>n>>a>>b;
    ll ans;
    if((b-a)%2==0){
        cout<<(b-a)/2<<endl;
        return 0;
    }
    else{
        ans=(b-a)/2+1+a-1;
        ans=min(ans, (b-a)/2+1+(n-b));
        cout<<ans<<endl;
        return 0;
    }
}

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000100
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)

typedef long long LL;
typedef long double LD;

int main(){
  int n,m;
  cin >> n >> m;
  vector<pair<int,int>> tre(n);
  map<int,int> xmp,ymp;
  rep(i,n){
    cin >> tre[i].first >> tre[i].second;
    xmp[tre[i].first]=-1;
    ymp[tre[i].second]=-1;
  }
  xmp[IINF]=-1;
  ymp[IINF]=-1;
  int xsz=0;
  for(auto &p:xmp) p.second=(xsz++);
  int ysz=0;
  for(auto &p:ymp) p.second=(ysz++);
  vector<vector<int>> rui(xsz+1,vector<int>(ysz+1,0));
  rep(i,n){
    rui[xmp[tre[i].first]+1][ymp[tre[i].second]+1]++;
  }
  repp(i,1,xsz+1){
    repp(j,1,ysz+1){
      rui[i][j]+=rui[i-1][j]+rui[i][j-1]-rui[i-1][j-1];
    }
  }
  int x1,y1,x2,y2;
  rep(i,m){
    cin >> x1 >> y1 >> x2 >> y2;
    x1=xmp.lower_bound(x1)->second;
    y1=ymp.lower_bound(y1)->second;
    x2=xmp.upper_bound(x2)->second;
    y2=ymp.upper_bound(y2)->second;
    cout << rui[x2][y2]-rui[x1][y2]-rui[x2][y1]+rui[x1][y1] << endl;
  }
  return 0;
}



Measured memory_bytes: 101280