akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using namespace std;
#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
#define rreps(i, n) for(int i=((int)(n)); i>0; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pl(s) cout << (s) << "\n";
#define pls(...) {bool space = false; for(auto i : __VA_ARGS__) (cout << (space?" ":"") << i), space = true; cout << "\n";}
#define plexit(s) {cout << (s) << "\n"; exit(0);}
#define yes(s) cout << ((s)?"Yes":"No") << "\n";
#ifdef __LOCAL
#include <dump.hpp>
#define dump(...) DUMPOUT << "  " << string(#__VA_ARGS__) << ": " << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl << "    ", dump_func(__VA_ARGS__)
#else
#define dump(...)
#endif
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
struct IOInit { IOInit() { cin.tie(nullptr); ios::sync_with_stdio(false); dump("READY"); /*cout << unitbuf;*/} } IO_INIT;
using ll = long long; using ull = unsigned long long; using ld = long double;
template<typename T = int> using V = vector<T>; template<typename T = int> using P = pair<T, T>;
using Vi = V<int>; using Vl = V<ll>; using Vd = V<ld>; using VVi = V<Vi>; using VVl = V<Vl>; using Pi = P<int>; using Pl = P<ll>; using Pd = P<ld>;
constexpr ll MOD = 1000000007; constexpr int INF = (1 << 30) - 1; constexpr ll INFL = 1LL << 60; constexpr ld EPS = 1e-12; constexpr ld PI = 3.141592653589793238462643383279;



signed main(void) {
  int n, m; cin >> n >> m;
  dsu uf(n);
  rep(i,m) {
    int a, b; cin >> a >> b;
    --a; --b;
    uf.merge(a,b);
  }
  pl(sz(uf.groups())-1)
  return 0;
}


Measured memory_bytes: 8944
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <bitset>
#include <vector>
#include <queue>
#include <map>
#include <set>

#define i64 int64_t
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define ffrvs(ii,nn,mm) for(int ii=nn;ii>=mm;ii--)
#define srt(vvv) sort(vvv.begin(),vvv.end())
#define srtrvs(vvv) reverse(vvv.begin(),vvv.end())
#define Graph vector<vector<int>>
i64 inf = 1000000007;
i64 giant = 4000000000000000037;

using namespace std;

//メモリ置き場
int n, m;
vector<int> ok;
vector<int> wa;

//inputします
void input() {
    cin >> n >> m;
    ok.resize(n);
    wa.resize(n);
}

//ライブラリ置き場

//main
int main() {
    input();
    ff(i, 0, m) {
        int a;
        string b;
        cin >> a >> b;
      a--;
        if ((ok[a]==0)&&(b == "WA"))wa[a]++;
        else ok[a]++;
    }
    int ansok = 0;
    int answa = 0;
    ff(i, 0, n) {
        if (ok[i]) {
            ansok++;
            answa += wa[i];
        }
    }
    cout << ansok << " " << answa << endl;
    return 0; 
}

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

mindiff = 10 ** 9 * 2 * 10 ** 5 + 1
s1 = 0
s2 = sum(a)
for i in range(N-1):
    s1 += a[i]
    s2 -= a[i]
    mindiff = min(mindiff, abs(s1 - s2))
    
print(mindiff)

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

int n, a[200010], c = 0;
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i], c ^= a[i];
    for(int i = 0; i < n; i++) cout << (c ^ a[i]) << " ";
}

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

int main() {
  int n;
  string s;
  cin >> n >> s;
  int count = 0;
  for(int i=2;i<n;i++){
    if(s[i]=='C'&&s[i-1]=='B'&&s[i-2]=='A') count++;
  }
  cout << count << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <functional>
#include <iomanip>
#include <cstring>
#include <cmath>

using namespace std;

int main() {
    int n, m;
    cin>>n>>m;
    vector<int> v(n, -1);
    for (int i=0;i<m;++i){
        int a, b;
        cin>>a>>b;
        if (v[a-1]!=-1&&v[a-1]!=b){
            cout<<"-1"<<endl;
            return 0;
        }
        v[a-1]=b;
    }
    if (n==1){
        cout<<(v[0]==-1?0:v[0])<<endl;
        return 0;
    }
    if (v[0]==-1){
        v[0]=1;
    } else if (v[0]==0){
        cout<<"-1"<<endl;
            return 0;
    }
    for (int i=0;i<n;++i){
        cout<<(v[i]==-1?0:v[i]);
    }
    cout<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

map<ll, ll> m;
ll f(ll p) {
    if (p == 0) return 1;
    else if (p == 1) return 2;
    else if (m[p] != 0) return m[p];
    else return m[p] = (f(p/2) + f((p-1)/2) + f((p-2)/2)) % mod;
}


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N; cin >> N;
    cout << f(N) << endl;

    return 0;
}


Measured memory_bytes: 256
import bisect,collections,copy,heapq,itertools,math,string
import sys
def I():
    #1 line 1 int
     return int(sys.stdin.readline().rstrip())
def LI():
    #1 line n int
     return list(map(int,sys.stdin.readline().rstrip().split()))
def S():
    #1 line 1 string
     return sys.stdin.readline().rstrip()
def LS():
    #1 line n strings
     return list(sys.stdin.readline().rstrip().split())

C1=S()
C2=S()

if C1[0]==C2[2] and C1[1]==C2[1] and C1[2]==C2[0]:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 9904
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define INFF 9223372036854775807
#define ll long long
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,m,n) for(int i=m;i<n;i++)
#define ALL(N) (N.begin(),N.end())
#define de cout << "debug" << endl;
#define pb push_back
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; }

int H,W;
vector<vector<char>> glid(2003,vector<char>(2003));
int ue = 0, sita = 0;
int migi = 0, hida = 0;
int ans = 0;
int cnt = 0;

int solveup(int X,int Y){
    if(glid[X-1][Y] == '.'){
        ue++;
        solveup(X-1,Y);
    }
    else{
        return ue;
    }
}

int solvedown(int X,int Y){
    if(glid[X+1][Y] == '.'){
        sita++;
        solvedown(X+1,Y);
    }
    else{
        return sita;
    }
}

int solveright(int X,int Y){
    if(glid[X][Y+1] == '.'){
        migi++;
        solveright(X,Y+1);
    }
    else{
        return migi;
    }
}

int solveleft(int X,int Y){
    if(glid[X][Y-1] == '.'){
        hida++;
        solveleft(X,Y-1);
    }
    else{
        return hida;
    }
}

int main() {
    cin.tie(0);    
	ios::sync_with_stdio(false);
    
    cin >> H >> W;
    REPP(i,1,H+1){
        REPP(j,1,W+1){
            cin >> glid[i][j];
        }
    }
    REP(i,H+2){
        glid[i][0] == '#';
    }
    REP(i,W+2){
        glid[0][i] == '#';
    }
    int maxv = 0;
    REP(i,H+2){
        REP(j,W+2){
            if(glid[i][j] == '.'){
                ans += solveup(i,j);
                ans += solvedown(i,j);
                ans += solveright(i,j);
                ans += solveleft(i,j);
                maxv = max(maxv,ans);
                if(maxv == H+W-2){
                    cout << maxv+1 << endl;
                    return 0;
                }
                ans = 0;ue = 0;sita = 0;migi = 0;hida = 0;
            }
        }
    }

    cout << maxv+1 << endl;
}

Measured memory_bytes: 4224
while True:
    H , W = map(int, input().split())
    if(H == 0 and W == 0):
        break
    str = "#" + "."*(W - 2) + "#"
    print("#"*W)
    for i in range(H - 2):
        print(str)
    print("#"*W)
    print()


Measured memory_bytes: 5616
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int K, X;

int main() {
	cin >> K >> X;
	int left, right;
	left = max(-1000000, X - K + 1);
	right = min(1000000, X + K - 1);
	for (int i = left; i <= right; i++) {
		if(i == right){ printf("%d\n", i); }
		else{ printf("%d ", i); }
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;(i)--)
#define rrep1(i,n) for(int i=((int)(n));i>0;(i)--)
#define sz(c) ((int)(c).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> P;
typedef pair<int, pair<int, int> > PP;
//const int MAX=;


void input(){

}

void solve(){

}

void output(){
  
}

int main(){
  int N;
  cin>>N;
  int p[51];
  rep1(i,N)cin>>p[i];
  int ct=0;
  rep1(i,N)if(p[i]!=i)ct++;
  
  if(ct<=2) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  
  input();
  solve();
  output();
}


Measured memory_bytes: 256
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <utility>
#include <climits>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define F first
#define S second
#define OUT(x) cout << x << "\n"
using namespace std;
using point = pair< int,int >;
using ll = long long;

int main() {
    int x, a;
    cin >> x >> a;

    OUT((x < a ? 0 : 10));
    return 0;
}



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

using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(i, st, ed) for(int i=st; i<=ed; i++)
#define repb(i, ed, st) for(int i=ed; i>=st; i--)

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

const long double PI  =3.141592653589793238463;
const int N = 5e5 + 10;
const ll INF = 1LL << 60;

template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}


vector<int> g[N];
bool viss[N];
int vis[N];

// Normal DFS
void dfs(int curr, int par)
{
  for(auto x: g[curr])
    if(x != par)
      dfs(x, curr);
}

// DFS with visiting status
void dfs1(int curr, int par)
{
  viss[curr] = 1;
  for(auto x: g[curr])
    if(!viss[x])
      dfs1(x, curr);
}

// DFS with strongly connected component
void dfs2(int curr, int par, int num)
{
  vis[curr] = num;
  for(auto x: g[curr])
    if(vis[x] == 0)
      dfs2(x, curr, num);
}

// XOR from 0 to n
ll fxor(ll n)
{
  if(n < 0) return 0;
  if(n % 4 == 3) return 0;
  else if(n % 4 == 0) return n;
  else if(n % 4 == 1) return n^(n-1);
  else if(n%4 == 2) return n^(n-1)^(n-2);
}

// Power in logn with mod 1000000007
llt ppow(llt x, llt y)
{
  llt res = 1;
  while(y > 0){
    if(y&1)
      res = (res * x)%M;
    y = y >> 1;
    x = (x * x)%M;
  }
  return res;
}

// Factorial with dp
ll factdp[N];
ll fact(ll x)
{
  if(x == 0) return 1;
  if(x == 1) return 1;
  if(factdp[x] != 0) return factdp[x];
  return factdp[x] = (x*fact(x-1))%M;
}

// String return to base b
string ansConv ="";
void convert10tob(llt N, int b)
{
     if (N == 0)
        return;
     int x = N % b;
     N /= b;
     if (x < 0)
        N += 1;
     convert10tob(N, b);
     ansConv += to_string(x);
     return;
}

// Convert string to num wiht base b
llt convertstrtob(string a, int b)
{
  llt aa = 0;
  llt mul = 1;
  for(int i=a.length()-1; i>=0; i--)
  {
    int curr = a[i] - '0';
    aa += (curr * mul);
    mul *= b;
  }
  return aa;
}

// Union Find algo with array
// Find()
int findpar(int curr, int arr[])
{
  while(arr[curr] != curr) curr = arr[curr];
  return curr;
}
// Union()
void Union(int b, int spa, int arr[])
{
  while(arr[b] != b)
  {
    int c = arr[b];
    arr[b] = spa;
    b = c;
  }
  arr[b] = spa;
}

// Main Code

int main()
{
  ll n, m;
  cin>>n>>m;
  if(abs(n-m) >= 2) cout<<0<<endl;
  else
  {
    ll ans = (fact(n) * fact(m)) % M;
    //cout<<ans<<endl;
    if((n&1) == (m&1))
      ans = (ans * 2) % M;
    cout<<ans<<endl;
  }
  return 0;
}


Measured memory_bytes: 14464
#include<stdio.h>
#include<stdlib.h>
int main(void){
	int N,K,X,Y,sum;
	scanf("%d",&N);
	scanf("%d",&K);
	scanf("%d",&X);
	scanf("%d",&Y);
	if(N<=K){
	sum=N*X;
	}else{
		sum=K*X+Y*(N-K);	
		}
	printf("%d\n",sum);
	return 0;	
	
}

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

int main() {
    string s;
    int k;
    cin >> s >> k;
    vector<string> sub;
    for(int len = 0; len <= k; len++)
    {
        for(int left = 0; left <= (int)s.size() - len; left++)
        {
            string t;
            for(int l = 0; l < len; l++)
            {
                t += s.at(left + l);
            }
            sub.push_back(t);
        }
        
    }
    sort(sub.begin(), sub.end());

    decltype(sub)::iterator result = unique(sub.begin(), sub.end());

    cout << sub.at(k) << endl;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
#define fin(ans) cout << ans << endl

int jdg_int(double a) {
  if (floor(a) == a)
    return 1;
  else
    return 0;
}

int main(void) {
  int N, D, i, j, k;
  double res = 0;
  int ans = 0;
  double add;
  cin >> N >> D;
  vector<vector<int>> vec(N, vector<int>(D));

  for (i = 0; i < N; i++) {
    for (j = 0; j < D; j++) {
      cin >> vec.at(i).at(j);
    }
  }

  for (i = 0; i < N; i++) {
    for (j = i+1; j < N; j++) {
      res = 0;
      for (k = 0; k < D; k++) {
        res += pow(vec.at(i).at(k) - vec.at(j).at(k), 2.0);
      }
      if (jdg_int(pow(res, 0.5)) == 1)
        ans += 1;

    }
  }
  fin(ans);
  
  
  return 0;
}


Measured memory_bytes: 256
n = gets.to_i
works = []
n.times do
  works << gets.split(" ").map(&:to_i)
end

works.each do |work|
  work << work[1] - work[0]
end

works.sort! {|a, b| (a[1] <=> b[1]).nonzero? || (a[0] <=> b[0])}

time_past = 0

ans = "Yes"
works.each do |work|
  if time_past + work[0] <= work[1]
    time_past += work[0]
  else
    ans = "No"
    break
  end
end
puts ans

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

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

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

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  int max_d = k + a[0] - a.back();
  for (int i = 1; i < n; ++i) {
    max_d = max(max_d, a[i] - a[i-1]);
  }
  cout << k - max_d << endl;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main()
{
	long long int n, i;
	scanf("%lld", &n);
	int a[105] = {0};
	for(i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
	}
	for(i = 0; i < n; i++)
	{
		printf("%lld", a[n-i]);
		if (i < n-1)
		printf(" ");
	}
	printf("\n");
	return 0;
}


Measured memory_bytes: 2732
#include<stdio.h>
struct P{int x,y;}p[100][100];
int F(int x,int y)
{
	P&r=p[y][x];
	if(r.x==-2)return 0;
	if(r.x==-1)return 1;
	x=r.x;
	r.x=-1;
	y=F(x,r.y);
	r.x=-2;
	return y;
}
int main()
{
	int N,i,j,s;
	while(scanf("%d",&N),N)
	{
		for(i=0;i<N;++i)for(j=0;j<N;++j)scanf("%d%d",&p[i][j].x,&p[i][j].y);
		for(s=i=0;i<N;++i)for(j=0;j<N;++j)s+=F(j,i);
		printf("%d\n",s);
	}
	return 0;
}

Measured memory_bytes: 0
import java.math.*;
import java.util.*;
public class Main
{
        public static void main(String[] args)
        {
            Scanner cin = new Scanner(System.in);
            int T;
            T = cin.nextInt();
            BigInteger t = new BigInteger("1000000000000000000");
            BigInteger ans = BigInteger.valueOf(1);
            for(int i = 1;i <= T;i ++)
            {
                int flag;
                BigInteger m = cin.nextBigInteger();
                int s = m.compareTo(BigInteger.valueOf(0));
                if (s == 0)
                {
                    ans = BigInteger.valueOf(0);
                }
                //BigInteger n = m.subtract(BigInteger.valueOf(1));
                //BigInteger  ans = m.multiply(n);
                //ans = ans.divide(BigInteger.valueOf(2));
                flag = ans.compareTo(t);
                if(s != 0 && flag <= 0)
                ans = ans.multiply(m);
            }
            int k = ans.compareTo(t);
            if(k <= 0)
                System.out.println(ans);
            else System.out.println("-1\n");
        }
}


Measured memory_bytes: 60344
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<math.h>
#include<time.h>

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)

typedef long long i64;
typedef pair<i64,i64> P;


int n, s,t, a[101010], b[101010], ky[101010];
vector<int> v[101010];

int main(){
	cin >> n >> s >> t;
	s--;
	t--;
	for(int i = 0; i < n-1; i++){
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		v[a[i]].push_back(b[i]);
		v[b[i]].push_back(a[i]);
	}
	
	int ans = 0;
	bool used[101010] = {0};
	queue<P> q;
	q.push(P(t, 0));
	used[t] = 1;	
	while(!q.empty()){
		P p = q.front();
		q.pop();
		int pos = p.first, now = p.second;
		ky[pos] = now;
		for(int i = 0; i < v[pos].size(); i++){
			if(used[v[pos][i]]) continue;
			used[v[pos][i]] = 1;
			q.push(P(v[pos][i], now+1));
		}
	}
	
	int must = ky[s] / 2 - !(ky[s]%2);
	int ma = 0;
	bool used2[101010] = {0};
	queue<int> qq;
	qq.push(s);
	used2[s] = 1;
	while(!qq.empty()){
		int p = qq.front();
		qq.pop();
		ma = max(ma, ky[p]);
		for(int j = 0; j < v[p].size(); j++){
			if(used2[v[p][j]]) continue;
			if(ky[v[p][j]] <= must) continue;
			used2[v[p][j]] = 1;
			qq.push(v[p][j]);
		}
	}
	cout <<  ma - 1 << endl;
	
	return 0;
}

Measured memory_bytes: 7800
N = int(input())
a = [int(c) for c in input().split()]
MOD = 10**9 + 7
dic = [0,0,0]
ans = 1
for i in range(N):
  x = a[i]
  m = 0
  n = 0
  for j in range(3):
    if dic[j]==x:
      n = j
      m += 1
  ans *= m
  ans %= MOD
  dic[n] += 1
print(ans)

Measured memory_bytes: 13964
#!/usr/local/bin/ruby
while line = gets
 n = line.to_i
 count = 0
 (0..9).to_a.repeated_permutation(4) do |a,b,c,d|
  if a+b+c+d == n
   #printf("(%d, %d, %d, %d)\n",a,b,c,d)
   count +=1
  end
 end
 puts count
end

Measured memory_bytes: 6180
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std ;
#define fl(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define endl '\n'
#define pb push_back
#define ff first
#define ss second
#define mod 1000000007
#define mx 100005
#define inf 2e18
// choices for each , states
// a + b = a^b + 2*(a&b)
#define Nitro ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) ;
int main()
{
    Nitro ;
    int n;
    cin >> n; 
    cout << n + n*n + n*n*n << endl;
    return 0;
}


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

using ll = long long;

template < typename T > T gcd(T a, T b) { return ( b ? gcd(b, a % b) : a ); }
template < typename T > T lcm(T a, T b) { return ( a / gcd(a, b) * b ); }

int main()
{
	ll N, M;
	ll div;
	string S, T;

	cin >> N >> M >> S >> T;
	div = gcd(N, M);
	
	bool flag = true;
	for ( int i = 0; i < div; i++ ) {
		flag &= S[i * (N / div)] == T[i * (M / div)];
	}

	if ( flag ) {
		cout << lcm(N, M) << endl;
	} else {
		cout << -1 << endl;
	}

	return ( 0 );
}


Measured memory_bytes: 512
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }



string N;
long long dp[21][10010][3][3]; // digit, last4, clear, smaller

bool judge(int n) {
  if ( (n/100) != 51) return false;
  if (n % 10 != 3) return false;
  return true;
}

int main() {
  while (cin >> N) {
	memset(dp, 0, sizeof(dp));
	dp[0][0][0][0] = 1;
	for (int i = 0; i <= N.size(); ++i) {
	  for (int j = 0; j <= 9999; ++j) {
		for (int k = 0; k < 10; ++k) {
		  int nj = (j % 1000) * 10 + k;

		  // smaller -> smaller
		  {
			// clear -> clear
			dp[i+1][nj][1][1] += dp[i][j][1][1];

			// nonclear -> 
			if (judge(nj)) dp[i+1][nj][1][1] += dp[i][j][0][1];
			else dp[i+1][nj][0][1] += dp[i][j][0][1];
		  }

		  // same -> smaller
		  if (k < (int)(N[i] - '0')) {
			// clear -> clear
			dp[i+1][nj][1][1] += dp[i][j][1][0];

			// nonclear ->
			if (judge(nj)) dp[i+1][nj][1][1] += dp[i][j][0][0];
			else dp[i+1][nj][0][1] += dp[i][j][0][0];
		  }

		  // same -> same
		  if (k == (int)(N[i] - '0')) {
			// clear -> clear
			dp[i+1][nj][1][0] += dp[i][j][1][0];

			// nonclear ->
			if (judge(nj)) dp[i+1][nj][1][0] += dp[i][j][0][0];
			else dp[i+1][nj][0][0] += dp[i][j][0][0];
		  }
		  
		}
	  }
	}

	long long res = 0;
	for (int j = 0; j <= 9999; ++j) {
	  for (int smaller = 0; smaller < 2; ++smaller) {
		res += dp[N.size()][j][1][smaller];
	  }
	}

	cout << res << endl;
  }
}





























Measured memory_bytes: 18004
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    let mut s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  input! {
    n: i64,
    k: i64,
  }

  let (mut c, mut m) = (0, n);
  while m != 0 {
    m /= k;
    c += 1;
  }
  
  println!("{}", c);
}

Measured memory_bytes: 4352
N = int(input())
H = list(map(int, input().split()))

ans = 0
tmp = 0
preh = H[0]
for h in H[1:]:
    if h > preh:
        ans = max(ans, tmp)
        tmp = 0
    else:
        tmp += 1
    preh = h
ans = max(ans, tmp)
print(ans)

Measured memory_bytes: 15020
#include <iostream>
#include <vector>
#include <cstdlib>
#include <queue>
#include <utility>
#include <climits>
using namespace std;

struct edge{
    int to;
    long long cost;
    edge(const int to_, const long long cost_):to(to_), cost(cost_){}
};

using P = pair<long long, int>;

using Graph = vector<vector<edge>>;

vector<long long> dijkstra(const Graph& G, const int s){
    vector<long long> d(G.size(), LONG_MAX);
    priority_queue<P, vector<P>, greater<P>> q;
    q.push(make_pair(0, s));
    d[s] = 0;

    while(!q.empty()){
        const int current_cost = q.top().first;
        const int current_v = q.top().second;
        q.pop();
        if(d[current_v] < current_cost) continue;

        for(const auto& e : G[current_v]){
            if(d[e.to] > d[current_v] + e.cost){
                d[e.to] = d[current_v] + e.cost;
                q.push(make_pair(d[e.to], e.to));
            }
        }
    }

    return d;
}

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

    Graph G(n);
    for(int i = 0; i < n-1; ++i){
        int a, b; 
        long long c;
        cin >> a >> b >> c;
        a--; b--;

        G[a].emplace_back(edge(b, c));
        G[b].emplace_back(edge(a, c));
    }

    int q, k; cin >> q >> k;
    k--;

    vector<long long> d = dijkstra(G, k);

    for(int i = 0; i < q; ++i){
        int x, y; cin >> x >> y;
        x--; y--;

        cout << d[x] + d[y] << endl;
    }

    return EXIT_SUCCESS;
}


Measured memory_bytes: 11264
bool debug=false;
#include <stdio.h>
const int N=1e3+10;
const int MOD=1e9+7;
int k;
long long int f[N][N];
int min(int a,int b){return a>b?b:a;}
long long int dp(int n,int top){
	if(debug)printf("dp(%d,%d)\n",n,top);
	if(n==0||n==top)return 1;
	if(n<top)return 0;
	if(f[n][top]>-1)return f[n][top];
	f[n][top]=MOD;
	int lim=min(n,k);
	for(int i=top;i<=lim;i++)f[n][top]+=dp(n-i,i);
	if(debug)printf("f[%d][%d]=%d\n",n,top,f[n][top]);
	return f[n][top]%=MOD;
}
int main(){
	int n;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)for(int j=1;j<=k;j++)f[i][j]=-1;
	printf("%lld\n",dp(n,1));
}



Measured memory_bytes: 10660
//54
#include<iostream>

using namespace std;

int main(){
  int n;
  cin>>n;
  long long a[101][21]={{}};
  int f;
  cin>>f;
  a[1][f]=1;
  for(int i=1;i<n-1;i++){
    int m;
    cin>>m;
    for(int j=0;j<=20;j++){
      for(int k=0;k<2;k++){
	int f[]={-1,1};
	int r=j+f[k]*m;
	if(0<=r&&r<=20){
	  a[i+1][r]+=a[i][j];
	}
      }
    }
  }
  int ans;
  cin>>ans;
  cout<<a[n-1][ans]<<endl;
  return 0;
}

Measured memory_bytes: 1180
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cctype>
#define rep(i,a,b) for(int i=(a);i<b;i++)
#define INF 1000000000
using namespace std;
bool debug=false;

int main(){
  int n;
  int data[105];
  
  while(true){
    cin>>n;
    if(n==0)break;

    rep(i,0,n)cin>>data[i];
    sort(data,data+n);

    long long sum=0;
    rep(i,1,n-1)sum+=data[i];

    cout<<sum/(n-2)<<endl;
    
  }
  return 0;
}

Measured memory_bytes: 3116
#include <iostream>
using namespace std;
#define ll long long

int main () {
    ll n;
    cin >> n;
    if (n % 2 == 1) {
        cout << 0 << endl;
        return 0;
    }
    // 2^aについてみていく
    ll stat = 2;
    ll two = 0;
    while (stat <= n) {
        two += n / stat;
        stat = stat * 2;
    }
    stat = 10;
    ll five = 0;
    while (stat <= n) {
        five += n / stat;
        stat = stat * 5;
    }
    if (five >= two) {
        cout << two << endl;
    }
    else {
        cout << five << endl;
    }

}

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

int main()
{
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i, n) cin >> h[i];
    int ans = 0, mx = 0;
    rep(i, n)
    {
        if (h[i] >= mx)
        {
            ans++;
            mx = h[i];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3608
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll;
typedef vector<int> vi; typedef vector<ll> vll; template<class T>using vv = vector<vector<T>>;
template<class T>vv<T> vvec(size_t n, size_t m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T>bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T>bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 28, MOD = int(1e9) + 7; constexpr ll LINF = 1ll << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;

int main() {
    int N;
    cin >> N;
    vi C(N), S(N), F(N);
    rep(i, N - 1) cin >> C[i] >> S[i] >> F[i];

    rep(i, N) {
        ll t = 0;
        rep(j, i, N - 1) {
            if (t > S[j]) {
                int n = (t - S[j] + F[j] - 1) / F[j];
                t = S[j] + n * F[j] + C[j];
            }
            else {
                t = S[j] + C[j];
            }
        }

        write(t);
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<climits>
#include<cstring>
#include<queue>
using namespace std;


#define REP(i,n) for(int i=0;i<(int)n;i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()


double EPS = 1e-10;

double add(double a, double b){
	if(abs(a+b) < EPS * (abs(a) + abs(b))) return 0;
	return a+b;
}

struct P{
	double x,y;
	P(){}
	P(double x, double y) : x(x), y(y){
	}
	P operator +(P p){
		return P(add(x,p.x), add(y,p.y));
	}
	P operator -(P p){
		return P(add(x,-p.x), add(y,-p.y));
	}
	P operator *(double d){
		return P(d*x, d*y);
	}
	double dot (P p){
		return add(x*p.x, y*p.y);
	}
	double det (P p){
		return add(x*p.y, -y*p.x);
	}
	void print (){
		cout << x << " " << y <<endl;
		return;
	}
};

void Check(){
	vector<P> vec(4);
	double x, y;

	REP(i, 4){
		cin >> vec[i].x >> vec[i].y ;
	}
	
	P q0 =vec[1]-vec[0];
	P q1 = vec[3] - vec[2]; 

	if(q0.dot(q1)==0)  cout << 1 << endl;
	if(q0.det(q1)==0)  cout << 2 << endl; 
	if(q0.dot(q1)!=0 && q0.det(q1)!=0) cout << 0 << endl;
	return;
}

int main(){
	int q;
	cin >> q;
	REP(i, q){
		Check();
	}
	
	return 0;
}

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int GCD[2][100010];
int A[100010];

int get_gcd(int n, int m) {
	if (n < m) swap(n, m);
	while (m) {
		swap(n, m);
		m %= n;
	}
	return n;
}

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	const int MOD = 998244353;
	
	int N;
	cin >> N;
	rep(i, 0, N)
	{
		cin >> A[i];
	}

	int t = A[0];
	GCD[0][0] = A[0];
	rep(i, 1, N)
	{
		t = get_gcd(t, A[i]);
		GCD[0][i] = t;
	}

	t = A[N - 1];
	GCD[1][N - 1] = A[N - 1];
	rrep(i, 0, N - 1)
	{
		t = get_gcd(t, A[i]);
		GCD[1][i] = t;
	}

	int ans = 1;
	rep(i, 0, N)
	{
		if (i == 0)
		{
			chmax(ans, GCD[1][i + 1]);
		}
		else if (i == N - 1)
		{
			chmax(ans, GCD[0][i - 1]);
		}
		else
		{
			chmax(ans, get_gcd(GCD[0][i - 1], GCD[1][i + 1]));
		}
	}

	cout << ans << endl;

	return 0;
}

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

bool check(int d[], int num)
{
    int dig;
    while (num)
    {
        dig = num % 10;
        if(d[dig] == 1)
        {
            return false;
        }
        num = num / 10;
    }
    return true;
}

int main(void)
{
    int n, k;
    int j;
    int d[10] = {0};
    cin >> n >> k;
    // cout << n << " " << k << endl;
    for (int i = 0; i < k; i++)
    {
        cin >> j;
        d[j] = 1;
    }
    // for (int i = 0; i < 10; i++)
    // {
    //     cout << i << ":" << d[i] << endl;
    // }
    
    while (!check(d, n))
    {
        n++;
    }
    cout << n << endl;
}

Measured memory_bytes: 256
n = int(input())
a = [input() for i in range(n)]
d = {}
ans = 0
for i in a:
  if i in d:
    d[i] += 1
  else:
    d[i] = 1
for i in d.keys():
  if d[i] % 2 == 1:
    ans += 1
print(ans)

Measured memory_bytes: 19476
//libraries
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//namespace
using namespace std;
using namespace __gnu_pbds;

//typedef
typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long,long> pll;

//define
#define inp(X) cin>>X;
#define inp_long(X) long long X; cin>>X;
#define inp_arr(A,N) long long A[N]; for(long long int i=0;i<N;i++) {cin>>A[i];}
#define sz(A) A.size()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define endl '\n'
#define vect(A) vector<long long> A;
#define inp_vect(A,N); vect(A);for(long long i=0;i<N;i++){long long q; cin>>q; A.push_back(q);}
#define forin(i,a,b) for(long long i=a;i<=b;i++)
#define forde(i,a,b) for(long long i=a;i>=b;i--)
#define fio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);

ll power(ll x,ll y)
{
    if (y == 0)
        return 1;
    ll p = power(x, y/2) % MOD;
    p = (p * p) % MOD;

    return (y%2 == 0)? p : (x * p) % MOD;
}
ll modInverse(ll a)
{
   return power(a,MOD-2);
}
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
ll p=1e9;

int main()
{
    /*
    #ifndef ONLINE_JUDGE
       freopen ("input.txt" , "r" , stdin);
		// freopen ("OUTPUT.txt" , "w" , stdout);
	#endif
    */
    fio;
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll z[12]={31,28,31,30,31,30,31,31,30,31,30,31};
    if(z[a-1]==b)
    {
        cout<<"1"<<endl;
    }
    else
    cout<<"0"<<endl;
    
}


Measured memory_bytes: 256
import java.util.*;
class Main
{
  public static void main(String args[])
  {
  Scanner obj=new Scanner(System.in);
    int n=obj.nextInt();
    if(n%1000!=0)
    	System.out.println(1000-(n%1000));
    else
      System.out.println("0");
  }
}

Measured memory_bytes: 27056
//https://atcoder.jp/contests/abc119/tasks/abc119_d
//D - Lazy Faith
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1; } return 0;}
int main() {
#if LOCAL&01
    std::ifstream in("./test/sample-1.in");
    //std::ifstream in("./input.txt");
    std::cin.rdbuf(in.rdbuf());
#else
    cin.tie(0);
    ios::sync_with_stdio(false);
#endif
    ll A,B,Q; cin>>A>>B>>Q;
    vector<ll> sa(A); //sorted
    vector<ll> tb(B); //sorted
    vector<ll> xq(Q);
    for(auto&& s:sa){
        cin>>s;
    }
    for(auto&& t:tb){
        cin>>t;
    }
    for(auto&& x:xq){
        cin>>x;
    }

    auto calc_dist = [&](ll x){
        auto it_s = lower_bound(sa.begin(),sa.end(),x);
        auto it_t = lower_bound(tb.begin(),tb.end(),x);
        auto it_su = upper_bound(sa.begin(),sa.end(),x);
        auto it_tu = upper_bound(tb.begin(),tb.end(),x);
        constexpr ll INF=1e+11;
        ll s[2]={INF,INF};
        ll t[2]={INF,INF};
        if(it_s != sa.end()) s[1]=*it_s-x;
        if(it_t != tb.end()) t[1]=*it_t-x;
        if(it_su != sa.begin()) s[0]=x-*(it_su-1);
        if(it_tu != tb.begin()) t[0]=x-*(it_tu-1);

        ll result=INT64_MAX;
        chmin(result, max(s[1],t[1]));
        chmin(result, max(s[0],t[0]));
        chmin(result, s[0]+t[1]*2);
        chmin(result, s[0]*2+t[1]);
        chmin(result, s[1]+t[0]*2);
        chmin(result, s[1]*2+t[0]);
        assert(result != INT64_MAX);
        return result;
    };

    for(const auto& x:xq){
        auto r = calc_dist(x);
        cout<<r<<endl;
    }

    return 0;
}

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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vint;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef vector<string> vstr;
typedef vector<vector<int>> vvint;
typedef vector<pair<int, int>> vpii;
typedef vector<pair<ll, ll>> vpll;
typedef priority_queue<int, vector<int>, greater<int>> spqint; //小さい順に取り出し
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;     //小さい順に取り出し
typedef priority_queue<int, vector<int>, less<int>> bpqint;    //大きい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;        //大きい順に取り出し

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define FOR(i, a, b) for (ll i = (ll)a; i < (ll)b; i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); i++)
#define FI first
#define SE second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define TS to_string
#define BS binary_search
#define LB lower_bound
#define UB upper_bound
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) (ll) x.size()
#define SP(x) setprecision((ll)x)


int INF = 1e9;
int NIL = -1;
ll MOD = 1000000007;
ll LINF = 1e18;
double EPS = 1e-9;
double PI = M_PI;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }     //最小公倍数

void yes(){ cout << "Yes" << endl;}
void no(){ cout << "No" << endl;}
//-----------------------------------------

//-----------------------------------------
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::chrono::system_clock::time_point start,end;
    start = std::chrono::system_clock::now();

    string s, t;
    cin >> s >> t;
    ll n = SZ(s);
    ll m = SZ(t);
    ll ans = 0 ;
    vector<ll> num ;
    vector<vector<ll>> pos(26,vector<ll>());
    REP(i,n){
        ll j = s[i] - 'a';
        pos[j].PB(i) ;
    }
    ll tmp = -1 ;
    REP(i,m){
        ll j = t[i] - 'a' ;
        if(pos[j].empty()){
            cout << -1 <<endl;
            return 0;
        }
        auto itr = LB(ALL(pos[j]),tmp) ;
        if(itr==pos[j].end()){
            num.PB(pos[j][0]+1) ;
            tmp = pos[j][0]+1 ;
        }
        else{
            ll k = itr - pos[j].begin() ;
            num.PB(pos[j][k]+1) ;
            tmp = pos[j][k]+1 ;
        }
    }
    ll tt = 0 ;

    /*

    REP(i,SZ(num)-1){
        cout << num[i] <<endl;
    }

    */

    REP(i,SZ(num)-1){
        if(num[i]>=num[i+1]){
            tt++ ;
        }
    }

    ans = tt*n + num[SZ(num)-1] ;

    cout << ans <<endl;






    end = std::chrono::system_clock::now();
    auto elapsed = std::chrono::duration_cast< std::chrono::milliseconds >(end - start).count();
    //std::cout << elapsed <<"ms"<< std::endl;

    

    return 0;
}



Measured memory_bytes: 5836
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	double a, b, x;
	cin >> a >> b >> x;
	double S = x / a;
	double rad;
	if (S >= a * b / 2) {
		double h = (a * b - S) * 2 / a;
		rad = atan2(h, a);
	}
	else {
		double w = S * 2 / b;
		rad = atan2(b, w);
	}
	cout << fixed << setprecision(10) << rad * 180.0 / M_PI;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned ui;
typedef unsigned long long ul;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<int> vi;
#define pb push_back
#define fi first
#define se second
#define do(i, j, k) for(int i = j; i <= (k); i ++)
#define open(i, j, k) for(int i = j; i < (k); i ++)
#define dec(i, j, k) for(int i = j; i >= (k); i --)
#define mfil(x, k) memset(x, k, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
#define fio(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout)
template <class T> bool chkmin(T &x, T y)
{ return y < x ? (x = y, true) : false; }
template <class T> bool chkmax(T &x, T y)
{ return y > x ? (x = y, true) : false; }
struct __init { __init()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cout.precision(16); cout << fixed;
    srand(time(0) ^ ul(new char));
} } static __init__;
/* default code ends here */

const int maxn = 1e5 + 10;
int n;
vi h[maxn];
int du[maxn];
bool vis[maxn];

priority_queue<pii, vector<pii>, greater<pii>> pq;

void fir()
{
    cout << "First\n";
    exit(0);
}
void sec()
{
    cout << "Second\n";
    exit(0);
}

int find_head(int x)
{
    if(du[x] > 1)
        return x;
    vis[x] = true;
    int y = -1;
    for(int v : h[x])
        if(!vis[v])
            y = v;
    if(y == -1)
        return -1;
    du[y] --;
    return find_head(y);
}

int main()
{
    cin >> n;
    for(int i = 1, u, v; i < n; i ++)
    {
        cin >> u >> v;
        h[u].pb(v);
        h[v].pb(u);
        du[u] ++;
        du[v] ++;
    }
    do(i, 1, n)
        if(du[i] == 1)
            pq.push({du[h[i][0]], i});
    while(!pq.empty())
    {
        pii p = pq.top();
        pq.pop();
        int x = p.se;
        if(vis[x])
            continue;
        vis[x] = true;
        int y = -1;
        for(int v : h[x])
            if(!vis[v])
                y = v;
        //cerr << "OP : " << x << ' ' << y << ' ';
        if(y == -1 || du[y] >= 3)
            fir();
        //y = find_head(x);
        //cerr << y << '\n';
        vis[y] = true;
        for(int v : h[y])
            if(!vis[v])
            {
                du[v] --;
                if(du[v] == 0)
                    fir();
                else if(du[v] == 1)
                {
                    for(int vv : h[v])
                        if(!vis[vv])
                            pq.push({du[vv], v});
                }
                else if(du[v] == 2)
                {
                    for(int vv : h[v])
                        if(!vis[vv] && du[vv] == 1)
                            pq.push({du[v], vv});
                }
            }
        // for(int v : h[y])
        //     if(!vis[v] && du[v] == 1)
        //     {
        //         pq.push({du[y], v});
        //     }
    }
    sec();
    return 0;
}

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

#ifdef DEBUG
#define deb(...) cerr __VA_ARGS__
#else
#define deb(...)
#endif
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	
	cout.setf(ios::fixed);
	cout.precision(8);
	int n;
	cin >> n;
	
	double w = (n & 1) ? double(n/2+1)/n : 0.5;
	
	cout << w;
}


Measured memory_bytes: 256
M(int*a){return*a-*1[&a];}n,T[1000000][2];j,m,s;main(i){for(;~scanf("%d",&n);qsort(T,n,8,M),n&&printf("%d\n%d\n%d\n",1[*T],T[1][1],T[n-2][1]))for(i=n;i--;)for(scanf("%d",T[i]+1),*T[i]=0,j=4;j--;*T[i]+=m*60+s)scanf("%d%d",&m,&s);}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  cin >> n;

  int ans = 0;
  rep(i,0,n){
    int a;cin>>a;
    if(i%2==0&&a&1)ans++;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3636
#include<cstdio>
using namespace std;
using LL=long long;

LL c,hi[200005],dp[200005],C;
int n,Q[200005],h,t;

long double slope(int x, int y)
{
	return 1.0L*((hi[y]*hi[y]+dp[y])-(hi[x]*hi[x]+dp[x]))/(hi[y]-hi[x]);
} 

int main()
{
	scanf("%d%lld",&n,&C);
	for(int i=1;i<=n;i++)
		scanf("%lld",&hi[i]);
	Q[t++]=1;
	for(int i=2;i<=n;i++)
	{
		while(h+1<t&&slope(Q[h],Q[h+1])<2*hi[i])
			h++;
		dp[i]=dp[Q[h]]+(hi[i]-hi[Q[h]])*(hi[i]-hi[Q[h]])+C;
		while(h+1<t&&slope(Q[t-2],Q[t-1])>slope(Q[t-1],i))
			--t;
		Q[t++]=i;
	}
	printf("%lld",dp[n]);
	return 0;
}

Measured memory_bytes: 4096
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<string>
#include<unordered_map>
using namespace std;

#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j,k
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define sort(a) sort(a.begin(),a.end())
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define sizeoof(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
double ans=0;llfor;///////////////////////////////////////////////////////////
int main(){
 ll n;sc(n);
 i=0;
 while(n/llpow(10,i)>0){
  ll a=(n/llpow(10,i))%10;
  if(a==9){py;return 0;}
  i++;
 }
 pn;
return 0;}

Measured memory_bytes: 3548
<?php
define('N', 1000);

function trace(array $A, $n) {
  for ($i=0; $i<$n; $i++) {
    if($i > 0) printf(" ");
    printf("%d", $A[$i]);
  }
  printf("\n");
}

$n = intval(trim(fgets(STDIN)));
$A = array_map('intval', explode(' ', trim(fgets(STDIN))));

for ($i=0; $i<$n; $i++) {
  $key = $A[$i];
  $j = $i - 1;
  while ($j >= 0 && $A[$j] > $key) {
    $A[$j+1] = $A[$j];
    $j--;
  }
  $A[$j+1] = $key;
  trace($A, $n);
}
?>


Measured memory_bytes: 9340
#include <bits/stdc++.h>
       
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
  int N, M;
  cin >> N >> M;
  cout << N * (N - 1) / 2 + M * (M - 1) / 2 << endl;
  return 0;
}


Measured memory_bytes: 256