akhauriyash/Code-Regression huggingface dataset:
# # Make IO faster
# import sys
# input = sys.stdin.readline

# # get single (or) multiple str
# X = input()

# # get single int
# N = int(input())
# # get multiple int (e.g., 2)
# X, Y = map(int, input().split())
# # get multiple int (e.g., 2) for N lines
# XY = [list(map(int, input().split())) for _ in range(N)]

# from IPython import embed; embed(); exit();

# 全部入り
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

print(48 - INT())


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

using namespace std;

typedef long long ll;

int main(){

    ll H, N;
    ll total = 0;

    cin >> H >> N;

    vector<int> A(N);

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

        total += A[i];

    }

    if(H <= total) cout <<"Yes";
    else cout << "No";

    return 0;
}

Measured memory_bytes: 640
package main

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

func main() {
	N := readi()
	M := readi()
	S := make([]int, M)
	C := make([]int, M)
	for i := 0; i < M; i++ {
		S[i] = readi()
		C[i] = readi()
	}

	mapN := make(map[int]int)
	for i := 0; i < M; i++ {
		n, ok := mapN[S[i]]
		if !ok {
			mapN[S[i]] = C[i]
		} else {
			if C[i] != n {
				fmt.Println(-1)
				return
			}
		}
	}

	ans := ""
	for i := 1; i <= N; i++ {
		n, ok := mapN[i]
		if !ok {
			if N >= 2 && i == 1 {
				ans = "1" + ans
				continue
			}
			ans = ans + "0"
		} else {
			ans = ans + strconv.Itoa(n)
		}
	}

	if N >= 2 {
		if string(ans[0]) == "0" {
			fmt.Println(-1)
			return
		}
	}

	fmt.Println(ans)
}

/*-------------------utilities-------------------*/

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func chmin(x *int, y int) bool {
	if *x > y {
		*x = y
		return true
	}
	return false
}

func chmax(x *int, y int) bool {
	if *x < y {
		*x = y
		return true
	}
	return false
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	return (a * b) / gcd(a, b)
}

func permutations(arr []int) [][]int {
	var helper func([]int, int)
	res := [][]int{}

	helper = func(arr []int, n int) {
		if n == 1 {
			tmp := make([]int, len(arr))
			copy(tmp, arr)
			res = append(res, tmp)
		} else {
			for i := 0; i < n; i++ {
				helper(arr, n-1)
				if n%2 == 1 {
					tmp := arr[i]
					arr[i] = arr[n-1]
					arr[n-1] = tmp
				} else {
					tmp := arr[0]
					arr[0] = arr[n-1]
					arr[n-1] = tmp
				}
			}
		}
	}
	helper(arr, len(arr))
	return res
}

func isPrime(n int) bool {
	if n == 1 {
		return false
	}
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

func divisor(n int) (res []int) {
	for i := 1; i*i <= n; i++ {
		if n%i == 0 {
			res = append(res, i)
			if i*i != n {
				res = append(res, n/i)
			}
		}
	}
	sort.Ints(res)
	return
}

/*-------------------init-------------------*/

const (
	INF = 1000000000000000000
	MOD = 1e9 + 7
)

var (
	readString func() string
)

func init() {
	readString = newReadString(os.Stdin)
}

/*-------------------inputs-------------------*/

func readi() int {
	return int(readi64())
}

func readi64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readf() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}


Measured memory_bytes: 640
# ALDS_2_B.
# バブルソート。
from math import sqrt, floor

def intinput():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

def show(a):
    # 配列の中身を出力する。
    _str = ""
    for i in range(len(a) - 1):
        _str += str(a[i]) + " "
    _str += str(a[len(a) - 1])
    print(_str)

def selection_sort(a):
    # 選択ソート。その番号以降の最小値を順繰りにもってくる。
    # 交換回数は少ないが比較回数の関係で結局O(n^2)かかる。
    count = 0
    for i in range(len(a)):
        # a[i]からa[len(a) - 1]のうちa[j]が最小っていうjを取る。
        # このときiとjが違うならカウントする。
        # というかa[i]とa[j]が違う時カウントでしたね。
        minj = i
        for j in range(i, len(a)):
            if a[j] < a[minj]: minj = j
        if a[i] > a[minj]: count += 1; a[i], a[minj] = a[minj], a[i]
    return count

def main():
    N = int(input())
    A = intinput()
    count = selection_sort(A)
    show(A); print(count)

if __name__ == "__main__":
    main()


Measured memory_bytes: 5668
S=input()

Q=int(input())

inst=[]
for i in range(Q):
    array=input().split()
    inst.append(tuple(array))

rev=True
front_str=[]
back_str=[]
for i in range(Q):
    if int(inst[i][0])==1:
        rev=not rev
    elif rev:
        if int(inst[i][1])==1:
            front_str.append(inst[i][2])
        else:
             back_str.append(inst[i][2])
    else:
        if int(inst[i][1])==1:
            back_str.append(inst[i][2])
        else:
            front_str.append(inst[i][2])

if rev:
    front_str.reverse()
else:
    back_str.reverse()
    S=S[::-1]

front="".join(front_str)
back="".join(back_str)

if rev:
    print(front+S+back)
else:
    print(back+S+front)

Measured memory_bytes: 25708
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n,k,ans=0;
  string s;
  cin >> n >> k >> s;
  vector<long long> imos;
  int cnt1=0,cnt0=0;
  for(int i=0;i<n;i++){
    if(s[i]=='1'){
      if(cnt0>0){
        imos.push_back(cnt0);
      }
      cnt0=0;
      cnt1++;
    }else{
      if(i==0 or cnt1>0){
        imos.push_back(cnt1);
      }
      cnt1=0;
      cnt0++;
    }
  }
  if(cnt0>0){
    imos.push_back(cnt0);
  }
  imos.push_back(cnt1);
  for(size_t i=0;i<imos.size()-1;i++){
    imos[i+1]+=imos[i];
  }
  for(int i=0;i<imos.size();i+=2){
    if(i+k+k>=imos.size()-1){
      if(i==0){
        ans=max(ans, imos[imos.size()-1]);  
      }else{
        ans=max(ans, imos[imos.size()-1]-imos[i-1]);
      }
      break;
    }else{
      if(i==0){
        ans=max(ans, imos[i+k+k]);  
      }else{
        ans=max(ans, imos[i+k+k]-imos[i-1]);
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1528
#include<bits/stdc++.h>
using namespace std;
const long long M =1e6+10,MOD=1000000000;
typedef long long ll;
ll arr[M];
ll tot=0;
ll tot2=0;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>arr[i];
      arr[0]=0;
      arr[m+1]=n;
    for(int i=1;i<m;i++)
    {
      tot+=abs(arr[i]-arr[i+1]);
    }
    tot2=tot;
    tot+=arr[1]-arr[0]+arr[m+1]-arr[m];
    for(int i=1;i<m;i++)
    {
      tot2=min(tot2,tot-(arr[i+1]-arr[i]));
    }
    cout<<tot2<<"\n";
    return 0;
  }

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <list>
#include <queue>
using namespace std;

int inf = (1 << 30);
int mod = 1e9 + 7;
int64_t inf64 = (1LL << 60);

template <typename T>
T gcd(T a, T b) {
    if(b == 0) return a;
    else return gcd(b, a % b);
}

template <typename T>
T lcm(T a, T b) {
    T g = gcd(a, b);
    return a / g * b;
}

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

int lower_bound(vector<int> a, int key){
    int left = -1, right = a.size();
    while(right - left > 1){
        int mid = left + (left + right) / 2;
        if(check(a, mid, key)) right = mid;
        else left = mid;
    }
    return right;
}

int main(){

    int64_t a, b, x;
    cin >> a >> b >> x;

    if(a == 0) cout << b / x + 1 << endl;
    else cout << b / x - (a - 1) / x << endl;

    return 0;
}

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

int main(void)
{
    int n;
    cin >> n;
    int a;
    double den = 0;
    for (int i = 0; i < n; i++) {
        cin >> a;
        den += 1.0 / a;
    }
    cout << fixed << setprecision(10) << 1.0 / den << endl;

    return 0;
}



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

int main()
{
    int n;
    cin >> n;
    int arr[4][3][10];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 10; k++) {
                arr[i][j][k] = 0;
            }
        }
    }
    while (n--) {
        int b, f, r, v;
        cin >> b >> f >> r >> v;
        b--; f--; r--;
        arr[b][f][r] += v;
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 10; k++) {
                cout << ' ' << arr[i][j][k];
                if (k == 9) cout << endl;
            }
        }
        if (i != 3) cout << "####################" << endl;
    }
}



Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll>m;
const int N = 2e5;
ll sum[N+100];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,k;
	ll ans = 0;
	cin >> n >> k;
	m[0] = 1;
	for(ll i=1;i<=n;i++){
		ll a;
		cin >> a;
		sum[i] = (sum[i-1]+a)%k;
		ans += (m[(sum[i]-(i)%k+k)%k]);
		m[(sum[i]-(i)%k+k)%k]++;
		if(i-k+1>=0){
			m[(sum[i-k+1]-(i-k+1)%k+k)%k]--;
		}
	}
	if(k==1){
		cout << "0\n";
	}
	else cout << ans << "\n";
}


Measured memory_bytes: 14336
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
typedef long long ll;
typedef long double ld;
#define str string
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
const ll Mod = 1000000007;
const ll gosenchou = 5000000000000000;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to;
	ld cost;
};
struct E {//辺の情報を入れる変数
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	/*if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;*/
	return ((a.x + 1)*(a.y + 1)) < ((b.x + 1)*(b.y + 1));
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(H a, H b) {
	return sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
}//rad＝座標上の2点間の距離
ll ari(ll a, ll b, ll c) {
	return (a + b)*c / 2;
}//等差数列の和
bool suf(ld a, ld b, ld c, ld d) {
	if (b <= c || d <= a) return 0;
	return 1;
}//[a,b),[c,d)
ll fact(ll x, ll k, ll p) {//最大値、個数
	ll sum = 1;
	for (int i = 0; i < k; i++) {
		sum *= (x--);
		sum %= p;
	}
	return sum;
}//階乗(正）
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res*x%p;
		x = x*x%p;
		n >>= 1;
	}
	return res;
}//x^n%p
 //#define int long long
const long long inf = 4523372036854775807;
const int iinf = 1500000000;
//----------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++
int n, m;
int a[1500],b[1500];
int c[2250000], d[2250000];
signed main() {
	while (cin >> n >> m&&n + m) {
		for (int i = 0; i < n; i++)
			cin >> a[i];
		for (int i = 0; i < m; i++)
			cin >> b[i];
		for (int i = 1; i < n; i++)
			a[i] += a[i - 1];
		for (int i = 1; i < m; i++)
			b[i] += b[i - 1];
		int k = 0, t = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				c[k++] = a[j] - a[i];
			}
			c[k++] = a[i];
		}
		for (int i = 0; i < m; i++) {
			for (int j = i + 1; j < m; j++) {
				d[t++] = b[j] - b[i];
			}
			d[t++] = b[i];
		}
		sort(c, c + k);
		sort(d, d + t);
		int ans = 0;
		for (int i = 0; i < k; i++) {
			ans += upper_bound(d, d + t, c[i]) - lower_bound(d, d + t, c[i]);
		}
		cout << ans << endl;
	}
	getchar(); getchar();
}


Measured memory_bytes: 11968
read a
j=2
echo $a > list 
for i in `seq 2 1000000`; do
	if [ $(($a%2 )) == 0 ]; then
    	a=$(($a/2))
    else
    	a=$(($a*3+1))
    fi    
echo $a >> list
sort list | uniq -d > list1
	if [ -s list1 ]; then
		echo $j
    	break 2
	else
		j=$((j+1))
	fi
done

Measured memory_bytes: 104404
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,from,to) for(int i=from; i<to; ++i)
#define REP(i,from,to) for(int i=from; i<=to; ++i)
using namespace std;
typedef pair<int, int> P;
typedef pair<P, P> area;
typedef struct answer answer;
template<typename T>
ostream& operator<<(ostream& out, const vector<vector<T> >& v) {
	for (size_t i = 0; i < v.size(); ++i) {
		out << v[i] << endl;
	}
	return out;
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
	out << "[";
	size_t last = v.size() - 1;
	for (size_t i = 0; i < v.size(); ++i) {
		out << v[i];
		if (i != last) {
			out << ",";
		}
	}
	out << "]";
	return out;
}

const int maxn = 110;
int n;
int a[maxn];
void print(int arr[maxn], int n) {
	for (int i = 0; i < n - 1; ++i) {
		cout << arr[i] << " ";
	}
	cout << arr[n - 1] << endl;
}

void selectionSort(int arr[maxn], int n) {
	int cnt = 0;
	REP(i,0,n-1)
	{
		int minj = i;
		REP(j,i,n-1)
		{
			if (arr[j] < arr[minj]) {
				minj = j;
			}
		}
		if (i != minj) {
			swap(arr[i], arr[minj]);
			cnt++;
		}
	}
	print(arr, n);
	cout << cnt << endl;
}

void bubbleSort(int arr[maxn], int n) {
	int cnt = 0;
	int flag = 1;
	while (flag) {
		flag = 0;
		for (int j = n - 1; j >= 1; j--) {
			if (arr[j] < arr[j - 1]) {
				swap(arr[j], arr[j - 1]);
				flag = 1;
				cnt++;
			}
		}
	}
	print(arr, n);
	cout << cnt << endl;
}

void insertionSort(int arr[maxn], int n) {
	print(arr, n);
	REP(i,1,n-1)
	{
		int v = arr[i];
		int j = i - 1;
		while (j >= 0 && arr[j] > v) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = v;
		print(arr, n);
	}
}

void solve() {
	cin >> n;
	rep(i,0,n)
	{
		cin >> a[i];
	}
	selectionSort(a, n);
}

int main() {
	solve();
}

Measured memory_bytes: 3092
#include <set>
#include <cstdio>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

inline int getInt(){ int s; scanf("%d", &s); return s; }

using namespace std;

vector<int> decode(int flag, int n){
  vector<int> ret(n);
  REP(i,n) ret[i] = (flag >> (3 * i)) & 7;
  return ret;
}

int encode(const vector<int> &v){
  const int n = v.size();
  int ret = 0;
  REP(i,n) ret |= v[i] << (3 * i);
  return ret;
}

int main(){
  int n = getInt();
  int c[8][8];

  REP(i,n) REP(j,n)
    c[i][j] = getInt();

  vector<bool> memo(1<<(3*n));
  typedef pair<int, int> data;
  priority_queue<data, vector<data>, greater<data> > pq;

  {
    vector<int> f(n); REP(i,n) f[i] = i;
    pq.push(make_pair(0, encode(f)));
  }

  int ans = 0;

  while(pq.size()){
    pair<int, int> d = pq.top(); pq.pop();
    int cost = d.first;
    int flag = d.second;
    vector<int> f = decode(flag, n);

    if(memo[flag]) continue;
    memo[flag] = true;
    ans = max(ans, cost);

    REP(i,n) REP(j,i){
      swap(f[i], f[j]);

      int ff = encode(f);
      if(!memo[ff])
        pq.push(make_pair(cost + c[i][j], ff));

      swap(f[i], f[j]);
    }

  }

  printf("%d\n", ans);

  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define ALL(c) (c).begin(), (c).end()
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int  n;
    string s;
    cin >> n >> s;
    rep(i,s.length())
    {
        int tmp_num = s[i] - 'A';
        tmp_num += n;
        tmp_num %= 26;
        char tmp_char = 'A'+tmp_num;
        cout << tmp_char;
    }
    cout << endl;
    
    
}




Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>
using namespace std;
using ll = long long;
constexpr ll INF = 1010000000000000017LL;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()

class C4Adjacent {
public:
	void solve(std::istream& in, std::ostream& out) {
        ll n;
        in>>n;

        ll nd=0,th=0,ks=0;
        rep(i,n){
            ll tmp;
            in>>tmp;
            if(tmp%4==0)  ++th;
            else if(tmp%2==0) ++nd;
            else ++ks;


        }
        if(nd>=2) {
            nd -= (nd / 2) * 2;
        }
        ks += nd;
        if(th+1>=ks) out<<"Yes"<<endl;
        else out<<"No"<<endl;

	}
};


int main() {
	C4Adjacent solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long n,k,ans;
long f(long x)
{
	return x*0;
}
long x(long x)
{
  return x;
}
int main()
{
	cin>>n>>k;
	ans=1;
	while (n--)
	{
	 ans+=min(ans,k);
	}
	cout<<x(x(x(x(x(x(x(x(x(x(x(x(x(x(x(ans)))))))))))))));
   return f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(1)))))))))))))))));
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int n,x,i=1;
    cin>>n;
    while(i<=n){x=i;
        if(x%3==0){
            cout<<" "<<i;
        }
        
        else{while(1){
            if(x%10==3){
            cout<<" "<<i;
                break;
        }

                    x/=10;if(x==0){break;}
        }
            
        }
        ++i;}
    cout<<endl;
        return 0;}

Measured memory_bytes: 3096
import java.util.*

fun main(args : Array<String>) {
    val sc = Scanner(System.`in`)
    val K = sc.nextInt() // 距離
    val N = sc.nextInt() // 家の数
    var k = 0
    var  A = arrayListOf<Int>()
    for (i in 0..N-1) {
        A.add(sc.nextInt())
        if (i > 0) {
            k = Math.max(Math.abs(A.get(i) - A.get(i -1)), k)
        }
    }
    if (A.get(0) + (K -A.get(N -1)) > k) {
        k = A.get(0) + (K -A.get(N -1))
    }
    print(K - k)
}


Measured memory_bytes: 77452
n = gets.to_i
a = Array.new(n, 0)
n.times {|i| a[i] = gets.to_i}
cnt = 0

insertion_sort = ->(a, g) {
  g.upto(n - 1) do |i|
    v = a[i]
    j = i - g
    while j >= 0 and a[j] > v
      a[j + g] = a[j]
      j -= g
      cnt += 1
    end
    a[j + g] = v
  end
}

i = (n == 1) ? 1 : n / 2
g = []
while i > 0
  g << i
  i /= 2
end
m = g.size
g.each {|i| insertion_sort.(a, i)}

puts m
puts g.join(" ")
puts cnt
puts a


Measured memory_bytes: 14660
import java.util.*;class Main{public static void main(String[]z){for(Scanner s=new Scanner(System.in);(n=i=s.nextInt())>0;f("",0),System.out.println(u.size()))for(k=s.nextInt(),a=new int[n],b=a.clone(),u=new HashSet<String>();i-->0;)a[i]=s.nextInt();}static int n,k,a[],b[],i;static Set<String>u;static void f(String r,int t){if(t==k)u.add(r);else for(int i=n;i-->0;)if(b[i]<1){f(r+a[i],b[i]=t+1);b[i]=0;}}}

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

signed main() {

    int a[6];
    for ( int i = 0; i < 6; i++ ) cin >> a[i];
    if ( a[4] - a[0] > a[5] ) cout << ":(" << endl;
    else cout << "Yay!" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
//#include <regex>

/* g++ -g -std=c++0x */
/* g++ -g -std=c++11 */

using namespace std;

// std::ios::sync_with_stdio(false);

// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

const int maxn = 1e5;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };
int H,W,N, A[maxn], ans[110][110];

int main()
{
/* #ifndef ONLINE_JUDGE */
/*     freopen("foo", "rt", stdin); */
/* #endif */
    while (cin >> H >> W >> N) {
        memset(ans,-1,sizeof(ans));
        FOR(i,0,N)
            cin >> A[i];
        int d = 0, x = 0, y = -1;
        FOR(i,0,N) FOR(j,0,A[i]) FOR(_,0,2) {
            const int X = x+dx[d];
            const int Y = y+dy[d];
            if (0 <= X && X < H && 0 <= Y && Y < W && ans[X][Y] == -1) {
                x = X; y = Y; ans[x][y] = i; break;
            }
            else {
                d++; d %= 4;
            }
        }
        FOR(i,0,H) {
            FOR(j,0,W)
                cout << ans[i][j]+1 << ' ';
            cout << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 384
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>


using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x*x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define loop(n) FOR(i,0,n)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

//写経して、レッドコーダーを感じる儀式
int main() {
	int ki[100001] = { 0 };
	int gu[100001] = { 0 };

	int n; cin >> n;

	//0,…n-1を偶奇で二分割
	for (int i = 0; i < n / 2; i++) {
		int u, v; cin >> u >> v;
		ki[u]++;
		gu[v]++;
	}

	//奇数の1,2番目と
	//偶数の1,2番目を管理したい。
	//1,2番目を知りたいだけなので、いちいちマップを使わなくても4つ変数使うことで
	//対処できたらものすごい楽。
	int ka = 0, kb = 0, ga = 0, gb = 0;

	//11b2222a33333
	//iはソートされていないので、
	//上の1,2,3のどこにくるかはわからない。
	//bより大きければ更新が発生するが、3だった場合aとbが逆転しているので
	//元に戻してやる必要がある

	for (int i = 0; i <= 100000; i++) {
	
		//ki[kb]より大きい要素があったら添字を更新する。
		if (ki[kb] < ki[i]) { kb = i; }

		//2番目が1番を追い越していたら、交換して正しい順位に戻す。
		if (ki[ka] < ki[kb]) { swap(ka, kb); }
		
		//偶数も同様
		if (gu[gb] < gu[i]) { gb = i; }
		if (gu[ga] < gu[gb]) { swap(ga, gb); }
	}

	//考察の通り、偶数と奇数で衝突が起きているかいないかで、変わる。
	//最頻値に衝突が起きていないなら
	//n/2-最頻値で最頻値以外を書き換えるのを偶奇でそれそれやればよい。

	//衝突が起きているならa1-b2,a2-b1の組合せを全部試す。


	if (ka != ga) { cout << n - (ki[ka] + gu[ga]) << endl; }
	else { cout << n - max(ki[ka] + gu[gb], ki[kb] + gu[ga]) << endl; }

	return 0;
}

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

template <int MOD_> struct modnum {
	static constexpr int MOD = MOD_;
	static_assert(MOD_ > 0, "MOD must be positive");
 
private:
	using ll = long long;
 
	int v;
 
	static int minv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
	}
 
public:
 
	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
 
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
 
	modnum inv() const {
		modnum res;
		res.v = minv(v, MOD);
		return res;
	}
	modnum neg() const {
		modnum res;
		res.v = v ? MOD-v : 0;
		return res;
	}
 
	modnum operator- () const {
		return neg();
	}
	modnum operator+ () const {
		return modnum(*this);
	}
 
	modnum& operator ++ () {
		v ++;
		if (v == MOD) v = 0;
		return *this;
	}
	modnum& operator -- () {
		if (v == 0) v = MOD;
		v --;
		return *this;
	}
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= o.inv();
	}
 
	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
using num = modnum<int(1e9) + 7>;

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

	int N[2]; cin >> N[0] >> N[1];
	num prod = 1;
	for (int z = 0; z < 2; z++) {
		num sum = 0;
		int prv = 0;
		for (int i = 0; i < N[z]; i++) {
			int v; cin >> v;
			if (i) {
				sum += num(v - prv) * i * (N[z] - i);
			}
			prv = v;
		}
		prod *= sum;
	}

	cout << prod << '\n';

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,x,sum=0;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>x;
        sum+=x;
    }
    n-=sum;
    if(n>=0) cout<<n<<endl;
    else cout<<"-1"<<endl;
    return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define x1 jfkljfewlkjfwekl
#define x2 jkfwejklfwej
#define y1 kfewfe
#define y2 jfwekj3w3e
 
int bomb[50][50];
 
 int counter = 0;
int a[50][50] = {
	{0,0,0,0},
	{0,0,0,0},
	{1,1,0,0},
	{1,1,0,0},
};
int myquery(int x1,int x2,int y1,int y2){
	int sum = 0;
	for(int i = y1 ; i <= y2 ; i++)
		for(int j = x1 ; j <= x2 ; j++)
			sum += a[i][j];
	return sum;
}
int query(int x1,int x2,int y1,int y2){
	counter++;
	cout << "? " << y1 << " " << x1 << " " << y2 << " " << x2 << endl;
	//return myquery(x1,x2,y1,y2);
	int sum;
	cin >> sum;
	return sum;
}

void color(int x1,int x2,int y1,int y2,int prv){
	for(int i = y1 ; i <= y2 ; i++)
		for(int j = x1 ; j <= x2 ; j++)
			bomb[i][j] = 1;
}

pair<int,int> dfs(int x1,int x2,int y1,int y2,int prv){
	int area = 	(x2-x1+1) * (y2-y1+1);
	if( x1 > x2 or y1 > y2 ) return {0,0};
	
	int ask = prv == -1 ? query(x1,x2,y1,y2) : prv;
	//cout << ask << endl;
	if( ask == (x2-x1+1) * (y2-y1+1) ){
		int ans = 0;
		for(int i = y1 ; i <= y2 ; i++)
			for(int j = x1 ; j <= x2 ; j++)
				bomb[i][j] = 1;
		return {ask,area};
		
	}else if( ask == 0 ){
		 return {0,area};
	}
	int X = (x1+x2) / 2;
	int Y = (y1+y2) / 2;
	int white = area-ask;
	auto a = dfs(x1,X,y1,Y,-1);
	white -= a.second - a.first;
	if( a.first == ask ) return {ask,area};
	
	if( white == 0 ){
		for(int i = y1 ; i <= y2 ; i++){
			for(int j = x1 ; j <= x2 ; j++){
				color(X+1,x2,y1,Y,-1);
				color(x1,X,Y+1,y2,-1);
				color(X+1,x2,Y+1,y2,-1);
			}
		}
		return {ask,area};
	}
				
			
	auto b = dfs(X+1,x2,y1,Y,-1);
	white -= b.second - b.first;
	if( a.first+b.first == ask ) return {ask,area};
	if( white == 0 ){
		for(int i = y1 ; i <= y2 ; i++){
			for(int j = x1 ; j <= x2 ; j++){
				color(x1,X,Y+1,y2,-1);
				color(X+1,x2,Y+1,y2,-1);
			}
		}
		return {ask,area};
	}
		
	
	auto c = dfs(x1,X,Y+1,y2,-1);
	
	if( a.first+b.first+c.first == ask ) return {ask,area};
	white -= c.second - c.first;
	if( white == 0 ){
		for(int i = y1 ; i <= y2 ; i++){
			for(int j = x1 ; j <= x2 ; j++){
				color(X+1,x2,Y+1,y2,-1);
			}
		}
		return {ask,area};
	}
	auto d = dfs(X+1,x2,Y+1,y2,ask-a.first-b.first-c.first);
	return {ask,area};
	
}
signed main(){
	int H,W,N,K;
	cin >> H >> W >> N >> K;
	for(int i = 0 ; i < N ; i++)
		a[rand()%H][rand()%W] = 1;
	//dfs(0,W-1,0,H-1,-1);
	
	long long ans = 0;
	long long w = 1;
	int ww = 50;
	for(int i = 0 ; i < H ; i+=ww){
		for(int j = 0 ; j < W ; j += ww){
			dfs(i,min(i+ww-1,H-1),j,min(j+ww-1,W-1),-1);
		}
	}
	for(int i = 0 ; i < H ; i++){
		for(int j = 0 ; j < W ; j++){
			ans += w * bomb[i][j];
			ans %= K;
			w *= 2;
			w %= K;
		}
	}
	
	cout << "!" << " " << ans << endl;
	cout << counter << endl;
}

Measured memory_bytes: 724
import java.util.Scanner;

class Main{
	public static void main(String arg[]) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		long x = sc.nextLong();
		sc.close();
		
		System.out.println(calc(a,b,x));
	}
	
	public static long calc(long a, long b, long x){
		return (b + x)/ x - (a + x - 1) / x;
	}
}

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

/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
*/

using namespace std;

#if DEBUG && !ONLINE_JUDGE
    #include "debug.h"
#else
    #define debug(...)
#endif

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<vector<int> > vvi;
typedef vector<vector<ii> > vvii;

#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define fill(a,x) memset(a,x,sizeof(a))
#define ff first
#define ss second
#define trav(a, x) for(auto& a : x) 
#define FOR(i,a,b) for(int i = a; i<=b; ++i)
#define NFOR(i,a,b) for(int i = a; i>=b; --i)
const ll INF = 1e18;
const int mod = 1e9 + 7;
ll gcd(ll a,ll b){if (a==0) return b;return gcd(b%a,a);}
ll lcm(ll a,ll b){return a*(b/gcd(a,b));}
ll Abs(ll a){if(a>0)return a;return -a;}
ll Ceil(ll a,ll b){if(a%b==0)return a/b;else return a/b+1;}
double Abs(double a){if(a>0)return a;return -a;}

//*X.find_by_order(2) element at index=2
//X.order_of_key(1) how many elements strictly less than 1

//#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_NOde_update> 

inline int pow_(ll x, ll y,ll p){
  int r = 1; while(y){if(y & 1) r = r * x % p; y >>= 1; x = x * x % p;} return r;
}
inline int inv_(int x){return pow_(x, mod - 2, mod);}
inline int add(int a, int b){a += b; if(a >= mod) a -= mod; return a;}
inline int mul(int a, int b){return a * 1LL * b % mod;}
inline int sub(int a, int b){a -= b; if(a < 0) a += mod; return a;}

int main()
{
    #ifdef LOCAL_TEST
    freopen("in.txt","r",stdin);
    //freopen("out.txt", "w", stdout);
    #else
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    #endif
    string s;
    cin>>s;
    string t = s.substr(0,1);
    int cnt = 1;
    for(int i=1;i<s.size();i++){
        if(t.size() == 1){
            if(s[i] == t[0]){
                if(i < s.size()-1){
                    t = s.substr(i,2);
                    i++;
                    cnt++;
                }
            } else {
                t = s.substr(i,1);
                cnt++;
            }
        } else {
            t = s.substr(i,1);
            cnt++;
        }
    }

    cout << cnt << "\n";
    return 0;   
}

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

#define for_(i,a,b) for(int i=a;i<b;++i)
#define for_rev(i,a,b) for(int i=a;i>=b;--i)
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define allof(a) a.begin(),a.end()
#define minit(a,b) memset(a,b,sizeof(a))
#define size_of(a) (int)a.size()
#define mp make_pair

typedef long long lint;
typedef double Double;
typedef pair< int, int > pii;
typedef unsigned long long ull;
typedef pair<string,int> psi;

const ull B = 1000000007;

int n,q;
string s[100010];
psi ns[100010];
set<int> ss;
vector<ull> v[100010];
int id[100010];

int main() {
	scanf("%d",&n);
	rep(i,n){
		cin>>s[i];
		ns[i]=mp(s[i],i);
		v[i].resize((int)s[i].size()+1);
		ull t=0;
		rep(j,s[i].size()){
			t=t*B+s[i][j];
			v[i][j]=t;
		}
	}
	sort(ns,ns+n);
	rep(i,n) id[ns[i].second]=i;
	scanf("%d",&q);
	while(q--){
		int k,p;
		scanf("%d %d",&k,&p);
		--p;
		if(k==1)ss.insert(id[p]);
		else if(k==2)ss.erase(id[p]);
		else{
			auto it=ss.lower_bound(id[p]);
			int f=0,ret;
			if(it==ss.end())ret=-1;
			else{
				int t=ns[*it].second,l=s[p].size();
				if((int)s[t].size()>=l&&v[t][l-1]==v[p][l-1])f=1;
				if(!f)ret=-1;
				else ret=t+1;
			}
			printf("%d\n",ret);
		}
	}
}


Measured memory_bytes: 28116
#include <algorithm>
    #include <iostream>
    #include <vector>
     
    using namespace std;
     
    typedef long long ll;
     
    #define MOD 1000000007
     
    ll dp[1010][30303];
     
    int main() {
      int h, n;
      cin >> h >> n;
      vector<int> a(n), b(n);
      for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
      }
      for (int i = 0; i <= 30000; ++i) {
        dp[0][i] = 1e18;
      }
      dp[0][0] = 0;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= 30000; ++j) {
          if (j < a[i]) {
            dp[i + 1][j] = dp[i][j];
          } else {
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - a[i]] + b[i]);
          }
        }
      }
      ll ans = 1e18;
      for (int i = h; i <= 30000; ++i) {
        ans = min(ans, dp[n][i]);
      }
      cout << ans << endl;
      return 0;
    }

Measured memory_bytes: 237824
n=input()
if len(n)==3:
  i=2
if len(n)==2:
  i=1
if len(n)==1:
  i=0
  
hon=['2','4','5','7','9']
pon=['0','1','6','8']
bon=['3']

if hon.count(n[i])==1:
  print('hon')
elif pon.count(n[i])==1:
  print('pon')
else:
  print('bon')



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

typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

const int Mx=1e6+11;
const double PI = acos(-1);
#define MOD 1000000007

#define nl '\n'
#define pb push_back
#define F first
#define S second
#define I insert
#define mp make_pair

#define sz(x) x.size()
#define tt int t; cin>>t; while(t--)
#define be(a) (a).begin(),(a).end()
#define rbe(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a,b,sizeof(a))
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl

#define su ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define frac cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

void f()
{
  int n,l;
  string s;
  cin>>n;
  pair<string, pair<int ,int> > p[n];
  for(int i=0;i<n;i++)
  {
    cin>>s>>l;
    p[i]=mp(s,mp(-1*l,i+1));
  }
  sort(p,p+n);
  for(auto i:p)
  {
    cout<<i.S.S<<nl;
  }
}

int main()
{
    su;
    f();
    return 0;
}


Measured memory_bytes: 3676
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)

int n, d, x;
int a[101];
int main()
{
	cin >> n >> d >> x;
	REP(i, 0, n) cin >> a[i];

	REP(i, 0, n) {
		x++;
		x += ((d - 1) / a[i]);
	}
	cout << x << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
    public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String S = br.readLine();
	char array[] = S.toCharArray();
	Arrays.sort(array);
	if (array[0] == array[1] && array[1] != array[2] && array[2] == array[3])
	    System.out.println("Yes");
	else
	    System.out.println("No");
    }
}

Measured memory_bytes: 23124
#include <iostream>
#include <fstream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <bitset>

typedef long long ll;
using std::vector;
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) {
    vec.resize(len);
    for (auto &v : vec) ndarray(v, args...);
}

//////////////////////////////////////

//////////////////////////////////////

int main() {
    //std::ifstream in("0_normal_2");
    //std::cin.rdbuf(in.rdbuf());
    
    int N;
    std::cin >> N;
    std::string S;
    std::cin >> S;
    
    //dp[i+1][j+1] = i-l+1~i文字目までと、j-l+1~j文字目までで共通する長さl
    //dp[0][0] = 0
    vector<vector<int>> dp;
    ndarray(dp, N+1, N+1);
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (S[i] == S[j]) {
                dp[i+1][j+1] = dp[i][j] + 1;
                
                if (dp[i+1][j+1] <= j - i) {
                    ans = std::max(ans, dp[i+1][j+1]);
                    //std::cout << S.substr(i-dp[i+1][j+1]+1, dp[i+1][j+1]) << ", ";
                    //std::cout << ans << std::endl;
                }
            }
        }
    }
    std::cout << ans << std::endl;
    
    return 0;
}


Measured memory_bytes: 98176
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <string.h>
#include <fstream>

using namespace std;


#define LL long long
#define ULL unsigned long long
#define N 1000220
#define M 5000100
#define MP make_pair
#define Pi acos(-1.0)
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define ls (rt << 1)
#define rs (ls | 1)
#define md ((ll+rr)/2)
#define lson ll, md, ls
#define rson md+1, rr, rs
#define mod 1000000007
#define inf 0x3f3f3f3f
#define sqr(x) ((x)*(x))
#define eps 1e-6
#define MP make_pair
#define uLL unsigned long long
LL powmod(LL a,LL b) {LL res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
#define F(x) ((x)/3+((x)%3 == 1 ? 0 : tb))
#define G(x) ((x)<tb ? (x)*3+1 : ((x) - tb)*3+2)
#define lowbit(x) ((x)&(-x))
#define fi first
#define se second
#define pii pair<int,int>
#define B 100000001
const LL INF = ~0u >> 1;

int gcd(int x,int y){
    while(y){
        int t = x % y;
        x = y;
        y = t;
    }
    return x;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

const int mask = (1 << 26) - 1;
char s[N];

int vis[10];

bool fckn(int n){
    while(n){
        if(vis[n % 10]) return false;
        
        n /= 10;
    }
    return true;
}
int main(){
    srand(time(0));
    //freopen("in.txt", "r", stdin);
    //freopen("in.txt", "w", stdout);
    //cout<<20<<endl;
    //int T = 20;
    //scanf("%d",&T);
    
    int n,k;
    scanf("%d%d",&n,&k);
    
    for(int i = 0; i < k; i++){
        int j;
        scanf("%d",&j);
        vis[j] = 1;
    }
    
    while(!fckn(n))
        n++;
    
    cout << n << endl;
    
    
    return 0;
}



Measured memory_bytes: 256
const input = require("fs").readFileSync("/dev/stdin", "utf8").split("\n");

const N = input[0].split(' ').map(item => parseInt(item))[0]
const H = input[1].split(' ').map(item => parseInt(item))

dp = new Array()
// console.log(dp)
dp[0] = 0
dp[1] = Math.abs(H[1] - H[0])
for (i=2; i<N; i++) {
    dp[i] = Math.min(dp[i-1] + Math.abs(H[i]-H[i-1]), dp[i-2] + Math.abs(H[i]-H[i-2]))
}

console.log(dp[N-1])


Measured memory_bytes: 27824
#include <cstdio>

int main()
{
	int N, T, c, t, min_c = (1 << 10);
	std::scanf("%d %d", &N, &T);

	for (int i = 0; i < N; i++) {
		std::scanf("%d %d", &c, &t);
		if (t <= T && c < min_c)
			min_c = c;
	}

	if (min_c & (1 << 10))
		std::printf("TLE\n");
	else
		std::printf("%d\n", min_c);

	return 0;
}

Measured memory_bytes: 128
//
//  main.cpp
//  ProCon
//
//  Created by hashimotoryoma on 2017/08/20.
//  Copyright © 2017年 hashimotoryoma. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <vector>

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

using namespace std;

typedef long long ll;

int group(int n){
    if(n==2)
        return 2;
    else if(n==4 || n==6 || n==9 || n==11)
        return 1;
    else
        return 0;

}

int main() {
    // insert code here...    return 0;
    //////
    // input from txt
    /*
     std::ifstream in("input.txt");
     std::cin.rdbuf(in.rdbuf());
     std::ofstream out("output.txt");
     std::cout.rdbuf(out.rdbuf());
     ////
     */
    int n,m;
    cin >> n >> m;
    cout << (n-1)*(m-1) << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

B=[]
C=[]
Z=[]

for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)

B.sort(reverse=True)
C.sort(reverse=True)

if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*(-c)%mod

    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()

if K>len(B)+len(C):
    print(0)
    sys.exit()

if B==[]:
    if Z==[] and K%2==0:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS%mod)
            
    elif Z==[] and K%2==1:
        C.reverse()
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(-ANS%mod)
        
    elif K%2==1:
        print(0)
    else:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS%mod)

    sys.exit()

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)

        while True:
            if c_start+ind+1<len(C) and len(B)-2-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-1-ind]*B[len(B)-2-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-1-ind]*B[len(B)-2-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)+1

        while True:
            if c_start+ind+1<len(C) and len(B)-3-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-2-ind]*B[len(B)-3-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-2-ind]*B[len(B)-3-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    print(S%mod)
    


Measured memory_bytes: 31948
import java.util.*;
public class Main
{
	public static void main(String[] args) {
		Scanner s=new Scanner(System.in);
	int a=s.nextInt();
	int n=100003;
	boolean[] isPrime = new boolean[n+1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        // mark non-primes <= n using Sieve of Eratosthenes
        for (int factor = 2; factor*factor <= n; factor++) {

            // if factor is prime, then mark multiples of factor as nonprime
            // suffices to consider mutiples factor, factor+1, ...,  n/factor
            if (isPrime[factor]) {
                for (int j = factor; factor*j <= n; j++) {
                    isPrime[factor*j] = false;
                }
            }
        }
        
        if(isPrime[a])
        System.out.println(a);
        else{
            
            while(!isPrime[a])
            a++;
            System.out.println(a);
        }

}
}
	

Measured memory_bytes: 23508
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>

using namespace std;


void prime_factor(int n){
    int d = n;
    for(int i=2; i * i <= d; i++){
        while(n % i == 0){
            cout << " " << i;
            n /= i;
        }
    }

    if(n != 1) cout << " " << n;
}
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    cout << n << ":";
    prime_factor(n);
    cout << "\n";
    return 0;
}

Measured memory_bytes: 3228
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
#include<cstdio>
#include<cstdlib>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

const double EPS = 1e-10;

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;


int main(){
    string S; cin >> S;
    int ans = 0;
    if(S == "SAT") ans = 1;
    if(S == "FRI") ans = 2;
    if(S == "THU") ans = 3;
    if(S == "WED") ans = 4;
    if(S == "TUE") ans = 5;
    if(S == "MON") ans = 6;
    if(S == "SUN") ans = 7;
    cout << ans << endl;
}


Measured memory_bytes: 256