akhauriyash/Code-Regression huggingface dataset:
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

constexpr int MOD_TYPE = 2;
constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
constexpr int INF = (int)1e9;
constexpr ll LINF = (ll)4e18;
constexpr ld PI = acos(-1.0);
constexpr ld EPS = 1e-11;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";

#pragma endregion

void solve()
{
  int n;
  cin >> n;
  int cnt = 0;
  int a[100010];
  rep(i, n) cin >> a[i];
  rep(i, n - 2)
  {
    if (a[i] < a[i + 1] && a[i + 1] < a[i + 2])
      cnt++;
    else if (a[i] > a[i + 1] && a[i + 1] > a[i + 2])
      cnt++;
  }
  cout << cnt << endl;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(30) << setiosflags(ios::fixed);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
int main()
{
    int cnt = 0;
    string a , b;
    cin >> a >> b;
    int n = a.length();
    for (int i = 0 ; i < n ; i++){
        cnt += (a[i] != b[i]);
    }
    cout << cnt << endl;
    return 0;
}


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

using namespace std;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    vector<int> dp, rocks;
    for (int i = 0; i < n; i++) dp.push_back(0);
    int num;
    while (cin >> num) rocks.push_back(num);
    /* while (cin >> num) {
        int left = abs(dp[i - 2] - num);
        int right = abs(dp[i - 1] - num);
        dp[i] = (left >= right ? right: left);
        i++;
    }
    */
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            continue;
        } else if(i == 1) {
            dp[1] = abs(rocks[1] - rocks[0]);
            continue;
        }
        int left = dp[i - 2] + abs(rocks[i - 2] - rocks[i]);
        int right = dp[i - 1] + abs(rocks[i] - rocks[i - 1]);
        dp[i] = (left >= right ? right : left);
    }
    /* for (auto j = 0; j < dp.size(); j++) {
        cout << "dp[" << j << "]"  << dp[j] << endl;
    } */
    cout << dp[n - 1] << endl;
}


Measured memory_bytes: 1400
using System;
public class Hello{
    public static void Main(){
        string[] i = Console.ReadLine().Split();
       int a = int.Parse(i[0]);
       int b = a/3600;
       int c = a%3600;
       int d = c/60;
       int e = c%60;
   
     Console.WriteLine(b+":"+d+":"+e);
    }
}


Measured memory_bytes: 17908
function main(input) {
  let args = input.split('\n');
  // let item = args[a++].split(' ').map((e) => +e);
  let a = 0;
  let n = +args[a++];
  let sum = 0;
  let map = {};
  let arr = args[a++].split(' ').map((e) => +e);
  for (let i = 0; i < n; ++i) {
    let x = arr[i];
    sum += x;
    if (map[x] != null) {
      map[x]++;
    } else {
      map[x] = 1;
    }
  }

  let q = +args[a++];
  for (let i = 0; i < q; ++i) {
    let [b, c] = args[a++].split(' ').map((e) => +e);
    if (map[b] && map[b] > 0) {
      let ct = map[b];
      sum -= ct * b;
      map[b] = 0;
      if (map[c]) {
        map[c] += ct;
      } else {
        map[c] = ct;
      }
      sum += ct * c;
    }
    console.log(sum);
  }
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 64940
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <cassert>
#include <queue>
#include <ctime>
#include <string>
#include <cstring>
#include <random>
#define mp make_pair
#define pb push_back
#define NAME ""
#define y1 y1_423
#define list lista

using namespace std;

typedef long long ll;
typedef long double ld;

template<typename T>
ostream& operator << (ostream& cout, const vector<T> &a) {
	if ((int)a.size() == 0) {
		return (cout << "()");
	}
	cout << "(" << a[0];
	for (int i = 1; i < (int)a.size(); i++) {
		cout << "; " << a[i];
	}
	return (cout << ")");
}

template<typename T>
ostream& operator << (ostream& cout, const set<T> &a) {
	if ((int)a.size() == 0) {
		return (cout << "{}");
	}
	auto it = a.begin();
	cout << "{" << *it;
	++it;
	for (; it != a.end(); ++it) {
		cout << "; " << *it;
	}
	return (cout << "}");
}

template<typename T>
ostream& operator << (ostream& cout, const multiset<T> &a) {
	if ((int)a.size() == 0) {
		return (cout << "{}");
	}
	auto it = a.begin();
	cout << "{" << *it;
	++it;
	for (; it != a.end(); ++it) {
		cout << "; " << *it;
	}
	return (cout << "}");
}

template<typename T1, typename T2>
ostream& operator << (ostream& cout, const pair<T1, T2> &a) {
	return cout << "(" << a.first << "; " << a.second << ")";
}

random_device gen;
mt19937 rnd(gen());

const int nmax = 2000 * 1000;
const int inf = 2000 * 1000 * 1000;
const ll infl = 1000ll * 1000ll * 1000ll * 1000ll * 1000ll * 1000ll;
const int mod = 1000 * 1000 * 1000 + 7;
const ld pi = acos(-1.0);

ll n, a, b;

int main() {
	cin >> n >> a >> b;
	if (a > b) cout << 0 << endl;
	else cout << max(0ll, (n - 1) * b + a - ((n - 1) * a + b) + 1);
	return 0;
}



Measured memory_bytes: 256
#include <assert.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;

using namespace std;

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

  ll N;
  cin >> N;

  for (ll h = 1; h <= 3500; h++) {
    for (ll n = h; n <= 3500; n++) {
      ll d = (4 * h * n - n * N - N * h);
      if (d > 0) {
        ll v = (h * n * N) / d;
        if (v > 0 && (4 * h * n * v / (h * n + n * v + v * h) == N)) {
          cout << h << " " << n << " " << v << endl;
          return 0;
        }
      }
    }
  }
  return 0;
}


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

int e;

int solve(){
  int min = 100000000;
  for(int z = 0; z * z * z <= e;z++){
    int y = floor(sqrt(e - z * z * z));
    int x = e - z * z * z - y * y;
    if(z + y + x < min){
      min = x + y + z;
    }
  }
  return min;
}

int main() {
  while(cin >> e && e > 0){
    cout << solve() << endl;
  }
}



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

int main()
{
	string s;
	int ans=0;
	cin>>s;
	for(int i=0;i<=3;++i)
	{
		if(s[i]=='+')	ans+=1;
		if(s[i]=='-')	ans-=1;	
	}
	cout<<ans;	
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication11 {
    class Program {
        readonly int[] angleEachTime = new int[]{0,30,60,90,120,150,180,210,240,270,300,330};
        readonly string[] message = new string[]{"safe","warning","alert"};

        static void Main(string[] args) {
            new Program().solve();
        }

        void solve() {
            int num_Input = int.Parse(Console.ReadLine());
            for (int i = 0; i < num_Input; i++) {
                TimeSpan input = TimeSpan.Parse(Console.ReadLine());
                int[] hand = new int[2];
                hand[0] = input.Hours;
                hand[1] = input.Minutes;
                Console.WriteLine(message[checkAngle(hand)]);
            }
        }

        int checkAngle(int[] hand) {
            double[] angle = new double[] { 0, 0 };
            angle[0] = angleEachTime[hand[0]] + hand[1] * 0.5;
            angle[1] = hand[1] * 6;
 
            double angleHands = 0;
            if (angle[0] < angle[1]) {
                angleHands = angle[1] - angle[0];
            } else angleHands = angle[0] - angle[1]; ;
            if (angleHands > 180) {
                angleHands = 360 - angleHands;
            }
            if (angleHands < 30) {
                return 2;
            } else if (angleHands >= 90) {
                return 0;
            } else return 1;
        }
        
    }
}

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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)

typedef long long ll;

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


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

    vector<string>s(n);
    rep(i,n){
        cin>>s[i];
    }

    sort(s.begin(),s.end());

    map<string,int>cnt;
    rep(i,n){
        cnt[s[i]]++;
    }

    int MAX=0;
    rep(i,n){
        MAX=max(MAX,cnt[s[i]]);
    }

    set<string>ss;
    rep(i,n){
        if(cnt[s[i]]==MAX){
            string sss=s[i];
            ss.insert(sss);
        }
    }
    for (auto itr = ss.begin(); itr != ss.end(); ++itr) {
            cout << *itr<<endl;
        }

}


Measured memory_bytes: 36096
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using P=pair<int,int>;
using lint=long long;
using ll=long long;
const lint inf=1e18+7;
const int MOD=1000000007;
signed main(){
  int x;cin>>x;
  x++;x%=2;
  cout<<x<<"\n";
  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
using namespace std;
const int MAXn = 100;
const int INFTY = 1 << 21;

int n, M[MAXn][MAXn], col[MAXn], d[MAXn], p[MAXn];

void dijkstra(int s) {
    for(int i = 0; i < n; i++) {
        col[i] = 0;
        d[i] = INFTY;
    }
    d[s] = 0;
    p[s] = -1;

    while(1) {
        int mincost = INFTY;
        int u;
        for(int i = 0; i < n; i++) {
            if(col[i] != 2 && d[i] < mincost) {
                mincost = d[i];
                u = i;
            }
        }
        if(mincost == INFTY) break;
        col[u] = 2;
        for(int v = 0; v < n; v++) {
            if(col[v] != 2 && M[u][v] != INFTY) {
                if(d[u] + M[u][v] < d[v]) {
                    d[v] = d[u] + M[u][v];
                    p[v] = u;
                    col[v] = 1;
                }
            }
        }
    }

    for(int i = 0; i < n; i++)
        cout << i << " " << (d[i] == INFTY ? -1 : d[i]) << endl;

    return;
}

int main() {
    cin >> n;
    int id, k, v, c;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) M[i][j] = INFTY;
    for(int i = 0; i < n; i++) {
        cin >> id >> k;
        for(int j = 0; j < k; j++) {
            cin >> v >> c;
            M[id][v] = c;
        }
    }
    dijkstra(0);
    return 0;
}


Measured memory_bytes: 3088
#include <stdio.h>
const int mod = 1000000007;
int pow(int a, int n);
// aの逆元の計算
int inv(int a) {
    return pow(a, mod - 2);
}
int sub(int a, int b) {
    a %= mod;
    b %= mod;
    return (a + mod - b) % mod;
}
int mul(int a, int b) {
    a %= mod;
    b %= mod;
    return (int)((long long)a * (long long)b % mod);
}
int div(int a, int b) {
    //printf("div:b:%d invb:%d\n", b,inv(b));
    int ret = mul(a, inv(b));
    //printf("div:%d %d %d\n", a,b,ret);
    return ret;
}
// a/bの計算 a/b = a*(b^1)
int pow(int a, int n) {
    if (n == 0) {
        return 1;
    }
    //printf("%d %d\n",a,n);
    int h = n / 2;
    int hv = pow(a, h);
    int ret = mul(hv, hv);
    if (n % 2 == 1) {
        ret = mul(ret, a);
    }
    return ret;
}
int combination(int n, int a) {
    int n1 = n;
    int n2 = 1;
    for (int i = n - 1; i >= n - a + 1; --i) {
        n1 = mul(n1, i);
    }
    for (int i = 2; i <= a; ++i) {
        n2 = mul(n2, i);
        //printf("i:%d n2:%d\n", i, n2);
    }
    int comb = div(n1, n2);
    //printf("%d,%d  comb:%d\n", n1, n2, comb);
    return comb;
}

int main()
{
    int n, a, b;
    scanf("%d%d%d",&n,&a,&b);
    int ans = pow(2,n);
    ans = sub(ans, combination(n,a));
    ans = sub(ans, combination(n,b));
    ans = sub(ans, 1);
    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= end; --i)
#define iter(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define riter(i, c) for (auto i = (c).rbegin(); i != (c).rend(); ++i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return 0;}
template<typename T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return 0;}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    cout << (N + 1) / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<random>
#include<ctime>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=500;
mt19937 mt(time(0));
struct edge{
	int u,v,w;
}e[N];
int n,m,ans=0x3fffffff,fa[16],nww,sum,rt[16];
bool con[N];
vector<int>G[16];
inline int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
void dfs(int now,int pre=0){
	for(int to:G[now])if(to!=pre)fa[to]=now,dfs(to,now);
}
void dfs2(int now){
	for(int to:G[now])if(!rt[to])rt[to]=rt[now],dfs2(to);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		sum+=w;
		e[i]=(edge){u,v,w};
	}
	while(1.*clock()/CLOCKS_PER_SEC<3.9){
		shuffle(e+1,e+m+1,mt);
		memset(con,0,sizeof con);
		for(int i=1;i<=n;++i)fa[i]=i,G[i].clear(),rt[i]=0;
		nww=sum;
		for(int i=1;i<=m;++i){
			int x=find(e[i].u),y=find(e[i].v);
			if(x!=y)nww-=e[i].w,con[i]=1,fa[y]=x,
			G[e[i].u].push_back(e[i].v),G[e[i].v].push_back(e[i].u);
		}
		fa[1]=0,dfs(1);
		for(int i=n;i;i=fa[i])rt[i]=i;
		for(int i=n;i;i=fa[i])dfs2(i);
		for(int i=1;i<=m;++i)if(!con[i]&&rt[e[i].u]==rt[e[i].v])nww-=e[i].w;
		if(nww<ans)ans=nww;
	}
	cout<<ans<<'\n';
	return 0;
}

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

void Solve(){
 	int n, m;
 	cin>>n>>m;
 	vector<int> g[n + 1];
 	while(m--){
 		int u, v;
 		cin>>u>>v;
 		g[u].push_back(v);
 		g[v].push_back(u);
 	}
 	vector<int> trace(n + 1);
 	trace[1] = 0;
 	queue<int> q;
 	vector<int> vst(n + 1);
 	vst[1] = true;
 	q.push(1);
 	while(!q.empty()){
 		int current = q.front();
 		q.pop();
 		for(auto x: g[current]){
 			if(!vst[x]){
 				vst[x] = true;
 				q.push(x);
 				trace[x] = current;
 			}
 		}
 	}
 	bool good = true;
 	for(int i = 1; i <= n; i++){
 		if(!vst[i]) good = false;
 	}
 	if(good){
 		cout<<"Yes\n";
 		for(int i = 2; i <= n; i++) cout<<trace[i]<<'\n';
 	}
 	else cout<<"No\n";

}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T = 1;
	//cin>>T;
	while(T--){
		Solve();
	}
}

Measured memory_bytes: 10636
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

#include <boost/multiprecision/cpp_int.hpp>
namespace boost_multiprecision = boost::multiprecision;
#define lll boost_multiprecision::cpp_int

lll X, K, D;
signed main(){
    cin >> X >> K >> D;
    X = abs(X);
    if(X-K*D >= 0){
        cout << X-K*D << endl;
    }
    else{
        lll ans1 = X%D;
        lll ans2 = D-ans1;
        if((X-ans1)/D % 2 == K%2) cout << ans1 << endl;
        else cout << ans2 << endl;
    }
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define per(i,n) for(ll i = n-1; i >= 0; i--)
#define REP(i,n) for(ll i = 1; i < n; i++)
#define PER(i,n) for(ll i = n; i >= 1; i--)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
using vP = vector<P>;
using vPP = vector<vP>;
using vPl = vector<Pl>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }



int main(){
  int d;
  cin >> d;
  int k = 26;
  vi c(k);
  rep(i,k) cin >> c[i];
  vii s(d,vi(k));
  rep(i,d)rep(j,k) cin >> s[i][j];
  vi lastday(k);
  rep(i,d) {
    P mx = make_pair(0,0); // min-point, index
    rep(j,k) {
      int m_p = c[j] * ((i+1) - lastday[j]+1);
      chmax(mx, make_pair(m_p, j));
    }
    int today = mx.se;
    cout << today + 1 << endl;
    lastday[today] = i+1;
  }
}

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

#define ll long long 
#define pb push_back
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define memf(a) memset(a,false,sizeof(a))
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define INF 2000000000000000000
#define endl "\n"
#define _time_ 1.0 * clock() / CLOCKS_PER_SEC
#define popcount(x) __builtin_popcountll(x)
#define pll pair<ll,ll> 
#define ld long double

const int M=1000000007;
const int MM=998244353;
const long double PI = acos(-1);

ll power(ll b,ll e,ll m)
{
    if(e==0) return 1;
    if(e&1) return b*power(b*b%m,e/2,m)%m;
    return power(b*b%m,e/2,m);
}
ll power( ll b, ll e)
{
    if(e==0) return 1;
    if(e&1) return b*power(b*b,e/2);
    return power(b*b,e/2);
}
template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
template<typename T, typename U> ostream& operator<<(ostream &os, const pair<T, U> &p)
{ 
    return os<<'('<<p.F<< ","<<p.S<<')'; 
}

int _runtimeTerror_()
{
    ll n;
    cin>>n;
    string s;
    cin>>s;
    int cnt1=0;
    for(auto j:s)
        cnt1+=j-'0';
    if(cnt1==0)
    {
        for(auto j:s)
            cout<<1<<"\n";
        return 0;
    }
    int cnt2=cnt1-1;
    ++cnt1;
    string t=s;
    reverse(all(t));
    ll ans1=0,ans2=0;
    for(int i=0;i<n;++i)
    {
        ans1=(ans1+(t[i]-'0')*power(2,i,cnt1))%cnt1;
        if(cnt2!=0)
            ans2=(ans2+(t[i]-'0')*power(2,i,cnt2))%cnt2;
    }
    auto f=[&](ll x)
    {
        ll ans=0;
        while(x)
        {
            x=x%popcount(x);
            ++ans;
        }
        return ans;
    };
    for(int i=0;i<n;++i)
    {
        if(s[i]=='1')
        {
            if(cnt2==0)
                cout<<0<<"\n";
            else
            {
                ll val=(ans2-power(2,n-i-1,cnt2)+cnt2)%cnt2;
                cout<<f(val)+1<<"\n";
            }
        }
        else
        {
            ll val=(ans1+power(2,n-i-1,cnt1))%cnt1;
            cout<<f(val)+1<<"\n";
        }
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef runSieve
        sieve();
    #endif
    #ifdef NCR
        initialize();
    #endif
    int TESTS=1;
    //cin>>TESTS;
    while(TESTS--)
        _runtimeTerror_();
    return 0;
}

Measured memory_bytes: 3872
n, m = map(int, input().split())

if n % 2 == 1:
    for i in range(1, m+1):
        print(i, n - i)
else:
    for i in range(1, min(n//4+1, m+1)):
        print(i, n - i + 1)
    for i in range(n//4+1, m+1):
        print(i, n - i)


Measured memory_bytes: 69468
n = gets.to_i
h = gets.split.map &:to_i
check = 0
(n - 2).times do |i|
  next if h[-1 * (i + 1)] >= h[-1 * (i + 2)]

  h[-1 * (i + 2)] -= 1
  unless h[-1 * (i + 1)] >= h[-1 * (i + 2)]
    check = 1
    break
  end
end
puts check.zero? ? :Yes : :No

Measured memory_bytes: 8580
#include <bits/stdc++.h>
#define REP(i,  n) for (int i  =  0; i < (int)(n); ++i)
#define REPR(i,  n) for (int i  =  n - 1; i >= 0; --i)
using namespace std;

int main() {
  int a; cin >> a;
  cout << a + a*a + a*a*a << endl;
  return 0;
}


Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200005;
int n,a[N];
LL k;
bool check(LL x){
	LL cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]<=0){
			int l=0,r=n,mid;
			while(l<r-1){
				mid=(l+r)>>1;
				if(1LL*a[i]*a[mid]<=x)r=mid;
				else l=mid;
			}
			if(r<=i)cnt+=n-r;
			else cnt+=n-r+1;
			if(1LL*a[i]*a[r]>x)cnt--;
		}else{
			int l=1,r=n+1,mid;
			while(l<r-1){
				mid=(l+r)>>1;
				if(1LL*a[i]*a[mid]<=x)l=mid;
				else r=mid;
			}
			if(l<=i)cnt+=l;
			else cnt+=l-1;
			if(1LL*a[i]*a[l]>x)cnt--;
		}
		if(cnt>=k*2)return 1;
	}
	return 0;
}
int main(){
	LL l=-1e18-1,r=1e18,mid;
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+1+n);	
	//printf("%d\n",check(-12));
	while(l<r-1){
		mid=(l+r)>>1;
		if(check(mid))r=mid;
		else l=mid;
	}
	printf("%lld\n",r);
	return 0;
}

Measured memory_bytes: 1024
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    let mut ans = 100000;
    for a in 1..n {
        let mut a = a;
        let mut b = n - a;
        let mut sum = 0;
        while a > 0 {
            sum += a % 10;
            a /= 10;
        }
        while b > 0 {
            sum += b % 10;
            b /= 10;
        }
        ans = std::cmp::min(ans, sum);
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
//↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const double pi = acos(-1);
const int SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
long long fac[200005], finv[200005], inv[200005];
vector<long long>dij;
struct edge { long long to, cost; };
vector<vector<edge> >G;

long long mod_pow(long long a, long long b) {
	long long res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}

	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

//↑template↑

long long n, k[305][305], ans;
vector<vector<long long>>d;
void warshall_floyd(long long a) {
	for (int i = 0; i < a; ++i) {
		for (int j = 0; j < a; ++j) {
			d[i][j] = k[i][j];
		}
	}

	for (int i = 0; i < a; ++i) {
		for (int j = 0; j < a; ++j) {
			for (int k = 0; k < a; ++k) {
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}
}

int main() {
	cin >> n;
	d.resize(n, vector<long long>(n));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) { cin >> k[i][j]; }
	}
	warshall_floyd(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) { if (d[i][j] < k[i][j]) { cout << -1 << endl; return 0; } }
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			bool ok = 1;
			for (int kk = 0; kk < n; ++kk) {
				if (d[i][kk] + d[kk][j] == d[i][j] && i != kk && j != kk) { ok = 0; break; }
			}
			if (ok) { ans += d[i][j]; }
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 2176
#[allow(unused_imports)]
use std::cmp::{min,max};

fn f(n: i64, a: i64, b: i64) -> bool {
    let mid = n / 2;
    let window = 10;
    let d = max(1, mid-window);
    let u = min(n, mid+window);
    for i in d..u+1 {
        let ai = if i <= a - 1 { i } else { i+1 };
        let bi = if n > b-1 && i < (n+1)-(b-1) { n+2-i } else { n+1-i };
        if ai * bi >= a * b {
            return false;
        }
    }
    true
}

fn main() {
    let q = read_i64();
    for _ in 0..q {
        let xs = read_vec_i64();
        let (a,b) = (xs[0],xs[1]);
        let mut lower = 0;
        let mut upper = 1<<31;
        while lower + 1 != upper {
            let mid = (lower + upper) / 2;
            if f(mid,a,b) {
                lower = mid;
            }
            else {
                upper = mid;
            }
        }
        println!("{}", lower);
    }
}

#[allow(dead_code)]
fn read_line() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    ret.pop();
    return ret;
}

#[allow(dead_code)]
fn read_i64() -> i64 {
    let ss = read_line();
    return ss.parse::<i64>().unwrap();
}

#[allow(dead_code)]
fn read_vec_i64() -> Vec<i64> {
    let mut res = vec![];
    let ss = read_line();
    for ts in ss.split_whitespace() {
        let x = ts.parse::<i64>().unwrap();
        res.push(x);
    }
    return res;
}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

string s;
LL n, dp[200000][3][3], MOD = 998244353;

int main() {
	string s;
	cin >> s;
	n = s.size();
	
	LL c = 0;
	inc(i, n - 1) { if(s[i] == s[i + 1]) { c++; } }
	
	if(c == n - 1) { cout << 1 << endl; return 0; }
	
	if(n == 2) {
		cout << 2 << endl;
		return 0;
	}
	if(n == 3) {
		LL ans = 0;
		if(s[0] == s[2]) { ans = 7; }
		else if(s[0] == s[1] || s[1] == s[2]) { ans = 6; }
		else { ans = 3; }
		
		cout << ans << endl;
		return 0;
	}
	
	inc(i, n) {
		if(i == 0) {
			inc(j, 3) { dp[i][j][j] = 1; }
		} else {
			inc(j, 3) {
			inc(k, 3) {
			inc(l, 3) {
				if(k == l) { continue; }
				(dp[i][(j + l) % 3][l] += dp[i - 1][j][k]) %= MOD;
			}
			}
			}
		}
	}
	
	LL w = 0;
	inc(i, n) { w += s[i] - 'a'; }
	w %= 3;
	
	LL x = 0;
	inc(k, 3) { x += dp[n - 1][w][k]; }
	x %= MOD;
	
	LL y = 1;
	inc(i, n - 1) { (y *= 3) %= MOD; }
	
	LL ans = (y + (MOD - x) + (c == 0 ? 1 : 0)) % MOD;
	
	cout << ans << endl;
	
	return 0;
}


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

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

    vector<int> A(N);
    vector<int> B(N); 
    // vector<double> cost(N); 
    // map<int, double> cost;
    rep(i, N){
        cin >> A[i] >> B[i];
        // cost[i] = (double)A[i] / (double)B[i];
    }

    vector<int> cost(H+1, 1001001001);
    cost[0] = 0;
    int can = 0;

    for(int HP = 0; HP <= H; ++HP){
        for(int i = 0; i < N; ++i){
            if (HP - A[i] >= 0){
                can = cost[HP - A[i]] + B[i];
            }else{
                can = cost[0] + B[i];
            }
            if (can < cost[HP]) cost[HP] = can;
        }
    }
    
    cout << cost[H] << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define sz(x) int(x.size())
using ll = long long;
using P = pair<int,int>;
const ll LLINF = numeric_limits<long long>::max();
const int mod = 1000000007;
const int INF = 1001001001;

int main()
{
    int a,p;
    cin >> a >> p;
    p += a*3;
    cout << p/2;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 5e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//
ll dp[1005][1005];

int main() {
    init();
    string s, t;
    cin >> s >> t;

    ll sn = s.size(), tn = t.size();
    rep(i, sn + 1) dp[i][0] = i;
    rep(i, tn + 1) dp[0][i] = i;

    rep(i, sn){
        rep(j, tn){
            dp[i + 1][j + 1] = min({dp[i][j + 1] + 1, dp[i + 1][j] + 1, dp[i][j] + (s[i] != t[j])});
        }
    }

    cout << dp[sn][tn] << endl;

    // rep(i, sn + 1) verr(dp[i], tn + 1);
}


Measured memory_bytes: 11088
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    testimonies = []
    for _ in range(n):
        a = input_int()
        testimony = []
        for _ in range(a):
            x, y = input_int_list()
            testimony.append([x, y])
        testimonies.append(testimony)
    # すべてのパターンを試すO(2**n)
    ans = 0
    for i in range(2**n):
        sample = [None] * n
        for j in range(n):
            if i >> j & 1:
                sample[j] = 1
            else:
                sample[j] = 0
        sample = [None] + sample  # 1-indexed
        # sampleが成立するか確認する
        is_possible = True
        for idx, testimony in enumerate(testimonies):
            if sample[idx + 1] == 1:
                for x, y in testimony:
                    if sample[x] == y:
                        continue
                    else:
                        is_possible = False
        # すべての証言が正しければ、正直者の数を答えにする
        if is_possible:
            ans = max(ans, sum(sample[1:]))
    print(ans)

    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 68484
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://code-festival-2016-qualb.contest.atcoder.jp/tasks/codefestival_2016_qualB_c>
問題文============================================================
 xy平面上の0≦x≦W,0≦y≦Hをみたす領域にあるx,yともに整数である点すべてに、ひとつずつ家があります。
 
 x座標が等しくy座標の差が1であるか、y座標が等しくx座標の差が1であるような2点の組のうち、
 両方の点に家が存在するような全てのものに対し、その2点の間には舗装されていない道路があります。
 
 座標(i,j)と(i+1,j)にある家の間の道路を舗装するのにはjの値にかかわらずコストがpi、
 座標(i,j)と(i,j+1)にある家の間の道路を舗装するのにはiの値にかかわらずコストがqjかかります。
 
 高橋君は、このうちいくつかの道路を舗装し、
 舗装された道路のみを通って任意の2つの家の間を行き来できるようにしたいです。
 かかるコストの総和の最小値を求めてください。
 
 1≦W,H≦10^5
 1≦pi≦10^8(0≦i≦W−1)
 1≦qj≦10^8(0≦j≦H−1)
 pi(0≦i≦W−1)は整数である
 qj(0≦j≦H−1)は整数である
=================================================================

解説=============================================================

 最小全域木の要領でコストの小さいものから辺を追加して行くことを考える。
 一辺づつ考えると　O(H*W) で　TLEするので　いくつかまとめて辺を追加できないかを考える
 
 そこで次のような考え方ができる
 
 最初、 縦、横　共に　あるコストに関してそれぞれ 最大 h = H+1本、w = W+1本の辺を追加できる
 
 ここで 横に関して最小のコストを見た時 cost * h を用いて辺を引くことができ、
 その後 横に関しては　一本辺を引かなくてもよくなるので　w = w-1 とできる
 
 逆に　縦に関して最小のコストを見た時 cost * w を用いて辺を引くことができ、
 その後　縦に関しては　一本辺を引かなくてもよくなるので h = h-1 とできる
 
 これを繰り返すことによって最小全域木のコストを作れる
================================================================
*/
ll solve(){
    ll ret = 0;
    ll W,H; cin >> W >> H;
    vector<ll> p(W),q(H);
    for(auto &in:p) cin >> in;
    for(auto &in:q) cin >> in;
    vector<pll> event(W+H);
    for(int i = 0; i < W;i++) event[i] = {p[i],0};
    for(int i = 0; i < H;i++) event[i+W] = {q[i],1};
    sort(event.begin(),event.end());
    
    W++; H++;
    for(const pll& e:event){
        if(e.second == 0){ ret += e.first*H; W--;
        }else{ ret += e.first*W; H--; }
    }
    return ret;
}
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    cout << solve() << endl;
	return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <array>
#include <string>
using namespace std;

typedef long long int ll;

int main(){
	cin.sync_with_stdio(false);
	cin.tie(0);
	ll n, m;
	cin >> n >> m;
	if(n < m){
		for(ll i=0; i<m; i++)
			cout << n;
	}
	else
		for(ll i=0; i<n; i++)
			cout << m;
	return 0;
}

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

int main(){
    int N,L;
    cin >> N >> L;
    int allpi = 0;
    for(int i=0;i<N;i++){
        allpi += L+i;
    }
    // cout << "allpi = " << allpi << endl;
    int c;
    int minc = 1000000;
    int prepi;
    int mini;
    for(int i=0;i<N;i++){
        prepi = allpi;
        allpi -= (L+i);
        c = abs(prepi - allpi);
        if(c < minc){
            minc = c;
            mini = i;
        }
        allpi = prepi;
    }
    cout << allpi - (L+mini) << endl;
}

Measured memory_bytes: 256
n, a, b, c = list(map(int, input().split()))
l = [int(input()) for i in range(n)]

def dfs(cur, ta, tb, tc):
  if cur==n:
    if ta<=0 or tb<=0 or tc<=0:
      return 1e9
    else:
      return abs(a-ta)+abs(b-tb)+abs(c-tc)-30

  t1 = dfs(cur+1, ta, tb, tc)
  t2 = dfs(cur+1, ta+l[cur], tb, tc)+10
  t3 = dfs(cur+1, ta, tb+l[cur], tc)+10
  t4 = dfs(cur+1, ta, tb, tc+l[cur])+10
  return min(t1, t2, t3, t4)

print(dfs(0, 0, 0, 0))

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <tuple>

using namespace std;
const long long mod=1e9+7;
const long long INF=1LL<<60;

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

   int ans=0;
   for(int i=1;i<n-1;i++){
       if(a[i]!=max({a[i-1],a[i],a[i+1]}) && a[i]!=min({a[i-1],a[i],a[i+1]}))ans++;
   }
   cout<<ans<<endl;
}
 
   

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

using namespace std;

using ll = long long;

int main(){
    int n,m,c;
    cin>>n>>m>>c;
    vector<int> b(m);
    for(auto & a : b) cin>>a;
    vector<vector<int>> a(n,vector<int>(m));
    for(auto & t : a)for(auto & tmp : t)cin>>tmp;
    int count  =0;
    for(int i=0;i<n;++i){
        int ret = c;
        for(int j=0;j<m;++j){
            ret+=a[i][j]*b[j];
        }
        if(ret >0)count++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define N 100000

using namespace std;

struct qq {
	char name[100];
	int t;
};

qq Q[N];
int head, tail;

void enqueue(qq x) {
	Q[tail] = x;
	if (tail != N - 1) tail++;
	else tail = 0;
}

qq dequeue() {
	if (head != N - 1) {
		head++;
		return Q[head - 1];
	}
	else {
		head = 0;
		return Q[N - 1];
	}
}


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

	for (int i = 0; i < n; i++) {
		cin >> Q[i].name >> Q[i].t;
	}

	int T = 0;
	head = 0;
	tail = n;
	while (head != tail) {
		qq u = dequeue();
		if (u.t <= time) {
			T += u.t;
			cout << u.name << " " << T << endl;
		}
		else {
			T += time;
			u.t -= time;
			enqueue(u);
		}

	}
	return 0;
}


Measured memory_bytes: 13148
#include <string>
#include <iostream>
using namespace std;
int main(){
  string input_str;
  cin >> input_str;
  if(input_str[0] == input_str[1] || input_str[1] == input_str[2] || input_str[2] == input_str[3]){
    cout << "Bad" << endl;
  }else{
    cout << "Good" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
using Graph = vector<vector<int>>;
ll mypow(ll x, ll n, ll m) {
	if (n == 0) {
		return 1;
	}
	if (n % 2 == 0) {
		return mypow(x*x%m, n / 2, m);
	}
	else {
		return x * mypow(x, n - 1, m) % m;
	}
}
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
//テーブルをつくる前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;//mod pにおける1,2,,,nの逆元
	for (int i = 2; i < MAX; ++i) {
		fac[i] = fac[i - 1] * i%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}

ll COM(int n, int k) {
	if (n < k)return 0;
	if (n < 0 || k < 0)return 0;
	return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}
///////////////////////////////////////



int main() {
	int K, N; cin >> K >> N;
	int a[200100];
	int key = 0;
	REP(i, N) {
		cin >> a[i];
	}
	vector<int>V;
	for (int i = 0; i < N; ++i) {
		if (i == N - 1) {
			V.push_back(K - a[i] + a[0]);
		}
		else {
			V.push_back(a[i + 1] - a[i]);
		}
	}
	for (int i = 0; i < V.size(); ++i) {
		key = max(key, V[i]);
	}
	cout << K - key << endl;
	return 0;
}


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

long long mod=1000000000+7;

int main(){
    int n;
    while(scanf("%d",&n)==1){
        long long ans=1;

        int i;
        for(i=2;i<=n;i++){
            ans=(ans*i)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>

int pow_mod_2019(int y)
{
    int ans = 1;
    for (int i = 0; i < y; i++)
    {
        ans = (ans * 10) % 2019;
    }
    return ans;
}

int main()
{
    std::string S;
    std::cin >> S;
    // S = 2019
    // T[0] = 9;
    // T[1] = 19;
    // T[2] = 19;
    // T[3] = 2019;

    // T[i] - T[j] mod 2019 == 0
    // T[i] mod 2019 - T[j] mod 2019 == 0
    // T[i] == T[j] となるような (i, j) の個数

    std::vector<int> decimal(S.length());
    int d = 1;
    for (int i = 0; i < decimal.size(); i++)
    {
        decimal[i] = d;
        d = (d * 10) % 2019;
    }

    std::reverse(S.begin(), S.end());
    std::unordered_map<int, int> count;
    count[0] = 1;
    int x = 0;
    for (int i = 0; i < S.length(); i++)
    {
        x = ((S[i] - '0') * decimal[i] + x) % 2019;
        count[x]++;
    }
    int ans = 0;
    for (auto const &e : count)
    {
        int diff = e.second * (e.second - 1) / 2;
        ans += diff;
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 4400
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#include <fstream>
//#include <random>
#include <map>
//#include <unordered_map>
#include <cstdlib>
#include <functional>
#include <time.h>
//#include <chrono>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <limits>
#include <numeric>
//#include <type_traits>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define MOD 1000000007
#define SORT(s) sort(s.begin(), s.end());
#define REVERSE(s) reverse(s.begin(), s.end());
#define SUM(s) accumulate(s.begin(), s.end(), 0LL);
#define P pair<int,int>
#define mp make_pair
#define valid(x,y,h,w) (0<=x&&x<h&&0<=y&&y<w)
//#define int ll
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int ndx[8] = { 0,1,0,-1, 1,1,-1,-1 };
int ndy[8] = { 1,0,-1,0, 1,-1,-1,1 };
double pi = 3.141592653589793;
using namespace std;
int POW(int x, int y) { return int(pow(double(x), double(y))); }
double log(double a, double b) { return log(b) / log(a); }



int main() {
	int n, m;
	cin >> n >> m;
	//vector<int> a(m), b(m);
	vector<vector<int>> p(n);
	rep(i, m) {
		int a, b;
		cin >> a >> b;;
		a--; b--;
		p[a].push_back(b);
		p[b].push_back(a);
	}

	vector<int> ans(n);
	rep(i, n) {
		ans[i] = -1;
	}
	ans[0] = 0;
	//int now = 0;
	queue<int> q;
	q.push(0);
	while (q.size()) {
		int now = q.front();
		q.pop();
		auto next = p[now];
		rep(i, next.size()) {
			int t2 = next[i];
			if (ans[t2] >= 0) {
				continue;
			}
			ans[t2] = now;
			q.push(t2);
		}
	}
	cout << "Yes" << endl;
	FOR(i, 1, n) {
		cout << ans[i] + 1 << endl;
	}
}




Measured memory_bytes: 10560
#include <iostream>

int main()
{
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    std::cout << (c / b + (c % b == 0 ? 0 : 1) <= (a / d + (a % d == 0 ? 0 : 1)) ? "Yes" : "No") << std::endl;

    return 0;
}


Measured memory_bytes: 3120
#include <stdio.h>
int main(void){
    int i,n;
    scanf("%d\n",&n);
    int a,j=0;
    
    for (i=0;i<n;i++){
	scanf("%d",&a);
	if(a%2==0&&a%3!=0&&a%5!=0){
	        printf("DENIED");
	        j++;
	        break;
	    }
	}
    if(j==0)printf("APPROVED");
 
    return 0;
    }

Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <map>
#include <numeric>
#include <functional>
#include <math.h>

using namespace std;

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

#define INF ((int)1e9)
#define INFLL ((ll)1e18)
#define MOD (1000000007LL)


int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> H(N);
    for (int n = 0; n < N; ++n) {
        cin >> H[n];
    }
    vector<vector<int>> G(N);
    for (int m = 0; m < M; ++m) {
        int A, B;
        cin >> A >> B;
        --A; --B;
        G[A].push_back(B);
        G[B].push_back(A);
    }
    
    int Res = 0;
    for (int n = 0; n < N; ++n) {
        bool b = true;
        for (int m : G[n]) {
            if (H[m] >= H[n]) {
                b = false;
                break;
            }
        }
        if (b) ++Res;
    }
    cout << Res << endl;

    return 0;
}


Measured memory_bytes: 8728
N = int(input())

c = 0
sb = ea = both = 0
for i in range(N):
    s = input()
    c += s.count('AB')
    if s[0] == 'B' and s[-1] == 'A':
        both += 1
    elif s[0] == 'B':
        sb += 1
    elif s[-1] == 'A':
        ea += 1

if both > 0:
    c += both-1
    if sb > 0:
        c += 1
        sb -= 1
    if ea > 0:
        c += 1
        ea -= 1
    c += min(sb, ea)
else:
    c += min(sb, ea)

print(c)

Measured memory_bytes: 3064
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

int n, cur, x, y, ans, ind[1000000];
vector<int> vec[1000000];
map<pair<int, int>, int> mp;

queue<int> qu;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	cur = 1;
	for (int i = 1; i <= n; i++) {
		int pre;
		x = i;
		cin >> y;
		if (x > y) swap(x, y);
		if (mp.count({ x, y }) == 0) {
			mp[{x, y}] = cur;
			cur++;
		}
		pre = mp[{x, y}];
		for (int j = 2; j <= n - 1; j++) {
			x = i;
			cin >> y;
			if (x > y) swap(x, y);
			if (mp.count({ x, y }) == 0) {
				mp[{x, y}] = cur;
				cur++;
			}
			int tmp = mp[{x, y}];
			vec[pre].pb(tmp);
			ind[tmp]++;
			pre = tmp;
		}
	}
	for (int i = 1; i < cur; i++) {
		if (ind[i] == 0) qu.push(i);
	}
	int lt = 0, cnt = 0;
	if (!qu.empty()) lt = qu.back();
	while (!qu.empty()) {
		auto p = qu.front();
		qu.pop();
		cnt++;
		for (int i = 0; i < (int)vec[p].size(); i++) {
			ind[vec[p][i]]--;
			if (ind[vec[p][i]] == 0) qu.push(vec[p][i]);
		}
		if (lt == p) {
			ans++;
			if (!qu.empty())
				lt = qu.back();
		}
	}
	if (cnt == n * (n - 1) / 2)
		cout << ans << E;
	else
		cout << -1 << E;
	//system("pause");
	return 0;
}

Measured memory_bytes: 73728
package main

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

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

func scanString() string { sc.Scan(); return sc.Text() }
func scanRunes() []rune { return []rune(scanString()) }
func scanInt() int { a,_ := strconv.Atoi(scanString()); return a }
func scanInt64() int64 { a,_ := strconv.ParseInt(scanString(),10,64); return a }
func scanFloat64() float64 { a,_ := strconv.ParseFloat(scanString(),64); return a }

func scanInts(n int) []int {
	res := make([]int, n); for i := 0; i < n; i++ { res[i] = scanInt() }; return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

func abs(a int) int { if a<0 { return -a }; return a }
func min(a,b int) int { if a<b { return a }; return b }
func max(a,b int) int { if a>b { return a }; return b }

//•*¨*•.¸¸♪Main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	a := scanInt()
	b := scanInt()

	if a < 9 && b < 9 {
		fmt.Fprintln(wr, "Yay!")
	} else {
		fmt.Fprintln(wr, ":(")
	}
}


Measured memory_bytes: 640
import sys
s = []
for e in sys.stdin:
    if e != "\n":
        s += list(e.lower().replace(" ", ""))
    else:
        break
alfa = [chr(i) for i in range(97, 97+26)]
d = {}
for i in alfa:
    if i in s:
        d[i] = s.count(i)
    else:
        d[i] = 0
for k,v in d.items():
    print("{} : {}".format(k, v))



Measured memory_bytes: 5588