akhauriyash/Code-Regression huggingface dataset:
import bisect
s=input()
n=len(s)
if n!=26:
  alp=[1]*26
  for i in s:
    alp[ord(i)-ord('a')]=0
  for i in range(26):
    if alp[i]:break
  ans=s+chr(ord('a')+i)
else:
  alp=[]
  for i in range(n-1,-1,-1):
    if bisect.bisect_left(alp,ord(s[i]))==len(alp):
      bisect.insort_left(alp,ord(s[i]))
    else:
      ans=s[:i]+chr(alp[bisect.bisect_left(alp,ord(s[i]))])
      break
  else:ans=-1
print(ans)

Measured memory_bytes: 9116
a,b = map(int,input().split())
answer = 0
for i in range(a,b+1) :
    j = str(i)
    p1 = j[4]
    p2 = j[3]
    p3 = j[2]
    p4 = j[1]
    p5 = j[0]
    k = int(p1+p2+p3+p4+p5)
    if i == k :
        answer += 1
print(answer)



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

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

	double debt = 100000;
	while (weeks--) {
		debt = debt + debt * 0.05;
		debt = ceil(debt / 1000) * 1000;
	}
	
	cout << int(debt) << endl;;
	return 0;
}

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

int main() {
  int A,B,K;
  cin >> K;
  cin >> A >> B;
  int a=0;
  
  for(int i=A;i<=B;++i){
    if(i%K==0) a = 1;
  }
  if(a==1) cout<<"OK"<<endl;
  else cout<<"NG"<<endl;
      
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int n,p[800],d,a,b,c,maxc;
bool used[800];
vector<P> e[800];
 
void dfs(int x,int sum){
  used[x]=true;
  for(int i=0;i<e[x].size();i++){
    int nx=e[x][i].first;
    if(used[nx])continue;
    if(e[nx].size()==1){
      maxc=max(maxc,sum);
      continue;
    }
    dfs(nx,sum+e[x][i].second);
  }
  return;
}
 
int main(){
  while(cin>>n&&n){
    a=b=c=0;
    for(int i=1;i<n;i++)cin>>p[i];
    for(int i=1;i<n;i++){
      cin>>d;
      a+=d;
      e[i].push_back(P(p[i]-1,d));
      e[p[i]-1].push_back(P(i,d));
    }
    for(int i=0;i<n;i++)
      if(e[i].size()==1)b+=e[i][0].second;
    for(int i=0;i<n;i++)
      if(e[i].size()!=1){
	memset(used,0,sizeof(used));
	maxc=0;
	dfs(i,0);
	c=max(c,maxc);
      }
    cout<<3*a-2*b-c<<endl;
    for(int i=0;i<n;i++)e[i].clear();
  }
  return 0;
}

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

using namespace std;

const int N = 5103;

int n, m;
int maxl, tot;
char s[N], minc;
char res[N][N];

int main() {
  scanf("%d%d", &n, &m);
  scanf("%s", s + 1);
  minc = 'z';
  for (int i = 1; i <= n; ++i) minc = min(minc, s[i]);
  if (m >= 14) {
    for (int i = 1; i <= n; ++i) putchar(minc);
    return !puts("");
  }
  for (int i = 1, len = 0; i <= n; ++i) {
    if (s[i] != minc) len = 0;
    else len++;
    if (len > maxl) maxl = len;
  }
  for (int i = 1, len = 0; i <= n; ++i) {
    if (s[i] != minc) len = 0;
    else len++;
    if (len == maxl) {
      ++tot;
      int have = min(n, len * (1 << (m - 1)));
      for (int j = 1; j <= have; ++j) res[tot][j] = minc;
      for (int j = have + 1, k = i + 1; j <= n; ++j, ++k) {
        if (k <= n) res[tot][j] = s[k];
        else res[tot][j] = s[2 * n - k + 1];
      }
    }
    if (i == n) {
      ++tot;
      int have = min(n, len * (1 << m));
      for (int j = 1; j <= have; ++j) res[tot][j] = minc;
      for (int j = have + 1, k = n - len; j <= n; ++j, --k)
        res[tot][j] = s[k];
    }
  }
  int best = 1;
  for (int i = 2; i <= tot; ++i) {
    if (strcmp(res[i] + 1, res[best] + 1) < 0)
      best = i;
  }
  puts(res[best] + 1);
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    string s;
    cin >> s;
    ll ans = 0;
    if (s == "MON") ans = 6;
    if (s == "TUE") ans = 5;
    if (s == "WED") ans = 4;
    if (s == "THU") ans = 3;
    if (s == "FRI") ans = 2;
    if (s == "SAT") ans = 1;
    if (s == "SUN") ans = 7;
    cout << ans << endl;
    //printf("%.12f", ans);
}

Measured memory_bytes: 3596
#include<iostream>
#include<algorithm>

typedef unsigned long long ULL;
typedef long long LL;

using namespace std;

int main(){
    int a,b;
    
    cin >> a >> b;
    
    if( a % 2 != 0 && b % 2 != 0){
        cout << "Odd" << endl;
    }else{
        cout << "Even" << endl;
    }
}


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

int main() {
  for (int i = 0; i < 10; i++) {
    string S;
    cin >> S;
    if (S == "-") break;
    int m, n = 0, l = S.size();
    cin >> m;
    for (int j = 0; j < m; j++) {
      int k;
      cin >> k;
      n += k;
    }
    n %= S.size();
    S += S;
    for (int k = n; k < n + l; k++) cout << S.at(k);
    cout << endl;
  }
}


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

int main() {
    long long a,b,k;

    cin >> a >> b >> k;

    if (a >= k){
        a -= k;
    } else {
        k -= a;
        a = 0;

        if (b >= k) b -= k;
        else b = 0;
    } 

    cout << a << " " << b << endl;

    return 0;
}

Measured memory_bytes: 256
N,M,X=map(int,input().split())
ls=[list(map(int,input().split())) for i in range(N)]
ls_c=[]
for i in range(1,2**N):
  ls_al=[0]*M
  c=0
  for j in range(N):
    if (i>>j)&1==1:
      c+=ls[j][0]
      for k in range(M):
        ls_al[k]+=ls[j][k+1]
  if min(ls_al)>=X:
    ls_c.append(c)
    
if ls_c!=[]:
  print(min(ls_c))
else:
  print(-1)

Measured memory_bytes: 68596
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=5005;
long long two=(mod+1)/2;
long long dp[maxn][maxn];
char shit[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s",shit);
    int l=strlen(shit);
    dp[0][0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            if(dp[i][j]==0) continue;
            dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j]*2)%mod;
            dp[i+1][max(j-1,0)]=(dp[i+1][max(j-1,0)]+dp[i][j])%mod;
        }
    }
    long long ans=dp[n][l];
    for(int i=1;i<=l;i++)
        ans=ans*two%mod;
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 193920
//も
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

void reverse(string &s) {
	int l = 0, r = s.length() - 1;
	while (l < r) {
		swap(s[l], s[r]);
		l++; r--;
	}
}

int n;
string s[200000];
vector<bool> isAppear[200000][26];
int l[200000], r[200000];
int cnts[1000001][26];

bool check(string &key, string &s, int comp) {
	if (s.length() < key.length()) return false;
	int i;
	for (i = 0; i < key.length(); i++) {
		if (s[i] != key[i]) {
			if (comp == 0) {
				if (s[i] < key[i]) return false;
				return true;
			}
			
			if (s[i] > key[i]) return false;
			return true;
		}
	}
	return true;
}

int findL(int index) {
	string key;
	int i;
	rep(i, (int)s[index].length() - 1) key += s[index][i];
	
	int ng = -1, ok = index;
	while (ok - ng >= 2) {
		int mid = (ng + ok) / 2;
		if (check(key, s[mid], 0)) ok = mid;
		else ng = mid;
	}
	return ok;
}

int findR(int index) {
	string key;
	int i;
	rep(i, (int)s[index].length() - 1) key += s[index][i];
	
	int ok = index, ng = n;
	while (ng - ok >= 2) {
		int mid = (ng + ok) / 2;
		if (check(key, s[mid], 1)) ok = mid;
		else ng = mid;
	}
	return ok;
}

void add(int index) {
	int len = s[index].length();
	
	for (int i = 0; i < 26; i++) {
		for (int j = 0; j < len; j++) {
			if (isAppear[index][i][j]) {
				cnts[j][i]++;
			}
		}
	}
}

void del(int index) {
	int len = s[index].length();
	
	for (int i = 0; i < 26; i++) {
		for (int j = 0; j < len; j++) {
			if (isAppear[index][i][j]) {
				cnts[j][i]--;
			}
		}
	}
}

signed main() {
	int i;
	
	cin >> n;
	rep(i, n) {
		cin >> s[i];
		reverse(s[i]);
	}
	sort(s, s + n);
	
	rep(i, n) {
		int j, k;
		rep(j, 26) {
			isAppear[i][j] = vector<bool>(s[i].length(), false);
		}
		
		bool flag[26] = {false};
		for (k = s[i].length() - 1; k >= 0; k--) {
			int c = s[i][k] - 'a';
			flag[c] = true;
			rep(j, 26) isAppear[i][j][k] = flag[j];
		}
	}
	
	rep(i, n) {
		l[i] = findL(i);
		r[i] = findR(i) + 1;
	}
	
	vector<int> qi(n);
	rep(i, n) qi[i] = i;
	int sq = sqrt((double)n);
	sort(qi.begin(), qi.end(), [&](int i, int j) {
		if (l[i] / sq != l[j] / sq) return l[i] < l[j];
		return r[i] < r[j];
	});
	
	//クエリの処理
	int ans = 0;
	int nl = 0, nr = 0;	//[nl, nr)
	for (int i : qi) {
		while (nl > l[i]) { --nl; add(nl); }
		while (nr < r[i]) { add(nr); nr++; }
		while (nl < l[i]) { del(nl); nl++; }
		while (nr > r[i]) { --nr; del(nr); }
		
		/*クエリの計算結果*/
		int len = s[i].length() - 1;
		ans += cnts[len][s[i][len] - 'a'];
	}
	
	cout << ans - n << endl;
	return 0;
}

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

using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using f64 = double;
using f80 = long double;

#define FOR(v, a, b) for(i64 v = (a); v < (b); ++v)
#define FORE(v, a, b) for(i64 v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(i64 v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

using namespace std;

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}

template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}
template <typename T> auto make_vector(int n, int m, const T &value){return vector<vector<T>>(n, vector<T>(m, value));}

template <typename T> void print(const T &value){std::cout << value << "\n";}
template <typename T, typename ...Args> void print(const T &value, const Args&... args){std::cout << value << " ";print(args...);}


struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);
  }
}init;

const i64 MAX = 1000000000000000000;


int main(){
  int N;

  while(cin >> N){
    vector<i64> A(N); cin >> A;
    bool ok = true;

    i64 ans = 1;
    
    REP(i,N){
      i64 k;
      if(__builtin_smulll_overflow(ans, A[i], (long long int*)&k)){
        ok = false;
        break;
      }
      
      if(ans * A[i] > MAX){
        ok = false;
        break;
      }

      ans = k;
    }

    REP(i,N) if(A[i] == 0) ok = true, ans = 0;

    
    if(!ok){
      print(-1);
    }else{
      print(ans);
    }
  }

  return 0;
}



Measured memory_bytes: 3980
// #pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")

// #include <bits/extc++.h>
// using namespace __gnu_pbds;

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
// template <typename T>
// using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RANDOM() random_device __rd; \
                 mt19937 __gen = mt19937(__rd()); \
                 uniform_int_distribution<int> __dis(1, 1E8); \
                 auto rnd = bind(__dis, __gen)

const int INF = 1E18;
const int mod = 1E9 + 7;

int32_t main() {
    fastIO();
    
    int n, ma, mb, lhf, rhf;
    cin >> n >> ma >> mb, lhf = n / 2, rhf = n - lhf;
    
    vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i] >> c[i];
    
    vector<int> la(1 << lhf, 0), lb(1 << lhf, 0), lc(1 << lhf, 0);
    for (int i = 1; i < (1<<lhf); ++i) {
        for (int j = 0; j < lhf; ++j) {
            if (i >> j & 1) la[i] += a[j], lb[i] += b[j], lc[i] += c[j];
        }
    }
    
    vector<int> ra(1 << rhf, 0), rb(1 << rhf, 0), rc(1 << rhf, 0);
    for (int i = 1; i < (1<<rhf); ++i) {
        for (int j = 0; j < rhf; ++j) {
            if (i >> j & 1) ra[i] += a[lhf+j], rb[i] += b[lhf+j], rc[i] += c[lhf+j];
        }
    }
    
    map<pii, int> lminC, rminC;
    for (int i = 1; i < (1<<lhf); ++i) {
        if (!lminC[{la[i], lb[i]}]) lminC[{la[i], lb[i]}] = lc[i];
        else lminC[{la[i], lb[i]}] = min(lminC[{la[i], lb[i]}], lc[i]);
    }
    for (int i = 1; i < (1<<rhf); ++i) {
        if (!rminC[{ra[i], rb[i]}]) rminC[{ra[i], rb[i]}] = rc[i];
        else rminC[{ra[i], rb[i]}] = min(rminC[{ra[i], rb[i]}], rc[i]);
    }
    
    int ans = INF;
    for (auto ab : lminC) {
        if (ab.X.X * mb == ab.X.Y * ma) ans = min(ans, ab.Y);
        else {
            for (int amount = 1; amount <= 400; ++amount) {
                if (ab.X.X > amount * ma or ab.X.Y > amount * mb) continue;
                if (rminC[{amount*ma - ab.X.X, amount*mb - ab.X.Y}]) {
                    ans = min(ans, ab.Y + rminC[{amount*ma - ab.X.X, amount*mb - ab.X.Y}]);
                }
            }
        }
    }
    for (auto ab : rminC) {
        if (ab.X.X * mb == ab.X.Y * ma) ans = min(ans, ab.Y);
    }
    
    cout << (ans == INF ? -1 : ans) << "\n";
    
    return 0;
}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a;
  cin >> a;
  int t[4][13] = {0};
  for (int i = 0; i < a; i++) {
    char b;
    int c;
    cin >> b >> c;
    if (b == 'S') {
      t[0][c-1] = 1;
    }
    if (b == 'H') {
      t[1][c-1] = 1;
    }
    if (b == 'C') {
      t[2][c-1] = 1;
    }
    if (b == 'D') {
      t[3][c-1] = 1;
    }
  }
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 13; j++) {
      if (t[i][j] == 0) {
        if (i == 0) {
          cout << "S " << j+1 << endl;
        }
        if (i == 1) {
          cout << "H " << j+1 << endl;
        }
        if (i == 2) {
          cout << "C " << j+1 << endl;
        }
        if (i == 3) {
          cout << "D " << j+1 << endl;
        }
      }
    }
  }
}


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

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

int main() {
  int m,k;
  cin >> m >> k;
  if (k >= (1<<m)) {
    cout << -1 << endl;
    exit(EXIT_SUCCESS);
  }
  if (m == 1 && k == 1) {
    cout << -1 << endl;
    exit(EXIT_SUCCESS);
  }
  if (k == 0) {
    rep(i,(1<<(m+1))) {
      printf("%d ", i/2);
    }
    printf("\n");
    exit(EXIT_SUCCESS);
  }
  int n = 1<<m;
  printf("%d ", k);
  rep(i,n) {
    if (i != k) printf("%d ", i);
  }
  printf("%d ", k);
  rep(i,n) {
    if (n-i-1 != k) printf("%d ", n-i-1);
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 3644
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
double a[15][15],d;
int js(int x,int y)
{
	int s=0;
	for(int i=1;i<=d;i++)
		s+=(a[x][i]-a[y][i])*(a[x][i]-a[y][i]);
	return s;
}
int main()
{
	int n,i,j;
	cin>>n>>d;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=d;j++)
		{
			cin>>a[i][j];
		}		
	}
	int ans=0;
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			int dist=js(i,j);
			int x=sqrt(dist);
			if(x*x==dist)
				ans++;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 1e9+7;
ll const INF = 1e18;
using namespace std;

int main(){
    int H, W, h, w;
    cin >> H >> W >> h >> w;
    cout << H * W - h * W - H * w + h * w << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;

ll mod_pow(ll x, ll n, ll mod){
    ll res = 1;
    while(n > 0){
        if (n & 1) (res *= x) % mod;
        (x *= x) %= mod;
        n >>= 1;
    }
    return res;
}


int main(){
    int n, m;
    cin >> n >> m;
    cout << mod_pow(2, m, MOD) * (1900 * m + 100 * (n - m)) << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <stdint.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-12;
static const double PI = acos(-1.0);
static const ll MOD = 1000000007;

#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(a) (a).begin(), (a).end()
#define DEBUG(x) cout << #x << ": " << x << endl

int main() {
  char ch;
  cin >> ch;
  if ('a' <= ch && ch <= 'z') {
    cout << 'a' << endl;
  } else {
    cout << 'A' << endl;
  }
  // Failed to predict input format
  return 0;
}


Measured memory_bytes: 3628
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) int((a).size())
#define out(a) cout<<(a)<<endl;
const int INF=INT_MAX;
const int MAX = 510000;
const ll MOD = 1000000007;
ll fac[MAX], finv[MAX], inv[MAX];

int main(){
  ll n,ave=0;cin>>n;
  vll a(n);
  rep(i,0,n){
    cin>>a[i];
    ave+=a[i];
  }
  ave/=n;
  ll ans1=0,ans2=0;
  rep(i,0,n){
    ans1+=(a[i]-ave)*(a[i]-ave);
    ans2+=(a[i]-ave-1)*(a[i]-ave-1);
  }
  cout<<min(ans1,ans2)<<endl;
}


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

int main(){
    ll a,b,c;
    cin>>a>>b>>c;
    if(a%2==1 && b%2==1 && c%2==1) {
        cout<<min(a*b,min(b*c,c*a));
    }
    else cout<<0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    string T; cin >> T;
    sort(T.begin(), T.end(), greater<char>());
    sort(S.begin(), S.end());
    if(S < T) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }


    return 0;
}


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

typedef long long  ll;

ll MOD = 1000000007;
ll INF = 100000000000000000;
int PI = 3.1415926535;

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<tuple<ll,ll,ll>>>;

void Primefactor(ll n,vector<ll>& A){
  ll a = n;
  for(ll i = 2;i * i <= n;i++){
    while(a % i == 0){
      A.push_back(i);
      a /= i;
    }
    if(a == 1){
      break;
    }
  }
  if(a != 1){
    A.push_back(a);
  }
  return;
}

int main(){
 ll A,B;cin >> A >> B;
 vector<ll> C,D;
 Primefactor(A,C);
 Primefactor(B,D);
 C.erase(unique(C.begin(),C.end()),C.end());
 D.erase(unique(D.begin(),D.end()),D.end());
 int c = C.size(),d = D.size();
 int ans = 1;
 /*for(int i = 0;i < c;i++)cout << C[i] << ' ';
 cout << endl;
 for(int i = 0;i < d;i++)cout << D[i] << ' ';
 cout << endl; */
 for(int i = 0;i < c;i++){
   bool frag = 0;
   for(int j = 0;j < d;j++){
     if(C[i] == D[j]){
       frag = 1;
     }
   }
   if(frag)ans++;
 }
 cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,i,c[1000005],x;
    cin>>t;
   for(i=1;i<=t-1;i++)
    {
      cin>>x;
      c[x]++;
        }
        for(int i=1;i<=t;i++)
        cout<<c[i]<<endl;

}





Measured memory_bytes: 4340
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
 
#define INF (1<<29)
#define D(x) cout << #x " is " << (x) << endl
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
 
using namespace std;
 
int dp[16][(1<<16)];
 
int main(void){
 
  int n;
  string s,t;
 
  while(cin >> n,n){
    cin >> s >> t;
 
    fill(dp[0],dp[n],INF);
    int tmp=0;
    for(int i=0;i<n;i++){
      if(s[i]==t[i])tmp|=(1<<i);
    }
    for(int i=0;i<n;i++)dp[i][tmp]=0;
     
    int ans=INF;
    for(int r=0;r<4;r++){
      for(int i=0;i<n;i++){
    if(!(tmp>>i&1)){
      for(int k=0;k<n;k++){
        for(int j=0;j<n;j++){
          if(s[j]!=s[k]){
        for(int S=0;S<(1<<n);S++){
          if(!(S>>j&1) && !(S>>k&1)){
            int next=S;
            next|=(1<<j)|(1<<k);
            if(dp[k][next]>dp[i][S]+abs(j-i)+abs(k-j))
              dp[k][next]=dp[i][S]+abs(j-i)+abs(k-j);
          }
        }
          }
        }
      }
    }
    ans=min(ans,dp[i][(1<<n)-1]);
      }
    }
    cout << ans << endl;
  }
  return 0;
}

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

int main()
{
    vector<long> a;
    int i,n;
    long long tmp,sum = 0;
    cin >> n;
    for(i = 0; i < n; i++){
        cin >> tmp;
        a.push_back(tmp);
        sum += tmp;
    }
    sort(a.begin(),a.end());

    cout << a[0] << ' ' << a[i -1] << ' ' << sum << endl;
}

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

/*
void print(vector<vector<int>> b){
   rep(p,3){
      rep(q,3){
         cout<<b[p][q]<<" ";
      }
      cout<<endl;
   }
}
*/

int main(){
   vector<vector<int>> board;
   int n;

   int hoge;
   rep(j,3){
      vector<int> piyo;
      rep(i,3){
         cin>>hoge;
         piyo.push_back(hoge);
      }
      board.push_back(piyo);
   }

   bool flg=false;
   cin>>n;
   vector<int> num;
   rep(i,n){
      cin>>hoge;
      num.push_back(hoge);
   }

   rep(i,n){
      rep(p,3){
         rep(q,3){
            if(board[p][q]==num[i]){
               board[p][q]=0;
            }
         }
      }
   }

   if(board[0][0]==0 && board[1][0]==0 && board[2][0]==0){
      cout<<"Yes"<<endl;
   }else if(board[0][1]==0 && board[1][1]==0 && board[2][1]==0){
      cout<<"Yes"<<endl;
   }else if(board[0][2]==0 && board[1][2]==0 && board[2][2]==0){
      cout<<"Yes"<<endl;
   }else if(board[0][0]==0 && board[0][1]==0 && board[0][2]==0){
      cout<<"Yes"<<endl;
   }else if(board[1][0]==0 && board[1][1]==0 && board[1][2]==0){
      cout<<"Yes"<<endl;
   }else if(board[2][0]==0 && board[2][1]==0 && board[2][2]==0){
      cout<<"Yes"<<endl;
   }else if(board[0][0]==0 && board[1][1]==0 && board[2][2]==0){
      cout<<"Yes"<<endl;
   }else if(board[0][2]==0 && board[1][1]==0 && board[2][0]==0){
      cout<<"Yes"<<endl;
   }else{
      cout<<"No"<<endl;
   }

   // print(board);
}


Measured memory_bytes: 256
//
// Created by 13783 on 2020/3/28.
//
#include<iostream>
using namespace std;
const int K=1E6;
const int N=2e5+2;
int a[N+1];
int d[N+1];
int k;
int n;
int ans;
void solve(){
    for(int i=1;i<=n;i++){
        d[i]=a[i]-a[i-1];
        ans+=d[i];
    }
    d[1]+=d[n];
    n--;
    int mx=0;
    for(int i=1;i<=n;i++){
        mx=max(mx,d[i]);
    }
    cout<<ans-mx;
}
int main(){
    cin>>k>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    n++;
    a[n]=k;
    solve();
    return 0;
}


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

using namespace std;

#define fast_io ios::sync_with_stdio(false); cin.tie(NULL);

int main()
{
	fast_io;
	
	int n,m;
	cin >> n >> m;

	long long array[n][3];
	long long maxi = 0;
	for (int i = 0; i < n; ++i)
	{
		cin >> array[i][0] >> array[i][1] >> array[i][2];
	}	


	for (int i = 0; i < 8; ++i)
	{
		string binaryRep = "";
		int copy = i;
		for (int j = 0; j < 3; j++)
		{
			binaryRep += to_string(copy%2);
			copy /= 2;
		}

		// cout << "binaryRep: " << binaryRep << endl;

		vector<long long> summations;
		for (int j = 0; j < n; j++)
		{
			long long currSum = 0;
			for (int k = 0; k < 3; k++)
			{
				if (binaryRep[k] == '0') currSum += array[j][k];
				else currSum -= array[j][k];
			}
			summations.push_back(currSum);
		}
		long long currMax = 0;
		sort(summations.begin(), summations.end());
		int done = 0;
		for (int j = n-1; j >= 0 && done < m; j--, done++)
		{
			currMax += summations[j];
		}
		maxi = max(maxi, currMax);
	}

	cout << maxi << endl;
	
	return 0;
}


Measured memory_bytes: 256
import sys
from io import StringIO
import unittest


def resolve():
    s = list(input())
    ll = len(s)
    ans = 0

    if ll % 2 == 0:
        for i in range(0, ll, 2):
            if i == 0:
                if s[:ll//2+1] == s[ll//2 + 1:]:
                    ans = ll//2
                    break
            else:
                tmp = s[:(-1 * i)]
                if tmp[:len(tmp)//2] == tmp[len(tmp)//2:]:
                    ans = len(tmp)
                    break
    else:
        for i in range(1, ll, 2):
            tmp = s[:-i]
            if tmp[:len(tmp)//2] == tmp[len(tmp)//2:]:
                ans = len(tmp)//2
                break
    print(ans)

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """abaababaab"""
        output = """6"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """xxxx"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """abcabcabcabc"""
        output = """6"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """akasakaakasakasakaakas"""
        output = """14"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

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

"""考え方
[入力例１]
10000

N = A * B より

A=10000, B=1
A=5000, B=2
A=2500, B=4
A=1250, B=8
A=1000, B=10
A=500, B=20
A=250, B=40
A=125, B=80
A=100, B=100
A=50, B=200  <-- ここまで来ると、Bの桁数が大きくなるいっぽうなので、最小値が更新されることはもうない
...

つまり、i = 1 ~ √N までを全探索しても、N<=10**10なので、計算量は高々10**5 これは間に合う。

"""
import math

def F(A, B):
    """ 10進表記における、Aの桁数とBの桁数のうち大きい方を返す """
    def keta(n):
        """ 桁数を求める """
        ans = 1
        while True:
            n = n // 10
            if n == 0:
                break
            ans += 1
        return ans
    
    return max(keta(A), keta(B))
    

def solve():
    N = int(input())
    ans = float("inf")

    for i in range(1, math.ceil(math.sqrt(N))+1):
        A = i
        if N%A != 0: continue
        B = int(N/A)

        ans = min(ans, F(A, B))

    print(ans)

if __name__ == "__main__":
    solve()


Measured memory_bytes: 3188
#include <iostream>
#include <algorithm>
#include <climits>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <tuple>
 
using namespace std;
 
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define cina(s, n, a) for(int i = s; i < n; i++) cin >> a[i]
#define couta(n, a) for(int i = 0; i < n; i++) cout << a[i] << ' '
#define copy(s, n, a, b) for(int i = s; i < n; i++) b[i] = a[i]
#define yesno(ok) cout << (ok ? "YES" : "NO")
#define mod(a, b) (b + (a % b)) % b
#define MOD (int)1e9 + 7
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void add_self (int& a, int b){ a += b; if(a >= MOD) a -= MOD; }
//-------------------------------------------------------------------------------------------------------//

void solve(){
    int n;
    cin >> n;
    n -= 1;
    vi a(n), b(n + 1, INT_MAX);
    cina(0, n, a);
    for(int i = 0; i < n; i++){
        b[i] = min(a[i], b[i]);
        b[i + 1] = min(a[i], b[i + 1]);
    }
    int sum = 0;
    for(int i = 0; i <= n; i++) sum += b[i];
    cout << sum;
}
 
int main(){
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int q = 1;
    //cin >> q;
    for(int i = 1; i <= q; i++){
        solve();
    }
}


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

struct data{
  double d;
  P p;
  bool operator < (const data &a)const{
    return d < a.d;
  }
};

double eps=1e-8;
double PI=acos(-1);

bool eq(double a,double b){return (b-a<eps&&a-b<eps);}
bool eq(P a,P b){return (abs(a-b)<eps);}
bool onSegment(P a,P b,P p){
  return eq( abs(a-b) , abs(a-p) + abs(b-p) );
}

double dot(P a,P b){return real(b*conj(a));}
double cross(P a,P b){return imag(b*conj(a));}
P getPoint(P a,P b,P c,P d){
  a-=d;b-=d;c-=d;
  return d+a+(b-a)*imag(a/c)/imag(a/c-b/c);
}
bool isParallel(P a,P b,P c,P d){
  return eq(0,cross(a-b,c-d));
}
int n;
P t[16];
vector<P> A;

double Arg(P a,P b,P c){
  b-=a,c-=a;
  return arg(c*conj(b));
}
 
bool inPolygon(P p){
  double sum=0;  
  for(int i=0;i<n;i++){
    P a=t[i],b=t[(i+1==n?0:i+1)];
    if(onSegment(a,b,p))return true;
    sum+= Arg(p,a,b);
  }
  if( abs(sum) < eps )return false;
  else  return true;
}

bool inPolygon(P a,P b){
  vector< data > v;
  for(int i=0;i<n;i++){
    P c=t[i],d=t[(i+1)%n];
    if(isParallel(a,b,c,d))continue;
    P sp=getPoint(a,b,c,d);
    if(!onSegment(a,b,sp))continue;
    if(!onSegment(c,d,sp))continue;
    v.push_back((data){ abs(a-sp) , sp});
  }
  v.push_back( (data){0,a} );
  v.push_back( (data){abs(a-b),b} );
  sort(v.begin(),v.end());

  for(int i=0;i<(int)v.size();i++){
    if( !inPolygon(v[i].p) )return false;
    if(i&& !inPolygon( (v[i].p+v[i-1].p)*0.5 ) )return false;
  }
  return true;
}


int solve(){
  bool f[20][20]={};
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      f[i][j]=inPolygon(t[i],t[j]);
  
  A.clear();
  for(int i=0;i<n;i++){
    P a=t[i],b=t[(i+1)%n];
    vector< data > v;
    for(int j=0;j<n;j++){
      P c=t[j];
      for(int k=0;k<j;k++){
        P d=t[k];
        //        if(!f[j][k])continue;
        if( eq( 0, cross(a-b,c-d) ) )continue;
        P np = getPoint(a,b,c,d);
        if(!onSegment(a,b,np))continue;
        v.push_back((data){ abs(np-a) , np } );
      }
    }
    sort(v.begin(),v.end());
    A.push_back(a);
    for(int j=0;j<(int)v.size();j++){
      A.push_back(v[j].p);
    }
  }

  bool g[1000][16]={};
  for(int i=0;i<(int)A.size();i++){
    P a=A[i];
    for(int j=0;j<n;j++){
      g[i][j]=inPolygon(a,t[j]);
    }
  }
  
  vector<int> G[6];
  for(int i=0;i<(1<<n);i++){
    int cnt=__builtin_popcount(i);
    if(cnt<=5)G[cnt].push_back(i);
  }
  
  for(int i=1;i<=5;i++){
    for(int j=0;j<(int)G[i].size();j++){
      int bit=G[i][j];
      int cnt=0;
      for(int k=0;k<(int)A.size();k++){
        bool flg=false;
        for(int l=0;l<n;l++){
          if(bit>>l&1){
            flg|=g[k][l];
          }
        }
        if(flg)cnt++;
      }
      if(cnt==(int)A.size()){
         return i;
      }
    }
  }
  return 6;
}

int main(){
  while(1){
    cin>>n;
    if(n==0)break;
    for(int i=0;i<n;i++){
      double x,y;
      cin>>x>>y;
      t[i]=P(x,y);
    }
    cout<<solve()<<endl;
  }
  return 0;
}

Measured memory_bytes: 1472
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t[111];
int main() {
    int n;
    cin>>n;
    for(int i = 0; i < n; ++i) {
        cin>>t[i];
    }
    ll ans = 1e18;
    for(int i = -100; i <= 100; ++i) {
        ll q = 0;
        for(int j = 0; j < n; ++j) {
            q += (t[j]-i)*(t[j]-i);
        }
        ans = min(ans, q);
    }
    cout<<ans<<'\n';
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int INF = numeric_limits<int>::max() / 2;
ll LINF = numeric_limits<ll>::max() / 2;
int MOD = 1e9 + 7;

const int MAX = 500001;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
    ll n,m,k;
    cin >> n >> m >> k;
    ll ans = 0;
    COMinit();
    for(ll i = 1; i < n; i++) (ans += i * m * m * (n-i) * COM(n*m-2, k-2)) %= MOD;
    for(ll i = 1; i < m; i++) (ans += i * n * n * (m-i) * COM(n*m-2, k-2)) %= MOD;
    cout << (ans + MOD) % MOD << endl;
}

Measured memory_bytes: 11904
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

const ll mod = 1000000007;
const int N = 100010;

vector<int> G[N];

ll dp[N][2];
ll dfs(int r, int c, int p){
    if(dp[r][c]>=0) return dp[r][c];

    ll ret = 1;
    for(int e:G[r])if(e!=p){
        ll a = 0;
        rep(i,2){
            if(i==1 && c==1) continue;
            (a += dfs(e,i,r)) %= mod;
        }
        (ret *= a) %= mod;
    }
    return dp[r][c] = ret;
}

int main(){
    int n;
    scanf(" %d", &n);
    rep(i,n-1){
        int x,y;
        scanf(" %d %d", &x, &y);
        --x;
        --y;
        G[x].pb(y);
        G[y].pb(x);
    }

    memset(dp,-1,sizeof(dp));
    ll ans = 0;
    rep(i,2) (ans += dfs(0,i,-1)) %= mod;
    printf("%lld\n", ans);
    return 0;
}


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

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

#define fr first
#define sc second

int main(){
	static int n,k;
	static int a[100010];
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	cout<<(n-1+k-2)/(k-1)<<endl;
}



Measured memory_bytes: 640
N, M = [int(i) for i in input().split()]
AC = [0] * (N + 1)
WA = [0] * (N + 1)
for i in range(M):
    p, S = input().split()
    if S == "AC":
        AC[int(p)] = 1
    else:
        if AC[int(p)] == 0:
            WA[int(p)] += 1
ans0 = 0
ans1 = 0
for i in range(N):
    ans0 += AC[i+1]
    if AC[i + 1] == 1:
        ans1 += WA[i+1]
print(ans0, ans1)

Measured memory_bytes: 4596
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>
#include <queue>
#include <deque>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin>>N;
  vector<ll>A(N);
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  sort(ALL(A));
  ll ans=0;
  if(A[0]>=0){
    ans=accumulate(ALL(A),0ll)-A[0]*2;
    cout<<ans<<endl;
    ll now=A[0];
    for(int i=1;i<N-1;i++){
      cout<<now<<' '<<A[i]<<"\n";
      now-=A[i];
    }
    cout<<A[N-1]<<' '<<now<<"\n";
  }else if(A[N-1]<0){
    ans=abs(accumulate(ALL(A),0ll)-A[N-1]*2);
    cout<<ans<<endl;
    ll now=A[N-1];
    for(int i=0;i<N-2;i++){
      cout<<now<<' '<<A[i]<<"\n";
      now-=A[i];
    }
    cout<<now<<' '<<A[N-2]<<"\n";
  }else{
    int maxi=0;
    for(int i=0;i<N;i++){
      if(A[i]>=0){
        ans+=A[i];
      }else{
        ans-=A[i];
        maxi=i;
      }
    }
    cout<<ans<<endl;
    ll pcnt=N-maxi-1;
    ll ncnt=maxi+1;
    ll pnow=A[maxi+1];
    ll nnow=A[0];
    for(int i=1;i<=maxi;i++){
      cout<<pnow<<' '<<A[i]<<"\n";
      pnow-=A[i];
    }
    for(int i=maxi+2;i<N;i++){
      cout<<nnow<<' '<<A[i]<<"\n";
      nnow-=A[i];
    }
    cout<<pnow<<' '<<nnow<<"\n";
  }
}


Measured memory_bytes: 2688
def main():
  n = int(input())
  A = [int(_) for _ in input().split()]
  m, M, s = 10 ** 8, -10 ** 8, 0
  for a in A:
    m = min(m, a)
    M = max(M, a)
    s += a
  print(m, M, s)
  return

if __name__ == '__main__':
  main()


Measured memory_bytes: 6612
import sys
import collections
input = sys.stdin.readline

def main():
  N = int(input()[:-1])
  X = collections.defaultdict(list)  # X
  Y = collections.defaultdict(list)  # Y
  XYp = collections.defaultdict(list) # X + Y
  XYn = collections.defaultdict(list) # X + Y
  YXp = collections.defaultdict(list) # Y - X
  YXn = collections.defaultdict(list) # Y - X
  
  for _ in range(N):
    x, y, u = input().split()
    x = int(x)
    y = int(y)
    if u in ('U', 'D'):
      X[x].append((y, u == 'U'))
    if u in ('R', 'L'):
      Y[y].append((x, u == 'R'))
    
    if u in ('U', 'R'):
      XYp[x + y].append((x - y, u == 'R'))
    if u in ('D', 'L'):
      XYn[x + y].append((x - y, u == 'D'))
      
    
    if u in ('U', 'L'):
      YXp[y - x].append((x + y, u == 'U'))
    if u in ('D', 'R'):
      YXn[y - x].append((x + y, u == 'R'))
  
  ans = 200000 * 100
  for x in [X, Y, XYp, XYn, YXp, YXn]:
    for V in x.values():
      V = sorted(V)
      
      for i in range(len(V)-1):
        if V[i][1] and not V[i+1][1]:
          ans = min(ans, V[i+1][0] - V[i][0])
  if ans == 200000 * 100:
    print('SAFE')
  else:
    print(ans * 5)
   
if __name__ == '__main__':
    main()

Measured memory_bytes: 192684
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int n, m;
char s[N], t[N];

int h[N][26];

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> s >> t;
    n = strlen(s);
    m = strlen(t);
    for (int j = 0; j < 26; ++j)
        h[n][j] = -1;
    for (int i = n - 1; i >= 0; --i)
    {
        for (int j = 0; j < 26; ++j)
            h[i][j] = h[i + 1][j];
        h[i][s[i] - 'a'] = i;
    }
    long long ans = 0;
    int j = 0;
    for (int i = 0; i < m; ++i)
    {
        if (h[j][t[i] - 'a'] == -1 && j != 0)
        {
            ++ans;
            j = 0;
        }
        if (h[j][t[i] - 'a'] == -1)
        {
            cout << -1 << endl;
            return 0;
        }
        j = h[j][t[i] - 'a'] + 1;
    }
    cout << ans * 1LL * n + j << endl;
    return 0;
}


Measured memory_bytes: 10624
#include<bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[32;1m" << #x << "->" ; err(x);} while(0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T,typename t,typename... A>
void err(T<t> a,A... x){for (auto v:a) cout << v << ' '; err(x...);}
template<typename T,typename... A>
void err(T a,A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;
template<class T> void mkuni(vector<T>&v)
{
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
template<class T>
void print(T x,int suc=1)
{
    cout<<x;
    if(suc==1) cout<<'\n';
    else cout<<' ';
}
template<class T>
void print(const vector<T>&v,int suc=1)
{
    for(int i=0;i<v.size();i++)
        print(v[i],i==(int)(v.size())-1?suc:2);
}
const int INF=0x3f3f3f3f;
const int maxn=2e5+7;
const int mod=1e9+7;
ll quick(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ret;
}
ll inv(ll a)
{
	return quick(a,mod-2);
}
vi G[maxn];
int sz[maxn];
ll ans=0;
ll inv2=inv(2);
int n;
void dfs(int u,int fa=-1)
{
	sz[u]=1;
	vi ssz;
	for(auto v:G[u])if(v!=fa)
	{
		dfs(v,u);
		sz[u]+=sz[v];
		ssz.push_back(sz[v]);
	}
	ssz.push_back(n-sz[u]);
	ll ap=1;
	for(auto v:ssz)
		ap=ap*(quick(inv2,v))%mod;
	ll sum=ap;
	for(auto v:ssz)
	{
		ll cc=ap*inv(quick(inv2,v))%mod;
		cc=cc*(1-quick(inv2,v)+mod)%mod;
		sum=(sum+cc)%mod;
	}
	ans=(ans+inv2*(1-sum+mod)%mod)%mod;
}
int main()
{
	cin>>n;
	for(int i=1,u,v;i<n;i++)
	{
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1);
	cout<<ans<<'\n';
}


Measured memory_bytes: 29952
//?????????????????¢?´¢
//??????????????????????????????????????¢?´¢
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
static const int N = 100;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[N][N];
int color[N], d[N], f[N], tt;
int nt[N];

//u?????£??\??????v?????????????????¨???
int next(int u){
    for(int v = nt[u]; v < n; v++){
        nt[u] = v + 1;
        if(M[u][v]) return v;
    }
    return -1;
}

void dfs_visit(int r){
    for(int i = 0; i < n; i++) nt[i] = 0;
    stack<int> S;
    
    S.push(r);
    color[r] = GRAY;
    d[r] = ++tt;
    
    while(!S.empty()){
        int u = S.top();
        int v = next(u);
        
        if(v != -1){
            if(color[v] == WHITE){
                color[v] = GRAY;
                d[v] = ++tt;
                S.push(v);
            }
        }
        else{
            S.pop();
            color[u] = BLACK;
            f[u] = ++tt;
        }
    }
}

void dfs(){
    int u;
    for(int i = 0; i < n; i++) nt[i] = 0;
    
    for( u = 0; u < n; u++){
        //????¨????u?????¢??????????????????dfs
        if(d[u] == WHITE) dfs_visit(u);
    }
    
    for( int i = 0; i < n; i++){
        cout << i + 1 << " " << d[i] << " " << f[i] << endl;
    }
}

int main(void){
    int u, v, k, j,i;
    
    cin >> n;
    
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++) M[i][j] = 0;
   
    for(i = 0; i < n; i++) {
        cin >> u >> k;
        u--;
        for(j = 0; j < k; j++){
            cin >> v;
            v--;
            M[u][v] = 1;
        }
    }
    
    dfs();
    
    return 0;
}

Measured memory_bytes: 1244
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define yes(n) cout << ((n) ? "yes" : "no"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define VSUM(V) accumulate(ALL(V), 0)
#define MID(a,b,c) (a) < (b) && (b) < (c)
#define MIDe(a,b,c) (a) <= (b) && (b) <= (c)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;
#define FIX cout << fixed << setprecision(15)

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define VVi vector<vector<ll>>
#define Vd vector<double>
#define Vb vector<bool>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

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

using ll = long long;
using Graph = vector<vector<int>>;

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int gcd(int a,int b){return b != 0 ? gcd(b, a % b) : a;} //最大公約数
int lcm(int a, int b){return a * b / gcd(a, b);}
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n=0,m=0,a=0,b=0,c=0,d=0,x=0,y=0,z=LONG_LONG_MAX;
  string s="",t="";
  //

  // ここから
  IN(n);
  Vi A(n);
  VIN(A)
  REP(i,n){
    x += A[i];
  }
  REP(i,n-1){
    y += A[i];
    m = x - y;
    z = min(z, abs(y-m));
  }
  OUT(z);
}

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

int main(){
    vector<int> vec;
    int n;cin >>n;
    for (int i=0;i<n;i++){
        int temp;
        cin >> temp;
        switch(temp){
            case 0:
                cin >> temp;
                vec.push_back(temp);
                break;
            case 1:
                cin >> temp;
                cout << vec.at(temp) << endl;
                break;
            case 2:
                vec.pop_back();
        }
    }
    return 0;
}



Measured memory_bytes: 3900
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def get_prime(N):
    prime = dict()
    prime[1] = 1
    i = 2
    while i * i <= N:
        while N % i == 0:
            if i in prime.keys():
                prime[i] += 1
            else:
                prime[i] = 1
            N = N // i
        i += 1
    if N != 1:
        prime[N] = 1
    return prime


def main():
    N = int(input().strip())
    div_table = [0] * (N + 1)
    MOD = 10**9 + 7
    ans = 1
    for i in range(2, N + 1):
        for j in range(i, N + 1, i):
            div_table[j] += 1

    prime = dict()
    for i in range(2, N + 1):
        if div_table[i] == 1:
            prime[i] = 0

    for i in range(2, N + 1):
        _prime = get_prime(i)
        for k, v in _prime.items():
            if k == 1:
                continue
            prime[k] += v

    for k, v in prime.items():
        ans *= v + 1
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9160
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: str):
    a = 0
    for n in N:
        a+=int(n)
        a%=9
    if a==0:print(YES)
    else:print(NO)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = next(tokens)  # type: str
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9400