akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
vector<int> g[205];
bool used[205]={0},us[205]={0};
int col[205],cor[205][205];

bool dfs(int x,int color){
	col[x]=color;
	used[x]=true;
	for(int i=0;i<g[x].size();i++){
		if(used[g[x][i]]){
			if(color%2==col[g[x][i]]%2) return false;
		} else {
			if(!dfs(g[x][i],color+1)) return false;
		}
	}
	return true;
}

int main (){
    int n,i,j,cmax[205]={0},ccmax=0,memo=0;
    char s[205];
    cin >> n;
    for(i=0;i<n;i++){
    	cin >> s;
    	for(j=0;j<n;j++){
    		if(s[j]=='1') g[i].push_back(j);
    	}
    }
    if(!dfs(0,0)){
    	cout << "-1" << endl;
    	return 0;
    }
    for(j=0;j<n;j++){
    queue<int> q;
    for(i=0;i<n;i++) cor[j][i]=0;
    q.push(j); cor[j][j]=1;
    while(!q.empty()){
    	int v=q.front();
    	q.pop();
    	for(i=0;i<g[v].size();i++){
    		if(cor[j][g[v][i]]==0){
    			cor[j][g[v][i]]=cor[j][v]+1;
    			q.push(g[v][i]);
    		}
    	}
    }
    }
    for(i=0;i<n;i++){
    	for(j=0;j<n;j++) cmax[i]=max(cmax[i],cor[i][j]);
    	ccmax=max(ccmax,cmax[i]);
    }
    cout << ccmax  << endl;
    return 0;
}

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

// int/long:		-2,147,483,648 - 2,147,483,648 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define	INF (1<<29)
//536,870,912

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

#define	MOD 1000000007

int	main() {
	int N;
	string S;
	cin >>N >>S;
	for (int i=0; i<S.size(); i++) {
		int j=S.at(i)-'A';
		j +=N;
		j%=26;
		char c='A'+j;
		cout <<c;
	}
	cout <<endl;
	return 0;
}



Measured memory_bytes: 256
K = int(input())
N=7
A = 1


def f(A, L):
    if L % 2 == 0 or L % 5 == 0:
        A = -1
    else:
        x = 10
        b = 0
        while b == 0:
            if x % L == 1:
                break
            else:
                x = (x * 10) % L
                A += 1
    return A


if K % 7 == 0:
    L = 9*K/7
    A = f(A, L)
else:
    L = 9*K
    A = f(A, L)

print(A)



Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
 
#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair
 
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e5+10, maxm=5e6+10, lg=16, mod=998244353, inf=1e18;

ll n,tt[lg],x[maxn],ans,dp[1<<lg],xo[1<<lg];

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n;
	for(int i=1;i<n;i++){
		ll v,u,a; cin>>v>>u>>a;
		x[v]^=a, x[u]^=a;
	}
	for(int i=0;i<n;i++) tt[x[i]]++;
	vector<ll> a;
	ans+=tt[0];
	for(int i=1;i<lg;i++){
		ans+=tt[i]/2;
		if(tt[i]%2) a.pb(i);
	}
	for(int msk=1;msk<(1<<SZ(a));msk++){
		for(int i=0;i<SZ(a);i++)if(msk>>i&1){ xo[msk]=xo[msk^(1<<i)]^a[i]; break; }
		for(int sub=msk;sub;sub=(sub-1)&msk)if(xo[sub]==0) dp[msk]=max(dp[msk],1+dp[msk^sub]);
	}
	cout<<n-(ans+dp[(1<<SZ(a))-1]);
	
	return 0;
}





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

int N,K;
int main(){
  scanf("%d %d",&N,&K);
  if(N/2<K){
    printf("-1\n");
    return 0;
  }
  vector<int> a,b;
  for(int i=0;i<N/2;i++){
    a.push_back(0);
    b.push_back(i+1);
  }
  for(int i=1;i<N/2;i++){
    a.push_back(N/2);
    b.push_back(N/2+i);
  }
  for(int tc=0;tc<K;tc++){
    if(tc)printf("\n");    
    if(N%2==1)printf("%d %d\n",N,tc+1);
    for(int i=0;i<(int)a.size();i++){
      printf("%d %d\n",a[i]+1,b[i]+1);
      a[i]++;
      a[i]%=N/2*2;
      b[i]++;
      b[i]%=N/2*2;
    }
  }
  return 0;
}

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

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#include <map>
#define all(x) (x).begin(),(x).end()

const int MOD = 1e9 + 7;

void solve(){

}
int main(){
    string s[3];
    cin >> 0[s] >> 1[s] >> 2[s];
    cout << "A" << s[1][0] << "C" << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define _USE_MATH_DEFINES
using namespace std;
int main()
{
ll n;
cin>>n;
ll a[n];
for(ll i=0;i<n;i++)
{
cin>>a[i];
}
bool ok=false;
string ans="YES";
for(int i=0;i<n;i++)
{
if(a[i]!=i+1)
{
    if(ok)
    {
    ans="NO";
    break;
    }
    bool f=false;
int j=i+1;
for(j;j<n;j++)
{
if(a[j]==i+1)
{
if(a[i]!=j+1)
{
ans="NO";
f=true;
break;
}
swap(a[i],a[j]);
}
}
if(f)
{
break;
}
ok=true;
}
}
cout<<ans;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(){
  int n,k;
  scanf("%d %d",&n,&k);
  if(n<k){
    for(int i=0;i<k;i++){
      printf("%d",n);
    }
  }else{
    for(int i=0;i<n;i++){
      printf("%d",k);
    }
  }
  return 0;
}


Measured memory_bytes: 128
import java.util.*;

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt()+1;
		String s = sc.next();
		s += "*";

		int ans = 0;
		char prev = s.charAt(0);
		for(int i = 0 ; i < n ; i++){
			if(prev != s.charAt(i)){
				ans++;
				prev = s.charAt(i);
			}
		}

		System.out.println(ans);
	}
}

Measured memory_bytes: 26964
while 1:
    n=input()
    if n==0:
        break
    s=raw_input()
    for i in range(n):
        cnt=0
        prev=" "
        ns=""
        for c in s:
            if c==prev:
                cnt+=1
            else:
                if prev!=" ":
                    ns+=str(cnt)+prev
                cnt=1
            prev=c
        if prev!=" ":
            ns+=str(cnt)+prev
        cnt=0
        s=ns
    print s

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

bool prime[8000000];
signed main(void)
{
  while(true) {
    int m, n;
    cin >> m >> n;
    if(!m && !n) break;
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    for (int i = m; i <= 8000000; i++) {
    	if (prime[i]) {
        n--;
    		for (int j = i; j <= 8000000; j += i) {
    			prime[j] = false;
    		}
        if(!n) {
          //cout << "a" << endl;
          break;
        }
    	}
    }
    FOR(i, m, 8000000) if(prime[i]) {
      cout << i << endl;
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 10772
n = int(input())
l = list(map(int, input().split()))
MIN = min(l)
MAX = max(l)
ans = float('inf')
for i in range(MIN, MAX + 1):
    count = 0
    for j in l:
        count += (i - j) ** 2
    ans = min(ans, count)
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<climits>
#include<vector>
#include<utility>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
 
int main(){
 
int N,K;
string S,ans;
cin>>N>>S>>K;

for(int i = 0; i < N; i++){
    if(S[i] == S[K-1]){
        ans += S[i];
    }else{
        ans += "*";
    }
}

cout << ans << endl;

}

Measured memory_bytes: 256
#define DEBUG 0
/**
 * File    : A.cpp
 * Author  : Kazune Takahashi
 * Created : 9/15/2019, 8:57:34 PM
 * Powered by Visual Studio Code
 */
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <functional>
#include <random>
#include <chrono>
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
using ll = long long;
class mint
{
public:
  static ll MOD;
  ll x;
  mint() : x(0) {}
  mint(ll x) : x(x % MOD) {}
  mint operator-() const { return x ? MOD - x : 0; }
  mint &operator+=(const mint &a)
  {
    if ((x += a.x) >= MOD)
    {
      x -= MOD;
    }
    return *this;
  }
  mint &operator-=(const mint &a) { return *this += -a; }
  mint &operator*=(const mint &a)
  {
    (x *= a.x) %= MOD;
    return *this;
  }
  mint &operator/=(const mint &a)
  {
    mint b{a};
    return *this *= b.power(MOD - 2);
  }
  mint operator+(const mint &a) const { return mint(*this) += a; }
  mint operator-(const mint &a) const { return mint(*this) -= a; }
  mint operator*(const mint &a) const { return mint(*this) *= a; }
  mint operator/(const mint &a) const { return mint(*this) /= a; }
  bool operator<(const mint &a) const { return x < a.x; }
  bool operator==(const mint &a) const { return x == a.x; }
  const mint power(ll N)
  {
    if (N == 0)
    {
      return 1;
    }
    else if (N % 2 == 1)
    {
      return *this * power(N - 1);
    }
    else
    {
      mint half = power(N / 2);
      return half * half;
    }
  }
};
ll mint::MOD = 1e9 + 7;
istream &operator>>(istream &stream, mint &a) { return stream >> a.x; }
ostream &operator<<(ostream &stream, const mint &a) { return stream << a.x; }
class combination
{
public:
  vector<mint> inv, fact, factinv;
  static int MAX_SIZE;
  combination() : inv(MAX_SIZE), fact(MAX_SIZE), factinv(MAX_SIZE)
  {
    inv[1] = 1;
    for (auto i = 2; i < MAX_SIZE; i++)
    {
      inv[i] = (-inv[mint::MOD % i]) * (mint::MOD / i);
    }
    fact[0] = factinv[0] = 1;
    for (auto i = 1; i < MAX_SIZE; i++)
    {
      fact[i] = mint(i) * fact[i - 1];
      factinv[i] = inv[i] * factinv[i - 1];
    }
  }
  mint operator()(int n, int k)
  {
    if (n >= 0 && k >= 0 && n - k >= 0)
    {
      return fact[n] * factinv[k] * factinv[n - k];
    }
    return 0;
  }
};
int combination::MAX_SIZE = 3000010;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
// constexpr double epsilon = 1e-10;
// constexpr ll infty = 1000000000000000LL;
// constexpr int dx[4] = {1, 0, -1, 0};
// constexpr int dy[4] = {0, 1, 0, -1};
void Yes()
{
  cout << "Yes" << endl;
  exit(0);
}
void No()
{
  cout << "No" << endl;
  exit(0);
}

int main()
{
  string S;
  cin >> S;
  if (S == "Sunny")
  {
    cout << "Cloudy" << endl;
  }
  else if (S == "Cloudy")
  {
    cout << "Rainy" << endl;
  }
  else
  {
    cout << "Sunny" << endl;
  }
}

Measured memory_bytes: 256
class Point():
      def __init__(self,base,score,out):
            self.base=base
            self.score=score
            self.out=out

      def hit(self):
            if self.base < 3:
                  self.base = self.base + 1
            else:
                  self.score = self.score + 1

      def home(self):
            self.score = self.score + self.base + 1
            self.base = 0

      def out1(self):
            self.out = self.out + 1

n = int(input())
for i in range(n):
      game = Point(0,0,0)
      while 1:
            eve = input()
            if eve == "HIT":
                  game.hit()             
            if eve == "HOMERUN":
                  game.home()
            if eve == "OUT":
                  game.out1()
                  if game.out == 3:
                        print(game.score)
                        del game
                        break



Measured memory_bytes: 5588
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
using namespace std;
int main() {
  int n,m;
  cin >> n >> m;
  int* p = new int[100000];
  for(int i=0;i<n;i++) cin >> p[i];
  int* g = new int[100000];
  for(int i=0;i<n;i++) g[i] = i;
  for(int i=0;i<m;i++){
    int x,y;
    cin >> x;
    cin >> y;
    x--;
    y--;
    while(g[x]!=x){
      x = g[x];
    }
    while(g[y]!=y){
      y = g[y];
    }
    if(g[y]>g[x]) g[y] = g[x];
    else g[x] = g[y];
  }
  int count = 0;
  for(int i=0;i<n;i++) {
    int v = p[i]-1;
    int gi = i;
    int gv = v;
    while(gi!=g[gi]) gi = g[gi];
    while(gv!=g[gv]) gv = g[gv];
    if(gi==gv) count ++;
  }
  cout << count << endl;

  return 0;
}



Measured memory_bytes: 1024
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 1<<30
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef long long int LL;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
template<class T> using V=vector<T>;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//---------------------------------------------------------------------------
int n,m;
int a[300][300];
void warshall_floyd(){
    for (int k = 0; k < n; k++){       // 経由する頂点
    for (int i = 0; i < n; i++) {    // 始点
        if(a[i][k]==IINF)continue;
        for (int j = 0; j < n; j++) {  // 終点
        if(a[k][j]==IINF)continue;
        chmin(a[i][j], a[i][k] + a[k][j]);
        }
    }
    }
}
//---------------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    cin>>n>>m;
    vector<int>aa(m),bb(m);
    for(int i=0;i<m;i++){cin>>aa[i]>>bb[i];aa[i]--;bb[i]--;}
    int ans=0;
    for(int i=0;i<m;i++){
        for(int x=0;x<n;x++){
            for(int y=0;y<n;y++){
                a[x][y]=IINF;
            }
        }
        for(int j=0;j<m;j++){
            if(i==j)continue;
            else{
                a[aa[j]][bb[j]]=1;
                a[bb[j]][aa[j]]=1;
            }
        }
        warshall_floyd();
          
   
        for(int j=1;j<n;j++){
            if(a[0][j]==IINF){
                ans++;
                break;
            }
        }
    }
    cout<<ans<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------
/*
int n;cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++)
    cin>>a[i];
*/


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef double ld;
typedef long long ll;
#define int ll
const ll mod=1e9+7;

int32_t main()
{
    int k,a,b;
    cin>>k;
    cin>>a>>b;
    if(a/k!=b/k ||(a%k==0 || b%k==0))
        cout<<"OK"<<endl;
    else
        cout<<"NG"<<endl;
}




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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}

int main2() {
  ll a = nextLong();
  ll b = nextLong();
  ll c = nextLong();
  ll d = nextLong();

  ll ans = a * c;
  if (a <= 0 && 0 <= b) chmax(ans, 0LL);
  if (c <= 0 && 0 <= d) chmax(ans, 0LL);
  chmax(ans, a * c);
  chmax(ans, a * d);
  chmax(ans, b * c);
  chmax(ans, b * d);
  cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

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

using namespace std;

typedef struct restaurant{
    string nome;
    int id, nota;
}restaurant;

bool cmp(restaurant a, restaurant b){
    if(a.nome == b.nome){
        return a.nota > b.nota;
    }
    return a.nome < b.nome;
}

int main(){
    int n;
    scanf("%d", &n);
    restaurant restaurants[n];
    for(int i = 0; i < n; i++){
        string nome; int nota;
        cin >> nome >> nota;
        restaurants[i].id = i + 1;
        restaurants[i].nome = nome;
        restaurants[i].nota = nota;
    }
    sort(restaurants, restaurants + n, cmp);
    for(int i = 0; i < n; i++){
        printf("%d\n", restaurants[i].id);
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
typedef long long ll;
typedef long long unsigned int llu;
ll MOD = 1000000007;
ll INF = 1e9+1;

/*
hi = h - |xi - cx| - |yi - cy|
の式N個から、h, cx, cyを計算する

cx、cyを全探索し、hがすべて同じになるような場合を答えとする
計算量は1000000程度なのでいけそう
*/

void solve(){
    int n;
    cin >> n;
    vector<int> x;
    vector<int> y;
    vector<int> h;
    rep(i,n){
        int a,b,c;
        cin >> a >> b >> c;
        //if(c>=1){
            x.emplace_back(a);
            y.emplace_back(b);
            h.emplace_back(c);
        //}
    }
    int s = x.size();
    bool ans = true;
    int a1,a2,a3;
    rep(cx,101){
        rep(cy,101){
            ans = true;
            //int cons = -1;
            int tmp=0;
            while(h[tmp]==0){
                tmp++;
            }
            int cons = h[tmp] + abs(x[tmp]-cx) + abs(y[tmp]-cy);
            for(int i=0; i<s; i++){
                if(h[i] != max(cons - abs(x[i]-cx) - abs(y[i]-cy),(ll)0)){
                    ans = false;
                }
            }
            if(ans) {
                a1 = cx;
                a2 = cy;
                a3 = cons;
            }
        }
    }
    cout << a1 << " " << a2 << " " << a3 << endl;
}

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


Measured memory_bytes: 256
sagyou = []
W,H,N = map(int,input().split(' '))
for i in range(0,N):
    sagyou.append(list(map(int,input().split(' '))))
area = [[0,W],[0,H]]
for i in range(0,N):
    if sagyou[i][2] == 1 and area[0][0] <= sagyou[i][0]:
        area[0][0] = sagyou[i][0]
    elif sagyou[i][2] == 2 and area[0][1] >= sagyou[i][0]:
        area[0][1] = sagyou[i][0]
    elif sagyou[i][2] == 3 and area[1][0] <= sagyou[i][1]:
        area[1][0] = sagyou[i][1]
    elif sagyou[i][2] == 4 and area[1][1] >= sagyou[i][1]:
        area[1][1] = sagyou[i][1]
    if (area[0][1]-area[0][0])*(area[1][1]-area[1][0]) <= 0:
        print(0)
        break
    if i == N-1 and (area[0][1]-area[0][0])*(area[1][1]-area[1][0]) >= 0:
        print((area[0][1]-area[0][0])*(area[1][1]-area[1][0]))

Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i = (a); i < (b); i++)
#define pb push_back
#define fs first
#define sc second
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

const double EPS = 1e-9;

struct node {
    int mx;
    node() { mx = 0; }
    node(int _mx) { mx = _mx; }
    node(node a, node b) {
        mx = max(a.mx, b.mx);
    }
};
struct segment_tree {
    int sz, n;
    vector<node> t;
    segment_tree(int _n) : sz(_n*4), n(_n) {
        rep(i,0,sz) t.pb(node());
    }
    void build(vi &a, int v=1, int tl=0, int tr=-1) {
        if(tr == -1) tr = n-1;
        if(tl == tr) {
            t[v] = node(a[tl]);
        } else {
            int tm = (tl+tr)/2;
            build(a, v*2, tl, tm);
            build(a, v*2+1, tm+1, tr);
            t[v] = node(t[v*2], t[v*2+1]);
        }
    }
    node query(int l, int r, int v=1, int tl=0, int tr=-1) {
        if(tr == -1) tr = n-1;
        if(l > r) return node();
        if(l == tl && r == tr) return t[v];
        int tm = (tl+tr)/2;
        return node( query(l,min(r,tm), v*2, tl, tm),
                query(max(l,tm+1), r, v*2+1, tm+1, tr));
    }
    void update(int pos, int new_val, int v=1, int tl=0, int tr=-1) {
        if(tr == -1) tr = n-1;
        if(tl == tr) t[v] = node(new_val);
        else {
            int tm = (tl+tr)/2;
            if(pos <= tm) update(pos, new_val, v*2, tl, tm);
            else update(pos, new_val, v*2+1, tm+1, tr);
            t[v] = node(t[v*2], t[v*2+1]);
        }
    }
};

int main() {
    cin.sync_with_stdio(false);
    int n,k;
    cin >> n >> k;
    segment_tree sq(300'100);
    vi A(n);
    rep(i,0,n) cin >> A[i];
    for(int i = n-1; i >= 0; i--) {
        sq.update(A[i], sq.query(max(0,A[i]-k), min(A[i]+k,300'001)).mx + 1);
    }
    cout << sq.query(0,300'001).mx << endl;
}





Measured memory_bytes: 11692
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long long int uint64;
typedef long long int          int64;
 
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void get_N (int64 *n)
{
  
  (void)scanf("%lld", n);

  return;
}

void get_NK (int64 *n, int64 *k)
{
  
  (void)scanf("%lld %lld", n, k);

  return;
}

void get_N1234 (int64 *n1, int64 *n2, int64 *n3, int64 *n4)
{
  int cnt;

  if (n2 == NULL) {
    cnt = scanf("%lld", n1);
    return;
  }
  if (n3 == NULL) {
    cnt = scanf("%lld %lld", n1, n2);
    return;
  }
  if (n4 == NULL) {
    cnt = scanf("%lld %lld %lld", n1, n2, n3);
    return;
  }
  cnt = scanf("%lld %lld %lld %lld", n1, n2, n3, n4);
  return;
}

void omit_LF (void)
{
  char c;
  int  cnt;
  
  cnt = scanf("%c", &c);
  return;
}

char *get_S (int64 n)
{
  char *buf;
  int  i;
  int  cnt;

  buf = (char *)malloc((size_t)(n * sizeof(char)));
  if (buf == NULL) {
    return NULL;
  }

  cnt = scanf("%s", buf);

  return buf;
}

char *get_SN (int64 max, int64 *size)
{
  char *buf;
  int  i;
  int  n;
  int  cnt;

  buf = (char *)malloc((size_t)(max * sizeof(char)));
  if (buf == NULL) {
    return NULL;
  }

  cnt = scanf("%s", buf);

  n = strlen(buf);

  *size = n;
  
  return buf;
}

int64 *get_NSeq (int64 n)
{
  int64 *buf;
  int64 i;

  buf = (int64 *)malloc((size_t)(n * sizeof(int64)));
  for (i=0; i<n; i++) {
    get_N(&buf[i]);
  }

  return buf;
}

typedef struct _tmp_t {
  int64    a;
  int64    b;
} tmp_t;

typedef int64 simple_t;

int compare_simple(const void *a, const void *b)
{
  simple_t *x;
  simple_t *y;

  x = (simple_t *)a;
  y = (simple_t *)b;

  if (x > y) return 1;
  if (y < x) return -1;

  return 0;
}
void qsort_simple (simple_t *array, int size)
{
  qsort(array, size, sizeof(simple_t), compare_simple);
}

int compare_a(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->a > y->a) return 1;
  if (x->a < y->a) return -1;

  return 0;
}

int compare_b(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->b > y->b) return 1;
  if (x->b < y->b) return -1;

  return 0;
}

void qsort_a (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_a);
}

void qsort_b (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_b);
}


int resolve1()
{
  int64 R;
  double pi=3.14159;
  double L;

  get_N(&R);

  L = pi*R*2;

  printf("%lf", L);
  return 0;
}

int resolve2()
{
  int64 N,X,T;
  int64 min;
  
  get_N1234(&N, &X, &T, NULL);

  min = (N/X) + (((N%X) == 0) ? 0 : 1);
  min *= T;

  printf("%lld",min);
  return 0;
}


void resolve3()
{
  int64 N;
  char *str;
  int64 i;
  int64 sum = 0;
  
  str = get_SN(2000001, &N);

  for (i=0; i < N; i++) {
    sum += str[i] - '0';
  }

  if (((sum % 9) == 0) || (sum == 0)) {
    printf("Yes");
  } else {
    printf("No");
  }

  return;
}

int main()
{
  resolve3();

  return 0;
}



Measured memory_bytes: 1900
// Colorful Transceivers

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <ios>
#include <iomanip>
#include <string>
#include <numeric>

using namespace std;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;

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

    return 0;
}


Measured memory_bytes: 256
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    cnt = 0
    for i in range(N):
        if A[i] > B[i]:
            cnt += B[i]
        else:
            cnt += A[i]
            rest = B[i] - A[i]
            if A[i+1] > rest:
                cnt += rest
                A[i+1] -= rest
            else:
                cnt += A[i+1]
                A[i+1] = 0
    
    print(cnt)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 81892
import math
n = int(input())
array = [[int(i) for i in input().split()] for i in range(2)] 
p1 = 0
p2 = 0
p3 = 0
pm = []
for i in range(n):
    p1 +=math.fabs(array[0][i]-array[1][i])
    p2 +=math.fabs(array[0][i]-array[1][i])**2
    p3 +=math.fabs(array[0][i]-array[1][i])**3
    pm.append(math.fabs(array[0][i]-array[1][i]))
print(p1)
print(math.sqrt(p2))
print(p3**(1/3))
print(max(pm))

Measured memory_bytes: 7904
using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			slove();
		}

		static void slove()
		{
			int N = int.Parse(Console.ReadLine());
			string[] str = Console.ReadLine().Split(' ');
			int[] a = str.Select(s => int.Parse(s)).ToArray();
			Array.Sort(a);
			Array.Reverse(a);
			int sum = 0;
			for(int i = 0; i < N; i++)
			{
				if (i % 2 == 0)
				{
					sum += a[i];
				}
				else
				{
					sum -= a[i];
				}
			}
			Console.WriteLine(sum);
			Console.ReadKey();
		}
	}
}


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

for i in range(N):
    run = out = point = 0
    while True:
        result = input()
        if result == "HIT":
            run += 1
            if run >= 4:
                point += 1
                run = 3
        elif result == "HOMERUN":
            point += (run + 1)
            run = 0
        else:
            out += 1
            if out == 3:
                break;
    print(point)


Measured memory_bytes: 5584
s = input()
s = s[::-1]

while 1:
    #print(s)
    #dreamの逆
    if s[:5] == "maerd":
        s=s[5::]
    #dreamerの逆
    elif s[:7] == "remaerd":
        s=s[7::]
    #eraseの逆
    elif s[:5] == "esare":
        s=s[5::]
    #eraserの逆
    elif s[:6] == "resare":
        s=s[6::]
    #出来ない
    else:
        print("NO")
        break
    #全部できた
    if len(s)==0:
        print("YES")
        break

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

int main(){
    int x, i;
    cin >> x;

    int sm = 400, bg = 599;
    for(i=1; i<=8; i++){
        if(x >= sm & x <= bg){
            break;
        }else{
            sm += 200;
            bg += 200;
        }
    }
    cout << 9 - i << '\n';
    return 0;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
inline int getint(void);
int main(void)
{
	int a=getint(),b=getint(),c=getint();
	if(b-a==c-b) printf("YES");
	else printf("NO");
	return 0;
}
inline int getint(void)
{
    int n=0,f=1;
	char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        n=n*10+ch-'0';
        ch=getchar();
    }
    return n*f;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
/*
#include<algorithm>
#include<array>
#include<cassert>
#include<cmath>
#include<cstdlib>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<typeinfo>
#include<utility>
#include<vector>
*/
#define int long long int
#define double long double
using namespace std;
#define INT_DMAX 1000000007
#define INF 1000000000000000007
const int MAX_N = 1 << 17;
#define rep(i, n) for (int(i) = 0, i##_len = (n); (i) < i##_len; (i)++)
#define reps(i, x) for (int(i) = 1; (i) <= (int)(x); (i)++)
#define rrep(i, x) for (int(i) = ((int)(x)-1); (i) >= 0; (i)--)
#define rreps(i, x) for (int(i) = ((int)(x)); (i) > 0; (i)--)
#define FOR(i, a, b) for (int(i) = (a); (i) < (b); (i)++)
#define pb push_back
#define mp make_pair
#define bit(n) ((int)(1) << (n))
#define all(x) (x).begin(), (x).end()
#define debug(x) std::cout << #x << ": " << (x) << std::endl
#define nint int
using namespace std;

int dy[] = {0, 0, 1, -1, 0};
int dx[] = {1, -1, 0, 0, 0};
typedef pair<int, int> p;
typedef pair<double, double> dop;
template <class T>
bool chmax(T& a, const T& b)
{
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b)
{
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
struct aaa {
    aaa()
    {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
    };
} aaaaaaa;


int orzero(int xnum, int ynum, int xcount, int ycount, int n)
{
    if (xnum == 0 && ynum == -1) {
        if (xcount == n) {
            return 0;
        }
    } else if (xnum == 0) {
        if (xcount == n / 3 && ycount == 2 * n / 3) {
            return 0;
        }
    } else if (ynum == 0) {
        if (ycount == n / 3 && xcount == 2 * n / 3) {
            return 0;
        }
    }
    return 1;
}

signed main()
{
    int n;
    cin >> n;
    std::vector<int> a(n, 0);
    rep(i, n)
    {
        cin >> a[i];
    }
    int flag = 0;

    int xnum = -1;
    int xcount = 0;
    int ynum = -1;
    int ycount = 0;
    int znum = -1;
    int zcount = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == xnum || xnum == -1) {
            xnum = a[i];
            xcount++;
        } else if (a[i] == ynum || ynum == -1) {
            ynum = a[i];
            ycount++;
        } else if (a[i] == znum || znum == -1) {
            znum = a[i];
            zcount++;
        } else {
            flag = 1;
            break;
        }
    }
    if (n % 3 != 0 && (xnum != 0 || xcount != n)) {
        flag = 1;
    }
    if (((xnum ^ ynum ^ znum) != 0 || (xcount != ycount || ycount != zcount)) && orzero(xnum, ynum, xcount, ycount, n)) {
        flag = 1;
    }
    if (flag) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
# A - 高橋君とホテルイージー
def main():
    n = int(input())
    k = int(input())
    x = int(input())
    y = int(input())
    cost = 0

    for i in range(1, n+1):
        if i <= k:
            cost += x
        else:
            cost += y
    else:
        print(cost)
        
    
if __name__ ==  "__main__":
    main()

Measured memory_bytes: 9032
num = list(map(int, input().split()))
n, tw = num[0], num[1]

w = [0]
v = [0]

for i in range(n):
    vals = list(map(int, input().split()))
    w.append(vals[0])
    v.append(vals[1])

if sum(w) < tw:
    tw = sum(w)

dp = [[0 for i in range(tw+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(1,tw+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j-w[i]])

print(dp[-1][-1])




Measured memory_bytes: 217660
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <istream>

using namespace std;

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

int main(){
	int n,m;
	cin >> n >> m;
	if(n%2==1&&m%2==1){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
A, B, C = map(int, input().split())

gokei = A + B + C
ans = 0

if A == B == C and all(map(lambda x: x % 2 == 0, (A, B, C))):
    print(-1)
else:
    while all(map(lambda x: x % 2 == 0, (A, B, C))):
        A = (gokei - A) / 2
        B = (gokei - B) / 2
        C = (gokei - C) / 2
        ans += 1
    print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX = 1e5+6;
const int INF = 1e19+8;
int n,k;
int h[MAX],dp[MAX];
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
	}
	
	for(int i=2;i<MAX;i++)
	{
		dp[i] = INF;
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			if(i > j)
			{
				dp[i] = min(dp[i],dp[i-j] + abs(h[i] - h[i-j]));
			}
		}
	}
	
	cout<<dp[n];
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll mod = 1e9+7;

int main(){
    string s;
    cin >> s;
    vector<int> a,pos;
    int cnt = 1;
    for (int i=1;i<s.length();i++){
        if (s[i]==s[i-1]){
            cnt++;
        } else {
            a.push_back(cnt);
            pos.push_back(i);
            cnt = 1;
        }
    }
    a.push_back(cnt);
    vector<int> ans(s.length(),0);
    for (int i=0;i<a.size();i+=2){
        ans[pos[i]-1] = (a[i]+1)/2 + a[i+1]/2;
        ans[pos[i]] = a[i]/2 + (a[i+1]+1)/2;
    }
    for (int i=0;i<ans.size();i++){
        cout << ans[i] << ' ';
    }
    cout << endl;
}

Measured memory_bytes: 1908
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 1LL << 60;
const ll MOD = (ll) 1e9 + 7;

int main(){
    int n, m;
    cin >> n >> m;
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int a;
            cin >> a;
            mp[a]++;
        }
    }
    int ans = 0;
    for (auto&& p : mp) {
        if (p.second == n) {
            ans++;
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
//#include <limits.h>
//#include <math.h>

#define Max(a, b) ((a > b) ? a : b)

int main() {
  int k, n;
  scanf("%d%d", &k, &n);
  int a[n];
  for (int i=0; i<n; i++)
    scanf("%d", a+i);
  int dis = k-a[n-1]+a[0];
  for (int i=0; i<n-1; i++)
    dis = Max(dis, abs(a[i]-a[i+1]));
  printf("%d\n", k-dis);
  return 0;
}


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

int bothStrings(string s, int n);

int main() {
    int N;
    string S;
    cin >> N;
    cin >> S;

    int max = 0;
    for(int i=0; i<N; i++) {
        int l = bothStrings(S, i);
        if(max < l)
            max = l;
    }
    cout << max << endl;
}

int bothStrings(string s, int n) {
    int left[26] = {0};
    int right[26] = {0};

    for(int i=0; i<=n; i++) {
        left[s[i] - 'a'] = 1;
    }
    for(int i=s.size()-1; i > n; i--) {
        right[s[i] - 'a'] = 1;
    }

    int ret = 0;
    for(int i=0; i < 26; i++) {
        if(left[i] > 0 && right[i] > 0) {
            ret++;
        }
    }
    return ret;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
q = int(input())
table = [0 for i in range(10**5+10)]
for i in range(n):
    table[a[i]] += 1

ans = 0
for i in range(len(table)):
    ans += table[i]*i

for i in range(q):
    b, c = map(int, input().split())
    ans = ans + table[b]*c - table[b]*b
    table[c] += table[b]
    table[b] = 0
    print(ans)




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

int main() {

    int x = 0;
    int a = 0;
    int b = 0;

    cin >> x >> a >> b;

    int c = b - a;  // 賞味期限を過ぎた日数

    if (c <= 0) {
        cout << "delicious";
    } else if (c <= x) {
        cout << "safe";
    } else {
        cout << "dangerous";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<cmath>
#include<queue>
#include<limits>
#include<cassert>
#include<set>
#include<tuple>
#include<map>

#define PB push_back
#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

using namespace std;
typedef long long ll;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n), b(n), c(n);
	REP(i, n) cin >> a[i];
	REP(i, n) cin >> b[i];
	REP(i, n) cin >> c[i];
	SORT(a);
	SORT(c);
	ll ans = 0;
	REP(i, n) {
		auto x = lower_bound(a.begin(), a.end(), b[i]); //aのb[i]以上の要素
		auto y = upper_bound(c.begin(), c.end(), b[i]); //cのb[i]以下の要素
		ans += (x - a.begin()) * (c.end() - y); //(a < b) * (b < c)
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1408
// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,mx;
int a[N],s[N],S[N];

int c[N<<1];
inline int lowbit(int x) { return x&-x; }
inline void add(int x,int y) {
    for (;x<=mx;x+=lowbit(x)) c[x]+=y;
}
inline int query(int x) {
    int res=0;
    for (;x;x-=lowbit(x)) res+=c[x];
    return res;
}

inline int check(int mid) {
    memset(c,0,sizeof(c)),mx=0;
    for (re int i=1;i<=n;++i) {
        if (a[i]<mid) s[i]=-1;
        else s[i]=1;
    }
    ll res=0;
    for (re int i=1;i<=n;++i) s[i]+=s[i-1],res+=(s[i]>=0);
    for (re int i=1;i<=n;++i) s[i]+=n+1,mx=max(mx,s[i]);
    for (re int i=1;i<=n;++i) res+=query(s[i]),add(s[i],1);
    ll cnt=1ll*n*(n-1)/2+n;
    return cnt-res<cnt/2+1;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) S[i]=a[i]=read();
    sort(S+1,S+n+1); int m=unique(S+1,S+n+1)-S-1;
    for (re int i=1;i<=n;++i) a[i]=lower_bound(S+1,S+m+1,a[i])-S;
    int L=1,R=m,ans=0;
    while (L<R) {
        int mid=L+R+1>>1;
        if (check(mid)) L=mid;
        else R=mid-1;
    }
    printf("%d\n",S[L]);
    return 0;
}

Measured memory_bytes: 5712
import java.util.*

fun main(args: Array<String>) {
    val scanner = Scanner(System.`in`)
    while (true) {
        val H =scanner.nextInt()
        val W =scanner.nextInt()
        if (H == 0 && W == 0) {
            break
        }
        val rectangle = (1..H).map { "#".repeat(W) }.joinToString("\n")
        println(rectangle)
        println()
    }
}



Measured memory_bytes: 28804
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6;
int arr[maxn];
bool mark[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
   	//freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n; cin>>n;
    memset(mark,false,sizeof(mark));
    int temp;
    for(int i=1;i<=n;i++){
    	cin>>arr[i]; 
    	if(arr[i]==i) mark[i]=true;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
    	if(mark[i]){
    		if(mark[i+1]){ans++; i++;}
    		else ans++;
    	}
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1664
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int main() {
  int Q; cin >> Q;
  for(int i = 0; i < Q; ++i) {
    long long A, B; cin >> A >> B;
    if(A > B) swap(A, B);
    if(A == B) cout << 2 * A - 2 << endl;
    else if(A + 1 == B) {
      cout << 2 * A - 2 << endl;
    } else {
      long long C = sqrtl(A * B);
      if(C * C == A*B) C--;
      if(C * (C+1) < A*B) {
        cout << 2 * C - 1 << endl;
      } else {
        cout << 2 * C - 2 << endl;
      }
    }
  }
  return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double ld;

int n;
const int mod = 1e9 + 7;
int dp[21][(1 << 21)];
int mat[21][21];

int solve(int idx, int mask)
{
  if(idx == n)
    return 1;
  int &ans = dp[idx][mask];
  if(ans != -1)
    return ans;
  ans = 0;
  for(int i = 0; i < n; i++)
  {
    if(!(mask & (1 << i)) && mat[idx][i])
      ans = (ans + solve(idx + 1, mask | (1 << i))) % mod;
  }
  return ans;
}
int main()
{
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      cin >> mat[i][j];
  memset(dp, -1, sizeof(dp));
  cout << solve(0, 0);
  return 0;
}


Measured memory_bytes: 172416
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cout << H << " "; debug_out(T...); }
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0) : x((x%mod+mod)%mod) {}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

vector<pair<ll,int>> factorize(ll n) {
  vector<pair<ll,int>> res;
  for (ll i = 2; i*i <= n; ++i) {
    if (n % i) continue;
    res.emplace_back(i,0);
    while (n%i == 0) {
      n /= i;
      res.back().second++;
    }
  }
  if (n != 1) res.emplace_back(n,1);
  return res;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  ll n;
  cin >> n;
  unordered_map<ll, int> mp;
  for (ll i = 2; i <= n; ++i) {
    vector<pair<ll,int>> res = factorize(i);
    for (auto p : res) {
      if (mp.count(p.first) == 0) mp[p.first] = p.second;
      else mp[p.first] += p.second;
    }
  }
  mint ans(1);
  for (auto p : mp) {
    // debug(p.first, p.second);
    ans *= (p.second+1);
  }
  cout << ans.x << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
int main(int argc, char* argv[]) {
   int a,b,t;
   cin >> a >> b >> t;
   int ans;
   ans = t/a * b;

   cout << ans << endl;
    
    return 0;
}


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


int main() {
    int n = 0, count = 0;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        if (a[i] != (i+1) && a[a[i]-1] == (i+1) && a[i] < (i+1)) {
            count++;
        }
    }
    cout << count;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
# define ll long long int
#define mm 1000000007
#define pb push_back
									//nestedcode



 int main(){
	ios::sync_with_stdio(false);
  	cin.tie(0); cout.tie(0);
  	string s,t;
  	ll n,nn,i,p=-1,ans=0;
  	map<char,vector<ll> > m;
    cin>>s>>t;
    n=s.length();
    nn=t.length();
    for(i=0;i<n;i++){
    	m[s[i]].pb(i);
	}
	for(i=0;i<nn;i++){
		if(m[t[i]].size() == 0){
			cout<<-1;
			return 0;
		}
		p=(upper_bound(m[t[i]].begin(),m[t[i]].end(),p)-m[t[i]].begin());
	
		if(p==m[t[i]].size()){
			ans++;
			p=m[t[i]][0];
		}else{
			p=m[t[i]][p];
		}	//cout<<p<<endl;
	}
	cout<<ans*n+p+1<<endl;
}

Measured memory_bytes: 1736
import datetime
from decimal import Decimal, ROUND_DOWN
import heapq
from fractions import gcd
from functools import reduce
from collections import deque
# from math import factorial
import itertools
import collections
import math
import sys
sys.setrecursionlimit(2000000)
# import statistics
# import numpy as np
# n = int(input())
# n, m, p = list(map(int, input().split()))
# a = list(map(int, input().split()))
#
#  abc = [int(input()) for i in range(5)]
#n = int(input())
#n, m = list(map(int, input().split()))
x, k, d = list(map(int, input().split()))
#l = list(map(int, input().split()))
# data = [list(map(int, input().split())) for i in range(n)]
# n = int(input())
# a = list(map(int, input().split()))
# b = list(map(int, input().split()))
# ab_sorted = sorted(ab, key=lambda x: x[0])
# data = [list(map(int, input().split())) for i in range(n)]
# print(min(15*n, 100*(n//10+1), 100*(n//10)+15*(n % 10)))
# for i in range(1, int(n**0.5)+1):

shou = x//d
amari = x % d

if x >= 0:
    if shou <= k:
        k -= shou
        if k % 2 == 0:
            ans = amari
        else:
            ans = min(abs(amari+d), abs(amari-d))
    else:
        ans = x-d*k
else:
    if -1*shou <= k:
        k += shou
        if k % 2 == 0:
            ans = amari
        else:
            ans = min(abs(amari+d), abs(amari-d))
    else:
        ans = abs(x+d*k)


# print(shou)
# print(amari)

print(ans)


Measured memory_bytes: 10120
#include<iostream>
#include<string>

using namespace std;

int main() {
	string s;
	cin >> s;

	int a[26] = {0};
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'a') {
			a[0]++;
		}
		if (s[i] == 'b') {
			a[1]++;
		}
		if (s[i] == 'c') {
			a[2]++;
		}
		if (s[i] == 'd') {
			a[3]++;
		}
		if (s[i] == 'e') {
			a[4]++;
		}
		if (s[i] == 'f') {
			a[5]++;
		}
		if (s[i] == 'g') {
			a[6]++;
		}
		if (s[i] == 'h') {
			a[7]++;
		}
		if (s[i] == 'i') {
			a[8]++;
		}
		if (s[i] == 'j') {
			a[9]++;
		}
		if (s[i] == 'k') {
			a[10]++;
		}
		if (s[i] == 'l') {
			a[11]++;
		}
		if (s[i] == 'm') {
			a[12]++;
		}
		if (s[i] == 'n') {
			a[13]++;
		}
		if (s[i] == 'o') {
			a[14]++;
		}
		if (s[i] == 'p') {
			a[15]++;
		}
		if (s[i] == 'q') {
			a[16]++;
		}
		if (s[i] == 'r') {
			a[17]++;
		}
		if (s[i] == 's') {
			a[18]++;
		}
		if (s[i] == 't') {
			a[19]++;
		}
		if (s[i] == 'u') {
			a[20]++;
		}
		if (s[i] == 'v') {
			a[21]++;
		}
		if (s[i] == 'w') {
			a[22]++;
		}
		if (s[i] == 'x') {
			a[23]++;
		}
		if (s[i] == 'y') {
			a[24]++;
		}
		if (s[i] == 'z') {
			a[25]++;
		}
	}
	int w = 0;
	for (int i = 0; i < 26; i++) {
		if (a[i] % 2 == 1) {
			w++;
			break;
		}
	}
	if (w == 1) {
		cout << "No" << endl;
	}
	else
		cout << "Yes" << endl;

	return 0;
}

Measured memory_bytes: 256