akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define LB(a,x) lb(all(a),x)-a.begin()
#define UB(a,x) ub(all(a),x)-a.begin()
#define mod 1000000007
//#define mod 998244353
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }
template<class T> inline void out(T a){ cout << a << '\n'; }
void YN(bool ok){if(ok) cout << "Yes" << endl; else cout << "No" << endl;}
//void YN(bool ok){if(ok) cout << "YES" << endl; else cout << "NO" << endl;}


const ll INF=1e18;
const int mx=200005;

//#include<atcoder/all>
//using namespace atcoder;

ll mod_pow(ll x,ll n,ll m){
    if(n==0) return 1;
    ll res=mod_pow(x*x%m,n/2,m);
    if(n&1) res=res*x%m;
    return res;
}

ll modinv(ll n){
    return mod_pow(n,mod-2,mod);
}

class UnionFind{
public:
    vector<ll> par,num;

    int find(ll v){
        return (par[v]==v)? v: (par[v]=find(par[v]));
    }
    explicit UnionFind(ll N):par(N),num(N,1){
        iota(par.begin(),par.end(),0);
    }
    void unite(ll u,ll v){
        u=find(u),v=find(v);
        if(u==v)return ;
        if(num[u]<num[v])swap(u,v);
        num[u] += num[v];
        par[v] = u;
    }
    bool same(ll u,ll v){
        return find(u) == find(v);
    }
    bool ispar(ll v){
        return v=find(v);
    }
    ll size(ll v){
        return num[find(v)];
    }
};

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    UnionFind uf(n);
    rep(i,m){
        ll a,b;
        cin>>a>>b;
        a--;b--;
        uf.unite(a,b);
    }
    set<ll> st;
    rep(i,n) st.insert(uf.find(i));
    ll ans=(ll)st.size();
    out(ans-1);
}
//ペナルティ出しても焦らない　ACできると信じろ！！！
//どうしてもわからないときはサンプルで実験　何か見えてくるかも
//頭で考えてダメなら紙におこせ！！
/*
V,P(大文字)使用不可
乗算などの際にオーバーフローに注意せよ！
(適切にmodをとれ　にぶたんで途中で切り上げろ)
制約をよく読め！
{
    ・全探索できるなら全探索しろ
    ・異常な制約ならそこに注目
}
stringの計算量(扱い)注意
コーナー注意！(特に数値が小さいものについては要検証)
N行出力のときは'¥n'
グリッド上では行先が範囲内におさまるかif文で確認(RE注意)
if文ではちゃんと比較演算子==を使え('='でもエラー出ない)
配列(vector)の大きさが0か1以上かで場合分けせよ(RE注意)
(vector<int> a(m)でm==0というものはできない)
modはなるべく最後に取れ！
doubleを扱うときには(abs)ではなく'fabs'!!!
dpするときは「配る」、「もらう」の両方を考えて最適な方を選べ
*/

Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

void yes() {
  cout << "Yes" << endl;
  exit(0);
}

void no() {
  cout << -1 << endl;
  exit(0);
}

int main() {
  ll n, m;
  cin >> n >> m;
  vector<ll> a(n, -1), s(m), c(m);
  REP(i, m) {
    cin >> s[i] >> c[i];
    s[i]--;
  }

  if (n == 1 && m == 0) {
    cout << 0 << endl;
    exit(0);
  }

  REP(i, m) {
    if (a[s[i]] == -1) {
      a[s[i]] = c[i];
    } else if (a[s[i]] != c[i]) {
      no();
    }
  }

  if (n > 1) {
    if (a[0] == 0) {
      no();
    } else if (a[0] == -1) {
      a[0] = 1;
    }
  }

  FOR(i, 1, n) {
    if (a[i] == -1) {
      a[i] = 0;
    }
  }

  REP(i, n) { cout << a[i]; }
  cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)
using namespace std;

using ll = long long;

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; }
const int INF = 1001001001;
const long long INFLL = LLONG_MAX / 3;
const double eps = (1e-9);


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

  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) {
    cin >> a[i];
    a[i]--;
  }

  set<int> s;
  rep(i, n) {
    if (a[a[i]] == i) s.insert(min(int(i), a[i]));
  }

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

  return 0;
}


Measured memory_bytes: 2944
#include<stdio.h>
#include<string.h>
main(){
  int data,i,j;
  int a[101][101];
  while(1){
    scanf("%d",&data);
    if(data == 0) break;
    for(i=0;i<data;i++){
      for(j=0;j<data;j++){
	scanf("%d",&a[i][j]);
	a[i][data] += a[i][j];
	a[data][j] += a[i][j];
	a[data][data] += a[i][j];
      }
    }
    for(i=0;i<data+1;i++){
      for(j=0;j<data+1;j++){
	printf("%5d",a[i][j]);
	if(j == data){
	  printf("\n");
	}
      }
    }
    for(i=0;i<data+1;i++){
      for(j=0;j<data+1;j++){
	a[i][j] = 0;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 628
#import numpy as np
from collections import deque
#T= str(input())
#K = int(input())
N,M= map(int,input().split())
#A = list(map(int,input().split()))
#B = list(map(int,input().split()))
#S= str(input())
ans=[-1]*(N+1)
X=[[] for i in range(N+1)]
#print(X)
for i in range(M):
    a,b= map(int,input().split())

    X[a].extend([b])
    X[b].extend([a])
#print(X)
c=0
dq=deque([1])

while c<N:
    i = dq.popleft()
    for j in X[i]:
        if ans[j]==-1:
            ans[j]=i
            c+=1
            dq.append(j)
            #print(ans)
print('Yes')
print(*ans[2:],sep='\n')


Measured memory_bytes: 35648
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main(void){
    cout << "Christmas";
    int d;
    scanf("%d",&d);
    while(d<25){
        cout << " Eve";
        d++;
    }
    cout << endl;
    return 0;
}

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


int main(){
	int	n,m;
	cin>>n>>m;
	bool ok[n];
	rep(i,n) ok[i]=false;
	int ans1=0,ans2=0;
	map<int,int> M;
	rep(i,m){
		int p;
		string s;
		cin>>p>>s;
		p--;
		if(ok[p]) continue;
		if(s=="AC"){
			ok[p]=true;
			ans1++;
			ans2+=M[p];
		}
		else{
			M[p]++;
		} 
	}
	cout<<ans1<<" "<<ans2<<endl;
}

Measured memory_bytes: 4992
H, W = map(int, input().split())

a = [[2]*(W+2)]
pos = []
for i in range(H):
    aa = list(map(int, input().split()))
    aaa = [ai%2 for ai in aa]
    a.append([2] + aaa + [2])
a.append([2]*(W+2))

temp = [[1, 1]]
visited = [[0]*(W+2) for _ in range(H+2)]
visited[1][1] = 1
ans = []
while temp:
    q = temp.pop()
    if a[q[0]][q[1]] % 2 == 1:
        old = q[:]
        da = 1
    else:
        old = [-1, -1]
        da = 0
        
    for dy, dx in [[0, 1], [0, -1], [1, 0]]:
        nxt = a[q[0]+dy][q[1]+dx]
        if nxt == 2 or visited[q[0]+dy][q[1]+dx] == 1: continue
        else:
            temp.append([q[0]+dy, q[1]+dx])
            visited[q[0]+dy][q[1]+dx] = 1
            if old != [-1, -1]: ans.append([old[0], old[1], q[0]+dy, q[1]+dx])
            a[q[0]+dy][q[1]+dx] += da
            break

print(len(ans))
for i in ans:
    print(*i)
      

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

using namespace std;

int main() {
    string a, b, c;
    cin >> a >> b >> c;
    if (a.back() == b[0] && b.back() == c[0]) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
//include
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath> 
#include <iomanip>
#include <math.h>
#include <utility>
#include <functional>
#include <cstdlib>
#include <map>
#include <utility>
//using
using namespace std;
using vl = vector <long long>;
using vs = vector <string>;
using vc = vector <char>;
using ll= long long;
using vvl = vector<vector<ll> >;
using vvc = vector<vector<char> >;
//vector<vector<char> > hyou(N, vector<char>(N));
using vd = vector <double>;
//define
//#define int long long
#define rep(i,n) for(int i=0; i<n; i++)
#define print(n) cout<<n<<endl;
#define sortp(d) sort(d.begin(),d.end()) //1234
#define sortm(d) sort(d.rbegin(),d.rend()) //4321
//素数判定　O(√A) 
bool is_prime(int x){
 if(x<=1) return false;
 for(int i=2;i*i<=x;i++)
 if(x%i==0) return false;
 return true;
 }
 //各位の和　
int wa(ll x)
{
ll sum = 0;
while(x!=0){
  sum += x% 10;
  x /= 10;
}
return sum;
}
/*順列生成
do {
  // 順列に対する処理
} while (next_permutation(配列変数.begin(), 配列変数.end()));*/

//絶対値　abs()
//文字→数字　'0' アルファベット→数字　'a'　'A'が65番,'a'が97番だわ
//型キャスト　char('a'+1)
//reverse 回文
//if(isupper('A'))->大なら真


//グローバル変数宣言
ll p=0,q=0,r=0;

int main()
{
  string n;
  cin>>n;
  
  p=n.size();
  rep(i,p-1)
  {
    if(n[i+1]=='9')r++;
  }
  if (r==p-1)
  {
    q=(p-1)*9+n[0]-'0';
  }
  else
  {
    q=(p-1)*9+n[0]-'1';
  }
  
  print(q);
  
}

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

using namespace std;

int main()
{
    int X,Y,Z;
    cin>>X>>Y>>Z;
    if(X>=1&&Y>=1&&Z>=1&&X<=100&&Y<=100&&Z<=100){
        cout<<Z<<" "<<X<<" "<<Y;
    }
    return 0;
}

Measured memory_bytes: 3604
import math

n, a, b = map(int, input().split())

sum_all = 0
for i in range(1, n + 1):
    sum_n = 0
    m = i
    while(m > 0):
        sum_n += math.floor(m % 10)
        m = int(m / 10)
    if a <= sum_n <= b:
        sum_all += i

print(sum_all)

Measured memory_bytes: 3060
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
  static void Main(string[] args)
  {
    int[] input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    int N = input[0];
    int A = input[1];

    int[] x = new int[N + 1];
    input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    for (int i = 0; i < N; ++i)
    {
      x[i + 1] = input[i];
    }

    long[,,] dp = new long[N + 1, N + 1, N * A + 1];

    for (int i = 0; i < N; ++i) dp[i, 0, 0] = 1;

    for (int i = 1; i <= N; ++i)
    {
      for (int j = 1; j <= i; ++j)
      {
        for (int k = 1; k <= N * A; ++k)
        {
          if (k < x[i])
          {
            dp[i, j, k] = dp[i - 1, j, k];
          }
          else
          {
            dp[i, j, k] = dp[i - 1, j, k] + dp[i - 1, j - 1, k - x[i]];
          }
        }
      }
    }

    long ans = 0;
    for (int j = 1; j <= N; ++j)
    {
      ans += dp[N, j, j * A];
    }

    Console.WriteLine(ans);
  }
}


Measured memory_bytes: 62304
//header{{{
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/math/common_factor_rt.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
  
using namespace std;
//using namespace boost;
//using namespace multiprecision;  

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(12)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7; 
constexpr int mod2 = 998244353;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
  
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }

constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
//}}}


signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int k, n;
    cin >> n >> k;

    vector<int> p(n);

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

    sort(all(p));

    int sum = 0;

    rep(i,k){
        sum += p[i];
    }
    
    cout << sum << '\n';

    return (0);
}


Measured memory_bytes: 3668
#!/usr/local/env python3

import sys


def main():
    while True:
        count = 0
        n, r = map(int, sys.stdin.readline().split())
        if n == r == 0:
            break
        for n1 in range(1, n-1):
            for n2 in range(n1+1, n):
                for n3 in range(n2+1, n+1):
                    if n1 + n2 + n3 == r:
                        count += 1
        print(count)


if __name__ == '__main__':
    main()

Measured memory_bytes: 7636
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    string a,b;
    bool hantei=false;
    cin >> a >> b;
    int ans = stoi(a+b);
    for(int i=1; i<=10000; i++){
        if(i*i == ans) hantei = true;
    }
    if(hantei) cout << "Yes"<<endl;
    else    cout << "No" <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
#include <list>
#include <time.h>
using namespace std;
#define pi pair<int,int>
#define pl pair<long long,long long>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define en cout << endl //セミコロンつけろ
//#define MM 1000000000
//#define MOD MM+7
const int MM = 1e9;
const int MOD = MM+7;
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
// 'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}


int main(){
    string s,t; cin >> s >> t;
    map<char,set<int>> mp;
    for (int i = 0; i < s.size(); i++){
        mp[s[i]].insert(i);
    }
    long long cp = -1,ans = 0,sz = s.size();
    for (int i = 0; i < t.size(); i++){
        auto it = mp[t[i]].upper_bound(cp);
        if (it != mp[t[i]].end()){
            ans += *it - cp, cp = *it;
        } else {
            it = mp[t[i]].upper_bound(-1);
            if (it != mp[t[i]].end()){
                ans += sz - cp + *it, cp = *it;
            } else {
                return cout << -1 << endl, 0;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 5248
#方針: 中心点は 101×101パターンしかないので全探索できる。
n = gets.to_i
ary = Array.new(n){gets.split.map(&:to_i)}.sort_by{|a| a[2]}.reverse

(0..100).each do |i|
  (0..100).each do |j|
    tmp1 = [] #h>0が矛盾しないか判定用
    tmp2 =[] #h=0が矛盾しないか判定用
    ary.each do |a|
      if a[2]>0
        tmp1 << (a[0]-i).abs + (a[1]-j).abs + a[2]
      else
        tmp2 << a
      end
    end
    if tmp1.uniq.length == 1
      flag = true
      tmp2.each do |t|
        if tmp1[0] - (t[0]-i).abs - (t[1]-j).abs > 0
          flag = false
        end
      end
      puts "%d %d %d" % [i,j,tmp1[0]] if flag
    end
  end
end

Measured memory_bytes: 3704
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
    ll n,x,t;
    cin>>n>>x>>t;
    if(n%x==0){
        cout<<n/x*t;
    }
    else{
        cout<<(n/x+1)*t;
    }
    return 0;
}

Measured memory_bytes: 3636
# -*- coding: utf-8 -*-

import collections

def factorial(n):
    a = 1
    for i in xrange(1, n + 1):
        a *= i
    return a

def prime_decomposition(n):
    i = 2
    counter = []
    while i < n:
        while n % i == 0:
            n /= i
            counter.append(i)
        i += 1

    if n > 1:
        counter.append(n)
    return counter

n = input()
a = factorial(n)

res = [v for v in collections.Counter(prime_decomposition(a)).values()]

divisor = 1
for i in res:
    divisor *= (1 + i)

print divisor % (10 ** 9 + 7)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;

int main(){
    int N;
    LL L,T;
    cin >> N >> L >> T;
    vector<LL> X,W;
    vector<P> last;
    bool c=false;
    for(int i=0;i<N;i++){
        LL x,w;
        cin >> x >> w;
        X.pb(x);
        W.pb(w);
        if(w==1) last.pb(P((x+T)%L,i));
        else last.pb(P((L+x-(T%L))%L,i));
        if(last[i].fs==last[0].fs&&i!=0&&W[0]==1) c=true;
    }
    LL count=0;
    for(int i=1;i<N;i++){
        if(W[i]==W[0]) continue;
        else{
            if(W[0]==1){
                count+=(2*T)/L;
                if(((2*T%L))>=(X[i]-X[0])) count++;
            }
            else{
                count-=(2*T)/L;
                if(((2*T%L))>=(L-(X[i]-X[0]))) count--;
            }
        }
    }
    sort(ALL(last));
    int u=0;
    for(int i=0;i<N;i++){
        if(last[i].sc==0){
            u=i;
            break;
        }
    }
    int t=(N+u-((N+(count%N))%N))%N;
    if(c) t++;
    for(int i=0;i<N;i++){
        cout << last[(t+i)%N].fs << endl;
    }
    return 0;
}


Measured memory_bytes: 4572
import math
k=int(input())
sums=0
for i in range(k):
    a=i+1
    for i in range(k):
        b=i+1
        d=math.gcd(a,b)
        for i in range(k):
            c=i+1
            
            sums=sums+math.gcd(c,d)
print(sums)

Measured memory_bytes: 9188
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner (System.in);
    int B[][]=new int[3][3];
    for(int i=0;i<3;i++){
      for(int j=0;j<3;j++){
        B[i][j]=sc.nextInt();}}
    int N =sc.nextInt();
    int M[]=new int[N];
    Integer[] P=new Integer[10];
    for(int k=0;k<N;k++){
      M[k]=sc.nextInt();
      loop:for(int l=0;l<3;l++){
        for(int m=0;m<3;m++){
          if(M[k]==B[l][m]){P[k]=3*l+m+1;break loop;}}}
      if(k>2){
    if(Arrays.asList(P).contains(1)){
        if(Arrays.asList(P).contains(2)&&Arrays.asList(P).contains(3)){System.out.println("Yes");System.exit(0);}
        else if(Arrays.asList(P).contains(4)&&Arrays.asList(P).contains(7)){System.out.println("Yes");System.exit(0);}
        else if(Arrays.asList(P).contains(5)&&Arrays.asList(P).contains(9)){System.out.println("Yes");System.exit(0);}}
      if(Arrays.asList(P).contains(5)){
        if(Arrays.asList(P).contains(2)&&Arrays.asList(P).contains(8)){System.out.println("Yes");System.exit(0);}
        if(Arrays.asList(P).contains(3)&&Arrays.asList(P).contains(7)){System.out.println("Yes");System.exit(0);}
        if(Arrays.asList(P).contains(4)&&Arrays.asList(P).contains(6)){System.out.println("Yes");System.exit(0);}}
      if(Arrays.asList(P).contains(9)){
        if(Arrays.asList(P).contains(3)&&Arrays.asList(P).contains(6)){System.out.println("Yes");System.exit(0);}
        if(Arrays.asList(P).contains(7)&&Arrays.asList(P).contains(8)){System.out.println("Yes");System.exit(0);}}}}
    System.out.println("No");}
}

Measured memory_bytes: 22740
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  ll a,b,k;
  cin >> a >> b >> k;
  ll cnt=0,i=min(a,b);
  while(cnt!=k&&i>=1){
    if(a%i==0&&b%i==0){
      cnt++;
    }
    i--;
  }
  cout << i+1 << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    String first = s.substring(0,1);
    String last = s.substring(1,2);

    if (first.equals("9") || last.equals("9")) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }

  }

}


Measured memory_bytes: 23124
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int main()
{
	string s[3];cin >> s[0] >> s[1] >> s[2];
	int n[3] = {};
	int now = 0;
	
	while(1)
	{
		if(n[now] == s[now].size())
		{
			char ret = 'A'+now;
			cout << ret << endl;
			return 0;
		}
//		cout << "!!" << now << ' ' << n[now] << endl;
		n[now]++;
		now = s[now][n[now]-1] - 'a';
	}
	
	
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+7;
typedef long long ll;
ll a,b,k;
int main()
{
  cin>>a>>b>>k;
  if(a>=k)
    a-=k;
  else if(a+b>=k)
  {

      b-=(k-a); a=0;
  }
  else
  {
      a=0;
      b=0;
  }
  cout<<a<<" "<<b<<endl;
}


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

typedef long long ll;
#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)
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 dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    int a, b, m; cin >> a >> b >> m;
    vector<int> aa(a), bb(b);
    int mina = 1e5, minb = 1e5;
    rep(i,a) cin >> aa[i], chmin(mina, aa[i]);
    rep(i,b) cin >> bb[i], chmin(minb, bb[i]);
    int ans = mina+minb;
    rep(i,m) {
        int x,y,c; cin >> x >> y >> c;
        x--, y--;
        chmin(ans, aa[x]+bb[y]-c);
    }
    cout << ans << endl;
    return 0;
}

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

int solve(string s) {
  sort(s.begin(), s.end());
  int mn = stoi(s);
  sort(s.begin(), s.end(), greater<char>());
  int mx = stoi(s);
  return mx - mn;
}

int main() {
  int n;
  cin >> n;
  for (auto i = 0; i < n; ++i) {
    string s;
    cin >> s;
    cout << solve(s) << endl;
  }
}


Measured memory_bytes: 3016
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

# 同じ数字2つをマージした時の行き先と増える操作回数
# (nxt, cnt)
D = {
    0: (0, 1),
    1: (2, 1),
    2: (4, 1),
    3: (6, 1),
    4: (8, 1),
    5: (1, 2),
    6: (3, 2),
    7: (5, 2),
    8: (7, 2),
    9: (9, 2),
}

M = INT()
C = Counter()
for i in range(M):
    d, c = MAP()
    # 同じ数字の桁は全て一纏めにする
    C[d] += c

# 数字aがcnt個あった時に、全てマージした後の数字と費やした操作回数を返す
def calc(a, cnt):
    sm = 0
    odd = []
    # 1つになるまでやる
    while cnt > 1:
        # 奇数だと半分にした時1つ余るので後で別処理するように分けておく
        if cnt % 2 == 1:
            odd.append(a)
            cnt -= 1
        cnt //= 2
        sm += cnt * D[a][1]
        a = D[a][0]
    # 奇数の時に分けておいた分を愚直シミュレーション
    for b in odd:
        a += b
        sm += 1
        if a >= 10:
            a = int(str(a)[0]) + int(str(a)[1])
            sm += 1
    return (a, sm)

ans = 0
A = []
for k, v in C.items():
    # 数字毎にマージ、これで残り最大10桁まで減るはず
    a, sm = calc(k, v)
    ans += sm
    A.append(a)

# 残りを愚直シミュレーション
for i in range(1, len(A)):
    A[i] += A[i-1]
    ans += 1
    if A[i] >= 10:
        A[i] = int(str(A[i])[0]) + int(str(A[i])[1])
        ans += 1
print(ans)


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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

void solve() {
    int h, w, m;
    cin >> h >> w >> m;

    vector<pair<int, int>> v(m);
    set<pair<int, int>> st;
    int mx = 0, id = -1;
    int mx1 = 0, id1 = -1;
    map<int, int> row, col;
    for (int i = 0; i < m; i++) {
        cin >> v[i].first >> v[i].second;
        row[v[i].first]++;
        col[v[i].second]++;
        if (mx < col[v[i].second]) {
            mx = max(mx, col[v[i].second]);
            id = v[i].second;
        }
        if (mx1 < row[v[i].first]) {
            mx1 = row[v[i].first];
            id1 = v[i].first;
        }
        st.insert(v[i]);
    }
    int ans = 0;
    for (int i = 1; i <= 300000; i++) {
        if (st.find({i, id}) != st.end())ans = max(ans, row[i] + mx - 1);
        else ans = max(ans, row[i] + mx);
    }
    for (int i = 1; i <= 300000; i++) {
        if (st.find({id1, i}) != st.end())ans = max(ans, col[i] + mx1 - 1);
        else ans = max(ans, col[i] + mx1);
    }
    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 64160
#include <iostream>
//#include <fstream>
#include <vector>
#include <unordered_set>
#include <math.h>

using namespace std;

int bitCount(int bits) {
    int cnt = 0;
    for(uint mask = 1; mask != 0; mask<<=1) {
        if( (bits & mask) != 0 )
            ++cnt;
    }
    return cnt;
}

int setBit(int num, int i){
    return num | (1 << (i-1));
}

unordered_set<int> getHashSet(vector<int> s, int p, int num_switchs){
    unordered_set<int> hash_set;
    int mask = 0;
    for(int x : s) {
        mask = setBit(mask, x);
    }
    for (int i=0; i< pow(2.0, num_switchs); i++){
        if (bitCount(i & mask) % 2 == p){
            hash_set.insert(i);
        }
    }
    return hash_set;
}

unordered_set<int> intersection(const unordered_set<int>& a, const unordered_set<int>& b){
    std::unordered_set<int> c;
    for (auto i = a.begin(); i != a.end(); i++) {
        if (b.find(*i) != b.end()) c.insert(*i);
    }
    return c;
}

int main(int argc, const char * argv[]) {
    
//    ifstream in("input.txt");
//    cin.rdbuf(in.rdbuf());
    
    int N, M, k;
    cin >> N >> M;
    vector<vector<int>> s;
    for (int i=0; i<M; i++){
        cin >> k;
        vector<int> si;
        int si_tmp;
        for (int j=0; j<k; j++){
            cin >> si_tmp;
            si.push_back(si_tmp);
        }
        s.push_back(si);
    }
    
    vector<int> p;
    for (int i=0; i<M; i++){
        int p_tmp;
        cin >> p_tmp;
        p.push_back(p_tmp);
    }
    
    unordered_set<int> patterns = getHashSet(s[0], p[0], N);
    
//    for (int x : patterns){
//        cout << std::bitset<5>(x) << endl;
//    }
    
    for (int i = 1; i<M; i++){
        unordered_set<int> tmp_patterns = getHashSet(s[i], p[i], N);
        patterns = intersection(patterns, tmp_patterns);
    }
    
    cout << patterns.size() << endl;
    
    return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);

		String S = sc.nextLine();

		int min = 999;
		for (int i = 0; i <= S.length() - 3; i++) {
			int tmp = Integer.parseInt(S.substring(i, i + 3));

			int sub = Math.abs(tmp - 753);
			if (sub < min) {
				min = sub;
			}
		}
		System.out.println(min);
	}
}

Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()


int main()
{
	int n; cin >> n;
	
    int o[100010] = {0};
    int e[100010] = {0};
    // vector<int> o(100010, 0), e(100010, 0);
    // vector<int> o(1e5 + 1, 0), e(1e5 + 1, 0);

	// when changing input process -> result doesn't change
    int a, b;
    for(int i=0;i<n/2;i++){
        cin>>a>>b;o[a]++;e[b]++;
    }
    /*
    rep(i, 1, n)
	{
		int x; cin >> x;
		if (i % 2 == 1) ++o[x];
		else ++e[x];
	}
    */
	int mxO, mxOId, secO, mxE, mxEId, secE;
	mxO = secO = mxE = secE = 0;
    // mxO = secO = mxE = secE = mxOId = mxEId = 0;

    // this code is ok
    // rep(i, 0, 100000){
    //     if(o[i]>mxO){
    //         secO=mxO;mxO=o[i];mxOId=i;
    //     }
    //     else if(o[i]>secO)
    //     secO=o[i];
    //     if(e[i]>mxE){
    //         secE=mxE;mxE=e[i];mxEId=i;
    //     }
    //     else if(e[i]>secE)
    //     secE=e[i];
    // }

    // bags included
    rep(i, 0, 100000){
        // if(o[i]>mxO){
        //     secO=mxO;mxO=o[i];mxOId=i;
        // }
        // else if(o[i]>secO)
        // secO=o[i];        
		if (mxO < o[i])
		{
			secO = mxO;
			mxO = o[i];
			mxOId = i;
		}
        else if(o[i]>secO)
        secO=o[i];       
		// else if (secO < o[i]);
		// {
		// 	secO = o[i];
		// }
        if (mxE < e[i])
		{
			secE = mxE;
			mxE = e[i];
			mxEId = i;
		}
		else if (secE < e[i])
		{
			secE = e[i];
		}
	}

    // output process changed -> result doesn't change
    int ans;
    if(mxEId==mxOId)
    ans=max(secE,secO)+mxE;
    else
    ans=mxE+mxO;
    cout<<n-ans<<endl;
    return 0;
    /*
    if (mxOId != mxEId) cout << n - mxO - mxE << endl;
	else
	{
		int res = max(mxO + secE, secO + mxE);
		cout << n - res << endl;
	}
    */
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
int kkkt(int a){
    int sum=0;
    while(a>0){
        sum += a%10;
        a/=10;
    }
    return sum;
}
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
using namespace std;
int main(){
    //Seiranchan!
    int N ,A,B,cnt=0;
    cin >>N>>A>>B;

    for(int i=0;i<=N;i++){
        int kk = kkkt(i);
      
        if(A<=kk&&kk<=B){
            cnt += i;
        }
    }
    cout << cnt <<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <map>
using namespace std;
int main() {
  int X,N,a,aa;
  cin>>X>>N;
map<int,int> p;
  for(int i=0;i<N;i++){
int pp;
    cin>>pp;
    p[pp]=1;
  }
int i,j;
  i=0;
  while(true){

  if(p[X-i]!=1){cout<<X-i;
  return 0;}  
 if(p[X+i]!=1){cout<<X+i;
  return 0;}  
  i++;
  }
 
}

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

int main(){
	int n, m;
	cin >> n >> m;
    vector<vector<int>> vvi(m+1);
    int a, b;
    for(int i=0; i<n; i++){
        cin >> a >> b;
        if(a>m) continue;
        vvi[a].push_back(b);
    }

    int w=0;
    priority_queue<int> pq;
    for(int i=1; i<=m; i++){
        for(int x : vvi[i]){
            pq.push(x);
        }
        if(pq.empty()) continue;
        w += pq.top();
        pq.pop();
    }
    
    cout << w << endl;
}

Measured memory_bytes: 5504
import java.util.*;

class Main{

	public static void main(String[] args){
	
		Scanner sc = new Scanner(System.in);
		
		String S = sc.next();
		String T = sc.next();

		int A = sc.nextInt();
		int B = sc.nextInt();

		String U = sc.next();

		if(S.equals(U)){
			System.out.println(--A + " ");
			System.out.println(B);
		}else{
		    System.out.print(A + " ");
			System.out.println(--B);

		}
	
	}


}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> a(n),b(n);
	for(int &x:a) cin >> x;
	for(int &y:b) cin >> y;
	if(a > b)
		swap(a,b);
	int cnt = 0;
	while(a < b && ++cnt ) next_permutation(a.begin(),a.end());
	cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline
    from collections import Counter

    import random

    n = int(input())
    s = input()[:-1]
    c = Counter(s)
    minus = 0
    for i in range(1,(n+1)//2):
        for j in range(n-2*i):
            if (s[j] != s[j+i]) and (s[j] != s[j+2*i]) and (s[j+i] != s[j+2*i]):
                # print(j, i)
                minus += 1

    cnt = 1
    if not 'R' in c:
        print(0)
        exit()
    if not 'G' in c:
        print(0)
        exit()
    if not 'B' in c:
        print(0)
        exit()
    for value in c.values():
        cnt *= value
    print(int(cnt-minus))
"""
    true = 0
    true_cnt = 0
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                if (s[i] != s[j]) and (s[i] != s[k]) and (s[j] != s[k]):
                    true_cnt += 1
                if (j-i != k-j) and (s[i] != s[j]) and (s[i] != s[k]) and (s[j] != s[k]):
                    true += 1

    print(true)
    print(true_cnt)
    print(s)
"""

Measured memory_bytes: 77632
#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;
    string st;
    cin >> n;
    cin >> st;
    int f = 0;
    if(n%2 == 1){
        cout << "No" << endl;
    }else{
        rep(i, n/2){
            if(st.at(i) != st.at(i+n/2)) f = 1;
        }
        if(f == 0){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    return 0;
}


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

int main() {
	int N;
	int sum = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		sum += b - a + 1;
	}
	cout << sum;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
    string a,b;
    int i;
    cin >> a >> b;
      if(a.size()>b.size()){
        cout <<"GREATER";
      }
      if(a.size()==b.size()){
        for(i=0;i<a.size();i++){
          if(a[i]>b[i]){
            cout <<"GREATER";
              return 0;
          }
          if(a[i]<b[i]){
            cout <<"LESS";
            return 0;
          }
        }
        cout << "EQUAL";
      }
      if(a.size()<b.size()){
        cout <<"LESS";
      }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin>>a.at(i);
  }
  int y=0;
  for(int i=0;i<n;i++){
    y=y+a.at(i);
  }
  int z=0;
  for(int i=0;i<n;i++){
    if(a.at(i)*4*m>=y){
      z++;
    }
  }
  if(z>=m){
    cout<<"Yes"<<endl;
  }
  if(z<m){
    cout<<"No"<<endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define eb emplace_back
#define precision(n) cout << fixed << setprecision(n);
#define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
int main()
{
    int d,t,s;
    cin>>d>>t>>s;
    if(d%s==0)
    {
        if(d/s<=t)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }

    }
    else
    {
    if(d/s+1<=t)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    }
    return 0;

}


Measured memory_bytes: 3640
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <math.h>
#include <string>
#include <numeric>
#include <queue>
#include <cstdio>
#include <cstring>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep1(i,n) for(ll i=1;i<n;++i)
#define mrep(i,n) for(ll i=n;i>=0;--i)
#define all(a) (a).begin(),(a).end()
#define vl vector<ll>
#define vvl vector<vector<ll> >
#define vb vector<bool>
#define vvb vector<vector<bool> >
#define pl pair<ll,ll>
#define inf 1001001001001001000
//#define mod 1000000007
#define mod 998244353
#define pi 3.1415926535
using namespace std;
struct __INIT {
	__INIT() {
		cin.tie(0);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(15);
	}
}__init;



int main(void) {
    string s;
    cin>>s;
    ll k;
    cin>>k;
    ll ind = -1;
    rep(i,s.size()){
        if(s[i] != '1'){
            ind = i;
            break;
        }
    }
    if(ind == -1){
        cout<<1<<endl;
        return 0;
    }
    if(k-1 < ind) cout<<1<<endl;
    else{
        cout<<s[ind]<<endl;
    }
	return 0;
}


Measured memory_bytes: 3624
d=input().split()
for _ in range(int(input())):
 t,f=[d.index(s)for s in input().split()]
 n=[(1,2,4,3,1),(0,3,5,2,0),(0,1,5,4,0),(1,0,4,5,1),(0,2,5,3,0),(1,3,4,2,1)][t]
 print(d[n[n.index(f)+1]])



Measured memory_bytes: 5608
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let 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: usize,
        m: usize,
        x: i32,
        y: i32,
        xx: [i32;n],
        yy: [i32;m]
    }
    let l = xx.iter().max().unwrap();
    let r = yy.iter().min().unwrap();
    if l < r && x < *l && *r <= y {
        println!("No War");
    } else {
        println!("War");
    }
}


Measured memory_bytes: 4352
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<string>

#define ls (t<<1)
#define rs ((t<<1)+1)
#define mid ((l+r)>>1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back

#define N 1000005
#define M 200005
#define seed 23333
#define Mo 998244353

using namespace std;
int i,j,m,n,p,k,ID[N],tot,Str[N],End[N],f[N],g[N],T[N];
int kong[N],vis[N],sum,full[N];
char c[N],title[N],s[N];
vector<pair<int,int> >ques[N];
void bl()
{
	int i,ans=0,j,k,last;
	for (;;)
	{
		++ans;
		last=n+1;
		for (i=n;i;--i)
			if (s[i]!=c[i])
			{
					for (j=i;j;--j) if (c[j]==s[i]) break;
					if (!j)
					{
							puts("-1");
							return;
					}
					for (k=j;k<=min(last,i);++k) c[k]=c[j];
					last=j-1;
			}
		for (i=1;i<=n;++i) if (c[i]!=s[i]) break;
		if (i>n) break;
	}
	printf("%d\n",ans); 
}
int main()
{
		scanf("%d",&n); 
		scanf("%s",c+1);
		scanf("%s",s+1);
		for (i=1;i<=n;++i) if (c[i]!=s[i]) break;
		if (i>n)
		{
				puts("0");
				return 0;
		}
		for (i=1;i<=n;i=j)
		{
			++tot;
			for (j=i;s[j]==s[i]&&j<=n;++j);
			title[tot]=s[i];
			Str[tot]=i;
			End[tot]=j-1;
		}
		int now=n,ans=0;
		for (i=tot;i;--i)
		{
				while (now&&(now>Str[i]||c[now]!=title[i])) --now;	
				if (!now) 
				{
						puts("-1");
						return 0;
				}
				ID[i]=now; 
				vis[now]=1;
		}
		f[tot]=(ID[tot]!=Str[tot]);
		g[tot]=1;
		now=tot;
		for (i=n;i;--i)
			if (!vis[i]) full[i]=full[i+1];
			else 
			{
					full[i]=full[i+1]+1;
					if (now!=tot)
					{
						int needgo=full[i+1]-full[Str[now]+1];
						if (needgo==0) f[now]=(ID[now]!=Str[now]);
						else ques[Str[now]+1].pb(mk(needgo,now));
					}
					--now;
			}
		for (i=n;i;--i)
		{
			if (!vis[i])
			{
					++sum;
					kong[1-sum+n]=i;
			}
			for (j=0;j<(int)ques[i].size();++j)
					T[ques[i][j].se]=kong[ques[i][j].fi-sum+n];
		}
		now=tot;
		for (i=n;i;--i)
			if (vis[i])
			{
					if (now!=tot)
					{
						int needgo=full[i+1]-full[Str[now]+1];
						if (needgo==0) f[now]=(ID[now]!=Str[now]);
						else 
						{
							int pos=T[now];
							f[now]=full[i+1]-full[pos]+1;
						}
						if (f[now]==1&&f[now+1]==0) g[now]=1;
						else
						g[now]=max(f[now]+(Str[now]!=End[now]),f[now+1]+1);
					}
					--now;
			}
		for (i=1;i<=tot;++i) ans=max(ans,g[i]);
		printf("%d\n",ans);
}


Measured memory_bytes: 89088
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
typedef long long ll;
typedef pair<int,int> p;
const ll mod=998244353;
const ll linf=1ll<<60;
const int inf=1<<30;




int main(){
    int n;cin >> n;
    cout <<setprecision(10) <<  1.0-n/2/(double)n << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include <cassert>
#include<algorithm>
#include <tuple>
#include <utility>
#include<string>
#include <cmath>
#include <functional>
using namespace std;

int main(){
    string a;
    int b=0;
    cin >> a;
    for(int i=0; i<a.size(); i++){
        if(a[i]=='R')b++;
    }
    if(b==3){
        cout << 3 << endl;
    }else if(b==2){
        if(a[1]=='S')cout << 1 << endl;
        else cout << 2 << endl;
    }else if(b==1){
        cout << 1 << endl;
    }else{
        cout << 0 << endl;
    }
}

Measured memory_bytes: 3620
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    int n,k,ans=inf; cin>>n>>k;
    vector<int> x(n,0);
    rep(i,n) cin>>x[i];
    rep(i,n-k+1){
        int dis1=abs(x[i])+abs(x[i]-x[i+k-1]);
        int dis2=abs(x[i+k-1])+(x[i+k-1]-x[i]);
        ans=min(min(dis1,dis2),ans);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 640
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)
#define repd(i,a) repdi(i,a,0)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define endl '\n'
#define debug(x) std::cerr << #x << " = " << (x) << endl;

using ll = long long;
using P = std::pair<ll, ll>;

constexpr ll INF = 1ll<<60;

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 S, class T>
std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a )
{ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }

template<class T>
std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a )
{ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }

ll N, M;
ll S, T;
std::vector<std::vector<P>> G;
std::vector<ll> dist;

ll id( ll v, ll m )
{ return v*3+m; } 

void dijkstra( ll s, std::vector<std::vector<P>> &G, std::vector<ll> &dist )
{
  std::priority_queue<P, std::vector<P>, std::greater<P>> pque;

  dist.assign( N*3+10, INF );
  dist[s] = 0;

  pque.emplace( dist[s], s );

  while( !pque.empty() )
  {
    P p = pque.top(); pque.pop();
    ll d = p.first, v = p.second;

    if( dist[v] < d )
      continue;

    for( auto u : G[v] )
    {
      if( chmin( dist[u.first], dist[v]+u.second ) )
        pque.emplace( dist[u.first], u.first );
    }
  }

  return;
}

void add_edge( ll u, ll v ) {
  rep( j, 3 ) {
    G[id(u,j)].emplace_back(id(v,(j+1)%3), 1);
  }

  return;
}

int main() {
  std::cin >> N >> M;

  G.resize( N*3+10 );

  rep( i, M ) {
    ll u, v;
    std::cin >> u >> v;
    --u; --v;

    add_edge( u, v );
  }

  std::cin >> S >> T;
  --S; --T;

  dijkstra( id(S,0), G, dist );

  std::cout << (dist[id(T,0)]==INF ? -1 : dist[id(T,0)]/3) << endl;

  return 0;
}

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

pair<vector<int>, vector<int>> solve(int n, const string& T) {
    if (n == 0) {
        vector<int> P = {0};
        vector<int> W(T.size(), 0);
        return {P, W}; 
    }
    //if(n==2) { return solve(1,T); }
    pair<vector<int>, vector<int>> Ans = solve(n-1,T);
    vector<int> P = Ans.first , L = Ans.second;
    int S = (int)P.size();
    vector<int> new_p(3*S),new_l((int)L.size()),dig(3*S);
    for(int i=0;i<3;++i) for(int j=0;j<S;++j) dig[j+S*i] = i;
    vector<int> last_change(3*S);
    int cnt = 0;  
    for(int i=0;i<(int)T.size();++i){
     	int wk = L[i];
        for(int j = wk ; j < 3*S ; j+=S){
			if(dig[j]!=0 && last_change[j]%2 != cnt%2) dig[j] = 3-dig[j];
            last_change[j] = cnt;
            if(dig[j] == 2) new_l[i] = j;
        }
        if(T[i] == 'R'){
            for(int j = wk ; j < 3*S ; j+=S) dig[j] = (dig[j]+1)%3;
        } 
        else{
          cnt++;
        }
    }  
    
    for(int i=0;i<3*S;++i){
      if(last_change[i]%2!=cnt%2 && dig[i]!=0) dig[i] = 3-dig[i];
      new_p[i] = P[i%S] + dig[i]*S;
    }
    return {new_p,new_l};
}

int main() {
    int N;
    cin >> N;
    string T;
    cin >> T;
    vector<int> P = solve(N, T).first;
    for (int x: P) cout << x << " ";
    cout << "\n";
    return 0;
}


Measured memory_bytes: 16524
{-# LANGUAGE BangPatterns #-}
import Data.Char (isSpace)
import Data.Int (Int64)
import Data.List (unfoldr)
import qualified Data.Vector.Unboxed as U
import qualified Data.ByteString.Char8 as BS
-- import Control.Monad (replicateM)

main = do
  [n,maxW] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  items <- U.replicateM n $ do
    [w,v] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    return (w, fromIntegral v :: Int64)
  print $ solve maxW items U.! maxW

{-
solve :: Int -> [(Int, Int64)] -> U.Vector Int64
solve maxW [] = U.replicate (maxW + 1) 0
solve maxW ((w,v):xs)
  = let a = solve maxW xs
    in U.generate (maxW + 1)
       $ \i -> if w <= i
               then max (a U.! i) (a U.! (i - w) + v)
               else a U.! i
-}
solve :: Int -> U.Vector (Int, Int64) -> U.Vector Int64
solve !maxW xs
  | U.null xs = U.replicate (maxW + 1) 0
  | otherwise = let (!w,!v) = U.head xs
                    !a = solve maxW (U.tail xs)
                in U.generate (maxW + 1)
                   $ \i -> if w <= i
                           then max (a U.! i) (a U.! (i - w) + v)
                           else a U.! i


Measured memory_bytes: 2940