akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(ll i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
template<class T>bool maxi(T &a,const T &b){if(a<b){ a=b; return 1;} return 0;}
template<class T>bool mini(T &a,const T &b){if(b<a){ a=b; return 1;} return 0;}
#define y0 y3487465 //j0
#define j1 j1347829 //j1
#define INF2 4000000000000000037
#define INF 1000000007
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;


void Main(){

  int Q; cin>>Q;

  ll sumb=0;
  ll fx=0;
  ll ct1=0;
  priority_queue<ll> st1; //xが小さい方、大きい方から出る
  priority_queue<ll,vector<ll>, greater<ll>> st2; //xが大きい方、小さい方から出る
  ll center;
  ll center1;
  ll center2;
  rep(i,Q){
    int qu; cin>>qu;
    if(qu==1){
      ll a,b; cin>>a>>b;
      sumb+=b;

      if(ct1==0){
        center=a;
        ct1++;
        continue;
      }
      if(ct1%2==0){
        if(a<center1){
          fx+=center1-a;
          center=center1;
          st1.push(a);
          st2.push(center2);
        }
        else if(a>center2){
          fx+=a-center2;
          center=center2;
          st1.push(center1);
          st2.push(a);
        }
        else{
          center=a;
          st1.push(center1);
          st2.push(center2);
        }
      }
      if(ct1%2==1){
        fx+= abs(center-a);
        if(a>=center){
          st2.push(a);
          center1=center;
          center2=st2.top();
          st2.pop();
        }
        else{
          st1.push(a);
          center2=center;
          center1=st1.top();
          st1.pop();
        }
      }
      ct1++;
    }
    else{
      if(ct1%2==0){
        cout<< center1<<" "<< fx+sumb <<"\n";
      }
      else{
        cout<< center<<" "<< fx+sumb <<"\n";
      }
    }
  }

}

//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


Measured memory_bytes: 3828
/*
 * main.c
 *
 *  Created on: 2020/03/28
 *      Author: family
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a > b ? b : a)
typedef long long int ll;
typedef unsigned long long int ull;

int sort_inc(const void *a, const void *b) { return (*(int*)a - *(int*)b);}
int sort_dec(const void* a, const void* b) { return (*(int*)b - *(int*)a);}
int sort_dec_ll(const void *a, const void *b) {
    ll da = *(ll*)a, db = *(ll*)b;    int val = 0;
    if(da > db) { val = -1; }
    else if (da == db) { val = 0; }
    else { val = 1; }
    return val;
}
int sort_inc_ll(const void *a, const void *b) {
    ll da = *(ll*)a, db = *(ll*)b;    int val = 0;
    if(da > db) { val = 1; }
    else if (da == db) { val = 0; }
    else { val = -1; }
    return val;
}
int sort_dic(const void *a, const void *b) {
    char *pa = (char *)a;    char *pb = (char *)b;    int i = 0, val = 0, N = 10;
    for (i = 0; i < N; i++) {
    	char da = pa[i], db = pb[i];
    	if (da == db) continue;
  		if (da > db) val = 1; else val = -1;
        break;
    }
    return val;
}

void yesno(int ans) {
	if (ans == 1) { printf("Yes\n");
	} else { printf("No\n"); }
	return;
}

int main()
{
	int R = 0;
	scanf("%d", &R);
	printf("%.6f\n", 2.0*3.1415926*(double)R);
	return 0;
}


Measured memory_bytes: 1728
from sys import stdin

readline = stdin.readline

n = readline()
aa = map(int, readline().split())
r = 0
mi = 1000000000
m = 0
for a in aa:
    if a < 0:
        m += 1
    b = abs(a)
    r += b
    if b < mi:
        mi = b
print(r - mi * 2 * (m % 2))


Measured memory_bytes: 11396
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
l = [0] * (10 ** 5 + 1)
for i in ab:
    l[i[0]] += i[1]
s = 0
for i in range(10 ** 5 + 1):
    s += l[i]
    if s >= k:
        print(i)
        break


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

#define rep(i, a, b) for(ll i = (a); i < (b); ++i)
#define per(i, a, b) for(ll i = (b)-1; i >= (a); --i)
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pii> vii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);

  ll n, m, k;
  cin >> n >> m >> k;

  vi a(n), b(m);
  rep(i,0,n) cin >> a[i];
  rep(i,0,m) cin >> b[i];

  ll tot = 0;
  ll j = 0;
  while (j<m and tot <= k) {
    if (tot+b[j] <= k) {
      tot += b[j];
      ++j;
    } else break;
  }
  --j;

  ll ans = j+1;
  rep(i,0,n) {
    tot += a[i];
    while (j>=0 and tot>k) {
      tot -= b[j]; 
      --j;
    }
    if (tot<=k) ckmax(ans, i+j+2);
  }

  cout << ans << '\n';
}

Measured memory_bytes: 6364
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	int a,b;
	scanf("%d%d",&a,&b);
	int c;
	scanf("%d",&c);
	vector<int> vi;
	for(int i = 0; i < n; i++){
		int tmp;
		scanf("%d",&tmp);
		vi.push_back(tmp);
	}
	sort(vi.begin(),vi.end());
	reverse(vi.begin(),vi.end());
	int ans = -1000;
	int x = 0;
	for(int i = 0; i < n; i++){
		x += vi[i];
		double tmp = (double)(x+c)/(a+b*(i+1));
		ans = max((int)tmp,ans);
	}
	printf("%d\n",ans);
	return 0;
}

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

int main(){
  int N, Y;
  int x=-1;
  int y=-1;
  int z=-1;
  cin >> N >> Y;
  Y /= 1000;

  for(int i=0; i<=(Y-N)/9; i++){
    if( (Y-N-9*i) % 4 == 0 ){
      if( 5*i+5*N-Y >= 0 ){
      	x = i;
      	y = (Y-N-9*i) / 4;
      	z = N-x-y;
        break;
      }
    }
  }
  
  cout << x << " " << y << " " << z << endl;

  return 0;
}


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

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

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

int main() {
    int N, P;
    string s;
    cin >> N >> P;
    long long ans = 0;
    cin >> s;
    if (10 % P == 0)
    {

        for (int i = 0; i < N; i++)
        {
            if ((s[i] - '0') % P == 0)
            {
                ans += i + 1;
            }
        }
        cout << ans << endl;
        return 0;
    }
    else
    {
        vector<int> d(N);
        vector<int> cnt(P);
        for (int i = 0; i < P; i++)
        {
            cnt[i] = 0;
        }
        int ten = 10;
        d[N - 1] = (s[N - 1] - '0') % P;
        for (int i = N - 2; i >= 0; --i)
        {
            d[i] = ((s[i] - '0') * ten + d[i + 1]) % P;
            ten *= 10;
            ten %= P;
            d[i] = d[i] % P;
        }
        cnt[0]++;
        for (int i = N - 1; i >= 0; i--)
        {
            ans += cnt[d[i]%P];
            cnt[d[i]]++;
        }

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

Measured memory_bytes: 1412
#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;
vector<pair<LLI,LLI>>items;
LLI ar[100001];
int main()
{
    //freopen("C:\\Users\\suman\\Desktop\\input.txt","r",stdin);
    LLI i,j,a,b,c,n,m,t;
        cin>>m>>n;
        LLI ar[m][n+1]={};
        //cout<<ar[2][4];return 0;
        for(i=0;i<m;i++)
        {
            cin>>a>>b;
            items.emplace_back(make_pair(a,b));
        }
        for(j=items[0].first;j<=n;j++)
            ar[0][j]=items[0].second;
        for(i=1;i<m;i++)
        {
            for(j=0;j<items[i].first;j++)
                ar[i][j]=ar[i-1][j];
            for(j=items[i].first;j<=n;j++)
                if(items[i].second+ar[i-1][j-items[i].first]>ar[i-1][j])
                    ar[i][j]=items[i].second+ar[i-1][j-items[i].first];
                else
                    ar[i][j]=ar[i-1][j];
        }
        /*for(i=0;i<m;i++)
        {
            cout<<"\n";
            for(j=0;j<=n;j++)
                cout<<ar[i][j]<<" ";
        }*/
        cout<<ar[m-1][n];
    return 0;
}


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

int main()
{
ll l , r , d ;
cin >> l >> r >> d ;
rep(i,110){
  if(l<=i*d&&i*d<=r)ans++;
}
cout << ans << endl;
return 0;
}

Measured memory_bytes: 3616
import java.util.Scanner;

public class Main {

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

    if(x < a) {
      System.out.println("0");
    } else {
      System.out.println("10");
    }
  }

}


Measured memory_bytes: 23764
#include <iostream>
#define ll long long
const int N=1e4+5;
using namespace std;
ll a[N];
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=0;i<k;i++)
		cin>>a[i];
	ll sum=0;
	for(int i=0;i<k;i++)
		sum+=a[i];
	cout<<(sum>n?-1:n-sum)<<endl;
	return 0;
}

Measured memory_bytes: 3704
#include<iostream>
using namespace std;
int main(void){
  int k,s;
  cin>>k>>s;
  int x,y,z,sum;
  for(x=0;x<=k;x++){
    for(y=0;y<=k;y++){
      z=s-x-y;
      if(z>=0&&z<=k)sum++;
    }
  }
  cout<<sum;
}

Measured memory_bytes: 256
def solve(N,A) :
    ans = 1
    for i in range(N) :
        if(A[i] == 0) :
            print(0)
            return
    for i in range(N) :
        ans = ans * A[i]
        if(ans > 10**18):
            ans = -1
            break
    print(ans)
    
N = int(input())
A = list(map(int, input().split()))
solve(N,A)

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

#define rep(i, m, n) for(int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for(int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

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

struct Edge {
    ll to, rev;
    long double cap;
    Edge(ll _to, long double _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph &G, ll from, ll to, long double cap, bool revFlag,
              long double revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve() {

    vec<pair<int, int>> qs;
    int x;
    int i = 0;
    while(cin >> x) {
        if(x == 0)
            break;
        qs.push_back({x, i});
        i++;
    }
    sort(all(qs));

    int n = 190;
    int m = 1000000;
    int pos = 0;

    vec<int> dp(m + 1, INF_INT), dp2(m + 1, INF_INT);
    dp[0] = 0;
    dp2[0] = 0;
    vec<pair<int, int>> ans(qs.size());

    REP(i, n) {
        vec<int> dp3(m + 1, INF_INT), dp4(m + 1, INF_INT);
        int k = (i + 1) * (i + 2) * (i + 3) / 6;
        REP(j, m + 1) {
            chmin(dp3[j], dp[j]);
            chmin(dp4[j], dp2[j]);
            if(j - k >= 0) {
                chmin(dp3[j], dp3[j - k] + 1);
                if(k % 2) {
                    chmin(dp4[j], dp4[j - k] + 1);
                }
            }
        }
        dp = dp3;
        dp2 = dp4;
        while(pos < qs.size() and k >= qs[pos].first) {
            ans[qs[pos].second] = {dp[qs[pos].first],
                                   dp2[qs[pos].first]};
            pos++;
        }
    }

    for(auto i : ans) {
        cout << i.first << " " << i.second << en;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*
    ll t;
    cin >> t;
    while(t--)*/
    solve();

    return 0;
}



Measured memory_bytes: 18584
#include <bits/stdc++.h>
#define rep(i,n)  for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;

int main(){
    fast_io();
    ll n, m;
    cin >> n >> m;
    ll count = n;
    ll res;
    rep(i,m){
        cin >> res;
        count -= res;
    }
    cout << ((count < 0)? -1 : count);
    return 0;
}


Measured memory_bytes: 3648
import java.util.Scanner;
public class Main{
    public static int min(int a, int b, int c){
        if(a <= b && a <= c)
            return a;
        else if(b <= c)
            return b;
        else
            return c;
    }
    public static int distance(String s1, String s2){
        int data[][] = new int[s1.length()+1][s2.length()+1];
        for(int i = 0 ; i < s1.length()+1 ; i++)
            data[i][0] = i;
        for(int i = 0 ; i < s2.length()+1 ; i++)
            data[0][i] = i;
        for(int i = 1 ; i <= s1.length() ; i++){
            for(int j = 1 ; j <= s2.length() ; j++){
                int c = 1;
                if(s1.charAt(i-1) == s2.charAt(j-1))
                    c--;
                data[i][j] = min(data[i-1][j-1]+c, data[i-1][j]+1, data[i][j-1]+1);
            }
        }
        return data[s1.length()][s2.length()];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
        System.out.println(distance(s1,s2));
    }
}


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

typedef long long ll;

bool table[20000000];

int num(char c){
    if(c=='A')return 1;
    if(c=='C')return 2;
    if(c=='G')return 3;
    if(c=='T')return 4;
}


ll hs(string str){
    ll n=0;
    for(int i=0;i<str.size();i++){
        if(i)n*=5;
        n+=num(str[i]);
    }
//    cout << str << " : " << n << endl;
    return n;
}

void inpt(ll key){
    table[key] = true;
}

bool find(ll key){
    return table[key];

}

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

    int n;
    cin >> n;
    string str,in;
    for(int i=0;i<n;i++){
        cin >> str >> in;
        if(str=="insert"){
            inpt(hs(in));
        }else{
            if(find(hs(in))) cout << "yes\n";
            else cout << "no\n";
        }
    }

}



Measured memory_bytes: 8436
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
using ll = long long;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
const ll INF = 1e17;

ll Pow(ll x, ll n){
  if(x == 0) return 0;
  if(n == 0) return 1;
  if(n % 2 == 0) return Pow(x*x % mod, n/2);
  else return x * Pow(x,n-1) % mod;
}

ll mod_inverse(ll a) {
  return Pow(a,mod-2);
}

int main(){
  ll n, k;
  cin >> n >> k;
  ll ans = 1;
  ll a[n];
  P b[n];
  rep(i,n) {
    cin >> a[i];
    if(a[i] >= 0) b[i] = P(a[i],1);
    else b[i] = P(-a[i],-1);
  }
  sort(b,b+n,greater<P>());
  int sign = 1;
  ll minus = INF;
  ll plus = INF;
  rep(i,k) {
    (ans *= b[i].first) %= mod;
    sign *= b[i].second;
    if(b[i].second < 0) minus = min(minus,b[i].first);
    if(b[i].second > 0) plus = min(plus,b[i].first);
  }
  if(sign < 0) {
    ll c = -INF;
    ll d = -INF;
    for(int i = k; i < n; i++) {
      if(b[i].second > 0) c = max(c,b[i].first);
      else d = max(d,b[i].first);
    }
    if(plus != INF and d >= 0 and c >= 0) {
      if(d*minus >= c*plus) {
        (ans *= mod_inverse(plus)) %= mod;
        (ans *= d) %= mod;
      } else {
        (ans *= mod_inverse(minus)) %= mod;
        (ans *= c) %= mod;
      }
    } else if(plus == INF or d < 0) {
      if(c >= 0) {
        (ans *= mod_inverse(minus)) %= mod;
        (ans *= c) %= mod;
      } else {
        ans = -1;
        for(int i = n-1; i >= n-k; i--) (ans *= b[i].first) %= mod;
      }
    } else {
      (ans *= mod_inverse(plus)) %= mod;
      (ans *= d) %= mod;
    }
  }
  if(ans < 0) ans += mod;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 8308
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

ll x,y;

void solve(){
    cin >> x >> y;
    ll ans=0;
    if (abs(x)>abs(y) && x>=0) {
        ans+=1+abs(x)-abs(y);
        x*=-1;
    }
    else if (abs(x)>abs(y) && x<0) {
        ans+=abs(x)-abs(y);
    }
    else if (abs(x)<abs(y) && x>=0) {
        ans+=abs(y)-abs(x);
    }
    else if (abs(x)<abs(y) && x<0) {
        ans+=1+abs(y)-abs(x);
        x*=-1;
    }
    
    if((x+1)*y<0) ans+=1;
    cout << ans << endl; 

}

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

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1e9+7;
#define N 505
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,m,cnt[N],ans,fac[N],inv[N];
int dp[N][N][N]; // 区间长度到i，区间个数j，区间长度和 k。 
inline int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return ans;
}
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i){
		fac[i]=1LL*fac[i-1]*i%mod;
	}
	inv[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=0;--i){
		inv[i]=1LL*inv[i+1]*(i+1)%mod;
	}
}
inline int C(int n,int m){
	return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		++cnt[read()];
	}
	init(m);
	dp[m+1][0][0]=1;
	for(int i=m;i>=1;--i){
		for(int k=0;k<=m;++k){
			for(int j=0;j<=m/i;++j){
				if(!dp[i+1][j][k])continue;
				int lim=min((m-k)/i,m-j);
				for(int p=0;p<=lim;++p){
					dp[i][j+p][k+p*i]=(dp[i][j+p][k+p*i]+1LL*dp[i+1][j][k]*inv[p])%mod;
				}
			}
		}
		for(int j=0;j<=m;++j){
			for(int k=j*(i-1);k<=m;++k){
				dp[i][j][k]=1LL*dp[i][j][k]*qpow(k-j*(i-1),cnt[i])%mod;
			}
		}
	}
	for(int j=0;j<=m;++j){
		for(int k=0;k<=m;++k){
			ans=(ans+1LL*fac[j]*dp[1][j][k]%mod*C(m-k+1,j)*((m-k)&1?-1:1))%mod;
		}
	}
	printf("%d\n",(ans+mod)%mod);
	return 0;
}



Measured memory_bytes: 14004
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#include<random>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define Endl endl
#define NL <<"\n"

using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
//#undef NUIP
#ifdef NUIP
#include "benri.h"
#else
#define out(args...)
#endif
#ifdef __cpp_init_captures
template<typename T>vector<T> table(int n, T v){ return vector<T>(n, v);}
template <class... Args> auto table(int n, Args... args){auto val = table(args...); return vector<decltype(val)>(n, move(val));}
#endif
const ll MOD=1e9+7; //998244353

mt19937 mt(1727273);

string encode(vector<int> vs){
	string re(30*vs.size(),'0');
	rep(i,vs.size())rep(d,30)if(vs[i]>>d&1) ++re[i*30+29-d];
	return re;
}
vector<int> decode(string s){
	vector<int> re;
	rep(i,s.size()){
		if(i%30==0) re.eb();
		re.back()*=2;
		if(s[i]=='1') ++re.back();
	}
	return re;
}

const int n=100;
const int m=1000;
vector<int> hs;
int get(const string &s){
	int re=0;
	rep(j,m)if(s[j]=='1') re^=hs[j];
	return re;
}

void AB(){
	vector<string> vs(n);
	for(auto &v:vs) cin>>v;
	vector<int> re(n);
	rep(i,n) re[i]=get(vs[i]);
	cout<<encode(re) NL;
}

void C(){
	vector<int> as,bs;
	{
		string a,b;
		cin>>a>>b;
		as=decode(a);
		bs=decode(b);
	}
	map<int,pii> re;
	rep(i,100)rep(j,100) re[as[i]^bs[j]]=pii(i,j);
	rep(_,100){
		string s;
		cin>>s;
		int h=get(s);
		int a,b;
		tie(a,b)=re[h];
		cout<<a+1<<" "<<b+1 NL;
		// int act=a^b;
		// int exp=(_/10)^(_%10);
		// out(exp,act,1);
	}
}

int main(){
	hs.resize(m);
	rep(i,m) hs[i]=mt()&((1<<30)-1);
	if(0){
		rep(_,10){
			const int n=mt()%100+2;
			vector<int> a(n);
			rep(i,n) a[i]=mt()&((1<<30)-1);
			assert(a==decode(encode(a)));
		}
		return 0;
	}
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout<<fixed<<setprecision(0);
	string s;
	cin>>s;
	if(s[0]=='C') C();
	else AB();
  return 0;
}



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

#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 ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;


int main() {
    double A,B,H,M; cin>>A>>B>>H>>M;
    double theta = abs(30*H+-5.5*M);
    if (theta > 180){
        theta = 360 - theta;
    }
    double ans = sqrt(A*A + B*B - 2*A*B*cos(theta*M_PI/180));

    cout << fixed << setprecision(20) << ans << endl;

    return 0;
}

Measured memory_bytes: 4212
s=input()
N=len(s)
kyonen=2019
ans=0

#alistつくる
alist=[]
for i in reversed(range(N)):
    alist.append((int(s[i])*pow(10,(N-1-i),kyonen))%kyonen)

#累積和とる
ruisekiwa=[0]
for i in range(N):
    ruisekiwa.append((ruisekiwa[-1]+alist[i])%kyonen)

#累積和リストの中から、同じ数字の組み合わせの個数を求める
kazoe=[0]*2019
for i in range(N+1):
    kazoe[ruisekiwa[i]]+=1

for i in range(2019):
    if kazoe[i]>=2:
        ans+=int(kazoe[i]*(kazoe[i]-1)/2)

if ruisekiwa[N]==0:
    ans+=1

print(ans)

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

int main()
{
	int N,Y,x,y,z;
	
	cin>>N>>Y;
	
	for(x=0;x<=Y/10000;x++)
		for(y=0;y<=Y/5000;y++)
		{
			z=N-x-y;
			if(z>=0&&x*10000+y*5000+z*1000==Y)
			{
				cout<<x<<" "<<y<<" "<<z;
				return 0;
			}
		}
	
	cout<<"-1 -1 -1";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define mp make_pair
const ll inf=1e9+2;
int32_t main()
{
	IOS
	ll n,i,j,k;
	cin>>n>>k;
	vector<ll>v(n),dp(n,inf);
	for(auto &x:v)
		cin>>x;
	dp[0]=0;
	dp[1]=abs(v[1]-v[0]);
	for(i=2;i<n;i++)
	{
		for(j=i-k>0?i-k:0;j<i;j++)
		{
			dp[i]=min(dp[i],dp[j]+abs(v[i]-v[j]));
		}
    
	}
	cout<<dp[n-1];
}

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int Q;
long a,b,c,d;
long T[31];
main()
{
	cin>>Q;
	T[0]=1;
	for(int i=1;i<=30;i++)T[i]=T[i-1]*3;
	for(;Q--;)
	{
		cin>>a>>b>>c>>d;
		a--,b--,c--,d--;
		if(a>c)swap(a,c);
		if(b>d)swap(b,d);
		long ans=c-a+d-b;
		long plus=0;
		for(int i=30;i>=1;i--)
		{
			if(a/T[i-1]==c/T[i-1]&&a/T[i-1]%3==1)
			{
				long B=b/T[i-1],D=d/T[i-1];
				if(B>D)swap(B,D);
				if(B+2<=D)
				{
					a%=T[i];
					c%=T[i];
					plus=min(min(a,c)+1-T[i-1],2*T[i-1]-max(a,c));
					break;
				}
			}
			if(b/T[i-1]==d/T[i-1]&&b/T[i-1]%3==1)
			{
				long A=a/T[i-1],C=c/T[i-1];
				if(A>C)swap(A,C);
				if(A+2<=C)
				{
					b%=T[i];
					d%=T[i];
					plus=min(min(b,d)+1-T[i-1],2*T[i-1]-max(b,d));
					break;
				}
			}
		}
		cout<<ans+plus*2<<endl;
	}
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin>>S;
  if(S[0]==S[1]||S[1]==S[2]||S[2]==S[3]){
    cout<<"Bad"<<endl;
  }
  else{
    cout<<"Good"<<endl;
  }
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
// Welcome to my source code!

int main() {
    int n;
    cin >> n;
    int digits[10][10] = {};
    for (int i = 1; i <= n; i++) {
        int t = i, cnt = 1;
        while (t / 10) t /= 10, cnt++;
        if (cnt == 1) digits[t][t]++;
        else digits[t][i%10]++;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int t = i, cnt = 1;
        while (t / 10) t /= 10, cnt++;
        if (cnt == 1) ans += digits[t][t];
        else ans += digits[i%10][t];
    }
    cout << ans << endl;
}

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

#define pu push_back
#define fi first
#define se second
#define mp make_pair
// #define int long long
#define pii pair<int,int>
#define mm (s+e)/2
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(int i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define sz 200000
int xa[4]={0,0,1,-1};
int ya[4]={1,-1,0,0};
int n,m,k;
int check(int x,int  y)
{
	if(x>=0 && y>=0 && x<n && y<m) return 1;
	else return 0;
}
signed main()
{
	
		fast
		cin>>n>>m>>k;
int a,b,c,d;
		cin>>a>>b>>c>>d;
		int vis[n+2][m+2][4];
		int dist[n+2][m+2][4];
		int op[n+2][m+2][4];
   int B[n+2][m+2];
   memset(vis,0,sizeof(vis));
   memset(B,0,sizeof(B));
   memset(op,0,sizeof(op));
   // cout<<"kk";
		multimap<pii,pair<int,pii> > ss;
		// cout<<"kk";
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{      char aa;
				cin>>aa;
                 if(aa=='.') B[i][j]=1;

                 for(int r=0;r<4;r++)
                 {
                 	dist[i][j][r]=1000000000;
                 }
			}
		}	
// cout<<"kk";
		a--;
		b--;
		c--;
		d--;
		// cout<<"io";
		ss.insert(mp(mp(1,-k),mp(0,mp(a,b))));
		ss.insert(mp(mp(1,-k),mp(1,mp(a,b))));
		ss.insert(mp(mp(1,-k),mp(2,mp(a,b))));
		ss.insert(mp(mp(1,-k),mp(3,mp(a,b))));
		// cout<<"ll";
		for(int r=0;r<4;r++)
                 {
                 	dist[a][b][r]=0;
                 	op[a][b][r]=k;
                 }
                 // cout<<"kk";
		while(ss.size()>0)
		{

			auto yy=*ss.begin();
			int val=yy.fi.fi;
			int cn=-yy.fi.se;
			int x=yy.se.se.fi;
			int y=yy.se.se.se;
			
			int dir=yy.se.fi;
			//cout<<x<<" "<<y<<" " <<dir<<" "<<cn<<" "<<val<<endl;
			ss.erase(ss.begin());
			if(vis[x][y][dir]==1) continue;
			vis[x][y][dir]=1;
			for(int i=0;i<4;i++)
			{
				int aa=x+xa[i];
				int bb=y+ya[i];
				//cout<<aa<<" "<<bb<<" "<<check(aa,bb)<<endl;
				if(check(aa,bb)==1 && B[aa][bb]==1 )
				{  // cout<<aa<<" "<<bb<<endl;
					 int u;
					int vl;
					if(i==dir && cn>0)
					{
                         u=cn-1;
                         vl=val;
					}else 
					{vl=val+1;  u=k-1;}
					if(dist[aa][bb][i]>vl ||(dist[aa][bb][i]==vl &&op[aa][bb][i]<u))
					{
						dist[aa][bb][i]=vl;
						op[aa][bb][i]=u;
						ss.insert(mp(mp(vl,-u),mp(i,mp(aa,bb))));
					}
				}
			}
		}

			int ans=1000000000;
			for(int r=0;r<4;r++)
                 {
                 	ans=min(ans,dist[c][d][r]);
                 }
                 if(ans>=100000000) cout<<-1<<endl;
                 else cout<<ans<<endl;


		

}

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

char f[103][103];

void dfs(int x, int y, int h, int w) {
	char fruit = f[x][y];
	f[x][y] = '0';

	for (int i = -1;i <= 1;i += 2) {
		int ax = x + i;
		if (0 <= ax&&ax < h&&f[ax][y] == fruit) { dfs(ax, y, h, w); }
	}

	for (int j = -1;j <= 1;j += 2) {
		int ay = y + j;
		if (0 <= ay&&ay < w&&f[x][ay] == fruit) { dfs(x, ay, h, w); }
	}
	return;
}

int main() {
	int h, w;
	while (cin >> h >> w, h, w) {
		for (int i = 0;i < h;i++) {
			for (int j = 0; j< w;j++) {
				cin >> f[i][j];
			}
		}
		int co = 0;
		for (int i = 0;i < h;i++) {
			for (int j = 0;j < w;j++) {
				if (f[i][j] != '0') {
					dfs(i, j, h, w);
					co++;
				}
			}
		}
		cout << co << endl;
	}
	return 0;
}

Measured memory_bytes: 3848
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define MOD 998244353

using namespace std;
using ll = long long;

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> room[n];
	rep(i,m) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		room[a].push_back(b);
		room[b].push_back(a);
	}
	vector<int> yudo(n,-1);
	queue<int> q;
	q.push(0);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i : room[now]) {
			if (yudo[i] == -1) {
				yudo[i] = now;
				q.push(i);
			}
		}
	}
	cout << "Yes" << endl;
	for (int i = 1; i < n; i++) {
		int ans = yudo[i] + 1;
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 10156
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
typedef long long ll;
typedef pair<int, int> P;
 
int main(){
  int n; cin >> n;
  string s; cin >> s;
  ll r=0;
  ll g=0;
  ll b=0;
  rep(i, n){
    if(s[i]=='R') r++;
    else if(s[i]=='G') g++;
    else b++;
  }
  ll mu = r*g*b;
  int a, ba, c;
  for(int i=0; i<n; i++){
    for(int j=1; i+j*2<n; j++){
      a = i;
      ba = i+j;
      c = i+j*2;
      if(s[a]!=s[ba] && s[a]!=s[c] && s[ba]!=s[c]) mu--;
    }
  }
  cout << mu << endl;
  return 0;
}

Measured memory_bytes: 3608
import java.util.*;
public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int K = sc.nextInt();


    ArrayList<Integer>onaji = new ArrayList<>();
    int cou = 0;    
    int max = Math.max(A,B); 
    for(int i=1; i<=max; i++){
        if(A%i==0 && B%i==0){
        onaji.add(i);
}
}
    Collections.sort(onaji, Collections.reverseOrder());
        System.out.println(onaji.get(K-1));
 }
}

Measured memory_bytes: 35880
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<deque>
#include<map>
using namespace std;
typedef long long ll;

int main() {
    int n; cin >> n;
    vector<pair<int, int>> a;
    for (int i = 0; i < n; i++)
    {
        int b; cin >> b;
        a.emplace_back(b, i+1);
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++)
    {
        printf("%d%c", a[i].second, (i==(n-1)? '\n' : ' '));
    }
    
    return 0;
}

Measured memory_bytes: 1780
#include<stdio.h>
int main()
{
 int s;
 int m;
 int h;
 scanf("%d",&s);
 h=s/3600;
 m=s%3600/60;
 s=s-(h*3600+m*60);
 printf("%d:%d:%d\n",h,m,s);
return 0;
}

Measured memory_bytes: 592
import java.util.Scanner;

public class Main {

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

		long x = scanner.nextLong();

		long max500 = x/500;
		long result = 0;
		for(long i = 0; i <= max500; i++){
			long current5 = (x-500*i)/5;
			result = Math.max(result, i*1000+current5*5);
		}

		System.out.println(result);
		scanner.close();
	}

}


Measured memory_bytes: 21716
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <assert.h>
#include <numeric>
#include <time.h>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < n; i++)
#define all(c) (c).begin(), (c).end()
#define P pair<int, int>
#define chmin(x, y) x = min(x, y)

int main()
{
  string s;
  cin >> s;
  reverse(all(s));
  s += '0';

  int n = s.size();

  const int INF = 100100100;
  vector<vector<int>> dp(n + 1, vector<int>(2, INF));
  dp[0][0] = 0;

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < 2; j++)
    {
      int x = s[i] - '0';
      x += j;
      if (x < 10)
        chmin(dp[i + 1][0], dp[i][j] + x);
      if (x > 0)
        chmin(dp[i + 1][1], dp[i][j] + (10 - x));
    }
  }

  cout << dp[n][0] << endl;
}


Measured memory_bytes: 55940
N = int(input())
A_list = [int(elm) -1 for elm in input().split(" ")]
B_list = list(map(int, input().split(" ")))
C_list = list(map(int, input().split(" ")))

out = 0
for i in range(N):
    now = A_list[i]
    out += B_list[now]
    if i >= 1:
        if before +1 == now:
            out += C_list[before]

    before = now

print(out)

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

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

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

	sort(A.begin(), A.end());
	sort(B.begin(), B.end());

	int output;
	if (N % 2 == 0) {
		output = B[N / 2 - 1] + B[N / 2] - A[N / 2 - 1] - A[N / 2] + 1;
	} else {
		output = B[N / 2] - A[N / 2] + 1;
	}

	//output
	cout << output << endl;


	return 0;
}


Measured memory_bytes: 4844
n,time=map(int,input().split())

min=1000
c = []
t = []
flag=1
for i in range(n):
    c1,t1=[int(i) for i in input().split()]
    c.append(c1)
    t.append(t1)

for i in range(n):
  if (t[i]<=time) and (c[i]<=min):
    min=c[i]
    flag=0

if flag==0:
  print(min)
else:
  print("TLE")


Measured memory_bytes: 3064
N = int(input())
A = list(map(int,input().split(' ')))

'''考え方

特定の配置なら、全部の数字を足せる。
そうでないなら、一番絶対値が小さい値だけ排除、となりそう。

・どこにいようと、0がいたら全ての値を合計できる。


・手順
負の値について、奇数個ブロックが2個あれば消滅できる。
奇数個ブロックが奇数個しかないときは、絶対値が一番小さい値を除外する。
'''


min_abs = 1000000000000
cnt_in_block = 0
cnt_blocks = 0
sum_all = 0


for i,a in enumerate(A):
  # 負の値
  if a < 0:
    cnt_in_block += 1
  
  # 正の値
  else:
    # 切り替わり直後
    if i > 0 and A[i-1] < 0:
      if cnt_in_block % 2 != 0:
        cnt_blocks += 1
    
      # reset
      cnt_in_block = 0
    
  tmp = abs(a)
  if min_abs > tmp:
    min_abs = tmp
  sum_all += abs(a)
  
  # 一番最後が負の値の場合、ブロック数として計算する
  if N -1 == i and cnt_in_block > 0:
    if cnt_in_block % 2 != 0:
      cnt_blocks += 1

  
if cnt_blocks % 2 == 1:
  out = sum_all - 2*min_abs
else:
  out = sum_all
  
print(out)

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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

long long int fac[1000001]; 

/* Iterative Function to calculate (x^y)%p  
in O(log y) */
long long int power(long long int x, 
                         long long int y, long long int p) 
{ 
    long long int res = 1; // Initialize result 
  
    x = x % p; // Update x if it is more than or 
    // equal to p 
  
    while (y > 0) { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res * x) % p; 
  
        // y must be even now 
        y = y >> 1; // y = y/2 
        x = (x * x) % p; 
    } 
    return res; 
} 
  
// Returns n^(-1) mod p 
long long int modInverse(long long int n, long long int p) 
{ 
    return power(n, p - 2, p); 
} 
  
// Returns nCr % p using Fermat's little 
// theorem. 
long long int nCrModPFermat(long long int n, 
                                 long long int r, long long int p) 
{ 
    // Base case 
    if (r == 0) 
        return 1; 
  
    // Fill factorial array so that we 
    // can find all factorial of r, n 
    // and n-r 
  
    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; 
} 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long int M=1e9+7;
    fac[0]=1;
    for (int i=1;i<1000001;i++) fac[i]=(fac[i-1]*i)%M;
    int n;
    cin>>n;
    if(n==1) cout<<0<<"\n";
    else{
        long long int ans1=1;
        for (int i=0;i<n;i++){
            ans1*=10;
            ans1%=M;
        }
        long long int ans2=1;
        for (int i=0;i<n;i++){
            ans2*=9;
            ans2%=M;
        }
        long long int ans3=1;
        for (int i=0;i<n;i++){
            ans3*=8;
            ans3%=M;
        }
        cout<<((ans1-ans2-ans2+ans3)%M+M)%M<<"\n";
    }
	return 0;
}

Measured memory_bytes: 11424
require 'matrix'

N = gets.to_i
MOD = 10 ** 9 + 7

(puts 0; exit) if N < 3

m = Matrix[[1, 0, 1], [1, 0, 0], [0, 1, 0]]

puts ((m**(N-3)) * Matrix[[1], [0], [0]])[0, 0] % MOD


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

int main() {
	string s;
	cin >> s;
	int l = s.size();
	s += "AB"; // 番兵
	for (int i = 0;i < l;i ++) {
		if (s[i] == s[i + 1]) {
			cout << i + 1 << " " << i + 2;
			return 0;
		} else if (s[i] == s[i + 2]) {
			cout << i + 1 << " " << i + 3;
			return 0;
		}
	}
	cout << "-1 -1";
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

AA、ABA以外の答えはあり得ない
これが存在しないなら少なくとも同じ文字は2マス以上離れてる、過半数になりえない
O(|s|)

*/

Measured memory_bytes: 512
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
#define MOD 1000000007
#define INF 1000000000
#define mp make_pair
#define pb push_back
#define ss second
#define ff first
#define endl '\n'
#define pl cout<<endl;
void fast() { ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); }
const long long INFll=1ll*INF*INF;
const long double PI=3.141592653589793238462643383279502884197169399375105820974944;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define debug(x) cout << x << endl;
#define sz(a) int((a).size())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
long long genrand(long long L,long long R)
{
	return uniform_int_distribution<long long>(L, R)(rng);
}
//use brackets before operations if taking MOD
//use map only when necessary
//give long long to arrays and variables properly
int mul(int a, int b,int mod = MOD) {
	return int(a * 1ll * b % mod);
}
int norm(int a,int mod = MOD) {
	while(a >= mod) a -= mod;
	while(a < 0) a += mod;
	//a = (a%mod+mod)%mod;
	return a;
}
int powmod(int x,int y,int mod = MOD){
	int res = 1;
	while(y>0)
	{
		if(y&1)
			res = mul(res,x,mod);
		x = mul(x,x,mod);
		y=y>>1;
	}
	return res;
}
int inv(int a,int mod = MOD) {
	return powmod(a, mod - 2);
}
int main() {

	fast();

	int a, b, c; cin>>a>>b>>c;
	cout<<c<<' '<<a<<' '<<b<<endl;
	return 0;
}

Measured memory_bytes: 256
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N, A, B = ILI()
    h = [II() for __ in range(N)]
    return (N, A, B, h)


def bool_exc(h, dif_ab, B, count):
    dif_count = 0
    for mon in h:
        dif_mon = mon - B * count
        if dif_mon <= 0:
            continue
        else:
            dif_count += math.ceil(dif_mon / dif_ab)
            if dif_count > count:
                break

    dif = count - dif_count
    return dif


def solve(N, A, B, h):
    right = max(h) // B + 1
    left = min(h) // A + 1
    dif_ab = A - B
    while left != right:
        mid = (left + right) // 2
        dif = bool_exc(h, dif_ab, B, mid)
        if dif >= 0:
            right = mid
        else:
            left = mid + 1

    ans = left
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()


Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
long long N, X, ans;
int main()
{
	scanf("%lld %lld", &N, &X);
	ans += X;
	ans+= N-X;
	long long L= max(X, N-X);
	long long W = min(X, N-X);
	while(true)
	{
		if(L%W==0)
		{
			ans+= W*(L/W *2 -1);
			break;
		}
		else
		{
			ans+= (L/W*2) * W;
			long long newL = W;
			long long newW = L%W;
			W = newW;
			L = newL;
		}
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 256
n = int(input())
p = []

for i in range(n):
    p.append(int(input()))

p.sort()

ans = sum(p)
if ans%10==0:
    for i in p:
        if i%10!=0:
            ans -= i
            break
    if ans%10==0:
        print(0)
    else:
        print(ans)
else:
    print(ans)


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

#define MP make_pair
#define FF first
#define SS second
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pie;
const int MOD = 1e9 + 7;
const int INF = 2e9;
const ll LINF = 1e18;
const ll delta = 96181;

ll a, b, c, k;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> a >> b >> c >> k;
	cout << (k % 2 ? b - a : a - b) << endl;
}



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

int kaisuu(int K,int n){ //2の何乗か数える関数
    int count=-1;
    while(1){
        if(K<=n){
            count++;
            break;
        }
        n*=2;
        count++;
    }
    return count;
}

long double kaijou(int n){
    double sum=1;
    for(int i=0;i<n;i++){
        sum/=2;
    }
    return sum;
}


int main(){
    int N,K;
    cin>>N>>K;
    long double sum=0;
    for(int i=1;i<=N;i++){
        int n=kaisuu(K,i);
        sum+=kaijou(n)/N;
    }
    
    cout<<setprecision(20)<<sum<<endl;
}

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

using namespace std;

int main(){
	int N, M;
	while(cin >> N >> M){
		vector<vector<int>> adj(N, vector<int>(N, 0));
		for(int i=0;i<M;i++){
			int a, b; cin >> a >> b;
			--a; --b;
			adj[a][b] = adj[b][a] = 1;
		}
		vector<vector<int>> g(N);
		for(int i=0;i<N;i++){
			for(int j=i+1;j<N;j++){
				if(adj[i][j]) continue;
				g[i].push_back(j);
				g[j].push_back(i);
			}
		}
		vector<vector<int>> dp(2, vector<int>(N+1, 0));
		dp[0][0] = 1;
		vector<int> team(N, -1);
		bool valid = true;
		for(int i=0;i<N;i++){
			if(team[i] != -1) continue;
			vector<int> cnt(2, 0);
			team[i] = 0;
			++cnt[0];
			queue<int> qu; qu.push(i);
			while(!qu.empty()){
				int p = qu.front(); qu.pop();
				for(int t : g[p]){
					if(team[t] == team[p]) valid = false;
					if(team[t] != -1) continue;
					team[t] = 1 - team[p];
					cnt[team[t]]++;
					qu.push(t);
				}
			}
			if(!valid) break;
			fill(dp[1].begin(), dp[1].end(), 0);
			for(int j=0;j<=N;j++){
				if(dp[0][j]) dp[1][j+cnt[0]] = dp[1][j+cnt[1]] = 1;
			}
			dp[0] = dp[1];
		}
		if(!valid){
			cout << -1 << endl;
			continue;
		}
		int res = M;
		for(int i=1;i<N;i++){
			if(!dp[1][i]) continue;
			res = min(res, i*(i-1)/2 + (N-i)*(N-i-1)/2);
		}
		cout << res << endl;
	}
}


Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

int main() {
	int N, L;
	cin >> N >> L;
	
	int sum = 0, mn = INF, mnv;
	REP(i, N) {
		int cur = L + i;
		if (chmin(mn, abs(cur))) mnv = cur;
		sum += cur;
	}
	sum -= mnv;
	
	cout << sum << endl;
	return 0;
}


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

using namespace std;

const long long INF = (1ll << 60);

bool many(long long m, long long K, vector<long long>&A){
  int N = A.size();
  for(int i = 0; i < N; i++){
    if(A[i] >= 0){
      int ok = i, ng = N;
      while(ng - ok > 1){
        int mid = (ok + ng) / 2;
        (A[i] * A[mid] <= m ? ok : ng) = mid;
      }
      K -= ok - i;
    }else{
      int ok = N, ng = i;
      while(ok - ng > 1){
        int mid = (ok + ng) / 2;
        (A[i] * A[mid] <= m ? ok : ng) = mid;
      }
      K -= N - ok;
    }
  }
  
  return K <= 0;
}

int main(){
  int N;
  long long K;
  cin >> N >> K;
  
  vector<long long> A(N);
  for(int i = 0; i < N; i++) cin >> A[i];
  sort(A.begin(), A.end());
  
  long long ok = INF, ng = -INF;
  while(ok - ng > 1){
    long long mid = (ok + ng) / 2;
    (many(mid, K, A) ? ok : ng) = mid;
  }
  
  cout << ok << endl;
  
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

int main() {
  ll n;
  cin >> n;
  vl a(n);
  bool b=true;
  rep(i,n){
    cin >> a[i];
  }
  sort(a.begin(),a.end());
  if(a[n-1]-a[0]>=2){
    b=false;
  }
  else if(a[n-1]>=n){
    b=false;
  }
  else if(a[n-1]==a[0]){
    if(n<2*a[0]&&n!=a[0]+1){
      b=false;
    }
  }
  else{
    ll x=0;
    rep(i,n){
      if(a[n-1]==a[i]){
        x++;
      }
    }
    if(a[0]==a[a[0]]){
      b=false;
    }
    if(a[n-1]!=a[n-2]){
      b=false;
    }
    if(x/2+(n-x)<a[n-1]){
      b=false;
    }
  }
  if(b){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 1024
n,m=map(int,input().split())
a=[]
for i in range(n):
	a.append(i)
for i in range(m):
	e=int(input())
	a[e-1]=-i-1
b=[]
for i in range(n):
	b.append([a[i],i+1])
b.sort()
for i in range(n):
	print(b[i][1])


Measured memory_bytes: 38040