akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#define MAX 500000
#define SENTINEL 1000000000
int  A[MAX];
 int count = 0 ;
void Merge(int, int, int);

void Merge_Sort(int, int);

main(){
  int n;
  int i;
  int left, mid, right;
 
  scanf("%d", &n);

  for(i = 0; i < n; i++){
    scanf("%d", &A[i]);
    // printf("%d ", A[i]);
  }
  //printf("\n");
  
  
  left = 0;
  right = n;
  Merge_Sort(left, right);
 
 for(i = 0; i < n; i++){
   printf("%d", A[i]);
   if(i != n-1)printf(" ");
 }
 printf("\n%d\n", count);
 return 0;
}

void Merge(int left, int mid, int right){
  int n1, n2;
  int i, j, k;
  n1 = mid - left;
  n2 = right - mid;
  int L[n1+1],  R[n2+1];

  for (i = 0; i < n1; i++){
    L[i] = A[left+i];

  }
  
  for (i = 0; i < n2; i++){
    R[i] = A[mid+i];

  }
  
  L[n1] = SENTINEL;
  R[n2] = SENTINEL;
  
  i = 0;
  j = 0;
  
  for(k = left; k < right; k++){
    count++;
    if(L[i] <= R[j])
      {
	A[k] = L[i];
	i++;
      }
  
    else
      { 
	A[k] = R[j];
	j++;
      }
  }
}
  
void Merge_Sort(int left, int right){
  int mid; 
  if(left+1 < right)
    { 
      mid = (left + right)/2;
      Merge_Sort(left, mid);
      Merge_Sort(mid, right);
      Merge(left, mid, right);
    }
}

Measured memory_bytes: 4504
#include <bits/stdc++.h>
#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(abs(c-a)<=d) cout<<"Yes"<<endl;
    else if(abs(b-a)<=d&&abs(c-b)<=d) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(60):
    cnt = 0
    for j in range(N):
        cnt += (A[j]>>i)&1
    ans = (ans+(((N-cnt)*cnt)%mod)*2**i)%mod
print(ans)

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

using namespace std;

#define INF 1e9
#define MAXN 100005
#define MAXM 100005
#define MOD 1000000007
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pii pair<int, int>

ll A,B,C,K,cnt=0;
bool flag;

void solve(){
    
    while(B <= A){
        B *= 2;
        cnt++;
    }

    while(C <= B){
        C *= 2;
        cnt++;
    }

    if(cnt <= K) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int main(){
    cin >> A >> B >> C >> K;

    solve();
}


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

#define fi first
#define se second
#define FO(x, n) for (int x = 0; x < n; ++x)
#define FOR(x, a, b) for (int x = a; x < b; ++x)
#define RFO(x, n) for (int x = n - 1; x >= 0; --x)
#define RFOR(x, a, b) for (int x = b - 1; x >= a; --x)
#define FOR_ITER(x, a) for(auto x = a.begin(); x != a.end(); ++x)



using namespace std;
typedef unsigned char byte;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<string, string> pss;
typedef pair<ll, ll> pll;
inline bool feq(const double& a, const double& b) { return fabs(a - b) < 1e-10; }

using namespace std;


int main(){
//    int n, l;
//    cin >> n >> k;
//    vector<bool> dislike(10, false);
//
//    FOR(i, 0, k) {
//        int t;
//        cin >> t;
//        dislike[t] = true;
//    }




int n;
string s;
cin >>n>>s;
int x = 0;
int xmax = x;


FO(i, n) {
    if('I' == s.at(i)) {
        ++x;

    }else{
        --x;
    }
    xmax=max(xmax,x);
}
cout << xmax<< endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define ll long long int
#define pb push_back
#define mp make_pair

using namespace std;

int main(){

    int n;
    cin >> n;

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

    ll ans = 0;
    map<string,int> m;

    for(int i=0;i<n;i++){
        sort(vec[i].begin(),vec[i].end());
        ans += m[vec[i]]++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 18176
import scala.io.StdIn

object Main extends App {
  val Array(x,k,d):Array[Long] = StdIn.readLine().split(' ').map(_.toLong)
  val stepToZeroNbhd = math.abs(x / d)
  val ans =
    if(stepToZeroNbhd >= k)
      x - math.signum(x)*d*k
    else{
      val x2=x - math.signum(x)*d*stepToZeroNbhd
      val kRemaining=k-stepToZeroNbhd
      if(kRemaining % 2 == 0 )
        x2
      else {
        val sgn = if(x2==0) 1 else math.signum(x2)
        x2 - sgn*d
      }
    }

  println(math.abs(ans))

}








Measured memory_bytes: 54772
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    string ans = "~";
    for(int i=0; i<=n-m; ++i){
        bool ok = true;
        string s2 = s;
        for(int j=0; j<m; ++j){
            if(s[i+j] != '?' && s[i+j] != t[j]) ok = false; //falseを一回でも通るとこの文字列は候補から外れる
            s2[i+j] = t[j];  //すべてsの先頭からtの文字列に変えたものを作成していく
        }
        if(ok){
            replace(s2.begin(), s2.end(), '?', 'a');
            ans = min(ans, s2);  //okを通った中でも辞書順の小さいものを選ぶ
        }
    }

    if(ans == "~")
        cout << "UNRESTORABLE" << endl;
    else
        cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    ll res = 0;
    rep(i, N) cin >> a[i];
    rep(i, N) rep(j, N) {
        if(i == j)
            continue;
        res += a[i] * a[j];
    }
    res /= 2;
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>

using namespace std;

struct locate{
  int x;
  int y;
};
 
char graph[20][20];
int cou = 0;
int H,W;

void bfs(locate z){
  queue<locate> Q;
  locate u;
  locate v;
  Q.push(z);
 

  while(!Q.empty()){

    u = Q.front();Q.pop();
    if(u.y < H - 1){
      if(graph[u.y + 1][u.x] == '.' && graph[u.y + 1][u.x] != 'N'){
	graph[u.y + 1][u.x] = 'N';
	cou++;
	v.y = u.y + 1;
	v.x = u.x;
	Q.push(v);
      }
    }
    if(u.x < W - 1){
      if(graph[u.y][u.x + 1] == '.' && graph[u.y][u.x + 1] != 'N'){
	graph[u.y][u.x + 1] = 'N';
	cou++;
	v.x  = u.x + 1;
	v.y = u.y;
	Q.push(v);
      }
    }
    if(u.y > 0){
      if(graph[u.y - 1][u.x] == '.' && graph[u.y - 1][u.x] != 'N'){
	graph[u.y - 1][u.x] = 'N';
	cou++;
	v.x = u.x;
	v.y = u.y - 1;
	Q.push(v);
      }
    }
    if(u.x > 0){
      if(graph[u.y][u.x - 1] == '.' && graph[u.y][u.x - 1] != 'N'){
	graph[u.y][u.x - 1] = 'N';
	cou++;
	v.x = u.x - 1;
	v.y = u.y;
	Q.push(v);
      }
    }

    /* cout << endl;
       for(int i = 0; i< H ;i++){
       for(int j = 0; j < W; j++){
       cout << graph[i][j];
       }
       cout << endl;*/
  }
}
  


int main(){

  int a1,a2;
  locate a;
  while(1){

    cin >> W >> H;

    if(W == 0 && H == 0) break; 


    for(int i = 0; i< H ;i++){
      for(int j = 0; j < W; j++){
	cin >> graph[i][j];
	if(graph[i][j] == '@'){
	  a1 = i;
	  a2 = j;
	}
      }
    }

    /*
      for(int i = 0; i< H ;i++){
      for(int j = 0; j < W; j++){
      cout << graph[i][j];
      }
      cout << endl;
      }
    */

    a.y = a1;
    a.x = a2;
    bfs(a);

    cout << cou+1 << endl;

    cou = 0;
    for(int i = 0;i < H ;i++){
      for(int j = 0;j < W; j++){
	graph[i][j] = 'N';
      }
    }
    cou = 0;
  }
  return 0;
}

Measured memory_bytes: 3096
#include <iostream> 
#include <string> 
#include <algorithm> 
using namespace std;
bool cmp(char a, char b){
	return a > b;
}
int main(){
	string s, t;
	cin >> s;
	cin >> t;
	sort(s.begin(), s.end()); sort(t.begin(), t.end(), cmp);
	if (s < t)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<functional>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;

LL N,M,a,b,c,d;
string s[100010];
int main(){
    cin>>N;
    int cnt=0;
    for(int i=0;i<N;i++){
        cin>>a;
        if(a%2==1)cnt++;
    }
    if(cnt%2==1){
        cout<<"NO";
    }else{
        cout<<"YES";
    }

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>

using namespace std;

int N, K;
long long int trees[100010];
int fin;
long long int mini = 1000000009;

int main()
{
  cin >> N >> K;
  for(int i=0; i<N; i++)
  {
    cin >> trees[i];
  }
  sort(trees, trees+N);
  fin=K-1;
  for(int i=0; fin<N; fin++,i++)
  {
    //cout << i << " " << fin << "\n";
    if(trees[fin]-trees[i]<mini)
      mini = trees[fin] - trees[i];
  }
  cout << mini;
  return 0;
}

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

#define ll long long
const int MOD = 1e9+7;


void solve()
{
    int n;
    cin >> n;
    vector<int> dp(3);

    for(int i=0;i<n;i++)
    {
        vector<int> a(3);
        for(int j=0;j<3;j++)
            cin >> a[j];
        vector<int> temp_dp(3);
        if(!i)
        {
            dp = a;
            continue;
        }
        temp_dp[0] = a[0]+max(dp[1],dp[2]);
        temp_dp[1] = a[1]+max(dp[2],dp[0]);
        temp_dp[2] = a[2]+max(dp[0],dp[1]);
        dp = temp_dp;
    }
    cout << *max_element(dp.begin(),dp.end());
}




int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int main() {
	int n; read(n);
	if (n >= 1000) printf("ABD\n");
	else printf("ABC\n");
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const ll MOD=1000000007;
const ll INF=1000000010;
const ll LINF=4000000000000000010;
const double EPS=1e-9;
int dx[5]={0,1,0,-1,0};
int dy[5]={1,0,-1,0,0};

int main(){
    int n;
    cin>>n;
    int ma=0;int s;
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        if(a>ma)ma=a,s=b;
    }   
    cout<<ma+s<<endl;
}

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

int main(void){
  int n;
  cin >> n;
  vector<int> p(n);
  for(int i = 0; i < n; i++){ cin >> p[i]; }
  int ans = 0;
  for(int i = 1; i < n-1; i++){
    if((p[i-1] < p[i] && p[i] < p[i+1]) || (p[i+1] < p[i] && p[i] < p[i-1])){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


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

const int N = 100005;

int n, m, h[N], cnt;
bool good[N];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &h[i]);
		good[i] = true;
	}
	for (int i = 1, u, v; i <= m; i++) {
		scanf("%d%d", &u, &v);
		if (h[u] <= h[v]) good[u] = false;
		if (h[v] <= h[u]) good[v] = false;
	}
	for (int i = 1; i <= n; i++) {
		cnt += (int)good[i];
	}
	printf("%d\n", cnt);
	return 0;
}

Measured memory_bytes: 4244
#include <iostream>
using namespace std;
 
int main(){
  int A, B;
  cin >> A;
  cin >> B;
  int result = 0;
  
  if( A == 1 || B == 1 ){
  	if( A == 2 || B == 2 ){
      result = 3;
    }else{
      result = 2;
    }
  }else{
    result = 1;
  }
  
  cout << result << endl;

  return 0;
}

Measured memory_bytes: 256
/**
 * Title: D - Handstand 2
 * Url: https://atcoder.jp/contests/abc152/tasks/abc152_d
 * 
 * <考えたポイント>
 * ・全探索 O(N^2)
 * AとBの組み合わせを全列挙して試すと確実に答えは出る. 
 * が、計算量が膨大となり、時間内に解き終わらない
 * 
 * ・片方を固定して考える.  
 * 例えば, Aを固定したときに, 
 * Bが取りうる値を列挙していくパターン. 
 * Bが取りうる値を列挙するのを O(1) で出来れば, 
 * O(N) で求められるけど、そのやり方が思いつかない.  
 */
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<numeric>
#include<functional>
#include<sstream>
#include<iomanip>

using namespace std;

#define ll long long

int ctoi(char c) {
	switch (c) {
		case '0': return 0;
		case '1': return 1;
		case '2': return 2;
		case '3': return 3;
		case '4': return 4;
		case '5': return 5;
		case '6': return 6;
		case '7': return 7;
		case '8': return 8;
		case '9': return 9;
		default: return 0;
	}
}

int main() {
    int n; cin >> n;
    
    // 辞書を作成
    vector<vector<int>> cij(10, vector<int>(10, 0));
    for(int k=1; k<=n; k++) {
        ostringstream ss;
        ss << k;
        string s(ss.str());
        int i = ctoi(s[0]);
        int j = ctoi(s[s.size()-1]);
        cij[i][j]++;
    }

    int ans = 0;
    for(int i=0; i<=9; i++) {
        for(int j=0; j<=9; j++) {
            ans += cij[i][j]*cij[j][i];
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int x = a + b;
        int y = a + c;
        int z = b + c;
        if (x < y && x < z) {
            System.out.println(x);
        } else if (y < x && y < z) {
            System.out.println(y);
        } else if (z < x && z < y) {
            System.out.println(z);
        } else {
            System.out.println(x);
        }
    }
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
// #include <atcoder/all>

using namespace std;
// using namespace atcoder;

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

typedef long long ll;
typedef unsigned long long ull;

ll solve(int n) {
    ll ret = 0;
    for (int i = 1; i < n; i++) {
        ret += (n - 1) / i;
    }
    return ret;
}

int main() {
    int n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}

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

using namespace std;

const int oo { 1000000010 };

vector<int> z(const string &s)
{
    int n = (int) s.size(), L = 0, R = 0;
    vector<int> zs(n, 0);

    for (int i = 1; i < n; i++)
    {
        if (i <= R)
            zs[i] = min(zs[i - L], R - i + 1);

        while (zs[i] + i < n && s[zs[i]] == s[i + zs[i]])
            zs[i]++;

        if (R < i + zs[i] - 1)
            L = i, R = i + zs[i] - 1;
    }

    return zs;
}

int dfs(int u, int v, int k, int N, vector<int>& dist, const vector<int>& zs)
{
    if (dist[u] > -1)
        return dist[u];

    if (u == v)
        return oo;

    if (zs[k + 1 + u] != k)
        return 0;

    auto w = (u + k) % N;
    dist[w] = dfs(w, v, k, N, dist, zs);

    return 1 + dist[w];
}

int max_seq(const vector<int>& zs, int k, int N)
{
#ifdef DEBUG
    for (int i = 0; i < N + k + 1; ++i)
        cout << setw(3) << i;
    cout << endl;
    for (int i = 0; i < N + k + 1; ++i)
        cout << setw(3) << zs[i];
    cout << endl;
#endif

    vector<int> dist(N, -1);

    for (int i = 0; i < N; ++i)
    {
        if (dist[i] > -1)
            continue;

        if (zs[k + 1 + i] != k)
            dist[i] = 0;
        else
            dist[i] = 1 + dfs((i + k) % N, i, k, N, dist, zs);
    }

#ifdef DEBUG
    for (int i = 0; i < N; ++i)
        cout << "dist[" << i << "] = " << (dist[i] == oo ? -1 : dist[i]) << endl;
#endif

    auto ans = *max_element(dist.begin(), dist.end());

    return ans >= oo ? -1 : ans;
}

int solve(string& s, string& t)
{
    while (s.size() < t.size())
        s += s;

    auto p = t + '#' + s + s;
    auto zs = z(p);
    auto ans = max_seq(zs, (int) t.size(), (int) s.size());

    return ans;
}

int main()
{
    ios::sync_with_stdio(false);

    string s, t;
    cin >> s >> t;

    auto ans = solve(s, t);

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 36732
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
F=[int(i) for i in input().split()]
A.sort()
F.sort()

def chk(x):
  ct=0
  for i in range(n):
    a,f=A[i],F[-i-1]
    ct+=max(0,a-x//f)
  if ct<=k:
    return True
  else:
    return False


l,r=0,A[-1]*F[-1]
while r-l>1:
  m=(l+r)//2
  if chk(m):
    r=m
  else:
    l=m

if chk(l):
  print(l)
else:
  print(r)


Measured memory_bytes: 119500
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    a,b = LI()
    if b < 0:
        if (b-a)&1:
            print("Positive")
        else:
            print("Negative")
    elif a <= 0:
        print("Zero")
    else:
        print("Positive")
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 38256
N, maxW = map(int, input().split())
V, W = [], []
for i in range(N):
    v, w = map(int, input().split())
    V.append(v); W.append(w)
dp = [[0]*(maxW+1) for _ in range(N+1)]
for i in range(N):
    for j in range(maxW+1):
        if j < W[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-W[i]] + V[i])
print(dp[N][maxW])

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

int meguru_binary_search (int val, int *array, int ok, int ng) {

    while (abs(ok - ng) > 1) {

        int mid = (ok + ng) / 2;

        if (array[mid] >= val) {
            ok = mid;
        }
        else {
            ng = mid;
        }
    }

    return ok;
}

int main () {

    int contest[] = {111, 222, 333, 444, 555, 666, 777, 888, 999};

    int N;
    cin >> N;

    cout << contest[meguru_binary_search(N, contest, 10, -1)] << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long int;
template<typename T> void swap(T *t1, T *t2){ T* tmp=t1; t1=t2; t2=tmp;}
Int tmp = 0;
double tmpd = 0.0;


Int inf = pow(10,9)+7;

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

    Int n, m;
    cin >> n >> m;
    Int a[100001];
    Int c[100001];
    a[0] = -1;
    for(Int i=1; i<=m; i++){
        cin >> a[i];
        if(a[i] == a[i-1]+1){
            cout << "0" << endl;
            return 0;
        }
    }

    c[0] = 1;
    c[1] = 1;
    c[2] = 2;
    for(Int i=3; i<=n; i++){
        c[i] = (c[i-1] + c[i-2])%inf;
    }

    Int cnt = 1;
    for(Int i=0; i<m; i++){
        Int diff = (a[i+1]-1) - (a[i]+1);
        cnt *= c[diff];
        cnt %= inf;
    }
    Int diff = n - (a[m]+1);
    cnt *= c[diff];
    cnt %= inf;
    cout << cnt << endl;

    return 0;
}

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

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

typedef long long ll;
typedef array<int, 3> tri;
typedef long double ld;

template <class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}


const int mod = 1e9 + 7;
void _main() {
        int n; cin >> n;
        vector<vector<int>> match(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                        cin >> match[i][j];
                }
        }

        vector<int> dp(1 << n);
        dp[0] = 1;
        for (int man = 0; man < n; man++) {
                vector<int> new_dp(1 << n);
                for (int mask = 0; mask < (1 << n); mask++) {
                        if (__builtin_popcount(mask) != man + 1) continue;
                        for (int woman = 0; woman < n; woman++) {
                                if (1 << woman & mask && match[man][woman]) {
                                        (new_dp[mask] += dp[mask ^ (1 << woman)]) %= mod;
                                }
                        }
                }
                dp = new_dp;
        }

        cout << dp.back();
}



signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}

Measured memory_bytes: 19724
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = int.Parse(line[0]);
        var b = int.Parse(line[1]);
        var x = 1;
        var y = 1;
        extgcd(a, b, ref x, ref y);
        Console.WriteLine("{0} {1}", x, y);
    }
    public static int extgcd(int a, int b, ref int x, ref int y)
    {
        var d = a;
        if (b != 0)
        {
            d = extgcd(b, a % b, ref y, ref x);
            y -= (a / b) * x;
        }
        else { x = 1; y = 0; }
        return d;
    }
}



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

using ll = long long;

#define for_(i,a,b) for(int i = (a);i < (b);i++)
#define rfor_(i,a,b) for(int i = (b)-1;i >= (a);i--)
#define rep(i,n) for_(i,0,(n))
#define rrep(i,n) rfor_(i,0,(n))

#define pb push_back

vector<int> p;

int n;

bool isp(int a) {
    rep(i, p.size()) {
        if(a==p[i])return true;
        if(a%p[i]==0)return false;
    }
    return true;
}

int main(){
	cin.tie(0);
	
	cin>>n;
	cout<<n<<':';
	int i = 2;
	while(i*i<=n) {
	    if(n%i==0) {
	        cout<<' '<<i;
	        n /= i;
	    } else i++;
	}
	
	cout<<' '<<n<<endl;
	
	return 0;
}



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

scores = []

for i in range(0, N):
    a, b = [int(i) for i in input().split()]
    scores.append((a + b, a, b))

scores.sort(reverse=True)
result = 0
for i in range(0, N):
    if i % 2 == 0:
        result += scores[i][1]
    else:
        result -= scores[i][2]

print(result)


Measured memory_bytes: 20996
#include <stdio.h>

int main(){
  int a , b;
  scanf("%d %d", &a, &b);
  if(a > 0 && a < 10 && b > 0 && b < 10){
    printf("%d\n", a*b);
  }
  else{
    printf("-1\n");
  }
  return 0;
}


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};


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

  string s;
  cin >> s;

  set<ll> t;
  REP(i, s.size())
    t.insert(s[i]-'a');

  if(t.size() == s.size())
    cout << "yes" << endl;
  else
    cout << "no" << endl;
}


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

#define int long long
using P = pair<int, int>;

vector<int> G[100001];
int N;

int pre[100001];
int col[100001];

int bfs() {
  vector<bool> used(N, false);
  queue<P> q;
  q.push(P(0, 0));
  while ( !q.empty() ) {
    P p = q.front(); q.pop();
    int v = p.first, c = p.second;

    if ( v == N-1 ) return c;    
    
    if ( used[v] ) continue;
    used[v] = true;

    for ( int u : G[v] ) {
      if ( used[u] ) continue;      
      pre[u] = v;
      q.push(P(u, c+1));      
    }
  }
}

void bfs2() {
  vector<bool> used(N, false);
  queue<P> q;
  q.push(P(0, 0));
  while ( !q.empty() ) {
    P p = q.front(); q.pop();
    int v = p.first, c = p.second;   
    
    if ( used[v] ) continue;
    used[v] = true;
    col[v] = 1;    

    for ( int u : G[v] ) {
      if ( used[u] ) continue;		       
      if ( col[u] == 2 ) continue;      
      q.push(P(u, c+1));      
    }
  }
}

signed main() {
  cin >> N;
  for ( int i = 0; i < N-1; i++ ) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  
  int c = bfs();
  int now = N-1;
  int cnt = 0;
  
  while ( 1 ) {
    
    if ( cnt < (c+1)/2 ) {
      col[now] = 2;
      // cout << now << endl;
    } else {      
      col[now] = 1;      
    }
    cnt++;    
    if ( now == 0 ) break;
    now = pre[now];    
  }
  
  bfs2();
  int bl = 0;
  for ( int i = 0; i < N; i++ ) {
    if ( col[i] == 1 ) bl++;    
  }

  if ( bl > (N-bl) ) puts("Fennec");
  else puts("Snuke");  
  
  return 0;  
}


Measured memory_bytes: 8144
#include <iostream>
#include <vector>
#include <set>

#define rep(i,a) for(int i = 0 ; i < a ; i ++)
#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define vi vector<int>
#define vs vector<string>
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
using namespace std;

int check(int n){
  int s = 0;
  while(n){
    s += n % 10;
    n /= 10;
  } 
  return s;
}

int main(void){
  int n,a,b;
  cin>>n>>a>>b;
  int ret = 0;
  rep(i,n+1){
    if(a <= check(i) && check(i) <= b){
    // cout<<i<<" "<<check(i)<<endl;
      ret += i;
    }
  }
  cout<<ret<<endl;
}

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

using namespace std;
using ll = long long;


const int MOD = 998244353;

class Edge{
public:
    ll from,to, value;
    Edge(int f,int t, int c){
        from = f;
        to = t;
        value = c;
    }
};

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

int main(){
    int N;cin >> N;
    vector<int> v;
    vector<pair<ll, ll>> usi;
    int q = 0;
    map<ll, ll> mp;
    for(int i = 0;i < N;i++){
        int b;cin >> b;
        v.push_back(b);
        if(b == 0)q++;
        mp[b]++;
    }
    if(v.front() != 0 || q >= 2){
        cout<<0<<endl;
        return 0;
    }
    vector<pair<ll,ll>> w;
    for(auto a : mp){
        w.push_back(a);
    }
    ll ans = 1;
    for(ll i = 0;i < w.size();i++){
        if(i != w[i].first){
            cout<<0<<endl;
            return 0;
        }
        if(i == 0)continue;
        ans *= modpow(w[i-1].second, w[i].second, MOD) % MOD;
        ans %= MOD;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 9076
loop{
  n = gets.to_i
  break if n == 0

  from_str = ""
  to_str = ""
  n.times{
    from_char, to_char = gets.chomp.split
    from_str += from_char
    to_str += to_char
  }
  m = gets.to_i
  out_str = ""
  m.times{
    ch = gets.chomp
    out_str += ch
  }
  puts out_str.tr(from_str, to_str)
}

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

int main() {
    int a,b,t,h=0;
    cin >> a >> b;

    t = b-a;
    rep(i,t)
        h += i+1;
    cout << h-b << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <unordered_map>
#define endl "\n"
#define all(v) v.begin(),v.end()
#define allr(s) s.rbegin(),s.rend()
#define RT(s) return cout<<s,0
#define watch(x) cout << (#x)<<" = "<<x<<endl
#define sz(s)	(int)(s.size())
//#define PI acos(-1)
#define EPS 1e-8
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
void file() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
	//freopen("street.in", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
}
void fast() {
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
}

int main() {
	//file();
	fast();
	int h, a; cin >> h >> a;
	cout << (h + a - 1) / a << endl;
	return 0;
}

Measured memory_bytes: 256
def f_single_dot():
    # https://atcoder.jp/contests/abc168/submissions/13368489
    import sys
    from collections import deque
    input = sys.stdin.readline
    N, M = [int(i) for i in input().split()]

    x_set, y_set = set([0]), set([0])  # 重複を除いた xy 座標の一覧 (座標圧縮に必要)

    vertical_lines = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        vertical_lines.append((a, b, c))
        x_set |= {a, b}
        y_set |= {c}

    horizontal_lines = []
    for _ in range(M):
        d, e, f = map(int, input().split())
        horizontal_lines.append((d, e, f))
        x_set |= {d}
        y_set |= {e, f}

    x_set = sorted(x_set)
    y_set = sorted(y_set)

    # 座標圧縮 (壁も配列に格納するので、2 倍している)
    x_encoded = {n: i * 2 for i, n in enumerate(x_set)}
    y_encoded = {n: i * 2 for i, n in enumerate(y_set)}
    # 座標圧縮されたグリッドで縦横に 1 マス分進むことは実際にはどれくらい進んだことなのか
    x_length = [x_set[i // 2 + 1] - x_set[i // 2] if i %
                2 else 0 for i in range(len(x_set) * 2 - 1)]
    y_length = [y_set[i // 2 + 1] - y_set[i // 2] if i %
                2 else 0 for i in range(len(y_set) * 2 - 1)]

    grid = [[0] * (len(x_set) * 2 - 1) for _ in range(len(y_set) * 2 - 1)]
    for a, b, c in vertical_lines:
        a, b, c = x_encoded[a], x_encoded[b], y_encoded[c]
        for x in range(a, b + 1):
            grid[c][x] = 1
    for d, e, f in horizontal_lines:
        d, e, f = x_encoded[d], y_encoded[e], y_encoded[f]
        for y in range(e, f + 1):
            grid[y][d] = 1

    que = deque()
    used = [[0] * len(x_set) * 2 for _ in range(len(y_set) * 2)]
    dy = [1, 1, -1, -1]
    dx = [1, -1, 1, -1]
    for k in range(4):
        nny, nnx = y_encoded[0] + dy[k], x_encoded[0] + dx[k]
        if 1 <= nny < len(y_set) * 2 - 1 and 1 <= nnx < len(x_set) * 2 - 1:
            que.append((nny, nnx))
            used[nny][nnx] = 1
    ans = 0
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    while que:
        y, x = que.popleft()
        if y % 2 and x % 2:
            ans += y_length[y] * x_length[x]
        for k in range(4):
            ny, nx = y + dy[k], x + dx[k]
            nny, nnx = ny + dy[k], nx + dx[k]
            if grid[ny][nx] == 0:
                if nny < 0 or nny >= len(y_set) * 2 - 1 or nnx < 0 or nnx >= len(x_set) * 2 - 1:
                    return 'INF'
                if not used[nny][nnx]:
                    que.append((nny, nnx))
                    used[nny][nnx] = 1
    return ans

print(f_single_dot())

Measured memory_bytes: 713648
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
  String s=sc.next();
  String t=sc.next();
  int count=0;
  for(int i=0;i<s.length();i++){
if(s.charAt(i)!=t.charAt(i)){
count++;
}
  }
  System.out.println(count);
}
}

Measured memory_bytes: 41196
def LI(): return list(map(int, input().split()))
def LS(): return input().split()
def I(): return int(input())
def S(): return input()

n = I()
a = LI()
even = a[0::2]
odd = a[1::2]

if n % 2:
    ans = even[::-1]
    ans.extend(odd)
else:
    ans = odd[::-1]
    ans.extend(even)
for i in ans:
    print(i, end=" ")

Measured memory_bytes: 26020
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack> //深さ優先
#include <queue> //幅優先
#include <set>

using namespace std;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int A,B,C;
	cin >> A >> B >> C;
	if(A + B >= C){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

const pid_t pid = getpid();
// Problem Specific Parameter:
#define error(args...) { vector<string> _debug = split(#args, ',');err(begin(_debug), args);}

vector<string> split(const string& s, char c){
	vector<string> v;stringstream ss(s);string x;
	while (getline(ss, x, c)) v.emplace_back(x);
	return move(v);
}

void err(vector<string>::iterator it) {cerr << endl;}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a,Args... args){
	cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << " ",err(++it, args...);
}

const int limit = 200010;
int out_l, out_r;
char t[limit], d[limit];

int main(void){
	int n,q;
	cin >> n >> q;
	string s;
	cin >> s;

	rep(i, q) cin >> t[i] >> d[i];
	int ng_l = -1, ok_l = n;

	while(abs(ok_l - ng_l) > 1){
		const int mid = (ok_l + ng_l) / 2;
		int cur = mid;
		rep(i, q){
			if(cur < 0 or n <= cur) break;
			if(t[i] == s[cur]){
				if(d[i] == 'L')
					cur--;
				else
					cur++;
			}
		}
		if(cur < 0) 
			ng_l = mid;
		else
			ok_l = mid;
	}

	
	int ok_r = -1, ng_r = n;

	while(abs(ok_r - ng_r) > 1){
		const int mid = (ok_r + ng_r) / 2;
		int cur = mid;
		rep(i, q){
			if(cur < 0 or n <= cur) break;
			if(t[i] == s[cur]){
				if(d[i] == 'L')
					cur--;
				else
					cur++;
			}
		}
		
		if(cur >= n) 
			ng_r = mid;
		else
			ok_r = mid;
	}

	const int ans = max(0, ok_r - ok_l + 1);
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define pri_que priority_queue
#define vint vector<int>
#define vvint vector<vector<int>>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vs vector<string>
#define vvc vector<vector<char>>
#define vc vector<char>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define show(x) cout<<#x<<"="<<x<<endl;
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e15;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int n; cin >> n;
    vint a(n);
    rep(i,n)cin>>a[i];
    vint b=a;
    sort(all(b));

    int l=b[n/2-1],r=b[n/2];
    rep(i,n){
        int c=lower_bound(all(b),a[i])-b.begin();
        if(c<n/2) cout<<r<<endl;
        else cout<<l<<endl;
    }


}

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

int main()
{
	int nInput1, nInput2;

	while (cin >> nInput1 >> nInput2)
	{
		if (nInput1>nInput2)
		{
			cout << "a > b" << endl;
		}
		else if (nInput1==nInput2)
		{
			cout << "a == b" << endl;
		}
		else
		{
			cout << "a < b" << endl;
		}
	}

	return 0;
}

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

using namespace std;
typedef long long ll;

int main() {
	string s;
	cin >> s;
//	strins D[7] = {'SUN','MON','TUE','WED','THU','FRI','SAT'};

	if(s == "SUN"){
		cout << "7" << endl;
	}else if(s == "MON"){
		cout << "6" << endl;
	}else if(s == "TUE"){
		cout << "5" << endl;
	}else if(s == "WED"){
		cout << "4" << endl;
	}else if(s == "THU"){
		cout << "3" << endl;
	}else if(s == "FRI"){
		cout << "2" << endl;
	}else if(s == "SAT"){
		cout << "1" << endl;
	}
}

Measured memory_bytes: 256
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let s = read_as_string();

    if s.len() == 3{
        println!("{}", s.chars().rev().collect::<String>());
    }else{
        println!("{}", s);
    }
}


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

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

  int b[100000];
  for(int k=0;k<100000;k++){
    b[k] = 0;
  }
  for(int i=0;i<n;i++){
    int temp = a[i];
    if(temp == 0){
      b[0]++;
      b[1]++;
    }
    else if(temp == 100000){
      b[100000]++;
      b[99999]++;
    }
    else{
      b[temp-1]++;
      b[temp]++;
      b[temp+1]++;
    }
  }

  int max_ = 0;
  for(int m=0;m<100000;m++){
    if(max_ < b[m]){
      max_ = b[m];
    }
  }

  cout << max_ << endl;
  return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
typedef pair<int,int> P;
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)cin>>a.at(i);
    sort(a.begin(),a.end());
    queue<P> Q;
        for(int i=0;i<n-2;i++){
        if(a.at(i)<=0&&a.at(i+1)<=0){
            Q.push(P(a.at(n-1),a.at(i)));
           a.at(n-1)-=a.at(i);
        }
        else if(a.at(i+1)>0){
            Q.push(P(a.at(i),a.at(i+1)));
            a.at(i+1)=a.at(i)-a.at(i+1);
        }
    }
    Q.push(P(a.at(n-1),a.at(n-2)));
    cout<<a.at(n-1)-a.at(n-2)<<endl;
    while(!Q.empty()){
        P q=Q.front();
        Q.pop();
       cout<<q.first<<" "<<q.second<<endl;
    }
}

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

int main() {
  char X, Y;
  cin >> X >> Y;

  if (X < Y) {
    cout << "<" << endl;
  }
  else if (X > Y) {
    cout << ">" << endl;
  }
  else {
    cout << "=" << endl;
  }
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

int main()
{
    int n, k, x, y;
    cin >> n >> k >> x >> y;

    int ans = min(n, k) * x + max(0, n - k) * y;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int a[2000001],c[10001],b[2000001],n,_max=0;;

int main(){
  cin >> n;
  for(int i=0; i<10001; ++i) c[i] = 0;
  for(int i=0; i<n; ++i) {
    cin >> a[i];
    ++c[a[i]];
    if(_max < a[i]) _max = a[i];
  }
  for(int i=0; i<_max; ++i) c[i+1] += c[i];

  for(int i=n-1; i>=0; --i){
    b[c[a[i]]] = a[i];
    --c[a[i]];
  }

  for(int i=1; i<n+1; ++i){
    cout << b[i];
    if(i < n) cout << " ";
  }
  cout << endl;
  


  return 0;
}



Measured memory_bytes: 18768
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	n := nextInt()
	k := nextInt()

	fmt.Println(n - k + 1)

}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // Default=64
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1780
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
using namespace std;
typedef long long ll;

int a,b,c;

int main(){
	scanf("%d%d%d",&a,&b,&c);
	int r=0;
	while(a%2==0&&b%2==0&&c%2==0&&r<10000000){
		int a2=a/2,b2=b/2,c2=c/2;
		a=b2+c2;
		b=a2+c2;
		c=a2+b2;
		r++;
	}
	if(r==10000000)puts("-1");
	else printf("%d\n",r);
	return 0;
}

Measured memory_bytes: 256
sx, sy, tx, ty = map(int, input().split())

ans = ""
count = 0

ans = ans + 'U' * (ty-sy) + 'R' * (tx-sx)
ans = ans + 'D' * (ty-sy) + 'L' * (tx-sx)
ans = ans + 'L' + 'U' * (ty-sy+1) + 'R' * (tx-sx+1) + 'D'
ans = ans + 'R' + 'D' * (ty-sy+1) + 'L' * (tx-sx+1) + 'U'

print(ans)

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

using namespace std;
typedef long long LL;
static const double EPS = 1e-9;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
void printset(set<int> s){
  for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
    cout<<*it<<endl;
  }
}

set<int> sumup(set<int> s1,set<int> s2){
  for(set<int>::iterator it = s2.begin(); it!=s2.end(); it++){
    s1.insert(*it);
  }
  return s1;
}

int main(void){
  int n;
  while(cin>>n,n){
    vector<int> member[31];
    REP(i,n){
      int m,d;
      cin>>m;
      REP(j,m){
        cin>>d;
        member[d].push_back(i);
      }
    }
    int ans = -1;
    set<int> gather[50];
    REP(i,n)gather[i].insert(i);
    FOR(day,1,31){
      set<int> sm;
      REP(i,member[day].size()){
        sm = sumup(sm,gather[member[day][i]]);
      }
      if(sm.size()==n){
        ans = day;
        break;
      }
      REP(i,member[day].size()){
        gather[member[day][i]] = sm;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
def f(x):
    a,b=0,0
    for e in x:
        if e>a: a=e
        elif e>b: b=e
        else: return False
    return True

n=input()
for i in range(n):
    dt=map(int, raw_input().split())
    if f(dt): print "YES"
    else: print "NO"

Measured memory_bytes: 4204
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	String text = sc.nextLine();
    	if (text.length() == 2) {
    		System.out.println(text);
    	} else {
    		StringBuffer sb = new StringBuffer(text);
    		System.out.println(sb.reverse());
    	}
    	sc.close();
    }
}

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

using namespace std;

#define vit vector<int>::iterator
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fr first
#define sc second
#define skip continue
#define PI 3.14159265

typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int ui;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<bool> vb;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 3e5 + 3;

void faster(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

bool cmp(const string& a, const string& b) {
    return (a + b) < (b + a);
}

void solve(){
    int x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int up1 = y2 - y1;
    int r1 = x2 - x1;
    for(int i = 1; i <= up1; i++)
        cout << 'U';
    for(int i = 1; i <= r1; i++)
        cout << 'R';
    for(int i = 1; i <= up1; i++)
        cout << 'D';
    for(int i = 1; i <= r1; i++)
        cout << 'L';
    cout << 'L';
    for(int i = 1; i <= up1 + 1; i++)
        cout << 'U';
    for(int i = 1; i <= r1 + 1; i++)
        cout << 'R';
    cout << "DR";
    for(int i = 1; i <= up1 + 1; i++)
        cout << 'D';
    for(int i = 1; i <= r1 + 1; i++)
        cout << 'L';
    cout << 'U';

}


int main(){
    //freopen("slalom.in","r",stdin);
    //freopen("slalom.out","w",stdout);
    //faster();
    int n = 1;
    //cin >> n;
    while(n--){
        solve();
        cout << endl;
    }
    //fclose(stdout);
}


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


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    long long x,k,d; cin >> x >> k >> d;
    x = (long long)fabs(x);
	long long tmp = min(k, x / d);
	k -= tmp, x -= tmp * 1ll * d;
	if (k % 2)x -= d;
    cout << (long long)fabs(x) << endl;
    return 0;
}


Measured memory_bytes: 3624