akhauriyash/Code-Regression huggingface dataset:
output = []

while True:
    length = int(input())

    if length == 0:
        break

    oldList = [int(item) for item in input().split(" ")]
    operateCount = 0

    while True:

        numberCount = {}
        for item in oldList:
            if item in numberCount:
                numberCount[item] += 1
            else:
                numberCount[item] = 1

        newList = []
        for number in oldList:
            newList.append(numberCount[number])

        if oldList == newList:
            output.append(str(operateCount))
            items = [str(item) for item in newList]
            items = " ".join(items)
            output.append(items)
            break

        operateCount += 1
        oldList = newList

print("\n".join(output))



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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//main code

// 条件
// 0. 目標より大きい数字が存在する
// 1. 互いに素な組が存在する
// 2. なかった時、目標より大きい数字

LL gcd(LL bigger,LL smaller) {
    if (bigger % smaller != 0) {
        return gcd(smaller,(bigger % smaller));
    }
    return smaller;
}

int main(int argc, char const* argv[])
{
    int N,K;
    string ok = "POSSIBLE", ng = "IMPOSSIBLE";
    cin >> N >> K;
    VI a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    SORT(a);

    if (N == 1) {
        if (a[0] != K) {
            cout << ng << endl;
            return 0;
        }
        else {
            cout << ok << endl;
            return 0;
        }
    }

    LL whole_gcd = gcd(a[0],a[1]);
    for (int i = 2; i < N; i++) {
        whole_gcd = gcd(whole_gcd,a[i]);
    }

    for (int i = a.back(); i >= K; i -= whole_gcd) {
        if (i == K) {
            cout << ok << endl;
            return 0;
        }
    }

    cout << ng << endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;

int main(){
	int n;
	cin >> n;
	int ans = 1;
	for(int i = 2; i <= sqrt(n); i++){
		int j = i;
		while(j * i <= n){
			ans = max(ans, j * i);
			j = j * i;
		}
	}

	cout << ans << endl;
}

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

int main()
{
	int a, b,i,j;
	while (1)
	{
		cin >> a >> b;
		if (a == 0 && b == 0)break;
		for(i = 0;i <a;i++)
		{
			for (j = 0; j < b; j++)
			{
				cout << '#';
			}
			cout << endl;
		}
		cout << endl;
	}
	return 0;
}

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

int main() {
    int index0 = 0, index1 = 0;
    string s;
    cin >> s;
    rep(i, s.size()) {
        if (s[i] != '0' && i % 2 == 0)
            index0++;
        if (s[i] != '1' && i % 2 == 1)
            index0++;
        if (s[i] != '1' && i % 2 == 0)
            index1++;
        if (s[i] != '0' && i % 2 == 1)
            index1++;
    }
    cout << min(index0, index1) << endl;
    return 0;
}

Measured memory_bytes: 3720
import numpy as np

n,m,x = (int(x) for x in input().split())
C=[]
A=[]
for i in range(n):
    c,*a = (int(x) for x in input().split())
    C.append(c)
    A.append(a)

buy = [{"c":0,"a":np.zeros(m)}]
for i in range(len(C)):
    temp = []
    for j in buy:
        temp.append(j)
        temp.append({"c":j["c"]+C[i],"a":j["a"]+np.array(A[i])})
    buy = temp

#print(buy)
    
res = 10**7
for i in buy:
    if np.all(i["a"]>=x):
        res = min(i["c"],res)
if res == 10**7:
    res = -1
    
print(res)

Measured memory_bytes: 28696
n = int(input())

sum_list = []
for i in range(1, int(n / 2) + 1):
    a = i
    b = n - i
    sum_a = 0
    for a_i in range(len(str(a))):
        sum_a += int(str(a)[a_i])
    sum_b = 0
    for b_i in range(len(str(b))):
        sum_b += int(str(b)[b_i])
    sum_list.append(sum_a + sum_b)

print(min(sum_list))

Measured memory_bytes: 3480
#include <bits/stdc++.h>
    #include <chrono>
  
    using namespace std;
    using namespace std::chrono; 
 
    typedef long long int ll;
 
    #define MOD (ll)(1e9+7)
    #define endl "\n"
    #define pb push_back
    #define TEST_CASES  ll t;cin>>t;while(t--)
    #define forn(i,a,n) for (int i = a; i < n; ++i)
    #define f first
    #define s second
    #define all(x) x.begin(), x.end()
    
    ll powD(ll x,ll y){
      ll res = 1;
      while(y > 0){
        if(y & 1)
          res = (res*x)%MOD;
        x = (x*x)%MOD;
        y = y>>1;
      }
      return res;
    }
  
    int main()
    {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      int n;
      cin>>n;
      vector<ll> a(n),b(n);
      forn(i,0,n){
        cin>>a[i];
        cin>>b[i];
      }
      sort(all(a));
      sort(all(b));
      ll ans;
      if(n%2)
        ans = b[n/2]-a[n/2]+1;
      else{
        ans = b[n/2-1]+b[n/2] - a[n/2-1]-a[n/2]+1;
      }
      cout<<ans<<endl;

    }
    


Measured memory_bytes: 6348
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;

int main(){
  int n, m;cin>>n>>m;
  int all_cost[] = {2, 5, 5, 4, 5, 6, 3, 7, 6};
  vector<int> dp(n+1, -INF); // dp[i+1] := i本使って作る整数の最大桁数
  vector<P> cost(m);
  rep(i, m){
    int a;cin>>a;
    cost[i] = P(-a, all_cost[a-1]);
  }
  sort(cost.begin(), cost.end());
  dp[0] = 0;
  repb(i, 1, n+1){
    rep(j, m){
      if(i-cost[j].second<0)continue;
      dp[i] = max(dp[i], dp[i-cost[j].second]+1);
    }
  }
  while(n>0){
    rep(i, m){
      if(n-cost[i].second<0 || dp[n]-1!=dp[n-cost[i].second])continue;
      cout<<-cost[i].first;n -= cost[i].second;break;
    }
  }
  cout<<endl;
  // for(auto& e: dp)cout<<e<<" ";cout<<endl;
  // system("read -n 1 -s -p \"Press any key to continue...\"");
}


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

vector<int> dijkstra(int N, vector< vector< pair<int,int> > > &G){
  int INF = 1000000000;
  vector<int> ret(N,INF);
  priority_queue< pair<int,int> > wait;
  wait.emplace(0,0);
  while(!wait.empty()){
    int v = wait.top().second, cost = -wait.top().first;
    wait.pop();
    if(cost >= ret[v]) continue;
    ret[v] = cost;
    for(int i = 0; i < G[v].size(); ++i){
      int next = G[v][i].first, c = G[v][i].second;
      if(cost + c < ret[next]){
        wait.emplace(-c-cost,next);
      }
    }
  }
  return ret;
}

int main(){
  int N;
  cin >> N;
  vector<int> p(N);
  for(int i = 0; i < N; ++i) cin >> p[i];
  vector<int> q(N,-1);
  for(int i = 0; i < N; ++i){
    map<int,int> visited;
    visited[i] = 1;
    if(!p[i]){
      q[i] = i;
      continue;
    }
    int next = i+p[i], t;
    while(!visited[next]){
      if(q[next] != -1){
        t = q[next];
        break;
      }
      if(!p[next]){
        t = next;
        break;
      }
      ++visited[next];
      next += p[next];
    }
    if(visited[next] > 0) t = N;
    for(map<int,int>::iterator itr = visited.begin(); itr != visited.end(); ++itr){
      if(itr->second > 0) q[itr->first] = t;
    }
  }
  /*
  cout << "q : " ;
  for(int i = 0; i < N; ++i){
    cout << q[i] << " | ";
  }
  cout << endl;
  */
  vector< vector< pair<int,int> > > G(N);
  for(int i = 0; i < N; ++i){
    if(q[i] == N) continue;
    if(q[i] != i){
      G[i].emplace_back(q[i],0);
      continue;
    }
    for(int j = 1; j <= 6; ++j)
      if(i+j < N)
        G[i].emplace_back(i+j,1);
  }
  /*
  for(int i = 0; i < N; ++i){
    cout << i << " : ";
    for(int j = 0; j < G[i].size(); ++j){
      cout << "(" << G[i][j].first << " , " << G[i][j].second << ") | ";
    }
    cout << endl;
  }
  */
  cout << dijkstra(N,G)[N-1] << endl;
  return 0;
}

Measured memory_bytes: 11024
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,w,k;
  cin >> h >> w >> k;
  char s[h][w];
  int ans[h][w] = {};
  int i,j,kk;
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      cin >> s[i][j];
    }
  }
  int ww[h] = {};
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      if(s[i][j]=='#')ww[i]++;
    }
  }
  int tmpU = 0;
  int tmpL = 0;
  int tmpR = 0;
  int tmpD = 0;
  int cnt = 1;
  for(i=0;i<h;i++){
    if(ww[h]>0){
      tmpD = i;
      break;
    }
  }
int chk = 0;
  for(i=tmpD;i<h;i++){
    chk = 0;
    tmpL = 0;
    if(ww[i]>0){
      tmpD = i;
      chk = 1;
    }
    while(ww[i]>0){
      if(ww[i]==1){
        tmpR = w-1;
      }else{
        for(j=tmpL;j<w;j++){
          if(s[i][j]=='#'){
            tmpR = j;
            break;
          }
        }
      }
      for(j=tmpU;j<=tmpD;j++){
        for(kk=tmpL;kk<=tmpR;kk++){
          ans[j][kk] = cnt;
        }
      }
      cnt++;
      tmpL = tmpR+1;
      tmpR = tmpL;
      ww[i]--;
    }
    if(chk == 1) tmpU = tmpD + 1;
  }
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      if(ans[i][j] == 0)ans[i][j] = ans[i-1][j];
    }
  }
  
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      cout << ans[i][j] << " ";
    }
    cout << endl;
  }




}


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

int main() {
    int n, m, a;
    while(cin >> n >> m >> a, n) {
        vector<tuple<int, int, int>> lines(m);
        for(int i=0; i<m; ++i) {
            int h, p, q;
            cin >> h >> p >> q;
            lines[i] = make_tuple(h, p, q);
        }
        sort(lines.begin(), lines.end(), [](auto const& t1, auto const& t2) {
            return get<0>(t1) > get<0>(t2);
        });
        int ret = a;
        for(int i=0; i<lines.size(); ++i) {
            if(get<1>(lines[i]) == ret) {
                ret = get<2>(lines[i]);
            } else if(get<2>(lines[i]) == ret) {
                ret = get<1>(lines[i]);
            }
        }
        cout << ret << endl;
    }
}


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

int main(){
    int A[3];
    int sum;
    int num;

    for(int i=0;i<3;i++) cin>>A[i];

    sort(A,A+3);

    sum=(A[2]-A[0])+(A[2]-A[1]);

    if(sum%2==0){
       num=sum/2;
    }
    else{
        num=(sum-1)/2+2;
    }

    cout<<num<<endl;
    return 0;
}

Measured memory_bytes: 764
x1,y1,x2,y2=map(int,input().split())

v=[x2-x1,y2-y1]
x,y=v[0],v[1]
v=[-y,x]
x3,y3=x2+v[0],y2+v[1]
x,y=v[0],v[1]
v=[-y,x]
x4,y4=x3+v[0],y3+v[1]
print(x3,y3,x4,y4)

Measured memory_bytes: 61544
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
typedef pair<int,int> Pi; typedef priority_queue<int> Pr; typedef vector<int> Vi; typedef vector<Pi> Vp;
typedef map<int,int> MPi; typedef pair<Int,Int> Pl; typedef vector<Int> VI;
const int mod = 1000000007; const Int INF = 1145141919810893931;
#define END {cout<<ans<<'\n'; return 0;}
#define ALL(v) v.begin(),v.end()
template<class T> inline bool cmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool cmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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

    int n; cin>>n; int a[n],b[n];
    for (int i = 0; i < n; i++){cin>>a[i]; b[a[i]-1]=i;}
    int ans=1,key=1;
    for (int i = 1; i < n; i++){
        if(b[i]>b[i-1])key++;
        else{cmax(ans,key); key=1;}
    }
    cmax(ans,key);
    cout<<n-ans<<'\n';
}

Measured memory_bytes: 1792
s = input()
t = input()

s_list = []
for i in range(len(s)):
    s_list.append(s[i])
s_list.sort()
s = ""
for i in range(len(s_list)):
    s += s_list[i]

t_list = []
for i in range(len(t)):
    t_list.append(t[i])
t_list.sort()
t_list.reverse()
t = ""
for i in range(len(t_list)):
    t += t_list[i]

if s < t:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let D: usize = sc.get();
    let T: usize = sc.get();
    let S: usize = sc.get();
    if (D+S-1)/S <= T {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 2144
#include<bits/stdc++.h>
using namespace std;
int main()
{
   long int n,ac=0,tle=0,wa=0,re=0;
  string s;
  cin>>n;
  while(n--)
  {
    cin>>s;
    if(s=="AC")
      ac++;
    else
      if(s=="RE")
      re++;
    else
      if(s=="WA")
      wa++;
    else
      tle++;
      
  }
  cout<<"AC x "<<ac<<endl;
   cout<<"WA x "<<wa<<endl;
   cout<<"TLE x "<<tle<<endl;
   cout<<"RE x "<<re<<endl;
  
}

Measured memory_bytes: 3612
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner scanner = new Scanner(System.in);
        
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        List<Integer> list = new ArrayList<Integer>();
        
        for(int i=0; i<N; i++){
            int s = scanner.nextInt();
            list.add(s);
        }
        
        Collections.sort(list);
        
        int sum = 0;
        
        for(int i=0; i<K; i++){
            sum += list.get(i);
        }
        
        System.out.println(sum);
    }
}


Measured memory_bytes: 38720
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#include <string>
const int mxN=1e5;
const int maxN=5e3;
#define ld long double
#define pb push_back
#define mp make_pair
#define ins insert
#define vi vector<int>

int main()
{
    int n;
    cin >> n;
    int cnt[100000]={};
    ll s=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin >> x;
        cnt[x-1]++;
        s+=x;
    }
    int q;
    cin >> q;
    while(q--)
    {
        int b,c;
        cin >> b >> c;
        s+=cnt[b-1]*(c-b);
        cnt[c-1]+=cnt[b-1];
        cnt[b-1]=0;
        cout << s << "\n";
    }
}

Measured memory_bytes: 3944
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
string alp="abcdefghijklmnopqrstuvwxyz";
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);



int main(){
    ll n;cin>>n;
    cout<<(n+1)/2<<endl;
    
    return 0;
}




Measured memory_bytes: 764
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

	Scanner sc;
	int N, M;
	String sAry[], tAry[];

	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		sc = new Scanner(System.in);
		N = sc.nextInt();
		sAry = Stream.generate(() -> sc.next()).limit(N).toArray(String[]::new);
		M = sc.nextInt();
		tAry = Stream.generate(() -> sc.next()).limit(M).toArray(String[]::new);
		sc.close();
      
		int max = 0;
		for(String s : sAry) max = Math.max(max, calc(s));

		System.out.println(max);
	}

	int calc(String s) {
		int res = 0;
		for(String b : sAry) {
			if(s.equals(b)) {
				res++;
			}
		}
		for(String r : tAry) {
			if(s.equals(r)) {
				res--;
			}
		}

		return res;
	}

}

Measured memory_bytes: 29012
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <functional>

using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
class Monoid {
public:
    using t = long;
    static t id() {
        return 10000000000000000;
    }
    static t op(const t& l, const t& r) {
        return min(l, r);
    }
};
template< typename M >
class SegmentTree {
	using T = typename M::t;
	const int n;
	vector<T> data;
	int size(int n_) {
        int res = 1;
        while (res < n_) {
			res <<= 1;
		}
        return res;
    }
	public:
    SegmentTree(int n_)
        : n(size(n_)), data(n * 2, M::id()) {}
    SegmentTree(int n_, T v)
        : n(size(n_)), data(n * 2, v) {}
    SegmentTree(const vector<T>& data_)
        : n(size(data_.size())), data(n * 2, M::id()) {
            init(data_);
    }
    void init() {
        for (int i = n - 1; i >= 1; i--) data[i] = M::op(data[i * 2], data[i * 2 + 1]);
    }
    void init(const vector<T>& data_) {
        for (int i = 0; i < (int)data_.size(); i++) data[i + n] = data_[i];
        init();
    }
  	T Query(int k){
    	k += n;
		T ans = data[k];
    	while(k >>= 1){
      		ans = M::op(ans,data[k]);
    	}
		return ans;
  	}
	//[a,b)
  	void Update(int a,int b,const T x){
    	for(a += n,b += n;a < b;a >>= 1,b >>= 1){
      		if(a & 1) data[a] = M::op(data[a],x),a++;
      		if(b & 1) b--,data[b] = M::op(data[b],x);
    	}
  	}
};
tuple<long,long,long> query[200000];
long D[200000];
void Calc(){
	int N = rei();
	int Q = rei();
	for(int i=0;i<N;i++){
		long s = rei();
		long t = rei();
		long x = rei();
		query[i] = 	make_tuple(s,t,x);
	}
	for(int i=0;i<Q;i++){
		D[i] = rei();
	}
	SegmentTree<Monoid> Seg(Q);
	for(int i=0;i<N;i++){
		long f = get<0>(query[i]);
		long t = get<1>(query[i]);
		long x = get<2>(query[i]);
		f -= x;
		t -= x;
		int fq;
		int tq;
		{
			int bf = 0;
			int bl = Q;
			while(bf != bl){
				int bc = (bf+bl)/2;
				if(bc == Q || D[bc] >= f){
					bl = bc;
				}
				else{
					bf = bc+1;
				}
			}
			fq = bf;
		}
		{
			int bf = -1;
			int bl = Q-1;
			while(bf != bl){
				long bc = (bf+bl+1)/2;
				if(bc == -1 || D[bc] < t){
					bf = bc;
				}
				else{
					bl = bc-1;
				}
			}
			tq = bf;
		}
		if(fq <= tq){
			Seg.Update(fq,tq+1,x);
		}
	}
	for(int i=0;i<Q;i++){
		long a = Seg.Query(i);
		if(a == Monoid::id()){
			a = -1;
		}
		cout << a << "\n";
	}
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 12288
#include<bits/stdc++.h>
using namespace std;
int rec(string a,string b)
{
    int m=a.length();
    int n=b.length();
    int lcs[4000][4000]={0};
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i-1]==b[j-1])
            {
                lcs[i][j]=1+lcs[i-1][j-1];
            }
            else
            lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
        }
    }
    int i=m,j=n,idx=lcs[m][n];
   // char *lcsans=new char[idx];
    //lcsans[idx]='\0';
  string lcsans ="";
    while(i>0 and j>0)
    {
        if(a[i-1]==b[j-1])
        {
            //lcsans[idx-1]=a[i-1];
            lcsans=a[i-1]+lcsans;
            idx--;
            i--;
            j--;
        }
        else if(lcs[i-1][j]>lcs[i][j-1])
        {
            i--;
        }
        else
        {
            j--;
        }
    }
    
    cout<<lcsans<<endl;
    return lcs[m][n];
}
int main()
{
    string a,b;
    cin>>a>>b;
    rec(a,b);
    return 0;
}


Measured memory_bytes: 66184
# 参考 : https://at274.hatenablog.com/entry/2020/01/15/060000
from functools import reduce
import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


def lcm_list(numbers):  # リストを投げると全要素のlcmが返ってくる
    return reduce(lcm, numbers, 1)


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

# 最初、Aの要素は全て偶数。2で割ったものに置き換え
A = [a // 2 for a in A]

# 全ての要素について、２で割れる回数が同じでないと題意は満たせない
count_div_2 = None
for a in A:
    cnt = 0
    while a % 2 == 0:
        a //= 2
        cnt += 1
    # 1個目は無条件で保存
    if count_div_2 is None:
        count_div_2 = cnt
    # 2個目からチェック
    elif cnt != count_div_2:
        print(0)
        exit()

# my_lcm = Aの全要素の最小公倍数。　この奇数倍が題意を満たす。
# my_lcmがMを超えていたら1つも作れない
my_lcm = lcm_list(A)
if my_lcm > M:
    print(0)
    exit()

tmp = M // my_lcm
# my_lcmの1,2,...tmp倍まで使えるが、偶数は使えない
# tmp=1or2なら1個, 3or4なら2個, 5or6なら3個,...
ans = (tmp + 1) // 2
print(ans)


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

int main(){
    int n,k;
    cin >> n >> k;
    int a[n];
    for(int i = 0 ; i < n; i++){
        cin >> a[i];
    }
    int count = k;
    if(n == k){
        cout << 1 << endl;
        return 0;
    }
    for(int i = 1; ; i++){
        count += k-1;
        if(count >= n){
            cout << i+1 << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
int a[100];
int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n - 1; i++)
        cout << a[i] << ' ';
    cout << a[n - 1] << '\n';

    for (int k = 1; k < n; k++) {
        int j = k;
        while (a[j] < a[j - 1]) {
            swap(a[j], a[j - 1]);
            j--;
        }
        for (int i = 0; i < n - 1; i++) {
            cout << a[i] << ' ';
        } cout << a[n - 1] << '\n';
    }
    return 0;
}


Measured memory_bytes: 3096
al = []
ans = 'No'
for i in range(3):
    al.append(list(map(int, input().split())))
n = int(input())
bl = [int(input()) for i in range(n)]
for i in bl:
    for a in al:
        if i in a:
            a[a.index(i)]=0           
t1 = al[0][0]+al[1][1]+al[2][2]
t2 = al[0][2]+al[1][1]+al[2][0]
if t1 ==0 or t2==0:
    ans = 'Yes'
else:
    for a in al:
        if sum(a)==0:
            ans = 'Yes'
            break
        else:
            for va in zip(*al):
                if sum(va)==0:
                    ans = 'Yes'
                    break
print(ans)


    

    


                
    
    

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define deb(x) cout<< #x << " " << x << "\n";
#define MAX 9223372036854775807
#define MIN -9223372036854775807
#define PI 3.141592653589
#define setbits(n) __builtin_popcountll(n)
const ll mod=1e9+7;


int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll T=clock();
    
    ll n;
    cin>>n;
    vector<ll> a (n),pref(n);
    for(ll i=0;i<n;i++)
        cin>>a[i];
    pref[0]=a[0];
    for(ll i=1;i<n;i++)
        pref[i]=(pref[i-1]+a[i])%mod;
    ll ans=0;
    for(ll i=1;i<n;i++)
        ans=(ans+(pref[i-1]*a[i])%mod)%mod;
    cout<<ans;

    cerr<<"\n\nTIME: "<<(double)(clock()-T)/CLOCKS_PER_SEC<<" sec\n";
    T = clock();
    return 0;
}

Measured memory_bytes: 6392
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
//cin.sync_with_stdio(false);
//streambuf
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int mincost[5001];
vector<pii> tx(5001);
vector<vector<int>> way(5001);
int main() {
	int n, r;
	while (cin >> n >> r, r) {
		vector<int> list(n);
		for (int i = 0; i < n; i++)list[i] = i + 1;
		for (int i = 0; i < r; i++) {
			int p, c;
			cin >> p >> c;
			vector<int> buf(list.end() - p + 1 - c, list.end() - p + 1);
			list.erase(list.end() - p + 1 - c, list.end() - p + 1);
			list.insert(list.end(), buf.begin(), buf.end());
		}
		cout << list.back() << endl;
	}
}

Measured memory_bytes: 3168
import math
N, D = map(int, input().split())

X = []
X = [input().split() for i in range(N)]

sum = 0
for i in range(N-1):
    for j in range(i+1,N):
        temp = 0
        for k in range(D):
            temp += (int(X[i][k]) - int(X[j][k]))**2
        ans = math.sqrt(temp)
        if ans.is_integer():
            sum += 1

print(sum)


Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main(){
    int N;
    const int MAX_N = 100;
    int L[MAX_N];
    int s = 0;
    int tmx = 0;
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> L[i]; 
        s += L[i];
        if(tmx < L[i])tmx = L[i];
    }
    if(tmx<s-tmx) cout << "Yes"<<endl;
    if(tmx>=s-tmx) cout << "No"<<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <string.h>
 
#define rep(i,n)    for(ll i=0;i<n;i++)
#define repu(i,k,n) for(ll i=k;i<=n;i++)
#define repd(i,k,n) for(ll i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl "\n"
#define INF (ll)ll_MAX
 
typedef long long ll;
typedef long double ld;
typedef std::pair<ll, ll> pii;
typedef std::vector< ll > vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, ll > > vpp;
 
const ll N = 3*1e5 +5 ;
const long long MOD = 1000000007;
const long long MOD2 = 998244353;
const long long inf = 1e18;
 
using namespace std;

// ll g[200000], ig[200000];

ll n;


ll dfs(int u, vll v[], bool vis[]){
    if(vis[u]) return 0;
    vis[u] = 1;

    int num = 1;
    for(ll i=0;i<v[u].size();i++){
        num+= dfs(v[u][i],v,vis);
    }

    return num;
}



void solve()
{	

    ll m;
    cin>>n>>m;

    vll v[n+1];

    for(ll i=0;i<m;i++){
        ll t1,t2;
        cin>>t1>>t2;
        v[t1].pb(t2);
        v[t2].pb(t1);
    }

    ll ctr = 0;
    bool vis[n+1];
    memset(vis,0,sizeof(vis));

    for(ll i=1;i<=n;i++){
        ll temp = dfs(i,v,vis);
        ctr = max(ctr,temp);
    }

    cout<<ctr;




}

int main() {


    // #ifndef ONLINE_JUDGE
    //     // for getting input from input.txt
    //     freopen("input.txt", "r", stdin);
    //     // for writing output to output.txt
    //     freopen("output.txt", "w", stdout);
    // #endif


    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    ll t = 1;
    // cin>>t;
    ll ctr=0;
    while(t--)
    {   
        ctr++;
        // cout<<"Case #"<<ctr<<": ";
        solve();    
    } 
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
 
}

Measured memory_bytes: 24188
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin>>N;
    int a[N];
    for(int i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    map<int,int> m;
    int p=1;
    for(int i=0;i<N+2;i++){
        if(p==2){cout<<i<<endl;exit(0);}
        if(m[p]==1){cout<<"-1"<<endl;exit(0);}
        m[p]++;
        p=a[p-1];
    }
}

Measured memory_bytes: 5376
module Main where
--import Debug.Trace
import Data.List
import Data.Char
import Data.Array
import Data.Maybe
import Data.Ord
import Control.Monad

solve :: [String] -> [Int]
solve [] = []
solve (x:xs) = iter x: solve xs where
    iter [] = 0
    iter (d:ds) = ord d - ord '0' + iter ds
                
readUntil :: (String -> Bool) -> IO [String]
readUntil eof = iter where
    iter = getLine >>=
            (\a -> if eof a then return [] else fmap (a:) iter)
            
eof :: String -> Bool
eof s = s == "0"

main :: IO() 
main = do
    l   <- readUntil eof
    mapM_ putStrLn $ map show (solve l)



Measured memory_bytes: 4036
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef pair<ll, ll> P;
typedef pair<int, int> i_i;
ll INF = 1e12+10;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
vector<pair<ll, ll> > pairs;
#define print1(x) cerr << "x = " << x << endl;
#define print2(x, y) cerr<< "x,y = "  << x << "," << y << endl;
#define print3(x, y, z) cerr << "x,y,z = " << x << "," << y << "," << z << endl;
#define print4(x, y, z, w) cerr << "x,y,z,w = " << x << "," << y << "," << z << "," << w << endl;
const ll MAX = ll(1e10) * 300 + 10;
ll dp[310][int(1e3+10)];
ll A[int(1e6) + 1];
ll B[int(1e6) + 1];
ll S2[int(1e6) + 1];

vector<pair<ll, ll> > P;

ll N, X, D;
string S;

ll gcd(ll a, ll b){
    if (b == 0)return a;
    return gcd(b, a % b);
}

int main()
{
    cin >> N >> X >> D;
 
#if 0    
    if (X == 0){
        if (D == 0){
            cout << 1 << endl;
            
        } else {
            cout << N * (N - 1)/2 << endl;
        }
        return 0;
    }
#endif
    if (D == 0){
        if (X == 0){
            cout << 1 << endl;
        } else {
            cout << N + 1 << endl;
        }
        return 0;
    }
    
    
    if (D < 0){
        D = -D;
        X = -X;
    }
    ll ans = 0;
    //cout << m << endl;
    //fprintf(stderr, "%d, %d, %d\n", m, D/m, D/X);
    
    //set<ll> st;
    
    ll m = gcd(abs(X), D);
    X /= m;
    D /= m;
    
    for (ll k = 0; k < D; k++){
            ll min1, max1 = -1;
            set<pair<ll,ll> > st;
            for (ll k2 = k; k2 <= N; k2 += D){ //D/m){
                ll min2 = k2 * (k2 - 1)/2 + k2 * X/D;
                ll max2 = (N - k2 + N - 1) * k2/2 + k2 * X/D;
                st.insert(make_pair(min2,max2 + 1));
#if 0
                //fprintf(stderr, "%d, (%d, %d)\n", 
                //    max1, k2 * (k2 - 1)/2, 
                //    (N - k2 + N - 1) * k2/2);
                if (k2 == k){
                    max1 = max2;
                    min1 = min2;
                } else if (max1 < max2){
                    max1 = max2;
                    min1 = max(min2, max1 + 1);
                } else {
                    max1 = min(max2, min1 - 1);
                    min1 = min2;
                }
                ans += max1 - min1 + 1;
                //fprintf(stderr, "  k2 = %d, %d\n", k2, max1 - min1 + 1);
#endif
            }
            ll r = -1E18;
            for (auto p : st) {
                ans += max(0LL, p.second - max(r, p.first));
                r = max(r, p.second);
            }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 12800
N, A, B = map(int, input().split())
X = list(map(int, input().split()))
here = X.pop(0) 
ans = 0

for _ in range(N-1):
    walk = (X[0] - here) * A
    if walk > B:
        ans += B
    else:
        ans += walk
    here = X.pop(0)

print(ans)

Measured memory_bytes: 14224
#include <stdio.h>
 
int main(int argc, const char * argv[]) {
    int a1=0,a2=0,a3=0,a4=0,dice[7],i=0;
    char cc[200];
     
    for(i = 1;i <= 6;i++){
        scanf("%d",&dice[i]);
    }
     
    scanf("%s",cc);
     
    i=0;
 
    while(cc[i]!='\0'){
            if(cc[i]=='E'){
            a1=dice[1];
            a2=dice[3];
            a3=dice[4];
            a4=dice[6];
            dice[1]=a3;
            dice[3]=a1;
            dice[4]=a4;
            dice[6]=a2;
        }else if(cc[i]=='N'){
            a1=dice[1];
            a2=dice[2];
            a3=dice[5];
            a4=dice[6];
            dice[1]=a2;
            dice[2]=a4;
            dice[5]=a1;
            dice[6]=a3;
        }else if(cc[i]=='S'){
            a1=dice[1];
            a2=dice[2];
            a3=dice[5];
            a4=dice[6];
            dice[1]=a3;
            dice[2]=a1;
            dice[5]=a4;
            dice[6]=a2;
        }else if(cc[i]=='W'){
            a1=dice[1];
            a2=dice[3];
            a3=dice[4];
            a4=dice[6];
            dice[1]=a2;
            dice[3]=a4;
            dice[4]=a1;
            dice[6]=a3;
        }else{
            //printf("No\n");
        }
        i++;
    }
    printf("%d\n",dice[1]);
    return 0;
}

Measured memory_bytes: 596
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const LL Maxn = 100010;
LL a[Maxn], n, b[Maxn], bl;
LL s[Maxn<<1], N, ss;
LL lowbit(LL x) { return x & (-x); }
void add(LL x) { while(x <= N){ s[x]++; x += lowbit(x); } }
LL qry(LL x) { LL ret = 0; while(x > 0){ ret += s[x]; x -= lowbit(x); } return ret; }
bool check(LL x) {
	LL i, j, k = n+1;
	for(i = 1; i <= N; i++) s[i] = 0;
	LL sum = 0;
	add(k);
	for(i = 1; i <= n; i++){
		if(a[i] <= b[x]) k++;
		else k--;
		sum += qry(k-1);
		add(k);
	}
	return sum >= ss;
}
int main() {
	LL i, j, k;
	scanf("%lld", &n);
	for(i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i];
	sort(b+1, b+n+1);
	bl = unique(b+1, b+n+1) - (b+1);
	N = 2*n+1;
	ss = (n*(n+1)/2)/2+1;
	LL L = 1, R = bl, ret;
	while(L <= R){
		LL mid = L+R>>1;
		if(check(mid)) ret = mid, R = mid-1;
		else L = mid+1;
	}
	printf("%lld\n", b[ret]);
	return 0;
}


Measured memory_bytes: 3328
n, k, q = [int(_) for _ in input().split()]

pt = [0] * n
for i in range(q):
    pt[int(input()) - 1] += 1

tmp = k - q
for i in range(n):
    if pt[i]  +tmp>0:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 4680
#include<stdio.h>
#include<iostream>
using namespace std;
#define MOD 1000000007
int main()
{
  long long sum = 0, a[200005], csum[200005];
  int n;
  cin >> n;
  csum[0] = 0;
  for(int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    csum[i] = (csum[i-1] + a[i]) % MOD;
  }
  
  for(int i = 1; i < n; i++) {
    sum = (sum % MOD + (a[i] * (( (csum[n] - csum[i])%MOD + MOD) % MOD) ) % MOD) % MOD;
  }
  cout << sum % MOD << endl;
  return 0;
}

Measured memory_bytes: 6348
#include <bits/stdc++.h>
#include <sstream> 
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define endl "\n"
#define pi 2*acos(0.0)
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define repe(i,a,b) for(ll i=a;i<=b;++i)
#define CPrint(c)  for(auto i:(c)) { cout<<i<<" "; } nl 
#define eb   emplace_back
#define ef   emplace_front
#define pb   push_back
#define pf   push_front
#define popb pop_back
#define popf pop_front
#define mp   make_pair
#define sz(a) int((a).size())
#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++)
//Allows to traverse any type of macro
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
//debuggers
#define trace2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define trace3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define trace4(w,x,y,z) cout<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
typedef long long ll;
using namespace std;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef pair<int,int> pii;
int main()
{
  ll a,b;
	FAST_IO;
  cin >> a >> b;
  cout << max({a*b,a+b,a-b}) << endl;
}


Measured memory_bytes: 256
N, L = list(map(int, input().split()))
a = list(map(int, input().split()))

judge = "Impossible"
for i in range(N - 1):
	x = a[i] + a[i + 1]
	if x >= L:
		judge = "Possible"
		c = i + 1
		break


if judge == "Impossible":
	print(judge)
else:
	print(judge)
	for i in range(1, c):
		print(i)
	for i in range(N - c - 1):
		print(N - 1 - i)
	print(c)


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int md = (int)1e9+7;
void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

int main(){
	int a,b;
	cin >>a >>b;
	
	int sa = b-a;
	ll sk = (1+sa)*(ll)sa /2;
	cout << sk -b <<"\n";
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const int N= 1e5 + 10;
using namespace std;
int ans, n;
int a[N];
char s[N];
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
        sort(a + 1, a + 1 + n);
    // int len = unique(a + 1, a + 1 + n) - a - 1;
    for (int i = 1; i <= n - 2; ++i)
        for (int j = i + 1; j <= n - 1; ++j)
            for (int k = j + 1; k <= n; ++k) {
                if (a[i] + a[j] > a[k]) ans++;
                else break;
            }
    cout << ans;
}

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

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

int main() {
	ll N, M;
	cin >> N >> M;
	vector<ll> A(N);
	REP(i, N) scanf("%lld", &A[i]);
	sort(ALL(A));
	
	set<int> ss;
	REP(i, N) {
		int cur = A[i];
		int c = 0;
		while (cur > 0) {
			if (cur % 2 != 0) break;
			++c;
			cur /= 2;
		}
		if (c > 0) ss.insert(c);
	}
	
	if (ss.size() != 1) {
		puts("0");
		return 0;
	}
	ll p2 = 1ll<<*ss.begin();
	REP(i, N) A[i] = A[i] /= p2;
	
	ll l = A[0];
	FOR(i, 1, N) l = lcm(l, A[i]);
	
	ll ans = (2 * M) / p2;
	cout << (ans / l + 1) / 2 << endl;
	
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using Pair = pair<int, int>;
using Vec = vector<int>;
using Graph = vector<Vec>;
#define INF 1000000007
#define MOD 1000000007
#define SEP " "

int		main(void)
{
	ll x;
	cin >> x;
	for (ll i = -150; i < 150; i++)
	{
		for (ll j = -150; j < 150; j++)
		{
			if (pow(i, 5) - pow(j, 5) != x)
				continue ;
			cout << i << SEP << j << endl;
			exit(0);
		}
	}
}


Measured memory_bytes: 4036
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    ll k;
    cin >> k;
    vector<ll> ans(50);
    for (int i = 0; i < 50; ++i) {
        ans[i] = i+k/50;
    }
    for (int i = 0; i < k%50; ++i) {
        for (int j = 0; j < 50; ++j) {
            if(i == j) ans[j] += 50;
            else ans[j]--;
        }
    }
    cout << 50 << "\n";
    for (int i = 0; i < 50; ++i) {
        if(i) cout << " ";
        cout << ans[i];
    }

    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();
		if ((n + 1) / 2 >= k) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}


Measured memory_bytes: 21972
import java.util.*;

public class Main {
	/*
	 * input : N * K
	 *         A1 , A2 .... An
	 * output : 回数
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		for(int i=0;i<N;i++) {
			int ai = sc.nextInt();
		}
		int count = (N-1)/(K-1);
		if((N-1)%(K-1) != 0) {
			count += 1;
		}
		System.out.println(count);
	}


}

Measured memory_bytes: 46912
#include <stdio.h>

int gcd(int a, int b);
int lcm(int a, int b);

int main(void)
{
	int s_gcd, s_lcm;
	int a, b;
	
	while (scanf("%d %d", &a, &b) != EOF){
	
		s_gcd = gcd(a, b);
		s_lcm = lcm(a, b);
		
		printf("%d %d\n", s_gcd, s_lcm);
	}
	return (0);
}

int gcd(int m, int n)
{
    int tmp;
	
	if (m < n){
		tmp = m;
		m = n;
		n = tmp;
	}
	
	while (n != 0){
		tmp = n;
		n = m % n;
		m = tmp;
	}
	
	return (m);
}

int lcm(int a, int b)
{
	return (a / gcd(a, b) * b);
}

Measured memory_bytes: 592
#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <iostream>
#include <algorithm>
#define INF 100000000000000
using namespace std;
typedef long long llong;

//int isalpha(char ch): ch がアルファベットなら true を返す
//int isdigit(char ch): ch が数字なら true を返す
//int islower(char ch): ch が小文字なら true を返す
//int isupper(char ch): ch が大文字なら true を返す
//int tolower(char ch): ch の小文字を返す
//int toupper(char ch): ch の大文字を返す

//string型
//size()	文字数を返す
//insert()	（指定した場所に）文字・文字列を挿入する
//erase()	（指定した場所の）文字・文字列を削除する
//clear()	すべての文字を削除する
//substr()	文字列の（指定した）部分文字列を返す
//replace()	（指定した）部分文字列を新しい文字列に置換する
//文字列の比較は、<=や==などを使え


int main(){
    int n;
    cin >> n;
    string s1, s2;
    int ans1=0, ans2=0;

    for(int i=0; i<n; i++){
        cin >> s1 >> s2;
        if(s1 > s2){
            ans1 = ans1 + 3;
        }else if(s2 > s1){
            ans2 = ans2 + 3;
        }else if(s1==s2){
            ans1++;
            ans2++;
        }
    }
    cout << ans1 << " " << ans2 << endl;
    return 0;
}


Measured memory_bytes: 3200
#include<stdio.h>
int main()
{
    int N,A,B,C,D,E,F;
    scanf("%d",&N);
    if(N>=100&&N<=999)
    {
        A=N%100;
        B=A%10;
        N=N-B;
        C=N%100;
        D=C/10;
        E=N-D;
        F=E/100;
        if(B==7||D==7||F==7)
        {
            printf("Yes");
        }
        else
            printf("No");
    }
}


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

int main() {
    int h,w;
    cin >> h >> w;
    vector<string> a(h);
    vector<string> a1;
    for (int i=0; i<h; i++) cin >> a[i];
    for (int i=0; i<h; i++) {
        bool flag=0;
        for (int j=0; j<w; j++) {
            if (a[i][j]=='#') flag=1;
        }
        if (flag) a1.push_back(a[i]);
    }
    vector<int> r;
    for (int j=0; j<w; j++) {
        bool flag=1;
        for (int i=0; i<a1.size(); i++) {
            if (a1[i][j]=='#') flag=0;
        }
        if (flag) r.push_back(j);
    }
    if (r.empty()) {
        for (int i=0; i<a1.size(); i++) cout << a1[i] << endl;
    } else {
        for (int i=0; i<a1.size(); i++) {
            auto itr=r.begin();
            for (int j=0; j<w; j++) {
                if (j!=*itr) cout << a1[i][j];
                else itr++;
            }
            cout << endl;
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include<iomanip>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;

using namespace std;
int res=0;
int n;
int m;
int edge[9][9];

void dfs(int no,int bit)
{
  if(bit==(1<<n)-1){res++;return;}
  repi(i,1,n+1)
  {
    if(edge[no][i]==1 && (!(bit & (1<<(i-1)))))
    {
      dfs(i,bit+(1<<(i-1)));
    }
  }
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout<<setprecision(10);
  cin>>n>>m;
  rep(i,m)
  {
    int a,b;
    cin>>a>>b;
    edge[a][b]=1;
    edge[b][a]=1;
  }
  dfs(1,1);
  cout<<res<<endl;



  return 0;

}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)




int main() {
    ll n;
    cin >> n;
    ll sum = 0, m = n * (n + 1) / 2;
    vector<ll> a(n);
    REP(i, n){
        cin >> a[i];
        sum += a[i];
    }
    if(sum % m != 0){
        cout << "NO" << endl;
        return 0;
    }
    
    vector<ll> d(n);
    REP(i, n){
        d[i] = a[(i + 1) % n] - a[i];
    }
    
    ll k = sum / m, x = 0;
    REP(i, n){
        ll t = k - d[i];
        ll xx = t / n;
        if(xx * n != t || xx < 0){
            cout << "NO" << endl;
            return 0;
        }
        x += xx;
    }
    if(x == k){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll read(){
	ll x=0,sign=1;char s=getchar();
	while(!isdigit(s)){if(s=='-')sign=-1;s=getchar();}
	while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=getchar();
	return x*sign;
}
string s,t;
vector <int> j[27];
ll pos=-1,ans;
int main()
{
	cin>>s>>t;
	for(int i=0;i<s.size();i++)j[s[i]-'a'].push_back(i);
	for(int i=0;i<t.size();i++){
		if(!j[t[i]-'a'].size())cout<<-1,exit(0);
		int k=t[i]-'a';
		int p=upper_bound(j[k].begin(),j[k].end(),pos)-j[k].begin();
//		cout<<p<<endl;
		if(p==j[k].size())ans+=s.size()-pos-1,pos=-1,p=upper_bound(j[k].begin(),j[k].end(),pos)-j[k].begin();
		ans+=j[k][p]-pos;
		pos=j[k][p];
//		cout<<ans<<" "<<pos<<endl;
	}
	cout<<ans;
	return 0;
}


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

n = int(input())


ans = 0
for i in range(1, n+1):
    if i % 2 == 0:
        continue
    tmp = 0
    for j in range(1, i+1):
        if i % j == 0:
            tmp += 1
    if tmp == 8:
        ans += 1

print(ans)


Measured memory_bytes: 8980