akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

constexpr int inf = 1e9;
constexpr ll linf = 1e18;

template <typename T>
class SegTree
{
public:
    SegTree(const int n, const T &unity) : _unity(unity)
    {
        _n = 1 << __lg(2 * n - 1);
        _data.resize(2 * _n, unity);
    }

    SegTree(const vector<T> &v, const T &unity) : _unity(unity)
    {
        int n = v.size();
        _n = 1 << __lg(2 * n - 1);
        _data.resize(2 * _n, unity);

        // 最下段に要素をセット
        for (int i = 0; i < n; i++) _data[i + _n] = v[i];
        // セグメント木を構築
        for (int i = _n - 1; i > 0; i--) _data[i] = f(_data[2 * i], _data[2 * i + 1]);
    }

    // k番目の値をxに更新する
    void update(int k, const T &x)
    {
        k += _n; // 葉の節点に変換
        _data[k] = x;
        while (k >>= 1) _data[k] = f(_data[2 * k], _data[2 * k + 1]);
    }

    // 区間[a, b)に対してクエリ処理した結果を返す
    T query(int a, int b)
    {
        T left = _unity, right = _unity;
        a += _n, b += _n; // 葉の節点に変換
        for (; a < b; a >>= 1, b >>= 1) {
            if (a & 1) left  = f(left, _data[a++]);
            if (b & 1) right = f(_data[--b], right);
        }
        return f(left, right);
    }

    const T &operator[](size_t i) const { return _data[i + _n]; }
    T &operator[](size_t i) { return _data[i + _n]; }

private:
    int _n;          // 要素数
    vector<T> _data; // データを格納する配列
    T _unity;        // 単位元

    // クエリ処理用の関数
    T f(const T &a, const T &b) { return a | b; }
};

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

    int n; cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        char c; cin >> c;
        v[i] = 1 << (c - 'a');
    }

    SegTree<int> st(v, 0);

    int q; cin >> q;
    while (q--) {
        int k; cin >> k;
        if (k == 1) {
            int i; cin >> i; i--;
            char c; cin >> c;
            st.update(i, 1 << (c - 'a'));
        } else {
            int l, r; cin >> l >> r; l--;
            int ans = __builtin_popcount(st.query(l, r));
            cout << ans << endl;
        }
    }
    return 0;
}

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

mt19937_64 llrand(random_device{}());

#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define cl(x, v) memset((x), (v), sizeof(x))
#define db(x) cerr << #x << " == " << x << endl
#define dbs(x) cerr << x << endl
#define _ << ", " <<
#define gcd(x, y) __gcd((x), (y))

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef vector<int> vi;
typedef vector<vi> vii;

const ld EPS = 1e-9, PI = acos(-1.);
const ll LINF = 0x3f3f3f3f3f3f3f3f, LMOD = 1011112131415161719ll;
const int INF = 0x3f3f3f3f, MOD = 1e9+7;
const int N = 2e5+5;

typedef long long type;
struct line { type b, m; };

int nh, pos;
line hull[N];

bool check(line s, line t, line u) {
    return (s.b - t.b)*(u.m - s.m) < (s.b - u.b)*(t.m - s.m);
}

void update (line s) {
    if (nh == 1 and hull[nh-1].b == s.b) nh--;
    if (nh > 0  and hull[nh-1].m >= s.m) return;
    while (nh >= 2 and !check(hull[nh-2], hull[nh-1], s)) nh--;
    pos = min(pos, nh);
    hull[nh++] = s;
}

type eval (int id, type x) { return hull[id].b + hull[id].m * x; }

type query (type x) {
                                       // Attention!!!
    while (pos+1 < nh and eval(pos, x) < eval(pos+1, x)) pos++;
    return eval(pos, x);
}

ll n, c, h[N], dp[N];

int main () {
    scanf("%lld%lld", &n, &c);

    for (int i = 0; i < n; i++) {
        scanf("%lld", &h[i]);
        ll q = -query(h[i]) + h[i]*h[i];
        if (i > 0) dp[i] = -query(h[i]) + h[i]*h[i];

        line l;
        l.b = -(h[i]*h[i] + c + dp[i]);
        l.m = -(-2*h[i]);
        update(l);
    }

    printf("%lld\n", dp[n-1]);

    return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <cstdlib>
#include <string>
#include <algorithm>
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 ans;
  ans=(n-1)/(k-1);
  if((n-1)%(k-1) !=0){
    ans++;
  }

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

Measured memory_bytes: 640
q=int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
from math import floor
for a,b in ab:
  if a==b:
    print(2*a-2)
    continue
  t=floor((a*b)**0.5)
  # t,t+1 組み合わせの積がa*bで抑えられているかどうか
  if t*t>=a*b: # t*tもだめ
    print(2*t-3)
  elif t*(t+1)>=a*b: # t*(t+1)はだめ
    print(2*t-2)
  else: # t*tもt*(t+1)もOK
    print(2*t-1)


Measured memory_bytes: 63652
#include<bits/stdc++.h>
using namespace std;
int main()
{
    map<string,int>mp;
    set<string>st;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;

        mp[s]++;
        st.insert(s);
    }
    set<string> :: iterator it;
    int mx=-9;
    for(it= st.begin();it!=st.end();it++)
    {
        int k=mp[(*it)];
        mx=max(mx,k);
    }
    for(it= st.begin();it!=st.end();it++)
    {
        int k=mp[(*it)];
        if(mx==k)
        {
            cout<<*(it)<<endl;
        }
    }

}


Measured memory_bytes: 34560
import java.io.*;
import java.util.*;

public class Main{
    static MyReader in = new MyReader();
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args){
        int N = in.i();
        String S = in.s();
        int ans = N;
        for(int i = 0; i < N-1; ){
            char c = S.charAt(i);
            int j = i+1;
            while(j < N && c == S.charAt(j)){
                j++;
            }
            ans -= j-i-1; 
            i = j;
        }
        out.println(ans);
        out.flush();
    }

    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }

        String s(){
            try{return readLine();}catch(IOException e){return "";}
        }

        String[] ss(){
            return s().split(" ");
        }

        int i(){
            return Integer.parseInt(s());
        }

        int[] ii(){
            String[] ss = ss();
            int[] ii = new int[ss.length];
            for(int j = 0; j < ss.length; j++) ii[j] = Integer.parseInt(ss[j]);
            return ii;
        }

        long l(){
            return Long.parseLong(s());
        }

        long[] ll(){
            String[] ss = ss();
            long[] ll = new long[ss.length];
            for(int j = 0; j < ss.length; j++) ll[j] = Long.parseLong(ss[j]);
            return ll;
        }
    }
}


Measured memory_bytes: 23124
n, m, k = map(int, input().split())
p = 998244353
fct, inv = [1], [1]
for i in range(1, max(n, m) + 1):
    fct.append((fct[-1] * i) % p)
    inv.append((inv[-1] * pow(i, p - 2, p)) % p)
ans = 0
for i in range(k + 1):
    cmb = fct[n - 1] * inv[i] * inv[n - 1 - i]
    ans = (ans + cmb * m * pow(m - 1, n - 1 - i, p)) % p
print(ans)


Measured memory_bytes: 24984
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;

long long int power(long long int x, long long int n, long long int M) {
	long long int ret = 1;
	long long int by = x;
	while (n) {
		if (n & 1) {
			ret *= by;
			ret %= M;
		}
		by *= by;
		by %= M;
		n >>= 1;
	}
	return ret;
}

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

	while (cin >> N >> M >> K, N) {
		vector<vector<long long int>>dp(N + 2, vector<long long int>(N + 2010));
		dp[0][0] = 1;
		dp[0][1] = -1;
		for (int i = 0; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				dp[i][j] += dp[i][j - 1];
				dp[i][j] %= MOD;
				//cout << j << " " << dp[i][j] << endl;
			}
			for (int j = 0; j <= N; j++) {
				dp[i + 1][j + 1] += dp[i][j];
				dp[i + 1][j + 1] %= MOD;
				dp[i + 1][j + K] += MOD - dp[i][j];
				dp[i + 1][j + K] %= MOD;
			}
		}
		long long int ans = 0;
		for (int i = 1; i <= N; i++) {
			long long int by = 1;
			long long int num = M - i;
			if (num < 0)continue;
			for (int j = 1; j <= i; j++) {
				by *= (num + j)%MOD;
				by %= MOD;
				by *= power(j, MOD - 2, MOD);
				by %= MOD;
			}
			ans += by * dp[i][N];
			ans %= MOD;
		//	cout << i << " " << ans << endl;
		}
		cout << ans << endl;
	}
}


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

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

    int n;
    cin >> n;

    set<int> st;
    REP(i, n){
        int d;
        cin >> d;
        st.insert(d);
    }

    cout << st.size() << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

#define rep(i,n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main() {
  string s, t;
  cin >> s >> t;

  std::sort(s.begin(), s.end());
  std::sort(t.begin(), t.end());

  int sz = std::min(s.size(), t.size());
  bool less = true;
  rep(i, sz) {
    if (s[i] > t[t.size() - 1 - i]) {
      less = false;
      break;
    } else if (s[i] < t[t.size() - 1 - i]) {
      break;
    }

    if (i == sz - 1 && s.size() >= t.size()) less = false;
  }

  if (less) cout << "Yes" << endl;
  else cout << "No" << endl;

  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 h = sc.nextInt();
		int w = sc.nextInt();
        int[][] counts = new int[h][w];
      
        for(int i = 0; i < h; i++) {
          // 文字列の入力
		  String[] s = sc.next().split("");
          for(int i2 = 0; i2 < w; i2++) {
            if (s[i2].equals("#")) {
              // 本体
              counts[i][i2] = -9;
              // 前
              if (i != 0) {
                counts[i - 1][i2]++;
              }
              // 後
              if (i != h - 1) {
                counts[i + 1][i2]++;
              }
              // 左
              if (i2 != 0) {
                counts[i][i2 - 1]++;
                // 前
                if (i != 0) {
                  counts[i - 1][i2 - 1]++;
                }
                // 後
                if (i != h - 1) {
                  counts[i + 1][i2 - 1]++;
                }
              }
              // 右
              if (i2 != w - 1) {
                counts[i][i2 + 1]++;
                // 前
                if (i != 0) {
                  counts[i - 1][i2 + 1]++;
                }
                // 後
                if (i != h - 1) {
                  counts[i + 1][i2 + 1]++;
                }
              }
            }
          }
        }
        for (int i = 0; i < h; i++) {
          String ans = "";
          StringBuilder builder = new StringBuilder();
          for (int i2 = 0; i2 < w; i2++) {
            int value = counts[i][i2];
            builder.append(value >= 0 ? value : "#");
          }
          // 出力
		  System.out.println(new String(builder));
        }
	}
}

Measured memory_bytes: 22740
/*input
18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i,j,k)     for(int i = j ; i < k ; ++i)
#define RREP(i,j,k)    for(int i = j ; i >=k ; --i)
#define A    first
#define B    second
#define mp   make_pair
#define pb   emplace_back
#define PII pair<int , int>
#define MEM(i,j)   memset(i , j , sizeof i)
#define ALL(i)     i.begin() , i.end()
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define int long long
#define MAX 
#define INF 0x3f3f3f3f
#define mod 1000000009LL
#define AC 10430579

int n;
map<PII , int> cc;
void solve(string s){
	REP(i , 0 , (1 << n)){
		int v1 = 0 , v2 = 0;
		RREP(j , n - 1 , 0) if((i & (1 << j)) == 0) v1 = (v1 * AC + s[j]) % mod;
		RREP(j , n - 1 , 0) if((i & (1 << j)) != 0) v2 = (v2 * AC + s[j]) % mod;
		cc[mp(v1 , v2)] ++;
	}
}
void S(string s){
	int ans = 0;
	REP(i , 0 , (1 << n)){
		int v1 = 0 , v2 = 0;
		REP(j , 0 , n) if((i & (1 << j)) == 0) v1 = (v1 * AC + s[j]) % mod;
		REP(j , 0 , n) if((i & (1 << j)) != 0) v2 = (v2 * AC + s[j]) % mod;
		ans += cc[mp(v1 , v2)];
	}
	cout << ans << endl;
}
string s;
int32_t main(){
	IOS;
	cin >> n >> s;
	string fr = s.substr(0 , n);
	string ba = s.substr(n , n);
	// cout << fr << endl;
	// cout << ba << endl;
	solve(fr);
	S(ba);

    return 0;
}

Measured memory_bytes: 33024
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	int n, input;
	cin >> n;
	vector<int> numbers;
	for(int i=1;i<=n;i++){
		cin >> input;
		numbers.push_back(input);
	}
  reverse(numbers.begin(),numbers.end());
	for(int i=0; i<numbers.size();i++){
		cout << numbers[i];
		if(i!=numbers.size()-1) cout << " ";
	}
  cout << endl;
}

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

int main(){
    string S;
    cin>>S;
    int min = 1000;
    FOR(i, 2, S.length()){
        min = std::min(abs(753 - stoi(S.substr(i-2, 3))), min);
    }

    cout << min << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S, T;
    cin >> S>> T;
    int ans = 0;
    for(int i = 0; i < 3; i++) {
        if(S[i] == T[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1e18;

int main(){
    int n,m;
    cin>>n>>m;
    ll ans=1900*m+100*(n-m);
    for(int i=0;i<m;i++){
        ans*=2;
    }
    cout<<ans<<endl;
}

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

using namespace std;

typedef pair<int, int> Pair;

int main() {
  int c, n, m, s, d, a, b, f;
  unsigned long long answer;
  vector<Pair> edges[1100];
  unsigned long long min_cost[1100];
  priority_queue<Pair, vector<Pair>, greater<Pair> > heap;
  while (true) {
    cin >> c >> n >> m >> s >> d;
    if (c == 0) {
      return 0;
    }
    for (int i = 0; i < (c + 1) * n; ++i) {
      edges[i].clear();
      min_cost[i] = -1;
    }
    for (int i = 0; i < m; ++i) {
      cin >> a >> b >> f;
      for (int ci = 0; ci <= c; ++ci) {
        edges[a - 1 + ci * n].push_back(Pair(b - 1 + ci * n, f));
        edges[b - 1 + ci * n].push_back(Pair(a - 1 + ci * n, f));
        if (ci < c) {
          edges[a - 1 + ci * n].push_back(Pair(b - 1 + ci * n + n, f / 2));
          edges[b - 1 + ci * n].push_back(Pair(a - 1 + ci * n + n, f / 2));
        }
      }
    }
    heap.push(Pair(0, s - 1));
    min_cost[s - 1] = 0;
    while (not heap.empty()) {
      int p1 = heap.top().second;
      heap.pop();
      for (size_t i = 0; i < edges[p1].size(); ++i) {
        int p2 = edges[p1][i].first;
        int len = edges[p1][i].second;
        if (min_cost[p1] + len < min_cost[p2]) {
          min_cost[p2] = min_cost[p1] + len;
          heap.push(Pair(min_cost[p2], p2));
        }
      }
    }
    answer = min_cost[d - 1];
    for (int ci = 1; ci <= c; ++ci) {
      answer = min(answer, min_cost[d - 1 + n * ci]);
    }
    cout << answer << endl;
  }
}

Measured memory_bytes: 1472
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxx = 1010;
int c[maxx][maxx];

int lcs(char s1[],char s2[]) {
    int m = strlen(s1), n = strlen(s2);
    for (int i = 0; i <= m; i++)
    c[i][0] = 0;
    for (int i = 0; i <= n; i++)
    c[0][i] = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (s1[i] == s2[j])
            c[i+1][j+1] = c[i][j] + 1;
            else
            c[i+1][j+1] = max(c[i][j+1], c[i + 1][j]);
        }
    }
    return c[m][n];
}
int main()
{
    char s1[maxx], s2[maxx];
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        scanf("%s %s", s1, s2);
        printf("%d\n",lcs(s1,s2));
    }
    
    return 0;
}



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



int main(){
    int n;
    cin >> n;
    double a[n+5];

    rep(i,n){
        cin >> a[i];
    }

    sort(a,a+n);
    double sum=(a[0]+a[1])/2;

    for(int i=2;i<n;i++){
        sum=(a[i]+sum)/2;
    }

    


cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
h, w = gets.split.map(&:to_i)
ans = 10 ** 10
(1...h).each do |height|
  half_width, mod = w.divmod(2)
  a = height * w
  b = (h - height) * half_width
  c = (h - height) * (half_width + mod)
  options = [a, b, c]
  gap = options.max - options.min
  ans = gap if ans > gap
end

if h >= 3
  third_height, mod = h.divmod(3)
  min = third_height * w
  max = mod.nonzero? ? (third_height + 1) * w : third_height * w
  gap = max - min
  ans = gap if ans > gap
end

h, w = w, h

(1...h).each do |height|
  half_width, mod = w.divmod(2)
  a = height * w
  b = (h - height) * half_width
  c = (h - height) * (half_width + mod)
  options = [a, b, c]
  gap = options.max - options.min
  ans = gap if ans > gap
end

if h >= 3
  third_height, mod = h.divmod(3)
  min = third_height * w
  max = mod.nonzero? ? (third_height + 1) * w : third_height * w
  gap = max - min
  ans = gap if ans > gap
end

puts ans


Measured memory_bytes: 1788
#include<stdio.h>
#define BUFSIZE 10000
#include<math.h>
#include<stdlib.h>
int a;
int flag=3;
int main (void){
	scanf("%d",&a);
	
if(a==2){
	printf("2");
}
		
	for(int i=0;i<BUFSIZE;i++){
	
	     for(int j=2;j<a+i;j++){
			 flag++;
			 if((a+i)%j==0){
              
				 break;
				 }
			if(flag==a+i && (a+i+1)%(a+i)!=0){
			  
				printf("%d",a+i);
	             exit(0);
			}
		 }
	
	}
	
}
				 

Measured memory_bytes: 128
#include <stdio.h>
#include <math.h>
#include <string.h>

int gcd(int a,int b){
    if(a<b){
        int now=a;
        a=b;
        b=a;
    }

    int r=a%b;
    while(r!=0){
        a=b;
        b=r;
        r=a%b;
    }

    return b;
}



/* 値を入れ替える関数 */
void swap (int *x, int *y) {
  int temp;    // 値を一時保存する変数

  temp = *x;
  *x = *y;
  *y = temp;
}

/***
* pivotを決め、
* 全データをpivotを境目に振り分け、
* pivotの添え字を返す
***/
int partition (int array[], int left, int right) {
  int i, j, pivot;
  i = left;
  j = right + 1;
  pivot = left;   // 先頭要素をpivotとする

  do {
    do { i++; } while (array[i] < array[pivot]);
    do { j--; } while (array[pivot] < array[j]);
    // pivotより小さいものを左へ、大きいものを右へ
    if (i < j) { swap(&array[i], &array[j]); }
  } while (i < j);

  swap(&array[pivot], &array[j]);   //pivotを更新

  return j;
}

/* クイックソート */
void quick_sort (int array[], int left, int right) {
  int pivot;

  if (left < right) {
    pivot = partition(array, left, right);
    quick_sort(array, left, pivot-1);   // pivotを境に再帰的にクイックソート
    quick_sort(array, pivot+1, right);
  }
}



int main(void){
    int h,a;
    scanf("%d%d",&h,&a);

    printf("%d\n",h/a+!!(h%a));
    return 0;
}

Measured memory_bytes: 1724
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define pb push_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
typedef long long ll;
typedef multiset<ll> S;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef priority_queue<ll> PQ;
typedef priority_queue<ll,vector<ll>,greater<ll>> SPQ;
using vi=vector<ll>;
using vvi=vector<vector<ll>>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
bool chmin(auto &a,auto b){if(a>b){a=b;return true;}return false;}
bool chmax(auto &a,auto b){if(a<b){a=b;return true;}return false;}
vector<bool> usea(100001),useb(100001);
vvi ga(100001),gb(100001);

void dfs(ll i,ll & a,ll & b){
    for(ll c:ga[i]){
        if(useb[c])continue;
        useb[c]=true;
        b++;
        for(ll d:gb[c]){
            if(usea[d])continue;
          	usea[d]=true;
            a++;
            dfs(d,a,b);
        }
    }
}

int main(){
    ll ans=0;
    rep(i,100001){
        usea[i]=false;useb[i]=false;
    }
    ll n;cin>>n;
    rep(i,n){
        ll a,b;cin>>a>>b;
        a--;b--;
        ga[a].pb(b);
        gb[b].pb(a);
    }
    rep(i,100001){
        if(usea[i])continue;
            usea[i]=true;
            ll a=1,b=0;
            dfs(i,a,b);
            ans+=a*b;
    }
    cout<<ans-n<<endl;
}

Measured memory_bytes: 10496
t = list(input())

for i,val in enumerate(t):
    if val =="?":
        t[i] = "D"

s = "".join(t)
print(s)
# ans = 0
#
# for i in range(len(s)-1):
#     if s[i:i+2] == "PD":
#         ans += 1
#
# for i in range(len(s)):
#     if s[i] == "D":
#         ans += 1
#
# print(ans)


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

using namespace std;

#define ll long long

int main(){
  ll n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  vector<ll> lc;
  vector<ll> rc;
  char prev_c = s[n - 1];
  ll count_c = 1;
  ll happy = 1;
  for(ll i = n - 2; i >= 0; i--){
    if(prev_c == s[i]){
      count_c++;
      happy++;
    }else{
      if(prev_c == 'R'){
        rc.push_back(count_c);
      }else{
        lc.push_back(count_c);
      }
      count_c = 1;
    }
    prev_c = s[i];
  }
  if(prev_c == 'R'){
    rc.push_back(count_c);
  }else{
    lc.push_back(count_c);
  }
  happy--;
  ll size = 2 * max(lc.size(), rc.size()) - 1;
  if(lc.size() != rc.size()){
    size--;
  }
  happy += min(size, 2 * k);
  
  cout << happy << endl;
  
  return 0;
}


Measured memory_bytes: 1404
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <string>

using namespace std;

#define int long long

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
	cin >> n;
	set<string> s;
	for(int i = 0; i < n; ++i)
	{
		string t;
		cin >> t;
		s.insert(t);
	}
	cout << s.size();
}

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ll r, g, b, n;
  cin >> r >> g >> b >> n;
  ll ans = 0;
  for (ll i = 0; i <= n; i++) {
    for (ll j = 0; j <= n; j++) {
      ll rest = n - i * r - j * g;
      if (rest < 0) continue;
      if (rest % b) continue;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

ll g[303][303],g2[303][303];
int N,M,L;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    rep(i,303)rep(j,303)g[i][j] = 1e18,g2[i][j] = 1e18;
    rep(i,303)g[i][i] = 0,g2[i][i] = 0;
    cin >> N >> M >> L;
    rep(i,M){
        ll a,b,c;
        cin >> a >> b >> c;
        a--;b--;
        if(c>L)continue;
        g[a][b] = c;
        g[b][a] = c;
    }
    rep(k,N)rep(i,N)rep(j,N)g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
    rep(i,N)rep(j,N){
        if(g[i][j]<=L)g2[i][j] = min(g2[i][j],1LL);
    }
    rep(k,N)rep(i,N)rep(j,N)g2[i][j] = min(g2[i][j],g2[i][k]+g2[k][j]);
    int Q;cin >> Q;
    vector<ll> ans;
    rep(i,Q){
        int s,t;
        cin >> s >> t;
        s--;t--;
        if(g2[s][t]>=1e18)ans.push_back(0);
        else ans.push_back(g2[s][t]);
    }
    for(auto x:ans)cout << x-1 << endl;
}

Measured memory_bytes: 2808
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60;
const ll mod=1e9+7;


vector<ll> inv,fact,invfact;
void mod_build(int n=101010){
    fact.resize(n+1);
    inv.resize(n+1);
    invfact.resize(n+1);
    fact[0]=inv[0]=invfact[0]=1;
    inv[1]=1;
    rep(i,n){
        fact[i+1]=fact[i]*(i+1)%mod;
        if(i>0)inv[i+1]=mod-inv[mod%(i+1)]*(mod/(i+1))%mod;
        invfact[i+1]=invfact[i]*inv[i+1]%mod;
    }
}
ll perm(int n,int k){
    if(n<0||k<0||k>n)return 0;
    return fact[n]*invfact[n-k]%mod;
}
ll comb(int n,int k){
    if(n<0||k<0||k>n)return 0;
    return (fact[n]*invfact[n-k]%mod)*invfact[k]%mod;
}
ll powmod(ll n,ll k){
    k%=mod-1;
    if(k<0)k+=mod-1;
    ll ret=1;
    while(k){
        if(k&1)ret=ret*n%mod;
        n=n*n%mod;
        k>>=1;
    }
    return ret;
}
int main(){
    int n,k;
    cin>>n>>k;
    mod_build();
    if(n==k){
        cout<<1<<endl;
        rep(i,n-1)cout<<0<<endl;
        return 0;
    }
    rep(i,k){
        ll ans = 0;
        ans =  comb(n-k+1,i+1)%mod;
        ans *= comb(k-1,i)%mod;
        cout<<ans%mod<<endl;
    }
    return 0;
}


Measured memory_bytes: 2688
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 30;
const int MOD = 1e9 + 7;

const int N = 1e5 + 10;
ii a[N];
int64 ret[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i].first);
    a[i].second = i + 1;
  }
  sort(a, a + n, greater<ii>());
  int sum = 0, idx = n;
  for (int i = 0, j; i < n; i = j) {
    for (j = i; j < n && a[j].first == a[i].first; ++j) {
      idx = min(idx, a[j].second);
    }
    sum += j - i;
    ret[idx] += j == n ? (int64)sum * a[i].first : (int64)sum * (a[i].first - a[j].first);
  }
  for (int i = 1; i <= n; ++i) {
    printf("%lld\n", ret[i]);
  }
  return 0;
}


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

int N;

int main()
{
    cin >> N;
    int cnt = 0;
    for (int C = 1; C < N; C++)
    {
        int X = N - C;
        for (int A = 1; A * A <= X; A++)
        {
            if (X % A == 0 && X / A == A)
            {
                cnt += 1;
            }
            else if (X % A == 0)
            {
                cnt += 2;
            }
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
#define rep(i,n) for(int i=0;i<n;++i)
typedef long long int ll;
typedef unsigned long long ull;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
typedef pair<ll,ll> P;


int main()
{
    ll n,k; cin >> n >> k;
    vector<int>d(n+1);
    rep(i,n+1)d[i]=0;
    rep(i,n)
    {
        int a; cin>>a;
        d[a]++;
    }
    sort(d.begin(),d.end());
    ll ans=0;
    for(int i=n;n-i!=k;--i)
    {
        ans +=d[i];
    }

    cout<<n-ans;
    return 0;
}

Measured memory_bytes: 1024
using System;
using System.Linq;
using System.Collections.Generic;

class Dmondai
{
    static void Main()
    {
        var nk = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        var N = nk[0];
        var K = nk[1];
        var S = Console.ReadLine();
        var list = new List<int[]>();
        var currentNum = -1;
        var currentNumCount = 0;
        var zeroCount = 0;
        var isFirstZero = false;
        var allCount = 0;
        for (int i=0;i<N;++i)
        {
            if (currentNum != S[i])
            {
                allCount++;
                if (currentNum == -1) isFirstZero = S[i] == '0';
                if (S[i] == '0') zeroCount++;
                if (currentNum != -1) list.Add(new int[2]{currentNum,currentNumCount});
                currentNum = S[i];
                currentNumCount = 1;
            }
            else currentNumCount++;
            if (i == N - 1) list.Add(new int[2] { currentNum, currentNumCount });
        }
        var ans = 0;
        var count = zeroCount - K+1;
        //isFirstZero 0246 else 1357
        //一番初め
        var c = 0;
        if (isFirstZero)
        {
            var iC = 2 * K-1;
            for (int i=0;i<=iC;++i) if (i < allCount) c += list[i][1];
        }
        else
        {
            var iC = 2 * K;
            for (int i = 0; i <= iC; ++i) if (i < allCount) c += list[i][1];
        }
        if (ans < c) ans = c;
        //累積和
        for (int i=1;i<count;++i)
        {
            //引く
            if (i == 1 && isFirstZero)
            {
                c -= list[0][1];
            }//0246
            else if(isFirstZero)
            {
                c -= (list[(i - 1) * 2][1] + list[(i - 1) * 2-1][1]);
            }//1357
            else
            {
                c -= (list[(i - 1) * 2][1] + list[(i - 1) * 2+1][1]);
            }
            //足す
            //0246
            if (isFirstZero)
            {
                var addIndex = (i + K - 1) * 2;
                c += list[addIndex][1];
                if(addIndex+1<allCount)c+= list[addIndex + 1][1];
            }//1357
            else
            {
                var addIndex = (i + K - 1) * 2 + 1;
                c += list[addIndex][1];
                if(addIndex+1<allCount) c += list[addIndex+1][1];
            }
            if (ans < c) ans = c;
        }
        Console.WriteLine(ans);
    }
}

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

vector<int> g[605];
double kakuritu[605];
double kitaiti[605];

int main() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int s, t; cin >> s >> t; --s, --t;
        g[s].push_back(t);
    }
    kitaiti[n - 1] = 0;
    kakuritu[0] = 1;
    for (int i = 0; i < n; i++) {
        for (auto to : g[i]) {
            kakuritu[to] += kakuritu[i] / (double)g[i].size();
        }
    }

    for (int i = n - 1; i >= 0; i--) {
        for (auto to : g[i]) {
            kitaiti[i] += (kitaiti[to] + 1) / (double)g[i].size();
        }
    }

    double ans = 0;

    for (int i = 0; i < n; i++) {
        for (auto to : g[i]) {
            double ato;
            if (g[i].size() == 1) continue;
            ato = (kitaiti[i] * g[i].size() - (kitaiti[to] + 1)) / (double)(g[i].size() - 1);
            ans = max(ans, (kitaiti[i] - ato) * kakuritu[i]);
        }
    }

    cout << fixed << setprecision(10);
    cout << kitaiti[0] - ans << endl;
}

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

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
const int MOD = 1e9 + 7;

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

    int n;cin>>n;
    vector<ll> x(n),tmp(n);
    for(int i=0;i<n;i++){
        cin>>x[i];
        tmp[i]=x[i];
    }
    sort(tmp.begin(),tmp.end());
    for(int i=0;i<n;i++){
        if(x[i]>=tmp[n/2]) cout<<tmp[n/2-1]<<endl;
        else cout<<tmp[n/2]<<endl;
    }
}


Measured memory_bytes: 5376
#include <iostream>
#include <map>

using namespace std;

int main()
{
  long N, M;
  cin >> N >> M;

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

  long B[ N + 1 ];
  B[ 0 ] = 0;

  for( long i = 0; i < N; ++i )
  {
    B[ i + 1 ] = ( B[ i ] + A[ i ] ) % M;
  }

  map<long, long> map;

  for( long i = 0; i < N + 1; ++i )
  {
    map[ B[ i ] ]++;
  }

  long ans = 0;
  for( auto entry : map )
  {
    ans += ( entry.second * ( entry.second - 1 ) ) / 2;
  }

  cout << ans << endl;

  return 0;
}


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

int main(){
    string b;
    cin>> b;
    if(b=="A"){
        cout << "T" <<endl;
    }
    else if(b=="T"){
        cout << "A" <<endl;
    }
    else if(b=="C"){
        cout << "G" <<endl;
    }
    else if(b=="G"){
        cout << "C" <<endl;
    }
    return 0;
}


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

int main()
{
    long N, M;
    cin >> N >> M;
    vector<long> divisor;
    long i;
    long result = 1;

    for(i = 1; i < sqrt(M); i++) {
        if (M % i == 0) {
            divisor.push_back(i);
            divisor.push_back(M / i);
        }
    }
    sort(divisor.begin(), divisor.end());

    for(i = 0; i < divisor.size(); i++) {
        if(divisor[i] > M / N) break;
        result = divisor[i];
    }

    cout << result;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>

#define f first
#define s second

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define print(x) printf("%d\n",x)

using namespace std;

const int _dx[] = {0,1,0,-1};
const int _dy[] = {-1,0,1,0};

int getInt(){
  int a; scanf("%d", &a); return a;
}

int p[10][10];
int id[10][10];
int w, h;
int cnt[100];
int all[100];
int g[100][100];
int idcnt;
double cap[100];

void dfs(int y, int x, int ids){
  id[y][x] = ids;

  REP(i,4){
    int yy = y + _dy[i];
    int xx = x + _dx[i];

    if(ISIN(xx, yy, w, h) && id[yy][xx] == -1 && p[yy][xx] == p[y][x]){
      dfs(yy, xx, ids);
    }
  }
}

const double eps = 1e-10;
void doflow(int i, double f){
  if(f < eps) return;
  double rest = (30.0 - cap[i]) * (cnt[i] * 30.0 * 30.0);

  if(rest < f){
    cap[i] = 30.0;
    f -= rest;
  }else{
    cap[i] += f / (cnt[i] * 30.0 * 30.0);
    f = 0.0;
  }

  if(f > eps){
    REP(j,idcnt) if(g[i][j] > 0){
      doflow(j, f * g[i][j] / all[i]);
    }
  }
}

int main(){
  while(true){
    w = getInt();
    h = getInt();

    if(w + h == 0) break;

    int fx = getInt();
    int fy = getInt();
    int fp = getInt();

    REP(i,h) REP(j,w){
      p[i][j]  = getInt();
      id[i][j] = -1;
    }

    int l = getInt();

    vector<pair<int, pair<int, int> > > q(l);

    REP(i,l){
      q[i].f   = getInt();
      q[i].s.f = getInt();
      q[i].s.s = getInt();
    }

    // ID
    idcnt = 0;
    REP(i,h) REP(j,w) if(id[i][j] == -1 && p[i][j] != 0){
      dfs(i,j,idcnt++);
    }

    REP(i, idcnt){
      cnt[i] = 0;
      all[i] = 0;
      REP(j, idcnt){
        g[i][j] = 0;
      }
    }

    REP(y,h) REP(x,w) if(id[y][x] != -1){
      cnt[id[y][x]]++;

      REP(k,4){
        int yy = y + _dy[k];
        int xx = x + _dx[k];

        if(ISIN(xx, yy, w, h) && id[yy][xx] == id[y][x]){
        }else{
          if(ISIN(xx, yy, w, h) && id[yy][xx] != -1){
            if(p[y][x] > p[yy][xx]){
              all[id[y][x]]++;
              g[id[y][x]][id[yy][xx]]++;
            }else{
            }
          }else{
            all[id[y][x]]++;
          }
        }
      }
    }

    int sid  = id[fy][fx];
    REP(i,l){
      int t = q[i].f;
      int x = q[i].s.f;
      int y = q[i].s.s;

      REP(i,idcnt) cap[i] = 0.0;
      doflow(sid, fp * t);

      printf("%d\n", (int)floor(cap[id[y][x]] + eps));
    }
  }

  return 0;
}

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, b, a) for(int i = b - 1; i >= a; i--)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define hash dhsjakhd
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;

unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937 eng(seed);

uniform_int_distribution<> DD(0, (1ll << 31));

ll random2(){
    return (ll(DD(eng))*(1ll << 31) + ll(DD(eng))) & ((1ll << 62ll)-1);
}

ll n,m,T,k,q;

const ll big = 1000000007;
const ll big2 = 1000000009;
const ll mod =  998244353;
const ll MAXN = 300001;

vl P;
ll ord[MAXN] = {0};

bool smallest[MAXN] = {0};
bool biggest[MAXN] = {0};

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

    //freopen("input.txt","r",stdin);
    //freopen("autput.txt","w",stdout);
    ll a,b,c,d,e;

    cin >> n >> k;
    rep(c1,0,n){
        cin >> a;
        P.push_back(a+1);
        ord[a+1] = c1;
    }
    ord[n+1] = -1;
    ord[0] = n;
    vl mq;
    mq.push_back(n+1);
    ll ans = 0;

    rep(c1,0,n){
        while(mq.back() < P[c1]){
            mq.pop_back();
        }
        if(c1-ord[mq.back()] >= k){
            biggest[c1] = 1;
        }//cerr << biggest[c1];
        mq.push_back(P[c1]);
    }//cerr << "\n";

    mq.clear();
    mq.push_back(0);
    for(int c1 = n-1; c1 >= 0; c1--){
        while(mq.back() > P[c1]){
            mq.pop_back();
        }
        if(ord[mq.back()] - c1 >= k){
            smallest[c1] = 1;
        }
       //cerr << smallest[c1];
        mq.push_back(P[c1]);
    }//cerr << "\n";

    int latest = -1;
    bool nothing = 0;
    rep(c1,0,n){

        if(c1 >= k-1){
            bool inc = 0;
            if(c1 == k-1 || !(biggest[c1] && smallest[c1-k])){
                ans++;
                inc = 1;
            }
            if(c1-latest >= k){
                if(nothing && inc)ans--;
                nothing = 1;
            }
        }

        if(c1 < n-1 && P[c1] > P[c1+1])latest = c1;
    }

    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 4084
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e15;
const ll MOD = 100000000;
const ll MOD2 = 998244353;
typedef pair<ll,ll> P;
const ll MAX = 200010;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin >> n >> m;
    ll ans = 0,s = m/n;
    ll k = sqrt(m);
    rep(i,1,k+1){
        if (m%i == 0){
            if (m/i <= s) chmax(ans,m/i); 
            if (i <= s) chmax(ans,i);
        }
    }
    PRINT(ans);
}



Measured memory_bytes: 256
/*                          /
/      2014.08.26           /
/                          */

//真っ白な紙にインクを垂らしインク絵汚れていない部分の数を出力し、汚れる回数が多いエリアを出力する。
//落とすインク液は少しならば１、中ぐらいなら２、多いならば３とする。
#include<stdio.h>

void littleDrop(int,int,int *,int);
void midiumDrop(int,int *,int,int);
void largeDrop(int,int *,int);
void showArray(int [][10]);

void largeDrop(int center,int *tbl,int place){
	if(center >= 20)//二つ上に配列があるか確認
		*(tbl - 20) += 1;
	if(place >= 2)//二つ左に配列があるか確認
		*(tbl - 2) += 1;
	if(place <= 7)//二つ右に配列があるか確認
		*(tbl + 2) += 1;
	if(center <= 80)//二つ下に配列がある確認
		*(tbl + 20) += 1;
}

void midiumDrop(int center,int *tbl ,int size, int place){
//右上、右下、左上、左下に+1//
	if(center > 10){//上に配列がある
		if(place != 0)//左に配列があるか確認
			*(tbl - 11) += 1;
		if(place != 9)//右に配列があるか確認
			*(tbl - 9) += 1;
	}
	if(center < 90){//下に配列がある
		if(place != 0)//左に配列があるか確認
			*(tbl + 9) += 1;
		if(place != 9)//右に配列があるか確認
			*(tbl + 11) += 1;
	}
	if(size == 3)
		largeDrop(center,tbl,place);
}

void littleDrop(int x ,int y ,int *tbl,int size){
//インクを落とす場所は左上(0,0)から何番目かを求める。
	int center = x + y * 10;
	int place = center % 10;//左、右に配列があるか確認するときに使用
//(0,0)からインクの落下位置へと移動させる
	tbl = (tbl + center);

//真ん中に+1
	*(tbl) += 1;
//上に+1
	if(center >= 10)//centerが最上列でない
		*(tbl - 10) += 1;
	if(center <= 90)//centerが最下列でない
		*(tbl + 10) += 1;
	if(place != 0)//centerが左側でない
		*(tbl - 1) += 1;
	if(place != 9)//centerが右側でない
		*(tbl + 1) += 1;
	if(size >= 2)
		midiumDrop(center, tbl, size,place);
}

void showArray(int in[10][10]){
	int i,j;
	for(i = 0 ; i < 10 ;i ++){
		for(j = 0; j < 10; j ++){
			printf("%d ",in[i][j]);
		}
		printf("\n");
	}
}


int main(void){
	int i,j,clear,max;
	int x,y,size;
	int tbl[10][10] = {0};

	while(scanf(" %d,%d,%d",&x ,&y ,&size) != EOF){
		//getchar();//バッファに\nがたまるのを防ぐ
		if(size <= 3 && x <= 9 && y <= 9)
			littleDrop(x,y,*tbl,size);
		//showArray(tbl);
	}

	for(i = 0, clear = 0, max = 0; i < 10 ;i ++){
		for(j = 0; j < 10; j ++){
			//showArray(tbl);//確認用
			if(tbl[i][j] == 0)
				clear ++;
			else if(tbl[i][j] > max)
				max = tbl[i][j];
		}
	}
	printf("%d\n",clear);//インクが落ちていない個所の合計
	printf("%d\n",max);//一番多くインクが落ちた量

	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using i64 = long long;

auto calc(const std::string &s) {
    std::vector<int> a(s.size() + 1);
    a[0] = -1;
    for (int i = 0, j = -1; i < s.size(); i++) {
        while (j >= 0 && s[i] != s[j]) j = a[j];
        j++;
        a[i + 1] = s[i + 1] == s[j] ? a[j] : j;
    }
    return a;
}

int main() {
    std::string s, t;
    std::cin >> s >> t;
    int n = s.size(), m = t.size();
    std::vector<int> e(s.size());
    auto ss = s;
    while (ss.size() < s.size() + t.size()) ss += s;
    auto a = calc(t);

    for (int i = 0, j = 0; i < ss.size(); i++) {
        while (j >= 0 && ss[i] != t[j]) j = a[j];
        j++;
        if (j == m) {
            e[(i - m + 1) % n] = 1;
            j = a[j];
        }
    }

    int ret = 0;
    std::vector<int> p(n);
    for (int i = 0; i < n; i++) {
        if (e[i] < 0 || p[i]) continue;
        int j = i, tmp = 0;
        while (!p[j] && e[j]) {
            p[j] = 1;
            j = (j + m) % n;
            if (j == i) {
                std::cout << -1 << std::endl;
                return 0;
            }
            tmp++;
        }
        p[i] = tmp + p[j];
        ret = std::max(ret, p[i]);
    }

    std::cout << ret << std::endl;

    return 0;
}


Measured memory_bytes: 8756
#include <iostream>
#include <algorithm>
using namespace std;
int data[100010];
int main()
{
	int n,q,ans = 0,L,R,mid,x;
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> data[i];
	cin >> q;
	while(q--)
	{
		cin >> x;
		if(*lower_bound(data+1,data+n+1,x) == x)
			++ans;
	}
	cout << ans << endl;
	return 0;
}


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

const ll MAXN = 200000;

ll N, ans=0, tmp=0, maxi=0;
vector<ll> A(MAXN, 0);

signed main(){
    cin >> N;
    for(int i=0;i<N;i++) {
        cin >> A[i];
        if(tmp<A[i]) {
            tmp = A[i];
            maxi = i;
        }
    }
    double a = tmp/2.0;
    double tmp1=tmp;
    ll id = 0;
    for(int i=0;i<N;i++) {
        if(maxi!=i&&tmp1>abs(A[i]-a)) {
            id = i;
            tmp1=abs(A[i]-a);
        }
    }
    cout << tmp << " " << A[id] << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	long long int N, A, B, C, D, E;
	cin >> N >> A >> B >> C >> D >> E;
	long long int a[5] = { A,B,C,D,E };
	sort(a, a + 5);

	cout << (N - 1) / a[0] + 5;
}

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

int main(){
    int n;
    int a,b;
    int c[10000];
    int j=0;
    int m=1;
    cin >> n;
    cin >> a >> b;

    for(int i=2;i<100000000;i++){
        if(a%i != 0)  continue;
        if(b%i != 0)  continue;
        c[j]=i;
        j++;
        a/=i;
        b/=i;
        i-=1;
    }
    for(int i=0; i<j;i++){
        m=m*c[i];
    }
    for(int i=1;i<=m;i++){
        if(m%i!=0) continue;
        cout << i <<endl;
    }

}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rREP(i,m,n) for(int (i)=(n)-1; (i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	int N; cin >> N;
	vector<ll>vec(N);
	rep(i, 0, N)cin >> vec[i];
	rep(i, 1, N) {
		vec[i] += vec[i - 1];
	}
	ll ans = (ll)1e18;
	rep(i, 0, N - 1) {
		ll a = vec[i];
		ll b = vec[N - 1] - vec[i];
		ans = min(ans, abs(a - b));
	}
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <limits>
#include <string>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n); i > 0; i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using lint = long long;
using P = pair<int, int>;

// int F, H, I, J, K, L, M, N, S, T, U, W;
lint F, H, I, J, K, L, M, N, S, T, U, W;
// string A, B;
string ans;
unsigned long long a, b, c;

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

	cin >> a >> b >> c;

	if (a >= c || b >= c) {
		cout << "No" << endl;
		return 0;
	}

	if (a * b * 4 < (c - a - b) * (c - a - b)) {
		ans = "Yes";
	} else {
		ans = "No";
	}

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

Measured memory_bytes: 256