akhauriyash/Code-Regression huggingface dataset:
// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int ll
#define loop(__x, __start, __end) for(Int __x = __start; __x < __end; __x++)
#define loopdown(__x, __start, __end) for(Int __x = __start; __x > __end; __x--)
#define rep(__n) for(Int __x = 0; __x < __n; __x++)
#define span(__a,__x,__y) __a.begin()+__x,__a.begin()+__y
#define span_all(__a) __a.begin(),__a.end()
#define len(__x) (__x.size())
#define last(__x) (__x[__x.size()-1])

using namespace std;

struct Point {
  Int x, y;
  Point(Int x, Int y): x(x), y(y) {}
  Point(): x(0), y(0) {}

  bool operator< (const Point &p1) const {
    return x < p1.x && y < p1.y;
  }
};
ostream & operator << (ostream & out, Point const & v) {
  out << "Point(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Point & v) {
  Int x, y;
  in >> x; in >> y; v.x = x; v.y = y;
  return in;
}

// Geometry

#define EPS 0.0000000001

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (Vector2 v) { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (Vector2 v) { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (double k) { return Vector2(x * k, y * k); }
  Vector2 operator / (double k) { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 v) { return x * v.x + y * v.y; }
  double cross (Vector2 v) { return x * v.y - y * v.x; }
  
  bool operator < (const Vector2 &v) const {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) const {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) { 
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) { 
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}

Int N, t = 1;
vector<vector<Int> > G(101);
vector<Int> D(101, -1), F(101, -1);

void input() {
  cin >> N;
  Int v, c, u;
  rep(N) {
    cin >> v >> c; v--;
    rep(c) {
      cin >> u; u--;
      G.at(v).push_back(u);
    }
  }
}

void dfs(Int n) {
  if (D.at(n) >= 0) return;
  D.at(n) = t++;
  for (auto v: G.at(n)) {
    dfs(v);
  }
  F.at(n) = t++;
  return;
}

void solve() {
  for (int i=0; i<N; i++) dfs(i);
  for (int i=0; i<N; i++) {
    cout << (i+1) << " " << D.at(i) << " " << F.at(i) << endl;
  }
}

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



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

template<class Type>
Type modpow(Type a, Type n, Type mod)
{
	Type res = 1;
	while (0 < n) {
		if (n & 1) {
			res = res * a % mod;
		}
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

template<class Type>
Type gcd(Type x, Type y)
{
	Type r;
	if (x < y) swap(x, y);

	while (0 < y) {
		r = x % y;
		x = y;
		y = r;
	}
	return x;
}

template<class Type>
Type lcm(Type x, Type y)
{
	return x * y / gcd(x, y);
}

template<class Type>
bool is_prime(Type x)
{
	if (x == 2) return true;
	if (x < 2 || x % 2 == 0) return false;

	for (Type i = 3; i <= sqrt(x); i += 2) {
		if (x % i == 0) return false;
	}
	return true;
}

template<class Type>
vector<bool> eratos(Type n)
{
	vector<bool> isPrime(n + 1, true);
	isPrime[0] = isPrime[1] = false;
	for (Type i = 2; i <= n; i++) {
		if (isPrime[i]) {
			Type j = i + i;
			while (j <= n) {
				isPrime[j] = false;
				j = j + i;
			}
		}
	}
	return isPrime;
}

bool binary_search_judge(vector<int> a, int index, int key)
{
	if (key <= a[index]) return true;
	else return false;
}

int binary_search(vector<int> a, int key)
{
	int ng = -1;
	int ok = a.size();
	while (1 < abs(ng - ok)) {
		int mid = (ng + ok) / 2;
		if (binary_search_judge(a, mid, key)) ok = mid;
		else ng = mid;
	}
	return a[ok] == key;
}

pair<int, int> i_to_pair(int x)
{
	int sentou = to_string(x)[0] - '0';
	int matubi = to_string(x)[to_string(x).size() - 1] - '0';
	return make_pair(sentou, matubi);
}

int main()
{
	int n, k, q;
	cin >> n >> k >> q;
	vector<int> score(n, k - q);
	for (int i = 0; i < q; i++) {
		int a;
		cin >> a;
		score[a - 1]++;
	}

	for (auto item : score) {
		if (0 < item) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using edge = struct {int to; ll cost;};

#define mod 1000000007
#define REP(i, n) for (int i = 0; i < n; i++)
#define INF (1 << 29)


void solve() {
    int n, k, r, s, p;
    string t;
    cin >> n >> k >> r >> s >> p >> t;
    ll ans = 0ll;
    vector<char> pre(n);
    for(int i = 1; i <= k; i++){
        switch (t[i-1])
        {
        case 'r':
            ans += (ll)p;
            pre[i-1] = 'p';
            break;

        case 's':
            ans += (ll)r;
            pre[i-1] = 'r';
            break;
        
        case 'p':
            ans += (ll)s;
            pre[i-1] = 's';
            break;
        
        default:
            break;
        }
    }
    for(int i = k+1; i <= n; i++){
        
        switch (t[i-1])
        {
        case 'r':
            if(pre[i-1-k] != 'p'){
                ans += (ll)p;
                pre[i-1] = 'p';
            }
            else {
                pre[i-1] = 'k';
            }
            break;

        case 's':
            if(pre[i-k-1] != 'r'){
                ans += (ll)r;
                pre[i-1] = 'r';
            }
            else {
                pre[i-1] = 'k';
            }
            break;
        
        case 'p':
            if(pre[i-k-1] != 's'){
                ans += (ll)s;
                pre[i-1] = 's';
            }
            else{
                pre[i-1] = 'k';
            }
            break;
        
        default:
            break;
        }
    }
    cout << ans << "\n";
}

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

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define endl '\n'
#define INF (1 << 21)
const int MOD = 1000000009;
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int z = 0, o = 0;
  string s;

  cin >> s;

  for(int i = 0;i < s.size();i++){
    if(s[i] == '1'){
      o++;
    }else{
      z++;
    }
  }

  cout << 2 * min(z, o) << endl;
  return 0;
}



Measured memory_bytes: 512
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;

const int MX = 2019;
int A[MX], B[MX];

int main() {
        cin.sync_with_stdio(0);
      
        string s;
        cin >> s;
        int n = s.length();

        ll ans = 0;

        for (int i = 0; i < n; ++i) {
                int me = s[i] - '0';
                for (int j = 0; j < MX; ++j) {
                        if (A[j] == 0) continue;
                        B[(j * 10 + me) % MX] += A[j];
                }
                B[me]++;
                ans += 1ll * B[0];
                for (int j = 0; j < MX; ++j)
                        A[j] = B[j], B[j] = 0;
        }

        cout << ans << "\n";

        return 0;
}

Measured memory_bytes: 3748
N=int(input())
h=[int(i) for i in input().split()]

ans=0
for i in range(len(h)):
    while h[i] > 0:
        ans+=1

        j=0
        while h[i+j]>0:
            h[i+j]-=1
            j+=1
            if i+j==N:
              break

print(ans)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int N = scan.nextInt();
	scan.close();
	int remainder;
	if((N % 1000) == 0) {
		remainder = 0;
	}
	else {
		remainder = 1000 - N % 1000;
	}
	System.out.println(remainder);
	}
	}

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

typedef pair<char,int>latte;

vector<latte>in(){
    char c;
    int d;
    vector<latte>A;
    while(cin>>c,c!='$'){
        cin>>d;
        A.pb(latte(c,d));
    }
    return A;
}

signed main(){
    vector<latte>A,B,C;
    A=in();B=in();C=in();

    for(int i=0;i+B.size()<=A.size();i++){
        bool ok=true;
        if(A[i].fi!=B[0].fi||A[i].se<B[0].se)ok=false;
        if(A[i+B.size()-1].fi!=B[B.size()-1].fi||A[i+B.size()-1].se<B[B.size()-1].se)ok=false;
        for(int j=1;j+1<B.size();j++)if(A[i+j]!=B[j])ok=false;
        if(!ok)continue;
        A[i].se-=B[0].se;
        if(B.size()>1)A[i+B.size()-1].se-=B[B.size()-1].se;
        for(int j=1;j+1<B.size();j++)A[i+j].se=0;
        A.insert(A.begin()+i+(B.size()>1),all(C));
        break;
    }

    vector<latte>ans;
    rep(i,A.size()){
        if(A[i].se==0)continue;
        if(ans.size()&&ans.back().fi==A[i].fi)ans.back().se+=A[i].se;
        else ans.pb(A[i]);
    }

    rep(i,ans.size())cout<<ans[i].fi<<" "<<ans[i].se<<" ";cout<<"$"<<endl;
    return 0;
}

Measured memory_bytes: 3152
#include <iostream>
#include <cstdio>
#include <cstring>

const int MAXN = 2e5;

int n;
int nxt[MAXN | 1], pre[MAXN | 1], ans[MAXN | 1];
char s[MAXN + 5];

int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = n, lst = 0; i >= 1; --i) {
    if (s[i] == 'L') lst = i;
    else pre[i] = lst;
  }
  for (int i = 1, lst = 0; i <= n; ++i) {
    if (s[i] == 'R') lst = i;
    else nxt[i] = lst;
  }
  for (int i = 1; i <= n; ++i) {
    if (s[i] == 'L') {
      if ((i - nxt[i]) % 2 == 0) ++ans[nxt[i]];
      else ++ans[nxt[i] + 1];
    } else {
      if ((pre[i] - i) % 2 == 0) ++ans[pre[i]];
      else ++ans[pre[i] - 1];
    }
  }
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  return 0;
}


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

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

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

const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

int main(){
    string s;
    int x, y;
    cin >> s >> x >> y;

    vector<int> a, b;
    int cnt = 0;
    for (char &c : s) {
        if (c == 'T') {
            if (a.size() == b.size()) a.push_back(cnt);
            else b.push_back(cnt);
            cnt = 0;
        } else {
            cnt++;
        }
    }
    if (cnt > 0) {
        if (a.size() == b.size()) a.push_back(cnt);
        else b.push_back(cnt);
    }

    unordered_set<int> X;
    X.insert(0);
    rep(i, a.size()) {
        unordered_set<int> res;
        for (const int &nx : X) {
            res.insert(nx+a[i]);
            if (i != 0) res.insert(nx-a[i]);
        }
        X = res;
    }

    unordered_set<int> Y;
    Y.insert(0);
    for (int &i : b) {
        unordered_set<int> res;
        for (const int &ny : Y) {
            res.insert(ny+i);
            res.insert(ny-i);
        }
        Y = res;
    }

    bool ans = X.count(x) && Y.count(y);
    if (ans) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 896
import java.util.*;

public class Main {
    static class UnionFind {
        List<Integer> Parent;
        UnionFind(int N) {
            Parent = new ArrayList<Integer>();
            Integer[] values = new Integer[N];
            Arrays.fill(values, -1);
            Parent.addAll(Arrays.asList(values));
        }
        int root(int A) {
            if (Parent.get(A) < 0)
                return A;
            int root = root(Parent.get(A));
            Parent.set(A, root);
            return root;
        }
        int size(int A) {
            return -Parent.get(root(A));
        }

        boolean connect(int A, int B) {
            A = root(A);
            B = root(B);
            if (A == B) {
                return false;
            }

            if (size(A) < size(B)) {
                int temp = A;
                A = B;
                B = temp;
            }

            Parent.set(A, Parent.get(A) + Parent.get(B));
            Parent.set(B, A);

            return true;
        }
    }
    static class Pair{
        public int x;
        public int y;
        public Pair(int x,int y) {
            this.x=x;
            this.y=y;
        }
        @Override
        public boolean equals(Object obj) {
            if(obj instanceof Pair) {
                Pair other = (Pair) obj;
                return other.x==this.x && other.y==this.y;
            }
            return false;
        }//同値の定義
        @Override
        public int hashCode() {
            return Objects.hash(this.x,this.y);
        }//これ書かないと正しく動作しない（要　勉強）
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int K = Integer.parseInt(sc.next());
        int L = Integer.parseInt(sc.next());
        UnionFind road = new UnionFind(N);
        for (int i=0;i<K;i++) {
            int p = Integer.parseInt(sc.next())-1;
            int q = Integer.parseInt(sc.next())-1;
            road.connect(p, q);
        }

        UnionFind train = new UnionFind(N);
        for (int i=0;i<L;i++) {
            int r = Integer.parseInt(sc.next())-1;
            int s = Integer.parseInt(sc.next())-1;
            train.connect(r, s);
        }

        HashMap<Pair, Integer> map = new HashMap<Pair, Integer>();
        for (int i=0;i<N;i++) {
            int road_r = road.root(i);
            int train_r = train.root(i);
            Pair pair = new Pair(road_r, train_r);
            if (map.containsKey(pair)) {
                map.put(pair, map.get(pair)+1);
            } else {
                map.put(pair, 1);
            }
        }

        for (int i=0;i<N;i++) {
            int road_r = road.root(i);
            int train_r = train.root(i);
            Pair pair = new Pair(road_r, train_r);
            System.out.println(map.get(pair));
        }
    }
}

Measured memory_bytes: 112640
#include <stdio.h>
#include <string.h>
#define N 1046527
#define L 14

char H[N][L];

int getChar(char ch){
  if(ch == 'A') return 1;
  else if(ch == 'C') return 2;
  else if(ch == 'G') return 3;
  else if(ch == 'T') return 4;
  else {
    return 0;
  }
}

long long getKey(char str[]){
  long long sum=0,p=1;
  long long i;

  for(i=0; i<strlen(str); i++){
    sum += p*(getChar(str[i]));
    p*=5;
  }
  return sum;
}

int h1(int key){
  return key % N;
}

int h2(int key){
  return 1 + (key % (N-1));
}

int find(char str[]){
  long long key,i,h;
  key = getKey(str);
  for(i=0; ; i++){
    h = (h1(key) + i * h2(key)) % N;
    if(strcmp(H[h],str) == 0) return 1;
    else if(strlen(H[h]) == 0) return 0;
  }
  return 0;
}

int insert(char str[]){
  long long key,i,h;
  key = getKey(str);
  for(i=0; ; i++){
    h = (h1(key) + i * h2(key)) % N;
    if(strcmp(H[h],str) == 0) return 1;
    else if(strlen(H[h]) == 0){
      strcpy(H[h],str);
      return 0;
    }
  }
  return 0;
}

int main(){
  int i,n,h;
  char str[L],com[9];

  for(i=0; i<N; i++){
    H[i][0] = '\0';
  }
  scanf("%d",&n);

  for(i=0; i<n; i++){
    scanf("%s %s",com,str);

    if(com[0] == 'i'){
      insert(str);
    }
    else {
      if(find(str)){
        printf("yes\n");
      }
      else {
        printf("no\n");
      }
    }
  }
  return 0;
}



Measured memory_bytes: 16068
#include<iostream>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> P;

char str[100];

int keta(int n){
  int i;
  int a=1;
  rep(i,n)
    a*=10;

  return a;
}

int main()
{
  int i,j,k;
  int sum=0;

  while(scanf("%s",str)!=EOF){
    rep(i,strlen(str))
      if(str[i]>='0' && str[i]<='9'){
	rep(j,strlen(str)-i)
	  if(str[i+j]<'0' || str[i+j]>'9')
	    break;
	j--;
	rep(k,j+1)
	  sum+=(str[i+j-k]-'0')*keta(k);
	i+=j;
      }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 1156
w = sorted(input())
n = len(w)
a = 0
t = list()
for i in range(n - 1):
    if w[i] == w[i + 1]:
        a += 1
    else:
        t.append(a)
        a = 0
t.append(a)
for i in range(len(t)):
    if t[i] % 2 == 0:
        a = -1
if a == -1:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 3064
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
char nxc(char c){
  if(c=='z')return 'a';
  else return c+1;
}

int main(){
  int n;
  while(cin>>n,n){
    string s;
    cin>>s;
    int va[101],vb[101];
    REP(i,n){
      cin>>va[i]>>vb[i];
      va[i]--;vb[i]--;
    }
    for(int i = n-1; i >= 0; i--){
      int a = va[i];
      int b = vb[i];
      int d = abs(a-b);
      swap(s[a],s[b]);
      REP(i,d)s[a] = nxc(s[a]);
      REP(i,d)s[b] = nxc(s[b]);
    }
    cout<<s<<endl;
  }

  return 0;
}

Measured memory_bytes: 0
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.sql.Array;
import java.util.*;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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


    static class TaskD {
        public int log(long a){
            int num = 0;
            while (a > 0){
                num++;
                a>>=1;
            }
            return num;
        }
        public long binerypow(long a){
            if (a == 0) return 1;
            long v = binerypow(a/2);
            return v*v*(a%2==1?2:1);
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            long ans = 0;
            int n = in.nextInt();
            int max = 1;
            long[] arr = new long[n];
            for (int i = 0; i <n ; i++) {
                arr[i] = in.nextLong();
                int v = log(arr[i]);
                if (v>max)max=v;
            }
            long [] zero = new long[max];
            long  [] one = new long[max];
            for (int i = 0; i <n; i++){
                int j = 0;
                while (j<max){
                    if ((arr[i]&1) == 1) one[j]++;
                    else zero[j]++;
                    arr[i]>>=1;
                    j++;
                }
            }

            for (int i = 0; i <max; i++) {
                if (zero[i]*one[i] > 0){
                    ans+=(((one[i]*zero[i])%1000000007)*((binerypow(i))%1000000007))%1000000007;
                    ans%=(1000000000+7);
                }
            }
            System.out.println(ans);

        }



    }

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

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

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

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}


Measured memory_bytes: 82716
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <stack>
using namespace std;
#define FI(n) FastIO::read(n)
namespace FastIO{
    const int SIZE  = 1<<16;
    char buf[SIZE] , obuf[SIZE] , str[60];
    int bi = SIZE , bn = SIZE , opt;
    int read(char *s){
        while( bn ){
            for(;bi<bn && buf[bi] <= ' ';bi++);
            if( bi < bn )   break;
            bn = fread(buf,1,SIZE,stdin);
            bi = 0;
        }
        int sn = 0;
        while( bn ){
            for(;bi<bn && buf[bi] > ' ';bi++)   s[sn++] = buf[bi];
            if( bi < bn )   break;
            bn = fread(buf,1,SIZE,stdin);
            bi = 0;
        }
        s[sn] = 0;
        return sn;
    }
    bool read(int& x){
        int n = read(str) , bf;
        if(!n)  return 0;
        int i = 0;
        if( str[i] == '-' ) bf = -1 , i++;
        else bf = 1;
        for(x = 0 ; i < n ; i++)    x = x*10 + str[i] - '0';
        if( bf < 0 )    x = -x;
        return 1;
    }
};
typedef long long LL;
const int N = 1e6+7 , INF = 0x3f3f3f3f , mz = 1e9+7;
const double PI = acos(0.0) * 2;
template<typename T1>
T1 gcd(T1 a , T1 b){ return b ? gcd(b,a%b) : a;}

int p[N];

int main(){
#ifdef LOCAL
    freopen("F:\\c++\\in.txt", "r", stdin);
//  freopen("F:\\c++\\out1.txt","w",stdout);
#endif
    int n,cnt = 0;
    FI(n);
    for(int i = 1 ; i <= n ; i++)
        FI(p[i]);
    for(int i = 1 ; i < n ; i++){
        if( p[i] == i ){
            swap(p[i],p[i+1]);
            cnt++;
        }
    }
    if( p[n] == n ){
        cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}


Measured memory_bytes: 640
import math


def main():
    n = int(input())
    a = int(input())
    b = int(input())
    c = int(input())
    d = int(input())
    e = int(input())

    l = [n, 0, 0, 0, 0, 0]
    time = 0

    move_a = a
    move_b = min(move_a, b)
    move_c = min(move_b, c)
    move_d = min(move_c, d)
    move_e = min(move_d, e)

    time = math.ceil(n / move_e) + 4

    print(time)


'''
    while True:
        move_a = min(a, l[0])
        move_b = min(b, l[1])
        move_c = min(c, l[2])
        move_d = min(c, l[3])
        move_e = min(c, l[4])

        l[0] -= move_a
        l[1] += move_a
        l[1] -= move_b
        l[2] += move_b
        l[2] -= move_c
        l[3] += move_c
        l[3] -= move_d
        l[4] += move_d
        l[4] -= move_e
        l[5] += move_e

        time += 1
        if l[5] >= n:
            break

    print(time)
'''

'''
    0: [n-a, a, 0, 0, 0, 0]
    1: [n-2a,2a-b, b, 0, 0, 0]
    2: [n-3a,3a-2b, 2b-c, c, 0, 0]
    3: [n-4a, 4a-3b, 3b-2c, 2c-d, d, 0]
    4: [n-5a, 5a-4b, 4b-3c, 3c-2d, 2d-e, e]
    5: [n-6a, 6a-5b, 5b-4c, 4c-3d, 3d-2e, 2e]
    6: [n-7a, 7a-5b, 6b-5c, 5c-4d, 4d-3e, 3e]

    v1: 全員が0->1に移動する: math.ceil(n/a)
    v2: 全員が1->2に移動する: math.ceil(n/min(v1, b))
    v3: 2->3: math.ceil

'''


if __name__ == "__main__":
    main()


Measured memory_bytes: 62396
#include <bits/stdc++.h>
using namespace std;
const int dx[] = {-1, 0, 1, 0, 0};
const int dy[] = {0, -1, 0, 1, 0};

struct STATE { int ax, ay, bx, by, d; };

char grid[32][32];
bool done[32][32][32][32][16];

int main()
{
	int h, w;
	while (scanf("%d %d", &h, &w), h + w){
		memset(grid, '*', sizeof(grid));
		memset(done, false, sizeof(done));
		STATE s = {0, 0, 0, 0, 0};
		
		for (int i = 1; i <= h; i++){
			for (int j = 1; j <= w; j++){
				scanf(" %c", &grid[i][j]);
				if (grid[i][j] == 'A'){
					s.ax = i;
					s.ay = j;
					grid[i][j] = '.';
				}
				else if (grid[i][j] == 'B'){
					s.bx = i;
					s.by = j;
					grid[i][j] = '.';
				}
			}
		}
		
		/*
		for (int i = 1; i <= h; i++){
			for (int j = 1; j <= w; j++){
				printf("%c", grid[i][j]);
			}
			cout << endl;
		}
		*/
		
		string pa;
		cin >> pa;
		for (int i = 0; i < pa.size(); i++){
			if (pa[i] == '5') pa[i] = 4;
			else if (pa[i] == '8') pa[i] = 0;
			else if (pa[i] == '6') pa[i] = 3;
			else if (pa[i] == '4') pa[i] = 1;
			else if (pa[i] == '2') pa[i] = 2;
		}
		
		STATE res = {0, 0, 0, 0, -1};
		queue<STATE> que;
		for (que.push(s); que.size(); que.pop()){
			STATE st = que.front();
			
			//printf("%d %d %d %d\n", st.ax, st.ay, st.bx, st.by);
			
			if (done[st.ax][st.ay][st.bx][st.by][st.d % pa.size()]){
				continue;
			}
			done[st.ax][st.ay][st.bx][st.by][st.d % pa.size()] = true;
			if (st.ax == st.bx && st.ay == st.by){
				res = st;
				break;
			}
			
			
			int tbx = st.bx + dx[pa[st.d % pa.size()]];
			int tby = st.by + dy[pa[st.d % pa.size()]];
			if (grid[tbx][tby] == '*'){
				tbx = st.bx;
				tby = st.by;
			}
			for (int dir = 0; dir < 5; dir++){
				int tax = st.ax + dx[dir];
				int tay = st.ay + dy[dir];
				if (grid[tax][tay] != '.') continue;
				que.push({tax, tay, tbx, tby, st.d + 1});
			}
		}
		
		if (res.d == -1) cout << "impossible" << endl;
		else cout << res.d << " " << res.ax - 1 << " " << res.ay - 1 << endl;
	}
	
	return 0;
}

Measured memory_bytes: 17680
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

// #include <bits/extc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp> // tree
// #include <ext/pb_ds/hash_policy.hpp> // hash
// #include <ext/pb_ds/trie_policy.hpp> // trie
// #include <ext/pb_ds/priority_queue.hpp> // priority_queue
// using namespace __gnu_pbds;

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define Push push_back

using lli = long long;
using pll = pair<lli, lli>;
using Double = long double;
template<typename T>
using priority = priority_queue<T>;

const lli mod = 1E9 + 7;
const Double PI = 3.1415926535846;
const Double eps = 1e-8;

lli fastPow(lli base, lli exp, lli module = mod) {
	lli ans = 1;
	base %= module;
	while (exp) {
		if (exp & 1) ans = ans * base % module;
		base = base * base % module;
		exp >>= 1;
	}
	return ans;
}

bool millerRabin(lli n, lli a) {
	if (n < 2 or n % 2 == 0) return n == 2;
	lli u, t;
	for (u = n-1, t = 0; u & 1; u >>= 1, ++t);
	a = fastPow(a, u, n);
	if (a == 1 or a == n - 1) return true;
	for (int i = 0; i < t; ++i) {
		a = a * a % n;
		if (a == 1) return false;
		if (a == n - 1) return true;
	}
	return false;
}

lli n, k;
lli GetNum(lli block, lli x) {
	return k + block * n + x;
}

void solve() {
	cin >> n >> k;
	
	if (2 * k > n + 1) {
		cout << -1 << "\n";
		return;
	}
	
	if (n % 2 == 0) {
		for (int i = 0; i < n/2; ++i) {
			cout << GetNum(0, n / 2 + i) << " " << GetNum(1, n - 1 - 2 * i) << " " << GetNum(2, n - i - 1) << "\n";
		}
		for (int i = 0; i < n/2; ++i) {
			cout << GetNum(0, i) << " " << GetNum(1, n - 2 - 2 * i) << " " << GetNum(2, n / 2 - i - 1) << "\n";
		}
		return;
	}
	
	lli tmpk = k;
	k = (n + 1) / 2;
	lli s = k - tmpk;
	
	set<int> check;
	int check1[n][2];
	for (int i = 0; i < n; ++i) {
		check1[i][0] = GetNum(1, (2 * (n - i) - 1) % n);
		check1[i][1] = GetNum(2, n - i - 1) - check1[i][0];
		if (check1[i][1] < k or check1[i][1] >= k + n) break;
		check.insert(check1[i][0]);
		check.insert(check1[i][1]);
	}
	
	if (check.size() == 2 * n) {
		for (int i = 0; i < n; ++i) {
			cout << check1[i][0] - s << " " << check1[i][1] - s << " " << GetNum(2, n - i - 1) - s << "\n";
		}
		return;
	}
	
	check.clear();
	
	for (int i = 0; i < n; ++i) {
		check1[i][0] = GetNum(1, (2 * (n - i) - 2) % n);
		check1[i][1] = GetNum(2, n - i - 1) - check1[i][0];
		if (check1[i][1] < k or check1[i][1] >= k + n) break;
		check.insert(check1[i][0]);
		check.insert(check1[i][1]);
	}
	
	if (check.size() == 2 * n) {
		for (int i = 0; i < n; ++i) {
			cout << check1[i][0] - s << " " << check1[i][1] - s << " " << GetNum(2, n - i - 1) - s << "\n";
		}
		return;
	}
}

int main() {
	int t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 12416
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define all(A) A.begin(),A.end()
typedef long long ll;

int main(){
  int h,w;
  cin >> h >> w;
  int k;
  cin >> k;
  vector<vector<char>> maze(h,vector<char>(w));
  int black = 0;
  rep(i,h){
    rep(j,w){
      cin >> maze[i][j];
      if(maze[i][j] == '#') black ++;
    }
  }
  int ans = 0;
  rep(i,pow(2,h)){//縦を全探索
    rep(j,pow(2,w)){//横を全探索
      int tmp = 0;//各ケースのtemp
      rep(p,h){//縦を操作
        rep(q,w){//横を操作
          bool hbit = (i>>p)&1;
          if (hbit) continue;
          bool wbit = (j>>q)&1;
          if (wbit) continue;
          if (maze[p][q] == '#') tmp++;
        }//w
      }//p
      if (tmp == k) ans++;
    }//j
  }//i
  cout << ans << endl;
}

Measured memory_bytes: 4096
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
		ArrayList<Integer> one = nextIntArray();
		one = nextIntArray();
		myout((one.get(1) == 1) ? 1 : 0);
	}
	//Method addition frame start



	//Method addition frame end
}


Measured memory_bytes: 32916
while s = gets.chop do
  break if s == ""

  x1, y1, x2, y2, x3, y3, xp, yp = s.split.map(&:to_f)
  gx, gy = (x1 + x2 + x3) / 3, (y1 + y2 + y3) / 3

  def c(x1, y1, x2, y2, x, y)
    (y2 - y1) * (x - x1) - (x2 - x1) * (y - y1)
  end

  r1 = c(x1, y1, x2, y2, gx, gy) * c(x1, y1, x2, y2, xp, yp) > 0
  r2 = c(x2, y2, x3, y3, gx, gy) * c(x2, y2, x3, y3, xp, yp) > 0
  r3 = c(x3, y3, x1, y1, gx, gy) * c(x3, y3, x1, y1, xp, yp) > 0

  puts r1 && r2 && r3 ? 'YES' : 'NO'
end

Measured memory_bytes: 2372
#include<stdio.h>

int main(){
 while(1){
  int H,W;
  scanf("%d%d", &H,&W);
  if(H==0 && W==0){break;}
  int i,j;
  for(i=0; i<H; i++){
   for(j=0; j<W; j++){
    if(i==0 || i==H-1 || j==0 || j==W-1){printf("#");}
    else{printf(".");}
   }
   printf("\n");
  }
  printf("\n");
 }
 return 0;
}

Measured memory_bytes: 572
#include<stdio.h>
#define X 1000000007

int res(int k){
    int i,r = 1;
    for(i = k;i >= 1;i--){r*=2;r%=X;}
    return r;
}

int main(void){
    int n,a[131072]={0},i,d,r;
    scanf("%d",&n);
    for(i = 1;i <= n;i++){scanf("%d",&d);a[d]++;}
    if(n%2){
        if(a[0] != 1){printf("0\n");return 0;}
        for(i = 2;i <= (n-1);i+=2){
            if(a[i] != 2){printf("0\n");return 0;}
        }
        r = res((n-1)/2);
        printf("%d\n",r);
    }
    else{
        for(i = 1;i <= (n-1);i+=2){
            if(a[i] != 2){printf("0\n");return 0;}
        }
        r = res((n/2));
        printf("%d\n",r);
    }
    return 0;
}

Measured memory_bytes: 640
#define _GLIBCXX_DEBUG //test only

#include<bits/stdc++.h>
using namespace std;

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
#define INF 1020304050

int main()
{
  int n;
  cin >> n;
  vector<int> x(n-1);
  vector<int> y(n-1);
  int i;
  rep(i,n-1)
  {
    cin >> x[i] >> y[i];
    x[i]--;
    y[i]--;
  }
  vector<vector<int>> e(n);
  rep(i,n-1)
  {
    e[x[i]].emplace_back(y[i]);
    e[y[i]].emplace_back(x[i]);
  }
  vector<int> root(n,-1);
  stack<int> st;
  queue<int> q;
  queue<int> q2;
  vector<int> grundy(n,0);
  q.push(0);
  while(!q.empty())
  {
    while(!q.empty())
    {
      int now = q.front();
      q.pop();
      rep(i,e[now].size())
      {
        int to = e[now][i];
        if(to != 0 && root[to] == -1)
        {
          root[to] = now;
          q2.push(to);
          st.push(to);
        }
      }
    }
    while(!q2.empty())
    {
      q.push(q2.front());
      q2.pop();
    }
  }
  while(!st.empty())
  {
    int now = st.top();
    st.pop();
    if(e[now].size()==1)
    {
      grundy[now] = 1;
    }
    else
    {
      int kg = 0;
      rep(i,e[now].size())
      {
        int from = e[now][i];
        if(from == root[now]) continue;
        kg = kg^grundy[from];
      }
      grundy[now] = kg+1;
    }
  }
  int judge = 0;
  rep(i,e[0].size())
  {
    judge = judge^grundy[e[0][i]];
  }
  if(judge == 0)
  {
    cout << "Bob" << endl;
  }
  else
  {
    cout << "Alice" << endl;
  }
  
}


Measured memory_bytes: 14012
#include<stdio.h>

int main()
{

  int x , y ;

  scanf("%d %d",&x , &y);

  while(x >0 && y>0)
    {
      if(x >= y) x = x-y;
      else y = y-x;
      //printf("x = %d   y = %d\n",x,y);
    }
  if(x >0)printf("%d\n",x);
  if(y >0)printf("%d\n",y);

}



Measured memory_bytes: 2136
#include<bits/stdc++.h>
#define ll long long
#define mod (ll)1000000007
using namespace std;
int n,m;
char grid[1002][1002];
int dp[1002][1002];

int rec(int i, int j)
{
	if(i < 0 || j < 0)
		return 0;
	if(i == 0 && j == 0)
		return 1;
	if(dp[i][j]!=-1)
		return dp[i][j];
	if(grid[i][j] == '#')
		return dp[i][j] = 0;
	else
	{
		dp[i][j] = (rec(i-1,j)%mod + rec(i,j-1)%mod)%mod;
	}

	return dp[i][j];
}
int main()
{
	// int n,m;
	cin>>n>>m;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin>>grid[i][j];

	memset(dp,-1,sizeof(dp));

	cout<<rec(n-1,m-1)<<"\n";
	
	// for(int i = 0; i < n; i++){
	// 	for(int j = 0; j < m; j++)
	// 		cout<<dp[i][j]<<" ";
	// 	cout<<"\n";
	// }
	return 0;
}


Measured memory_bytes: 5248
#AGC002B
n,m=map(int,raw_input().split())
a=[1 for _ in xrange(n)]
r=[0 for _ in xrange(n)]
r[0]=1
for i in xrange(m):
 x,y=map(int,raw_input().split())
 x-=1
 y-=1
 a[x]-=1
 a[y]+=1
 if r[x]==1: r[y]=1
 if a[x]==0: r[x]=0
 
print sum(r)


Measured memory_bytes: 4328
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    a[i]--;
  }
  vector<ll> cnt(n);
  for (int i = 0; i < n; ++i) {
    cnt[a[i]]++;
  }
  ll sum = 0;
  for (int i = 0; i < n; ++i) {
    sum += max(0ll, cnt[i] * (cnt[i] - 1) / 2);
  }
  for (int k = 0; k < n; ++k) {
    ll num = a[k];
    ll res = sum;
    res -= max(0ll, cnt[num] * (cnt[num] - 1) / 2);
    res += max(0ll, (cnt[num] - 1) * (cnt[num] - 2) / 2);
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 5632
import java.io.File;
import java.io.IOException;
import java.util.Scanner;

public class Main {

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

		Scanner scan = new Scanner(System.in);
		// Scanner scan = new Scanner(new
		// File("D:\\UserArea\\J0124567\\Downloads\\ALDS1_6_A-in9.txt"));

		int n = scan.nextInt();
		Tree t = new Tree(n);

		for (int i = 0; i < n; i++) {
			int id = scan.nextInt();
			t.setLeftChild(id, scan.nextInt());
			t.setRightChild(id, scan.nextInt());
		}

		for (int i = 0; i < n; i++)
			t.printR(i);

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

class Tree {
	private class Node {
		int Parent = -1;
		int LeftChild = -1;
		int RightChild = -1;

		public int getDepth() {
			if (Parent == -1)
				return 0;
			else
				return (node[Parent].getDepth() + 1);
		}

		public String getType() {
			if (Parent == -1)
				return "root";
			else if (LeftChild == -1 && RightChild == -1)
				return "leaf";
			else
				return "internal node";
		}

		public int getSib(int id) {
			if (Parent == -1)
				return -1;
			else if (node[Parent].LeftChild == id)
				return (node[Parent].RightChild);
			else
				return (node[Parent].LeftChild);
		}

		public int getDegree() {
			int r = 2;
			if (LeftChild == -1)
				r--;
			if (RightChild == -1)
				r--;
			return r;
		}

		public int getHeight() {
			if (getDegree() == 0)
				return 0;
			int l = 0, r = 0;
			if (LeftChild != -1)
				l = node[LeftChild].getHeight();
			if (RightChild != -1)
				r = node[RightChild].getHeight();
			return Math.max(l, r) + 1;
		}
	}

	private Node[] node;

	public Tree(int n) {
		node = new Node[n];
		for (int i = 0; i < n; i++) {
			node[i] = new Node();
		}
	}

	public void setRightChild(int id, int c) {
		node[id].RightChild = c;
		if (c != -1)
			node[c].Parent = id;
	}

	public void setLeftChild(int id, int c) {
		node[id].LeftChild = c;
		if (c != -1)
			node[c].Parent = id;
	}

	public void printR(int id) {
		System.out.println("node " + id + ": parent = " + node[id].Parent + ", sibling = " + node[id].getSib(id)
				+ ", degree = " + node[id].getDegree() + ", depth = " + node[id].getDepth() + ", height = "
				+ node[id].getHeight() + ", " + node[id].getType());
	}
}

Measured memory_bytes: 26444
def solve():
    s = input()
    n = len(s)

    left = 0
    right = n - 1

    ret = 0
    while left < right:
        if s[left] == s[right]:
            left += 1
            right -= 1
        elif s[left] == 'x':
            ret += 1
            left += 1
        elif s[right] == 'x':
            ret += 1
            right -= 1
        else:
            return -1
    return ret


print(solve())


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#include <map>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
typedef long long ll;

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(){
    string S,T,U;
    ll A,B;
    cin >> S>>T>>A>>B>>U;
    if(U==S){
        A -= 1;
    }
    else{
        B -= 1;
    }
    cout << A << ' ' << B << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
    int n, W; cin >> n >> W;
    long long dp[100100] = {};
    dp[0] = 0;
    while (n--) {
        int w, v; cin >> w >> v;
        for (int u = W-w; u >= 0; u--)
            dp[u+w] = max(dp[u+w], dp[u] + v);
    }
    cout << *max_element(dp, dp+W+1) << endl;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
    long long int a,b,c,count = 0;
    scanf("%lld%lld%lld",&a,&b,&c);
    count = b/c - a/c;
    if (a%c == 0)  {
        count++;
    }
    printf("%lld\n",count);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1e9;

using namespace std;

using ll = long long;

int main()
{
    int N,K;
    cin >> N >> K;
    int ans = 1;
    for(int i = 0; i < N; ++i){
        if(ans+K < ans*2)
            ans+=K;
        else
            ans*=2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define re register
#define LL long long
#define MOD 998244353
#define MAXN 200005
using namespace std;
int n,k,ans,a[MAXN],q1[MAXN],q2[MAXN],pos1[MAXN],pos2[MAXN],mx[MAXN],mn[MAXN];
int hd1=1,hd2=1,tail1=0,tail2=0;
LL rd(){
	LL x=0,tp=1;char c;
	c=getchar();
	while(c<'0' || c>'9'){if(c=='-')tp=-1;c=getchar();}
	while(c>='0' && c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*tp;
}
void pt1(int val,int pos,int lim){
	// while(hd1<=tail1 && pos1[hd1]<=lim)hd1++;
	while(hd1<=tail1 && q1[tail1]>val)tail1--;
	q1[++tail1]=val;
	pos1[tail1]=pos;
	while(hd1<=tail1 && pos1[hd1]<=lim)hd1++;
}
void pt2(int val,int pos,int lim){
	// while(hd2<=tail2 && pos2[hd2]<=lim)hd2++;
	while(hd2<=tail2 && q2[tail2]<val)tail2--;
	q2[++tail2]=val;
	pos2[tail2]=pos;
	while(hd2<=tail2 && pos2[hd2]<=lim)hd2++;
}
int main(){
	// freopen("sb.in","r",stdin);
	// freopen("sb.out","w",stdout);
	n=rd(),k=rd();
	for(int i=1;i<=n;i++)a[i]=rd();
	for(int i=1;i<k;i++){
		pt1(a[i],i,i-k);//min
		pt2(a[i],i,i-k);//max
	}
	bool shit=1;
	for(int i=k;i<=n;i++){
		pt1(a[i],i,i-k);
		pt2(a[i],i,i-k);
		mn[i]=q1[hd1];
		mx[i]=q2[hd2];
		if(mn[i-1]==a[i-k] && mx[i]==a[i] && i>k)continue;
		if(tail1-hd1+1==k){
			ans+=shit;
			shit=0;
			continue;
		}
		// printf("i=%d: %d %d %d %d   len=%d\n",i,a[i-k],q1[hd1],q2[hd2],a[i],tail1-hd1+2);
		ans++;
	}
	printf("%d\n",ans);
	// int tmp[MAXN];
	// for(int i=k;i<=n;i++){
	// 	for(int j=1;j<=n;j++)tmp[j]=a[j];
	// 	sort(tmp+i-k+1,tmp+i+1);
	// 	for(int j=1;j<=n;j++)printf("%d ",tmp[j]);
	// 	printf("\n");
	// }
	return 0;
}


Measured memory_bytes: 5248
from collections import defaultdict, deque

N, M = map(int, input().split())
e = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    e[(a, 0)].append((b, 1))
    e[(a, 1)].append((b, 2))
    e[(a, 2)].append((b, 0))

S, T = map(int, input().split())

d = deque()
d.appendleft((S, 0))

inf = float('inf')
dist = defaultdict(lambda: inf)
dist[(S, 0)] = 0

while d:
    next_node = d.pop()
    for v in e[next_node]:
        if(dist[v] > dist[next_node] + 1):
            dist[v] = dist[next_node] + 1
            if(v == (T, 0)):
                break
            d.appendleft(v)

ans = dist[(T, 0)]
if(ans == inf):
    print(-1)
else:
    print(ans//3)



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

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

using namespace std;

using ll = long long;
using P = pair<int , int>;
  
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int a; cin >> a;
  int l, r; l = a/100; r = a%100;

  if(l>=1 && l<=12) {
    if(r>=1 && r<= 12) {
      cout << "AMBIGUOUS";
    } else {
      cout << "MMYY";
    }
  } else {
    if(r>=1 && r <= 12) {
      cout << "YYMM";
    } else {
      cout << "NA";
    }
  }
}


Measured memory_bytes: 256
#include <cstdio>
using namespace std;
int main() {
    int n, t, sum;
    for (; ;) {
        scanf("%d", &n);
        if (n == 0) break;
        sum=0;
        n /= 4;
        for (int i = 0; i < n; i++){
            scanf("%d", &t);
            sum+=t;
        }
        printf("%d\n", sum);
    }
}



Measured memory_bytes: 2568
def main():
    n =int( input())

    cnt=dict()
    
    for _ in range(n):
        s=input()
        if s in cnt:
            cnt[s]+=1
        else :
            cnt[s]=1
    #print(cnt)
    
    num = 0
    res =[]
    for key,value in cnt.items():
        #print(key,":::",value)
        if value > num:
            num=value
            res=[]
            res.append(key)

        elif value==num:
            res.append(key)

    #print("res::",res)

    
    #a = [k for k, v in cnt.items() if v == max(cnt.values())]


    #print("結果発表：：：：",len(res))
    res.sort()
    for elm in res:
        print(elm)


main()



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

using namespace std;

int main()
{
    /*1
    freopen("flat.in", "r", stdin);
    freopen("flat.out", "w", stdout);
    */
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n;
    cin>>n;
    if(n%2==0){
        cout<<n<<endl;
    }
    else{
        cout<<n*2<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
/* Author : Aaryan Srivastava ^__^ */ 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define pb push_back
#define popb pop_back
#define mt make_tuple 
#define eb emplace_back
#define mp make_pair
#define ff first
#define ss second 
#define ull unsigned long long  
#define pii pair<int, int>
#define piii pair<int,pii>
#define beg begin
#define rep(i,n) for(int (i) = 0 ; i < (n) ; i++)
#define repA(i,x,y) for(int i = (x) ; i <= (y) ; i++)
#define repD(i,x,y) for(int i = (x) ; i >= (y) ; i--)
#define all(c) (c).begin(),(c).end()
#define fill(a,val) memset(a,val,sizeof(a))
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define int ll
using ll = long long;
const int N = 3*1e5 +5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e18 ;
const int SZ = 101 ;
const double eps = 1e-9 ;
using namespace __gnu_pbds;
using namespace std;
using ordered_set =  tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ;

#ifdef AaryanS
#define mycout cout
#define mycerr cerr 
#endif

#ifndef AaryanS
#define mycout if(false) cout
#define mycerr if(false) cerr
#endif


void solve()
{
    int n , m ;
    cin >> n>> m ;
    vector<int> a(n) ;
    vector<pii> kx ;
    rep(i,n) cin >> a[i] , kx.eb(a[i],1) ;
    rep(i,m){
        int x,c ;
        cin >> c >> x ;
        kx.eb(x,c) ;
    }
    sort(all(kx)) ;
    reverse(all(kx)) ;
    int ans = 0, cur = 0 ;
    for(auto it : kx){
        if(cur >= n)
            break ;
        // cout << it.ff << " " << it.ss << endl ;
        if(it.ss + cur  > n)
            ans += (n-cur)*it.ff , cur = n;
        else
            ans +=  it.ss*it.ff ;
        cur += it.ss ;
    }
    cout << ans ;
}   

     
int32_t main(int32_t argc, char *argv[])
{
    double t1 = clock() ;
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    int TC = 1, t = 0;
    //cin >> TC ;
    while(t++ < TC)
    {
        //cout << "Case #" << t << ": " ;
        solve();
        //cout << endl ;
    }
    mycerr << "Time : " << 1000 *(clock() - t1)/CLOCKS_PER_SEC << " ms\n" ;
    return 0;
}

Measured memory_bytes: 7024
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n = 0;
  cin >> n;
  vector<double> guzai(n,0);
  for(int i = 0; i < n; i++){
    cin >> guzai[i];
  }
  sort(guzai.begin(), guzai.end()); 
  for(int i = 0; i < n-1; i++){
    guzai[i+1] = (guzai[i]+guzai[i+1])/2;
  }
  cout << guzai[n-1];
}

Measured memory_bytes: 256