akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip> 
//#include <bits/stdc++.h>
using namespace std;
double pi=3.14159265358979323846264338;

const int dx[4]={0,-1,1,0};
const int dy[4]={-1,0,0,1};
int ty[4];
int tx[4];
bool ok[4];
long long ans,ans2,ind,ind2;
int n,m;
const int ad='A'-'a';
bool issqt(int k){
	if(k==1)return true;
	int s=(int)(sqrt(k)+0.00001);
	if(s*s==k)return true;
	return false;
}
string s;

int arr[61];

int cnt;
void dfs(int cur){
	for(int i=0;i<n;i++){
		if(arr[i]==0){
			arr[i]=cur;
			
			dfs(cur+1);
			arr[i]=0;
			return;
		}
		if(issqt(arr[i]+cur)){
			int l=arr[i];
			arr[i]=cur;
			
			
			dfs(cur+1);
			arr[i]=l;
		}
	}
	cnt=max(cnt,cur-1);
	return;
}
int main() {
	int n;
	cin>>n;
	int cnt=0;
	for(int i=1;i<=n;i++){
		int t;
		cin>>t;
		if(i%2==1&&t%2==1)cnt++;
	}
	cout<<cnt<<endl;
  return 0;
}




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

typedef long long ll;

int main()
{
	int k;
	cin>>k;
	ll num=0;
	queue<ll> q;
	for(int i = 0; i < 9; i++)
	{
		q.push(i+1);
	}
	// k-=9;
	int it=1;
	while(it<=k)
	{
		ll f=q.front();
		// cout<<f<<endl;
		q.pop();
		if(f%10!=0)
		{
			q.push(10*f+(f%10)-1);
		}
		q.push(10*f+(f%10));
		if(f%10!=9)
		{
			q.push(10*f+(f%10)+1);
		}
		// k--; 
		it++;
		if(it==k+1)
		{
			num=f;
		}
	}
	if(k<10) cout<<k<<endl;
	else cout<<num<<endl;

}

Measured memory_bytes: 1792
private fun readInts() = readLine()!!.split(" ").map { it.toInt() }.toList()

fun main(args: Array<String>) {
    val a = readLine()!!.toInt()
    val b = readLine()!!.toInt()
    val h = readLine()!!.toInt()

    println((a + b) * h / 2)
}

Measured memory_bytes: 31776
#include<stdio.h>

int main(){
	
	int n,i,j,k,z;
	
	scanf("%d",&n);
	
	int c[n][3],s[200]={};
	
	for(i=0;i<n;i++){
		scanf("%d %d %d" ,&c[i][0] ,&c[i][1] ,&c[i][2]);
	}
	
	for(i=0;i<3;i++){
		for(j=0;j<n;j++){
			
			z=0;
			
			for(k=0;k<n;k++){
				if(j!=k && c[j][i]!=c[k][i]){
					z++;
				}
			}
			
			if(z==n-1){
				s[j]+=c[j][i];
			}
			
		}
		
	}
	
	for(i=0;i<n;i++){
		printf("%d\n",s[i]);
	}
	
return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define ALL(A) (A).begin(),(A).end()
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)

const ll mod = 1e9+7;
const ll INF = 2*1e18;
const int inf = 1e9+7;

using namespace std;

bool isPrime(ll x){
	if(x<2)return 0;
	for(ll i = 2;i*i<=x;i++){
		if(x%i==0)return 0;
	}
	return 1;
}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a,b;
	cin >> a >> b;
	set<ll> st;
	vector<ll> v;
	for(ll i = 1;i*i<=a;i++){
		if(a%i==0){
			st.insert(i);
			st.insert(a/i);
		}
	}
	for(ll i=1;i*i<=b;i++){
		if(b%i==0){
			if(st.find(i)!=st.end()){
				v.push_back(i);
			}
			if(st.find(b/i)!=st.end()){
				v.push_back(b/i);
			}
		}
	}
	ll cnt = 1;
	for(auto x:v){
		if(isPrime(x))cnt++;
	}
	cout << cnt << endl;
}

Measured memory_bytes: 640
import java.util.Scanner;
import java.util.ArrayList;
class Main{
    public static void main(String[] args){
        Scanner scn=new Scanner(System.in);
        int s=scn.nextInt();
        ArrayList<Integer> element=new ArrayList<Integer>();
        for(int i=1;;){
            if(i==1){
                element.add(s);
            }else{
                if(s%2==1){
                    s=odd(s);
                }else{
                    s=even(s);
                }
                if(element.indexOf(s)==-1){
                    element.add(s);
                }else{
                    System.out.println(i);
                    break;
                }
            }
            i++;
        }
    }
    public static int even(int n){
        return n/2;
    }
    public static int odd(int n){
        return 3*n+1;
    }
}


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

using namespace std;

namespace clib {
// 任意の整数型で動くテンプレート版のabs
template <class T>
constexpr auto abs(T i) -> std::enable_if_t<std::is_integral<T>{}(), T> {
    return i < T(0) ? -i : i;
}
}  // namespace clib

// 二つの実引数が整数型であるかどうかを確認し、また共通の型を返すメタ関数common_int_t
template <class M, class N = M>
using common_int_t = std::enable_if_t<std::is_integral<M>{}() and std::is_integral<N>{}(), std::common_type_t<M, N>>;

// 最大公約数
template <class M, class N>
constexpr auto gcd(M m, N n) -> common_int_t<M, N> {
    using CT = common_int_t<M, N>;
    return n == 0 ? clib::abs<CT>(m) : gcd<CT, CT>(n, m % n);
}

// 最小公倍数
template <class M, class N>
constexpr auto lcm(M m, N n) -> common_int_t<M, N> {
    return clib::abs((m / gcd(m, n)) * n);
}

void solve(void){
    long n, m;
    cin >> n >> m;
    string s, t;
    cin >> s;
    cin >> t;
    long divide = gcd(n, m);
    long span_s = n / divide;
    long span_t = m / divide;
    for(long i = 0; i < divide; i++){
        if(s[i * span_s] != t[i * span_t]){
            cout << -1 << endl;
            return;
        }
    }
    //cout << n << ", " << m << ", " << divide << endl;
    cout << lcm(n, m) << endl;
}

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

Measured memory_bytes: 640
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  long long int v[n+1],w[n+1];
   long long int dp[n+1][k+1];

  for(int i=1;i<=n;i++)
  {cin>>w[i]>>v[i];
   }
  
  for(int i=0;i<=n;i++)
  {
    for(int j=0;j<=k;j++){
      if(i==0||j==0)
        dp[i][j]=0;
      else if(w[i]>j)
        dp[i][j]=dp[i-1][j];
      else
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        
    }
  }
    cout<<dp[n][k]<<endl;

}


Measured memory_bytes: 79104
#include <bits/stdc++.h>
const int maxn = int(1e5) + 7;
int x, y, h, w, n;
long long ans[17], base = int(1e9) + 7, zero, node[maxn << 4], tot_node;
int main(void) {
    scanf("%d%d%d", &h, &w, &n);
    zero = 1ll * (h - 2) * (w - 2);
    while (n--) {
        scanf("%d%d", &x, &y);
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
                if (1 <= x - i && x - i <= h - 2 && 1 <= y - j && y - j <= w - 2)
                    node[tot_node++] = base * (x - i) + (y - j);
    }
    std::sort(node, node + tot_node);
    for (int i = 0, cnt = 1; i < tot_node; i++) {
        if (node[i] == node[i + 1]) cnt++;
        else ans[cnt]++, cnt = 1, zero--;
    }
    printf("%lld\n", zero);
    for (int i = 1; i < 10; i++) printf("%lld\n", ans[i]);
    return 0;
}

Measured memory_bytes: 8448
/*
 *Author : zsenshi
 DP 
 */
#include <bits/stdc++.h> //Only for gcc compilers
#define mt make_tuple
#define eb emplace_back
#define pb push_back
#define dg(x) cout << #x << ":"<<x<<endl
#define dg2(x,y) cout<<#x<<':'<<x<<' '<<#y<<':'<<y<<endl
#define dg3(x,y,z) cout<<#x<<':'<<x<<' '<<#y<<':'<<y<<' '<<#z<<':'<<z<<endl
#define dg4(x,y,z,zz) cout<<#x<<':'<<x<<' '<<#y<<':'<<y<<' '<<#z<<':'<<z<<' '<<#zz<<':'<<zz<<endl
#define rep(i,begin,end) for(__typeof(end) i = (begin)-((begin) > (end)); i != (end) - ((begin) > (end)); i += 1-2*((begin) > (end)))
#define ll long long 
using namespace std;
typedef vector<vector<int>> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<vector<pii>> vvpi;
const ll INF = 1e18L+5;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n,W;
  cin >> n >> W;
  vector<int> weight(n),value(n);
  for(int i = 0; i < n; i++){
    cin >> weight[i] >> value[i];
  }
  int sum_value = 0;
  for(int x : value){
    sum_value += x;
  }
  //dp[i] minimum weight to get to value i.
  vector<ll> dp(sum_value+1,INF); //0..sum_value.
  dp[0] = 0;
  for(int i = 0; i< n; ++i){
    for(int value_already=sum_value-value[i]; value_already >= 0; value_already--){
      dp[value_already+value[i]] = min(dp[value_already+value[i]],dp[value_already] + weight[i]);
    }
  }
  ll answer = 0;
  for(int i = 0; i <= sum_value; i++){
    if(dp[i] <= W){
      answer = max(answer,(ll)i);
    }
  }
  cout << answer << "\n";


}


Measured memory_bytes: 1024
#include <iostream>
#include <math.h>

using namespace std;


int main(){

	int N, aux;
	cin >> N;
	int A[N] = {0};

	for (int i = 0; i < N-1; ++i){
		cin >> aux;
		A[aux-1]++;
	}
	for (int i = 0; i < N; ++i){
		cout << A[i] << endl;
	}
}


Measured memory_bytes: 4360
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <utility>
using namespace std;

int main() {
  long long int gcd(long long int a, long long int b);
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long int N, X; cin >> N >> X;
  set<long long int> S;
  for (long long int i = 0; i < N; i++) {
    long long int x; cin >> x;
    S.insert(abs(x-X));
  }
  long long int ans = *S.begin();
  for (auto it = S.begin(); it != S.end(); ++it) {
    ans = gcd(ans, *it);
  }
  cout << ans << endl;
}

long long int gcd(long long int a, long long int b) {
  long long int n = min(a,b); long long int x = max(a,b);
  if (n == 0)
    return x;
  else
    return gcd(n, x%n);
}


Measured memory_bytes: 4864
# D
import math
A, B, C = map(int, input().split())
x = C / A**2
height = 2 * x - B
if (height >= 0):
    y = B -height
    print(math.degrees(math.atan(y/A)))
else:
    z = 2*C / (A*B)
    print(math.degrees(math.atan(B/z)))

Measured memory_bytes: 39024
#include <iostream> 
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[1000];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=n-1;i>=1;i--){
		cout<<a[i]<<" ";
	}
	cout<<a[0]<<endl;
}



Measured memory_bytes: 3008
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define each(a,x) for(auto a : (x))
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) ((a) = min((a),(b)))
#define chmax(a,b) ((a) = max((a),(b)))
#define in_range(x,l,r) ((l)<=(x) && (x)<(r))
#define printvec(a) rep(i,a) cout << a[i] << " \n"[i+1==(a).size()];
#define fs first
#define sc second
#define em emplace
#define eb emplace_back
#define sz size()
#define MP make_pair
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;

const ll INF = 1e8;
const D EPS = 1e-8;
const ll MOD = 1e9+7;

long double dfs(int v, int par, int d, long double p,
                vector<int> &cnt, const vector< vector< pair<int,int> > > &t){
  cnt[d]++;
  long double res = 0;
  for(auto e : t[v]){
    int u = e.first, c = e.second;
    if(u==par) continue;
    res += (dfs(u,v,d+1,p,cnt,t) + c) * p;
  }
  return res;
}

int main(){
  long double p; cin >> p;
  int n; cin >> n;
  vector< vector< pair<int,int> > > t(n);
  rep(i,n-1){
    int a,b,c;
    cin >> a >> b >> c; a--; b--;
    t[a].eb(MP(b,c));
    t[b].eb(MP(a,c));
  }
  vector<int> cnt(n,0);
  cnt[0]++;
  long double exp = dfs(0,-1,0,p,cnt,t);

  long double ans = 0, k = 1;
  rep(i,n){
    ans += exp*cnt[i]*k;
    k *= p;
  }
  cout << fixed << setprecision(9) << ans << endl;
}

Measured memory_bytes: 19724
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int k;
	cin >> k;
	int cnt = 1;
	int curr = 7 % k;
	vector <bool> appear(k);
	while (curr != 0 && !appear[curr]) {
		appear[curr] = true;
		curr = (curr*10+7) % k;
		//cout << curr << '\n';
		cnt++;
	}
	if (curr == 0) {
		cout << cnt;
	} else {
		cout << -1;
	}
}

Measured memory_bytes: 3724
import itertools

# input
H, W, K = map(int,input().split())
init_map = []
for i in range(H):
    row = list(input())
    init_map.append(row)
ans = 0

for paint_h in range(2**H):
    for paint_w in range(2**W):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if (paint_h>>i)&1==0 and  (paint_w>>j)&1==0:
                    if init_map[i][j] == "#":
                        cnt += 1
        if cnt==K:
            ans += 1
print(ans)

Measured memory_bytes: 9204
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    boolean flag = false;
    if (S.matches("[a-z]*keyence")) {
      flag = true;
    }
    if (S.matches("k[a-z]*eyence")) {
      flag = true;
    }
    if (S.matches("ke[a-z]*yence")) {
     flag = true;
    }
    if (S.matches("key[a-z]*ence")) {
      flag = true;
    }
    if (S.matches("keye[a-z]*nce")) {
      flag = true;
    }
    if (S.matches("keyen[a-z]*ce")) {
      flag = true;
    }
    if (S.matches("keyenc[a-z]*e")) {
      flag = true;
    }
    if (S.matches("keyence[a-z]*")) {
      flag = true;
    }
    if (flag) {
      System.out.println("YES");
    } else {
      System.out.println("NO");
    }
  }
}

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

int main() {
  int N;
  cin >> N;
  long long div = pow(10,9) + 7;
  long long tmp = 1;
  for(int i=1;i<=N;i++){
    tmp = (i*tmp) % div;
  }
  cout << tmp << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <queue>
using namespace std;
#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
struct TEMP_OMAZINAI_ { TEMP_OMAZINAI_() { std::ios::sync_with_stdio(false); std::cin.tie(0); } } TEMP__omazinai_instance__;
#define INF ((1LL<<61) + (1<<29))
#define YesNo(x) {std::cout << ((x)?"Yes":"No") << std::endl;}
#define YESNO(x) {std::cout << ((x)?"YES":"NO") << std::endl;}
#define OddEven(x) {std::cout << ((x)%2?"Odd":"Even") << std::endl;}
#define ODDEVEN(x) {std::cout << ((x)%2?"ODD":"EVEN") << std::endl;}
typedef long long int ll;
ll my_gcd(ll a, ll b) { return b ? my_gcd(b, a%b) : a; };
void TEMP_INPUT_IMPL_() {};
template <class T, class... Args> void TEMP_INPUT_IMPL_(T& dest, Args&... args) { cin >> dest; TEMP_INPUT_IMPL_(args...); }
void TEMP_OUTPUT_IMPL_() {};
template <class T, class... Args> void TEMP_OUTPUT_IMPL_(T dest, Args... args) { cout << dest << (sizeof...(Args) ? " " : ""); TEMP_OUTPUT_IMPL_(args...); }
#define in(type, ...) type __VA_ARGS__; TEMP_INPUT_IMPL_(__VA_ARGS__)
#define in_v(type, name, cnt) vector<type> name(cnt); loop(i, cnt) cin >> name[i];
#define sort_v(v) std::sort(v.begin(), v.end())
#define rsort_v(v) std::sort(v.rbegin(), v.rend())
#define unique_v(v) v.erase(std::unique(v.begin(), v.end()), v.end()) //必ずソート後に実行
#define out(...) (TEMP_OUTPUT_IMPL_(__VA_ARGS__), std::cout<<std::endl)
#define set_fix(x) ((std::cerr<<std::fixed<<std::setprecision(x)),(std::cout<<std::fixed<<std::setprecision(x)))
//小さい方に寄る
#define space_op(x, y, a, b, c) ([](auto x_, auto y_, auto a_, auto b_, auto c_){if(x_<y_)return a_;if(x_>y_)return c_;return b_;}(x,y,a,b,c))
#define space_out(x, y, a, b, c) out(space_op(x, y, a, b, c))

// ^^^ Template ^^^ //

int main() {
	in(string, S);
	loop(s, S.size()) {
		for (ll e = s; e < S.size(); ++e) {
			if (S.substr(0, s) + S.substr(e, S.size() - e) == "keyence") {
				out("YES");
				return 0;
			}
		}
	}
	out("NO");
	return 0;
}

Measured memory_bytes: 256
import heapq


n, m = map(int, input().split())
a = list(map(lambda a: -int(a), input().split()))
heapq.heapify(a)
for i in range(m):
    tmp = heapq.heappop(a)
    tmp = (- tmp) // 2
    heapq.heappush(a,  - tmp)
print(-sum(a))


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

using namespace std;

template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename G >
struct StronglyConnectedComponents {
  const G &g;
  UnWeightedGraph gg, rg;
  vector< int > comp, order, used;

  StronglyConnectedComponents(G &g) : g(g), gg(g.size()), rg(g.size()), comp(g.size(), -1), used(g.size()) {
    for(int i = 0; i < g.size(); i++) {
      for(auto e : g[i]) {
        gg[i].emplace_back((int) e);
        rg[(int) e].emplace_back(i);
      }
    }
  }

  int operator[](int k) {
    return (comp[k]);
  }

  void dfs(int idx) {
    if(used[idx]) return;
    used[idx] = true;
    for(int to : gg[idx]) dfs(to);
    order.push_back(idx);
  }

  void rdfs(int idx, int cnt) {
    if(comp[idx] != -1) return;
    comp[idx] = cnt;
    for(int to : rg[idx]) rdfs(to, cnt);
  }

  void build(UnWeightedGraph &t) {
    for(int i = 0; i < gg.size(); i++) dfs(i);
    reverse(begin(order), end(order));
    int ptr = 0;
    for(int i : order) if(comp[i] == -1) rdfs(i, ptr), ptr++;

    t.resize(ptr);
    for(int i = 0; i < g.size(); i++) {
      for(auto &to : g[i]) {
        int x = comp[i], y = comp[to];
        if(x == y) continue;
        t[x].push_back(y);
      }
    }
  }
};

int main() {
  int V, E, Q;
  scanf("%d %d", &V, &E);
  UnWeightedGraph g(V), buff;
  for(int i = 0; i < E; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    g[a].emplace_back(b);
  }
  StronglyConnectedComponents< UnWeightedGraph > scc(g);
  scc.build(buff);
  scanf("%d", &Q);
  while(Q--) {
    int a, b;
    scanf("%d %d", &a, &b);
    puts(scc[a] == scc[b] ? "1" : "0");
  }
}




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

// m:1, f:2
int data[100001];

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

    string s0;
    cout << 0 << endl;
    cin >> s0;
    if(s0 == "Vacant"){
        cout << 0 << endl;
        return 0;
    }
    if(s0 == "Male"){
        data[0] = 1;
        data[N] = 1;
    }
    else{
        data[0] = 2;
        data[N] = 2;
    }

    int f = 0;
    int l = N;
    for(int i = 1; i < 20; ++i){
        int num = (f + l) / 2;
        cout << num << endl;
        cin >> s0;
        if(s0 == "Vacant"){
            cout << num << endl;
            return 0;
        }
        if(s0 == "Male") data[num] = 1;
        else data[num] = 2;
        if((data[f] != data[num] && (num - f) % 2 == 0) ||
        (data[f] == data[num] && (num - f) % 2 != 0)){
            l = num;
        }
        if((data[l] != data[num] && (l - num) % 2 == 0) ||
        (data[l] == data[num] && (l - num) % 2 != 0)){
            f = num;
        }
    }
    cout << N-1 << endl;
}

Measured memory_bytes: 852
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long ans=0,count=0;
  string s;
  cin>>s;
  for(long long i=0;i<s.size();++i){
    if(s[i]=='W'){
      ans+=i-count;
      ++count;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3712
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
#include <queue>
#include <map>
#include <set>
using namespace std;
using Int = int64_t;
const Int INF = 1<<30;
const Int MOD = (Int)1e9 + 7;
const Int MAX_N = (Int)1e5 + 5;
#define debug(x) cout << #x << ": " << x << endl
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2>& p) { os << p.first << " " << p.second; return os; }
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) { for(int i = 0; i < (int) v.size(); i++) os << v[i] << (i + 1 != v.size() ? " " : ""); return os; }

int n, k;
void solve()
{
    cin >> n >> k;
    vector<int> A(n);
    for(int i = 0; i < n; i++) cin >> A[i];

    while(k--)
    {
        bool is_convergence = true;
        // 左右からimos法を行う
        vector<int> imos1(n, 0), imos2(n, 0);
        for (int i = 0; i < n; i++)
        {
            imos1[i]++;
            if(i + A[i] + 1 < n)
            {
                imos1[i + A[i] + 1]--;
            }
        }
        for(int i = 1; i < n; i++)
        {
            imos1[i] += imos1[i - 1];
        }

        for(int i = n - 1; i >= 0; i--)
        {
            if(A[i] == 0 || i - 1 < 0) continue;
            imos2[i - 1]++;
            if(i - A[i] - 1 >= 0)
            {
                imos2[i - A[i] - 1]--;
            }
        }
        for(int i = n - 2; i >= 0; i--)
        {
            imos2[i] += imos2[i + 1];
        }
        vector<int> B(n);
        for(int i = 0; i < n; i++)
        {
            B[i] = imos1[i] + imos2[i];
            if(B[i] != n) is_convergence = false;
        }
        A = B;
        if(is_convergence) break;
    }
    for(int i = 0; i < n; i++) cout << A[i] << " "; cout << endl;
}

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

Measured memory_bytes: 6308
#include <iostream>
#include <sstream>

int main() {

	int a, b, c, d;
	int n;
	std::cin >> n;
	
	a = n / 1000;
	n = n - a * 1000;
	b = n / 100;
	n = n - b * 100;
	c = n / 10;
	n = n - c * 10;
	d = n;

	char A = static_cast<char>(a);
	char B = static_cast<char>(b);
	char C = static_cast<char>(c);
	char D = static_cast<char>(d);
	if (a + b + c + d == 7) { std::cout << a << '+' << b << "+" << c << "+" << d << "=7"; }
	else if (a + b + c - d == 7) { std::cout << a << '+' << b << "+" << c << "-" << d << "=7"; }
	else if (a + b - c + d == 7) { std::cout << a << '+' << b << "-" << c << "+" << d << "=7"; }
	else if (a - b + c + d == 7) { std::cout << a << '-' << b << "+" << c << "+" << d << "=7"; }
	else if (a + b - c - d == 7) { std::cout << a << '+' << b << "-" << c << "-" << d << "=7"; }
	else if (a - b + c - d == 7) { std::cout << a << '-' << b << "+" << c << "-" << d << "=7"; }
	else if (a - b - c + d == 7) { std::cout << a << '-' << b << "-" << c << "+" << d << "=7"; }
	else if (a - b - c - d == 7) { std::cout << a << '-' << b << "-" << c << "-" << d << "=7"; }
}


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

int main() {
  int N, a, b, c, d;
  cin >> N;
  a = N / 1000;
  b = (N - 1000 * a) / 100;
  c = (N - 1000 * a - 100 * b) / 10;
  d = N % 10;

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

Measured memory_bytes: 3496
import math

a,b,h,m = map(lambda x: int(x), input().split())

kaku_a = (math.pi * (h + m/60))/6
kaku_b = (math.pi * m / 5)/6

sub = kaku_a - kaku_b

if sub > 0:
    xx = a**2 + b**2 - 2*a*b*math.cos(sub)
else:
    xx = a**2 + b**2 - 2*a*b*math.cos(-1 * sub)

print(math.sqrt(xx))



Measured memory_bytes: 9448
import sys
input=sys.stdin.readline
import heapq

def dijkstra(Route,v,start):
    Dist=[float('inf')]*v
    Dist[start]=0
    Visited=[False]*v
    hq=[(0,start)]
    while hq:
        dist,fr=heapq.heappop(hq)
        Visited[fr]=True
        for to,cost in Route[fr]:
            if (not Visited[to]) and Dist[to]>dist+cost:
                Dist[to]=dist+cost
                heapq.heappush(hq,(Dist[to],to))
    return Dist

def main():
    n,m,s=map(int,input().split())
    s_max=2500
    Edges=[[] for _ in range(n*s_max)]
    for _ in range(m):
        u,v,cost,time=map(int,input().split())
        u-=1; v-=1
        for i in range(cost,s_max):
            Edges[u*s_max+i].append((v*s_max+i-cost,time))
            Edges[v*s_max+i].append((u*s_max+i-cost,time))
    Change=[None]*n
    for i in range(n):
        change,time=map(int,input().split())
        for j in range(s_max-change):
            Edges[i*s_max+j].append((i*s_max+j+change,time))
    Dist=dijkstra(Edges,n*s_max,min(s,s_max-1))
    for i in range(1,n):
        print(min(Dist[i*s_max:(i+1)*s_max]))
    
if __name__=='__main__':
    main()

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

int main(){
  int a;
  cin >> a;
  int ans = 0;
  rep(i,3){
    if(a%10) ans++;
    a/=10;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      	int n = sc.nextInt();
      	int k = sc.nextInt();
      	int[] pi = new int[n];
      	int sum = 0;
      	for(int i = 0; i < n; i++){
        	pi[i] = sc.nextInt();
        }
		Arrays.sort(pi);
      	for(int i = 0; i < k; i++){
        	sum += pi[i];
        }
      
      	System.out.println(sum);
    }
}

Measured memory_bytes: 38980
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
int dp[62][2][2]; // bit, r=y? l=x? allzero?
signed main(){
	int l,r;
	cin>>l>>r;
	bool fl = false, fr = false, ffl = false, ffr = false;
	for(int i=60;i>=0;i--){
		int br = ( r >> i ) % 2;
		int bl = ( l >> i ) % 2;
		if( !fl && bl ){ fl = true; ffl = true; }
		if( !fr && br ){ fr = true; ffr = true; }
		if( fr && ( !fl || ffl ) ){
			dp[i][ffr][ffl]++;
		}
		if( br == 0 && bl == 0){
			dp[i][0][0] += 3*dp[i+1][0][0] + dp[i+1][0][1];
			dp[i][1][0] += dp[i+1][1][0];
			dp[i][0][1] += 2*dp[i+1][0][1];
			dp[i][1][1] += dp[i+1][1][1];
		}
		if( br == 1 && bl == 0){
			dp[i][0][0] += 3*dp[i+1][0][0] + dp[i+1][0][1] + dp[i+1][1][0];
			dp[i][1][0] += 2*dp[i+1][1][0] + dp[i+1][1][1];
			dp[i][0][1] += 2*dp[i+1][0][1] + dp[i+1][1][1];
			dp[i][1][1] += dp[i+1][1][1];
		}
		if( br == 0 && bl == 1){
			dp[i][0][0] += 3*dp[i+1][0][0];
			dp[i][1][0] += dp[i+1][1][0];
			dp[i][0][1] += dp[i+1][0][1];
		}
		if( br == 1 && bl == 1){
			dp[i][0][0] += 3*dp[i+1][0][0] + dp[i+1][1][0];
			dp[i][1][0] += 2*dp[i+1][1][0];
			dp[i][0][1] += dp[i+1][0][1];
			dp[i][1][1] += dp[i+1][1][1];
		}
		dp[i][0][0] %=inf; dp[i][0][1]%=inf; dp[i][1][0] %=inf; dp[i][1][1]%=inf;
		ffl = false; ffr = false;
	}
	int ans = dp[0][0][0]+dp[0][1][0]+dp[0][0][1]+dp[0][1][1];
	cout<<ans%inf<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
    int n,a,b,c,d,ans=0;
    cin>>n;
    vector<pair<int,int>> R,B;
    rep(i,n) cin>>a>>b,R.push_back(make_pair(a,b));
    rep(i,n) cin>>c>>d,B.push_back(make_pair(c,d));
    sort(B.begin(),B.end());
    int r[100]={0};
    rep(i,n){
        int a=B[i].first,b=B[i].second,c=0,d=-1;
        rep(j,n){
            if(!r[j]&&a>R[j].first&&b>R[j].second&&c<=R[j].second){
                c=R[j].second;
                d=j;
            }
        }
        if(d!=-1) r[d]=1,ans++;
    }
    cout<<ans;
}

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

int main(){
    string s;
    cin >> s;
    int backs=0;
    vector<char> w;
    for(int i = (int) s.length(); i>=0;i--){
		if (s[i] == 'B') backs ++;
		else if (s[i] == '1') {
			if (backs>0) backs--;
			else w.push_back('1');
		}
		else if (s[i] == '0') {
			if (backs>0) backs--;
			else w.push_back('0');
		}
	}
	for(auto x = w.end()-1;x>=w.begin();x--) cout << *x;
	
}


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

const int N = 1e5 + 5;
int n;

int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    
    cout<<"Christmas";
    for (int i = 0; i < 25 -n; i++){
        cout<<" Eve";
    }
    cout<<endl;
    
    return 0;
}



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

int main(){
    int N;
    cin >> N;
    map<int,int> mp;
    for(int x=1;x<100;x++){
        for(int y=1;y<100;y++){
            for(int z=1;z<100;z++){
                ll tmp;
                tmp = x*x + y*y + z*z + x*y + y*z + z*x;
                mp[tmp]++;
            }
        }
    }
    rep(i,N+1){
        if(i==0) continue;
        cout << mp[i] << endl;
    }
    return 0;
}

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

using namespace std;

int main() {
  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  if ( e - a > k )
    cout << ":(" << endl;
  else
    cout << "Yay!" << endl;
  return 0;
}

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

int main(int argc, char const *argv[]) {
    double pi = 3.141592653589;
    double r;
    cin >> r;
    cout << fixed << setprecision(10) << pi*r*r << ' ' << fixed << setprecision(10) << 2*pi*r << endl;

    return 0;
}



Measured memory_bytes: 3272
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
char s[10];

int main()
{
    scanf("%s",s);
    if(strlen(s) == 2) puts(s);
    else
    {
        printf("%c%c%c\n",s[2],s[1],s[0]);
    }

    return 0;
}


Measured memory_bytes: 256
h,w = map(int,input().split())
S = [input() for i in range(h)]

A = [[0 for i in range(w)] for j in range(h)]

a = -1
b = -1
for i in range(h):
    a = -1
    for j in range(w):
        if S[i][j] == "#":
            if a != -1:
                for k in range(a,j):
                    A[i][k] += j-a
                a = -1
        else:
            if a == -1:
                a = j
                #print(j)
    if a != -1:
        for k in range(a,j+1):
            A[i][k] += j+1-a

for i in range(w):
    a = -1
    for j in range(h):
        if S[j][i] == "#":
            if a != -1:
                for k in range(a,j):
                    A[k][i] += j-a
                a = -1
        else:
            if a == -1:
                a = j
    if a != -1:
        for k in range(a,j+1):
            A[k][i] += j+1-a
#print(A)

ans = 0
for i in range(h):
    ans = max(ans, max(A[i]))

print(ans-1)

Measured memory_bytes: 100824
#include<bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
//g++ -std=c++11 

using namespace std;

long long N;
long long A[200005];

int main(){
	cin >> N;
	rep(i, N) {
		cin >> A[i];
	}

	long long cur = 1;
	rep(i, N) {
		if(cur == A[i]) {
			cur++;
		}
	}
	if(cur == 1)  {
		cout << -1 << endl;
		return 0;
	}
	cout << N - cur + 1<< endl;

}


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

struct Card{ char suit, value; };

void bubble(struct Card A[], int N) {
  for(int i = 0; i<N; i++) {
    for(int j = N-1; j >= i; j--) {
      if(A[j].value < A[j-1].value) {
        Card t = A[j]; A[j] = A[j-1]; A[j-1] = t;
      }
    }
  }
}

void selection(struct Card A[], int N) {
  for(int i=0;i<N;i++) {
    int minj = i;
    for(int j=i; j<N; j++) {
      if(A[j].value < A[minj].value) minj = j;
    }
    Card t = A[i]; A[i] = A[minj]; A[minj] = t;
  }
}

void print(struct Card A[], int N) {
  for(int i=0; i<N; i++) {
    if(i>0) cout << " ";
      cout << A[i].suit << A[i].value;
  }
  cout << endl;
}

bool isStable(struct Card C1[], struct Card C2[], int N) {
  for(int i=0; i<N; i++) {
    if(C1[i].suit != C2[i].suit) return false;
  }
  return true;
}

int main(void) {
  Card C1[100], C2[100];
  int N;
  char ch;

  cin >> N;
  for(int i=0;i<N; i++) {
    cin >> C1[i].suit >> C1[i].value;
  }
  for(int i=0; i<N; i++) C2[i] = C1[i];

  bubble(C1,N);
  selection(C2,N);

  print(C1,N);
  cout << "Stable" << endl;
  print(C2,N);
  if(isStable(C1,C2,N)) {
    cout << "Stable" << endl;
  } else {
    cout << "Not stable" << endl;
  }

  return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define dbg(x) cout<<#x" = "<<(x)<<ln

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > mat;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

int a, n, l, r;
string s;

int main() {
	cin >> s;
	n = s.length();
	r = n-1;
	while (l<r) {
		if (s[l]==s[r]) l++, r--;
		else if (s[l]=='x') l++, a++;
		else if (s[r]=='x') r--, a++;
		else {
			a = -1;
			break;
		}
	}
	cout << a << ln;
}

Measured memory_bytes: 512
#!/usr/bin/env python
from collections import deque

def comb(a, b):
    result = 1
    for i in range(b):
        result *= (a - i) / (i + 1)
    return result


def main():
    N = int(input())
    As = map(int, input().split())

    is_valid = True
    for A in As:
        if A % 2 == 0:
            if A % 3 == 0 or A % 5 == 0:
                pass
            else:
                is_valid = False

    if is_valid:
        print("APPROVED")
    else:
        print("DENIED")


if __name__ == '__main__':
    main()


Measured memory_bytes: 39852
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cmath>
#include <tuple>
#include <map>
#include <unordered_map>
#include <deque>
#include <queue>
using namespace std;
typedef long long ll;

int main(int argc, char *argv[])
{
	int i, j, k;
	int n, x, y;
	cin >> n >> x >> y;
    vector<ll> answer(n - 1, 0);
    int distance;
	bool asorlowerx = false;
	bool betweenxandy = false;
	bool asorhighery = false;

	for (i = 1; i <= n - 1; i++) {
		asorlowerx = betweenxandy = asorhighery = false;
		if (i <= x)
			asorlowerx = true;
		else if (x < i && i < y)
			betweenxandy = true;
		else
			asorhighery = true;
		
		for (j = i + 1; j <= n; j++) {
			if (asorlowerx) {
				if (j <= x)
					distance = j - i;
				else if (x < j && j < y) 
					distance = min(j - i, y - j + 1 + x - i);
				else
					distance = j - y + 1 + x - i;
			} else if (betweenxandy) {
				if (j < y)
					distance = min(j - i, y - j + 1 + i - x);
				else
					distance = min(j - i, j - y + 1 + i - x);
			} else {
				distance = j - i;
			}
			answer[distance - 1]++;
		}
	}
	for (i = 0; i < n - 1; i++)
		cout << answer[i] << endl;
	
	return 0;
}


Measured memory_bytes: 256
import java.math.BigDecimal;
import java.sql.Array;
import java.util.*;
public class Main {
	public static void main(String[] args){
      	
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		boolean good = true;
		for (long i = -100; i <= 100; i++) {
			for (long j = -100; j <= 100; j++) {
				if((i*i*i*i*i)-(j*j*j*j*j)==X){
					System.out.println(i+" "+j);
					good = false;
					break;
				}		
			}
			if(!good){
				break;
			}
		}

		if(good){
		for (long i = 64; i <= 128; i++) {
			for (long j = 64; j <= 128; j++) {
				if((i*i*i*i*i)-(j*j*j*j*j)==X){
					System.out.println(i+" "+j);
					good =false;
					break;
				}		
			}
			if(!good){
				break;
			}
		}
		}
		if(good){
		for (long i = -128; i <= -64; i++) {
			for (long j = -128; j <= -64; j++) {
				if((i*i*i*i*i)-(j*j*j*j*j)==X){
					System.out.println(i+" "+j);
					good = false;
					break;
				}		
			}
			if(!good){
				break;
			}
		}
		}
		sc.close();
    }	
		
}

Measured memory_bytes: 27048
N, Y = map(int, input().split())
Y = Y // 1000
for i in range(N + 1):
    if i * 10 > Y:
        continue
    for j in range(N + 1):
        if i + j > N:
            continue
        if Y == i * 10 + j * 5 + N - i - j:
            print(i, j, N - i - j)
            exit()
print(-1, -1, -1)


Measured memory_bytes: 3060
(let* ((n (read))
       (l (read))
       (s (+ (* n (1- l)) (/ (* n (1+ n)) 2)))
       (d (cond ((< 0 (+ l 1 -1))
                 (+ l 1 -1))
                ((< (+ l n -1) 0)
                 (+ l n -1))
                (t
                 0))))
  (format t "~A~%" (- s d)))


Measured memory_bytes: 24200
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readNInts = readInt >>= flip replicateM readInt

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

keyence = "keyence"

main = do
	s <- getLine
	putStrLn $ which "YES" "NO" $ not $ null $ do
		i <- [ 0 .. length keyence ]
		let
			prefix = take i keyence
			suffix = drop i keyence
		guard $ prefix `isPrefixOf` s && suffix `isSuffixOf` s
		return ()

Measured memory_bytes: 380
#include <cstdio>
#include <memory.h>
#include <cstring>
#include <vector>
#include <deque>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <functional>
#include <iostream>
#include <set>
#include <list>
#include <map>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef unsigned long long llu;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
const ll MOD = 1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;

priority_queue<int, vector<int>, greater<int> > pq;
vector<int> v;

// 최소 스왑횟수로 팰린드롬 만들기.
// 주어진 알파벳으로 가능한 팰린드롬 찾기.
// n이 홀수인 경우, 딱 한개만 홀수개 있고 나머지 짝수개
// n이 짝수인 경우, 전부 짝수개.
// 항상 모든 n개를 사용해야 하는 점을 이용할 수 있지 않을까?
// 맨끝부터 정해준다는 그리디를 계속 사용.
// 나머지는 안쪽으로 들어가니까...
// 그러면 현재 상태에서 가장 왼쪽에 있는 알파벳이 왼쪽으로 갈때
// 오른쪽에 있는 알파벳이 오른쪽으로 갈때.
// 현재꺼에서 그리디하게 채워줄 수 있고,
// 이제 나머지는 펜윅트리를 이용해서, 
// 이제 나머지 할 일은... 나머지가 다 같이 움직이는 거니까.
// 왼쪽으로 간 것 하나와 오른쪽으로 간 것 하나.
// 위치라는 게... 음 이 위치는 안 변하나?
// 상대적인 순서가 바뀌지는 않음.
// 

set<int> se[26];
char s[200002];
int ltree[200002];
int rtree[200002];
int n;

void update(int i, int val, int *tree) {
	for (; i <= n; i += i & -i)
		tree[i] += val;
}

int find(int i, int *tree) {
	int sum = 0;
	for (; i; i -= i & -i)
		sum += tree[i];
	return sum;
}

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

	for (int i = 1; i <= n; i++)
		se[s[i] - 'a'].insert(i);
	
	int flag = 0;
	if (n % 2) {
		for(int i = 0; i < 26; i++)
			if (sz(se[i]) % 2) {
				if (flag) return !printf("-1");
				flag = 1;
			}
	}
	else {
		for (int i = 0; i < 26; i++)
			if (sz(se[i]) % 2)
				return !printf("-1");
	}

	ll ans = 0;
	ll ls, rs;
	for (int i = 1; i <= n / 2; i++) {
		ls = rs = 0;
		int miv = 1e9, mivi = -1;
		int t;

		for (int j = 0; j < 26; j++) {
			if (sz(se[j]) < 2) continue;
			t = *se[j].begin() + (n - *(--se[j].end()));
			if (t < miv) {
				miv = t;
				mivi = j;
			}
		}

		int le = *se[mivi].begin();
		int ri = *(--se[mivi].end());
		se[mivi].erase(se[mivi].begin());
		se[mivi].erase(--se[mivi].end());

		ls += le - i;
		ls -= find(le, rtree);
		ls += find(n, ltree) - find(le, ltree); // 왼->오가는 트리 rtree, 오->왼가는 트리 ltree
		
		rs += (n - i + 1) - ri;
		rs += find(ri, rtree);
		rs -= find(n, ltree) - find(ri, ltree);

		update(le, 1, ltree);
		update(ri, 1, rtree);

		ans += ls + rs;
	}

	printf("%lld", ans);
}

Measured memory_bytes: 10752
#include<bits/stdc++.h>
  
using namespace std;
  
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
  
int a,b,c;
cin>>a>>b>>c;

int n=0;

for(int i=a; i<=b; i++){
    if(c%i==0) n++;
}
  
 cout<<n<<endl;

  
return 0;
  
}


Measured memory_bytes: 3176
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

enum Type{
	sit_down,
	stand_up,
};

struct Info{
	bool operator<(const Info &arg) const{
		return time > arg.time;
	}
	int row_or_col,loc,time;
	Type order;
};

int Q;
ll R,C;
Info order_row[50000],order_col[50000];

void func(){

	for(int i = 0; i < R; i++){
		order_row[i].row_or_col = -1;
	}
	for(int i = 0; i < C; i++){
		order_col[i].row_or_col = -1;
	}

	int row_or_col,loc,order;

	for(int loop = 0; loop < Q; loop++){
		scanf("%d %d %d",&row_or_col,&loc,&order);
		if(row_or_col == 0){
			order_row[loc].row_or_col = 0;
			order_row[loc].loc = loc;
			order_row[loc].time = loop;
			if(order == 0){
				order_row[loc].order = sit_down;
			}else{
				order_row[loc].order = stand_up;
			}
		}else{
			order_col[loc].row_or_col = 1;
			order_col[loc].loc = loc;
			order_col[loc].time = loop;
			if(order == 0){
				order_col[loc].order = sit_down;
			}else{
				order_col[loc].order = stand_up;
			}
		}
	}

	vector<Info> V;

	for(int i = 0; i < R; i++){
		if(order_row[i].row_or_col != -1){
			V.push_back(order_row[i]);
		}
	}

	for(int i = 0; i < C; i++){
		if(order_col[i].row_or_col != -1){
			V.push_back(order_col[i]);
		}
	}

	sort(V.begin(),V.end());

	ll ans = 0;
	ll sit_row_num = 0,sit_col_num = 0,stand_row_num = 0,stand_col_num = 0;

	for(int i = 0; i < V.size(); i++){

		if(V[i].row_or_col == 0){
			if(V[i].order == stand_up){
				ans += C-(sit_col_num+stand_col_num);
				stand_row_num++;
			}else{
				sit_row_num++;
			}
		}else{
			if(V[i].order == stand_up){
				ans += R-(sit_row_num+stand_row_num);
				stand_col_num++;
			}else{
				sit_col_num++;
			}
		}
	}

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

int main(){

	while(true){
		scanf("%lld %lld %d",&R,&C,&Q);
		if(R == 0 && C == 0 && Q == 0)break;

		func();
	}

	return 0;
}

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

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

	if (a < b) {
		if (b < c) {
			cout << a << ' ' << b << ' ' << c << endl;
		}
		else if(c < a){
			cout << c << ' ' << a << ' ' << b << endl;
		}
		else {
			cout << a << ' ' << c << ' ' << b << endl;
		}
	}
	else {
		if (a < c) {
			cout << b << ' ' << a << ' ' << c << endl;
		}
		else if(c < b){
			cout << c << ' ' << b << ' ' << a << endl;
		}
		else {
			cout << b << ' ' << c << ' ' << a << endl;
		}
	}

    return 0;
}

Measured memory_bytes: 1160
n,m,x=gets.split(' ').map(&:to_i)
a=Array.new(m)
a[0..m]=gets.split(' ').map(&:to_i)

c_n=a.count{|item| item>x && item<n}
c_0=a.count{|item| item<x}

if c_n<=c_0 
  puts c_n
else
  puts c_0
end


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
using Int = signed;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
const Int MAX = 102;
Int h,w,x,y;
Int b[MAX*3][MAX*3];
// [l, r] * [u, d]
Int sum(Int l,Int r,Int u,Int d){
  if(l>r||u>d) return 0;
  l+=MAX-1;r+=MAX;u+=MAX-1;d+=MAX;
  return b[d][r]+b[u][l]-b[u][r]-b[d][l];
}

short dp[MAX][MAX][MAX][MAX];

short calcL(Int l,Int r,Int u,Int d){
  if(x-l<r) return 0;
  return sum(x-l,x-l,max(y-u,d),min(y+d,h-(u+1)));
}
short calcR(Int l,Int r,Int u,Int d){
  if(w-(l+1)<x+r) return 0;
  return sum(x+r,x+r,max(y-u,d),min(y+d,h-(u+1)));
}
short calcU(Int l,Int r,Int u,Int d){
  if(y-u<d) return 0;
  return sum(max(x-l,r),min(x+r,w-(l+1)),y-u,y-u);
}
short calcD(Int l,Int r,Int u,Int d){
  if(h-(u+1)<y+d) return 0;
  return sum(max(x-l,r),min(x+r,w-(l+1)),y+d,y+d);
}

signed main(){
  cin>>h>>w;
  vector<string> s(h);
  for(Int i=0;i<h;i++) cin>>s[i];
  memset(b,0,sizeof(b));
  for(Int i=0;i<h;i++)
    for(Int j=0;j<w;j++)
      if(s[i][j]=='o') b[MAX+i][MAX+j]++;
  
  for(Int i=0;i<h;i++)
    for(Int j=0;j<w;j++)
      if(s[i][j]=='E') y=i,x=j;

  for(Int i=0;i<MAX*3;i++)
    for(Int j=1;j<MAX*3;j++)
      b[i][j]+=b[i][j-1];
  
  for(Int i=1;i<MAX*3;i++)
    for(Int j=0;j<MAX*3;j++)
      b[i][j]+=b[i-1][j];

  memset(dp,0,sizeof(dp));

  for(int l=0;l<=w;l++){
    for(int r=0;r<=w;r++){
      for(int u=0;u<=h;u++){
	for(int d=0;d<=h;d++){
	  //cout<<l<<" "<<r<<" "<<u<<" "<<d<<":"<<dp[l][r][u][d]<<endl;
	  chmax(dp[l+1][r][u][d],dp[l][r][u][d]+calcL(l+1,r,u,d));
	  chmax(dp[l][r+1][u][d],dp[l][r][u][d]+calcR(l,r+1,u,d));
	  chmax(dp[l][r][u+1][d],dp[l][r][u][d]+calcU(l,r,u+1,d));
	  chmax(dp[l][r][u][d+1],dp[l][r][u][d]+calcD(l,r,u,d+1));
	}
      }
    }
  }	  
  
  cout<<dp[w][w][h][h]<<endl;
  return 0;
}


Measured memory_bytes: 212096
#include <stdio.h>

int main(){
  int x,y,z;

  scanf("%d%d",&x,&y);

  if(x < y){
    z = x;
    x = y;
    y = z;
  }
  if(x>=1 & y>=1){
    z = x % y;
    
    while(z != 0){
      x = y;
      y = z;
      z = x % y;
    }
  }
  printf("%d\n",y);
  return 0;
}



Measured memory_bytes: 2144
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 1000000007;
int arr[7368792];
signed main(){
    while(1){
        int n;
        cin >> n;
        if(n == 0)break;
        vector<string> s(n);
        rep(i,n)cin >> s[i];
        for(int i = 0;i <= n-5;i++){
            int num[5] = {0};
            int stage = 0;
            int flag = 0;
            for(int j = i;j < n;j++){
                if(stage == 0){
                    num[stage] += s[j].size();
                    if(num[stage] == 5)stage++;
                    else if(num[stage] > 5)break;
                }else if(stage == 1){
                    num[stage] += s[j].size();
                    if(num[stage] == 7)stage++;
                    else if(num[stage] > 7)break;
                }else if(stage == 2){
                    num[stage] += s[j].size();
                    if(num[stage] == 5)stage++;
                    else if(num[stage] > 5)break;
                }else if(stage == 3){
                    num[stage] += s[j].size();
                    if(num[stage] == 7)stage++;
                    else if(num[stage] > 7)break;
                }else if(stage == 4){
                    num[stage] += s[j].size();
                    if(num[stage] == 7){
                        cout << i+1 << endl;
                        flag = 1;
                        break;
                    }
                    else if(num[stage] > 7)break;
                }
            }
            if(flag)break;
        }
    }
    
    return 0;
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://abc133.contest.atcoder.jp/tasks/abc133_b


Measured memory_bytes: 3164
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  int n,q;
  cin>>n>>q;
  string s;
  cin>>s;

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

  for(int i=0;i<q;i++){
    int l,r;
    cin>>l>>r;
    int ans=sum[r]-sum[l-1];
    if(l>1&&s[l-2]=='A'&&s[l-1]=='C') ans--;
    cout<<ans<<endl;
  }

  return 0;
}


Measured memory_bytes: 1408