akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
class Program
    {
        class Node
        {
            int id;
            public int dist;
            public List<Node> links;
            public Node(int i)
            {
                this.id = i;
                this.links = new List<Node>();
                this.dist = -1;
            }
            public void connectTo(Node n)
            {
                this.links.Add(n);
            }
        }
    	static void Main(string[] args)
    	{
            string[] s1 = Console.ReadLine().Split(' ');
            int n = int.Parse(s1[0]), m = int.Parse(s1[1]);
            Node[,] nodes = new Node[n, 3];
            for (int i=0; i<n; i++)
            {
                for (int j=0; j<3; j++)
                {
                    nodes[i, j] = new Node(i + j * 1000000);
                }
            }
            for (int i=0; i<m; i++)
            {
                string[] s2 = Console.ReadLine().Split(' ');
                int u = int.Parse(s2[0]) - 1, v = int.Parse(s2[1]) - 1;
                for (int j=0; j<3; j++)
                {
                    nodes[u, j].connectTo(nodes[v, (j + 1) % 3]);
                }
            }
            Queue<Node> que = new Queue<Node>();
            string[] s3 = Console.ReadLine().Split(' ');
            int s = int.Parse(s3[0]) - 1, t = int.Parse(s3[1]) - 1;
            nodes[s, 0].dist = 0;
            que.Enqueue(nodes[s, 0]);

            while(que.Count > 0)
            {
                Node looking = que.Dequeue();
                foreach (Node nn in looking.links)
                {
                    if (nn.dist < 0)
                    {
                        nn.dist = looking.dist + 1;
                        que.Enqueue(nn);
                    }
                }
            }
            if (nodes[t, 0].dist < 0) Console.WriteLine(-1);
            else Console.WriteLine(nodes[t, 0].dist / 3);
            
        }
    }

Measured memory_bytes: 63876
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
using namespace __gnu_pbds;  
using namespace std;



typedef tree<long long, null_type, less<long long>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    new_data_set; 
    
    
    
//defines
typedef long long ll;
typedef long double ld;

ll a,b,c,n,m,k;

ll t=1;


void solve()
{
   cin>>n>>m>>k;
   if(n>m)swap(n,m);
   if(k>=n and k<=m)cout<<"Yes";
   else cout<<"No";
 if(t>0)cout<<"\n";
}



int32_t main()
{
#ifdef ONPC
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  //cin>>t;
    while(t--)
    {
        solve();
    }
  //cout<<sum;
        
    return 0;
}

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

namespace ConsoleApp5
{
    class Program
    {

        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int[] res = new int[100];

            for(int i=0; i<=N; i++)
            {
                int A = i.ToString()[0] - '0';
                int B = i % 10;
                res[A * 10 + B]++;
            }

            long ans = 0;
          
            for(int i=1; i<=9; i++)
            {
                for(int j=1; j<=9; j++)
                {
                    ans += res[i * 10 + j] * res[j * 10 + i];
                }
            }

            Console.WriteLine(ans);

        }
    }
}

Measured memory_bytes: 15312
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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

typedef long long ll;
typedef pair<ll, ll> p;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int k;
  string s;
  cin >> k >> s;
  if(int(s.size()) <= k) cout << s << endl;
  else cout << s.substr(0, k) << "..." << endl;
}


Measured memory_bytes: 3656
n = int(input())

x = []
y = []
h = []
for i in range(n):
    xi, yi, hi = map(int, input().split())
    x.append(xi)
    y.append(yi)
    h.append(hi)

isOk = False
i = 0
j = 0
constant = -1

for i in range(101):
    for j in range(101):

        constant = -1
        for xi, yi, hi in zip(x, y, h):
            if hi != 0:
                temp = hi+ abs(i - xi) + abs(j - yi)

                if constant == -1:
                    constant = temp

                if constant != temp:
                    break
        else:

            for xj, yj, hj in zip(x, y, h):
                if hj == 0 and constant - abs(i - xj) - abs(j - yj) > 0:
                    break
            else:
                isOk = True
                break
        
    if isOk:
        break

print(i, j, constant)
        


Measured memory_bytes: 3064
#[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, usize1) => {
        read_value!($next, usize) - 1
    };

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

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::io::{stdout, stdin, BufWriter, Write};

fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }

    input!{
      n: usize,
      aa: [usize; n],
    }
    let mut bb: Vec<_> = aa.iter().map(|&v|v).collect();
    bb.sort();
    bb.dedup();
    let mut count = vec![0; n];
    let mut pos = vec![n; n];
    for i in 0..n {
        let a = aa[i];
        let idx = bb.binary_search(&a).unwrap();
        count[idx] += 1;
        pos[idx] = min(pos[idx], i);
    }

    let mut ans = vec![0; n];
    let mut nums = 0;
    let mut cur_pos = n;
    for i in (0..bb.len()).rev() {
        nums += count[i];
        let value = bb[i];

        // Get next lower value
        let next = if i == 0 {
            0
        } else {
            bb[i-1]
        };

        cur_pos = min(cur_pos, pos[i]);
        ans[cur_pos] += (value - next) * nums;
    }

    for a in ans {
        puts!("{}\n", a);
    }
}


Measured memory_bytes: 9212
n = int(input())
a = [int(i) for i in input().split()]
cnt = 0
for i in range(n):
    minj = i
    for j in range(i,n):
        if a[j] < a[minj]:
            minj = j
    if i != minj:
        a[i], a[minj] = a[minj], a[i]
        cnt += 1
print(' '.join([str(i) for i in a]))
print(cnt)



Measured memory_bytes: 5608
#include<iostream>

int main(){
	char map[26][2];
	map[0][0] = 'x';
	map[0][1] = 'y';
	map['x'-'a'][0] = 'u';
	map['x'-'a'][1] = 'z';
	map['y'-'a'][0] = 'x';
	map['y'-'a'][1] = 'u';
	map[25][0] = 'w';
	map[25][1] = 'b';
	map['w'-'a'][0] = 'b';
	map['w'-'a'][1] = 'y';
	map[1][0] = 'y';
	map[1][1] = 'x';
	map['u'-'a'][0] = 'u';
	map['u'-'a'][1] = 'u';
	
	std::string route;
	while(std::cin >> route, route != "#"){
		char city = 'a';
		for(int i=0;i<route.size();i++){
			city = map[city-'a'][route[i]-'0'];
		}
		std::cout << (city=='b'?"Yes":"No") << std::endl;
	}
}

Measured memory_bytes: 1180
#include <stdio.h>
#include <math.h>
 
#define sqr(x) ((x) * (x))
 
typedef struct point {
  double x;
  double y;
}Point;
 
int main(void)
{
  Point p1, p2;
 
  scanf("%lf %lf %lf %lf", &p1.x, &p1.y, &p2.x, &p2.y);
 
  printf("%f\n", sqrt(sqr(p2.x - p1.x) + sqr(p2.y - p1.y)));
 
  return 0;
}
 

 

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

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (long long i = 0; i < (long long) (n); ++i)
#define pb emplace_back
#define endl '\n'

template<typename T> void _dbg(const char*_s,T _h) { cerr<<_s<<" = "<<_h<<"\n"; }

template<typename T, typename... Ts> void _dbg(const char*_s,T _h,Ts... _t) {
    for(int _b=0;((_b+=*_s=='(')-=*_s==')')!=0||*_s!=',';)cerr<<*_s++;
    cerr<<" = "<<_h<<",";_dbg(_s+1,_t...);
}

#define int long long

#ifdef LOCAL
    #define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
    #define dbg(...)
#endif

const int N = 500 * 1000 + 17;
const int MOD = 1000 * 1000 * 1000 + 7;

int n;
string s;
vector<int> v['Z' + 1];

bool read() {
    if (!(cin >> n >> s))
        return false;

    return true;
}

int get(char c, int r) {
    return upper_bound(v[c].begin(), v[c].end(), r) - v[c].begin();
}

int get(char c, int l, int r) {
    return max(0ll, get(c, r) - get(c, l - 1));
}

void solve(int id = 0) {
    forn (i, n)
        v[s[i]].pb(i);

    int ans = 0; 

    forn (i, n) {
        int x = 'R';
        int y = 'G';

        if (s[i] == 'R') {
            x = 'B';
        } else if (s[i] == 'G') {
            y = 'B';
        }

        ans += get(x, 0, i - 1) * get(y, i + 1, n - 1);
        ans += get(y, 0, i - 1) * get(x, i + 1, n - 1);

        for (int l = 0; i - l >= 0 && i + l < n; ++l)
            if (s[i - l] != s[i] && s[i + l] != s[i] && s[i - l] != s[i + l])
                --ans;
    }

    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    T = 1;

    while (read())
        solve(T++);

    return 0;
}



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


int main() {
    int N;
    cin >> N;
    int A;
    bool flag = true;
    for(int i=0;i<N;i++) {
        cin >> A;
        if(A%2) continue;
        if(A%3 != 0 && A%5 != 0) flag = false;
    }
    if(flag) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;
}

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

typedef long long ll;
typedef pair<int, int> ii;
const int mod = 1e9+7;
const ll INF = 1e18;
const int inf = 1e9;

void solve()
{
  int n,k; cin>>n>>k;
  vector<int> v(n);
  for (int i=0; i<n; i++) cin>>v[i];

  int ans=0;
  for (int l=0; l<=n; l++) for (int r=0; l+r<=n; r++) {
    int kc = k-l-r;
    if (kc < 0) continue;

    vector<int> a;
    for (int i=0; i<l; i++) {
      a.push_back(v[i]);
    }
    for (int i=0; i<r; i++) {
      a.push_back(v[n-i-1]);
    }
    sort(a.rbegin(), a.rend());
    while (a.size() && a.back()<0 && kc>0) {
      a.pop_back();
      kc -= 1;
    }
    int sum=0;
    for (int i=0; i<(int)(a.size()); i++) {
      sum += a[i];
    }
    ans = max(ans, sum);
  }
  cout << ans << endl;
}

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


Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [usize; n]
    };
    let mut res = 0;
    for i in 0..a.len() {
        if i%2 == 0 && a[i]%2 == 1 { res += 1 }
    }
    println!("{}", res);
}


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

int main() {
    int n, k;
    cin >> n >> k;
    int a[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<int> v(200000, 0);
    for (int i = 0; i < n; i++)
        v[a[i]]++;
    sort(v.begin(), v.end(), greater<int>());
    int ans = 0;
    for (int i = k; i < v.size(); i++) {
        ans += v[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main(){
    int a,b,c,d,n;
    cin >> n >> a >> b >> c >> d;
    int ap = (n + (a - 1))/a*b;
    int cp = (n + (c - 1))/c*d;
    if(ap > cp ){
        ap = cp;
    } 
    cout << ap << endl;
    return 0;
}


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

int main() {
    int h, w;
    vector<string> ss;

    cin >> h >> w;
    ss = vector<string>(h);

    for (int i = 0; i < h; i++) {
        cin >> ss.at(i);
    }
    for (int i = -1; i < h+1; i++) {
        if (i > -1 && i < h) {
            cout << "#" << ss.at(i) << "#" << endl;
        } else {
            for (int j = 0; j < w+2; j++) {
                cout << "#";
            }
            cout << endl;
        }
    }
}


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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;

int n, m;
pair<int,int> A[maxn];
int a[maxn];
int b[maxn];

vector<pair<int,int>> g[maxn];
bool viz[maxn];
vector<int> ans;


// don't worry about cycles because then flipping the ones we've seen
// so far is equivalent to flipping that one.
void dfs(int at) {
  viz[at]=true;
  for (auto ed: g[at]) {
    int j = ed.first;
    int to = ed.second;
    if (viz[to]) continue;
    dfs(to);

    // we have to greedily flip here because we're the only ones
    // who can fix it
    if (b[to]==1) {
      b[at]^=1;
      ans.push_back(j);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  cin>>n>>m;
  for (int i=0; i<n; i++) {
    cin>>A[i].first>>A[i].second;
    a[i] = A[i].first;
  }

  sort(a,a+n);
  sort(A,A+n);
  for (int i=1; i<n; i++) {
    b[i] = A[i].second^A[i-1].second;
  }

  b[0] = A[0].second;
  b[n] = A[n-1].second;

  for (int i=0; i<m; i++) {
    int l,r; cin>>l>>r;
    // mark [inclusive, exclusive)
    r = std::upper_bound(a,a+n,r) - a;
    l = std::lower_bound(a,a+n,l) - a;
    g[r].push_back({i,l});
    g[l].push_back({i,r});
  }

  for (int i=0; i<=n; i++) {
    if (!viz[i]) {
      dfs(i);

      // we did all the necessarily flips and it doesn't work out for us
      if (b[i]==1) out(-1);
    }
  }
  


  sort(ans.begin(), ans.end());
  cout<<ans.size()<<endl;
  for (int x: ans) cout<<x+1<<" ";
  cout<<endl;  

  return 0;
}
// don't forget to read in the input :^)


Measured memory_bytes: 45564
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
//typedef __int128_t Int;
#define DBG 1
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define loop(n) rep(loop,(0),(n))
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

int f(int x){
  int ret=0;
  while(x%2==0){
    x/=2;
    ret++;
  }
  return ret;
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(12);

  int N; cin >> N;
  int ans=0;
  vector<int> a(N); rep(i, 0, N){ cin >> a[i];ans+=f(a[i]); }
  cout<<ans<<endl;
  
  


    return 0;
}


Measured memory_bytes: 384
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

using Pair = pair<int, int>;
using lint = long long;

// const int mod = 1e9 + 7;
// const int mod = 998244353;

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

int main(){
  lint n,d;
  cin >> n >> d;
  int ret = 0;
  for (int i = 0; i < n; i++) {
    lint x, y;
    cin >> x >> y;
    if (x * x + y * y <= d * d) ret++;
  }
  cout << ret << endl;
}


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

#define lint long long
#define P pair<int, int>


int main() {
    string S;
    cin >> S;

    int a = (S[0] - '0') * 10 + (S[1] - '0');
    int b = (S[2] - '0') * 10 + (S[3] - '0');

    bool ta = (a <= 12) && (a > 0);
    bool tb = (b <= 12) && (b > 0);

    if(ta){
        if(tb){
            cout << "AMBIGUOUS" << endl;
        } else {
            cout << "MMYY" << endl;
        }
    } else {
        if(tb){
            cout << "YYMM" << endl;
        } else {
            cout << "NA" << endl;
        }
    }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main() {
  int k, s;
  int i, j;
  int count = 0;
  scanf("%d %d", &k, &s);

  for (i = 0; i <= k; i++) {
    for (j = 0; j <= k; j++) {
      if (s - i - j <= k && s-i-j >= 0) {
        count++;
      }
    }
  }

  printf("%d", count);

  return 0;
}

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

using namespace std;

typedef long long ll;

#define FOR(a, b, i) for(int i=a; i<b; i++)
#define RFOR(a, b, i) for(int i=a; i>=b; i--)
#define PB push_back
#define MP make_pair
#define MOD 1e9+7
#define newline cout<<"\n"

void add_self(ll &a, ll b)
{
    a+=b;
    if(a>=MOD) a-=MOD;
}


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

    int h, w; cin>>h>>w;
    vector<string> v(h);

    FOR(0, h, i) cin>>v[i];

    vector<vector<ll> > dp(h, vector<ll> (w, 0));
    // ll x = 5, y=2;
    // add_self(x, y);
    // cout<<x;
    // newline;

    dp[0][0] = 1;

    FOR(0, h, i)
    {
        FOR(0, w, j)
        {
            if(v[i][j]=='.')
            {
                if(i>0) add_self(dp[i][j], dp[i-1][j]);
                if(j>0) add_self(dp[i][j], dp[i][j-1]);
            }
        }
    }

    cout<<dp[h-1][w-1];
    newline;


    return 0;
}

Measured memory_bytes: 9216
L=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K=int(input())
print(L[K-1])

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

int main(){
  int x, y;
  cin >> x >> y;
  if(x<y){
    if(x<0 && 0<y){
      if(-x<y){
        cout << x+y+1 << endl;
      }else if(-x>y){
        cout << -y-x+1 << endl;
      }else{
        cout << 1 << endl; 
      }
    }else{
      cout << y-x << endl;
    }
  }else{
    if(y<0 && 0<x){
      if(-y<x){
        cout << x+y+1 << endl;
      }else if(-y>x){
        cout << -y-x+1 << endl;
      }else{
        cout << 1 << endl; 
      }
    }else{
      if(x==0){
        cout << -y+1 << endl;
      }else if(y==0){
        cout << x+1 << endl;
      }else{
      	cout << (-y)-(-x)+2 << endl;
      }
    }
  }
  return 0;
}
  


Measured memory_bytes: 3616
#include <bits/stdc++.h>
 
 #define int long long
 #define pa pair<int,int>
  #define  mp make_pair
  #define  pb push_back
 using namespace std;




vector<pa> kouho;
vector<pair<double,pa>> conv;


bool hikaku(pa x,pa y){
	if(x.second!=y.second)return x.second<y.second;
	return x.first>y.first;
}

double kouten(pa t,pa s){
	return (s.first-t.first+0.0)/(t.second-s.second);
}

void make_conv(){
	sort(kouho.begin(),kouho.end(),hikaku);
	int n=kouho.size();
	
	conv.pb(mp(0.0,mp(0,0)));
	for(int i=1;i<n;i++)if(kouho[i].second>kouho[i-1].second){
		
		while(1){
			double kou=kouten(conv.back().second,kouho[i]);
			if(conv.back().first<kou){
				conv.pb(mp(kou,kouho[i]));
				break;
			}
			conv.pop_back();
		}
	}

}


double query(int x,int v){
	int n=conv.size();
	int si=0,ue=n;
	while(ue-si>1){
		int me=(ue+si)/2;
		if(conv[me].second.second<=v){
			si=me;
			continue;
		}
		double kou=kouten(mp(x,v),conv[me].second);
		if(kou>=conv[me].first) si=me;
		else ue=me;
	}
	double kotae=kouten(mp(x,v),conv[si].second);
	return kotae;
}


double ans[200020];
bool muri[200020]={};

 signed main(){
 	
 
    cin.tie(0);
	ios::sync_with_stdio(false);
	
 	int n;
 	cin>>n;
 	
 	int xx,vv;
 	cin>>xx>>vv;
 	vector<pa> ve(n);
 	for(int i=0;i<n;i++){
 		int y,yy;
 		cin>>y>>yy;
 		ve[i]=mp(y-xx,yy-vv);
 	}
 	kouho.pb(mp(0,0));
 	for(auto v:ve)if(v.first<0 && v.second>0)kouho.pb(v);
 	make_conv();
 	for(int i=0;i<n;i++)if(ve[i].first>0){
 		if(ve[i].second>=conv.back().second.second)muri[i]=1;
 		else ans[i]=query(ve[i].first,ve[i].second);
 	}
 	
 	kouho.clear();
 	conv.clear();
 	kouho.pb(mp(0,0));
 	
 	for(auto v:ve)if(v.first>0 && v.second<0){
 		pa w=v;
 		w.first*=-1,w.second*=-1;
 		kouho.pb(w);
 	}
 	make_conv();
 	for(int i=0;i<n;i++)if(ve[i].first<0){
 		if(-ve[i].second>=conv.back().second.second)muri[i]=1;
 		else ans[i]=query(-ve[i].first,-ve[i].second);
 	}
 	
 	for(int i=0;i<n;i++){
 		if(muri[i])printf("-1\n");
 		else{
 			printf("%.14lf\n",ans[i]);
 			if(ans[i]<0) exit(1);
 		}
 	}
return 0;

 }


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

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

	vector<int> a(n);
	for (int i=0;i<n;++i)
	{
		cin >> a[i];
	}

	vector<int64_t> dp(s+1);
	dp[0]=0;
	const int mod=998244353;
	for (int i=0;i<n;++i)
	{
		for (int j=s;j>=0;--j)
		{
			dp[j]+=dp[j];
			if (j>=a[i])
			{
				dp[j]+=dp[j-a[i]];
			}
			if (j==a[i])
			{
				++dp[j];
			}
			if (j==0)
			{
				++dp[j];
			}
			if (dp[j]>=mod)
			{
				dp[j]%=mod;
			}
		}
	}

	cout << dp[s] << endl;
}






Measured memory_bytes: 3636
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    sum_even_A = sum(A[::2])
    B = [sum(A)-2*sum(A[1::2])]
    for i in range(1,N):
        B.append(2*A[i-1]-B[i-1])
        
    print(' '.join(map(str, B)))
    
solve()

Measured memory_bytes: 24904
#include <stdio.h>
 
int main(void) {
	int x1, y1, x2, y2, x3, y3, x4, y4;
	scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
	x3 = x2-y2+y1;
	y3 = y2+x2-x1;
	x4 = x1-y2+y1;
	y4 = y1+x2-x1;
	printf("%d %d %d %d", x3, y3, x4, y4);
	return 0;
}

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

// ------ graph ------ //
using Weight = long long;
using Flow = int;
struct Edge {
    int src, dst;
    Weight weight;
    Flow cap;
    Edge() : src(0), dst(0), weight(0) { }
    Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // pqが降順のため
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
using Edges = vector<Edge>;
struct Graph {
    vector<Edges> adj;
    Graph(int n) : adj(n) { }
    int size() { return adj.size(); }
    Edges operator [] (int v) { return adj[v]; }
    void add_edge(int a, int b, Weight w = 1) { // graph
        adj[a].emplace_back(a, b, w);
        adj[b].emplace_back(b, a, w);
    }
    void add_arc(int a, int b, Weight w = 1) {  // digraph
        adj[a].emplace_back(a, b, w);
    }
};
using Array = vector<Weight>;
using Matrix = vector<Array>;
using UnweightedGraph = vector<vector<int>>;

// ------ StronglyConnectedComponents ------ //
struct StronglyConnectedComponents {
    const UnweightedGraph &g;
    UnweightedGraph gg, rg;
    vector<int> comp, order, seen;
    StronglyConnectedComponents(UnweightedGraph &g)
    : g(g), gg(g.size()), rg(g.size()), comp(g.size(), -1), seen(g.size(), 0) {
        for (int u = 0; u < g.size(); ++u) {
            for (int v: g[u]) {
                gg[u].emplace_back(v);
                rg[v].emplace_back(u);
            }
        }
    }
    int operator[](int k) { return comp[k]; }
    void dfs(int u) {
        seen[u] = true;
        for (int v: gg[u]) if (!seen[v]) dfs(v);
        order.emplace_back(u);
    }
    void rdfs(int u, int id) {
        comp[u] = id;
        for (int v: rg[u]) if (comp[v] == -1) rdfs(v, id);
    }
    UnweightedGraph build() {
        for (int u = 0; u < gg.size(); ++u) if (!seen[u]) dfs(u);
        reverse(begin(order), end(order));
        int id = 0;
        for (int u: order) if (comp[u] == -1) rdfs(u, id++);
        UnweightedGraph g_comp(id);
        for (int u = 0; u < g.size(); ++u) for (int v: g[u]) {
            int x = comp[u], y = comp[v];
            if (x != y) g_comp[x].push_back(y);
        }
        return g_comp;
    }
};

int main() {
    int V, E; cin >> V >> E;
    UnweightedGraph g(V);
    while (E--) {
        int s, t; cin >> s >> t;
        g[s].emplace_back(t);
    }
    StronglyConnectedComponents scc(g);
    scc.build();
    int Q; cin >> Q;
    while (Q--) {
        int u, v; cin >> u >> v;
        cout << (scc[u] == scc[v]) << endl;
    }
    return 0;
}


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

int main()
{
	/*#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif*/
	int n,k;
	scanf("%d%d",&n,&k);
	vector<int> a(n);
	for(int& x:a){
		scanf("%d",&x);
	}
	// dp[i] - TRUE first player wins with i remaininig stones
	vector<bool> dp(k+1);
	for(int stones=0;stones<=k;stones++)
	{
		for(int x:a){
			if(stones>=x&&!dp[stones-x])
				dp[stones]=true;
		}
		
	}
	printf("%s",dp[k]?"First":"Second");
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char arr[1001];
int main()
{
	int n;
	int i;
	scanf("%s",arr);
	scanf("%d",&n);
	for(i=0;i<strlen(arr);i++)
	{
		if(i%n==0)
		{
			printf("%c",arr[i]);
		}
	}
	return 0;		 
}

Measured memory_bytes: 256
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<iostream>
#include<algorithm>
#define LL long long
#define add_edge(u,v) nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
char ch;bool fs;void re(int& x)
{
	while(ch=getchar(),ch<33);
	if(ch=='-')fs=1,x=0;else fs=0,x=ch-48;
	while(ch=getchar(),ch>33)x=x*10+ch-48;
	if(fs)x=-x;	
}
using namespace std;
int n,sum;
int main()
{
	re(n);
	for(int c=n;c;c/=10)
		sum+=c%10;
	puts(n%sum?"No":"Yes");
}

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

int main() {
  vector<char> vec(9);
  for (int i = 0; i < 9; i ++) {
    cin >> vec.at(i);
  }

  cout << vec.at(0) << vec.at(4) << vec.at(8) << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}
template<typename T>
ostream& operator << (ostream& os, vector<T>& vs){
  for (const T& v : vs) os << v << " ";
  return os;
}

LL dp[2001][2001];

int main() {
  int N; cin >> N;
  vector<pair<LL, LL>> ps(N);  // A[i], index
  for (int i = 0; i < N; ++i) {
    LL a; cin >> a;
    ps[i] = {a, i};
  }

  sort(ps.rbegin(), ps.rend());
  for (int x = 0; x < N; ++x) {
    for (int y = 0; y < N; ++y) {
      dp[x][y] = 0;
    }
  }

  for (int n = 0; n < N; ++n) {
    auto [a, i] = ps[n];
    for (int x = 0; x <= n; ++x) {
      int y = n - x;
      dp[x + 1][y] = max<LL>(dp[x + 1][y], dp[x][y] + abs(i-x) * a);
      dp[x][y + 1] = max<LL>(dp[x][y + 1], dp[x][y] + abs(i-(N-1-y)) * a);
    }
  }

  LL vmax = 0;
  for (int x = 0; x <= N; ++x) {
    vmax = max(vmax, dp[x][N-x]);
  }
  cout << vmax << endl;
}


Measured memory_bytes: 34876
n=list(map(int,input()))

arr = [1, -1]
tmp = []
for i in arr:
	for j in arr:
		for k in arr:
			if n[0] + i*n[1] + j*n[2] + k*n[3] == 7:
				ar2 = [i,j,k]
				for l in ar2:
					if l == 1:
						tmp.append('+')
					else:
						tmp.append('-')
		
print(str(n[0]) + tmp[0] + str(n[1]) + tmp[1] + str(n[2]) + tmp[2] + str(n[3]) + '=7')

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

using namespace std;

typedef long int lint;
typedef long long int llint;

#define INF 1073741824
#define LINF 4611686018000000000
#define MOD 1000000007

int main() {
    int n, x, t;
    cin >> n >> x >> t;
    cout << (n / x + (n % x != 0)) * t << endl;
    return 0;
}


Measured memory_bytes: 3636
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

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

//    Scanner cin = new Scanner(new FileReader("input.txt"));
    Scanner cin = new Scanner(System.in);

    int n = cin.nextInt();
    int m = cin.nextInt();
    int[] kinds = new int[m];

    for (int i=0;i<n;i++) {

      int k = cin.nextInt();
      for (int j=0;j<k;j++) {
        int in = cin.nextInt();
        kinds[in-1]+=1;
      }

    }
    int count = 0;
    for (int i: kinds) {
      if (i==n)
        count+=1;
    }
    System.out.println(count);
  }

}

Measured memory_bytes: 23892
n,k=map(int,input().split())
a=[]
b=[]
for _ in range(n):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
#binary search for answer
lo=1
hi=max(a)
while lo<hi:
    md=(lo+hi)//2
    def chk(md):
        cnt=0
        for i in range(n):
            if a[i]<=md:
                cnt+=b[i]
        return cnt
    if chk(md)>=k:
        hi=md
    else:
        lo=md+1
print(lo)


Measured memory_bytes: 11064
#include <cstdio>
#include <queue>

const int N=2e5+5,M=4e5+5;
int n,m,tot,lnk[N],ter[M],nxt[M],deg[N][2];
char col[N];
bool vis[N];

void add(int u,int v) {
	ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot;
}
bool check() {
	for(int i=1;i<=n;++i) if(!vis[i]) return 0;
	return 1;
}
int main() {
	scanf("%d%d%s",&n,&m,col+1);
	while(m--) {
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
		++deg[u][col[v]=='B'];
		++deg[v][col[u]=='B'];
	}
	std::queue<int> q;
	for(int i=1;i<=n;++i) {
		if(!deg[i][0]||!deg[i][1]) q.push(i),vis[i]=1;
	}
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int i=lnk[u];i;i=nxt[i]) {
			int v=ter[i];
			if(vis[v]) continue;
			if(!--deg[v][col[u]=='B']) q.push(v),vis[v]=1;
		}

	}
	puts(check()?"No":"Yes");
	return 0;
}

Measured memory_bytes: 6400
fn get_input() -> String {
    let mut word = String::new();
    std::io::stdin().read_line(&mut word).unwrap();
    word.trim().to_owned()
}

fn main() {
    let line = get_input();
    let mut split = line.split_whitespace();
    let w:f64 = split.next().unwrap().parse().unwrap();
    let h:f64 = split.next().unwrap().parse().unwrap();
    let x:f64 = split.next().unwrap().parse().unwrap();
    let y:f64 = split.next().unwrap().parse().unwrap();

    println!("{:.10} {}", w * h / 2.0, if x + x == w && y + y == h { 1 } else { 0 });
}

Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void func(int n, int m, vector<int> vec)
{
	if(n == 0){
		cout << vec[0];
		for(int i = 1; i < vec.size(); i++){
			cout << " " << vec[i];
		}
		cout << endl;
		
		return ;
	}
	
	for(int i = min(n,m); i >= 1; i--){
		vec.push_back(i);
		func(n-i, i, vec);
		vec.erase(vec.end()-1);
	}
	
	return ;
}

int main()
{
	int n;
	
	while(cin>>n && n){
		vector<int> vec;
		func(n, n, vec);
	}
	
	return 0;
}

Measured memory_bytes: 912
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

class Factorial {
private:
	vector<lint> fac, inv, finv;

	void build(int N) {
		fac[0] = fac[1] = 1; inv[1] = 1; finv[0] = finv[1] = 1;

		for (int i = 2; i < N; i++) {
			fac[i] = fac[i - 1] * i % MOD;
			inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
			finv[i] = finv[i - 1] * inv[i] % MOD;
		}
	}

public:
	Factorial(int N = 200) : fac(N + 1), inv(N + 1), finv(N + 1) { build(N + 1); }

	lint operator() (int n, int k) {
		if (n < k || k < 0) return 0LL;
		return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
	}

	lint Pmod(int n, int k) {
		if (n < k || k < 0) return 0LL;
		return fac[n] * finv[n - k] % MOD;
	}
};

template<class T>
vector<T> make_vec(size_t s, T val) { return vector<T>(s, val); }
template<class... Size>
auto make_vec(size_t s, Size... tail) {
	return vector<decltype(make_vec(tail...))>(s, make_vec(tail...));
}

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	string N;
	cin >> N;
	lint len = N.size();

	int K;
	cin >> K;

	auto dp = make_vec(len + 1, 4, 2, 0LL);
	dp[0][0][0] = 1;

	for (int i = 0; i < len; i++) {
		for (int j = 0; j <= 3; j++) {

			// j->j+1 1->1
			if(j != 3)dp[i + 1][j + 1][1] += dp[i][j][1] * 9;

			// j->j 1->1
			dp[i + 1][j][1] += dp[i][j][1];
			
			if (N[i] != '0') {
				if (j != 3)dp[i + 1][j + 1][1] += dp[i][j][0] * (N[i] - '0' - 1);
				if (j != 3)dp[i + 1][j + 1][0] += dp[i][j][0];
				dp[i + 1][j][1] += dp[i][j][0];
			}
			else dp[i + 1][j][0] += dp[i][j][0];

		}
	}

	cout << (dp[len][K][0] + dp[len][K][1]) << "\n";

	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF ((1<<30)-1)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()


int n;
int v[1<<18];
int w[1<<18];

vector<pair<int, int64_t>> memo[1024];

vector<pair<int, int64_t>> f(const vector<int> &idxs) {
	vector<pair<int, int64_t>> vec, ret;
	rep(i, 1<<idxs.size()) {
		int64_t a = 0;
		int b = 0;

		rep(j, idxs.size()) {
			if ((i >> j & 1) == 0)continue;
			a += v[idxs[j]];
			b += w[idxs[j]];
			if (100000 < b)break;
		}
		vec.emplace_back(b, a);
	}
	sort(all(vec));

	int prev = -1;
	int64_t ma = 0;
	for (auto p : vec) {
		ma = max(ma, p.second);
		if (prev == p.first) {
			ret.pop_back();
		}
		ret.push_back(make_pair(p.first, ma));
		prev = p.first;
	}
	return ret;
}


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


	cin >> n;
	rep(i, n)cin >> v[i] >> w[i];

	int X = 1023;
	rep(i, min(X, n)) {
		vector<int> idxs;
		int j = i;
		while (0 < j) {
			idxs.push_back(j);
			j = (j - 1) / 2;
		}
		idxs.push_back(j);
		memo[i] = f(idxs);
	}

	int q;
	cin >> q;
	rep(_, q) {
		int u, c;
		cin >> u >> c;
		u--;

		vector<int> idxs;
		int j = u;
		while (X <= j) {
			idxs.push_back(j);
			j = (j - 1) / 2;
		}
		
		int64_t ans = 0;
		auto vec = f(idxs);

		int k = vec.size() - 1;

		for(auto p : memo[j]) {
			if (p.first > c)break;
			while (p.first + vec[k].first > c) {
				k--;
			}
			ans = max(ans, p.second + vec[k].second);
		}
		cout << ans << endl;
	}


	return 0;
}


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

int main(void){
    string s;cin>>s;
    int n = s.size();
    vv dbl(20, vi (n));
    
    rep(i,n){
        if(s[i]=='L')
            dbl[0][i]=i-1;
        else
            dbl[0][i]=i+1;
    }
    
    rep(j,19){
        rep(i,n){
            dbl[j+1][i] = dbl[j][dbl[j][i]];
        }
    }
    
    vi seat(n, 0);
    rep(i,n){
        seat[dbl[19][i]]++;
    }
    rep(i,n){
        printf("%d%c", seat[i], i==n-1?'\n':' ');
    }
    
    return 0;
}

Measured memory_bytes: 11728
export class Main {
  static main(input: string): string {
    const tmp: string[] = input.split("\n");
    const [a]: string[] = tmp.shift().split(" ");
    return `${a.toUpperCase() == a ? "A" : "a"}`;
  }
}
console.log(Main.main(require("fs").readFileSync("/dev/stdin", "utf8")));


Measured memory_bytes: 29668
import math
import itertools
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
color = [0]*3
ans = 1
for i in range(N):
  if A[i] not in color:
    ans = 0
    break
  ind = color.index(A[i])
  ans *= len([c for c in color if c == A[i]])
  ans %= mod
  color[ind] += 1

#ans = rec(color,0)
print(ans)

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

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

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

int N;
int Q;
LL A[114514];
LL imos[2][114514];
LL rimos[114514];

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

  cin >> N >> Q;
  rep(i, N) {
    cin >> A[i];
  }

  imos[0][0] = imos[0][1] = A[0];
  imos[1][0] = 0;
  imos[1][1] = A[1];

  reps(i, 2, N) {
    rep(j, 2) {
      imos[j][i] = imos[j][i-1];
    }
    imos[i%2][i] += A[i];
  }

  rrep(i, N) {
    rimos[i] = rimos[i+1] + A[i];
  }

  rep(i, Q) {
    LL X;
    cin >> X;

    if (A[N-2] <= X) {
      //cout << "here\n";
      cout << imos[1-N%2][N-1] << "\n";
      continue;
    }

    LL low = -1;
    LL high = int(1e9)+1;
    while (high - low > 1) {
      LL mid = (high+low)/2;
      int r = upper_bound(A, A+N, X+mid) - A;
      int l = lower_bound(A, A+N, X-mid) - A;
      if (r-l <= N-r) low = mid;
      else high = mid;
    }

    LL low2 = -1;
    LL high2 = int(1e9)+1;
    while (high2 - low2 > 1) {
      LL mid = (high2+low2)/2;
      int r = lower_bound(A, A+N, X+mid) - A;
      int l = lower_bound(A, A+N, X-mid) - A;
      if (r-l <= N-r) low2 = mid;
      else high2 = mid;
    }

    if (low < low2) {
      int r = lower_bound(A, A+N, X+low2) - A;
      int l = lower_bound(A, A+N, X-low2) - A;
      LL ans = rimos[r];
      //assert(r-l == N-r);
      //if (l >= 1) {
      //  ans += imos[(l-1)%2][l-1];
      //}
      if (r-l < N-r) {
        assert(r-l+1 == N-r);
        if (l >= 2) {
          ans += imos[(l-2)%2][l-2];
        }
      } else {
        assert(r-l == N-r);
        if (l >= 1) {
          ans += imos[(l-1)%2][l-1];
        }
      }
      cout << ans << "\n";
    } else {
      int r = upper_bound(A, A+N, X+low) - A;
      int l = lower_bound(A, A+N, X-low) - A;
      LL ans = rimos[r];
      if (r-l < N-r) {
        assert(r-l+1 == N-r);
        if (l >= 2) {
          ans += imos[(l-2)%2][l-2];
        }
      } else {
        assert(r-l == N-r);
        if (l >= 1) {
          ans += imos[(l-1)%2][l-1];
        }
      }
      cout << ans << "\n";
    }
  }
}


Measured memory_bytes: 4864
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
     string s;
     cin>>s;
     if(n%2==1)
     {
            cout<<"No"<<endl;
            return 0;
     }
     int j=n/2;
     int check=0;
     for(int i=0;i<n/2;i++)
     {
         if(s[i]!=s[j])
         {
             check=1;
             break;
         }
         j++;



     }
     if(check==1)
        cout<<"No"<<endl;
     else
         cout<<"Yes"<<endl;




}


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

using namespace std;
using ll =long long;
using db = double;

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

#define che(a,string) cout<<"//"<<string <<"=="<<(a)<<"//" <<endl;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define leftunique(v) SORT(v);(v).erase(unique((v).begin(),(v).end()),(v).end())
//leftuniqueは配列から同じ要素のものを取り除く 例 4 6 2 1 3 4 1 2 なら 1 2 3 4 6 になる
bool IsInt(double a){int b = a/1;if(a==b){return true;}else {return false;}}
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}
const int mod = 1e9 + 7;

const ll INF = 1LL << 60;

int n; 
ll h[100010];

ll dp[100010];

ll ans;
//ここから書き始める
int main()
{
	cout << setprecision(10);
	int n ; cin >> n;
	vector<ll> h(n);
	rep(i,n) cin >> h[i];

	rep(i,100010) dp[i] = INF;
	dp[0] = 0;

	for(int i = 1 ;i < n ; i ++ ){
		chmin(dp[i],dp[i-1]+abs(h[i] - h[i-1]));
		if(i>1){
			chmin(dp[i],dp[i-2]+abs(h[i] - h[i-2]));
		}
	}
	cout << dp[n-1] << endl;

}


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


int main() {
string s;
cin>>s;
long n=s.size();
int N;
cin>>N;
int rev=-1;
string tp="",btm="";
for(int i=0;i<N;i++){
  int t;
  cin>>t;
  if(t==1){
    rev*=-1;
  }
  if(t==2){
    int f;
    char c;
    cin>>f>>c;
    if(rev==-1){
      if(f==1){
        //s= c+s;
        tp= c+tp;
      }
      if(f==2){
        //s+=c;
        btm+=c;
      }
    }
    if(rev==1){
      if(f==2){
        //s= c+s;
        tp= c+tp;
      }
      if(f==1){
        //s+=c;
        btm+=c;
      }
    }
  }
}

s = tp+s+btm;
if(rev==1){
  reverse(s.begin(),s.end());
}

cout<<s<<endl;
}


Measured memory_bytes: 1360
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
using namespace std;
int inf = 1000000000;

int main(void) {

  int n;
  while(cin >> n){
    cout << 1 + n*(n+1)/2 << endl;
  }

  return 0;
}

// EOF

Measured memory_bytes: 3048
#include <stdio.h>

typedef struct _node{
    int parent;
    int l,r;
}NODE;

void preorder(NODE node[],int id){
    printf(" %d",id);
    
    if(node[id].l!=-1)preorder(node,node[id].l);
    if(node[id].r!=-1)preorder(node,node[id].r);
    
    return;
}
void inorder(NODE node[],int id){
    if(node[id].l!=-1)inorder(node,node[id].l);
    printf(" %d",id);
    if(node[id].r!=-1)inorder(node,node[id].r);
    
    return;
}
void postorder(NODE node[],int id){
    if(node[id].l!=-1)postorder(node,node[id].l);
    if(node[id].r!=-1)postorder(node,node[id].r);
    
    printf(" %d",id);
    
    return;        
}

int main(void){
    int i;
    
    int n;
    scanf("%d\n",&n);
    
    NODE node[n];
    for(i=0;i<n;i++){
        node[i].parent=-1;
        node[i].l=-1;
        node[i].r=-1;
    }
    
    int id,l,r;
    for(i=0;i<n;i++){
        scanf("%d %d %d\n",&id,&l,&r);
        node[id].l=l;
        node[id].r=r;
        if(l!=-1)node[l].parent=id;
        if(r!=-1)node[r].parent=id;
    }
    
    int root;
    for(root=0;root<n;root++)if(node[root].parent==-1)break;

    printf("Preorder\n");
    preorder(node,root);
    printf("\nInorder\n");
    inorder(node,root);
    printf("\nPostorder\n");
    postorder(node,root);
    printf("\n");

    return 0;
}



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

using namespace std;

int main()
{
    string s;
    cin >> s;
    if(s == "Sunny") cout << "Cloudy";
    if(s == "Cloudy") cout << "Rainy";
    if(s == "Rainy") cout << "Sunny";
    return 0;
}


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

int main() {
  long long X;
  cin >> X;
long long A;
A = 100;
  
 for(int i = 0;; i++) {
A = A*1.01;
  if (A >= X){
 int N;
 N= i + 1;
 cout << N << endl;
    break; 
  } 
 }
 
 }


Measured memory_bytes: 3576
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<i64>();
    let mut sq_n = 0;
    for i in 1..n {
        if i * i > n {
            sq_n = i;
            break;
        }
    }
    if n == 2 {
        println!("1");
        return;
    }
    let primes = get_primes(sq_n as usize);
    let fact_dict = factorize(n, &primes);
    let factors = collect_all_factors(&fact_dict);
    let mut ans_pair = (1, n);
    for num in factors {
        if (ans_pair.0 - 1) + (ans_pair.1 - 1) > (num - 1) + (n / num - 1) {
            ans_pair = (num, n / num);
        }
    }
    println!("{}", (ans_pair.0 - 1) + (ans_pair.1 - 1));
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn get_primes(n: usize) -> Vec<i64> {
    let mut is_prime = vec![true; n + 1];
    let mut primes = Vec::new();
    is_prime[0] = false;
    is_prime[1] = false;

    for i in 2..n + 1 {
        if is_prime[i] {
            primes.push(i as i64);
            let mut j = 2 * i;
            while j < n {
                is_prime[j] = false;
                j += i;
            }
        }
    }
    primes
}

fn factorize(mut num: i64, primes: &Vec<i64>) -> std::collections::HashMap<i64, i64> {
    // max_primes >= (num)^(1/2)
    let mut dict = std::collections::HashMap::new();
    for &p in primes.iter() {
        while num % p == 0 {
            *dict.entry(p).or_insert(0) += 1;
            num /= p;
        }
        if num == 1 {
            break;
        }
    }
    if num != 1 {
        dict.insert(num, 1);
    }
    dict
}

fn pow(n: i64, mut p: i64) -> i64 {
    let mut r = n;
    let mut ret = 1;
    while p > 0 {
        if p % 2 == 0 {
            r = r * r;
            p /= 2;
        } else {
            ret = ret * r;
            p -= 1;
        }
    }
    ret
}

fn collect_all_factors(dict: &std::collections::HashMap<i64, i64>) -> Vec<i64> {
    let mut ret = vec![1];
    for &key in dict.keys() {
        let mut new = ret.clone();

        for coef in 1..dict[&key] + 1 {
            let coef_1 = pow(key, coef);
            for &num in ret.iter() {
                new.push(num * coef_1);
            }
        }
        ret = new;
    }
    ret
}


Measured memory_bytes: 6396