akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#define N 41

typedef struct node{
	int L_id;
	int R_id;
}node;

node c[N];
int a[N];
int b[N];
int cnt=0;

void postorder(int root,int n){
	
	if(c[root].L_id!=-1)
		postorder(c[root].L_id,n);
	
	if(c[root].R_id!=-1)
		postorder(c[root].R_id,n);
	
	if(cnt<n-1)
		printf("%d ",root);
	else 
		printf("%d\n",root);
	
	cnt++;

	return;
	
}

int reconst(int start,int last,int n){
	
	if(start==last)
		return b[start];
		
	else if(start > last)
		return -1;
	
	else {
		for(int i=1;i<=n;i++){
			for(int j=start;j<=last;j++){
				if(a[i]==b[j]){
					c[a[i]].L_id=reconst(start,j-1,n);
					c[a[i]].R_id=reconst(j+1,last,n);
					return a[i];
				}
			}
		}
	}
	
}




int main(){
	int n,i;
	int root;
	
	scanf("%d",&n);
	
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	for(i=1;i<=n;i++)
		scanf("%d",&b[i]);
		
	for(i=1;i<=n;i++){
		c[i].L_id=-1;
		c[i].R_id=-1;
	}
	
	root=reconst(1,n,n);
	
	postorder(root,n);
	
	return 0;
	
}


Measured memory_bytes: 2104
#include <stdio.h>
int main(void){
    int i,j,a,b;
    
    while(1){
        scanf("%d %d",&a,&b);
        if(a == 0 &&b==0){
            break;
        }
        for(i=0;i<a;i++){
            for(j=0;j<b;j++){
                printf("#");
            }     
            printf("\n");
            }
       printf("\n");
        }
    return(0);
}



Measured memory_bytes: 2140
#include<iostream>
#include<vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <limits>
#include <map>
#include <bitset>
#include <iomanip>

#define rep(i,n) for(int (i) = 0; (i)<(n); (i)++)
#define FOR(i,s,e) for(int (i) = (s); (i)<(e); (i)++)
#define vecall(itr,vec) for(auto (itr) = (vec).begin(); (itr) != (vec).end(); (itr)++)
#define vecshow(vec) for(auto itr = (vec).begin(); itr != (vec).end(); itr++)cout << *itr << " ";

using namespace std;
using p = pair<int, int>;
using ll = long long;

int gcd(int a, int b) {
	int l = max(a, b);
	int s = min(a, b);
	while (l * s != 0) {
		int tmp = s;
		s = l % s;
		l = tmp;
	}

	return l;
}

vector<vector<int>> path;

int main() {
	ll a, b, v, w, t;
	cin >> a >> v;
	cin >> b >> w;
	cin >> t;
	
	ll dist = abs(b - a);
	ll move = (v - w) * t;

	if (dist > move) cout << "NO" << endl;
	else cout << "YES" << endl;

	return 0;

}

Measured memory_bytes: 3632
input = require('fs').readFileSync('/dev/stdin', 'utf8')
lines = input.split('\n')
line = lines.shift().split(' ')
N = line[0] * 1
Q = line[1] * 1 
S = lines.shift()
a = [0]
cnt = 0
for (i=0; i<S.length-1; i++) {
    if (S[i] == 'A' && S[i+1] == 'C') {
        cnt++
    }
    a[i+1] = cnt
}
for (i=0; i<Q; i++) {
    line = lines[i].split(' ')
    l = line[0] * 1
    r = line[1] * 1
    console.log(a[r-1] - a[l-1])
}


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

using namespace std;

#define int long long 
#define MOD 1000000007

int f(int a,int b,int c){
	return a*a*c - 2*b*a;
}

signed main(){
	//freopen("a.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int a[n];
	int b = 0;
	int c = 0;
	for(int i=0;i<n;i++){
		cin >> a[i];
		b += a[i];
		c += a[i]*a[i];
	}
	int l = -101,h = 101;
	for(int i=0;i<100;i++){
		int m1 = 2*l + h;
		int m2 = 2*h + l;
		m1 /= 3;
		m2 /= 3;
		if(f(m1,b,n) < f(m2,b,n)){
			h = m2;
		}
		else l = m1;
	}
	int cur = 100000000;
	for(int i=l;i<=h;i++){
		cur = min(cur,f(i,b,n) + c);
	}
	cout << cur << "\n";
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n;
	int i, j;
	int a[5000];
	long long ans;
	long long buf;
	
	while (1){
		scanf("%d", &n);
		if (n == 0){
			break;
		}
		
		for (i = 0; i < n; i++){
			scanf("%d", &a[i]);
		}
		
		ans = -5000000000;
		for (i = 0; i < n; i++){
			if (ans < a[i]){
				ans = a[i];
			}
		}
		
		for (i = 0; i < n - 1; i++){/*スタート*/
			buf = a[i];
			for (j = i + 1; j < n; j++){/*ゴール*/
				buf += a[j];
				if (ans < buf){
					ans = buf;
				}
			}
		}
		
		
		printf("%lld\n", ans);
	}
	
	return (0);
}
/* 音ゲーの精度がよくなりますように。 */

Measured memory_bytes: 620
#include <iostream>
#include <cmath>
#include <vector>
#include <utility>
using namespace std;

#define EPS 1e-8
#define sqr(x) ((x)*(x))
#define fi first
#define se second

class circle {
	public:
		int x, y, r;
		circle(int x, int y, int r) {
			this->x = x;
			this->y = y;
			this->r = r;
		}

		bool is_cross(int x1, int y1, int x2, int y2) {
			pair<int,int> range;
			int x0 = x, y0 = y;
			if(x1 == x2 && y1 == y2) {
				return false;
			}
			if(x1 == x2) {
				swap(x1, y1);
				swap(x2, y2);
				swap(x0, y0);
			}

			range.fi = min(x1, x2);
			range.se = max(x1, x2);

			double a, b;
			a = (double)(y2 - y1) / (x2 - x1);
			b = y1 - a * x1;

			double d;
			d = sqr(x0 - a * (b - y0)) - (1 + sqr(a)) * (sqr(x0) + sqr(b - y0) - sqr(r));

			if(d < 0)
				return false;

			double z, zz;
			z  = (x0 - a * (b - y0) - sqrt(d)) / (1 + sqr(a));
			zz = (x0 - a * (b - y0) + sqrt(d)) / (1 + sqr(a));

			if((range.fi <= z && z <= range.se) || (range.fi <= zz && zz <= range.se))
				return true;
			return false;
		}
};

int main(void) {
	int n, m;

	while(cin >> n, n) {
		vector<circle> v;
		for(int i = 0; i < n; i++) {
			int x, y, r;
			cin >> x >> y >> r;
			v.push_back(circle(x,y,r));
		}
		cin >> m;
		for(int i = 0; i < m; i++) {
			int x1, y1, x2, y2;
			bool flag = false;
			cin >> x1 >> y1 >> x2 >> y2;
			for(int j = 0; j < v.size(); j++) {
				if(v[j].is_cross(x1, y1, x2, y2))
					flag = true;
			}
			if(flag)
				cout << "Safe" << endl;
			else
				cout << "Danger" << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1192
N=int(input())
A=list(map(int,input().split()))
ans = []
for i in reversed(range(1, N+1)):
    a = A[i-1]
    for j in range(2, N+1):
        tmp = i * j
        if tmp > N:
            break
        a += A[tmp-1]
    if a % 2 == 1:
        ans.append(i)
    A[i-1] = a % 2
print(len(ans))
for a in ans:
    print(a)

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

int main()
{
    string s1,s2;
    getline(cin,s1);
    getline(cin,s2);
    int ans=0,i=0;
    while(i<s1.length())
    {
        if(s1[i]!=s2[i])
            ans++;
        i++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3912
#include<stdio.h>
#include<stdbool.h>
#define N 8
#define FREE -1
#define NOT_FREE 1

int row[N], col[N], dpos[2*N-1],dneg[2*N-1];
bool X[N][N];
void initialize(void){
  for(int i=0;i<N;i++){
    row[i]=FREE,col[i]= FREE;
  }
  for(int i=0;i<2*N-1;i++){
    dpos[i]=FREE,dneg[i]=FREE;
  }
}
void printboard(void){
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(X[i][j]){
	if(row[i]!= j)return;
      }
    }
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      printf((row[i]==j)?"Q":".");
    }
    printf("\n");
  }
}

  void recursive(int i){
    if(i==N){
      printboard();
      return;
    }
    for(int j=0;j<N;j++){
      if(NOT_FREE == col[j]||NOT_FREE == dpos[i+j]|| NOT_FREE == dneg[i-j+N-1])continue;
      row[i]=j;col[j]= dpos[i+j]=dneg[i-j+N-1]= NOT_FREE;
      recursive(i+1);
      row[i]=col[j]= dpos[i+j]=dneg[i-j+N-1]=FREE;
    }
  }

  
int main(){
  initialize();

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      X[i][j]=false;
    }
  }
 int k;
 scanf("%d",&k);
 for(int i=0;i<k;i++){
   int r,c;
   scanf("%d %d",&r,&c);
   X[r][c]=true;
 }
 recursive(0);

 return 0;
}



Measured memory_bytes: 2112
//AUTHOR: RAVAN_2070
//PUNE INSTITUTE OF COMPUTER TECHNOLOGY
/*                                                    
      I ♥ CLARICE STARLING...                                                               
        EXPLAINATION BELOW->
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<pair<ll,ll>> vii;
typedef pair<ll,ll> pii;
typedef map<ll,ll> mii;
#define MOD7 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define Test_cases ll TC;cin>>TC;while(TC--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define sp(x) fixed<<setprecision(x)
#define sz(x) (ll)(x.size())
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
const ll INF = (ll)2e18 + 77;
void solve()
{
    int n,i,j,k,cnt=0;cin>>n;
    vector<int>x(n);
   // set<pair<int,pair<int,int>>>s;
    fo(i,0,n)
    cin>>x[i];
    fo(i,0,n)
    {
        fo(j,i+1,n)
        {
                fo(k,j+1,n)
                {
                    if((x[j]!=x[k]&&x[i]!=x[j]&&x[i]!=x[k])&&(x[i]+x[j]>x[k])&&(x[j]+x[k]>x[i])&&(x[i]+x[k]>x[j]))cnt++;//s.insert(mp(x[i],mp(x[j],x[k])));
                }
            
        }
    }
  // cnt=sz(s);
    cout<<cnt<<"\n";
}
int main()
{
   fastio
   //Test_cases
   solve();
  return 0;
}
//**always check if you are not killing input in between
//map<ll,ll,greater<int>> to sort in descending order ,in iterator declaration no greater<int>
//if you want to apply lowerbound on set use s.lower_bound(key),not the one used for vector
// Syntax to create a min heap for priority queue priority_queue <int, vector<int>, greater<int>>; 
//for modinverse use modularexponention(x,M-2,M);
//for "each" subtraction from ans(ans-k) if(ans<0) do ans+=MOD,ans%=MOD
//vector<vector<int>>dp(201,vector<int>(n+1)); A way to initialize vector of vector
//string2=string1.substr(pos,length);if len no specified then till end
//void fill (ForwardIterator first, ForwardIterator last, const T& val);
//The range filled is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.


//If wrong on pretest 2 means logically wrong
/* TIPS FOR DEBUGGING
 * Check if values are not overflowing (use long long where required)
 * Check if ranges are inclusive or not.
 * Check properly if greedy will work or not before using it.
 * Check EDGE CASES!! Seriously, even in 2B, saving 8 points by being
 * 2 minutes faster will bite you in the ass if you don't make sure
 * it works on edge cases.
 * Keep adding to this list.
*/


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

int main(){
    string s;
    cin >> s;
    rep(i,s.length()){
        cout << "x";
    }
    cout << endl;

    return 0;
}









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

int main() {
	int n,k;
	cin>>n>>k;
	if (n==1) cout << k << endl;
	else if (k==1) cout << 1 << endl;
	else cout << k*int (pow((k-1),(n-1)))<<endl;
}

Measured memory_bytes: 256
R,C,K = map(int, input().split())
L = [[0]*C for _ in range(R)]
for _ in range(K):
    r,c,v = map(int, input().split())
    L[r-1][c-1] = v

dp0 = [[0]*C for _ in range(R)]
dp1 = [[0]*C for _ in range(R)]
dp2 = [[0]*C for _ in range(R)]
dp3 = [[0]*C for _ in range(R)]
for i in range(R):
    for j in range(C):
        if i == 0 and j == 0 and L[i][j] > 0:
            dp1[i][j] = L[i][j]
        elif i == 0:
            dp0[i][j] = dp0[i][j-1]
            dp1[i][j] = dp1[i][j-1]
            dp2[i][j] = dp2[i][j-1]
            dp3[i][j] = dp3[i][j-1]
            if L[i][j] > 0:
                dp1[i][j] = max(dp1[i][j], dp0[i][j-1]+L[i][j])
                dp2[i][j] = max(dp2[i][j], dp1[i][j-1]+L[i][j])
                dp3[i][j] = max(dp3[i][j], dp2[i][j-1]+L[i][j])
        elif j == 0:
            dp0[i][j] = max(dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
            if L[i][j] > 0:
                dp1[i][j] = dp0[i][j]+L[i][j]
        else:
            dp0[i][j] = max(dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j], dp0[i][j-1])
            dp1[i][j] = dp1[i][j-1]
            dp2[i][j] = dp2[i][j-1]
            dp3[i][j] = dp3[i][j-1]
            if L[i][j] > 0:
                dp1[i][j] = max(dp1[i][j], dp0[i][j]+L[i][j])
                dp2[i][j] = max(dp2[i][j], dp1[i][j-1]+L[i][j])
                dp3[i][j] = max(dp3[i][j], dp2[i][j-1]+L[i][j])

print(max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))

Measured memory_bytes: 429720
public class Main {
  private static void solve() {
    long N = ni();
    
    
    for (long h = 1; h <= 3500; h ++) {
      for (long n = h; n <= 3500; n ++) {
        long x = N * h * n;
        long y = 4 * h * n - N * n - N * h;
        
        if (y > 0 && x % y == 0) {
          System.out.println(h + " " + n + " " + (x / y));
          return;
        }
      }
    }
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}




Measured memory_bytes: 23504
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007

using namespace std;

int main()
{

#ifdef WIN32
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ll X, K, D;
    cin >> X >> K >> D;
    X = abs(X);

    ll straight = min(K, X / D);
    K -= straight;
    X -= straight * D;

    if (K % 2 == 0)
    {
        cout << X << endl;
    }
    else
    {
        cout << D - X << endl;
    }

    return 0;
}

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


typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ld;

typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 3;

#define _  %  MOD
#define __ %= MOD

#define      each(it,s)        for(auto it = s.begin(); it != s.end(); ++it)
#define      sortA(v)          sort(v.begin(), v.end())
#define      sortD(v)          sort(v.begin(), v.end(), greater<auto>())
#define      fill(a)           memset(a, 0, sizeof (a))

#define      swap(a,b)        {a=a+b;b=a-b;a=a-b;}
#define      rep(i, n)         for(ll i = 0; i < (n); ++i)
#define      repA(i, a, n)     for(ll i = a; i <= (n); ++i)
#define      repD(i, a, n)     for(ll i = a; i >= (n); --i)
#define watch(x) cout << (#x) << " is " << (x) <<endl

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define fbo find_by_order
#define ook order_of_key

ll gcd(ll a,ll b){if(b==0) return a; else return gcd(b,a%b);}
ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=res*x;y=y>>1;x=x*x;}return res;} // modular exponent

int main()
{
    ios_base::sync_with_stdio(false); // don't use printf and scanf
    cin.tie(NULL); // cout<<fixed<<setprecision
    set<string> st;
    ll n;
    cin>>n;
    rep(i,n)
    {
        string s;
        cin>>s;
        st.insert(s);
    }
    cout<<st.size()<<'\n';
    return 0;
}
// JUST ASK YOURSELF DID YOU GIVE YOUR BEST ? ISSE ZYADA
// KUCH KAR BHI NAHI SAKTE !! ENJOY AND GIVE YOUR BEST!!


Measured memory_bytes: 19184
#include<stdio.h>
int main()
{
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    if(c>a) a=c;
    if(b>d) b=d;
    if(b>a) printf("%d",b-a);
    else printf("0");
    return 0;
}

Measured memory_bytes: 128
#include<iostream>

using namespace std;
int main(){
  int long long n,k;
  cin>>n>>k;
  if(k%2==1){
    cout<<(n/k)*(n/k)*(n/k)<<endl;
  }
  else{
    int long long wa=((n+k/2)/k)*((n+k/2)/k)*((n+k/2)/k);
    int long long wawa=(n/k)*(n/k)*(n/k);
    cout<<wa+wawa<<endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
  
{
int n;
  cin>>n;
  int r=n%10;
  if(r==2 || r==4 || r==5 || r==7 ||r==9)
    cout<<"hon"<<endl;
  else if(r==0 || r==1 || r==6 || r==8)
    cout<<"pon"<<endl;
  else
    cout<<"bon"<<endl;
  
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
#define MAX 100005
#define NIL -1

struct node{
    int p, l, r;
};

node t[MAX];
int n, d[MAX], h[MAX];

void AllDepth(int u, int p){
    if(u == NIL) return;
    d[u] = p;
    AllDepth(t[u].r, p+1);
    AllDepth(t[u].l, p+1);
}
int AllHeight(int u){
    int h1 = 0, h2 = 0;
    if(t[u].r != NIL) h1 = AllHeight(t[u].r)+1;
    if(t[u].l != NIL) h2 = AllHeight(t[u].l)+1;
    h[u] = max(h1, h2);
    return h[u];
}
int GetSidling(int u){
    if(t[u].p == NIL) return NIL;
    if(t[t[u].p].l != u && t[t[u].p].l != NIL)return t[t[u].p].l;
    else if(t[t[u].p].r != u && t[t[u].p].r != NIL) return t[t[u].p].r;
    return NIL;
}

int main() {
    int root, left, right, id;
    cin >> n;
    for(int i = 0; i < n; i++) t[i].p = NIL;
    for(int i = 0; i < n; i++) {
        cin >> id >> left >> right;
        t[id].l = left;
        t[id].r = right;
        if(left != NIL)t[left].p = id;
        if(right != NIL)t[right].p = id;
    }
    for(int i = 0; i < n; i++) {
        if(t[i].p == NIL)root = i;
    }
    AllDepth(root, 0);
    AllHeight(root);
    for(int i = 0; i < n; i++) {
        int degree=0;
        cout << "node " << i;
        cout << ": parent = " << t[i].p;
        cout << ", sibling = " << GetSidling(i);
        if(t[i].l != NIL) degree++;
        if(t[i].r != NIL) degree++;
        cout << ", degree = " << degree;
        cout << ", depth = " << d[i];
        cout << ", height = " << h[i];
        if(t[i].p == NIL) cout << ", root";
        else if(t[i].l == NIL && t[i].r == NIL) cout << ", leaf";
        else cout << ", internal node";
        cout << endl;
    }
    
}


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

int main()
{
  vector<int> vec(3);
  cin >> vec.at(0) >> vec.at(1) >> vec.at(2);
  
  sort(vec.begin(), vec.end());
  cout << vec.at(0) + vec.at(1) << endl;
}

Measured memory_bytes: 256
# Problem E - Yutori

# input
N, K, C = map(int, input().split())
S = list(input())

# initialization
left_list = [0]*(N+1)
right_list = [0]*(N+1)

# count
k = 1
i = 0
while i<N:
    if S[i]=='o':
        left_list[i+1] = k
        k += 1
        i += C + 1
    else:
        i += 1

k = K
i = N - 1
while i>=0:
    if S[i]=='o':
        right_list[i+1] = k
        k -= 1
        i -= C + 1
    else:
        i -= 1

# check
for i in range(1, N+1):
    if not left_list[i]==0 and not right_list[i]==0:
        if left_list[i]==right_list[i]:
            print(i)


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

const int N = 100005;
int n, a[N];
bool solve() {
	int odd = 0, even = 0, g = 0;
	for (int i = 1; i <= n; ++i)
		++(a[i] & 1 ? odd : even);
	if (even & 1) return 1;
	if (odd > 1) return 0;
	for (int i = 1; i <= n; ++i) if (a[i] == 1) return 0; else if (a[i] & 1) --a[i];
	for (int i = 1; i <= n; ++i) g = std::__gcd(g, a[i]);
	for (int i = 1; i <= n; ++i) a[i] /= g;
	return !solve();
}

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n;
	for (int i = 1; i <= n; ++i) std::cin >> a[i];
	std::cout << (solve() ? "First" : "Second") << '\n';
	return 0;
}

Measured memory_bytes: 640
package main
import (
    "bufio"
    "fmt"
    "math"
    "os"
    "strconv"
    "strings"
)

var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*10)

func main() {
    list := getStdinArr()
    A, _ := strconv.Atoi(list[0])
    B, _ := strconv.ParseFloat(list[1], 64)
    a := A
    b := int(math.Round(B * 100))
    fmt.Println((a*b)/100)
}


func getStdin() string {
    return readLine()
}
func getStdinInt() int {
    str := getStdin()
    res, _ := strconv.Atoi(str)
    return res
}
func getStdinintArr() []int {
    str := getStdin()
    list := strings.Split(str, " ")
    res := make([]int, len(list))
    for idx, v := range list {
        res[idx], _ = strconv.Atoi(v)
    }
    return res
}
func getStdinArr() []string {
    str := getStdin()
    list := strings.Split(str, " ")
    return list
}
func getStdinIntArr64() []int64 {
    str := getStdin()
    list := strings.Split(str, " ")
    res := make([]int64, len(list))
    for idx, v := range list {
        res[idx], _ = strconv.ParseInt(v, 10, 64)
    }
    return res
}
func readLine() string {
    buf := make([]byte, 0, 0)
    for {
        l, p, e := sc.ReadLine()
        if e != nil {
            panic(e)
        }
        buf = append(buf, l...)
        if !p {
            break
        }
    }
    return string(buf)
}

Measured memory_bytes: 2156
while gets
  a = $_.split.map(&:to_i)
  #a = $_.split(" ").map{|val| val.to_i}

  a.sort!.reverse!
  puts a*" "

  #puts a.join(" ")

  #for i in 0...a.size
  #  print " " if i != 0
  #  print a[i]
  #end
  #puts
end

Measured memory_bytes: 2296
#include <bits/stdc++.h>
#define FI(i,a,b) for(int i=(a);i<=(b);i++)
#define FD(i,b,a) for(int i=(b);i>=(a);i--)
#define len(a) int((a).size())
using namespace std;
using LL = long long;
using PII = pair<int, int>;

const int N = 505;
int C[N], S[N], F[N];

int main() {
    int n;
    scanf("%d", &n);
    vector<int> A;
    FI(i,1,n-1) scanf("%d%d%d", &C[i], &S[i], &F[i]);
    FI(i,1,n-1) {
        int t = 0;
        FI(j,i,n-1) {
            t = max(S[j], F[j] * (t / F[j] + (t%F[j]!=0)));
            t += C[j];
        }
        A.push_back(t);
    }
    for (auto x: A) printf("%d\n", x);
    printf("0\n");
        
}

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

int main() {
    string s1,s2;
    int cnt = 0;
    cin >> s1;
    for (int i=0; i<s1.size(); ++i) {
        s1[i] = tolower(s1[i]);
    }
    while (cin >> s2) {
        if (s2 == "END_OF_TEXT") break;
        for (int i=0; i<s2.size(); ++i) {
            s2[i] = tolower(s2[i]);
        }
        if (s2 == s1) ++cnt;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3192
H, W = list(map(int, input().split()))
A = []

for i in range(H):
    s = input()
    A.append(list(s))

# for i in range(H):
#     print(A[i])

di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

ans = True
for i in range(H):
    for j in range(W):
        # if (i == 0 and j == 0) or (i == H-1 and j == W-1):
        #     continue
        if A[i][j] == '#':
            ul = 0  # 上 or 左
            rd = 0  # 右 or 下
            for k in range(4):
                ni = i + di[k]
                nj = j + dj[k]
                if 0 <= ni < H and 0 <= nj < W:
                    if A[ni][nj] == '#':
                        if k == 0 or k == 1:
                            ul += 1
                        else:
                            rd += 1
            # print(i, j, ':', ul, rd)
            if i == 0 and j == 0:
                if not (ul == 0 and rd == 1):
                    ans = False
            elif i == H-1 and j == W-1:
                if not (ul == 1 and rd == 0):
                    ans = False
            else:
                if not (ul == 1 and rd == 1):
                    ans = False

if ans:
    print('Possible')
else:
    print('Impossible')


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int EX_GCD(int a, int b, int& x, int& y) {
    int d = a;
    if (b != 0) {
        d = EX_GCD(b, a % b, y, x);
        y -= (a / b) * x;
    }
    else {
        x = 1;
        y = 0;
    }
    return d;
}
 
int main()
{
    int a, b, x, y;
    cin >> a >> b;
    EX_GCD(a, b, x, y);
    cout << x << ' ' << y << endl;
    return 0;
}

Measured memory_bytes: 3096
#include<bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0;i--)
using namespace std;

int main(){
  string s;
  cin >> s;
  char c = 0;
  invrep(i,26){
    bool flag = true;
    rep(j,s.size()){
      if(s.at(j) == i+'a'){
        flag = false;
      }
    }
    if(flag){
      c = 'a' + i;
    }
  }
  if(c == 0){
    cout << "None" << endl;
  }else{
    cout << c << endl;
  }
    
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	/*ll t;
	cin >> t;
	while(t--){
      
    }
    * */
    ll s,w;
    cin >> s >> w;
    if(w>=s)
    cout << "unsafe"<<endl;
    else cout << "safe"<<endl;
}


Measured memory_bytes: 3624
#include <iostream>
using namespace std;
int main(void){
    // Here your code !
    long long int A,B,C;
    cin >> A >> B >> C;
    
    if(A%2 && B%2 && C%2){
        cout << min(A*B,min(B*C,A*C)) << endl;
    }else{
        cout << 0 << endl;
    }
    
}


Measured memory_bytes: 256
S = input()
if S == 'SAT':
    print(1)
    exit()
if S == 'FRI':
    print(2)
if S == 'THU':
    print(3)
if S == 'WED':
    print(4)
if S == 'TUE':
    print(5)
if S == 'MON':
    print(6)
if S == 'SUN':
    print(7)

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

import sys


def generate_default_spreadsheet():
    r, c = [int(row_col) for row_col in sys.stdin.readline().split()]
    sheet = [
                [int(row_num) for row_num in sys.stdin.readline().split()]
                for row in range(r)
            ]
    return c, sheet


def generate_spreadsheet_with_sums():
    orig_total_col, sheet_with_sums = generate_default_spreadsheet()

    sheet_with_sums.append([0 for col in range(orig_total_col)])

    for row in range(len(sheet_with_sums)-1):
        for col in range(len(sheet_with_sums[0])):
            sheet_with_sums[-1][col] += sheet_with_sums[row][col]

    for row in sheet_with_sums:
        row.append(sum(row))

    return sheet_with_sums


def print_summed_spreadsheet():
    sheet_with_sums = generate_spreadsheet_with_sums()
    [print(*row) for row in sheet_with_sums]


def main():
    print_summed_spreadsheet()


if __name__ == '__main__':
    main()

Measured memory_bytes: 8236
Q = int(input())
for i in range(Q):
    n = int(input())
    ans = 0
    while n >= 10:
        s = str(n)
        a = 0
        for i in range(len(s) - 1):
            a = max(a, int(s[:i + 1]) * int(s[i + 1:]))
        n = a
        ans += 1
    print(ans)


Measured memory_bytes: 5600
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    int a;
    string s;
    cin >> a >> s;
    if(a < 3200)
        cout << "red";
    else
        cout << s;
    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;

const int mod = 1e9+7;
const int INF = 2000000;

int main() {
    int n;
    cin >> n;
    vector<int> C1(100010,0),C2(100010,0);
    int v[n];
    rep(i,n) cin >> v[i];
    for(int i=0;i<n;++i) {
        if(i & 1) ++C2[v[i]];
        else ++C1[v[i]];
    }
    int ind1 = max_element(C1.begin(), C1.end())-C1.begin();
    int ind2 = max_element(C2.begin(), C2.end())-C2.begin();
    int mval1 = C1[ind1], mval2 = C2[ind2];
    C1[ind1] = 0;
    C2[ind2] = 0;
    int sec1 = *max_element(C1.begin(), C1.end());
    int sec2 = *max_element(C2.begin(), C2.end());
    int ans;
    if(ind1 == ind2) ans = min(n-mval1-sec2, n-mval2-sec1);
    else ans = n - mval1 - mval2;
    cout << ans << endl;
}


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

int main() {
  string S;
  cin >> S;
  // 隣同士比較して同じなら右側を変える
  int N = S.size(), answer = 0;
  for (int i=0; i<N-1; i++) {
    if (S.at(i)==S.at(i+1)) {
      if (S.at(i+1)=='0') {
        S.at(i+1) = '1';
      }
      else {
        S.at(i+1) = '0';
      }
      answer++;
    }
  }
  cout << answer << endl;
}

Measured memory_bytes: 512
h,w=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(input()))
dp=[]
for i in range(h):
    dp.append([0]*w)
c=1
for i in range(w):
    if l[0][i]=='#':
        c=0
    dp[0][i]=c
c=1
for i in range(h):
    if l[i][0]=='#':
        c=0
    dp[i][0]=c
for i in range(1,h):
    for j in  range(1,w):
        if l[i][j]=='.':
            dp[i][j]=dp[i-1][j]+dp[i][j-1]
        else:
            dp[i][j]=0
print(dp[h-1][w-1]%1000000007)

        
        


Measured memory_bytes: 244444
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <regex>



using ull = unsigned long long;
using ll = long long;

using namespace std;


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

	for (int i = 1; i <= 10; i++)
	{
		if (i * 1000 - n >= 0) {
			cout << i * 1000 - n;
			break;
		}
	}
	
	return 0;
	
}

Measured memory_bytes: 3180
#include "bits/stdc++.h"

#define int long long

using namespace std;

const int mod = 1e9 + 7;

int32_t main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    vector<int> dp(1 << n, 0);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if (__builtin_popcount(mask) != i) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) == 0 && a[i][j]) {
                    dp[mask | (1 << j)] += dp[mask];
                    dp[mask | (1 << j)] %= mod;
                }
            }
        }
    }
    cout << dp[(1 << n) - 1] << endl;
    return 0;
}


Measured memory_bytes: 19532
class Solution:
    def solve(self, N: int, A) -> str:

        for a in A:
            if a % 2 == 0:
                if a % 3 != 0 and a % 5 != 0:
                    return "DENIED"

        return "APPROVED"


if __name__ == '__main__':

    # standard input
    N = int(input())
    A = list(map(int, input().split()))

    # solve
    solution = Solution()
    print(solution.solve(N, A))


Measured memory_bytes: 2940
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author cunbidun
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABallDistribution solver = new ABallDistribution();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABallDistribution {
        private InputReader in;
        private PrintWriter out;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            this.in = in;
            this.out = out;
            int n = in.nextInt();
            int k = in.nextInt();
            if (k == 1) {
                out.println(0);
                return;
            }
            for (int i = 1; i < k; i++) {
                n--;
                if (n < 0) {
                    out.println(0);
                    return;
                }
            }

            out.println(n - 1);
        }

    }

    static class InputReader extends InputStream {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        private static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }
}



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

int main() {
  double W, H, x, y;
  cin >> W >> H >> x >> y;
  cout << setprecision(15) << W*H/2 << endl;
  if(W/2.0 == x && H/2.0 == y){
    cout << 1 << endl;
  }
  else{
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
N = int(input())
X = []
U = []
count = 0

for _ in range(N):
    x, u = map(str, input().split())
    X.append(float(x))
    if u == 'JPY':
        U.append(1)
    else:
        U.append(380000)

for n in range(N):
    count += X[n] * U[n]

print(count)





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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> l(N);
  
  for (int i = 0; i < N; i++) {
    cin >> l.at(i);
  }
  
  sort(l.begin(), l.end());
  reverse(l.begin(), l.end());
  
  int ans = 0;
  
  for (int j = 0; j < K; j++) {
    ans += l.at(j);
  }
  cout << ans << endl;
  
}

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

int main() {
    auto mochi = std::set<int>();
    auto n = 0;
    std::cin >> n;
    for (auto i_ = 0; i_ < n; ++i_) {
        auto l = 0;
        std::cin >> l;
        mochi.insert(l);
    }
    std::cout << mochi.size() << std::endl;
    return 0;
}

Measured memory_bytes: 256
object Main extends App {
  val Array(n, x) = io.StdIn.readLine.split(" ").map(_.toInt)
  var costs: Array[Int] = new Array(n)
  for(i <- 0 until n) costs(i) = io.StdIn.readInt
  val sum = costs.sum
  val ans = n + (x-sum) / costs.min
  println(ans)
}


Measured memory_bytes: 27332
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
template <typename T> 
using lim = numeric_limits<T>;
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

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

const int N = 2e5;
int h[N+1];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
    int n; cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> h[i];
    }

    ll ans = 0;
    unordered_map<int,int> um;
    for (int i = 1; i <= n; i++){
        ans += um[i-h[i]];
        um[i+h[i]]++;
    }  
    cout << ans << "\n";
}

Measured memory_bytes: 19284
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <utility>

int main(){
  std::string s;
  std::cin >> s;
  int n=s.length();
  long long ans = (long long)n*(n-1)/2;
  std::map<char, int > mp;
  for (int i=0; i<n; i++){
    mp[s[i]]++;
  }
  for (auto &entry: mp){
    ans -= (long long)(entry.second-1)*entry.second/2;;
  }
  ans++;
  std::cout << ans << std::endl;
  return 0;
}

Measured memory_bytes: 832
// ConsoleApplication1.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//


#include <iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
using namespace std;
#define rep(i, n) for(long i = 0; i < n; i++)
#define erep(i, n) for(long i = 1; i <= n; i++)
#define show(ans) cout << ans << endl
const long MOD = 1000000007;

int main() {
	double a, b, ans;
	cin >> a >> b;
	ans = a / b;
	cout << setprecision(9) << ans << endl;
	return 0;

}
// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント: 
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します 
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこのプロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します


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

typedef long long ll;
typedef vector<int> vi;

const double PI=acos(-1.0);

int N,K; 
// vi A;
void input()
{
    cin>>N>>K;
    // for(int i=0;i<N;++i){
    //     int a; cin>>a; A.emplace_back(a);
    // }
}

void solve()
{
    int ans=(N-1)/(K-1);
    if((N-1)%(K-1)!=0) ++ans;
    cout<<ans<<endl;
}

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

Measured memory_bytes: 3620
h,w=map(int,input().split())
s=eval('list(input()),'*h)
r=range
for i in r(h):
  for j in r(w):
    c=0
    for a in r(i-1,i+2):
      for b in r(j-1,j+2):
        c+=all((min(a,b)>=0,a<h,b<w))and s[a][b]=='#'
    if s[i][j]=='.':s[i][j]=c
for a in s:print(*a,sep='')

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

using namespace std;

const int N = 1e5 + 5, MAX_H = 1e4 + 5, inf = (int)1e9 + 123;
int n, K, h[N], dp[N];
deque<int> deq[MAX_H];

struct It {
    int node[MAX_H << 2];
    It () {
        for (int i = 0; i < (MAX_H << 2); ++i) node[i] = inf;
    }
    void update (int nd, int Left, int Right, int pos, int val) {
        if (pos < Left || Right < pos) return ;
        if (Left == Right) {
            node[nd] = val; return ;
        }
        int mid = Left + Right >> 1;
        update(nd << 1, Left, mid, pos, val); update(nd << 1 | 1, mid + 1, Right, pos, val);
        node[nd] = min(node[nd << 1], node[nd << 1 | 1]);
    }
    int get (int nd, int Left, int Right, int l, int r) {
        if (Right < l || r < Left) return inf;
        if (l <= Left && Right <= r) return node[nd];
        int mid = Left + Right >> 1;
        return min(get(nd << 1, Left, mid, l, r), get(nd << 1 | 1, mid + 1, Right, l, r) );
    }
} it[2];

int main () {
    scanf("%d", &n); K = 2;
    for (int i = 1; i <= n; ++i) scanf("%d", h + i);

    for (int i = 2; i <= n; ++i) {
        if (i - K - 1 > 0) {
            int id = h[i - K - 1];
            while (!deq[id].empty() && deq[id].front() < i - K) deq[id].pop_front();
            it[0].update(1, 1, MAX_H - 5, id, (deq[id].empty() ? inf : dp[deq[id].front()] - id) );
            it[1].update(1, 1, MAX_H - 5, id, (deq[id].empty() ? inf : dp[deq[id].front()] + id) );
        }
        int id = h[i - 1];
        while (!deq[id].empty() && dp[ deq[id].back() ] >= dp[i - 1]) deq[id].pop_back();
        deq[id].push_back(i - 1);
        it[0].update(1, 1, MAX_H - 5, id, (deq[id].empty() ? inf : dp[deq[id].front()] - id) );
        it[1].update(1, 1, MAX_H - 5, id, (deq[id].empty() ? inf : dp[deq[id].front()] + id) );
        dp[i] = min(it[0].get(1, 1, MAX_H - 5, 1, h[i]) + h[i], it[1].get(1, 1, MAX_H - 5, h[i], MAX_H - 5) - h[i]);
    }

    cout << dp[n];

    return 0;
}


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

using namespace std;

using ll = long long;
using ld = long double;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<int> b(n + 1);
    for (int i = n; 1 <= i; --i) {
        int sum = 0;
        for (int j = 2; i * j <= n; ++j)
            sum += b[i * j];

        if ((a[i] == 1 && (sum % 2 == 0))
            || (a[i] == 0 && (sum % 2 == 1)))
            b[i] = 1;
    }

    int m = count(b.begin(), b.end(), 1);
    cout << m << "\n";
    for (int i = 1; i <= n; ++i)
        if (b[i] == 1) cout << i << "\n";
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    solve();

    return 0;
}


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

int main(){
int N;
  cin >> N;
  vector<int> x(N),y(N),h(N);
  for(int i=0;i<N;i++){
    cin >> x[i] >> y[i] >> h[i];
  }
int max=100;
  for(int posy=0;posy<=max;posy++){
    for(int posx=0;posx<=max;posx++){
    int needh=-1;
      for(int i=0;i<N;i++){
        if(h[i]>0){
          int tmp=h[i]+abs(posy-y[i])+abs(posx-x[i]);
          if(needh==-1){
           needh=tmp;
          }
          else{
            if(needh!=tmp){
            needh=-2;
            break;
            }
          }
        }
      }
     if(needh==-2) continue;
     for(int i=0;i<N;i++){
       if(h[i]==0){
       int dist = abs(posy-y[i])+abs(posx-x[i]);
         if(needh>dist){
           needh=-2;
           break;
         }
       }
     } 
     if(needh==-2)continue;
     cout << posx << " " << posy << " " << needh << endl;
    }
  }


}

Measured memory_bytes: 3640
#[allow(unused_imports)]
use proconio::{fastout, input, marker::*};

#[fastout]
fn main() {
    input! {
        n: usize,
        l: [u64; n],
    }

    let mut ans = 0;

    for i in 0..n {
        for j in (i+1)..n {
            if l[i] == l[j] {
                continue;
            }
            for k in (j+1)..n {
                if l[i] == l[k] || l[j] == l[k] {
                    continue;
                }

                if l[i] + l[j] <= l[k] || l[j] + l[k] <= l[i] || l[k] + l[i] <= l[j] {
                    continue;
                }
                // println!("{} {} {} = {} {} {}", i+1, j+1, k+1, l[i], l[j], l[k]);
                ans += 1;
            }
        }
    }

    println!("{}", ans);
}


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


int main() {
    int64_t A, B, ans;
    cin >> A >> B;
    int64_t mx = max(A, B);
    bool is_ans = false;
    for (int64_t i=0; i < mx; i++) {
        if (abs(A - i) == abs(B - i)) {
            ans = i;
            is_ans = true;
            break;
        }
    }

    if (is_ans) {
        cout << ans << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import fractions
from functools import reduce

N = int(input())
A = list(map(int, input().split()))

p = 10**9+7

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

lcm = lcm(*A)

B = [lcm//i for i in A]

print(sum(B)%p)

Measured memory_bytes: 264700
n = int(input())
p_list = list(map(int, input().split()))
ans = 0
for i in range(1, n-1):
    mini_list = p_list[i-1:i+2]
    sorted_mini_list = sorted(mini_list)
    if mini_list[1] == sorted_mini_list[1]:
        ans += 1

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const LL LLINF = 1e16;

int dp[3340][3340];
int main(){
    string s, t;
    cin >> s >> t;
    rep(i, s.size()+1){
        rep(j, t.size()+1){
            chmax(dp[i+1][j], dp[i][j]);
            chmax(dp[i][j+1], dp[i][j]);
            if(s[i] == t[j]) chmax(dp[i+1][j+1], dp[i][j] + 1);
            // cout << dp[i][j];
        }
        // cout << endl;
    }
    string ans = "";
    for(int i=s.size(),j=t.size(); i > 0 && j > 0;){
        if(dp[i-1][j-1] == dp[i][j]-1){
            while(dp[i-1][j] == dp[i][j]) i--;
            while(dp[i][j-1] == dp[i][j]) j--;
            // cout << i <<" " << j << endl;
            ans += s[i-1];
            i--; j--;
        }
        else if(dp[i-1][j] == dp[i][j]) i--;
        else j--;
    }
    reverse(all(ans));
    cout << ans << endl;



}


Measured memory_bytes: 41216
//By Don4ick
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qwer1234

const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};

const int N = (int)1e5 + 228;

using namespace std;

int n, m, tin[N], timer, fup[N], ans = 0;
vector < pair < int, int > > g[N];
bool was[N];

void dfs(int v, int pr)
{
	was[v] = true;
	tin[v] = fup[v] = ++timer;
	for (auto e : g[v])
	{
		int to = e.first;
		if (to == pr)
			continue;
		if (was[to])
			fup[v] = min(tin[to], fup[v]);
		else
		{
			dfs(to, v);
			fup[v] = min(fup[to], fup[v]);
			if (fup[to] > tin[v])
			{
			 	ans++;
			}
		}
	}	
}

int main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	//cout.tie(NULL);

	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

	scanf("%d%d", &n, &m);
	forn(i, m)
	{
		int v, u;
		scanf("%d%d", &v, &u);
		g[v].pb({u, i});
		g[u].pb({v, i});
	}
	dfs(1, -1);
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 2560