akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          	cerr<<"///REACHED///\n";
#define deb1(x)        	cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      	cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    	cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';
//#define N 1000000007 // prime modulo value 

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll , ll> 			pll;
typedef pair<ld, ld> 			pld;
typedef unordered_map<ll, ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5 + 7;
const ll 	MAX7 	= 	1e+7 + 7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const ll   	N   	=  	2*MAX5;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e9 + 7;


// <------------- Declare Variables Here ------------> //

ll T = 1;
ll n, x, k, m, y;
string s, t;
 
// <------------- Implement Functions Here ----------> //


// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> n >> s;
	ll i=0;
	while(i<n && s[i]=='R') i++;
	if(i == n) {
		cout<<0;return;
	}
	s = s.substr(i);
	n = s.length();

	vll w,r;
	for(ll i=0;i<n;i++) {
		if(s[i]=='W') w.pb(i);
		else r.pb(i);
	}
	reverse(all(r));

	i=0;
	while(i<w.size() && i<r.size()) {
		if(w[i] < r[i]) {
			i++;
		}
		else break;
	}
	cout<<min({i,(ll)w.size(),(ll)r.size()});
}	

int main() {
	fastio; randomINT;
	//cin >> T;
	while (T--) {
		MAIN();
	}
	return 0;
}

Measured memory_bytes: 6220
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
using namespace std;

  int main(){
int n,m;
cin >> n >> m;
int p[m],y[m];
rep(i,m) cin >> p[i] >> y[i];
vector<pint> v[n],a[n];
rep(i,m){
v[p[i]-1].push_back({y[i],i});
}
rep(i,n){
sort(v[i].begin(),v[i].end());
}
rep(i,n){
rep(j,v[i].size()){
a[i].push_back({v[i][j].second,j+1});
}
}
    pint t[m];
rep(i,n)sort(a[i].begin(),a[i].end());
rep(i,n){
rep(j,a[i].size()){
  t[a[i][j].first].first=i+1;
  t[a[i][j].first].second=a[i][j].second;
}
}
    rep(i,m){
      printf("%06lld", t[i].first);
      printf("%06lld", t[i].second);
      cout << endl;
    }
return 0;}

Measured memory_bytes: 13952
N, X = map(int, input().split())
x = list(map(int, input().split()))

def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    # if x%y:
    #     while x%y:
    #         z = x%y
    #         x, y = y, x
    #     else:
    #         return z
    # else:
    #     return y
    if y == 0:
        return x
    else:
        return gcd(y, x%y)


x.append(X)
x.sort()
# print(x)
# d = []
# for i in range(N):
#     d.append(x[i+1]-x[i])
# print(d)
for i in range(N):
    if i == 0:
        c = x[i+1]-x[i]
    else:
        c = gcd(x[i+1]-x[i], c)
print(c)


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

/*** Template Begins ***/

struct custom_hash {static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;return x ^ (x >> 31);}
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};
// USE : unordered_map<int, int, custom_hash> m;
//     : unordered_set<int, custom_hash> s;

typedef long long    ll;
typedef pair<int,int>  PII;
typedef pair<int, PII> PIII;
#define endl         '\n'
#define pb           push_back
#define INF          ll_MAX/10
#define F            first
#define S            second
#define mp           make_pair
#define ios          ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define hell         1000000007
#define all(a)       (a).begin(),(a).end()
ll power(ll x, ll y, ll p){ ll res = 1;x = x % p;while (y > 0){ if (y & 1) res = (res*x) % p;y = y>>1;x = (x*x) % p;} return res; } 

// Constants //

const int N = 1e5+7;

/*** Template Ends ***/

int n, m;
vector<PII> p[N];
int ans[N][12];

void fill_1(int i, int num, int x){

	if ( x == 0 ){
		for ( int j = 5; j >= 0; j-- ){
			ans[i][j] = num%10;
			num /= 10;
		}
	}
	else{
		for ( int j = 11; j >= 6; j--){
			ans[i][j] = num%10;
			num /= 10;
		}
	}

}


int main(){
	
	ios;
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	cin >> n >> m;
	int pi, yi;
	for (int i = 0; i < m; i++){
		cin >> pi >> yi;
		p[pi].pb(mp(yi, i));
	}
	
	for (int i = 1; i <= n; i++){
		sort(all(p[i]));

		for (int j = 0; j < p[i].size(); j++){
			//cout << "here" << endl;
			// have to fill up ans[p[i].i]
			fill_1(p[i][j].S, i, 0);
			fill_1(p[i][j].S, j+1, 1);
		}
	}

	for ( int i = 0; i < m; i++ ){
		for ( int j = 0; j < 12; j++ )	cout << ans[i][j];
		cout << endl;
	}
	

	return 0;
}














Measured memory_bytes: 11648
// Created by Nandu Vinodan
#include <bits/stdc++.h>

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define vi vector<int>
#define pi pair<int, int>
#define INF INT_MAX
#define _INF INT_MIN
#define TC 0

using namespace std;
using ll = long long;

void testcase() {
    int k; cin >>  k;

    if (k <= 12) {
    	cout << k;
    	return; 
    }
    int cur = 0;
    unordered_map<char, string> mp;
    mp['0'] = {"01"};
    mp['1'] = {"012"};
    mp['2'] = {"123"};
    mp['3'] = {"234"};
    mp['4'] = {"345"};
    mp['5'] = {"456"};
    mp['6'] = {"567"};
    mp['7'] = {"678"};
    mp['8'] = {"789"};
    mp['9'] = {"89"};
    
    queue <string> q;
    q.push("1");
    q.push("2");
    q.push("3");
    q.push("4");
    q.push("5");
    q.push("6");
    q.push("7");
    q.push("8");
    q.push("9");
    while (cur < k) {
    	string u = q.front();
    	q.pop();
    	cur++;
    	if (cur == k) {
    		cout << u;
    		return;
    	}
    	char c = u.back();
    	string nei = mp[c];
    	for (char v : nei) {
    		string dummy = "a"; dummy[0] = v;
    		q.push(u + v);
    	}
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    if (TC)
        cin>>t;
    while(t--) {
        testcase();
    }
    return 0;
}

Measured memory_bytes: 13824
# reffer https://qiita.com/hironobukawaguchi3/items/55e751ecf72bb7894a46
N, K = map(int, input().split())
S = input()
Nums = []
now = 1 # 今見ている数
cnt = 0 # nowがいくつならんでいるか

for i in range(N):
  if S[i] == str(now):
    cnt+=1
  else:
    Nums.append(cnt)
    now = 1 - now
    cnt = 1

if cnt != 0:
  Nums.append(cnt)

if len(Nums) % 2 == 0:
  Nums.append(0)

Add = 2 * K + 1
sum = [0] * (len(Nums) + 1)
for i in range(len(Nums)):
  sum[i + 1] = sum[i] + Nums[i]
ans = 0
for i in range(0, len(Nums), 2):
  left = i
  right = min(i + Add, len(Nums))
  tmp = sum[right] - sum[left]
  ans = max(tmp, ans)

print(ans)

Measured memory_bytes: 7884
import sys

H, W = map(int, input().split())
S = [list(sys.stdin.readline().strip()) for _ in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

if len(S) == len(S[0]) == 1:
    if S[0][0] == "#":
        print("Yes")
    else:
        print("No")
    exit()

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            ok = False
            for k in range(4):
                ny = i + dy[k]
                nx = j + dx[k]
                if not (0 <= ny <= H - 1 and 0 <= nx <= W - 1):
                    continue
                if S[ny][nx] == "#":
                    ok = True
                    break
            if ok is False:
                print("No")
                exit()
print("Yes")


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

int main() {
  string n;
  cin >> n;
  vector<int> ans(3);
  for(int i = 0;i < 3;i++){
   if(n.at(i) == '1'){
     ans.at(i) = 9;
  }else if(n.at(i) == '9'){
     ans.at(i) = 1;
   }
  }
    cout << ans.at(0)*100 + ans.at(1)* 10 + ans.at(2) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pll = pair<long long, long long>;
const long long INF = 1<<29;

const int MOD = 1000000007;
long long ruizyou(long long m,long long n){
  if(m == 0)return 0;
  if(m == 1)return 1;
  long long ans = 1;
  long long tmp = m;
  for(int i=0;i<=30;i++){
    if(n & (1<<i)){
      ans *= tmp;
      ans %= MOD;
    }
    tmp *= tmp;
    tmp %= MOD;
  }
  return ans;
}
long long kaizyou(long long x){
  if(x == 0)return 1;
  return x * kaizyou(x-1) % MOD;
}
long long comb(long long x,long long y){
  long long bunsi = kaizyou(x);
  long long bunbo = kaizyou(x-y) * kaizyou(y) % MOD;
  return bunsi * ruizyou(bunbo,MOD-2) % MOD;
}
struct unionfind{
  vector<int> par;
  vector<int> hukasa;
  vector<int> kazu;
  unionfind(int n){
    par = vector<int>(n);
    hukasa = vector<int>(n,0);
    kazu = vector<int>(n,1);
    for(int i=0;i<n;i++){
      par.at(i) = i;
    }
  }
  int root(int x){
    if(par.at(x) == x)return x;
    return root(par.at(x));
  }
  void unite(int x,int y){
    int rx = root(x);
    int ry = root(y);
    if(rx == ry)return;
    if(hukasa.at(rx) >= hukasa.at(ry)){
      par.at(ry) = rx;
      hukasa.at(rx) = max(hukasa.at(ry) + 1,hukasa.at(rx));
      kazu.at(rx) += kazu.at(ry);
    }
    else{
      par.at(rx) = ry;
      kazu.at(ry) += kazu.at(rx);
    }
  }
  void newkazu(){
    int n = kazu.size();
    for(int i=0;i<n;i++){
      kazu.at(i) = kazu.at(root(i));
    }
  }
  bool same(int x,int y){
    return root(x) == root(y);
  }
};
int ctoi(char a){
  return a - '0';
}
long long gcd(long long a,long long b){
  long long c = max(a,b);
  long long d = min(a,b);
  if(d % c == 0)return c;
  return gcd(c,d%c);
}
long long lcm(long long a,long long b){
  return a * b / gcd(a,b);
}
int main(){
  int x;
  cin >> x;
  int ans;
  for(int i=1;i<361;i++){
    if(x * i % 360 == 0){
      ans = i;break;
    }
  }
  cout << ans << endl;
}

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

# define C continue;
# define R return

# define D double
# define I insert
# define ll long long
# define ld long double

# define ull unsigned long long
# define ui unsigned int

# define pb push_back
# define pf push_front

# define vi vector < int >
# define vc vector < char >
# define vs vector < string >
# define vb vector < bool >
# define vd vector < D >
# define vll vector < ll >
# define vull vector < ull >
# define vld vector < ld >
# define PQ priority_queue

# define vvi vector < vector < int > >
# define vvb vector < vector < bool > >
# define vvc vector < vector < char > >
# define vvs vector < vs >
# define vvll vector < vector < ll > >
# define vvd vector < vector < D > >
# define vvld vector < vector < ld > >

# define all(v) (v).begin() , (v).end()
# define allrev(v) (v).rbegin() , (v).rend()
# define allcomp(v) v.begin() , v.end() , comp
# define allrevcomp(v) v.rbegin() , v.rend() , comp

# define pii pair < int , int >
# define pll pair < ll , ll >
# define pld pair < ld , ld >
# define pDD pair < D , D >

# define vpld vector < pld >
# define vpii vector < pii >
# define vpll vector < pll >
# define vpDD vector < pDD >

# define vvpii vector < vector < pii > >
# define F first
# define S second
# define mp make_pair

# define dist(a,b,p,q) sqrt((p-a)*(p-a) + (q-b)*(q-b))

# define pp(n) printf("%.10Lf",n);
# define line cout<<"\n";
# define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);

string vow = "aeiou";
int month[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};

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

const ld pie = 3.1415926535897932384626 ;
const ll mod = 1e9 + 7 ;

/// Tip : If a and b are positive integers ; we may say - ceil (a/b) = 1 + floor ( (a-1)/b ) .

const int N = 1e5 + 10 ;
const int M = 1e2 + 2 ;

ll dp[N][M] ;
int n , w ;

pii v[N] ;
const ll inf = 1e12 ;

ll f ( int cap , int indx )
{
    if ( cap < 0 )
        return -inf ;

    if ( indx == n )
        return 0 ;

    if ( dp[cap][indx] != -1 )
        return dp[cap][indx] ;

    ll q1 = f ( cap , indx + 1 ) ;
    ll q2 = f ( cap - v[indx].F , indx + 1 ) + v[indx].S ;

    ll ans = max ( { 0LL , q1 , q2 } ) ;
    dp[cap][indx] = ans ;

    return ans ;
}

void solve ( int test_case )
{
    cin >> n >> w ;

    for ( int i=0 ; i < n ; i ++ )
        cin >> v[i].F >> v[i].S ;

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

    f ( w , 0 ) ;
    ll ans = dp[w][0] ;

    cout << ans ; line ;
}

int main()
{fast
    int t = 1;
    // cin >> t;

    for ( int i=1 ; i <= t ; i ++ ) solve ( i ) ;
    return 0;
}


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

int main() {

  vector<int> v(3);
  cin >> v.at(0) >> v.at(1) >> v.at(2);
  int c = v.at(2);
  
  sort(v.begin(),v.end());
  if (v.at(1) == c) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int i=0,j=n-1,cnt=0;
    while(i<j){
        if(s[i] == 'R'){
            i++;
        }
        if(s[j] == 'W'){
            j--;
        }
        else if(s[i] == 'W' && s[j] == 'R'){
            cnt++;
            j--;
            i++;
        }
    }
    cout<<cnt;
    return 0;
}

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

typedef long long ll;
ll mod = 1000000007;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    ll n = s.length();
    vector<ll> ac(n, 0), cc(n, 0), ncl(n, 0), ncr(n, 0);
    ac[0] = (s[0] == 'A');
    cc[n - 1] = (s[n - 1] == 'C');
    ncl[0] = (s[0] == '?');
    ncr[n - 1] = (s[n - 1] == '?');

    for(int i = 1; i < n; i++)
    {
        ac[i] = ac[i - 1];
        ac[i] += (int)(s[i] == 'A');
        ncl[i] = ncl[i - 1];
        ncl[i] += (int)(s[i] == '?');
    }

    for(int i = (n - 2); i >= 0; i--)
    {
        cc[i] = cc[i + 1];
        cc[i] += (int)(s[i] == 'C');
        ncr[i] = ncr[i + 1];
        ncr[i] += (int)(s[i] == '?');
    }   

    vector <ll> p3(n + 1, 1);

    for(int i = 1; i <= n; i++)
        p3[i] = (p3[i - 1] * 3) % mod;

    ll ans = 0;

    for(int i = 1; i < (n - 1); i++)
    {
        if(s[i] == 'A')
            continue;
            
        if(s[i] == 'C')
            continue;

        ll lans = 0, nl = ncl[i - 1], nr = ncr[i + 1], rans = 0;
        lans = (p3[nl] * ac[i - 1]) % mod;

        if(nl)
            lans = (lans + (nl * p3[nl - 1]) % mod) % mod;

        rans = (p3[nr] * cc[i + 1]) % mod;

        if(nr)
            rans = (rans + (nr * p3[nr - 1])% mod) % mod;

        ans = (ans + (lans * rans)) % mod;
    }   

    ans = (ans + mod) % mod;
    cout << ans <<"\n";
    return 0;
}


Measured memory_bytes: 4432
#include <bits/stdc++.h>
using namespace std;
bool have[1000007];
int cnt[1000007];
int main(){
	int n;
	cin >> n;
	int a[n];
	for(int i = 0; i < n; i++){
		cin >> a[i];
		cnt[a[i]]++;
	}
	sort(a, a + n);
	int ans = 0;
//	cout << "aa";
	for(int i = 0; i < n; i++){
		if(cnt[a[i]] > 1){
			if(!have[a[i]]){
				for(int j = a[i]; j <= 1000000; j += a[i]){
					have[j] = true;
				}
			}
		}else if(!have[a[i]]){
			for(int j = a[i]; j <= 1000000; j += a[i]){
				have[j] = true;
			}
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
} 

Measured memory_bytes: 9192
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repf(i,a,b) for (int i = (a); i < (b); i++)
#define repi(i,a,b) for (int i = (a); i <= (b); i++)
#define repr(i,a,b) for (int i = (a); i >= (b); i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(all(x));
#define RSORT(x) sort(rall(x));
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vd = vector<double>;
using vb = vector<bool>;
using pii = pair<int, int>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using tiii = tuple<int, int, int>;
const int inf = 1<<29;
const ll mod = 1000000007;
const double eps = 1e-9;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

int main () {
 int A, B; cin >> A >> B;
 if ((A+B)%2==0) {
   cout << (A+B)/2 << endl;
 }
 else {
   cout << "IMPOSSIBLE" << endl;
 }
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define H 510
ll dx[]={0,1,0,-1},dy[]={1,0,-1,0};
ll h,w;
char c[H][H];
ll bane[H][H],goal[H][H];
long double f(ll x,ll y,long double k){
	return min((long double)goal[x][y],(long double)bane[x][y]+k);
}
bool solve(long double k){
	long double sum=0;
	ll cnt=0;
	rep(i,h)rep(j,w)if(c[i][j]=='.'){
		sum+=f(i,j,k);
		cnt++;
	}
	sum/=(long double)cnt;
	//cout<<"solve:"<<sum<<" "<<k<<endl;
	return sum<=k;
}

int main(){
	cin>>w>>h;
	ll sx,sy,gx,gy;
	rep(i,h)rep(j,w){
		cin>>c[i][j];
		if(c[i][j]=='s')sx=i,sy=j,c[i][j]='.';
		if(c[i][j]=='g')gx=i,gy=j;
		bane[i][j]=goal[i][j]=1e17;
	}
	queue<ll> Qx,Qy,Qcost;
	Qx.push(gx); Qy.push(gy); Qcost.push(0);
	while(!Qx.empty()){
		ll x=Qx.front(),y=Qy.front(),cost=Qcost.front();
		Qx.pop(); Qy.pop(); Qcost.pop();
		if(goal[x][y]<=cost)continue;
		goal[x][y]=cost;
		rep(r,4){
			ll xx=x+dx[r],yy=y+dy[r];
			if(0<=xx&&xx<h&&0<=yy&&yy<w&&c[xx][yy]=='.'){
				Qx.push(xx);
				Qy.push(yy);
				Qcost.push(cost+1);
			}
		}
	}
	rep(i,h)rep(j,w)if(c[i][j]=='*'){
		Qx.push(i);
		Qy.push(j);
		Qcost.push(0);
	}
	while(!Qx.empty()){
		ll x=Qx.front(),y=Qy.front(),cost=Qcost.front();
		Qx.pop(); Qy.pop(); Qcost.pop();
		if(bane[x][y]<=cost)continue;
		bane[x][y]=cost;
		rep(r,4){
			ll xx=x+dx[r],yy=y+dy[r];
			if(0<=xx&&xx<h&&0<=yy&&yy<w&&c[xx][yy]!='#'&&c[xx][yy]!='*'){
				Qx.push(xx);
				Qy.push(yy);
				Qcost.push(cost+1);
			}
		}
	}
	/*cout<<"goal"<<endl;
	rep(i,h){
		rep(j,w){
			if(goal[i][j]==1e17)cout<<"# ";
			else cout<<goal[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<"bane"<<endl;
	rep(i,h){
		rep(j,w){
			if(bane[i][j]==1e17)cout<<"# ";
			else cout<<bane[i][j]<<" ";
		}
		cout<<endl;
	}*/
	long double l=0,r=1e15,mid;
	rep(d,100){
		mid=(l+r)/2.0;
		if(solve(mid))r=mid;
		else l=mid;
	}
	cout<<fixed<<setprecision(9)<<f(sx,sy,r)<<endl;
	/*for(double x=0.01;x<=10.0;x+=0.01){
		bool res=solve(x);
		if(res!=(r<x))cout<<"WrongAnswer"<<endl;
	}*/
}




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

int main()
{
    int n,j,x,i;
    cin>>n;
    for(i=0;i<=n;i++)
    {
        for(j=1;j<=1000;j++)
        {
            for(x=2;x<=10;x++)
            {
                if(ceil(pow(j,x))>n) break;
                if(ceil(pow(j,x))==n-i)
                {
                    cout<<n-i;
                    return 0;
                }
            }
        }
    }
    return 0;
}


Measured memory_bytes: 768
#include<iostream>

using namespace std;

int main(){

	int a, b, k;
	int i = 100;
	int c = 0;

	cin >> a >> b >> k;

	while( c < k ){
		if( a % i == 0 && b % i == 0 ){
			c = c + 1;
		}
		i = i - 1;
	}

	cout << i + 1 << endl;


	return 0;
}

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

public class Main {
	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int n = sc.nextInt();
		//int m = sc.nextInt();

		/*
		int[] a = new int[n];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
		}
		*/


		ArrayList<Integer> a = new ArrayList<>();
		for(int i=0;i<n;i++) {
			int temp = sc.nextInt();
			a.add(temp);
		}

		Collections.sort(a);
		ArrayList<Integer> b = new ArrayList<>();
		for(int i=0;i<n;i++) {
			int temp = sc.nextInt();
			b.add(temp);
		}

		Collections.sort(b);
		ArrayList<Integer> c = new ArrayList<>();
		for(int i=0;i<n;i++) {
			int temp = sc.nextInt();
			c.add(temp);
		}

		Collections.sort(c);

		
		int indexB = 0;
		int indexC=0;

		long[] holder = new long[n];

		for(int i=0;i<n;i++) {
			holder[i] =0;
			while(indexC<n) {
				if(b.get(i)<c.get(indexC)) {
					holder[i]=n-indexC;
					break;
				}else {
					indexC++;
				}
			}
		}

		for(int i=1;i<n;i++) {
			holder[n-i-1]+=holder[n-i];
		}

		long sum =0;

		for(int i =0;i<n;i++) {
			while(indexB<n) {
				if(a.get(i)<b.get(indexB)) {
					sum+=holder[indexB];
					break;
				}else {
					indexB++;
				}
			}
		}



		System.out.println(sum);

		/*
		TreeMap<Integer,Integer> treeMap = new TreeMap<>();
		treeMap.put(b[n], n);
		*/

	}
}
/*
class City{
	int order;
	int prefecture;
	int year;
	int number;
	City(int order,int prefecture, int year){
		this.order = order;
		this.prefecture = prefecture;
		this.year = year;
	}
}
*/

Measured memory_bytes: 98740
class Heep
  def initialize
    @node = []
  end
  def insert(num)
    i = @node.size
    @node[i] = num
    down_heap(i)
  end
  def extract
    ret = @node[0]
    @node[0] = @node.pop()
    up_heap(0)
    return ret
  end
  def modify(i, val)
    if @node[i] > val
      @node[i] = val
      down_heap(i)
    else
      @node[i] = val
      up_heap(i)
    end
  end
  def up_heap(i)
    h = @node.size
    largest = i
    l = 2 * i + 1
    largest = l if l < h && @node[l] > @node[largest]
    r = 2 * i + 2
    largest = r if r < h && @node[r] > @node[largest]
    if largest != i then
      @node[i], @node[largest] = @node[largest], @node[i]
      up_heap(largest)
    end
  end
  def down_heap(i)
    p = (i+1)/2-1
    while i > 0 && @node[p] < @node[i]
      @node[i], @node[p] = @node[p], @node[i]
      i = p
      p = (i+1)/2-1
    end
  end
end

heep = Heep.new()
loop do
  cmd, num = gets.split
  case cmd;
  when "insert";
    heep.insert(num.to_i)
  when "extract";
    puts heep.extract
  when "end";
    break
  end
end

Measured memory_bytes: 16732
package main
import (
	"fmt"
	"bufio"
	"os"
)

func main(){
	stdin := bufio.NewScanner(os.Stdin)
	var i string
	count_max:=0
	count_now:=0
	if stdin.Scan(){
		i=stdin.Text()
	}

	for iter:=0;iter<len(i);iter++{
		if(i[iter] == 'A' || i[iter] == 'T' || i[iter] == 'C' || i[iter] == 'G'){
			count_now++
		}else{
			if count_max < count_now {
				count_max = count_now
			}
			count_now = 0
		}
	}
	if count_max < count_now {
		count_max = count_now
	}
	fmt.Println(count_max)
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  N -= 1;
  K -= 1;
  cout << (N + K - 1) / K << endl;
}

Measured memory_bytes: 640
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e18;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}


int main(){
    ll N, Q; cin >> N >> Q;
    string s; cin >> s;
    vl ls(Q, 0), rs(Q, 0);
    REP(i, Q){
        ll l, r; cin >> l >> r; ls[i] = l-1; rs[i] = r-1;
    }
    vl sum(N, 0); ll suml = 0;
    FOR(i, 1, N){
        if(s[i-1] == 'A' && s[i] == 'C'){
            suml += 1;
        }
        sum[i] = suml;
    }
    REP(i, Q){
        cout << sum[rs[i]] - sum[ls[i]] << endl;
    }
    return 0;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int N, x=0;

 cin >> N;

 int a[N]={0};

 for(int i=0;i<N;i++){
     cin >> a[i];
 }

 for(int i=0;i<N;i++){
     x=a[x]-1;
    // cout << x << endl;
     if(x==1){
         cout<< i+1 <<endl;
         break;
     }
     else if(i==N-1){
         cout << -1 << endl;
         break;
        }
 }

}

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

v = (p2[0] - p1[0], p2[1] - p1[1])
v = (-v[1], v[0])
p3 = (p2[0] + v[0], p2[1] + v[1])
v = (p3[0] - p2[0], p3[1] - p2[1])
v = (-v[1], v[0])
p4 = (p3[0] + v[0], p3[1] + v[1])

print(p3[0], p3[1], p4[0], p4[1])

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

#define fi first
#define se second
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define endl '\n'

#define si(v) int(v.size())
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep2(i, n, m) for (ll i = n; i <= (m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (m); --i)

template<class T, class U> void chmax(T &a, U b) { if (a < b) a = b; }
template<class T, class U> void chmin(T &a, U b) { if (b < a) a = b; }

using ll = long long;
using ld = long double;
using namespace std;

constexpr ll MOD = 1000000007;

struct UnionFind {
  vector<int> par, siz;

  UnionFind(int n) : par(n), siz(n, 1) {
    for (int i = 0; i < n; ++i) par[i] = i;
  }

  int root(int x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }

  bool unite(int x, int y) {
    x = root(x);
    y = root(y);

    if (x == y) return false;

    if (siz[x] < siz[y]) swap(x, y);
    siz[x] += siz[y];
    par[y] = x;
    return true;
  }

  bool same(int x, int y) {
    return root(x) == root(y);
  }

  int size(int x) {
    return siz[x];
  }
};

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

  int n, m; cin >> n >> m;
  vpi edge(m);

  rep(i, m) cin >> edge[i].fi >> edge[i].se;

  int ans = 0;
  rep(i, m) {
    UnionFind uf(n);
    
    rep(j, m) {
      if (i == j) continue;
      uf.unite(edge[j].fi-1, edge[j].se-1);
    }

    bool connect = true;
    rep(i, n-1) if (!uf.same(i, i+1)) connect = false;

    if (!connect) ++ans;
  }

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

Measured memory_bytes: 3656
#ifdef loc
    #include "loc_debug.h"
#else
    #include <bits/stdc++.h>
    #define pr(...)
    #define pra(a,n)
    #define praa(a,n,m)
    #define prl()
#endif

typedef long long ll;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define sz(a) int(a.size())
const int N = 100005;
ll a[105], f[105][N], w[105], v[105], inf = 1e18 + 5;

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    int n, W;
    std::cin >> n >> W;
    rep(i, 1, n + 1) {
        std::cin >> w[i] >> v[i];
    }
    rep(i, 0, (int)N) {
        f[0][i] = inf;
    }
    f[0][0] = 0;
    rep(i, 1, n + 1) {
        rep(j, 0, (int)N) {
            f[i][j] = f[i - 1][j];
        }
        rep(j, v[i], (int)N) {
            f[i][j] = std::min(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    ll ans = 0;
    rep(i, 0, (int)N) {
        if(f[n][i] <= W) {
            ans = i;
        }
    }
    std::cout << ans << std::endl;
}


Measured memory_bytes: 80128
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();

		int[] num = new int[N];
		int[] d = new int[K];
		int[][] A = new int[K][N];

		int i = 0;

		while(i < N) {
			num[i] = 0;
			i++;
		}

		i = 0;
		while(i<K) {
			d[i] = sc.nextInt();
			for(int j = 0; j < d[i];j++) {
				A[i][j] = sc.nextInt();
				num[A[i][j]-1] += 1;
			}
			i++;
		}


		int counter = 0;
		for(i = 0 ; i < N ; i++ ) {
			if(num[i] == 0) {
				counter++;
			}

		}
		System.out.println(counter);
	}

}


Measured memory_bytes: 46184
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define clr(a,b) memset(a,b,sizeof(a))
#define all(v) ((v).begin()),((v).end())
double const EPS = 1e-8, PI = acos(-1);
const int N = 1e5 + 9, OO = 1e9;

int arr[N];

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i)
    cin >> arr[i];
  sort(arr, arr+n);
  int ans = arr[(n/2)] - arr[(n/2) - 1];
  cout << ans;
  return 0;
}


Measured memory_bytes: 764
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N;
    vector<int> A;
    cin>>N;
    for (int i=0; i<N; i++) {
        int x;
        cin>>x;
        A.push_back(x);
    }
    
   int max = *max_element(A.begin(), A.end());
    int min=*min_element(A.begin(), A.end());
    cout<<max-min<<endl;

    return 0;
}


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

using namespace std;

int main() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 0, ret = 1e9;
  for (int i = 1; i < n; ++i) {
    if (s[i] == 'E') ans++;
  }
  ret = min(ans, ret);
  for (int i = 1; i < n; ++i) {
    if (s[i - 1] == 'W') ans++;
    if (s[i] == 'E') ans--;
    ret = min(ans, ret);
  }
  cout << ret << endl;
}

Measured memory_bytes: 900
#include<bits/stdc++.h>
using namespace std;
int n,k,m;
int main() {
	scanf("%d%d",&n,&k);
	if(k>(n-2)*(n-1)/2)printf("-1");
	else {
		m=n-1+(n-1)*(n-2)/2-k;
		printf("%d\n",m);
		for(int i=2; i<=n; i++,m--) {
			printf("1 %d\n",i);
		}
		for(int i=2; i<=n; i++) {
			for(int j=i+1; j<=n; j++,m--) {
				if(m==0)break;
				printf("%d %d\n",i,j);
			}
		}
	}
}

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

int main() {
  int N,T,A;
  cin >> N>>T>>A;
  vector<int> h(N);
  for(int i=0;i<N;i++){
    cin >> h[i];
  }

  int idx=0;
  int dif=100000000;
  int tmp=0;
  for(int i=0;i<N;i++){
    tmp = T*1000-h[i]*6;
    //cout << tmp << endl;
    if(abs(tmp - A*1000)<dif){
      dif =abs(tmp - A*1000);
      idx=i;
    }
  }

cout << idx+1 << endl;
  }


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

class Main{
    public static void main(String args[]){
	int n;
	Scanner in = new Scanner(System.in);
	n = in.nextInt();
	int[] all = new int[n];
	int u,each,cost;
	cost = in.nextInt();
	each = in.nextInt();
	u = in.nextInt();

	for(int i=0;i<n;i++){
	    all[i] = in.nextInt();
	}
	Arrays.sort(all);

	int ans=0;
	for(int i=n-1;i>=0;i--){
	    u += all[i];
	    cost += each;
	    if (u/cost > ans)ans = u/cost;
	}
	System.out.println(ans);
    }
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main ()
{
    ll A,B,a[3];
    scanf("%lld %lld",&A,&B);
    a[0]=A-B;
    a[1]=A*B;
    a[2]=A+B;
    sort(a,a+3);
    printf("%lld",a[2]);
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
char p[101000];
int n, w[101000], cnt;
int main() {
	int i, j;
	scanf("%s", p+1);
	for (i = 1; p[i]; i++);
	n = i - 1;
	if (p[n] == '1' || p[1]=='0') {
		puts("-1");
		return 0;
	}
	for (i = 1; i < n; i++)if (p[i] != p[n - i ]) {
		puts("-1");
		return 0;
	}
	int bef = 0, bn = 0;
	for (i = 1; i <= n; i++) {
		if ((p[i] == '1' && i<=n/2)||i==n) {
			cnt++;
			if (bn)printf("%d %d\n", bn, cnt);
			int pv = cnt;
			for (j = 1; j < i - bef; j++) {
				printf("%d %d\n", pv, ++cnt);
			}
			bn = pv;
			bef = i;
		}
	}
}


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

int main(){//素因数分解ではなく、単に大きな数で割れるか否か
  ll N;//入力からlong long
  cin>>N;
  
  ll sqrt=pow(N,0.5);//平方数で近い数で割りたい
  ll FS=floor(sqrt);//切り捨て
  ll tmp;
  ll ans=1e18;//最小化問題：答の初期値は無限大
  
  for (ll i=FS; i>=1;--i){
    if (N%i!=0) continue;//割り切れなければスルー
    tmp=N/i;//約数に分解する
    ans=tmp+i-2;//約数が見つかれば、答は簡単に出る
    break;//ブレイクしないと延々と計算してしまう
  }
  
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace AtCoder.XXX.B
{ 
    public class Program
    {
        public static void Main(string[] args)
        {
            var s = r();
            var t =r();
            var cnt = 0;

            for(var i = 0;i< s.Length;i++)
			{
                if(s[i] != t[i])
				{
                    cnt++;
				}
			}
            P(cnt);
        }

        private static StreamReader sr;
        public static int[] Ecr()
        {
            if (sr == null)
            {
                sr = new StreamReader("input.txt", Encoding.GetEncoding("UTF-8"));
            }
            return sr.ReadLine().Split().Select(int.Parse).ToArray();
        }
        public static string Er()
        {
            if (sr == null)
            {
                sr = new StreamReader("input.txt", Encoding.GetEncoding("UTF-8"));
            }
            return sr.ReadLine();
        }
        public static string r()
        {
            return Console.ReadLine();
        }
        public static  int[] cr()
        {
            return Console.ReadLine().Split().Select(int.Parse).ToArray();
        }
        public static int cri()
        {
            return int.Parse(Console.ReadLine());
        }
        public static void P(string str)
        {
            Console.WriteLine(str);
        }
        public static void P(int num)
        {
            P(num.ToString());
        }
    }
}


Measured memory_bytes: 27368
#include<bits/stdc++.h>
#define ll long long
using namespace std;
stack<int>st;
char s[100005];
int main()
{
    scanf("%s",s+1);
    int len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        if(s[i]=='0')
        {
            if(st.empty())st.push(0);
            else if(st.top()==1)
            {
                st.pop();
            }
            else st.push(0);
        }
        else
        {
            if(st.empty())st.push(1);
            else if(st.top()==0)
            {
                st.pop();
            }
            else st.push(1);
        }
    }
    printf("%d\n",len-st.size());
}


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

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

const int maxn = 150;

int main() {
	int a[maxn];
	int N;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		scanf("%d", &a[i]);
	std::sort(a + 1, a + 1 + N);
	int ans = 0x3f3f3f3f;
	for (int i = 1; i <= 100; i++) {
		int res = 0;
		for (int j = 1; j <= N; j++) {
			res += ((a[j] - i) * (a[j] - i));
		}
		ans = std::min(ans, res);
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 256
import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

a = _S()

if a.islower():
    print('a')
else:
    print('A')

Measured memory_bytes: 91720
#include<bits/stdc++.h>
#define ll long long
#define all(x) (x).begin(),(x).end()
#define sz(x) (x).size()
using namespace std;


const int maxn=1e6+7;
int a[maxn],x,y,z;

    long long C[2100][2100];


const ll mod=1e9+7;

int main (){

    for(int i = 0; i <= 2009; i ++) C[i][0] = 1;
    for(int i = 1; i <= 2009; i ++)
        for(int j = 1; j <= i; j ++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
            //cout<<C[5][2]<<endl;
    ll n,k;cin>>n>>k;
    n-=k;
    for(int i=1;i<=k;i++){
        cout<<C[k-1][i-1]*C[n+1][i]%mod<<endl;
    }
    return 0;
}



Measured memory_bytes: 33536
from collections import deque, defaultdict

N, M = map(int, input().split())
ab = []
for _ in range(N + M - 1):
    a, b = map(int, input().split())
    ab.append((a, b))

out = defaultdict(list)
in_cnt = defaultdict(int)
rev = defaultdict(list)
for a, b in ab:
    out[a].append(b)
    in_cnt[b] += 1
    rev[b].append(a)

queue = deque(i for i in range(1, N + 1) if in_cnt[i] == 0)
sorted_ans = []

while len(queue) != 0:
    v = queue.popleft()
    sorted_ans.append(v)
    for v2 in out[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

order = [0] + [i + 1 for i, v in sorted(enumerate(sorted_ans), key=lambda x: x[1])]
ans = [0] * (N + 1)
ans[sorted_ans[0] + 1] = 0

for v in sorted_ans[:0:-1]:
    ans[v] = max((order[v2], v2) for v2 in rev[v])[1]
    
for a in ans[1:]:
    print(a)


Measured memory_bytes: 74340
def check(s, n, k):
    l = n - k
    r = k

    for c in s[l + 1:r]:
        if c != s[l]:
            return False
    
    return True


def submit():
    s = input()
    n = len(s)

    if check(s, n, n):
        print(n)
        return

    l = 1
    r = n
    while l + 1 < r:
        m = (l + r) // 2
        if check(s, n, m):
            l = m
        else:
            r = m
    print(l)
    


if __name__ == "__main__":
    submit()

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

int main() {
  long long N, A, B;
  cin >> N >> A >> B;
  long long A_ans[] = {A, A - B, -B, -A, B - A, B},
            B_ans[] = {B, A, A - B, -B, -A, B - A};
  cout << A_ans[((N + 1) / 2) % 6] << ' ' << B_ans[N / 2 % 6] << endl;
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<ll> VLL;
typedef vector<PLL> VP;
const static int INF = 1000000000;
const static int MOD = 1000000007;
const int dx[4]={1, 0, -1, 0};
const int dy[4]={0, 1, 0, -1};
#define rep(i,n) for (ll i=0; i<(ll)(n); i++)
#define repd(i,n) for (ll i=n-1; i>=0; i--)
#define rept(i,m,n) for(ll i=m; i<n; i++)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define PF push_front
#define PB push_back
#define SORT(V) sort((V).begin(), (V).end())
#define RVERSE(V) reverse((V).begin(), (V).end())
#define paired make_pair
#define PRINT(V) for(auto v : (V)) cout << v << " "
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
//charを整数に
int ctoi(char c) { if (c >= '0' && c <= '9') { return c - '0'; } return 0; }
// 累積和 for (int i = 0; i < N; ++i) s[i+1] = s[i] + a[i]; 
void cum_sum(int N,vector<double> a, vector<double> &s){ for(int i=0; i<N; i++){ s[i+1]=s[i]+a[i];}}
//ユークリッドの控除法
ll gcd(ll a,ll b){
    if(b == 0) return a;
    return gcd(b,a%b);
}
//最小公倍数
ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b; // Be careful not to overflow
}
//素数判定
bool is_prime(long long n) {
    if (n <= 1) return false;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) return false;
    }
    return true;
}
int getdigit(ll num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}
//空白文字も入力 getline(cin, S);
//桁数指定 setprecision

int main()
{
    int N;
    cin >> N;
    vector<vector<ll>> a(100010, vector<ll>(3));
    vector<vector<ll>> dp(100010, vector<ll>(3));
    rep(i,N){
        rep(j,3){
            cin >> a[i][j];
        }
    }

    rep(i,N){
        rep(j,3){
            rep(k,3){
                if(j==k) continue;
                chmax(dp[i+1][k],dp[i][j]+a[i][k]);
            }
        }
    }
    ll res=0;
    rep(j,3) chmax(res, dp[N][j]);
    cout << res << endl;
}


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

int main(){

    int x, n, y;
    int array[10000];

    for(x=0; x <= 10000; x++){
        cin >> array[x];
        if (array[x] == 0){
            n = x;
            x = 10000;
        }
    }

    for(x=0; x <= n-1; x++){
        cout << "Case " << x+1 << ": " << array[x] << endl;
    }

    return 0;

}


Measured memory_bytes: 3056
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define _USE_MATH_DEFINES
#include <math.h>

#define ABS(x) ( (x)>0 ? x : -(x) )
#define MIN(x,y) ( (x) < (y) ? (x) : (y) )
#define MAX(x,y) ( (x) > (y) ? (x) : (y) )
#define INF 1000000000

int main()
{
	int r, c;
	int table[101][101] = { 0 };

	scanf("%d%d", &r, &c);

	int i, j;

	for (i = 0; i < r; i++)
	{
		for (j = 0; j < c; j++)
		{
			scanf("%d", &table[i][j]);
		}
	}

	for (i = 0; i < r; i++)
	{
		for (j = 0; j < c; j++)
		{
			table[i][c] += table[i][j];
			table[r][j] += table[i][j];
			table[r][c] += table[i][j];
		}
	}

	for (i = 0; i <= r; i++)
	{
		for (j = 0; j <= c; j++)
		{
			if (j == c)
				printf("%d\n", table[i][j]);
			else
				printf("%d ", table[i][j]);

		}
	}

	return 0;
}


Measured memory_bytes: 2088
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Runtime.CompilerServices;
using static MyUtil;

class MyUtil
{
    public static int[] ReadIntArray()
    {
	return ReadLine().Split().Select(x => int.Parse(x)).ToArray();
    }
}

class Program
{
    public static void Main()
    {
	var tmp = ReadIntArray();
	int h = tmp[0], w = tmp[1], d = tmp[2];

	var pos = new Tuple<int,int>[h*w+1];
	for (int i = 1; i <= h; i++)
	{
	    var a = ReadIntArray();
	    for (int j = 1; j <= w; j++)
	    {
		pos[a[j-1]] = Tuple.Create(i, j);
	    }
	}

	var s = new int[h*w+1];

	for (int i = d; i <= h*w; i += d)
	{
	    for (int j = 1; j <= d; j++)
	    {
		int n1 = i+j, n0 = n1 - d;
		if (n1 > h*w) break;
		var t0 = pos[n0];
		var t1 = pos[n1];
		int dist = Math.Abs(t1.Item1 - t0.Item1) +
		    Math.Abs(t1.Item2 - t0.Item2);
		s[n1] = s[n0] + dist;
	    }
	}
	
	int q = int.Parse(ReadLine());
	for (int i = 0; i < q; i++)
	{
	    tmp = ReadIntArray();
	    int l = tmp[0], r = tmp[1];
	    WriteLine(s[r] - s[l]);
	}
    }
}



Measured memory_bytes: 22576
//#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2")  //Enable AVX
#include<bits/stdc++.h>
using namespace std;
 
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define ll long long
#define vi vector<int>
#define pi pair<int,int>
#define mp make_pair
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int mod=998244353;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int mul(int a,int b){
  return ((a)*1ll*(b))%mod;
}
 
void add(int &a,int b){
  a+=b;
  if(a>=mod)a-=mod;
}
 
int sub(int a,int b){
  a-=b;
  if(a<0){
	a+=mod;
  }
  return a;
}
 
int powz(int a,int b){
  int res=1;
  while(b){
	if(b&1){
	  res=mul(res,a);
	}
	b/=2;
	a=mul(a,a);
  }
  return res;
}
 
template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
  input>>x.F>>x.S;
  return input;
}
 
template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
	input>>i;
  return input;
}
 
template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
	output<<i<<' ';
  return output;
}
 
const int N=200002;

struct Node{
	Node *left,*right;
	int val;
	Node(){
	}
	Node(Node *_left,Node* _right,int _val):left(_left),right(_right),val(_val){
	}
	Node *insert(int tl,int tr,int ind,int vl);
	int query(int tl,int tr,int l,int r){
		if(l>r)return 0;
		if(l<=tl&&tr<=r){
			return val;
		}
		int md=tl+tr>>1;
		return this->left->query(tl,md,l,min(r,md))+this->right->query(md+1,tr,max(md+1,l),r);		
	}
};
 
Node abcd[N*50];
int sz=50*N;
Node *newNode(Node *left,Node *right,int val){
	abcd[--sz]=Node(left,right,val);
	return &abcd[sz];
}
	
Node *null=newNode(NULL,NULL,0);
 
Node *Node::insert(int tl,int tr,int ind,int vl){
	if(tl==tr&&ind==tl){
		return newNode(null,null,val+vl);
	}
	int md=tl+tr>>1;
	if(ind<=md&&ind>=tl){
		return newNode(this->left->insert(tl,md,ind,vl),this->right,val+vl);
	}
	else if(ind>md&&ind<=tr){
		return newNode(this->left,this->right->insert(md+1,tr,ind,vl),val+vl);
		
	}
	return this;
	
}
 
Node *rt[N];
 
void solve(){
  int n,m;
  cin>>n>>m;
  vector<pair<int,int>>a(n);
  cin>>a;
  sort(all(a));
  null->left=null->right=null;
  rt[0]=null;
  for(int i=0;i<n;i++){
	  rt[i+1]=rt[i]->insert(1,m,a[i].S,1);
  }
  for(int i=1;i<=m;i++){
	  int ans=0;
	  for(int j=i;j<=m;j+=i){
		  int lf=lower_bound(all(a),mp(j-i+1,-1))-a.begin();
		  int rg=lower_bound(all(a),mp(j,(int)1e9))-a.begin();
		  rg--;
		  ans+=rt[rg+1]->query(1,m,j,m);
		  ans-=rt[lf]->query(1,m,j,m);
	  }
	  cout<<ans<<'\n';
  }
}  
 
signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc=1;
  //cin>>tc;
  for(int _=0;_<tc;_++){
	// cout<<"Case #"<<_+1<<": ";
	solve();
	if(_!=tc-1){
	  cout<<'\n';
	}
  }
}


Measured memory_bytes: 132736
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n = readInt()
a = readInts()

suma = sum(a)
ans = float("inf")
t = 0
for i in range(n-1):
	t += a[i]
	ans = min(ans,abs(suma-t-t))

print(ans)

Measured memory_bytes: 31160
#include <stdio.h>
int main(){
	int n, m;
	int i;
	scanf("%d%d", &n, &m);
	int MAX=m;
	int a[2][n];
	for(i=0;i<n;i++)
	{
		scanf("%d%d", &a[0][i], &a[1][i]);
	}
	for(i=0;i<n;i++)
	{
		m=m+a[0][i]-a[1][i];
		if(m>MAX)
		{
			MAX=m;
		}
		if(m<0)
		{
			MAX=0;
			break;
		}
	}
	printf("%d\n", MAX);
	return 0;
}

Measured memory_bytes: 668
#include<stdio.h>

int A[2000];
int n;

int  solve(int i, int x){
    int res;

    if(x == 0) return 1;
    if(i >= n) return 0;
    res = solve(i + 1, x) || solve(i + 1, x - A[i]);
    
}

int main(void){
    int i, q, ans;
    int m[2000];

    scanf("%d", &n);
    for(i  = 0; i < n; i++){
        scanf("%d", &A[i]);
    }
    scanf("%d", &q);
    for(i = 0; i < q; i++){
        scanf("%d", &m[i]);
    }

    for(i = 0; i < q; i++){
        ans = solve(0, m[i]);
        if(ans == 1) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}


Measured memory_bytes: 2036