akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl '\n'
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); 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 INF 2147483647
#define LLINF 9223372036854775807LL
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define TOUPPER(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define TOLOWER(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define FILLZERO(s, n)                      \
    do {                                    \
        ostringstream os;                   \
        os << setw(n) << setfill('0') << s; \
        s = os.str();                       \
    } while (0);
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
#define INIT                               \
    std::cin.tie(nullptr);                 \
    std::ios_base::sync_with_stdio(false); \
    cout << std::fixed << std::setprecision(10);

template <typename T>
vector<T> make_vec(size_t a, T n) { return vector<T>(a, n); }
template <typename T, typename... Ts>
auto make_vec(size_t a, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...)); }
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

signed main() {
    INIT;
    cin >> A >> B >> C;
    if (A + B == C or A + C == B or A == B + C)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int a[6];
int main ()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		if(s[0] == 'M') a[0]++;
		if(s[0] == 'A') a[1]++;
		if(s[0] == 'R') a[2]++;
		if(s[0] == 'C') a[3]++;
		if(s[0] == 'H') a[4]++;
	}
	long long ans = 0;
	for(int i = 0; i < 5; i++)
	{
		for(int j = i + 1; j < 5; j++)
		{
			for(int k = j + 1; k < 5; k++)
			{
				ans += (1LL * a[i] * a[j] * a[k]);
			}
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int N;
    int sum;
    cin>>N;
    int ans=0;
    for(int i=0;i<25;i++){
        for(int j=0;j<25;j++){
            sum=4*i+7*j;
            if(sum==N) ans=1;
        }
    }
    if(ans==1)cout<<"Yes";
    else cout<<"No";
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#define INF 100000000
using namespace std;
int main(){
  int n;cin>>n;
  int u,k,v,c;
  int mp[101][101],d[101];
  for(int i=0;i<=100;i++){
    d[i]=INF;
    for(int j=0;j<=100;j++)mp[i][j]=INF;
  }
    while(u!=n-1){
    cin>>u>>k;
    for(int i=0;i<k;i++){
      cin>>v>>c;
      mp[u][v]=c;
    }
  }
    
    int mn,s,t[101]={},cn=n-1;
    d[0]=0,t[0]=1;
    while(cn){
      mn=INF;
      for(int i=0;i<n;i++){
	if(t[i]==0){
	  if(d[i]>d[s]+mp[s][i])d[i]=d[s]+mp[s][i];
	  if(mn>d[i])mn=d[i],k=i;
	}
      }
      if(mn!=INF)cn--,t[k]=1,s=k;
    }
    for(int i=0;i<n;i++)cout<<i<<" "<<d[i]<<endl;
    
  return 0;
}

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

int main(){
	int A,B;
	cin >> A >> B;
	int N=A+B;
	
	if(A<=B){
		cout << "Impossible" << endl;
		return 0;
	}
	
	int c=B+1;
	vector<int> v;
	
	for(int i=0;i<N;i++){
		if(v.empty()){
			v.push_back(i);
			if(c==1)break;
		}
		else{
			printf("? %d %d\n",i,v.back());
			char ans;
			cin >> ans;
			if(ans=='Y'){
				v.push_back(i);
				if(v.size()>=c)break;
			}
			else{
				v.pop_back();
				c--;
			}
		}
	}
	
	int honest=v[0];
	string res;
	for(int i=0;i<N;i++){
		printf("? %d %d\n",honest,i);
		char ans;
		cin >> ans;
		if(ans=='Y')res.push_back('1');
		else res.push_back('0');
	}
	cout << "! " << res << endl;
	return 0;
}

Measured memory_bytes: 848
while true
  
  x,y = gets.split.map(&:to_i)
  if x == 0 && y == 0 
    break
  end

  if x < y
    puts x.to_s + " " + y.to_s
  else
    puts y.to_s + " " + x.to_s
  end
 
end


Measured memory_bytes: 6832
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

#define ff          first
#define ss          second
#define ll          int64_t
#define ld          long double
#define nl          cout<<"\n"
#define dbg(x)      cerr<<#x<<" = "<<x<<"\n"
#define dbg2(x,y)   cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<"\n"
#define all(v)      v.begin(),v.end()
#define mset(a,v)   memset((a),(v),sizeof(a))
#define forn(i,a,b) for(int64_t i=int64_t(a);i<int64_t(b);++i)
#define forb(i,a,b) for(int64_t i=int64_t(a);i>=int64_t(b);--i)
#define fastio()    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> 

#define mod         1000000007
#define mod2        998244353 
#define inf         1000000000000007
#define pi          3.14159265358979323846

template<typename T,typename U> static inline void amin(T &x,U y)                   {if(y<x)x=y;}
template<typename T,typename U> static inline void amax(T &x,U y)                   {if(x<y)x=y;}  
template<class L,class R> ostream& operator<<(ostream& out,pair<L,R> &p)            {return out<<"("<<p.ff<<", "<<p.ss<<")";}
template<class T> ostream& operator<<(ostream& out,vector<T> &v)                    {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,deque<T> &v)                     {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,set<T> &s)                       {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class L,class R> ostream& operator<<(ostream& out,map<L,R> &m)             {out<<"{";for(auto it=m.begin();it!=m.end();++it){if(it!=m.begin())out<<", ";out<<*it;}return out<<"}";}

ll count_digits(ll n)   {ll dig=floor(log10(n)+1);return dig;}
ll mpow(ll x,ll y,ll p) {ll r=1;x=x%p;while(y>0){if(y&1)r=(r*x)%p;y=y>>1;x=(x*x)%p;}return r;} 
string dec_bin_32(ll n) {string s;for(ll i=31;i>=0;i--){ll k=n>>i;s+=(k&1)?'1':'0';}return s;} 
string dec_bin_64(ll n) {string s;for(ll i=63;i>=0;i--){ll k=n>>i;s+=(k&1)?'1':'0';}return s;} 
ll mod_inv(ll a,ll m)   {ll m0=m,y=0,x=1;if(m==1)return 0;while(a>1){ll q=a/m,t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=m0;return x;} 
/* const ll MAXN=10000007;ll spf[MAXN+5];vector<ll> prime; */
/* void sieve(ll n)        {forn(i,2,MAXN+1)spf[i]=i;for(ll i=2;i*i<=n;i++)if(spf[i]==i)for(ll j=i*i;j<=n;j+=i)if(spf[j]==j)spf[j]=i;forn(i,2,MAXN+1)if(spf[i]==i)prime.push_back(i);} */

//-------------------------------L_I_Erq34-------------------------------

int main()
{
	fastio();
	ll z,n,m,t,k,i,j,l,d,h,r;
	cin>>n;
	r=7;
	ll ans=-1;
	forn(i,1,n+1)
	{
		if(r%n==0)
		{
			ans=i;
			break;
		}
		r%=n;
		r=r*10+7;
	}
	cout<<ans<<"\n";
	cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
	return 0;
}


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

int main() {
  int N, K, sum;
  cin >> N >> K;
  sum = 0;

  // ここにプログラムを追記
  for (int i = 0; i < N; i++){
    int x;
    cin >> x;
    if (x <= K - x) {
      sum += 2 * x;
    }
    
    else {
      sum += 2 * (K - x);
    }

  }  

  cout << sum << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define PRN(n) printf("%d\n",n)
#define PRF(n) printf("%lf\n",n)
#define PRL(n) printf("%lld\n",n)
#define PRS(s) printf("%s\n",s)
#define PRC(c) printf("%c",c)
#define INI(n) scanf("%d",&n)
#define INL(n) scanf("%lld",&n)
#define INS(s) scanf("%s",s)
#define INF 10000000000
#define mod 1000000007
#define X 1000000
typedef long long int ll;
ll finv[X];
ll fac[X];
ll inv[X];
ll usort(const void *a, const void *b){return *(ll*)a-*(ll*)b;}
ll dsort(const void *a, const void *b){return *(ll*)b-*(ll*)a;}
ll ssort(const void *a, const void *b){return strcmp((char*)a,(char*)b);}
ll min(ll a,ll b){
  if(a>b)return b;
  return a;
}
ll max(ll a,ll b){
  if(a>b)return a;
  return b;
}
ll z(ll a){return max(a,-a);}
ll gcd(ll a,ll b){if(!b){return a;}else{return gcd(b,a%b);}}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll kt(ll a){
  ll sum=0;
  while(a){
    a/=10;
    sum++;
  }
  return sum;
}
ll ks(ll a){
  ll sum=0;
  while(a){
    sum+=a%10;
    a/=10;
  }
  return sum;
}
void nCrReady(){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  for (int i=2;i<X;i++){
    fac[i]=fac[i-1]*i%mod;
    inv[i]=mod-inv[mod%i]*(mod/i)%mod;
    finv[i]=finv[i-1]*inv[i]%mod;
  }
}
ll nCr(int n,int k){
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}

int main(void){
  int n,r;
  INI(r);
  INI(n);
  if(r<10)n+=1000-100*r;
  PRN(n);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;

namespace chrono = std::chrono;
using namespace std::literals;

[[gnu::constructor]]
void fast_iostream() {
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);
}

int main() {
    std::string s; cin >> s;
    int n = s.length();
    bool nine = true;
    for (int i = 1; i < n; ++i) {
        if (s[i] != '9') {
            nine = false;
        }
    }
    int ans = 0;
    if (nine) {
        ans += s[0] - '0';
    } else {
        ans += s[0] - '0' - 1;
    }
    ans += 9 * (n - 1);
    cout << ans << endl;
}


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

int main() {
	int A, B, C;
	bool found = false;
	cin >> A >> B >> C;
	for (int i = 1; i <= B; i++) {
		if ((A * i) % B == C) {
			found = true;
		}
	}
	if (found == true) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	rep(i,n){
		cin >> a[i];
	}
	int ans = (n - 1 + k - 1 - 1) / (k - 1);
	chmax(ans, 1);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll A,B,C,D,E,F,G,H,I,N;
ll ans=0;
ll cnt=0;
string S,T;
map<char,ll> m;
int v[20];
bool flag;
int main()
{
	cin>>N;
	for(ll i=0;i<N;i++) cin>>v[i];
	for(ll i=1;i<N-1;i++){
		if(v[i-1]>v[i]&&v[i]>v[i+1]) cnt++;
		else if(v[i-1]<v[i]&&v[i]<v[i+1]) cnt++;
	}
	cout<<cnt<<endl;
}

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

int main(){
  string str,tmp = "";
  cin >> str;
  int a,b,c=0;
  tmp = str[0];
  a = stoi(tmp);
  tmp = str.substr(1,2);
  b = stoi(tmp);
  if(b <= 11*a){
    cout << 111*a << endl;    
  }else{
    a++;
    cout << 111*a << endl;    
  }
}

Measured memory_bytes: 256
n,k,c=map(int,input().split())
s=input()
l=[0]*k
r=[0]*k
rest=0
work=0
for i in range(n):
  rest = max(rest-1,0)
  if s[i]=='o' and rest==0 and work < k:
    l[work]=i+1
    work+=1
    rest+=c+1
rest=0
work=0
for i in range(n-1,-1,-1):
  rest = max(rest-1,0)
  if s[i]=='o' and rest==0 and work < k:
    r[k-work-1]=i+1
    work+=1
    rest+=c+1
for i in range(k):
  if l[i]==r[i]:
    print(l[i])
  

Measured memory_bytes: 20544
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#include<map>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
int main(){
    vl a(3); vector<string>ans;
    int n; ll r;
    while(cin>>a[0]>>a[1]>>a[2],a[0]+a[1]+a[2]){
        cin>>n;
        rep(i,n){
            cin>>r;
            sort(all(a));
            ll temp=a[0]*a[0]+a[1]*a[1];
            if((r*2)*(r*2)>temp)ans.push_back("OK");
            else ans.push_back("NA");
        }
    }
    rep(i,ans.size())cout<<ans[i]<<endl;
}

Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll n,t,a,b,i,j,k;
    cin>>n;
    int sum=0;
    sum+=n/500*1000;
    n%=500;
    sum+=n/5*5;
    cout<<sum;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int a[105][105];
int c[10001];
int main()
{
	int H,W,N,i,j,x,y,k;
	cin>>H>>W>>N;
	int* b=new int[N];
	for(i=0;i<N;i++)
	{
		cin>>b[i];
	}
	k=1;
	for(j=0;j<H*W;)
	{for(i=b[k-1];i>0;i--)
	{
	c[j++]=k;
	
	}
	k++;}
	
	for(i=0;i<H;i++)
	for(j=0;j<W;j++)
	a[i][j]=0;
	int tot=1;
	a[x=0][y=W-1]=c[0];
	while(tot<H*W)
	{
		while(x+1<H && !a[x+1][y]){a[++x][y]=c[tot++];}
		while(y-1>=0 && !a[x][y-1]){a[x][--y]=c[tot++];}
		while(x-1>=0 && !a[x-1][y]){a[--x][y]=c[tot++];}
		while(y+1<W && !a[x][y+1]){a[x][++y]=c[tot++];}
		
	}
	for(x=0;x<H;x++)
	{
	for(y=0;y<W;y++)
	cout<<a[x][y]<<" ";
	cout<<"\n";}
	delete [] b;
	return 0;
} 

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int n,x;
int L[100];

void solve(){
    int ans = 1;
    int pos = 0;
    for(int i=1; i<n+1; i++){
        pos += L[i-1];
        if(pos <= x) ans++;
    }
    cout << ans << endl;
}



int main(){
    cin >> n >> x;
    for(int i=0; i<n; i++){
        cin >> L[i];
    }
    solve();
    return 0;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 0; i < 7; ++i) {
        int a, b;
        cin >> a >> b;
        cout << a - b << '\n';
    }
    return 0;
}


Measured memory_bytes: 3180
#include <cstdio>
#include <cstring>
using namespace std;

char s[200002];

int main(){
  scanf("%s", s + 1); int L = strlen(s + 1);

  int bc = 0; bool c = false;
  long long ans = 0;

  for(int i = L; i >= 1; i--){
    if(s[i] == 'A'){
      if(!c) ans += bc;
      else{ bc = 0; c = false; }
    }
    else if(s[i] == 'B'){
      if(c){ bc++; c = false; }
      else{ bc = 0; c = false; }
    }
    else if(s[i] == 'C'){
      if(!c){ c = true; }
      else{ bc = 0; c = true; }
    }
  }

  printf("%lld\n", ans);
  return 0;
}

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

const int64_t mod = 1e9+7;

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

	int N;
	cin >> N;
	int64_t running = 0, ans = 0;
	for (int i = 0; i < N; ++i) {
		int64_t e;
		cin >> e;
		ans += (e*running);
		ans %= mod;
		running = (running+e)%mod;
	}
	// vector<int64_t> A(N), pre(N), suf(N);
	// for (int64_t& e : A) cin >> e;
	// pre[0] = A[0];
	// for (int i = 1; i < N; ++i) pre[i] = (pre[i-1]+A[i])%mod;
	// int64_t ans = 0;
	// for (int i = 1; i < N; ++i) {
	// 	cout << i << " " << pre[i-1] << endl;
	// 	ans += (A[i]*pre[i-1])%mod;
	// }
	cout << ans << endl;
	// suf[N-1] = A[N-1];
	// for (int i = N-2; i >= 0; --i) suf[i] = (suf[i+1]+A[i])%mod;
}

Measured memory_bytes: 3652
import math
A,B,H,M = map(int,input().split())


H = H/12 * 60
H = H + (1/12 * M)
shita = math.radians(abs(H-M)*6)
if shita > math.pi:
    shita = 2*math.pi - shita
cos_shita = math.cos(shita)
c_zizyou = A**2 + B**2 - 2 * A * B * cos_shita
print(math.sqrt(c_zizyou))


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

int mod = 1'000'000'007;

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> s(n);
    for (int i = 0; i < n; i++) cin >> s[i];
    vector<int> t(m);
    for (int i = 0; i < m; i++) cin >> t[i];
    vector<vector<long long>> ans(n+1, vector<long long>(m+1, 1));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if (s[i] == t[j]){
                ans[i+1][j+1] = ans[i+1][j] + ans[i][j+1];
            }
            else {
                ans[i+1][j+1] = ans[i+1][j] + ans[i][j+1] + mod - ans[i][j];
            }
            ans[i+1][j+1] %= mod;
        }
    }
    cout << ans[n][m] % mod << endl;
}


Measured memory_bytes: 31616
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define ll long long
#define INF 1000000000000000000
#define INT_MAX 2147483647

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cmath>
#include <ios>
#include <iomanip>

using namespace std;

int main(){
    int N;
    cin >> N;
    int h[N];
    int dp[N];
    REP(i,N){
        cin >> h[i];
        dp[i] = INT_MAX;
    }

    dp[0]=0;
    REP(i,N){
        if(i+1<N && dp[i] + abs(h[i] - h[i+1]) < dp[i+1])dp[i+1] = dp[i] + abs(h[i] - h[i+1]);
        if(i+2<N && dp[i] + abs(h[i] - h[i+2]) < dp[i+2])dp[i+2] = dp[i] + abs(h[i] - h[i+2]);
    }

    cout << dp[N-1] << endl;
    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1LL << 50;
static const int NIL = -1;
static const int MOD = 1000000007;
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define SORT(v) sort(v.begin(), v.end());
#define pb push_back
#define mp make_pair
#define np next_permutation
#define pq priority_queue
 
int gcd(int a, int b) { int c; while (b != 0) { c = a%b; a = b; b = c; }return a; }
int lcm(int a, int b) { int c = gcd(a, b); a /= c; return a*b; }
int nCr(int a, int b) { int i, r = 1; for (i = 1; i <= b; i++) { r *= (a + 1 - i); r /= i; }return r; }
int pow(int a, int b) { int i, r = 1; for (i = 1; i <= b; i++) { r *= a; }return r; }
long long llpow(long long a, long long b) { long long i, r = 1; for (i = 1; i <= b; i++) { r *= a; }return r; }
long long llgcd(long long a, long long b) { long long c; while (b != 0) { c = a%b; a = b; b = c; }return a; }
long long lllcm(long long a, long long b) { long long c = llgcd(a, b); a /= c; return a*b; }
long long llnCr(long long a, long long b) { long long i, r = 1; for (i = 1; i <= b; i++) { r *= (a + 1 - i); r /= i; }return r; }
 
//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};
 
struct edge{
    int from, to; ll cost;
};

//  通ってください

int main(){
    int n;
    cin >> n;
    vector<int> a;
    REP(i, n){
        int tmp;
        cin >> tmp;
        a.pb(tmp);
    }
    SORT(a);
    int cnt[9];
    REP(i, 9) cnt[i] = 0;
    REP(i, n){
        for(int j = 400; j < 5600; j += 400){
            if(a[i] < j){
                if(j / 400 - 1 > 8){
                    cnt[8]++;
                }else{
                    cnt[j / 400 - 1]++;
                }
                break;
            }
        }
    }
    int minan = 0;
    REP(i, 8){
        if(cnt[i]) minan++;
    }
    if(minan == 0){
        minan = 1;
        cnt[8]--;
    }
    cout << minan << " " << minan + cnt[8] << endl;
}

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

#define MAX 100

int check(char s[]){
    int len=strlen(s);
    char ss[len/2+1];
    strncpy(ss,s,len/2);
    int i;
    
    for(i=0;i<len/2;i++){
        //ssは前方から、sは後方から比較するので中央は気にしなくてよい
        if(ss[i]!=s[len-1-i])return 0;
    }
    
    return 1;
}

int main(void){
    char s[MAX+1];
    int cnt=0;
    
    while(scanf("%s\n",s)==1){
        cnt+=check(s);
    }
    
    printf("%d\n",cnt);
    
    return 0;
}



Measured memory_bytes: 2032
#include <malloc.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//ABC112C
int main(void) {
  int n, k, m, i, tmp, toph, mxh=-1, mxi=-1;
  scanf("%d", &n);
  int x[n], y[n], h[n];
  for(i=0; i<n; i++){
    scanf(" %d %d %d", &x[i], &y[i], &h[i]);
    if(mxh<h[i]) mxh=h[i], mxi=i;
  }

  for(i=0; i<=100; i++){
    for(k=0; k<=100; k++){
      toph=h[mxi]+abs(x[mxi]-i)+abs(y[mxi]-k);

      for(m=0; m<n; m++){
        tmp=h[m]+abs(x[m]-i)+abs(y[m]-k);
        if(h[m]==0&&(abs(x[m]-i)+abs(y[m]-k)>=toph)){
          //printf("(%d,%d) %d\n", i, k, toph);
          if(m==n-1){
            printf("%d %d %d", i, k, toph);
            return 0;
          }else continue;
        }

        if(toph!=tmp) break;
        if(m==n-1){
          printf("%d %d %d", i, k, toph);
          return 0;
        }
      }
    }
  }
  return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

int N;
int L[200];

int main(){
	scanf("%d" , &N);
	for(int i = 0 ; i < 2 * N ; ++i) scanf("%d" , L + i);
	sort(L , L + 2 * N);
	int ans = 0;
	for(int i = 0 ; i < 2 * N ; i += 2) ans += L[i];
	printf("%d\n" , ans);
}


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

int main(){
    int N,M;
    while(cin>>N>>M,N){
        vector<int> C(M);
        for(int i=0;i<M;i++){
            cin>>C[i];
        }
        int error[2][256];
        fill(error[0],error[2],1000000000);
        error[0][128]=0;
        for(int i=1;i<=N;i++){
            int x;
            cin>>x;
            for(int j=0;j<256;j++) error[i&1][j]=1000000000;
            for(int j=0;j<256;j++){
                if(error[i&1^1][j]!=1000000000){
                    for(int k=0;k<M;k++){
                        int jk=j+C[k];
                        jk=max(jk,0);
                        jk=min(jk,255);
                        error[i&1][jk]=min(error[i&1][jk],error[i&1^1][j]+(x-jk)*(x-jk));
                    }
                }
            }
        }
        int ans = 1000000000;
        for(int j=0;j<256;j++){
            ans=min(ans,error[N&1][j]);
        }
        cout<<ans<<endl;
    }

    return 0;
}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;

int main() {
    long double pi = acos(-1);
    long double a, b, h, m;
    cin >> a >> b >> h >> m;

    // 長針について
    // alp_1 = m * 12 *pi/360
    // 短針について
    // h * 60 * pi / 360 + m * pi / 360

    long double diff;
    if (60 * h + m > m * 12) diff = 60 * h + m - 12 * m;
    else diff = 12 * m - (60 * h + m);

    long double c = a * a + b * b - (long double) 2 * b * a * cos(diff *  pi / 360);

    printf("%-.15Lf\n", sqrt(c));
    return 0;
}

Measured memory_bytes: 4148
N=int(input())
W=list(map(int,input().split()))
Wsum=0

for w in W:
  Wsum+=w
ansum=0
ans=10**11
for i in range(N):
  ansum+=W[i]
  Wsum-=W[i]
  if abs(ansum-Wsum)<ans:
    ans=abs(ansum-Wsum)
print(ans)

Measured memory_bytes: 3064
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    N = makeMultiInteger(input_string[0])
    S = makeStringMatrix(input_string[1:])
    for _i, s in enumerate(S):
        s.append(_i+1)
    S = sorted(S, key=lambda x: x[0])
    a = []
    i = 0
    for _i, s in enumerate(S):
        #print(s)
        if a != []:
            if s[0] == a[i-1][0]:
                a.append(s)
            else:
                if len(a) > 1:
                    a = sorted(a, key=lambda x: int(x[1]), reverse=True)
                    #print(a)
                    for _a in a:
                        print(_a[2])
                else:
                    for _a in a:
                        print(_a[2])
                i = 0
                a = []
                a.append(s)
        else:
            a.append(s)
    if a != []:
        if len(a) > 1:
            a = sorted(a, key=lambda x: int(x[1]), reverse=True)
            for _a in a:
                print(_a[2])
        else:
            for _a in a:
                print(_a[2])


def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    #print(answer)


if __name__ == '__main__':
    main()


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

using namespace std;
#define ll long long int

int main(){
    string s , t;
    cin >> s >> t;
    int n = s.length();
    int m = t.length();
    int dp[n + 1][m + 1];

    memset(dp , 0 , sizeof(dp));
    // for(int i =0 ; i<=m; i++)
    // {
    //     dp[0][i] = 0;
    // }
    // for(int i =0 ; i<=n; i++)
    // {
    //     dp[i][0] = 0;
    // }
    int l = min(n , m);
    int index[l + 1];
    memset(index , -1 , sizeof(index));
    for(int i = 1 ; i <=n ; i ++)
    {
        for(int j = 1; j <= m ; j ++)
        {
            dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1]);
            if(s[i - 1] == t[j - 1])
            {
                dp[i][j] = max(dp[i][j] , 1 + dp[i - 1][j - 1]);
                if(index[dp[i][j]] != -1)
                {
                    index[dp[i][j]] = min(index[dp[i][j]] , j - 1);
                }
                else
                index[dp[i][j]] = j - 1;
            }
        }
    }
    string ans = "";
    int i = n;
    int j = m;
    while( i>0 && j >0)
    {
        if(s[i - 1] == t[ j - 1])
        {
            ans += s[i - 1];
            i--;
            j--;
        }
        else
        {
            if(dp[i - 1][j] >= dp[i][j - 1])
            {
                i -= 1;
            }
            else
            j -= 1;
        }
    }
    reverse(ans.begin() , ans.end());
    cout << ans << endl;
}

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

int main() {
	priority_queue<int, vector<int>, greater<int> > pqn;
	priority_queue<int, vector<int>, greater<int> > pqt;
	int N, M;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int t;
		cin >> t;
		pqn.push(t);
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		int t;
		cin >> t;
		pqt.push(t);
	}

	int t = pqt.top();
	while (pqn.size()) {
		int d = pqn.top();
		pqn.pop();
		if (t == d) {
			pqt.pop();
			if (!pqt.size())
				break;
			t = pqt.top();
		} 
	}
	if (pqt.size()) {
		cout << "NO\n";
	} else {
		cout << "YES\n";
	}
}


Measured memory_bytes: 2548
import java.util.*;
import static java.lang.System.*;

public class Main {

	class P {
		int x, y;
		P(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	Scanner sc = new Scanner(in);
	
	void run() {
		int n;
		P[] c = new P[200];
		c[0] = new P(0, 0);
		while (true) {
			n = sc.nextInt();
			if (n == 0) break;
			if (n == 1) {
				out.println("1 1");
			} else {
				int xmax, xmin, ymax, ymin;
				xmax = xmin = ymax = ymin = 0;
				for (int i = 1; i < n; i++) {
					int x = sc.nextInt(), y = sc.nextInt();
					switch(y) {
					case 0:
						c[i] = new P(c[x].x-1, c[x].y);
						xmin = Math.min(xmin, c[x].x-1);
						break;
					case 1:
						c[i] = new P(c[x].x, c[x].y-1); 
						ymin = Math.min(ymin, c[x].y-1);
						break;
					case 2:
						c[i] = new P(c[x].x+1, c[x].y); 
						xmax = Math.max(xmax, c[x].x+1);
						break;
					case 3:
						c[i] = new P(c[x].x, c[x].y+1); 
						ymax = Math.max(ymax, c[x].y+1);
						break;
					}
				}
				out.printf("%d %d\n", xmax-xmin+1, ymax-ymin+1);
			}
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

}

Measured memory_bytes: 34368
n = int(input())
L = []
for i in range(n):
    L.append(int(input()))

L_sorted = sorted(L,reverse=True)
for i in L:
    if i == L_sorted[0]:
        print(L_sorted[1])
    else:
        print(L_sorted[0])

# こいつはn **16 = 10**8**16
#3
#[1,4,3]
#[4,3,1]

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

int main() {
  int N, M, X;
  scanf("%d%d%d", &N, &M, &X);

  int cost_to_front = 0;
  int cost_to_back = 0;
  for (int i = 0; i < M; i++) {
    int A = 0;
    scanf("%d", &A);
    if (A < X) {
      cost_to_front++;
    } else {
      cost_to_back++;
    }
  }

  printf("%d", min(cost_to_front, cost_to_back));
  return 0;
}


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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

//! i番目の左にあるA/?の数
ll LA[100005];
ll L[100005];
//! i番目の右にあるC/?の数
ll RC[100005];
ll R[100005];

//! 3-Q mod;
ll T[100005];

int main()
{
    string S;
    cin >> S;
    LA[0] = 0;
    L[0] = 0;
    REP(i, S.length())
    {
        LA[i + 1] = LA[i];
        L[i + 1] = L[i];
        if (S[i] == 'A')
            LA[i + 1]++;
        if (S[i] == '?')
            L[i + 1]++;
    }
    RC[S.length() - 1] = 0;
    R[S.length() - 1] = 0;
    for (int i = S.length() - 1; i >= 1; --i)
    {
        RC[i - 1] = RC[i];
        R[i - 1] = R[i];
        if (S[i] == 'C')
            RC[i - 1]++;
        if (S[i] == '?')
            R[i - 1]++;
    }

    T[0] = 1;
    REP(i, S.length())
    {
        T[i + 1] = (T[i] * 3) % MOD;
    }
    ll ans = 0;
    FOR(i, S.length() - 1, 1)
    {
        if (S[i] == 'B' || S[i] == '?')
        {
            //! ?以外を使う
            ll s0 = ((LA[i]*RC[i]%MOD)*T[L[i]+R[i]])%MOD;
            //! 左側の?を使う
            ll s1 =(L[i]*RC[i]%MOD)*T[std::max(0LL,L[i]+R[i]-1)]%MOD;
            //! 右側の?を使う
            ll s2 =(LA[i]*R[i]%MOD)*T[std::max(0LL,L[i]+R[i]-1)]%MOD;
            //! 左右?を使う
            ll s3 =(L[i]*R[i]%MOD)*T[std::max(0LL,L[i]+R[i]-2)]%MOD;

            ans = (ans + s0+s1+s2+s3) % MOD;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4352
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define M 200020
using namespace std;
int read(){
	int nm=0,fh=1; char cw=getchar();
	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
	return nm*fh;
}
int n,p[M],now,at,last=1,rem;
char ch[M];
void e(int x,int y){rem--,printf("%d %d\n",x,y);}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%s",ch+1),n=strlen(ch+1),rem=n-1;
	for(int i=1;i<=n;i++) p[i]=ch[i]-'0';
	if(p[n]==1||p[1]==0){puts("-1");return 0;}
	for(int i=1;i<=(n>>1);i++) if(p[i]^p[n-i]){puts("-1");return 0;}
	now=at=1;
	for(int i=1;i<n;i++){
		now++,e(now,at);
		if(p[i]) at=now;
	}
	return 0;
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
#define M 2005
using namespace std;
int a[M][M]={0};
int h[M][M]={0},w[M][M]={0},sum[M][M]={0};
char c[M]={0};
int main(){
	int n,m,q;
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++){
		scanf("%s",c+1);
		for(int j=1;j<=m;j++){
			a[i][j]=c[j]-'0';
		}
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		h[i][j]=h[i-1][j]+h[i][j-1]-h[i-1][j-1]+(a[i][j]==1&&a[i-1][j]==1);
		w[i][j]=w[i-1][j]+w[i][j-1]-w[i-1][j-1]+(a[i][j]==1&&a[i][j-1]==1);
		sum[i][j]=(a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]);
	}
	while(q--){
		int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		int Sum=h[x2][y2]+w[x2][y2];
		int r=w[x1-1][y2]+h[x1][y2];
		int l=h[x2][y1-1]+w[x2][y1];
		int lr=h[x1][y1-1]+w[x1-1][y1];
		int edgsum=Sum-l-r+lr;
		int nodsum=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
		printf("%d\n",nodsum-edgsum);
	}
}

Measured memory_bytes: 64640
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#include <numeric>
using namespace std;
 int main(){
 int n,a,b,f=0; 
 cin>>n;
while(n>0){
a=n%10;
if(a==7)f=1;
n/=10;
}
if(f==1)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}

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

const int mod = 1e9 + 7;

int exp(int x, int n) {
    int ret = 1;
    while(n) {
        if(n & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod;
        n >>= 1;
    }
    return ret;
}
int inv(int x) {
    return exp(x, mod - 2);
}
int fact[222], invf[222];
int comb(int n, int k) {
    return 1LL * fact[n] * invf[k] % mod * invf[n - k] % mod;
}
int H(int n, int k) {
    return comb(n + k - 1, k);
}

int N, M, K;
vector<int> adj[55], U, V;
int tin[55], bck[55], id[111], timer, bcnt;
stack<int> stk;

void dfs(int u, int fe) {
    tin[u] = timer++;
    bck[u] = tin[u];

    for(int i = 0; i < adj[u].size(); i++) {
        int e = adj[u][i];
        int v = U[e] + V[e] - u;
        if(e == fe) continue;
        if(tin[v] == -1) {
            stk.push(e);
            dfs(v, e);
            bck[u] = min(bck[u], bck[v]);
            if(bck[v] >= tin[u]) {
                while(1) {
                    int t = stk.top(); stk.pop();
                    id[t] = bcnt;
                    if(t == e) break;
                }
                bcnt++;
            }
        }
        else if(tin[v] < tin[u]) {
            stk.push(e);
            bck[u] = min(bck[u], tin[v]);
        }
    }
}

int prec[55];

int main() {
    fact[0] = 1;
    for(int i = 1; i < 222; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
    }
    for(int i = 0; i < 222; i++) {
        invf[i] = inv(fact[i]);
    }

    scanf("%d %d %d", &N, &M, &K);

    for(int i = 0; i < M; i++) {
        int u, v; scanf("%d %d", &u, &v);
        u--; v--;

        adj[u].push_back(i);
        adj[v].push_back(i);
        U.push_back(u);
        V.push_back(v);
    }

    memset(tin, -1, sizeof(tin));
    for(int i = 0; i < N; i++) if(tin[i] == -1) {
        dfs(i, -1);
    }

    for(int i = 1; i <= N; i++) {
        vector<int> cnt(i + 1, 0);

        for(int j = 1; j <= i; j++) {
            if(i % j) continue;

            cnt[j] += exp(K, j);
            cnt[j] %= mod;
            prec[i] += 1LL * cnt[j] * inv(j) % mod;
            prec[i] %= mod;
            for(int k = 2 * j; k <= i; k += j) {
                cnt[k] += mod - cnt[j];
                cnt[k] %= mod;
            }
        }
    }

    int ans = 1;
    for(int i = 0; i < bcnt; i++) {
        vector<int> chk(N, 0);
        int vcnt = 0;
        int ecnt = 0;
        for(int j = 0; j < M; j++) {
            if(id[j] == i) {
                if(!chk[ U[j] ]) {
                    chk[ U[j] ] = 1;
                    vcnt++;
                }
                if(!chk[ V[j] ]) {
                    chk[ V[j] ] = 1;
                    vcnt++;
                }
                ecnt++;
            }
        }
        if(vcnt == ecnt) {
            //cout << vcnt << endl;
            ans = 1LL * ans * prec[vcnt] % mod;
        }
        else if(ecnt == 1) ans = 1LL * ans * K % mod;
        else ans = 1LL * ans * H(K, ecnt) % mod;
    }
    printf("%d", ans);
}


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

const int MAXN = 100010;

int n, a[MAXN], ans;
long long sum;

int main()
{
#ifdef wxh010910
	freopen( "data.in", "r", stdin );
#endif
	scanf( "%d", &n );
	for( int i = 1 ; i <= n ; i++ ) scanf( "%d", &a[ i ] );
	sort( a + 1, a + n + 1 );
	for( int i = 1 ; i < n ; i++ ) sum += a[ i ], ans = ( sum * 2 < a[ i + 1 ] ) ? i : ans;
	return printf( "%d\n", n - ans ), 0;
}


Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main() {
	string s, t;
	cin >> s >> t;
	
	int n = s.size(), m = t.size();
	
	int len[n + 1][m + 1];
	pair<int, int> from[n + 1][m + 1];
	
	for (int i = 0;i <= n;i++) { len[i][0] = 0; from[i][0] = {0, 0}; }   
        for (int i = 0;i <= m;i++) { len[0][i] = 0; from[0][i] = {0, 0}; }

	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			//cout << "s[" << i - 1 << "]: " << s[i - 1] << "  t[" << j - 1 << "]: " << t[j - 1] << endl; 
			if (s[i - 1] == t[j - 1]) {
				len[i][j] = len[i - 1][j - 1] + 1;
				from[i][j] = {i - 1, j - 1};				
			} else {	
				if (len[i][j - 1] > len[i - 1][j]) {
					len[i][j] = len[i][j - 1]; from[i][j] = {i, j - 1};
				} else {
					len[i][j] = len[i - 1][j]; from[i][j] = {i - 1, j};
				}				
			}
		}
	}

	/*for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) cout << len[i][j] << " ";
		cout << endl;
	}
	cout << endl;
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) cout << from[i][j].first << "-" << from[i][j].second << " ";
		cout << endl;
	}
	cout << endl;*/

	int I = n, J = m;

	string ans = "";

	while (I != 0 || J != 0) {
		//cout << I << " " << J << endl;
		pair<int, int> take = {I - 1, J - 1};
		if (from[I][J] == take) { 
			I--; J--; ans += s[I]; 
		} else {
			int tmp_i = from[I][J].first, tmp_j = from[I][J].second;
			I = tmp_i; J = tmp_j;
		}
	}	

	for (int i = ans.size() - 1;i >= 0;i--) cout << ans[i];
}                       

Measured memory_bytes: 105856
#include <bits/stdc++.h>
using namespace std;
 
long long a,b,l,n;
string s;
 
int main(){
	
  cin >> n;
  
  int a[n];
  
  for (int i=0; i<n; i++){
    	cin >> a[i];
  	}
  
  int l=0,k=0;

  for (int i=0; i<n; i++){
  	  if (a[i]!=l+1){
        l--;
        k++;
      }

      l++;
  }
  
  if (k==n)
    cout << -1 << endl;
  else
    cout << k << endl;
    
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iterator>
#pragma warning(disable:4996)
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
#define MOD 1000000007
using namespace std;



int main(int argc, char* argv[])
{
    long a, b, q;
    scanf("%ld%ld%ld", &a, &b, &q);

    vector<ll> s(a);
    vector<ll> t(b);
    vector<ll> x(q);

    long i;
    for(i=0; i<a; i++) {
        scanf("%lld", &s[i]);
    }
    for(i=0; i<b; i++) {
        scanf("%lld", &t[i]);
    }
    for(i=0; i<q; i++) {
        scanf("%lld", &x[i]);
    }
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());

    long  j, k;
    for(i=0; i<q; i++) {
        // s->t
        ll min = LINF;
        {
            long tmp = lower_bound( s.begin(), s.end(), x[i] ) - s.begin();
            ll aa[2] = { tmp>0? s[tmp-1]: s[0], tmp<a? s[tmp]: s[a-1] };

            for(j=0; j<2; j++) {
                long tmp2 = lower_bound( t.begin(), t.end(), aa[j] ) - t.begin();
                ll bb[2] = { tmp2>0? t[tmp2-1]: t[0], tmp2<b? t[tmp2]: t[b-1] };

                for(k=0; k<2; k++) {
                    ll val = abs(aa[j] - x[i]) + abs(aa[j] - bb[k]);
                    min = MIN(min, val);
                }
            }
        }

        // t->s
        {
            long tmp2 = lower_bound( t.begin(), t.end(), x[i] ) - t.begin();
            ll bb[2] = { tmp2>0? t[tmp2-1]: t[0], tmp2<b? t[tmp2]: t[b-1] };

            for(j=0; j<2; j++) {
                long tmp = lower_bound( s.begin(), s.end(), bb[j] ) - s.begin();
                ll aa[2] = { tmp>0? s[tmp-1]: s[0], tmp<a? s[tmp]: s[a-1] };

                for(k=0; k<2; k++) {
                    ll val = abs(bb[j] - x[i]) + abs(bb[j] - aa[k]);
                    min = MIN(min, val);
                }
            }
        }
        printf("%lld\n", min);
    }

    return 0;
}



Measured memory_bytes: 3712
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll INF = 1LL << 60;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
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;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
//printf("%.10f\n", N);
/*
ll fibo(ll n){
    if(memo[n] != 0)return memo[n];
    if(n <= 1)return n;
    else return memo[n] = fibo(n - 1)+ fibo(n - 2);
}*/
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/
int main(){
    string S,T,U;
    cin >> S >> T >> U;
    char now;
    now = 'a';
    ll s = S.size(),t = T.size(),u = U.size();
    ll cnts = 0,cntt = 0,cntu = 0;
    char ans = 'A';
    while(true){//s-1=cnts -> break
        if(now == 'a'){
            if(cnts == s)break;
            else {
                now = S[cnts];
                cnts++;
            }
        }
        else if(now == 'b'){
            if(cntt == t){
                ans ='B';
                break;
            }
            else {
                now = T[cntt];
                cntt++;
            }
        }
        else{
            if(cntu == u){
                ans ='C';
                break;
            }
            else {
                now = U[cntu];
                cntu++;
        }
    }
//    cout << cnts <<" " << cntt << " " << cntu << endl;
}
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;

int main(){
	typedef pair<int,int> pii;
	priority_queue<pii> pq;
	int n, r, l, d, t, x, u = 0;
	scanf("%d%d%d", &n, &r, &l);
	vector<int> s(n + 1), c(n + 1);
	for(int i = 1; i <= n; ++i){
		pq.push(pii(0, ~i));
	}
	for(int i = 0; ; ++i){
		if(i == r){
			t = l;
		}
		else{
			scanf("%d%d%d", &d, &t, &x);
		}
		while(1){
			if(s[~pq.top().second] == pq.top().first){
				c[~pq.top().second] += t - u;
				break;
			}
			pq.pop();
		}
		if(i == r){
			break;
		}
		s[d] += x;
		pq.push(pii(s[d], ~d));
		u = t;
	}
	int ans = max_element(c.begin(), c.end()) - c.begin();
	printf("%d\n", ans);
}

Measured memory_bytes: 11612
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

a = I()
print(a + a**2 + a**3)


Measured memory_bytes: 65348
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(int i=(a),i##Len_=(b);i<i##Len_;i++)
const char* LF = "\n";
namespace{struct _{_(){
    cin.tie(0);
    ios::sync_with_stdio(false);
}}a;}
signed main() {
    int n;
    cin >> n;
    vector<ll> xi(n), yi(n), hi(n);
    ll x_,y_,h_;
    REP(i, n) {
        cin >> xi[i] >> yi[i] >> hi[i];
        if (hi[i] >= 1) {
            x_ = xi[i]; y_ = yi[i]; h_ = hi[i];
        }
    }
    REP(iy, 100+1) {
        REP(ix, 100+1) {
            bool same = true;
            ll d = abs(ix - x_) + abs(iy - y_) + h_;
            for (int j=0; j<n; j++) {
                ll d_ = d - abs(ix - xi[j]) - abs(iy - yi[j]);
                d_ = max(d_, 0LL);
                if (hi[j] != d_) {
                    same = false;
                    break;
                }
            }
            if (same) {
                cout << ix << " " << iy << " " << d << LF;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream> 
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
 
using namespace std;
using ll = long long;
 
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };


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

	cin >> a >> b >> c >> d;

	if(a + b > c + d){
		cout << "Left" << endl;
	}
	else if(a + b < c + d){
		cout << "Right" << endl;
	}
	else{
		cout << "Balanced" << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int l,r,p[2030];
int main(){
    cin>>l>>r;
    if(r-l>=2018){
        cout<<0<<endl;
        return 0;
    }
    else{
        for(int i=l;i<=r;i++)p[i-l]=i%2019;
        sort(p,p+(r-l+1));
        int ans=114514;
        for(int i=0;i<r-l+1;i++){
            for(int j=0;j<r-l+1;j++){
                int f=(p[i]*p[j])%2019;
                if(i==j)continue;
                else if(f<ans)ans=f;
            }
        }
        cout<<ans<<endl;
    }

}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#define ll long long
#define lowbit(x) x&-x
using namespace std;
int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a<b?b:a;}
int ab(int x){return x>0?x:-x;}
//int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
//int MO(int x){return x>=MOD?x-MOD:x;}
//void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f,maxn=100100;

int n,a[maxn],b[maxn],c[maxn];
ll d[maxn],sum[maxn];

int main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();
    for(int i=1;i<=n;i++)c[i]=read();
    sort(a+1,a+n+1);sort(b+1,b+n+1);sort(c+1,c+n+1);
    int now=1;
    for(int i=1;i<=n;i++){
    	while(now<=n&&b[i]>=c[now])now++;
    	d[i]=n-now+1;
    }
    sum[n+1]=0;for(int i=n;i>=1;i--)sum[i]=sum[i+1]+d[i];
    now=1;
    ll ans=0;
    for(int i=1;i<=n;i++){
    	while(now<=n&&a[i]>=b[now])now++;
    	ans+=sum[now];
    }
    printf("%lld",ans);
    return 0;
}

Measured memory_bytes: 2944