akhauriyash/Code-Regression huggingface dataset:
N, M, K = map(int, input().split())
table = [-1]*N
def union(x, y):
    global table
    x, y = find(x), find(y)
    if x==y:
        return False
    else:
        if table[x]>table[y]:
            x, y = y, x
        table[x] += table[y]
        table[y] = x
        return True
def find(x):
    if table[x]<0:
        return x
    else:
        table[x] = find(table[x])
        return table[x]
def rank(x):
    return table[find(x)]
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
    union(a-1, b-1)

for _ in range(K):
    c, d = map(int, input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

ans = [""]*N
for i in range(N):
    tmp = abs(rank(i)) - len(friend[i]) - 1
    cnt = 0
    for b in block[i]:
        if find(i)==find(b):
            cnt += 1
    ans[i] = str(tmp - cnt)
print(" ".join(ans))

Measured memory_bytes: 54836
from collections import defaultdict

N = int(input())
S = defaultdict(int)

for _ in range(N):
    s = input()
    S[s] += 1

poll = defaultdict(list)
for k, v in S.items():
    poll[v].append(k)

ans = sorted(poll[max(poll.keys())])

for a in ans:
    print(a)

Measured memory_bytes: 33364
#include<stdio.h>
#include<string.h>
 
int main(){
	
	//準備部分
	char ch[201]={},ch1[200]={},ch2[200]={};
	int m,h,len,i,j;
	
	//入力・処理・出力部分
	while(1){
		scanf("%s",ch);
		if(ch[0]=='-')break;
		len=strlen(ch);
		scanf("%d",&m);
		for(i=0;i<m;i++){
			scanf("%d",&h);
			for(j=0;j<h;j++)ch1[j]=ch[j];
			for(j=h;j<len;j++)ch2[j-h]=ch[j];
			//printf("%s %s\n",ch1,ch2);
			strcat(ch2,ch1);
			strcpy(ch,ch2);
			//printf("[%s]\n",ch);
			for(j=0;j<200;j++){
				ch1[j]=0;
				ch2[j]=0;
			}
		}
		printf("%s\n",ch);
	}
	
	return 0;
}


Measured memory_bytes: 2048
S = input()

before = False
after = False
if 0 < int(S[0:2]) <= 12:
    before = True

if 0 < int(S[2:4]) <= 12:
    after = True

if before and after:
    print("AMBIGUOUS")
elif before:
    print("MMYY")
elif after:
    print("YYMM")
else:
    print("NA")


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main()
{

    int x, a;
    cin >> x >> a;

    int ans;

    if(x<a)
        ans = 0;
        else
        {
            ans = 10;
        }
        

    cout << ans <<"\n";

    return 0;
}

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

int main() {
  int a,b;
  cin >> a >> b;
  int count = 0;
  for(int i = 1;i < 1000;i++) {
    count = count + i;
    if(i == b - a) {
      break;
    }
  }
  cout << count - b << endl;
}

Measured memory_bytes: 256
n,*a=map(int,open(0).read().split())
a.sort()
num=[True for i in range(a[-1]+1)]
for i in range(n):
  if num[a[i]]:
    for j in range(a[-1]//a[i]+1):
      if j<2:
        continue
      num[a[i]*j]=False
    if i==n-1:
      pass
    elif a[i]==a[i+1]:
      num[a[i]]=False
    else:
      pass
  else:
    continue
ans=0
for i in range(n):
  if num[a[i]]:
    ans+=1
print(ans)

Measured memory_bytes: 33024
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = long.Parse(line[0]);
        var b = long.Parse(line[1]);
        var x = long.Parse(line[2]);
        var ret = b / x - a / x;
        if (a % x == 0) ret++;
        Console.WriteLine(ret);
    }
}


Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
int n,m,chk[15];
char s[15][15],t[15][15];
vector<pair<int,int> >pick;
void go(int r)
{
	if(r<=1)
	{
		int x=-1;
		for(int i=0;i<n;i++)
		{
			if(chk[i]==2)
			{
				x=i;
			}
		}
		int y=0;
		for(int i=0;i<pick.size();i++)
		{
			for(int j=0;j<m;j++)
			{
				t[y][j]=s[pick[i].first][j];
			}
			y++;
		}
		if(x>=0)
		{
			for(int j=0;j<m;j++)
			{
				t[y][j]=s[x][j];
			}
			y++;
		}
		for(int i=pick.size()-1;i>=0;i--)
		{
			for(int j=0;j<m;j++)
			{
				t[y][j]=s[pick[i].second][j];
			}
			y++;
		}
		vector<string>p;
		for(int j=0;j<m;j++)
		{
			string s="";
			for(int i=0;i<n;i++)
			{
				s+=t[i][j];
			}
			p.push_back(s);
		}
		for(int i=0;i<p.size();i++)
		{
			string s=p[i];
			reverse(s.begin(),s.end());
			for(int j=i+1;j<p.size();j++)
			{
				if(s==p[j])
				{
					p.erase(p.begin()+j);
					p.erase(p.begin()+i);
					i--;
					break;
				}
			}
		}
		if(p.size()==1)
		{
			string s=p[0];
			reverse(s.begin(),s.end());
			if(p[0]!=s)
			{
				return;
			}
		}
		if(p.size()<=1)
		{
			cout<<"YES"<<endl;
			exit(0);
		}
	}
	else
	{
		int x;
		for(int i=0;i<n;i++)
		{
			if(!chk[i])
			{
				x=i;
				break;
			}
		}
		chk[x]=1;
		for(int i=x+1;i<n;i++)
		{
			if(!chk[i])
			{
				chk[i]=1;
				pick.push_back(make_pair(x,i));
				go(r-2);
				pick.pop_back();
				chk[i]=0;
			}
		}
		chk[x]=0;
	}
}
void slove()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>s[i][j];
		}
	}
	if(n%2)
	{
		for(int i=0;i<n;i++)
		{
			chk[i]=2;
			go(n-1);
			chk[i]=0;
		}
	}
	else
	{
		go(n);
	}
	cout<<"NO"<<endl;
}
int main()
{
	slove();
	return 0;
}

Measured memory_bytes: 256
// AtCoder Beginner Contest 125 - Problem A: Biscuit Generator (https://atcoder.jp/contests/abc125/tasks/abc125_a)
#include <bits/stdc++.h>

using namespace std;

int solve(int A, int B, int T)
{
    return B*(T/A);
}

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

    int A, B, T;
    cin >> A >> B >> T;

    auto ans = solve(A, B, T);

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main() {
	int a, b, c, d, sa = 0,max=0;
	scanf("%d%d%d%d", &a, &b, &c, &d);

	if (a >= c) {
		sa = a - c;
		max = a;
		
	}
	else if (c >= a) {
		sa = c - a;
		max = c;
	}
	if (sa <= d) {
		printf("Yes\n");
		return 0;
	}
	else if (sa > d) {
		if (max - b >= d)printf("No\n");
		else if (max - b <= d)printf("Yes\n");

	}
	return 0;

}

Measured memory_bytes: 128
input = STDIN.read.split("\n").map{|l| l.split(" ").map{|i| i.to_i}}
drops = input[0][1]
requires = input[1]
sorted_requires = requires.sort

funs = 0
sorted_requires.each do |r|
  if drops < r
    drops = 0
    break
  end

  drops = drops - r
  funs = funs + 1
end

if drops != 0
  funs = funs - 1
end

puts funs


Measured memory_bytes: 1788
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <fstream>
#include <iterator>
using namespace std;
// #include "prettyprint.hpp"

typedef long long ll;

int main()
{
    ll N;
    cin >> N;
    ll A, B, C, D, E;
    cin >> A >> B >> C >> D >> E;
    ll ans = ceil(double(N) / min({A, B, C, D, E})) + 4;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<vector>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using namespace std;

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define CEVCOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define P pair<int , int>
#define V vector<int>
#define M map<int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>
int gcd(int a , int b){

  if(b == 0)  return a;

  return gcd(b , a % b);
}

int main(void){

  int N;    cin >> N;
  V a(N + 1), b(N + 1), c(N + 2);   b[0] = 0; c[N + 1] = 0;
  for(int i = 1 ; i <= N ; i++)	  cin >> a[i];

  for(int i = 1 ; i <= N ; i++)
    b[i] = gcd(a[i] , b[i - 1]);

  for(int i = N ; 1 <= i ; i--)
    c[i] = gcd(a[i] , c[i + 1]);

  int ans = 0;
  for(int i = 1 ; i <= N ; i++)
      ans = max(ans , gcd(b[i - 1] , c[i + 1]));

  SCOUT(ans) << endl;

    return 0;
}


Measured memory_bytes: 1408
#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> 

using namespace std;

#define _int64 long long

vector<int> a[200000];
int ans[200000];
int used[200000];

int main()
{
  int i,j,x,y,xx,yy,n,m,b1,st,ed;
  scanf("%d%d",&n,&m);
  for (i=0;i<n;i++)
    a[i].clear();
  for (i=0;i<m;i++)
  {
    scanf("%d%d",&x,&y);
    x--;y--;
    a[x].push_back(y);
    a[y].push_back(x);
    xx=x;yy=y;
  }
  memset(used,0,sizeof(used));
  ans[100000]=xx;ans[100001]=yy;
  st=100000;ed=100001;
  used[xx]=1;used[yy]=1;
  b1=1;
  while (b1==1)
  {
    b1=0;
    x=ans[st];
    for (i=0;i<a[x].size();i++)
      if (used[a[x][i]]==0)
      {
        y=a[x][i];
        b1=1;
        used[y]=1;
        st--;
        ans[st]=y;
        break;
      }
  }
  b1=1;
  while (b1==1)
  {
    b1=0;
    x=ans[ed];
    for (i=0;i<a[x].size();i++)
      if (used[a[x][i]]==0)
      {
        y=a[x][i];
        b1=1;
        used[y]=1;
        ed++;
        ans[ed]=y;
        break;
      }
  }
  printf("%d\n",ed-st+1);
  for (i=st;i<=ed;i++)
  {
    if (i!=st) printf(" ");
    printf("%d",ans[i]+1);
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 9856
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

#define INF 1000000009LL
int N, M;

int dp[100005];

int dfs(vector<vector<int>> &v, int node) {
  if (dp[node] != -1) return dp[node];
  else {
    dp[node] = 0;
    for (int i = 0; i < v[node].size(); i++) {
      dp[node] = max(dp[node], dfs(v, v[node][i]) + 1);
    }
    return dp[node];
  }
}

int main() {
  int N, M; cin >> N >> M;
  vector<vector<int>> edge(N);
  for (int i = 0; i < M; i++) {
    int v, t; cin >> v >> t;
    edge[v-1].push_back(t-1);
  }
  
  for (int i = 0; i < N; i++) dp[i] = -1;
  
  int ans = 0;
  for (int i = 0; i < N; i++) {
    ans = max(ans, dfs(edge, i));
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 8192
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  int n,q,l,r;
  string s;
  cin>>n>>q>>s;
  int sum[100010];
  sum[0]=0;
  for(int i=1;i<n;i++)
  {
    if(s[i]=='C' && s[i-1]=='A') sum[i]=sum[i-1]+1;
    else sum[i]=sum[i-1];
  }
  // for(int i=0;i<n;i++) cout<<sum[i]<<endl;
  for(int i=1;i<=q;i++)
  {
    cin>>l>>r;
    l--,r--;
    cout<<sum[r]-sum[l]<<endl;
  }
  return 0;
}


Measured memory_bytes: 1408
#include <stdio.h>
 
int main(void){
    int a,b;
   char op;
        while(1){
          scanf("%d %c %d",&a,&op,&b);
           if( op =='?')
               break;
           else if( op == '+')
               printf("%d\n",a+b);
           else if( op == '-')
               printf("%d\n",a-b);
           else if( op == '*')
               printf("%d\n",a*b);
           else if( op == '/')
               printf("%d\n",a/b);
           }
              return 0;
}
      
 


Measured memory_bytes: 2048
import java.util.Stack;
import java.util.Scanner;
import java.math.BigDecimal;

public class Main {
    public static Scanner sc = new Scanner(System.in);
    public static long res = 0;
    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        while (sc.hasNext()) {
            BigDecimal a = new BigDecimal(sc.next());
            BigDecimal b = new BigDecimal(sc.next());
            a = a.add(b);
            String s = a.toPlainString();
            if (s.length() > 80) {
                System.out.println("overflow");
            } else {
                System.out.println(s);
            }
        }
    }
}

Measured memory_bytes: 26652
N, M, C, = map(int, input().split())
B = list(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(N)]

cnt = 0
for a in range(N):
    math_list = []
    for b in range(M):
        math_list.append(A[a][b] * B[b])
    if sum(math_list) + C > 0:
        cnt += 1

print(cnt)

Measured memory_bytes: 9040
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;

public static class P
{
    public static void Main()
    {
        var ab = Console.ReadLine().Split().Select(decimal.Parse).ToArray();
        Console.WriteLine(Floor((ab[0] * ab[1])));
    }
}


Measured memory_bytes: 28332
#include <stdio.h>
int main(void)
{
	char S[256];
	int N = 0;
	int K = 0;

	scanf("%d %d",&N,&K);
	scanf("%s",&S);

	if (S[K - 1] == 'A')
	{
		S[K - 1] = 'a';
	}

	if (S[K - 1] == 'B') {
		S[K - 1] = 'b';
	}

	if (S[K - 1] == 'C') {
		S[K - 1] = 'c';
	}

	printf("%s\n",S);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> void cmax(T& a, U b) { if (a<b) a = b; }
template<class T, class U> void cmin(T& a, U b) { if (a>b) a = b; }

const ll MOD = 1e9+7;
const int MAX = 50000;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() { fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

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

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

  int n, k;
  cin >> n >> k;

  COMinit();

  for (int i = 1; i <= k; i++) {
    cout << COM(n-k+1, i) * COM(k-1, i-1) % MOD << endl;
  }
}


Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <tuple>
#include <string>

using namespace std;

int main(){
  int N; cin>>N;
  vector<long long> X(N,0),A(N,0);

  for(long long i=0;i<N;i++){
    long long temp; cin>>temp;
    X[i]=temp;A[i]=temp;
  }

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

  long long num0= X[N/2-1], num1=X[N/2];

  for(long long i=0;i<N;i++){
    if(A[i]<num1) cout<<num1<<endl;
    else cout<<num0<<endl; 
  }

  return 0;
}



Measured memory_bytes: 5376
import sys
from builtins import map
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
from heapq import heappush, heappop
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy4, dx4 = [0, -1, 0, 1], [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    A, B = map(int, input().split())
    S = input()

    ans = "Yes"
    for i in range(A):
        if not S[i].isdigit():
            ans = "No"
    if S[A] != "-":
        ans = "No"

    for i in range(A + 1, A + B + 1):
        if not S[i].isdigit():
            ans = "No"
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3960
function inI()
    a = Ref{Int64}(0)
    ccall(:scanf, Int32, (Ptr{UInt8}, Ref{Int64},), "%lld", a)
    a[]
end

function outI(x::Int64)
    ccall(:printf, Void, (Ptr{UInt8}, Int64), "%lld\n", x)
end

@inbounds let
    n = inI()
    x = [inI() for _ in 1:n]
    l = inI()
    q = inI()
    const lg = 20
    F = Array(Int, lg, n)
    B = Array(Int, lg, n)
    for i = 1:n
        F[1,i] = searchsortedlast(x, x[i]+l)
        B[1,i] = searchsortedfirst(x, x[i]-l)
    end

    for fe = 2:lg
        for i = 1:n
            F[fe,i] = F[fe-1,F[fe-1,i]]
            B[fe,i] = B[fe-1,B[fe-1,i]]
        end
    end

    for i = 1:q
        a = inI()
        b = inI()

        ans = 1
        if a < b
            for fe = lg:-1:1
                if F[fe,a] < b
                    a = F[fe,a]
                    ans += 2^(fe-1)
                end
            end
        else
            for fe = lg:-1:1
                if B[fe,a] > b
                    a = B[fe,a]
                    ans += 2^(fe-1)
                end
            end
        end
        outI(ans)
    end
end


Measured memory_bytes: 102068
import bisect

INF = 10 ** 9 + 1

N = int(input())
S = [int(input()) for l in range(N)]
L = [S[0]]

for i in range(1, N):
    if L[-1] < S[i]:
        L.append(S[i])
    else:
        L[bisect.bisect_left(L, S[i])] = S[i]

print(len(L))



Measured memory_bytes: 10352
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for _ in range(M):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    data.append((a,b))
par = [i for i in range(N+1)]
rank = [0] * (N+1)
size = [1] * (N+1)

def find(x):
    if par[x] == x:
        return par[x]
    else:
        par[x] = find(par[x])
        return par[x]

def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
        size[y] += size[x]
        size[x] = 0
        
    else:
        par[y] = x
        size[x] += size[y]
        size[y] = 0
        if rank[x] == rank[y]:
            rank[x] += 1

def check_same(x,y):
    return find(x) == find(y)

def check_size(x):
    return size[find(x)]

score = (N*(N-1))//2
ans = []

while data:
    ans.append(score)
    x,y = data.pop()
    a = find(x)
    b = find(y)
    if not check_same(a,b):
        score -= (check_size(x)*check_size(y))
    union(x,y)
print(*ans[::-1],sep="\n")


Measured memory_bytes: 24752
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vb=vector<bool>;
using pii=pair<int,int>;
using vpii=vector<pair<int,int>>;
using plli=pair<ll,int>;
using vplli=vector<pair<ll,int>>;
using pllll=pair<ll,ll>;
using vpllll=vector<pair<ll,ll>>;

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
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;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)
//試験導入
#define irep(i, end_i, begin_i) for (ll i = (ll)begin_i-1; i >= (ll)end_i; i--)

long long INF = 1LL<<60;
int main( ){
    ll N;
    cin>>N;
    vll cnt(N+1,0);
    for(ll i=1;i*i<=N;i++){
        for(ll j=1;j*j<=N;j++){
            for(ll k=1;k*k<=N;k++){
                ll p=i*i+j*j+k*k+i*j+i*k+k*j;
                if(p<=N){
                    cnt[p]++;
                }
            }
        }
    }
    rep(i,1,N+1){
        cout<<cnt[i]<<endl;
    }
    return 0;
}




Measured memory_bytes: 3672
#include <bits/stdc++.h>
const int maxn = 1e5 + 10;
using namespace std;
int a[3][maxn];
int b[maxn];
int main()
{
    int n, k;
    cin >> n;
    int max1 = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[1][i];
        a[0][i] = a[1][i] - 1;
        a[2][i] = a[1][i] + 1;
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) {
            b[a[i][j]]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        max1 = max(max1, b[i]);
    }
    if (n == 1)
        cout << "1" << endl;
    else
        cout << max1 << endl;
    return 0;
}


Measured memory_bytes: 1792
#include<stdlib.h>
#include<limits.h>
#include<math.h>
#include<string.h>

int main(void){
	int k,n,i;
	int a[100000];

	scanf("%d %d",&n,&k);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	printf("%d\n",(n-k)/(k-1)+1+((n-k)%(k-1)!=0?1:0));
	
	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#define MAXN 1000005
#define PLI pair<long long,int>
#define fi first
#define se second
#define mp make_pair
#define ha 99994711
#define ba 823
//#define ivorysi
using namespace std;
typedef long long int64;
int N,Lim,dis;
int64 X,D,m[55],cost[55];
int p[55],siz[55],q[125005],id[55];
int64 dp[125005],ans;
int ql,qr;
bool cmp(int a,int b) {
	return siz[a] * cost[b] > siz[b] * cost[a];
}
void update(int64 &x,int64 y) {
	x = min(x,y);
}
void Solve() {
	scanf("%d%lld%lld",&N,&X,&D);
	Lim = N * N * N;
	scanf("%d",&m[1]);
	for(int i = 2 ; i <= N ; ++i) scanf("%d%d",&m[i],&p[i]);
	for(int i = N ; i >= 1 ; --i) {
		cost[i] += m[i];siz[i]++;
		cost[p[i]] += cost[i];siz[p[i]] += siz[i];
		id[i] = i;
	}
	for(int i = 1 ; i <= Lim ; ++i) dp[i] = X + 1;
	sort(id + 1,id + N + 1,cmp);
	dis = min(N,(int)D);
	for(int k = 1 ; k <= N ; ++k) {
		int s =  siz[id[k]];int64 v = cost[id[k]];
		for(int j = 0 ; j < s ; ++j) {
			int T = min((Lim - j)/ s,dis);
			if(id[k] == 1) T = min((Lim - j) / s,N);
			int p = (Lim - j) / s;
			ql = 1,qr = 0;
			for(int i = (Lim - j) / s ; i >= 1 ; --i) {
				while(p >= 0 && i - p <= T) {
					while(ql <= qr && dp[j + q[qr] * s] - q[qr] * v > dp[j + p * s] - p * v) --qr;		
					q[++qr] = p;
					--p;
				}
				while(ql <= qr && q[ql] >= i) ++ql;
				if(ql <= qr) {
					update(dp[j + i * s],dp[j + q[ql] * s] + (i - q[ql]) * v);
				}
			}
		}
	}
	for(int i = 0 ; i <= Lim ; ++i) {
		int64 T = X - dp[i];
		if(T < 0) continue;
		int64 tmp = i;
		int num;
		for(int k = 1 ; k <= N ; ++k) {
			if(id[k] == 1) num = T;
			else num = D - dis;
			int t = min(T / cost[id[k]],(int64)num);
			tmp += 1LL * t * siz[id[k]];
			T -= t * cost[id[k]];
		}
		ans = max(ans,tmp);
	}
	printf("%lld\n",ans);
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	Solve();
	return 0;
}

Measured memory_bytes: 1664
N = int(input())
A = [int(input()) for _ in range(N)]

A.sort()

ans = A[len(A) - 1] - A[0]
small = 0
large = len(A) - 1
while (True):

    if large - small == 1:
        break
    elif large - small == 2:
        ans += max(A[large] - A[large - 1], A[small + 1] - A[small])
        break
    ans += A[large - 1] - A[small] + A[large] - A[small + 1]
    small += 1
    large -= 1

print(ans)


Measured memory_bytes: 7504
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll pre,x,n,i,tot=0,c[200005],dp[200005],vis[200005],sum[200005];
const ll mod=1e9+7;
int main()
{
	pre=0;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&x);
		if(x!=pre)c[++tot]=x;
		pre=x;	
	}
	sum[0]=1;
	for(i=1;i<=tot;i++)
	{
		sum[i]=sum[i-1];
		if(vis[c[i]])sum[i]=(sum[i]+sum[vis[c[i]]])%mod;
		vis[c[i]]=i;
	}
	printf("%lld\n",sum[tot]);
	return 0;
} 

Measured memory_bytes: 6400
L = list(input())
T = input()
flag = 0
for i in range(len(L)) :
    L.append(L[0])
    L.pop(0)

    if T == "".join(L) :
        flag = 1
        break
if flag == 1 :
    print("Yes")
else :
    print("No")
    

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

#define EPS (1e-10)
#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)

using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;

constexpr int MOD = 1000000007;

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

    int k, x;
    cin >> k >> x;
    cout << (500 * k >= x ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
<?php
  $a = [];
  list($a[]) = explode(" ", trim(fgets(STDIN)));
  list($a[]) = explode(" ", trim(fgets(STDIN)));
  list($a[]) = explode(" ", trim(fgets(STDIN)));
  list($a[]) = explode(" ", trim(fgets(STDIN)));
  list($a[]) = explode(" ", trim(fgets(STDIN)));

  $min = 10;
  for ($i=0; $i<count($a); $i++) {
    if($a[$i] % 10 != 0){
      $min = min($min, $a[$i]%10);
    }
  }
  $ans = 0;
  for ($i=0; $i<count($a); $i++) {
    $ans += intdiv($a[$i] + 9, 10) * 10;
  }

  if($min != 10){
    $ans-=10;
    $ans+=$min;
  }

  echo $ans;

Measured memory_bytes: 16212
x1, y1, x2, y2 = map(int, input().split())

x3 = x2 - (y2 - y1)
y3 = y2 + (x2 - x1)
x4 = x3 - (x2 - x1)
y4 = y3 - (y2 - y1)

print(x3, end=' ')
print(y3, end=' ')
print(x4, end=' ')
print(y4)

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

int main() {
  int N;
  cin >> N;
  string s, t;
  cin >> s >> t;
  string u = "";
  for (int i = 0; i < N; i++) {
    u += (char)s[i];
    u+= (char)t[i];
  }
  cout << u << endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define SFOR(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define INF INT_MAX
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int main(){
   cin.tie(0);  
   ios::sync_with_stdio(false);
   int c=0,n,l,d[202],ans=0;
   cin>>n>>l;
   FOR(i,n){
     d[i]=l+i;
     ans+=d[i];
   }
   FOR(i,n){
    if(abs(ans-(ans-d[i]))<abs(ans-(ans-d[c]))) c=i;
   }
   cout<<ans-d[c]<<endl;
   return 0;
}



Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		ArrayList<Integer> w_list = new ArrayList<Integer>();
		
		int w = sc.nextInt();
		int n = sc.nextInt();
		
		for(int i = 0; i < w; i++){
			w_list.add(i + 1);
		}
		
		for(int i = 0; i < n; i++){
			String[] str = sc.next().split(",");
			
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);
			
			int tmp_a = w_list.get(a - 1);
			int tmp_b = w_list.get(b - 1);
			
			w_list.set(a - 1, tmp_b);
			w_list.set(b - 1, tmp_a);
		}
		
		print(w_list);
	}
	
	public static void print(ArrayList<Integer> a) {
		for(int i = 0; i < a.size(); i++)
			System.out.println(a.get(i));
	}
}

Measured memory_bytes: 17212
#include <stdio.h>
#include<string.h>

int main() {
    int a,b;
	scanf("%d %d", &a, &b);
	int l=a+b;
	int m=a-b;
	int n=a*b;
	if(l>=m) {
		if (l>=n) printf("%d", l);
		else printf("%d", n);	
	}
	else if ( m>=n)printf("%d", m);
	     else printf("%d", n);
	
	return(0);
	
}

Measured memory_bytes: 128
calcNum = [1, -1]
calcSign = ["+", "-"]
n = list(input())
for a in range(2):
    for b in range(2):
        for c in range(2):
            if int(n[0]) + calcNum[a] * int(n[1]) + calcNum[b] * int(n[2]) + calcNum[c] * int(n[3]) == 7:
                string = n[0] + calcSign[a] + n[1] + \
                    calcSign[b] + n[2] + calcSign[c] + n[3] + "=7"

print(string)


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, ans, i, j, k, x;
	cin >> n;
	set<int> s;
	while (n--) {
		cin >> x;
		s.insert(x);
	}
	cout << s.size() << "\n";

	return 0;
}



Measured memory_bytes: 256
n = int(input())
xy = []
for _ in range(n):
	xy.append([int(x) for x in input().split()])
dis = 0
for x1, y1 in xy:
	for x2, y2 in xy:
		#print(x1,y1,x2,y2)
		dis += ((x1 - x2)**2 + (y1 - y2)**2)**0.5
print(dis/n)

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

 
int main()
{
    
     long int n;
     cin>>n;
     set<string> s1;
     string s[n];
     long int i;
     for(i=0;i<n;++i)
        {
            cin>>s[i];
            s1.insert(s[i]);
        }
        
    cout<<s1.size();    

    
    
     return 0;   
         
  
  
}

Measured memory_bytes: 25476
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long int lli;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    lli a,b,n;
    cin>>a>>b>>n;
    lli x=min(b-1,n);
    lli i,cur;
    
    if(n>b-1)
    {
        cur=n-(b-1);
        cur/=b;
        x=(b-1)+cur*b;
    }
    // for(i=b-1;i<=n;i+=b)
    // {
    //     x=i;
    // }
    if(x==0) x=1;
    lli ans1=(a*x)/b;
    lli ans2=a*(x/b);
    cout<<ans1-ans2;
    return 0;
}

Measured memory_bytes: 3648
#include<iostream>
  
int const MOD = 1000000007;
int const MAXN = 100;
int const MAXK = 100000;

int N, K, a[MAXN];

int dp[MAXN+1][MAXK+1];

int calc(int n, int k) {
  if(dp[n][k] >= 0) return dp[n][k];
  int ret = (calc(n, k-1) + calc(n-1, k)) % MOD;
  int j = k-1-a[n-1];
  if(j >= 0) ret = (ret - calc(n-1, j) + MOD) % MOD;
  return dp[n][k] = ret;
}

int main() {
  std::cin >> N >> K;
  for(int i = 0; i < N; ++i) std::cin >> a[i];

  for(int i = 0; i <= N; ++i) for(int j = 0; j <= K; ++j) dp[i][j] = -1;
  for(int i = 0; i <= N; ++i) dp[i][0] = 1;
  for(int i = 1; i <= K; ++i) dp[0][i] = 0;
  std::cout << calc(N, K)  << std::endl;
  return 0;
}


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

using namespace std;

typedef long long       ll;

#define all(x)            (x).begin(),(x).end()
#define Sort(x)            sort(all(x))
#define A               first
#define B               second
#define sep             ' '
#define fast_io         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define set_random     mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())

const ll XN = 5e2+7,
         Md = 1e9+7;

ll n, ans, x , y, H, W, Ans[10];
vector <pair<ll, ll> > vec;
set <pair<ll, ll> > st;
unordered_map <ll, ll> mp;

void Solve(pair<ll, ll> num){
	ll jav = 0;
	for (int i = -1; i < 2; ++i){
		for (int j = -1; j < 2; ++j){
			if (mp[(num.A+i)*Md+(num.B+j)])	++jav;
		}
	}
	++Ans[jav];
}

int main(){
	fast_io;
	cin >> H >> W >> n;
	for (int i = 0; i < n; ++i){
		cin >> x >> y;
		mp[x*Md+y] = 1;
		vec.push_back({x, y});
	}
	for (int i = 0; i < n; ++i){
		x = vec[i].A;
		y = vec[i].B;
		for (int j = -1; j < 2; ++j){
			for (int k = -1; k < 2; ++k){
				if (x+j < H && x+j > 1 && y+k < W && y+k > 1)	st.insert({x+j, y+k});
			}
		}
	}
	for (auto i : st){
		Solve(i);
	}
	Ans[0] = (H-2)*(W-2);
	for (int i = 1; i < 10; ++i)	Ans[0] -= Ans[i];
	for (int i = 0; i < 10; ++i)	cout << Ans[i] << '\n';
    return 0;
}
/*             now or never                 */


Measured memory_bytes: 175936
s=input()
n=len(s)
n2a = lambda c: chr(c+64).lower()
d={}
d_={}
for i in range(1,27):
  d[n2a(i)]=[0]
  d_[n2a(i)]=0
for i in range(n):
  d_[s[i]]+=1
  for j in range(1,27):
    d[n2a(j)].append(2*d_[n2a(j)]-(i+1))
def func(l):
  mina=[0,0]
  for k in range(2,n+1):
    if mina[0]<l[k]:
      return [mina[1]+1,k]
    elif mina[0]>l[k-2]:
      mina=[l[k-2],k-2]
  return [-1,-1]
for i in range(1,27):
  tmp=func(d[n2a(i)])
  if tmp[0]>0:
    print(tmp[0],tmp[1])
    exit()
print(-1,-1)


Measured memory_bytes: 133640
from __future__ import division, print_function

''' Hey stalker :) '''
INF = 10 ** 10
TEST_CASES = False


def main():
    st = input()
    if len(st)%2!=0:
        print('No')
        return
    for i in range(0,len(st),2):
        if st[i]!='h' or st[i+1]!='i':
            print('No')
            return
    print('Yes')


''' FastIO Footer by @c1729 and other contributors '''
import os
import sys
from bisect import bisect_left, bisect_right
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
# else:
#     sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))
if __name__ == "__main__":
    if TEST_CASES:
        [main() for _ in range(int(input()))]
    else:
        main()


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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()


void solve(long long N, long long K, std::vector<long long> A){
    rep(i, K){
        bool changed = false;
        vector<i64> B(N + 1);
        rep(j, N){
            B[max(j - A[j], 0LL)]++;
            B[min(j + A[j] + 1, N)]--;
        }
        i64 s = 0;
        rep(j, N){
            s += B[j];
            if(A[j] != s) changed = true;
            A[j] = s;
        }
        if(!changed) break;
    }
    rep(i, N){
        if(i != N - 1) cout << A[i] << " ";
        else cout << A[i] << endl;
    }
}

struct IoSetup {
    IoSetup() {
        // cin.tie(nullptr);
        // ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, K, std::move(A));
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<int, ll> PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define N 100010
#define K 310
int n, m, k;
ll a[N];

deque<PII> q[K];
ll S = 0;

void add(int x, PII y) {
	while (!q[x].empty() && q[x].back().se < y.se) q[x].pop_back();
	q[x].push_back(y);
}

void clr(int x, int nw) {
	while (!q[x].empty() && q[x].front().fi < nw - m) q[x].pop_front();
}

ll ans(int x) {
	if (q[x].empty()) return -1;
	return q[x].front().se;
}

int main () {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i ++) cin >> a[i];
	for (int i = 0; i < n; i ++) {
		for (int j = k-1; j >= 1; j --) {
			clr(j, i);
			ll s = ans(j);
			if (s != -1) {
				add(j+1, mp(i, s+(ll)(j+1)*a[i]));
			}
		}
		add(1, mp(i, a[i]));
		S = max(S, ans(k));
	}
	
	cout << S << endl;
	return 0;
}

Measured memory_bytes: 1280
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader stdIn = new BufferedReader(new InputStreamReader(System.in));
		String s;
		int inCnt = 0;
		while ((s = stdIn.readLine()) != null) {
			inCnt++;
			if (inCnt % 2 == 1)
				continue;
			String[] se = s.split(" ");
			// int e = Integer.valueOf(se[0]);
			doMain(inCnt, se);
		}
		System.exit(0);
	}

	private static void doMain(int inCnt, String[] se) {
		System.out.print(se[se.length - 1]);
		for (int i = se.length - 2; i >= 0; i--) {
			System.out.print(" " + se[i]);
		}
		System.out.println("");

	}
}

Measured memory_bytes: 24404
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a,b;
    cin>>a>>b;
    if((a*b)%2){
        cout1("Odd")
    }else{
        cout1("Even")
    }
}

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

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

    ll Tsum = 1;
    ll Asum = 1;
    ll cnt = 1;
    rep(i, n){
        cnt = max((Tsum + T[i] - 1)/T[i], (Asum + A[i] - 1)/A[i]);
        Tsum = T[i]*cnt;
        Asum = A[i]*cnt;
    }

    cout << Tsum + Asum << endl;
    return 0;
}

Measured memory_bytes: 256
# include <stdio.h>
int main()
{
	int a[100];
	int n;
	int num = 0;
	
	scanf("%d",&n);
	for(int i = 0; i < n; ++i)		scanf("%d", &a[i]);
	for (int i = 0; i < n; i++)
	{
		int tem = i;
		for (int j = i + 1; j < n; j++)
		{
			if (a[tem] > a[j])	tem = j;
		}
		if (tem != i)
		{
		int v = a[tem];
		a[tem] = a[i];
		a[i] = v;
		++num;
		}
	}
	for(int i = 0; i < n - 1; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("%d\n%d\n", a[n-1],num);
 } 


Measured memory_bytes: 2744
n=int(input())

xy=[list(map(int,input().split())) for _ in range(n)]

xpy=[]
xmy=[]

for i in range(n):
    xpy.append(xy[i][0]+xy[i][1])
    xmy.append(xy[i][0]-xy[i][1])

xpy.sort()
xmy.sort()

print(max(abs(xpy[-1]-xpy[0]),abs(xmy[-1]-xmy[0])))


Measured memory_bytes: 133108
#include<iostream>
#define INF 100000000
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
	int x,y,c,n,m,s,p,q,d[110][110];
	while(cin>>n>>m>>s>>p>>q,n!=0){
		s--;p--;q--;
		rep(i,n)
		rep(j,n)
		d[i][j]=INF;
		rep(i,n)
		d[i][i]=0;
		rep(i,m){
			cin>>x>>y>>c;
			x--;y--;
			d[x][y]=c;
		}
		rep(k,n)
		rep(i,n)
		rep(j,n)
		d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
		int ans=INF;
		rep(i,n)
		ans=min(ans,d[s][i]+d[i][p]+d[i][q]);
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 916
#include <iostream>
using namespace std;
class Dice {
private:
  int dice[6];
  int tmp;
 public:
  Dice(int a, int b, int c, int d, int e, int f) {
	dice[0] = a;
	dice[1] = b;
	dice[2] = c;
	dice[3] = d;
	dice[4] = e;
	dice[5] = f;
  }
  void roll(char ch) {
	if(ch == 'N') {
	  rollN();
	}
	else if(ch == 'E') {
	  rollE();
	}
	else if(ch == 'S') {
	  rollS();
	}
	else {
	  rollW();
	}
  }
  void rollN() {
	swap(dice[0], dice[1]);
	swap(dice[1], dice[5]);
	swap(dice[5], dice[4]);
  }
  void rollS() {
	swap(dice[0], dice[4]);
	swap(dice[4], dice[5]);
	swap(dice[5], dice[1]);
  }
  void rollE() {
	swap(dice[0], dice[3]);
	swap(dice[3], dice[5]);
	swap(dice[5], dice[2]);
  }
  void rollW() {
	swap(dice[0], dice[2]);
	swap(dice[2], dice[5]);
	swap(dice[5], dice[3]);
  }
  void spinL() {
	swap(dice[1], dice[2]);
	swap(dice[2], dice[4]);
	swap(dice[4], dice[3]);
  }
  int top() {
	return dice[0];
  }
  int front() {
	return dice[1];
  }
  int right() {
	return dice[2];
  }
};
void solve(Dice d1, int top, int front) {
	for(int i = 0; i < 4; ++i) {
	  if(d1.top() == top) break;
	  d1.rollE();
	}
	for(int i = 0; i < 4; ++i) {
	  if(d1.top() == top) break;
	  d1.rollN();
	}
	for(int i = 0; i < 4; ++i) {
	  if(d1.front() == front) break;
	  d1.spinL();
	}
	cout <<  d1.right() << endl;
}
int main() {
  int a, b, c, d, e, f;
  int q;
  int top, front;
  
  cin >> a >> b >> c >> d >> e >> f;
  cin >> q;
  for(int i = 0; i < q; ++i) {
	Dice d1(a, b, c, d, e, f);
	cin >> top >> front;
	solve(d1, top, front);
  }
  return 0;
}

Measured memory_bytes: 3048
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Map = map<string,ll>;

ll MOD=1000000007;



int main(){
	string S;
	cin >> S;
	ll N=S.size();
	string ans="Yes";
	for(ll i=0;i<N;i++){
		if(i%2!=1&&S[i]=='L')ans="No";
		else if (i%2!=0&&S[i]=='R')ans="No";
	;}
	cout<<ans<<endl;
return 0;
}  



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



int main(){
    string S,T;
    cin >> S >> T;
    bool ok = false;

    for(int i = 0;i<=S.size()-1;i++){
        if(S == T){
            ok = true;
            break;
        }
        S = S.back() + S.substr(0,S.size()-1);
    }

    if(ok == true){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 18;

int n;
vector <int> a, ans[1 << 18];

void add(vector <int> &c, int x){
    for(auto &i : c) if(i == x) return;
    c.push_back(x);
    sort(c.begin(), c.end(), [&](int l, int r){
        return a[l] > a[r];
    });
    while(c.size() > 2) c.pop_back();
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    a.resize(1 << n);
    for(auto &i : a) cin >> i;
    for(int i = 0 ; i < (1 << n) ; i++){
        add(ans[i], i);
    }
    int res = 0;
    for(int i = 1 ; i < (1 << n) ; i++){
        for(int j = 0 ; j < n ; j++){
            if((i >> j) & 1){
                for(auto &k : ans[i ^ (1 << j)]){
                    add(ans[i], k);
                }
            }
        }
        res = max(res, a[ans[i][0]] + a[ans[i][1]]);
        cout << res << "\n";
    }
}


Measured memory_bytes: 18688
#include <iostream>
#include <string>
#include <cstdlib>              // abs
#define FOR(i,k,n) for (int (i)=(k);(i)<(n);(i)++)
using namespace std;

// マンハッタン距離
int dist(int x1, int y1, int x2, int y2)
{
  return abs(x1 - x2) + abs(y1 - y2);
}

int main()
{
  int N, M;
  int a[50], b[50], c[50], d[50];
  cin >> N >> M;

  FOR(i,0,N) {
    cin >> a[i] >> b[i];
  }
  FOR(i,0,M) {
    cin >> c[i] >> d[i];
  }

  // 各学生に対して、最も近いチェックポイント
  FOR(i,0,N) {
    // 最も近い, 最短距離
    int nearest, dmin = 10000000000;
    int z;

    FOR(j,0,M) {
      z = dist(a[i], b[i], c[j], d[j]);
      // 最短距離を更新
      if (z < dmin) {
        nearest = j;
        dmin = z;
      }
    }

    cout << nearest + 1 << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define rep(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define Rep(i,a,b) for (int (i)=(a);(i)<(b);(i)++)
#define REP(i,a,b) for (int (i)=(a);(i)>=(b);(i)--)
#define reg(i,x)   for (int (i)=head[x];(i);i=e[i].next)
#define lowbit(x) ((x)&(-(x)))
#define ls ((x)<<1)
#define rs ((x)<<1|1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define P pair<int,int>
const int N = 100010 ;
const int inf = 1e18 ; 
const int MOD = 1e9+7 ;

struct node {
	int x,y,dis ;
}e[100010];

bool cmp(node a,node b){
	return a.dis<b.dis ;
}

int n,m,ans ;
int dis[310][310] ;

void floyd(int k){ //floyd
	rep(i,1,n) rep(j,1,n) dis[i][j]=dis[j][i]=min(dis[i][j],dis[i][k]+dis[k][j]) ;
}

void print(){
	printf("-1\n") ;
	exit(0) ;
}

signed main(){
	ios::sync_with_stdio(false) ;
	scanf("%lld",&n) ;
	rep(i,1,n) {
		rep(j,1,n) dis[i][j]=inf ;
		dis[i][i]=0 ;
	}
	rep(i,1,n) rep(j,1,n) {
		int x ;
		scanf("%lld",&x) ;
		if (j>i) {
			e[++m].x=i;
			e[m].y=j ;
			e[m].dis=x ;
		}
	}
	sort(e+1,e+m+1,cmp) ;//把边排序，选最小的构成图 
	for (int i=1;i<=m;i++){ //选较小的边，更新 
		int from=e[i].x,to=e[i].y,dist=e[i].dis ;
		if (dis[from][to]<dist) print() ;
		else if (dis[from][to]>dist){
			dis[from][to]=dis[to][from]=dist ;
			ans+=dist ;
			floyd(from);floyd(to) ;
		}
	}
	printf("%lld\n",ans) ; 
}

Measured memory_bytes: 2048
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <map>
#include <string>
#include <deque>

#pragma warning(disable:4996)
#define MAX_N 10000

struct Node {
	std::vector<int>connection;
	int c;
	Node() : c(0) {}
};

Node N[MAX_N+1];
std::vector<int>C;


void Connect(int a, int b) {
	N[a].connection.push_back(b);
	N[b].connection.push_back(a);
}
void refunc(Node& node) {
	node.c = C[C.size()-1];
	C.pop_back();
	for (int i = 0; i < node.connection.size(); ++i) {
		int index = node.connection[i];
		if (N[index].c != 0) continue;
		refunc(N[index]);
	}
}
int main(void) {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n-1; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		Connect(a, b);
	}
	for (int i = 0; i < n; ++i) {
		int c;
		scanf("%d", &c);                                                            
		C.push_back(c);
	}
	std::sort(C.begin(), C.end());
	int sum = 0;
	for (int i = 0; i < C.size() - 1; ++i) {
		sum += C[i];
	}
	printf("%d\n", sum);
	for (int i = 1; i < n+1; ++i) {
		if (N[i].connection.size() == 1) {
			refunc(N[i]);
			break;
		}
	}
	for (int i = 1; i < n+1; ++i) {
		printf("%d ", N[i].c);
	}
	return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>
#include <queue> 
using namespace std;
char a[200005],b[200005];
int main()
{
	long long a;
	string s;
	cin>>a>>s;
	if(a>=3200)
		cout<<s;
	else
		cout<<"red";
		return 0;	
}
//aa a c ca c a b aa b a b c
//a ab b aa 
//first    R1 G5 B9
//second   R2 G4 B8
//third    R3 G6 B7

Measured memory_bytes: 256
//#include "Header.h"
#include <iostream>
#include<bits/stdc++.h>

#define endl '\n'
using namespace std;

int main()
{	
	
	int N;
	cin>>N;
	vector<long long> A(N);
    int t;
	for(int i = 0; i < N; ++i)
    {
      cin>>A[i];
    }
	vector<long long> v(N);
	v[0] = 0;
	v[1] = abs(A[0] - A[1]);

	for (int i = 2; i < N; ++i)
	{
		v[i] = min(v[i - 1] + abs(A[i] - A[i - 1]), v[i - 2] + abs(A[i - 2] - A[i]));
	}
	
	cout<< v[N - 1]<<endl;
}


Measured memory_bytes: 1792
n = int(input())
memo = [0]*(n+1)


for a in range(int((2*n)**(1/2))+1):
    r1 = 2*n-a**2
    for b in range(int(r1**(1/2))+1):
        r2 = r1-b*2
        if r2 < 0: continue
        for c in range(int(r2**(1/2))+1):
            if 0<a**2<2*n and 0<b**2<2*n and 0<c**2<2*n:
                s = a**2 + b**2 + c**2
                if s%2==1 or s>2*n: continue
                x = (a+b+c)//2-a
                y = (a+b+c)//2-b
                z = (a+b+c)//2-c
                if x>=1 and y>=1 and z>=1:
                    # print(x, y, z)
                    memo[s//2] += 1

for i in range(1, n+1):
    print(memo[i])

Measured memory_bytes: 69700