akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <limits>
using namespace std;
// 素因数分解
typedef pair<long long, long long> P;
vector<P> prime_factorize(long long n)
{
vector<P> res;
for (long long p = 2; p * p <= n; ++p)
{
if (n % p != 0)
continue;
int num = 0;
while (n % p == 0)
{
++num;
n /= p;
}
res.push_back(make_pair(p, num));
}
if (n != 1)
res.push_back(make_pair(n, 1));
return res;
}
// 因数分解
long long gcd(long long x, long long y)
{
  if (y == 0)
  {
    return x;
  }
  else
  {
    return gcd(y, x % y);
  }
}
//素数判定
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;
}
const int MOD = 1000000007;
typedef long long int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for (int i = 0; i < (n); i++)
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; }

bool judge(int N,int bit,vector<vector<pair<int, int> > > v){
    for (int i = 0; i < N;i++){
        if(!(bit&(1<<i))){
            continue;
        }
        for(pair<int,int> xy:v[i]){
            int x = xy.first;
            int y = xy.second;
            if(y==1&&!(bit&1<<x)){
                return false;
            }
            if(y==0&&(bit&1<<x)){
                return false;
            }
        }
    }
    return true;
}

int main()
{
    int N;
    cin >> N;
    vector<vector<pair<int, int> > > v(N);
    rep(i,N){
        int A;
        cin >> A;
        rep(j,A){
            int x, y;
            cin >> x >> y;
            x--;
            v[i].push_back(make_pair(x, y));
        }
    }
    int res = 0;
    for (int bit = 0; bit < (1 << N);bit++){
        if(judge(N,bit,v)){
            int count = 0;
            for (int i = 0; i < N;i++){
                if(bit&(1<<i)){
                    count++;
                }
            }
            res = max(res, count);
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3600
import heapq
const = 0
left = []
right = []

q = int(input())
cnt = 0
left_sum = 0
right_sum = 0
for _ in range(q):
    t = list(map(int, input().split()))
    if t[0] == 1:
        # update
        a, b = t[1:]
        const += b
        if cnt % 2 == 0:
            if not right:
                heapq.heappush(left, -a)
                left_sum += a
                cnt += 1
                #print(left_sum, right_sum, cnt)
                continue

            c = heapq.heappop(right)
            right_sum -= c
            if a <= c:
                heapq.heappush(left, -a)
                heapq.heappush(right, c)
                left_sum += a
                right_sum += c
            else:
                heapq.heappush(left, -c)
                heapq.heappush(right, a)
                left_sum += c
                right_sum += a
        else:
            c = heapq.heappop(left)
            left_sum += c
            if a <= -c:
                heapq.heappush(left, -a)
                heapq.heappush(right, -c)
                left_sum += a
                right_sum -= c
            else:
                heapq.heappush(left, c)
                heapq.heappush(right, a)
                left_sum -= c
                right_sum += a
        cnt += 1
        #print(left_sum, right_sum, cnt)
    else:
        tmp = -left[0]
        print(tmp, const - left_sum + right_sum + tmp * (cnt % 2))



Measured memory_bytes: 84488
//Dragon_warrior7(IITK)
// #pragma GCC optimize("O0") 
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize ("-ffloat-store")
#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 umap unordered_map
#define uset unordered_set
#define ll long long
//#define lll long long
#define pb push_back
#define nl cout << '\n'
#define sor(x) sort(x.begin(), x.end())
#define rev(v) reverse(v.begin(), v.end())
#define lb(v, temp) lower_bound(v.begin(), v.end(), temp)
#define ub(v, temp) upper_bound(v.begin(), v.end(), temp)
#define fi first
#define se second
#define llmax 1000000000000000000
#define pll pair<ll, ll> 
//#define ull unsigned ll
#define vll vector<ll>
#define vpll vector<pll> 
#define rub cerr << "\n------------------------------------\n"
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
#define fo(i,a,b) for(int i=a;i<b;i++)
#define Lets_be_precise cout<<fixed<<setprecision(10)
//typedef  tree < int ,  null_type ,  greater<int> ,  rb_tree_tag ,  tree_order_statistics_node_update > oset;
const int mod=1e9+7;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// ll modInverse(ll a){return power(a,mod-2);}
ll n,m,a,b,c,k,temp,x,y;
const int MAXN=100000+11;
void read(vector<ll> &v)
{for (int i = 0; i < v.size(); i++)cin>>v[i];}
inline ll max(ll a,ll b)
{return ((a>b)?a:b);}
inline ll min(ll a,ll b)
{return ((a>b)?b:a);}
inline ll int gcd(ll int a ,ll int b)
{if(b==0) return a;a%=b;return gcd(b,a);}
//#define cerr if(false)cerr//uncomment to remove cerr from program...
void solveforthiscase(const int & test)
{//deb(test);
cin>>n>>k;
ll dp[k+10];
for(int i=k;i>=1;i--)
{
    dp[i]=power(k/i,n);
    for(int j=2*i;j<=k;j+=i)
    {
        dp[i]=(dp[i]+mod-dp[j])%mod;
    }
}
ll ans=0;
for(int i=1;i<=k;i++)
{
    ans+=(dp[i]*i)%mod;
    ans%=mod;
}
cout<<ans;
return ;
}
int main()
{
	ios_base::sync_with_stdio(false);
	Lets_be_precise;
	cin.tie(NULL);
	cout.tie(NULL);
	int test=1;
// 	cin>>test;
    for(int i=1;i<=test;i++)
    {
        solveforthiscase(i);
    }
}

Measured memory_bytes: 4292
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

// vector<vector<int>> data(3, vector<int>(4));

bool is_product_overflow(long long unsigned a, long long unsigned b) {
  long long prod = a * b;

  return (prod / b == a);
}

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

  long long unsigned a;

  long long unsigned n;
  cin >> n;
  vector<long long unsigned> vec;

  for (long long unsigned i = 0; i < n; i++) {
    cin >> a;
    if (a == 0) {
      cout << "0";
      return 0;
    }
    if (a > 1000000000000000000) {
      cout << "-1";
      return 0;
    }
    vec.push_back(a);
  }
  sort(vec.begin(), vec.end(), std::greater<int>());

  long long unsigned ans = 1;
  for (long long unsigned i = 0; i < n; i++) {
    if (!is_product_overflow(ans, vec[i])) {
      // cout << "test";
      cout << "-1";
      return 0;
    }
    ans *= vec[i];
    //printf("%llu\n", ans);
    if (ans > 1000000000000000000 && ans < 0) {
      cout << "-1";
      return 0;
    }
  }

  if (ans > 1000000000000000000) {
    cout << "-1";
    return 0;
  }
  printf("%llu", ans);

  return 0;
}

Measured memory_bytes: 4284
#include <cstdio>

int main() {
    int a, b, c, t;
    scanf("%d%d%d", &a, &b, &c);

    if (a > b) {
        t = b;
        b = a;
        a = t;
    }
    if (b > c) {
        t = c;
        c = b;
        b = t;
    }
    if (a > b) {
        t = b;
        b = a;
        a = t;
    }

    printf("%d %d %d\n", a, b, c);
}


Measured memory_bytes: 2624
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d;
  cin>>a>>b;
   if(a==1 || a==3 || a==5 || a==7 || a==8 || a==10 || a==12)
     c=1;
  	if(a==4 || a==6 || a==9 || a==11)
      c=2;
  	if(a==2)
      c=3;
   if(b==1 || b==3 || b==5 || b==7 || b==8 || b==10 || b==12)
     d=1;
  if(b==4 || b==6 || b==9 || b==11)
      d=2;
  	if(b==2)
      d=3;
  	if(c==d)
     cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
      
  return(0);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int gcd(int a, int b) {  
  return b != 0 ? gcd(b, a % b) : a;
}//MAX
int lcm(int a, int b) { 
   return a * b / gcd(a, b);
   }
//MIN
 main() {
int n;
cin >> n;
int che =0,chea=0;
for(int i=0;i<n;i++){
  int z;
  cin >> z;
  if(z%4==0)che++;
  else if(z%2==0)chea++;
}
che+=chea/2;
  if(n/2<=che)cout <<"Yes"<<endl;
  else{
    cout << "No"<<endl;
  }
 }
 


Measured memory_bytes: 256
N = int(input())
joblist = [[int(s) for s in input().split()] for i in range(N)]
joblist_sorted = sorted(joblist, key=lambda x: x[1])
task = 0
flg = 'Yes'
for i in range(N):
  A, B = joblist_sorted[i]
  task = task + A
  if task > B:
    flg = 'No'
print(flg)

Measured memory_bytes: 90200
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#define int long long
#define MOD 1000000007
using namespace std;
using namespace __gnu_pbds; 
typedef tree<int, null_type, less<int>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    pbds;
   
int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    vector<pair<string, int>> v;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        int r;
        cin>>r;
        v.push_back({s,r});
    }
    string t;
    cin>>t;
    int ans = 0;
    bool found = false;
    for(int i=0;i<n;i++)
    {
        if(v[i].first == t)
        {
            found = true;
            continue;
        }
        if(found)
        {
            ans += v[i].second;
        }
    }
    cout<<ans<<'\n';
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

int main()
{
  int h,w,d;
  cin>>h>>w>>d;
  vector<pair<int,int>> mp(h*w+10);
  for (int i = 0; i < h; ++i)
  {
    for (int j = 0; j < w; ++j)
    {
      int a;
      cin>>a;
      mp[a]={i,j};
    }
  }
  auto diff=[](pair<int,int> l, pair<int,int> r){
    return abs(l.first-r.first)+abs(l.second-r.second);
  };
  unordered_map<int, int> cost;
  for (int start = 1; start <= d; ++start)
  {
    for (int i = start; i+d <= h*w ; i+=d)
    {
      cost[i+d]=cost[i]+diff(mp[i],mp[i+d]);      
    }
  }
  int q; cin>>q;
  for (int i = 0; i < q; ++i)
  {
    int l,r;
    cin>>l>>r;
    cout<<cost[r]-cost[l]<<endl;
  }

}

Measured memory_bytes: 7816
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1e9+7,INF=mod*mod*3;//M_PI
#define rep(i,N) for(ll i=0; i<(N); i++)
#define rep1(i,N) for(ll i=1; i<(N); i++)
#define pb push_back
ll N;
ll ans[100005];
int main(){

cin.tie(0);
ios::sync_with_stdio(false);

cin>>N;
rep(i,N){
    ll A;
    cin>>A; A--;
    ans[A]=i+1;
}
rep(i,N) cout<<ans[i]<<" ";
cout<<endl;


}
    


Measured memory_bytes: 4416
def read_int():
    return int(input())


def read_ints():
    return map(int, input().split(' '))


x, n = read_ints()
p = []
if n > 0:
    p = list(read_ints())
ans = -1
delta = 1000
for i in range(-1, 102):
    ok = True
    for j in p:
        if j == i:
            ok = False
            break
    if ok:
        d = abs(x - i)
        if d < delta:
            ans = i
            delta = d
print(ans)


Measured memory_bytes: 9196
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include <string>
#include <cmath>
#include <functional>
#include <queue>
#include <map>
using namespace std;

typedef long long ll;
const int M = 1e9 + 7;
const int N = 2e5 + 100;
const int MAX = 1e9 + 1;
//int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int n, m;
vector<int> adj[N];
int vis[N];

bool dfs(int x, int deep) {
    if (deep > 2)
        return x == n;
    for (int i = 0; i < adj[x].size(); ++i) {
        int t = adj[x][i];
        if (!vis[t]) {
            vis[t] = 1;
            if (dfs(t, deep + 1))
                return 1;
        }
    }
    return 0;
}

int main() {
    int i, j;
    scanf("%d%d", &n, &m);
    for (i = 0; i < m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vis[1] = 1;
    printf("%s\n", dfs(1, 1) ? "POSSIBLE" : "IMPOSSIBLE");
    return 0;
}


Measured memory_bytes: 12784
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl "\n"

int main()
{
  i64 N;
  cin >> N;
  vector<i64> A(N), B(N);
  for (i64 i = 0; i < N; i++)
    cin >> A[i] >> B[i];
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());
  if (N % 2 == 0)
    cout << B[N / 2 - 1] + B[N / 2] - (A[N / 2 - 1] + A[N / 2]) + 1 << endl;
  else
    cout << B[N / 2] - A[N / 2] + 1 << endl;
  return 0;
}


Measured memory_bytes: 6428
import sys
readline = sys.stdin.readline
s = [-1, -2] + list(map(ord, readline().strip()))
N = len(s)
ans = (-1, -1)
for i in range(2, N):
    if s[i] == s[i-1]:
        ans = (i-2, i-1)
        break
    if s[i] == s[i-2]:
        ans = (i-3, i-1)
        break
print(*ans)

Measured memory_bytes: 46192
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>
#include <utility>
#include <vector>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <stack>
#include <queue>
#define div1 1000000007
const long long INF = 1LL << 60;
using namespace std;
using ll = long long;
using ld = long double;
// a>b -> a==b;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
// a<b -> a==b;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(void)
{
    ll N, i, A[100001], S[100001], judge[100001], ans=0;

    cin >> N;

    S[0] = 0;

    for(i=1; i<=N; i++){
        cin >> A[i];
    }

    sort(A+1, A+N+1);

    for(i=1; i<=N; i++){
        S[i] = S[i-1]+A[i];
    }

    for(i=1; i<=N-1; i++){
        if(S[i]*2 < A[i+1]) judge[i] = 0;
        else judge[i] = 1;
    }

    judge[N] = 1;

    for(i=N; i>=1; i--){
        if(judge[i]==1) ans++;
        else break;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 2560
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())

AB = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

# 二部グラフかどうかを判定する
color = [None] * (N+1)
color[1] = 0
q = [1]
while q:
    x = q.pop()
    for y in graph[x]:
        if color[y] is None:
            color[y] = 1 - color[x]
            q.append(y)

bl = all(color[a] != color[b] for a,b in AB)

if bl:
    # 完全二部グラフにする
    x = sum(color[1:])
    y = N - x
    answer = x*y - M
else:
    # 完全グラフにする
    answer = N*(N-1)//2 - M

print(answer)

Measured memory_bytes: 34596
Q = int(input())
lr = [[int(_) for _ in input().split()] for _ in range(Q)]

p_max = 101010
is_prime = [True] * (p_max)
is_prime[0] = is_prime[1] = False

for i in range(2, p_max):
    if not is_prime:
        continue
    for j in range(i+i, p_max, i):
        is_prime[j] = False

a = [0] * (p_max)
for i in range(p_max):
    if is_prime[i] is True and is_prime[(i+1)//2] is True:
        a[i] = 1

s = [0] * (p_max+1)
for i in range(p_max):
    s[i+1] = s[i] + a[i]

for i in lr:
    print(s[i[1]+1]-s[i[0]])

Measured memory_bytes: 26616
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF LLONG_MAX/5
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
int mypow(int a,int b,int c){
	if(b==0)return 1;
	if(b%2)return mypow(a,b-1,c)*a%c;
	int z=mypow(a,b/2,c);
	return z*z%c;
}
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
signed main(){
	int a,b,c;
	cin>>a>>b>>c;
	if(c==mod-7){
		f(i,b){
			if(i)cout<<" ";
			cout<<mod-7;
		}
		f(i,a-b)cout<<" 1";
		puts("");
	}
	else{
		f(i,b){
			if(i)cout<<" ";
			cout<<c;
		}
		f(i,a-b)cout<<" 1000000000";
		puts("");
	}
}


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

int main()
{
	int n;
	cin>>n;
	double a[n+1];
	
	for(int i=1; i<=n; i++)
	cin>>a[i];
	
	double dp[n+1][n+1];
	
	double t[n+1];
	double h[n+1];
	t[1]=1-a[1];
	h[1]=a[1];
	
	for(int i=2; i<=n; i++)
	t[i]=t[i-1]*(1-a[i]);
	
    for(int i=2; i<=n; i++)
	h[i]=h[i-1]*(a[i]);
	
	for(int i=1; i<=n ; i++)
	dp[i][i]=h[i];
	
	
	for(int i=2; i<=n; i++)
	dp[i][1]=dp[i-1][1]*(1-a[i])+t[i-1]*a[i];
	
	
	for(int i=2; i<=n; i++)
	{
		for(int j=2; j<i; j++)
		{
			dp[i][j]=dp[i-1][j-1]*a[i]+dp[i-1][j]*(1-a[i]);
			
		}
	}
	
	double s=0;
	for(int i=n/2+1; i<=n; i++)
	s+=dp[n][i];
	
	cout<<setprecision(12)<<s;
	
	
}

Measured memory_bytes: 70144
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';


using namespace std;

int main(void){
    ll N, M;
    ll A, B;
    vector<pair<ll, ll> > cost;
    cin>>N>>M;
    rep(i, N){
        cin>>A>>B;
        cost.push_back({A, B});
    }
    sort(all(cost));
    ll count=0, cosc=0;
    rep(i,N){
        if(cost[i].second<M-count){
            count+=cost[i].second;
            cosc+=cost[i].first*cost[i].second;
        }
        else{
            cosc+=(M-count)*cost[i].first;
            break;
        }
        //cout<<cosc<<sp<<count<<endl;
    }
    cout<<cosc<<endl;
    return 0;
}


Measured memory_bytes: 2420
#include<bits/stdc++.h>
using namespace std;
//#include<boost/multiprecision/cpp_int.hpp>
//using boost::multiprecision::cpp_int;

#define int long long
#define cint cpp_int
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) (((a)+(b)-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2
#define PI acos(-1.0)

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;
typedef priority_queue<int> PQi;

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;}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vout(Vs &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vvout(VVi &v){for(int i=0;i<(v).size();i++) vout(v[i]);}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int mypow(int x, int n, int m){if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}
int digit(int k,int i){string s = to_string(k);return s[s.size()-i]-'0';}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());} //vectorの同じ要素消す
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
int leng(int n){string s=to_string(n); return s.size();} //intの桁数
int digitsum(int n){int ret=0; while(n>0){ret+=n%10;n/=10;}return ret;} //桁和
int lesscount(int x,Vi &a){return lower_bound(a.begin(),a.end(),x)-a.begin();} //vector aにおけるx未満の数の個数
int orlesscount(int x,Vi &a){return upper_bound(a.begin(),a.end(),x)-a.begin();} //vector aにおけるx以下の数の個数
int morecount(int x,Vi &a){return a.size()-orlesscount(x,a);} //vector aにおけるxより大きい数の個数
int ormorecount(int x,Vi &a){return a.size()-lesscount(x,a);} //vector aにおけるx以上の数の個数
int count(int x,Vi &a) {return upper_bound(ALL(a),x)-lower_bound(ALL(a),x);} //vector aにおけるxの個数
Vi accum(Vi &v){Vi ret((v).size()+1);REP(i,0,(v).size()) ret[i+1]=ret[i]+v[i];return ret;}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);
    int n;
    cin>>n;
    Vi a(n);
    REP(i,0,n){
        cin>>a[i];
        a[i]--;
    }

    int now=0,count=0;
    while(1){
        now = a[now];
        count++;
        if(now==1) break;
        if(count==10000000) {cout<<-1<<endl; return 0;}
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mex = 1e9 + 7;
int main()
{
    ll n, k; cin >> n >> k;
    vector<ll> h(n), dp(n, mex);
    for(ll& i : h) cin >> i;
    dp[0] = 0;
    for(ll i = 0; i < n; i++) {
        for(ll j = i + 1; j <= i + k and j < n; j++) {
            dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
        }
    }
    cout << dp[n-1] << '\n';
    return 0;
}

Measured memory_bytes: 4820
#include<stdio.h>
int inverse(int n)
{
	int sum=0;
	while(n>0)
	{
		sum=sum+n%10;
		n=n/10;
		sum*=10;
	}
	return sum/10;
}
int main()
{
	int a,b,i,c=0;
	scanf("%d%d",&a,&b);
	for(i=a;i<=b;i++)
	{
		if(inverse(i)==i)
		{
			c++;
		}		
	}
	printf("%d\n",c);
	return 0;
} 

Measured memory_bytes: 128
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
int N,K,X,Y;
int main(){
	cin>>N>>K>>X>>Y;
	if(N>K)cout<<K*X+(N-K)*Y<<endl;
	if(N<=K)cout<<N*X<<endl;


	return 0;
}


Measured memory_bytes: 256
n,q = map(int,input().split())
s = list(input())
p = [tuple(map(str,input().split())) for i in range(q)]

#s[x]が左へ抜けるか O(q)
def judge_left(x):
    for i in range(q):
        if p[i][0] == s[x]:
            if p[i][1] == 'L':
                x -= 1
            else:
                x += 1
        if x == -1:
            return True
        if x == n:
            return False
    return False

#s[x]が右へ抜けるか O(q)
def judge_right(x):
    for i in range(q):
        if p[i][0] == s[x]:
            if p[i][1] == 'L':
                x -= 1
            else:
                x += 1
        if x == -1:
            return False
        if x == n:
            return True
    return False

#どこまで左で抜けるか
ok = -1
ng = n
while ng-ok > 1:
    mid = (ng+ok)//2
    if judge_left(mid):
        ok = mid
    else:
        ng = mid
left = ok+1

#どこまで右で抜けるか
ok = n
ng = -1
while ok-ng >1:
    mid = (ok+ng)//2
    if judge_right(mid):
        ok = mid
    else:
        ng = mid
right = n-ok

print(max(n-left-right,0))

Measured memory_bytes: 103880
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()
template<class T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;


int main(){
    ll n;
    cin >> n;
    vector<ll> x(n), y(n), p(n);
    REP(i, n){
        cin >> x[i] >> y[i] >> p[i];
    }

    vector<vector<ll>> x2d(1LL << n, vector<ll>(n)), y2d(1LL << n, vector<ll>(n));
    REP(i, (1LL << n)){
        REP(j, n){
            ll dx = abs(x.at(j)), dy = abs(y.at(j));
            REP(k, n){
                if((i >> k) & 1){
                    dx = min(dx, abs(x.at(j) - x.at(k)));
                    dy = min(dy, abs(y.at(j) - y.at(k)));
                }
            }
            x2d.at(i).at(j) = dx;
            y2d.at(i).at(j) = dy;
        }
    }

    ll ub = 1;
    REP(i, n){ ub *= 3; }

    vector<ll> ans(n + 1, numeric_limits<ll>::max());

    REP(i, ub){
        ll ix = 0, iy = 0, k = 0;
        {
            ll m = i;
            REP(j, n){
                const ll l = m % 3;
                if(l == 1){
                    ix += (1LL << j);
                    k++;
                }else if(l == 2){
                    iy += (1LL << j);
                    k++;
                }
                m /= 3;
            }
        }

        ll s = 0;
        const auto& dx = x2d.at(ix), dy = y2d.at(iy);
        REP(j, n){
            s += p.at(j) * min(dx.at(j), dy.at(j));
        }

        ans.at(k) = min(ans.at(k), s);
    }

    for(auto ai : ans){
        cout << ai << endl;
    }
    return 0;
}


Measured memory_bytes: 13012
using System;
using System.Collections.Generic;

class Program
{
	static void Main(string[] args)
	{
		var IN = Console.ReadLine().Split(' ');
		var N = int.Parse(IN[0]);
		var K = int.Parse(IN[1]);
		var Q = uint.Parse(IN[2]);
		var A = new List<uint>();
		var member = new List<long>();
		var tmpmember = new List<long>();
		
		for (int i = 0; i < Q; i++) {
			A.Add(uint.Parse(Console.ReadLine()));
		}
		
		for (int i = 0; i < N; i++) {
			member.Add(K - Q);
		}
		var score = member.ToArray();
		foreach (var a in A) {
			score[a - 1]++;
		}
		
		foreach (var element in score) {
			if (element <= 0) {
				Console.Write("No\r\n");
			} else {
				Console.Write("Yes\r\n");
			}
		}
//		Console.ReadLine();
	}
}

Measured memory_bytes: 19040
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
C = sorted(list(map(int, input().split())))
M = sum(C[:-1])
import sys
sys.setrecursionlimit(10**8)

def dfs(v):
  for u in edge[v]:
    if nums[u]==-1:
      nums[u]=C.pop(-1)
      dfs(u)
  return 0

nums = [-1]*N
nums[0] = C.pop(-1)
dfs(0)

print(M)
print(*nums)

Measured memory_bytes: 19268
isPalindrome::[Char]->Bool
isPalindrome cn = cn == reverse cn

main = do
  s <- getLine
  let n = length s
  putStrLn $ if (isPalindrome s) && (isPalindrome $ take (div (n-1) 2) s) && (isPalindrome $ drop ((div (n+3) 2)-1) s) then "Yes" else "No"

Measured memory_bytes: 508
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

int main() {
  int n;
  cin >> n;

  if (n < 105) cout << 0 << endl;
  else if (n < 135) cout << 1 << endl;
  else if (n < 165) cout << 2 << endl;
  else if (n < 189) cout << 3 << endl;
  else if (n < 195) cout << 4 << endl;
  else if (n <= 200) cout << 5 << endl;
  
  return 0;
}

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

int main() {
    string s, p;
    cin >> s >> p;
    s += s;
    int slen = s.size(),
        plen = p.size();
    
    //for (int i = 0; i < plen; ) {
        for (int j = 0; j < slen; ) {
            if (s.at(j) == p.at(0)) {
                string str = s.substr(j, plen);
                if (p == str) {
                    cout << "Yes" << endl;
                    return 0;
                } else {
                  j++;
                  if (j == slen) {
                    cout << "No" << endl;
                    return 0;
                  }
                }
            } else {
                j++;
                if (j == slen) {
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    //}
}


Measured memory_bytes: 3228
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <random>
#include <fstream>
#include <string>
#include <tuple>
#include <deque>
#include <set>
#include <map>
#include <stack>

#define REP(i, N) for(int i = 0; i< N; i++)
using namespace std;
#define ll long long
const int INF = 1 << 29;
const ll llINF = 10000000000000000;

const int MOD = 1000000007;

#define MAX_N 100100
typedef pair<int, int> P;
typedef pair<ll, ll> llP;

class UnionFindTree{
private:
    int par[MAX_N];
    int urank[MAX_N];
    int size[MAX_N];
public:
    int init(int n);
    int find(int x);
    int unite(int x, int y);
    int same(int x, int y);
    int parnum(int x){return par[x];}
    int ranknum(int x){return urank[x];}
    int sizenum(int x){return size[find(x)];}
};

int UnionFindTree::init(int n){
    REP(i, n){
        par[i] = i;
        urank[i] = 0;
        size[i] = 1;
    }
    return 0;
}

int UnionFindTree::find(int x){
    if(par[x] == x)return x;
    else return par[x] = find(par[x]);
}

int UnionFindTree::unite(int x, int y){
    x = find(x);
    y = find(y);
    
    if(x == y)return 0;
    if(urank[x] < urank[y]){
        par[x] = y;
        size[y] += size[x];
    }else{
        par[y] = x;
        size[x] += size[y];
        if(urank[x] == urank[y])urank[x] ++;
    }
    return 0;
}

int UnionFindTree::same(int x, int y){
    return find(x) == find(y);
}


int main(){
    int N, i;
    cin >> N >> i;
    printf("%d\n", N - i  +1);
}


Measured memory_bytes: 888
#include <stdio.h>

#define M_MAX         10000
#define N_MAX         1000
#define r_MAX         1000
#define q_MAX         50
#define DATASET_MAX   10
#define TS_MIN        540
#define TE_MAX        1260
#define USETIME_MAX   TE_MAX-TS_MIN

struct LogInfo{
  int PCNum;
  int LogInTime;
  int LogOutTime;
};

int LogInCnt[M_MAX];
struct LogInfo LogInfoData[M_MAX][r_MAX];
int UsePCTime[DATASET_MAX];

void VarInit( void ){
  int i;
  int j;
  
  for( i=0; i<M_MAX; i++ ){
    LogInCnt[i] = 0;
    for( j=0; j<r_MAX; j++ ){
      LogInfoData[i][j].PCNum = 0;
      LogInfoData[i][j].LogInTime = 0;
      LogInfoData[i][j].LogOutTime = 0;
    }
  }
}


void RecLogInInfo( int t, int n, int m ){
  LogInfoData[m][LogInCnt[m]].PCNum = n;
  LogInfoData[m][LogInCnt[m]].LogInTime = t;
  LogInCnt[m]++;
}

void RecLogOutInfo( int t, int n, int m ){
  int i;
  
  for( i=0; i<LogInCnt[m]; i++ ){
    if( (LogInfoData[m][i].PCNum == n) && (LogInfoData[m][i].LogOutTime == 0)){
      LogInfoData[m][i].LogOutTime = t;
    }
  }
}

int CalcUsePCTime( int ts, int te, int m ){
  int i,j,t1,t2,Time;
  int Work[USETIME_MAX+1];
  Time = 0;
  
  for( i=0; i<USETIME_MAX+1; i++){
    Work[i] = 0;
  }
  
  for( i=0; i<LogInCnt[m]; i++ ){
    if( LogInfoData[m][i].LogInTime > ts ){
      t1 = LogInfoData[m][i].LogInTime;
    }else if((LogInfoData[m][i].LogInTime <= ts) && (LogInfoData[m][i].LogOutTime >= ts)){
      t1 = ts;
    }else{
      t1 = 0;
    }
    
    if( LogInfoData[m][i].LogOutTime < te ){
      t2 = LogInfoData[m][i].LogOutTime;
    }else if((LogInfoData[m][i].LogInTime <= te) && (LogInfoData[m][i].LogOutTime >= te)){
      t2 = te;
    }else{
      t2 = 0;
    }
    
    for( j=t1; j<t2; j++){
      Work[j-TS_MIN] = 1;
    }
  }
  
  for( i=ts; i<=te; i++){
    if(Work[i-TS_MIN] == 1){
      Time++;
    }
  }
  
  return Time;
}


int main( void ){
  int i,N,M,r,q,t,n,m,s,ts,te;
  int qNum;
  int UseTime;
  
  qNum = 0;
  for( i=0; i<DATASET_MAX; i++ ){
    UsePCTime[i] = 0;
  }
  while( 1 ){
    scanf( " %d %d", &N, &M );
    if( N == 0 ){
      break;
    }
    VarInit();
    scanf( " %d", &r );
    for( i=0; i<r; i++ ){
      scanf( " %d %d %d %d", &t, &n, &m, &s );
      if( s == 1 ){
         RecLogInInfo( t, n, m );
      }else{
        RecLogOutInfo( t, n, m );
      }
    }
    
    scanf( " %d", &q );
    for( i=0; i<q; i++ ){
      scanf( " %d %d %d", &ts, &te, &m );
      UseTime = CalcUsePCTime( ts, te, m );
      printf("%d\n",UseTime);
    }
  }
}




Measured memory_bytes: 119900
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <utility>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <cmath>

#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vec vector
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

using namespace std;

bool comb(pair<int,int> a,pair<int,int> b){
    if(a.first==b.first){
        return a.second>b.second;
    }else return a>b;
}

int main(){
    int h,r;
    cin>>h>>r;
    if(h==-r)cout<<0<<endl;
    else if(h<-r)cout<<-1<<endl;
    else cout<<1<<endl;
    
    return 0;
}



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

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 << "Balanced" << endl;
  else
    cout << "Right" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    char b;
    cin>>b;
    if (b=='A') {
        cout<<"T"<<endl;
    } else if (b=='C') {
        cout<<"G"<<endl;
    } else if (b=='G') {
        cout<<"C"<<endl;
    } else {
        cout<<"A"<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N; cin >> N;
  vector<int> H(25);
  
  for(int i=0; i<N; i++) cin >> H.at(i);
  int count =1;
  int maxim = H.at(0);
  for(int i=1; i<N; i++) {
    if(maxim <= H.at(i)) count++;
    maxim = max(maxim,H.at(i));
  }
  cout << count << endl;
}

Measured memory_bytes: 3560
fun main(args: Array<String>) {
    var i = readLine()!!.toInt()
    while (true) {
        if (isSosu(i)) {
            println(i)
            return
        }
        i += 1
    }
}

fun isSosu(n: Int): Boolean {
    if (n < 2) {
        return false
    }
    for (i in 2..(n - 1)) {
        if (n % i == 0) {
            return false
        }
    }
    return true
}


Measured memory_bytes: 33528
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;

#[fastout]
fn main() {
    input! {
    n: usize,
    m: usize,
    }
    let mut a_list = vec![];
    for _ in 0..n {
        input! {
        k: usize,
        a: [Usize1; k]
        }
        a_list.push(a);
    }
    let mut is_like = vec![1; m];
    for i in 0..n {
        for j in 0..m {
            if !a_list[i].contains(&j) {
                is_like[j] = 0;
            }
        }
    }
    let ans = is_like.iter().filter(|&&x| x == 1).count();
    println!("{}", ans);
}


Measured memory_bytes: 2168
using System;
using System.Collections.Generic;
class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            int n = s.Length;
            char c = '0';
            int ans = 0;
            for (int i=0; i<n; i++)
            {
                if (s[i] == c) ans ++;
                if (c == '1') c = '0';
                else c = '1'; 
            }
            ans = Math.Min(ans, n - ans);
            Console.WriteLine(ans);

            
            

            
            


            
        }
    }
    //mcs Main.cs
    //mono Main.exe

Measured memory_bytes: 11232
import java.util.*;
import java.io.*;

public class Main {

	private static void solve(){
		//Implement solution here.
		int n = ni();
		int k = ni();
		int r = ni();
		int s = ni();
		int p = ni();
		char[] t = next().toCharArray();
		boolean[] changed = new boolean[n];
		int result = 0;
		
		for(int i = 0; i < n; i++) {
			if(i + k < n && !changed[i]) {
				if(t[i] == t[i + k])changed[i + k] = true;
			}
		}
		
		for(int i = 0; i < n; i++) {
			if(!changed[i]) {
				if(t[i] == 'r') {
					result += p;
				}else if(t[i] == 's') {
					result += r;
				}else {
					result += s;
				}
			}
		}
		System.out.println(result);
	}

	//Switch input source (stdin/file)
	private static BufferedReader br;
	public static void main(String[] args){
		br = new BufferedReader(new InputStreamReader(System.in));
		String debugDataPath = System.getenv("DD_PATH");        
		if(debugDataPath != null){
			try{
				br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
			}catch(Exception e){
				throw new RuntimeException(e);
			}
		}
		solve();
	}

	//Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	//Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
	//Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
	//Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
	//Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
	//Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}

Measured memory_bytes: 24404
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int ac = 0;
        int wa = 0;
        int tle = 0;
        int re = 0;

        for (int i = 0; i < N; i++) {
            String hantei = sc.next();
            switch (hantei) {
                case "AC":
                    ac++;
                    break;
                case "WA":
                    wa++;
                    break;
                case "TLE":
                    tle++;
                    break;
                case "RE":
                    re++;
                    break;

            }
        }

        sc.close();

        System.out.printf("AC x %d\n", ac);
        System.out.printf("WA x %d\n", wa);
        System.out.printf("TLE x %d\n", tle);
        System.out.printf("RE x %d\n", re);
    }
}

Measured memory_bytes: 57948
s=int(input())
a=[s]
check=0
for i in range(1000000):
    n=a[i]
    if n%2==0:
        num=n//2
        if num in a:
            check=i+2
            break
        a.append(num)
    else:
        num=3*n+1
        if num in a:
            check=i+2
            break
        a.append(num)
print(check)
#print(*a)

Measured memory_bytes: 9144
var     a:array[1..1000]of longint;
        n,max,min:longint;

procedure nhap;
var     i:longint;
begin
        readln(n);
        max:=0;
        min:=maxlongint;
        for i:=1 to n do
            begin
                read(a[i]);
                if a[i]>max then max:=a[i];
                if a[i]<min then min:=a[i];
            end;
end;

procedure xuli;
begin
        writeln(max-min);
end;

begin
        //assign(input,'at_02.inp');reset(input);
        //assign(output,'at_02.out');rewrite(output);
                nhap;
                xuli;
end.


Measured memory_bytes: 128
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#include <map>
#include <stdio.h>
#include <queue>
#include <unordered_set>
#define rep(i,n) for (int i=0;i<(n);++i)
#define REP(i,n) for (int i=0;i<=(n);++i)
#define all(x) (x).begin(), (x).end()

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; }

using namespace std;
typedef long long ll;
const int INF = 10000000;

int main() {
    int n; cin >> n;

    vector<int> b(1000001);
    rep(i, 1000001) {
        b[i] = 0;
    }

    vector<int> a(n);
    rep(i, n) {
        cin >> a[i];
        ++b[a[i]];
    }

    int ans = n;
    
    for(int i = 0; i < n; ++i) {
        for(int j = 1; j <= sqrt(a[i]); ++j) {
            if(a[i] % j == 0) {
                if(a[i] == 1) {
                    if(b[j] > 1) {
                        --ans;
                        break;
                    }
                }else if(b[j] > 0) {
                    --ans;
                    break;
                }else if(j == 1) {
                    if(b[a[i]] > 1) {
                        --ans;
                        break;
                    }
                }else{
                    if(b[a[i]/j] > 0) {
                        --ans;
                        break;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 7924
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define FOR(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 speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int strToInt(string s){
    int x = 0;
    reverse(all(s));
    for(int i = 0; i < s.size(); i++){
        x += (s[i] - '0') * pow(10, i);
    }
    return x;
}
string t;
int ans = 0;
void f(string s){
    int cnt3 = 0;
    int cnt5 = 0;
    int cnt7 = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '3') cnt3++;
        if(s[i] == '5') cnt5++;
        if(s[i] == '7') cnt7++;
    }
    if(cnt3 > 0 && cnt5 > 0 && cnt7 > 0) if(strToInt(s) <= strToInt(t)) ans++;
    if(s.size() == t.size()) return ;
    f(s + "3");
    f(s + "5");
    f(s + "7");
}
int main(){
    cin >> t;
    f(""); 
    cout << ans;   
}

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

  int inner = 0;
  int outer = 0;

  for (int i = 0; i < n; i++){
    for (int j = i + 1; j < n; j++){
      if(a[i] > a[j]){
        inner++;
      }else if (a[i] < a[j]){
        outer++;
      }
    }
  }
  
  cout << ((inner + outer) * (k * (k - 1) / 2 % 1000000007) + inner * k) % 1000000007 << endl;
  return 0;
}


Measured memory_bytes: 256
K = int(input())

def snuke(n):
  n_list = [int(i) for i in list(str(n))]
  return n / sum(n_list)

ans = 1
digit = 0

while K > 0:
  print(ans)
  if snuke(ans + 10**digit) > snuke(ans + 10**(digit+1)):
    digit += 1
  ans += 10**digit
  K -= 1


Measured memory_bytes: 3188
#define _CRT_SECURE_WARNINGS

#include<stdio.h>

int main(void)
{
	int x;

	int i = 1;

	while (i > 0) {
		scanf("%d", &x);

		if (x == 0)
			break;

		printf("Case %d: %d\n", i, x);
		i++;
	}
	return 0;
}


Measured memory_bytes: 2564
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int dig(int n){
  int ans = 0;
  while(n >= 1){
    ans++;
    n /= 10;
  }

  return ans;
}

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

  int cnt = 0;
  for(int i = 1; i <= N; i++){
    if(dig(i) % 2 == 1) cnt++;
  }

  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> /**  I'm Klaus, NicKlaus :v **/
using namespace std;
#define ms(a,v) memset(a,v,sizeof a)
#define ll long long
#define ld long double
ll gcd(ll x, ll y){return (y ? gcd(y, x%y) : x); }
ll lcm(ll x, ll y){return x*(y/gcd(x,y));}

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	#ifdef LOCAL_JUDGE
		//freopen("in_out/in.txt", "rt", stdin);
		//freopen("int_out/out.txt", "wt", stdout);
	#endif
	int n, k;
	cin>>n>>k;
	vector<int> v(n+1);
	vector<int> w(n+1);
	int nax = 0;
	for(int i=1; i<=n; i++){
		cin>>w[i]>>v[i];
		nax += v[i];
	}
	vector<int> dp(nax+7,-1);
	dp[0] = 0;
	for(int i=1; i<=n; i++){
		for(int j=nax; j>=0; j--){
			if(dp[j] != -1){
				dp[j+v[i]] = min((dp[j+v[i]] != -1 ? dp[j+v[i]] : (int)1e9 ),dp[j]+w[i]);
			}
		}
	}
	int ans = 0;
	for(int i=0; i<dp.size(); i++){
		//cout<<i<<" "<<dp[i]<<endl;
		if(dp[i] <= k && dp[i] != -1 ){
			ans = max(ans,i);
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 640
N=int(input())
l=[]
for x in range(0,N):
    l.append(input())
for x in range(N):
    k=list(l[x])
    k.sort()
    k=''.join(k)
    l[x]=k
l.sort()
k=1
ans=0
for i in range(N-1):
    if l[i]==l[i+1]:
        k+=1
    else:
        ans+=k*(k-1)//2
        k=1
ans+=k*(k-1)//2
print(ans)

Measured memory_bytes: 10584
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0185

"""
import sys
from sys import stdin
from bisect import bisect_left
input = stdin.readline


def create_prime_list(limit):
    """ ??¨??????????????????????????§limit?????§????´???°?????????????±???????
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    nums = [x for x in range(2, limit+1)]
    while nums[0] <= x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x % current_prime != 0]
    primes.extend(nums)
    return primes


def main(args):
    primes = create_prime_list(1000000)

    while True:
        n = int(input())
        if n == 0:
            break

        ans = 0                 #  ????????????????????????????????°
        for i in range(n):
            a = primes[i]
            if a > n/2:
                break
            i = bisect_left(primes, n - a)
            if i != len(primes) and primes[i] == n-a:
                ans += 1
        print(ans)



if __name__ == '__main__':
    main(sys.argv[1:])
    

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

int main(){
    int n,m;
    vector<string> img;
    vector<string> tmp;
    int cnt = 0;
    int flag = 0;

    cin >> n >> m;

    for(int i = 0; i < n; i++){
        string str;
        cin >> str;
        img.push_back(str);
    }
    for(int i = 0; i < m; i++){
        string str;
        cin >> str;
        tmp.push_back(str);
    }

    for(int i = 0; i < n - m + 1; i++){
        for(int j = 0; j < n - m + 1; j++){
            for(int k = 0; k < m; k++){
                for(int l = 0; l < m; l++){
                    if(img[i + k][j + l] == tmp[k][l]){
                        cnt++;
                        if(cnt == m * m){
                            flag = 1;
                        }
                    }
                    else{
                        cnt = 0;
                    }
                }
            }
        }
    }

    if(flag == 1){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> as(n);
    for (auto& a : as)
    {
        cin >> a;
    }

    // dp[i] = 石が i 個残っている状況で、先手番が勝てるか
    vector<bool> dp(k + 1, false);
    for (int i = 0; i <= k; i++)
    {
        int move_count = 0;
        bool is_all_true = true;
        for (auto a : as)
        {
            if (a <= i)
            {
                move_count++;
                is_all_true &= dp[i - a];
            }
        }
        dp[i] = (move_count > 0 && !is_all_true);
    }
    cout << (dp[k] ? "First" : "Second") << endl;
}

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

# かぶりなし
if A + K - 1 < B - K + 1:
    for i in range(K):
        print(A + i)
    for i in reversed(range(K)):
        print(B - i)
else:
    for i in range(A, B + 1):
        print(i)

Measured memory_bytes: 38384