akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <set>

using namespace std;
typedef long long ll;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct Point {
  int x;
  int y;
  char type;
  Point() {;}
  Point(double x, double y, int type) : x(x), y(y), type(type) {;}
  bool operator<(const Point &rhs) const {
    if (y != rhs.y) { return y < rhs.y; }
    return x < rhs.x;
  }
};

struct Event {
  int x;
  Point p;
  char in;
  Event() {;}
  Event(int x, Point p, int in) : x(x), p(p), in(in) {;}
  bool operator<(const Event &rhs) const {
    if (x != rhs.x) { return x < rhs.x; }
    return in > rhs.in;
  }
};

inline int square(int x) { return x * x; }

inline int dist2(const Point &a, const Point &b) {
  return square(a.x - b.x) + square(a.y - b.y);
}

int an, bn, n;
int r;
Event event[500000];

int PlaneSweep() {
  int ans = 0;
  int r4 = 4 * r;
  int r2 = 16 * r * r;
  set<Point> open[2];
  REP(iter, n) {
    Event &e = event[iter];
    Point &p = e.p;
    if (e.in) {
      set<Point>::iterator lower = open[(int)p.type ^ 1].lower_bound(Point(0, p.y - r4, 0));
      set<Point>::iterator upper = open[(int)p.type ^ 1].upper_bound(Point(1000000000, p.y + r4, 0));
      for (set<Point>::iterator it = lower; it != upper; it++) {
        if (dist2(*it, p) <= r2) { ans++; }
      }
      open[(int)p.type].insert(p);
    } else {
      open[(int)p.type].erase(open[(int)p.type].find(p));
    }
  }
  return ans;
}

int main() {
  while (scanf("%d %d %d", &an, &bn, &r), an|bn) {
    n = (an + bn) * 2;
    REP(i, an) {
      int x, y;
      scanf("%d %d", &x, &y);
      event[2 * i + 0] = Event(x - 2 * r, Point(x, y, 0), 1);
      event[2 * i + 1] = Event(x + 2 * r, Point(x, y, 0), 0);
    }
    REP(i, bn) {
      int x, y;
      scanf("%d %d", &x, &y);
      event[2 * an + 2 * i + 0] = Event(x - 2 * r, Point(x, y, 1), 1);
      event[2 * an + 2 * i + 1] = Event(x + 2 * r, Point(x, y, 1), 0);
    }
    sort(event, event + n);
    int ans = PlaneSweep();
    printf("%d\n", ans);
  }
}

Measured memory_bytes: 8752
#include<iostream>
#include<vector>
#include<string>
using namespace std;
using ll = long long;

void solve() {
	string s;
	cin >> s;
	int n = s.length();
	const ll mod = 1000000007;
	vector<vector<ll>>dp(n + 1, vector<ll>(13, 0));
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		if (s[i] == '?') {
			for (int j = 0; j < 10; j++) {
				for (int k = 0; k < 13; k++) {
					dp[i + 1][(k * 10 + j) % 13] += dp[i][k];
				}
			}
		} else {
			int c = s[i] - '0';
			for (int j = 0; j < 13; j++) {
				dp[i + 1][(j * 10 + c) % 13] += dp[i][j];
			}
		}
		for (int j = 0; j < 13; j++)dp[i + 1][j] %= mod;
	}
	cout << dp[n][5] << endl;
}

int main() {
	solve();
}

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

int main(){
  int x, a, b;
  cin >> x >> a >> b;

  int da, db;
  da = abs(x - a);
  db = abs(x - b);

  if(da > db) cout << "B" << endl;
  else cout << "A" << endl;  
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;

int main() {
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    bool flag = true;
    int count = 0;

    while (flag){
        for (int i = 0; i < n; ++i) {
            if(a[i] % 2 == 0){
                a[i] /= 2;
            }else{
                flag = false;
                break;
            }
        }
        if(flag)count++;
    }
    print(count);
}

Measured memory_bytes: 256
/*
srt: 2017年06月19日 22時00分00秒
   《将赴吴兴登乐游原》杜牧
清时有味是无能，闲爱孤云静爱僧。
欲把一麾江海去，乐游原上望昭陵。
end: 2017年06月20日 00時01分10秒
*/

#include<cstdio>

typedef long long ll;const int mod=1e9+7;
int dp[32768],to[15];

#define c __builtin_popcount

int main()
{
	int s,k,u,v,m,n;scanf("%d%d",&n,&m);
	while(m--)scanf("%d%d",&u,&v),to[--u]|=1<<--v;


	*dp=1,m=(1<<n)-1;
	for(s=m;s;s--)
		if(dp[m^s])
			for(k=s;k;k=(k-1)&s)
				if((k&3)!=3)
				{
					v=dp[m^s];
					for(u=0;u<n;u++)
						if((s^k)&1<<u)v=(ll)v*((1<<c(k&to[u]))-1)%mod;
						else if(!(s&1<<u))v=(ll)v*(1<<c(k&to[u]))%mod;
					(dp[m^s^k]+=v)>=mod&&(dp[m^s^k]-=mod);
				}


	printf("%d\n",dp[m]);
}

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

int main(void) {
	int num, kind, temp;
	cin >> num >> kind;
	vector<int> vec(num);
	vector<int> ball;

	for (int i = 0; i < num; i++) {
		cin >> temp;
		vec.at(temp-1)++;
	}
	for (int i = 0; i < num; i++) {
		if (vec.at(i) > 0) ball.push_back(vec.at(i));
	}
	if (ball.size() <= kind) cout << 0 << endl;
	else {
		sort(ball.begin(), ball.end());
		int change = 0;
		for (int i = 0; i < ball.size(); i++) {
			change += ball.at(i);
			if ((ball.size() - i - 1) <= kind) break;
		}
		cout << change << endl;
	}
	return 0;
}


Measured memory_bytes: 2168
#include <stdio.h>

int		main(void)
{
	int N;
	int M;
	int i = 0;
	int A[10000];
	int sum = 0;

	scanf("%d%d", &N, &M);
	while (i < M)
	{
		scanf("%d", &A[i]);
		sum = sum + A[i];
		i++;
	}
	if (sum > N)
		printf("-1\n");
	else
		printf("%d\n", N - sum);
	return (0);
}


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

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

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

  int n, k;
  cin >> n >> k;
  VI a(n);
  REP(i, n) cin >> a[i];

  int idx = -1;
  REP(i, n) if(a[i] == 1) idx = i;

  int ret = LLINF;
  REP(i, k) {
    int l = idx - i + 1, r = n - idx + i;
    chmin(ret, ceil(l-1,k-1) + ceil(r-1, k-1));
  }

  cout << ret << endl;

  return 0;
}


Measured memory_bytes: 1024
# 2 "2298.cpp"
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <complex>
#include <functional>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>


namespace solution {
   using namespace std;

   typedef istringstream ISS;
   typedef ostringstream OSS;
   typedef vector<string> VS;
   typedef long long LL;
   typedef int INT;
   typedef vector<INT> VI;
   typedef vector<VI> VVI;
   typedef pair<INT, INT> II;

   const int SIZE = 201;
   const int MAX_LENGTH = 10001;
   const int NONE = -1.0;
   const double EPS = 1e-9;
   int N;
   int K;
   int T;
   int U;
   int V;
   int L;
   bool D[MAX_LENGTH];

   typedef pair <II, int> State;
   typedef pair <double, State> Node;
   typedef queue <Node> Queue;
   Queue Q;

   void dijkstra_init() {
      Q = Queue();
   }


   bool lessthan_equal( double a, double b ) {
      if ( fabs( a - b ) < EPS ) return true;
      return a < b;
   }

   double dijkstra( int start, int goal ) {
      dijkstra_init();

      Node start_node( 0.0, State( II( start, 0 ), 0 ) );
      Q.push( start_node );

      double base = 1.0 / U;
      double fast = 1.0 / V;

      while ( ! Q.empty() ) {
         Node node = Q.front();
         Q.pop();

         double cost = node.first;
         int id = node.second.first.first;
         int remains = node.second.first.second;
         int carrots = node.second.second;

         if ( id == goal ) {
            return cost;
         }


         if ( D[id] ) {
            if ( carrots == K ) {
               remains = T * V;
            } else {
               carrots ++;
               if ( remains == 0 ) {
                  remains = T * V;
                  carrots --;
               }
            }
         }

         double t = base;
         if ( remains ) {
            t = min( t, fast );
            remains --;
         }
         if ( remains == 0 && carrots ) {
            remains = T * V;
            carrots --;
         }
         Q.push( Node( cost + t, State( II( id + 1, remains ), carrots ) ) );
      }
      return NONE;
   }

   class Solution {
   private:
      void init() {
         for ( int i = 0; i < MAX_LENGTH; ++ i ) {
            D[i] = false;
         }
      }

      bool input() {
         if ( ! ( cin >> N >> K >> T >> U >> V >> L ) ) return false;
         for ( int i = 0; i < N; ++ i ) {
            int d;
            cin >> d;
            D[d] = true;
         }
         return true;
      }

      double solve() {
         return dijkstra( 0, L );
      }

   public:
      int run() {
         while ( init(), input() ) {
            printf( "%.9f\n", solve() );
         }
         return 0;
      }
   };
}

int main() {
   using namespace solution;
   Solution s;
   return s.run();
}

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

int main(){
  int N;
  cin >> N;
  vector<int> vec(N - 1);
  for(int i = 0;i < N - 1; i++){
    cin >> vec.at(i);
  }
  
  vector<int> count(N + 1);
  for(int i = 0; i < N-1; i++){
        count.at(vec.at(i))++;
  }
  
  for(int i = 1; i <= N; i++){
    cout << count.at(i) << endl;
  }
    
}


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

using namespace std;

#define ll long long int
#define ld long double
#define pii pair<int,int>
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define bit(a,b) ((a>>b)&1)
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const ll mx = 2e5+2, Mx = 12, Mod = 1e9+7;

int n, p[Mx], c[Mx];
int dp[Mx][mx];

int main()
{
    int g;
    cin >> n >> g; g/=100;
    for(int i=1;i<=n;i++)
        cin >> p[i] >> c[i], c[i]/=100;
    for(int i=0;i<Mx;i++)
        for(int j=0;j<mx;j++)
            dp[i][j] = Mod;
    dp[0][0] = 0;
    for(int i=1;i<=n;i++)
    {
        dp[i][0] = 0;
        for(int j=1;j<=g;j++)
        {
            for(int k=0;k<p[i];k++)
                dp[i][j] = min(dp[i][j], k + dp[i-1][max(j-k*i, 0)]);
            dp[i][j] = min(dp[i][j], p[i] + dp[i-1][max(0, j-p[i]*i-c[i])]);
        }
    }
    cout << dp[n][g] << '\n';
    return 0;
}












Measured memory_bytes: 9600
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <math.h>
#include <time.h>
#include <assert.h>

using namespace std;

#define x first
#define y second
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define SZ(x) int(x.size())
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = b-1; i >= a; i--)
#define DBG(x) cerr << (#x) << "=" << x << "\n";
#define ll long long
#define inf 1000000007
#define mod 1000000007
#define N 1000005

template<typename U, typename V> void Min(U &a, const V & b){if(a > b)a = b;}
template<typename U, typename V> void Max(U &a, const V & b){if(a < b)a = b;}
template<typename U, typename V> void add(U &a, const V & b){a = (a + b) % mod;}
template<typename U> U gcd(U a, U b){
    if(a == 0)return b;
    if(b == 0)return a;
    if(a >= b)return gcd(a % b, b);
    else return gcd(a, b % a);
}
int pow(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)ans = 1LL * ans * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int pow(int a, ll b, int c){
    int ans = 1;
    while(b){
        if(b & 1)ans = 1LL * ans * a % c;
        a = 1LL * a * a % c;
        b >>= 1;
    }
    return ans;
}

char s[101][101];
int dp[101][101][2];
int dx[] = {0, 1}, dy[] = {1, 0};
int main(){
  int T, m, i, j, k, n, K;
  scanf("%d%d", &n, &m);
  rep(i, 0, n)scanf("%s", s[i]);
  memset(dp, 63, sizeof(dp));
  if(s[0][0] == '.')dp[0][0][0] = 0;
  else dp[0][0][1] = 1;
  rep(i, 0, n){
    rep(j, 0, m){
      rep(k, 0, 2)if(dp[i][j][k] < inf){
        int &w = dp[i][j][k];
        rep(l, 0, 2){
          int x = i + dx[l], y = j + dy[l];
          if(x == n || y == m)continue;
          if(s[x][y] == '#') {
            if(k)Min(dp[x][y][k], w);
            else Min(dp[x][y][1], w + 1);
          }
          else{
            Min(dp[x][y][0], w);
          }
        }
      }
    }
  }
  printf("%d\n", min(dp[n-1][m-1][0], dp[n-1][m-1][1]));
}


Measured memory_bytes: 384
n = int(input())
a = list(map(int, input().split()))
rates = [0] * 8
cnt = 0

for i in range(n):
  if a[i] < 3200:
    rates[a[i] // 400] += 1
  else:
    cnt += 1
    
cn = len(rates) - rates.count(0) #color number
if sum(rates) == 0:
  cmin = 1
else:
  cmin = cn #color min

if all([x < 3200 for x in a]):
  cmax = cn #color max
else:
  cmax = cn + cnt
  
print(cmin,cmax)

Measured memory_bytes: 9136
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        Integer[] a = new Integer[n];
        Arrays.setAll(a, i -> Integer.parseInt(sc.next()));
        sc.close();

        // 主処理
        int result = 0;
        for (int i = 0; i < n; i += 2) {
            if (a[i] % 2 == 1) {
                result++;
            }
        }

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 35648
#include<iostream>
using namespace std;
int main(){
    long long int x,y,u;
    cin>>x>>y;
    u=x;
    int count=0;
    while(1){
        if(u>y)break;
        u*=2;
        count++;
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	string S;
	cin >> S;
	int N = S.length();
	vector<int> next_eq(N, N);
	for(int i = N-2; i >= 0; i--) {
		if(S[i] == S[i+1]) next_eq[i] = i+1;
		else next_eq[i] = next_eq[i+1];
	}
	vector<int> dif(N+1, 0);
	for(int i = 0; i < N; i++) {
		if(S[i] == 'a') dif[i+1] = (dif[i]+1) % 3;
		else dif[i+1] = (dif[i]+2) % 3;
	}
	vector<int> dif_occ[3];
	for(int i = 0; i <= N; i++) dif_occ[dif[i]].push_back(i);
	cat mod = 1000000007;
	vector<cat> dp(N+1, 0);
	dp[0] = 1;
	for(int i = 0; i < N; i++) {
		dp[i+1] += dp[i];
		if(dp[i+1] >= mod) dp[i+1] -= mod;
		if(next_eq[i] == N) continue;
		int d = (S[i] == 'a') ? (dif[i]+2)%3 : (dif[i]+1)%3;
		auto it = lower_bound(begin(dif_occ[d]), end(dif_occ[d]), next_eq[i]+1);
		if(it == end(dif_occ[d])) continue;
		dp[*it] += dp[i];
		if(dp[*it] >= mod) dp[*it] -= mod;
	}
	cat ans = dp[N];
	for(int i = 0; i < N; i++) if(next_eq[i] < N) {
		if(next_eq[i+1] == N) {
			auto it = lower_bound(begin(dif_occ[dif[i+1]]), end(dif_occ[dif[i+1]]), i+1);
			ans = (ans + dp[i] * (end(dif_occ[dif[i+1]])-1-it)) % mod;
		}
		int d = (S[i] == 'a') ? (dif[i]+2)%3 : (dif[i]+1)%3;
		auto it = lower_bound(begin(dif_occ[d]), end(dif_occ[d]), next_eq[i]+1);
		if(it == end(dif_occ[d])) continue;
		if(next_eq[*it] < N) continue;
		ans = (ans + dp[i] * (end(dif_occ[d])-1-it)) % mod;
	}
	for(int i = 1; i < N; i++) if(next_eq[i] < N && dif[i] == dif[N]) {
		ans += dp[i];
		if(ans >= mod) ans -= mod;
	}
	cout << ans << "\n";
	return 0;
}

// look at my code
// my code is amazing


Measured memory_bytes: 2632
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vii;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip> vip;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 :1e9;
int main(){
	int n,a,b;
	while(cin>>n>>a>>b,n){
		vi in(n);
		rep(i,n)cin>>in[i];
		int ma=-1,mai;
		loop(i,a-1,b){
			int s=in[i]-in[i+1];
			if(s>=ma){
				ma=s;
				mai=i;
			}
		}
		cout<<mai+1<<endl;
	}
}


Measured memory_bytes: 3084
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nに直した
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nに直した

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt
#------Union-Findおわり-------------#

import collections

N = int(input())
XYs = [tuple(mi()) for _ in range(N)]

if N==1:
  print(1)
  exit()
if N==2:
  print(1)
  exit()

sa_list = []
cmb_with_same_diff = collections.defaultdict(list)
import itertools
diffidx = 0
for a in range(0, N):
  for b in range(0, N):
    if a>=b: continue
    #ここでa, bは各ボールのidx
    ax, ay = XYs[a]
    bx, by = XYs[b]
    if ax-bx==0: nowsa = (ax-bx,abs(ay-by))
    elif ay-by==0: nowsa = (abs(ax-bx), ay-by)
    elif ax-bx>0: nowsa = (ax-bx,ay-by)
    else: nowsa = (-(ax-bx),-(ay-by))
    sa_list.append(nowsa)
    cmb_with_same_diff[nowsa].append((a, b))


ans = N
for each_samesa_list in cmb_with_same_diff.values():
  UF = UnionFind(N) #ノード数はボールの数
#  print(each_samesa_list, 'における処理前の木の数は', UF.Count_Trees())
  for a, b in each_samesa_list:
    UF.Unite(a, b)
#  print(each_samesa_list, 'における処理後の木の数は', UF.Count_Trees())
  ans = min(ans, UF.Count_Trees())

print(ans)



Measured memory_bytes: 42864
def Main(a, b, c):
    x = c-a-b
    if x > 0:
        if x*x > 4*a*b:
            return "Yes"
    return "No"

def main():
    a, b, c = map(int, input().split())
    print(Main(a, b, c))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

class SegmentTree:
    def __init__(self, N, func, I):
        self.func = func
        self.I = I
        self.sz = 2**(N-1).bit_length()
        self.seg = [I] * (self.sz * 2)
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = list(map(int,read().split()))
    seg = SegmentTree(N , gcd , 0)
    for i,n in enumerate(L):
        seg.assign(i , n)
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()


Measured memory_bytes: 55440
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

struct Point{
    ll x;
    ll y;
    ll id;
    Point(ll x, ll y, ll id): x(x), y(y), id(id) {}

    static bool sortByX(Point a, Point b){
        if(a.x == b.x){
            return a.y < a.y;
        }else{
            return a.x < b.x;
        }
    }

    static bool sortByY(Point a, Point b){
        if(a.y == b.y){
            return a.x < a.x;
        }else{
            return a.y < b.y;
        }
    }
};

struct Edge{
    ll from;
    ll to;
    ll cost;

    static bool sortByCost(Edge a, Edge b){
        return a.cost < b.cost;
    }
};

const int N_MAX = 100010;
int parent[N_MAX] = {};
vector<Point> P;
vector<Edge> edgeList;

ll findRoot(ll x){
    if(parent[x] == x){
        return x;
    }else{
        auto root = findRoot(parent[x]);
        parent[x] = root; // path compression
        return root;
    }
}

void _union(ll a, ll b){
    auto rootA = findRoot(a);
    auto rootB = findRoot(b);
 
    if(rootA == rootB){
        return;
    }else{
        parent[a] = b;
    }
}

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

    // input
    ll N;
    cin >> N;

    P.reserve(N);

    FOR(i, 0, N){
        ll x, y;
        cin >> x >> y;
        Point p = Point(x, y, i);
        P.push_back(p);
    }

    sort(ALL(P), Point::sortByX);
    FOR(i, 0, N-1){
        Edge edge;
        edge.from = P[i].id;
        edge.to = P[i+1].id;
        edge.cost = min(abs(P[i].x - P[i+1].x), abs(P[i].y - P[i+1].y));
        edgeList.push_back(edge);
    }

    sort(ALL(P), Point::sortByY);
    FOR(i, 0, N-1){
        Edge edge;
        edge.from = P[i].id;
        edge.to = P[i+1].id;
        edge.cost = min(abs(P[i].x - P[i+1].x), abs(P[i].y - P[i+1].y));
        edgeList.push_back(edge);
    }

    sort(ALL(edgeList), Edge::sortByCost);

    // make MST by kruskal
    FOR(i, 0, N_MAX){
        parent[i] = i;
    }

    ll cost_sum = 0;

    // 短いエッジから見ていって必要なら連結
    for(auto edge : edgeList){

        if(findRoot(edge.from) == findRoot(edge.to)){
            // skip
        }
        else{
            // つなぐ
            _union(findRoot(edge.from), findRoot(edge.to));
            cost_sum += edge.cost;
        }
    }

    p(cost_sum);
    
    return 0;
}

Measured memory_bytes: 10736
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int maxRow = 3;
        int maxCol = 3;
        Map<Integer, Integer> locationMap = new HashMap<>();
        boolean[][] grid = new boolean[maxRow][maxCol];

        for(int i = 0; i < maxRow; i++) {
            for(int j = 0; j < maxCol; j++) {
                locationMap.put(sc.nextInt(), i * maxCol + j);
            }
        }

        int n = sc.nextInt();
        while(n-- > 0) {
            int b = sc.nextInt();
            if(!locationMap.containsKey(b)) continue;

            int loc = locationMap.get(b);
            int row = loc / maxCol;
            int col = loc % maxCol;
            grid[row][col] = true;
        }

        for(int i = 0; i < maxRow; i++) {
            if(grid[i][0] && grid[i][1] && grid[i][2]) {
                System.out.println("Yes");
                return;
            }
            if(grid[0][i] && grid[1][i] && grid[2][i]) {
                System.out.println("Yes");
                return;
            }
        }
        if(grid[0][0] && grid[1][1] && grid[2][2] || 
            grid[2][0] && grid[1][1] && grid[0][2]
        ) {
            System.out.println("Yes");
                return;
        }
        System.out.println("No");
    }
}


Measured memory_bytes: 21972
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i): is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
## libs ##
from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    n, m, x = MII()
    query = [MII() for _ in range(n)]
    mincost = 10**7
    for bit in range(1<<n):
        vals = [0]*m
        cost = 0
        for i in range(n):
            if bit&(1<<i):
                cost += query[i][0]
                for i, c in enumerate(query[i][1:]):
                    vals[i] += c
                x_g = [1 for v in vals if v >= x]
                if sum(x_g) == m:
                    mincost = min(cost, mincost)
    if mincost == 10**7:
        print(-1)
    else:
        print(mincost)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9520
#include<bits/stdc++.h>
using namespace std;
int main()
{
 long long int x;
 cin>>x;
 double p=0.01;
 long long int a=100;
 int cnt=0;
 while(a<x)
 {
 	a+=a/100;
 	cnt++;
 }
 cout<<cnt<<endl;
 return 0;
}


Measured memory_bytes: 3536
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
using ll = long long;
constexpr long long INF = 1LL << 62;
constexpr int MOD = 1e9 + 7;
constexpr double EPS = 1e-10;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int n,s; cin >> n >> s;
    vector<int> a(n);
    REP(i,n) cin >> a[i];

    int l = 0, r = 0, sum = 0, ans = 101010;
    while(true) {
        while(sum < s && r < n) sum += a[r++];
        if(sum < s) break;
        ans = min(ans, r - l);
        sum -= a[l++];
    }
    if(ans == 101010) ans = 0;
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3364
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
int main() {
    int N;
    string S;
    cin >> N >> S;
    int m = INT_MIN;
    for (int i = 0; i < N - 1; ++i) {
        set<char> l,r;
        for (int j = 0; j <=i ; ++j) {
            l.insert(S[j]);
        }
        for (int k = i+1; k < S.length() ; ++k) {
            r.insert(S[k]);
        }
        int cnt = 0;
        for (auto it = l.begin(); it != l.end(); it++) {
            if(r.find(*it) != r.end()) {
                cnt++;
            }
        }
        m = max(m, cnt);
    }
    cout << m << endl;


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used: %.6lf(s)\n", ((double)TIME_END - TIME_START) / CLOCKS_PER_SEC);
    system("pause");
#endif
}
string s, t;

void solve()
{
    cin>> s >> t;
    int ans = 0;
    for (int i = 0; i < s.length();++i)
    {
        if(s[i]!=t[i])
            ans++;
    }
    printf("%d\n", ans);
}

int main()
{
    TIME_START = clock();
    int Test = 1;
    // cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

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

#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)

#define gcd3(x,y,z)                __gcd(__gcd(x,y),z)
#define INF                     LLONG_MAX
#define inf                     LONG_MAX
#define PI                      (2.0*acos(0.0))
#define Log(b,x)                (log(x)/log(b))
#define Unique(x)               sort(all(x)); x.erase(unique(all(x)), x.end());
#define inttostring(x)          to_string(x)
#define stringtoint(x)          stoll(x)
#define valid(nx,ny,row,col)    nx>=0 && nx<row && ny>=0 && ny<col
#define CLR(x,y)                memset(x,y,sizeof(x));
#define max3(x,y,z)             max(z,max(x,y));
#define min3(x,y,z)             min(z,min(x,y));
#define MP(x, y) make_pair(x, y)
#define SZ(c) (int)c.size()
#define pb(x) push_back(x)
#define all(x)                  (x).begin(), (x).end()
#define sz(c)               int(c.size())
#define clr(x, y)           memset(x, y, sizeof(x))
#define ff first
#define ss                  second
#define sf                  scanf
#define si(x)               scanf("%d", &x)
#define sii(x, y)           scanf("%d %d", &x, &y)
#define siii(x, y, z)       scanf("%d %d %d", &x, &y, &z)
#define sl(x)               scanf("%lld", &x)
#define sll(x, y)           scanf("%lld %lld", &x, &y)
#define slll(x, y, z)       scanf("%lld %lld %lld", &x, &y, &z)
#define pf                  printf
#define pi(x)               printf("%d\n", x)
#define pii(x, y)           printf("%d %d\n", x, y)
#define piii(x, y, z)       printf("%d %d %d\n", x, y, z)
#define pl(x)               printf("%lld\n", x)
#define pll(x, y)           printf("%lld %lld\n", x, y)
#define plll(x, y, z)       printf("%lld %lld %lld\n", x, y, z)
#define Pii pair< int, int >
#define psi pair< string, int >
#define case(n) printf("Case %d: ",n);
#define eps 1e-15
#define mod 100000007
#define MAX 100000010
priority_queue<Pii, vector<Pii>, greater<Pii> > q;

int res=-999999999,n;
int a[500],b[500];
void call(int po,int x1,int x2)
{
    res=max(x1-x2,res);
    if(po>=n)
        return;
    call(po+1,x1,x2);
    call(po+1,x1+a[po],x2+b[po]);
}

int main()
{
    //READ("input.txt");
   // WRITE("output.txt");

    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
     for(int i=0;i<n;i++)
        cin>>b[i];
    call(0,0,0);
    cout<<res<<endl;
}




Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	private void solve() {
		Scanner in = new Scanner(System.in);
		int r = in.nextInt();
		int D = in.nextInt();
		int X2000 = in.nextInt();
		int x = X2000;
		for(int i=2001;i<=2010;i++) {
			x = r * x - D;
			System.out.println(x);
		}
	}

	public static void main(String[] args) {
		new Main().solve();
	}
}

Measured memory_bytes: 21076
"""while True:
	try:
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
	except: break
	
	hit = blow = 0
	for i in range(4):
		if a[i] == b[i]:
			hit += 1
			b[i] = -1
	for i in range(4):
		if b[i] >= 0:
			if b[i] in a: blow += 1
	print(hit, blow)
"""
while True:
    try:
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
    except:
        break
    hit = blow = 0
    for i in range(4):
        if (a[i] == b[i]):
            hit += 1
            b[i] = -1
    for i in range(4):
        if b[i] >= 0:
            if b[i] in a:
                 blow += 1
    print(hit, blow)




Measured memory_bytes: 5612
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>

const int MAXN = 2e5 + 10, MAXS = 26;

int len;
int dp[MAXN], ch[MAXN][MAXS], nxt[MAXS];
char s[MAXN];

int main() {
	s[0] = 'a';
	scanf(" %s", s + 1), len = strlen(s + 1);
	for (int i = 0; i < MAXS; ++i) nxt[i] = len + 1;
	for (int i = len; ~i; --i) {
		int v = s[i] - 'a'; dp[i] = 23333333;
		std::copy(nxt, nxt + MAXS, ch[i]);
		for (int j = 0; j < MAXS; ++j) dp[i] = std::min(dp[i], dp[nxt[j]] + 1);
		nxt[v] = i;
	}
	int u = 0;
	for (; u <= len;) {
		for (int k = 0; k < MAXS; ++k) if (dp[u] == dp[ch[u][k]] + 1) { putchar(k + 'a'), u = ch[u][k]; break; }
	}
	puts("");
	return 0;
}

Measured memory_bytes: 21504
#include<bits/stdc++.h>
using namespace std;
void pre(){}
long long int p=1e9+7;
long long int mod = 1e9+7;
long long int power(long long int x,long long int y){  
    long long int res = 1;
    x = x % p;
    if (x == 0) return 0; 
    while (y > 0)  {  
        if (y & 1)  
            res = (res*x) % p;   
        y = y>>1; 
        x = (x*x) % p;  
    }  
    return res;  
}  
void solve(){
    long long int n,k;cin>>n>>k;
    long long int ans = 0;
    long long int arr[k+1];
    for(int i=1;i<=k;i++){
        arr[i]=power(k/i,n);
    }
    for(int i=k;i>=1;i--){
        for(int j=2;i*j<=k;j++){
            arr[i]=(arr[i]-arr[i*j]+mod)%mod;
        }
    }
    for(long long int i=1;i<=k;i++){
        ans+=(arr[i]*i)%mod;
        ans%=mod;
    }
    cout<<ans%mod<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pre();
    long long int num = 1;
    for(long long int i=0;i<num;i++){
       	solve();
    }   
}


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

int main()
{
    int n, x, y;
    cin >> n >> x >> y;
    --x;
    --y;
    vector<int> c(n - 1, 0);
    rep(i, n)
    {
        rep(j, n)
        {
            if (i == j)
                continue;
            // int idx = 1;
            int idx = min(
                abs(i - j),
                abs(x - i) + 1 + abs(y - j));
            idx = min(idx,
                      abs(y - i) + 1 + abs(x - j));
            --idx;
            ++c.at(idx);
        }
    }
    rep(i, n - 1)
    {
        printf("%d\n", c.at(i) / 2);
    }
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize("Ofast")
//*********************************************DO IT NOW****************************************************************
#include<bits/stdc++.h> 
#include<random>
#define int long long   
#define pp pair<int,int> 
#define ss second 
#define ff first 
#define pb push_back
#define mod 1000000007
#define pi 3.14159265359
#define mk(arr,n,type)  type *arr=new type[n];
#define sl s1.length();
#define yes cout<< "YES"<<endl
#define no  cout<< "NO"<<endl
#define all(v) (v).begin(),(v).end()
#define s(v)   sort(v,v+n)
#define  mt mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define read(a,n) for(int i=0;i<n;i++)cin>>a[i]
#define print(a,n) for(int i=0;i<n;i++)cout<<a[i]<<" "
using namespace std;
//**********************************************DO IT NOW***************************************************************
void fastio()
{  
  #ifndef ONLINE_JUDGE
  freopen("INPUT.txt","r",stdin);
  freopen("OUTPUT.txt","w",stdout); 
  #endif
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL) ; 
  cout.tie(NULL);
}
int dp[101][1001],ans1=1e9,dp1[1000001];
int num[10];
int a[1000000];
int prime(int n)
{
 for(int i=2;i*i<=n;i++)
      {
          if(n%i==0)
          return 0;
      }
      return 1;
}
signed main()
{   
    fastio();
    int t=1;
   // cin>>t;
    while(t--)
    {  
        int n;
        cin>>n;
        string s,ss;
        cin>>s>>ss;
        string s1="";
        int c=1;
        for(int i=0;i<n;i++)
        {
            if(c)
            {
                s1+=s[i];
                c=0;
            }
            if(c==0)
            {
                s1+=ss[i];
                c=1;
            }
        }
        cout<<s1;
    }
    
}
// 🍪 🍪 🍪


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

using namespace std;

#define ll long long

int h, w, k;
vector<string> grid;
vector<vector<int>> rows;
vector<vector<int>> cols;
vector<int> nums;

void search(int z, vector<int> subset, bool row) {
  int n;
  if (row)
    n = h;
  else
    n = w;
  if (z == n) {
    if (row)
      rows.push_back(subset);
    else
      cols.push_back(subset);
  } else {
    search(z + 1, subset, row);
    subset.push_back(nums[z] - 1);
    search(z + 1, subset, row);
    subset.pop_back();
  }
}

bool solve(vector<int> a, vector<int> b) {
  vector<string> g = grid;
  for (int i : a) {
    for (int j = 0; j < w; j++) g[i][j] = '.';
  }
  for (int i : b) {
    for (int j = 0; j < h; j++) g[j][i] = '.';
  }
  int cnt = 0;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (g[i][j] == '#') cnt++;
    }
  }
  if (cnt == k) return true;
  return false;
}

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

  cin >> h >> w >> k;
  nums.assign(h, 0);
  for (int i = 1; i <= h; i++) {
    nums[i - 1] = i;
  }
  search(0, vector<int>(0), true);
  nums.assign(w, 0);
  for (int i = 1; i <= w; i++) {
    nums[i - 1] = i;
  }
  search(0, vector<int>(0), false);

  grid.assign(h, "");
  for (int i = 0; i < h; i++) cin >> grid[i];

  int cnt = 0;
  for (vector<int> row : rows) {
    for (vector<int> col : cols) {
      if (solve(row, col)) cnt++;
    }
  }
  cout << cnt << "\n";

  return 0;
}

Measured memory_bytes: 3664
//Optional FAST

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")

//Required Libraries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);
const long double PI=3.14159265358979;

// Required random number generators

// mt19937 gen_rand_int(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 gen_rand_ll(chrono::steady_clock::now().time_since_epoch().count());

//Required Functions

ll power(ll x,ll y) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2) % MOD; 
    p = (p * p) % MOD; 
  
    return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work

int main()
{
    #ifndef ONLINE_JUDGE
    if (fopen("INPUT.txt", "r"))
    {
        freopen ("INPUT.txt" , "r" , stdin);
        //freopen ("OUTPUT.txt" , "w" , stdout);
    }
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    clock_t clk;
    clk = clock();
//-----------------------------------------------------------------------------------------------------------//

    READV(N);
    READV(L);
    bool pos=false;
    READAR(A,N);
    FORI(i,1,N)
    {
        if(L<=A[i-1]+A[i])
        {
            cout<<"Possible"<<endl;
            FORI(j,1,i)
            {
                cout<<j<<endl;
            }
            FORD(j,N-1,i)
            {
                cout<<j<<endl;
            }
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<"Impossible"<<endl;

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


    clk = clock() - clk;
    cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << endl;

    return 0;
}

Measured memory_bytes: 4564
#include <bits/stdc++.h>
using namespace std;
#define sci1(a) scanf("%d",&a)
#define sci2(a,b) scanf("%d %d",&a,&b)
#define sci3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define scs(s) scanf("%s",s)
#ifndef GET_MACRO

#define GET_MACRO(__1,__2,__3,NAME,...) NAME

#endif // GET_MACRO

#define sci(...) GET_MACRO(__VA_ARGS__,sci3,sci2,sci1)(__VA_ARGS__)
#define ll long long
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
#define LSB(i) ((i)&(-i))
#define read freopen("input.txt","r",stdin)
#define write freopen("output.txt","w",stdout)
#define infl 0x7ffffffffffffff
#define infi  0x7fffffff
#define fill_(a,b) fill(a.begin(),a.end(),b)
#define pb push_back
#define xx first
#define yy second
int main(){
    int A[100000],B[100000],i,j;
    int  n;
    sci(n);
    for(i=0;i<n;i++){
        sci(A[i],B[i]);
    }
    ll ans=0;
    ll tsum=0;
    ll tmp;
    for(i=n-1;i>=0;i--){
        ans+=(B[i]-((ll)(A[i]+ans)%(ll)B[i]))%B[i];

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


Measured memory_bytes: 1024
use std::cmp::max;
#[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, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

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

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

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

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
//usage
//input! {
//  h: i32;
//  v: [i32; n]
//  x: [[i32; n]; m]
//  f: chars <- Vec<char>
//}

fn main() {
    input!{
        s: chars,
        t: chars
    }

    // dp[i][j] = sのi文字目までとtのj文字目までの中での部分列の最大
    // dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[i][j - 1])
    let mut dp = vec![vec![0; s.len() + 1]; t.len() + 1];

    for i in 1..t.len() + 1 {
        for j in 1..s.len() + 1 {
            dp[i][j] = max(max(dp[i - 1][j - 1] + (t[i - 1] == s[j - 1]) as i64, dp[i - 1][j]), dp[i][j - 1]);
        }
    }

    let mut ans: Vec<char> = Vec::new();
    let (mut slen, mut tlen) = (s.len(), t.len());
    // 文字が同じなときは[i - 1][j - 1] => [i][j]で更新が行われているので
    // そこだけ探索すれば良い
    while slen > 0 && tlen > 0 {
        if dp[tlen][slen] == dp[tlen - 1][slen] {
            tlen -= 1;
        }
        else if dp[tlen][slen] == dp[tlen][slen - 1] {
            slen -= 1;
        }
        else {
            tlen -= 1;
            slen -= 1;
            ans.push(s[slen])
        }
    }
    println!("{}", ans.into_iter().rev().collect::<String>());

}

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

int main()
{
    int n; cin>>n;
    vector<int> a(n+2, 10001);
    for(int i=1; i<=n; ++i) cin>>a[i];

    int res=INT_MAX;
    for(int t=1; t<=2; ++t) {
        auto b=a;
        int cnt=0;
        for(int i=t; i<=n; ++i) {
            if (a[i]==a[i-1]) {
                for(int j=1; j<=10000; ++j) if (j!=a[i] && j!=a[i-1] && j!=a[i+1]) {
                    a[i]=j;
                    ++cnt;
                    break;
                }
            }
        }
        a=b;
        res=min(res, cnt);
    }
    cout<<res<<endl;
}


Measured memory_bytes: 256