akhauriyash/Code-Regression huggingface dataset:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return (i for i in range(self.n) if self.find(i) == root)

    def roots(self):
        return (i for i, x in enumerate(self.parents) if x < 0)

    def group_count(self):
        return len(self.roots())

    def sizes(self):
        return {x: self.size(x) for x in self.roots()}

    def all_group_members(self):
        d = {}
        for i in range(self.n):
            p = self.find(i)
            d[p] = d.get(p, []) + [i]
        return d

    def __str__(self):
        return '\n'.join('{}: {}'.format(k, v) for k, v in self.all_group_members().items())


def resolve():
    n, q = map(int, input().split())
    u = UnionFind(n)
    for _ in range(q):
        t, a, b = map(int, input().split())
        if t == 0:
            u.union(a, b)
        else:
            if u.same(a, b):
                print(1)
            else:
                print(0)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 11480
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <queue>
#include <deque>
#include <stack>

using namespace std;

const int maxn = 1e5 + 5;

vector<int> G[maxn];
deque<int> q;
bool vis[maxn];
int N, M;

int main(int argc, char const *argv[]) {
    cin>>N>>M;
    for (int i = 0; i < M; i ++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    bool flag1 = false, flag2 = false;
    
    q.push_front(1);
//    q.push_back(G[1][0]);
    vis[1] = true;
    while (!flag1 || !flag2) {
        bool change1 = false, change2 = false;
        if (!flag1) {
            for (int v : G[q.front()]) {
                if (!vis[v]) {
                    vis[v] = true;
                    q.push_front(v);
                    change1 = true;
                    break;
                }
            }
            if (!change1) flag1 = true;
        }
        if (!flag2) {
            for (int v : G[q.back()]) {
                if (!vis[v]) {
                    vis[v] = true;
                    q.push_back(v);
                    change2 = true;
                    break;
                }
            }
            if (!change2) flag2 = true;
        }
    }
    
    cout<<q.size()<<endl;
    for (auto x : q) cout<<x<<" ";
    return 0;
}

Measured memory_bytes: 6784
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
       return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}



int main()
{

   fastread();

   ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r;

      bool flag=false;

      string str;

      cin>>n;

      ll ara[n+2];

      input(ara,n);

      map<ll,ll>mp;

         for(i=0; i<n; i++)
         {
             for(j=i+1; j<n; j++)
             {
                 for(k=j+1; k<n; k++)
                 {
                   set<ll>s;
                   s.insert(ara[i]);
                   s.insert(ara[j]);
                   s.insert(ara[k]);


    if(s.size()==3 &&  (ara[i]+ara[j]>ara[k] && ara[i]+ara[k]>ara[j] && ara[k]+ara[j]>ara[i]))
                    {

                        cnt++;
                       // break;

                        //cout<<i+1<<" "<<j+1<<" "<<k+1<<endl;
                    }

             }
         }}

         cout<<cnt<<endl;







}



Measured memory_bytes: 3652
using System.Text;
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var m = int.Parse(line[1]);
        var a = new int[m];
        var b = new int[m];
        for (int i = 0; i < m; i++)
        {
            line = Console.ReadLine().Trim().Split(' ');
            a[i] = int.Parse(line[0]);
            b[i] = int.Parse(line[1]);
        }
        var c = getAns(a, b, n, m);
        var p1 = 0L;
        for (int i = 0; i < m; i++) p1 += (a[i] + 1) % b[i];
        print(c, p1, n, m);

    }
    static void print(long[] c, long p1, int n, int m)
    {
        var sb = new StringBuilder();
        for (int i = 1; i <= n; i++)
        {
            var w = p1 + c[i] + m * (long)(i - 1);
            sb.Append(w.ToString() + "\n");
        }
        Console.Write(sb);
    }
    static long[] getAns(int[] a, int[] b, int n, int m)
    {
        var c = new long[n + 1];
        for (int i = 0; i < m; i++)
        {
            var bi = b[i];
            var p = bi - a[i];
            while (p <= n)
            {
                if (p != 1) c[p] -= bi;
                p += bi;
            }
        }
        for (int i = 2; i <= n; i++)
            c[i] = c[i - 1] + c[i];
        return c;
    }
}



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

#define ll long long
class Item{
    public:
    int weight;
    ll int value;
};
bool compare(Item i1,Item i2){
    return i1.weight < i2.weight;
}

ll int solve(vector<Item> items, int capacity){
    sort(items.begin(),items.end(),compare);
    int len = items.size();
    vector<vector<ll int>> dp(len,vector<ll int>(capacity+1,0));
    for(int i = 0; i <= capacity; i++){
        if(items[0].weight <= i){
            dp[0][i] = items[0].value;
        }
    }    
    for(int i = 1; i < len; i++){
        for(int j = 1; j <= capacity; j++){
            if(items[i].weight <= j){
                dp[i][j] = max(items[i].value + dp[i-1][j - items[i].weight],dp[i-1][j]);
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
            // cout<<dp[i][j]<<" ";

        }
        // cout<<endl;
    }

    return dp[len - 1][capacity];
}
int main(){
    int N,capacity;
    cin>>N>>capacity;
    vector<Item> val;
    for(int i = 0; i < N; i++){
        Item item;
        cin>>item.weight>>item.value;
        val.push_back(item);
    }
    cout<<solve(val,capacity);
}

Measured memory_bytes: 82340
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int x[210];

int main(void){
	          int i;

	      	  cin.tie(0);  ios_base::sync_with_stdio(false);
	      	  
	      	  int a,b,c;
	      	  cin >> a >> b >> c;
	      	  x[a+100]++;
	      	  x[b+100]++;
	      	  x[c+100]++;
	      	  
	      	  for(i=0;i<=200;i++){
	      		  if(x[i]==1){
	      			  cout << i-100 << endl;
	      			  return 0;
	      		  }
	      	  }
	      	  
	          return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main(void) {
  int N, T;
  std::cin >> N >> T;
  int t;
  int total = 0;
  int end = 0;
  for(int i = 0; i < N; i++) {
    std::cin >> t;
    if(t <= end) {
      int new_end = t + T;
      total += new_end - end;
      end = new_end;
    } else {
      end = t + T;
      total += T;
    }
  }
  std::cout << total;
  return 0; 
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a, b, c;
	cin >> a >> b >> c;
	cout << a * b / 2 << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String n = sc.next();
		for (int i = 0; i < n.length(); ++i) {
			if (n.charAt(i) == '7') {
				System.out.println("Yes");
				return;
			}
		}

		System.out.println("No");
	}

}


Measured memory_bytes: 35452
#include <bits/stdc++.h>
#include <tr1/unordered_map>
#define ll long long
#define il inline
const ll inf = 1e9;

namespace io {

#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a), putchar('\n')

#define I_int ll
inline I_int read() {
    I_int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
char F[200];
inline void write(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
}
#undef I_int

}
using namespace io;

using namespace std;

#define N 100010
const ll mod = 1e9 + 7;

int n, x, a[N];
ll ans = 0, inv[N], f[210][N];

ll power(ll a, ll b) {
	ll ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod; b >>= 1;
	} return ans;
}

/*
f[i][j]位置i，黑板上的值为j 
*/

int main() {
	in(n), in(x);
	f[0][x] = 1; inv[0] = 1;
	for(int i = 1; i <= n; ++i) inv[i]=power(i, mod - 2), in(a[i]);
	sort(a+1,a+n+1); reverse(a+1,a+n+1);
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j <= x; ++j) 
			f[i][j] = f[i - 1][j] * inv[n-i+1] % mod * (n - i) % mod;
		for(int j = 0; j <= x; ++j) {
			int t = j % a[i];
			f[i][t] = (f[i][t] + f[i - 1][j] * inv[n-i+1] % mod) % mod;
		}
	}
	ll ans = 0;
	for(int i = 0; i <= x; ++i) ans = (ans + i * f[n][i]) % mod;
	for(int i = 1; i <= n; ++i) ans = ans * i % mod;
	outn(ans);
}

Measured memory_bytes: 157184
S = input()
l_even = len(S[0::2])
l_odd = len(S[1::2])

white_even = S[0::2].count('0')
black_even = l_even - white_even
white_odd = S[1::2].count('0')
black_odd = l_odd - white_odd

print(min(white_even + black_odd, white_odd + black_even))


Measured memory_bytes: 3188
#include <stdio.h>

int main(void)
{
	int n,i,a[100];
	scanf("%d",&n);
	for (i=0; i<n; i++) {
		scanf("%d",&a[i]);
	}
	for (i=1; i<n; i++) {
		printf("%d ",a[n-i]);
	}
	printf("%d\n",a[0]);
	return 0;
}

Measured memory_bytes: 596
# D - 井井井 / ###
# 問題URL:http://abc058.contest.atcoder.jp/tasks/arc071_b

n , m = map(int, input().split())
X = [int(i) for i in input().split()]
Y = [int(i) for i in input().split()]

x_sum = 0
y_sum =0

for i in range(1,n+1):
    x_sum += (X[i-1] * (i - 1)) - (X[i-1] * (n - i))
    
for i in range(1,m+1):
    y_sum += (Y[i-1] * (i - 1)) - (Y[i-1] * (m - i))

print((x_sum * y_sum)%1000000007)

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

using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
int mod = 998244353;

long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}

/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  

double eps = .000000001;
vector<int> graph[201];
bool vis[201];

int vals[201];
bool good = true;
void bip(int node, int val){
    if (vis[node] || !good){
        return;
    }
    vis[node] = true;
    vals[node] = val;
    for (int i=0; i<graph[node].size(); i++){
        int cur = graph[node][i];
        if (vals[cur] == val){
            good = false;
            break;
        }
        int newval = 1;
        if (val == 1){
            newval = 2;
        }
        bip(cur, newval);
    }
}
int main ()
{
  prep();
  int n;
  cin >> n;
  bool conn[n][n];
  memset(conn, false, sizeof(bool)*n*n);
  for (int i=0; i<n; i++){
      string s;
      cin >> s;
      for (int j=0; j<n; j++){
          if (s[j] == '1'){
              graph[i].push_back(j);
              conn[i][j] = true;
          }
      }
  }
  // start from 0
  int first = 0;
  // start from something connected to 0
  int second = graph[0][0];
  bip(first, 1);
  if (!good){
      memset(vals, 0, sizeof(int)*n);
      memset(vis, false, sizeof(bool)*n);
      good = true;
      bip(second, 1);
      if (!good){
          cout << -1;
          return 0;
      }
  }
  int dists[n+1][n+1];
  for (int i=0; i<n; i++){
      for (int j=0; j<n; j++){
          if (conn[i][j]){
              dists[i][j] = 1;
          }else if (i == j){
              dists[i][j] = 0;
          }else{
              dists[i][j] = 1000000000;
          }
      }
  }
  for (int i=0; i<n; i++){
      for (int j=0; j<n; j++){
          for (int k=0; k<n; k++){
              dists[j][k] = min(dists[j][k], dists[j][i]+dists[i][k]);
          }
      }
  }
  int maxest = 0;
  for (int i=0; i<n; i++){
      for (int j=0; j<n; j++){
          maxest = max(dists[i][j], maxest);
      }
  }
  cout << maxest+1;
  return 0; 
}


Measured memory_bytes: 512
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
int32_t main()
{
	#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
	freopen("out","w",stdout);
	#endif
	int n;
	cin>>n;
	vector<int> a(n+1);
	for(int i=1;i<=n;i++)cin>>a[i];
	int ans=0;
	int sum=0,xr=0,j=0;
	for(int i=1;i<=n;i++)
	{
		while(j+1<=n and (sum+a[j+1])==(xr^a[j+1]))
		{
			j++;
			sum+=a[j];
			xr^=a[j];
		}
		ans+=(j-i+1);
		sum-=a[i];xr^=a[i];
	}
	cout<<ans;
}

Measured memory_bytes: 4844
//                             In The Name Of Allah
#include <bits/stdc++.h>
#define ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define ll long long
#define int long long
#define pb push_back
using namespace std; 

const ll N = 1e6 + 100, OO = 1e10 + 10, M = 998244353, lg = 6151;
typedef pair <int, int> pii;
int a[N], pw[N], n;
map <int, int> m;

bool god(int x) {
	if(x == 0)
		return true;
	bool u = false;
	set <int> s;
	for(int i = x; i <= n; i++) {
		int j = i - x;
		int t = a[j] * pw[x];
		t %= M;
		t = a[i] - t;
		t += M;
		t %= M;
		if(s.find(t) == s.end()) {
			m[t] = i;
			s.insert(t);
		}
		else {
			if(m[t] <= j) {
				u = true;
				break;
			}
		}
	}
	for(auto u : s)
		m[u] = 0;
	return u;
}

int32_t main() {
	cin >> n;
	pw[0] = 1;
	string s;
	cin >> s;
	for(int i = 1; i <= n; i++) {
		pw[i] = pw[i - 1] * lg;
		pw[i] %= M;
	}
	for(int i = 1; i <= n; i++) { 
		a[i] = a[i - 1] * lg + (s[i - 1] - 'a');
		a[i] %= M;
	}
	int l = 1, r = n + 1;
	while(l < r) {
		int mid = (l + r) / 2;
		if(god(mid)) 	
			l = mid + 1;
		else
			r = mid;	
	}
	cout << l - 1 << endl;
	return 0;
}

Measured memory_bytes: 6144
using System;

namespace ConsoleApplication{
    public class Program{
        public static void Main(string[] args){
            string[] words = Console.ReadLine().Split(' ');
            double x1 = double.Parse(words[0]);
            double y1 = double.Parse(words[1]);
            double x2 = double.Parse(words[2]);
            double y2 = double.Parse(words[3]);

            double answer = Math.Sqrt(((x2-x1) * (x2 - x1)) + ((y2-y1) * (y2-y1)));

            Console.WriteLine(answer.ToString("F5"));
        }
    }
}

Measured memory_bytes: 9156
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
#define ii for(int i=1;i<=n;++i)
#define ji for(int j=1;j<=n;++j)
#define jj for(int j=1;j<=m;++j)
#define ij for(int i=1;i<=m;++i)
#define sz(x) ((ll)x.size())
#define all(x) x.begin(),x.end()
#define alll(x) x+1,x+1+n
#define asd cout<<"ok"<<endl;
#define endl '\n'

int main()
{
    string s;
    cin >> s;
    int k;
    cin >> k;
    vector<string> ans;
    for(int i=0;i<s.size();++i) {
        for(int j=1;j<=min(5,(int)s.size()-i);++j)
            ans.push_back(s.substr(i,j));
    }
    sort(all(ans));
    ans.erase(unique(all(ans)),ans.end());
    cout << ans[k-1] << endl;
}


Measured memory_bytes: 1660
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(System.out);

        char[] S = sc.next().toCharArray();
        char[] T = sc.next().toCharArray();

        int[][] dp = new int[S.length + 1][T.length + 1];

        for (int i = 1; i < S.length + 1; i++) {
            for (int j = 1; j < T.length + 1; j++) {
                if (S[i-1] == T[j-1]) {
                    dp[i][j] = Math.max(Math.max(dp[i - 1][j - 1] + 1, dp[i - 1][j]), dp[i][j - 1]);
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        int i = S.length;
        int j = T.length;

        StringBuffer res = new StringBuffer();
        while (0 < i && 0 < j) {
            if (dp[i][j] == dp[i-1][j]) {
                i--;
            } else if (dp[i][j] == dp[i][j-1]) {
                j--;
            } else {
                res.insert(0, S[i-1]);
                i--;
                j--;
            }
        }
        out.println(res.toString());
        out.flush();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Measured memory_bytes: 79316
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0)
#define so sizeof
#define pb push_back
#define cl clear() ;
#define vl vector<ll>
#define sz size()
#define len length()
#define emp empty()
#define eps 1e-10
#define gcd(a,b) __gcd(a,b)
#define el endl;cout.flush()
#define be begin()
#define fi first
#define se second
#define br break
#define en end()
#define ro return 0
#define eb emplace_back
#define con continue
#define ms(x) memset(x , 0ll, so x)
#define all(x) (x).be , (x).en
#define acc(x) accumulate((x).be , (x).en , 0ll)
#define forn(i,a,b) for(ll i=a;i<=b;++i)
#define rng_58 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define plll pair<ll,pair<ll,ll>>
#define plvl pair<pair<ll,ll> ,ll>
#define mp make_pair
#define trace3(a,b,c) cerr <<"a is " << a << " b is " << b << " c is " << c << el;
#define trace4(a,b,c,d) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << el ;
#define trace5(a,b,c,d,e) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << el;
#define trace6(a,b,c,d,e,f) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << " f is " << f << el ;

typedef long double ld;
vector<ld> v;
ll n ;
ld dp[3005][3005];
int main()
{
    ios;
    cin >> n ;
    cout << fixed;
    cout << setprecision(10);
    forn(i , 1 , n ) {
       ld x;
       cin >> x;
       v.pb(x) ;
    }
    dp[0][0] = 1;

    /// dp[i][j] denotes probability of getting j heads with i coins.
    dp[1][1] = v[0];
    dp[1][0] = 1 - v[0];
    forn(i , 2 , n ) {
      forn(j , 0 , i ){
         if(j == 0 ){
             ld foo = (1-v[i-1]) * dp[i-1][0] ;
             dp[i][j] = foo ;
         }
         else {
            /// if current is head ... then tail ..
            ld foo = v[i-1] * dp[i-1][j-1] + ( 1 - v[i-1]) * dp[i-1][j] ;
            dp[i][j] = foo ;
         }
      }
    }
    ld res = 0;
    forn(i , 0 , n){
       if(i > (n/2)){
         res = res + dp[n][i];
       }
    }
    cout << res << el ;
    ro ;
}




Measured memory_bytes: 139392
a,b,c,d = gets.split(" ").map(&:to_i)

if (a == 1 or a == 9 or a == 7 or a == 4) and (b == 1 or b == 9 or b == 7 or b == 4) and (a != b) and (b != d) and (b != c) and (c == 1 or c == 9 or c == 7 or c == 4) and (a != c) and (d == 1 or d == 9 or d == 7 or d == 4) and (a != d) and (c != d)
  puts "YES"
else
  puts "NO"
end

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

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

bool isprime(int v) {
  if (v == 1) return false;
  for (int i = 2; 1ll * i * i <= v; ++i)
    if (v % i == 0) return false;

  return true;
}

int main() {
  int n;
  cin >> n;
  vector<int> v[5];
  rep(i, 55556) if (isprime(i)) v[i % 5].push_back(i);

  rep(i, n) cout << v[1][i] << (i == n - 1 ? "\n" : " ");
  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i=s;i<n;i++)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define int long long
using namespace std;
using P=pair<int,int>;
using Graph=vector<vector<int>>;
using ll=long long;


ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}
bool root(string s){
    int n=s.length();
    if(n==2){
        if(s[0]==s[1]){
            return true;
        }
        else return false;
    }
    if(n==3){
        if(s[0]==s[2]){
            return true;
        }
        else return false;
    }
 
    return false;
}
 
 
//深さ優先
vector<int> seen;
vector<ll> h;
 
//普通の深さ優先探索seenを返す感じ
void dfs(const Graph &G,int v){

    seen[v] = 0; //v探索済み
 
    P good=make_pair(v,h[v]);
    for(auto next_v :G[v]){
        if(seen[next_v]!=-1) continue;//もう探索していた
        if(h[next_v]>good.second){
            good=make_pair(next_v,h[next_v]);
        }
        dfs(G,next_v);
    }
 
    if(!(h[v]==good.second && v==good.first)){
        seen[good.first]=1;
    }
}


int n;

void dfs(string s, char mx){
    if(s.length()==n){
        cout<<s<<endl;
    }else{
        for(char c='a';c<=mx;c++){
            dfs(s+c,((c==mx) ? (char)(mx+1) : mx));
        }
    }
}


int mod = 998244353;
int m,k;

int dfs(int cnt,int pred, int sk){
    int sum=0;
    if(cnt==n){
        return 1LL;
    }
    for(int i=1;i<=m;i++){
        if(i==pred){
            if(sk+1<=k){
                sum+=dfs(cnt+1,i,sk+1)%mod;
            }
        }else{
            sum+=dfs(cnt+1,i,sk)%mod;
        }
    }

    return sum;
}

int num(int n,int a,int b){
    return n-(n/a)-(n/b)+(n/(a/gcd(a,b)*b));
}

signed main(){ 
    int k; string s;
    cin>>k>>s;
    int n=s.length();

    if(n<=k){
        cout<<s<<endl;
    }else{
        cout<<s.substr(0,k)<<"..."<<endl;
    }
}  

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define uniq(x) (x).erase(unique(ALL(x)),(x).end())
#define SORT(x) sort(ALL(x))
#define REV(x) reverse(ALL(x))
#define foreach(it,x) for(__typeof((x).begin()) it=(x).begin();it!=(x).end();it++)
#define debug(x) cerr<<#x<<"="<<(x)<<endl
#define gett() cerr<<"Time:"<<clock()<<"ms."<<endl
#define ri(x) scanf("%d",&x);
#define rl(x) scanf("%lld",&x);
#define rlcfpoj(x) scanf("%I64d",&x);
#define pi(x) printf("%d",x);
#define pl(x) printf("%lld",x);
#define plcfpoj(x) printf("%I64d",x);
#define lfd() printf("\n");
#define sp() printf(" ");
string s;
int n;
bool wolf[100100];
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>n>>s;
	s+=s[0];
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			wolf[1]=i;
			wolf[2]=j;
			for(int k=2;k<=n+1;k++){
				wolf[k+1]=(1-((s[k-1]=='o')^(wolf[k]))^wolf[k-1]);
			}
			if(wolf[n+2]!=wolf[2])
				continue;
			if(wolf[n+1]!=wolf[1])
				continue;
			for(int i=1;i<=n;i++){
				if(wolf[i])
					cout<<"W";
				else
					cout<<"S";
			}
			cout<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;
	return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
int main(){
int A,B,C,D;
//scanfで文字列以外を指定する時は&が必要
scanf("%d %d %d %d",&A,&B,&C,&D);
if(A*B>= C*D){
printf("%d",A*B);
}
else{
printf("%d",C*D);
}
return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)

void dfs(int id,int pre,vector<vector<pair<int,int> > > &g,vector<bool>&flag,vector<int>&dst){
    for(auto x:g[id]){
        int s = x.first;
        int d = x.second;
        if(flag[s])continue;
        if(s!=pre){
            dst[s] = dst[id] + d;
            dfs(s,id,g,flag,dst);
        }
    }
}

int main(){
    int n;
    while(cin>> n&&n!=0){
        vector<vector<pair<int,int> > > g(n);
        vector<bool>flag(n);
        vector<int>dst(n);
        vector<int> p(n-1);
        vector<int> d(n-1);
        rep(i,n-1){
            cin >>p[i];
            p[i]--;
        }
        rep(i,n-1){
            cin >> d[i];
        }
        if(n==2){
            cout << d[0] << endl;
            continue;
        }
        rep(i,n-1){
            g[i+1].push_back(MP(p[i],d[i]));
            g[p[i]].push_back(MP(i+1,d[i]));
        }
        int sm = 0;
        int sm2 = 0;
        rep(i,n){
            if(g[i].size()==1){
                flag[i] = true;
                sm2 += g[i][0].second;
            }else{
                for(auto x:g[i]){
                    sm += x.second;
                }
            }
        }
        sm = (sm-sm2)/2*3;
        sm += sm2;
        int k = -1;
        rep(i,n){
            if(!flag[i]){
                k = i;
            }
        }
        dfs(k,-1,g,flag,dst);
        k = -1;
        int ma = -1;
        for(int i=0;i<n;i++){
            if(ma<dst[i]&&!flag[i]){
                ma = dst[i];
                k = i;
            }
        }
        rep(i,n){
            dst[i] = 0;
        }
        dfs(k,-1,g,flag,dst);
        ma = 0;
        for(int i=0;i<n;i++){
            if(ma<dst[i]){
                ma = dst[i];
                k = i;
            }
        }
        //cerr << sm << " " << ma << endl;
        cout << sm-ma << endl;
    }
    return 0;
}


Measured memory_bytes: 3236
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#include<random>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

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

ll lcm(ll n, ll m) {
	return abs(n) / gcd(n, m)*abs(m);//gl=xy
}
 
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 namespace std;

void solve(){
  ll h,w;
  cin>>h>>w;
  if(h!=1&&w!=1)cout<<(h*w+1)/2;
  else cout<<1;
}

int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
  solve();
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int d[100001],a[100001],sum[100001];
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		d[i]=c-'0';
	}
	for(int i=1;i<=n;i++)
	{
		a[i]=d[i-1]^d[i];
	}
	sum[0]=0;
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+a[i];
	}
	int x=0;
	int maxn=0;
	for(int i=1;i<=n;i++)
	{
		x^=a[i];
		int b=upper_bound(sum,sum+n+1,2*k-(!x)+sum[i])-sum;
		maxn=max(maxn,b-i);
	}
	cout<<maxn<<endl;
	return 0;
}

Measured memory_bytes: 1408
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>
/**
   ceil(0, 2) == 0
   ceil(1, 2) == 1
   ceil(2, 2) == 1
   ceil(3, 2) == 2
   ceil(4, 2) == 2
*/
template<class T>
T ceil(T dividend, T divisor)
{
    return (dividend + (divisor - 1)) / divisor;
}
using namespace std;

int main()
{
    int64_t N, H;
    std::cin >> N >> H;

    std::vector<int64_t> B;
    int64_t maxA = 0;

    for (decltype(N) i = 0; i < N; ++i) {
        int64_t a, b;
        std::cin >> a >> b;
        B.push_back(b);
        maxA = std::max(maxA, a);
    }

    std::sort(std::begin(B), std::end(B),
              [](const auto& a, const auto& b) {
                  return a > b;
              });

    int64_t count = 0;
    for (auto bitr = B.begin(); bitr != B.end(); ++bitr) {
        if (H <= 0) {
            std::cout << count << std::endl;
            return 0;
        }
        if (*bitr < maxA) {
            count += ceil(H, maxA);
            std::cout << count << std::endl;
            return 0;
        }

        H -= *bitr;
        count++;
    }

    count += ceil(H, maxA);
    std::cout << count << std::endl;

    return 0;
}


Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i)
#define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i)
const int N=1e5+5;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
	T ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
	return ans*f;
}
template<typename T>void write(T x,char y)
{
	if(x==0)
	{
		putchar('0'),putchar(y);
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	static char wr[20];
	int top=0;
	for(;x;x/=10)wr[++top]=x%10+'0';
	while(top)putchar(wr[top--]);
	putchar(y);
}
void file()
{
#ifndef ONLINE_JUDGE
	freopen("D.in","r",stdin);
	freopen("D.out","w",stdout);
#endif
}
int n,a[N],b[N],c[N],d[N];
void input()
{
	int now=0;
	n=read<int>();
	For(i,1,n)a[i]=c[i]=read<int>(),now^=a[i];
	a[n+1]=c[n+1]=now;
	now=0;
	For(i,1,n)b[i]=d[i]=read<int>(),now^=b[i];
	b[n+1]=d[n+1]=now;
}
unordered_map<int,int>mp;
int fa[N<<1];
int find(int x)
{
	if(!fa[x]||fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
bool vis[N<<1];
void work()
{
	int cnt=0;		
	n++;
	sort(c+1,c+n+1);sort(d+1,d+n+1);
	For(i,1,n)
	{
		if(c[i]^d[i]){write(-1,'\n');return;}
		if(!mp.count(c[i]))mp[c[i]]=++cnt;
		if(!mp.count(d[i]))mp[d[i]]=++cnt;
	}
	int ans=0;
	int x,y;
	For(i,1,n)
	{
		a[i]=mp[a[i]],b[i]=mp[b[i]];
		if(a[i]==b[i])continue;
		if(i<n)ans++;
		x=find(a[i]),y=find(b[i]);
		fa[y]=x;
		vis[x]=vis[y]=1;
	}
	if(!ans)write(ans,'\n');
	else
	{
		vis[a[n]]=vis[b[n]]=1;
		For(i,1,cnt)if(vis[i]&&find(i)==i)ans++;
		write(ans-1,'\n');
	}
}
int main()
{
//	file();
	input();
	work();
	return 0;
}

Measured memory_bytes: 6436
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
using ll = long long;
using P = pair<int, int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef vector<ll> vi;
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
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(){
  ll x, t;
  cin >> x >> t;
  if(x>=t){
    print(x - t);
  }
  else{
    print(0);
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h> //STL include
typedef long long ll;// long long int
const ll INF = 10000000000;//INFinity
using namespace std;//namespace

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}//transform
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//#define int long long // yabai

#define dump(x)  cout << #x << " = " << (x) << endl;// debug cout

#define FOR(i,a,b) for(int i=(a);i<(b);++i)// for macro
#define REP(i,n) for(int i=0;i<(n);++i)
#define REP(i,n) for(int i=n;i>=0;i--)

#define ALL(obj) (obj).begin(),(obj)// iterator

#define pb(a) push_back(a)end()//push_back
#define mp make_pair// make_pair


int main(){

    // kokoni kaku
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(a+b==c+d)cout<<"Balanced"<<endl;
    else cout<<(a+b<c+d?"Right":"Left")<<endl;
    return 0;

}


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

// varibable settings
#define infile "../test/sample-1.in"
#define int long long //{{{
const int INF=1e18;
const int MOD=1e9+7; //}}}

// define basic macro {{{
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ceil(a,b) ((a)+(b)-1)/(b)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ub upper_bound
#define lb lower_bound
#define posl(A, x) (lower_bound(all(A), x)-A.begin())
#define posu(A, x) (upper_bound(all(A),x)-A.begin())
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

#if defined(PCM) || defined(LOCAL)
  #include "lib/dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
//}}}

struct UnionFind {
  vector<int> data;  // size defined only for root node
  int count;

  UnionFind(int size) : data(size, -1), count(size){ }

  bool merge(int x, int y) {
    x=root(x); y=root(y);
    if (x!=y) {
      if (data[y]<data[x]) swap(x, y);
      data[x]+=data[y]; data[y]=x;
      count--;
    }
    return x != y;
  }
  int root(int x) {
    return (data[x]<0 ? x : data[x]=root(data[x]));
  }
  bool same(int x,int y){
    return root(x)==root(y);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

int solve(){
  int n,m;cin>>n>>m;
  UnionFind uf(n);
  rep(i, m){
    int x,y,z;cin>>x>>y>>z;
    x--;y--;
    dump(n,x,y);
    uf.merge(x, y);
  }
  cout << uf.count << endl;
  return 0;
}

signed main() { //{{{
#ifdef INPUT_FROM_FILE
  std::ifstream in(infile);
  std::cin.rdbuf(in.rdbuf());
#endif
  solve();
  return 0;
} //}}}


Measured memory_bytes: 1024
#include<iostream>
#include<string>
using namespace std;
main()
{
  string s;
  cin >> s;
  for (int i = s.size()-2;;i-=2)
  {
    string r, t;
    for (int j = 0; j < i / 2;j++)
    {
      r += s[j];
      t += s[j + i / 2];
    }
    if(r==t)
    {
      cout << i << endl;
      break;
    }
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
int main()
{
    string s;
    cin>>s;

    if(s[2]==s[3] && s[4]==s[5])

        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;

}


Measured memory_bytes: 3572
#include<stdio.h>
#define ll long long
int main()
{
    char a[10];
    gets(a);
    if(a[0]=='S')
        printf("Cloudy\n");
    else if(a[0]=='R')
        printf("Sunny\n");
    else if(a[0]=='C')
        printf("Rainy\n");
    return 0;
}



Measured memory_bytes: 128
def resolve():
    N, M = list(map(int, input().split(" ")))
    loved = [0 for _ in range(M)]
    for i in range(N):
        _, *a = list(map(int, input().split(" ")))
        for food in a:
            loved[food-1] += 1
    print(len(list(filter(lambda x: x == N, loved))))
    

if '__main__' == __name__:
    resolve()

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

int main(){
  ll x,k,d;
  cin>>x>>k>>d;
  x=max(x,-x);
  if(k<=x/d)cout<<x-k*d<<endl;
  else{
    k-=x/d;
    x%=d;
    if(k%2)cout<<d-x<<endl;
    else cout<<x<<endl;
  }
}


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

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define for_rev(i,a,b) for(int i=(a);i>=(b);--i)
typedef unsigned long long ull;
const ull BASE = 1e9 + 7;
ull mul[4003];

string A, B;
int n, m;

bool check(int k) {
	if (k == 0) return true;
	
	vector< int > c(26, 0);
	for_(i,0,k) c[A[i] - 'a']++;
	
	ull h = 0;
	for_(i,0,26) h = h + c[i] * mul[i];
	
	unordered_set< ull > hash_set;
	hash_set.insert(h);
	
	for_(i,k,n) {
		int x = A[i-k] - 'a';
		h = h - c[x] * mul[x];
		c[x]--;
		h = h + c[x] * mul[x];
		
		x = A[i] - 'a';
		h = h - c[x] * mul[x];
		c[x]++;
		h = h + c[x] * mul[x];
		
		hash_set.insert(h);
	}
	
	c.assign(26, 0);
	for_(i,0,k) c[B[i] - 'a']++;
	
	h = 0;
	for_(i,0,26) h = h + c[i] * mul[i];
	
	if (hash_set.count(h)) return true;
	
	for_(i,k,m) {
		int x = B[i-k] - 'a';
		h = h - c[x] * mul[x];
		c[x]--;
		h = h + c[x] * mul[x];
		
		x = B[i] - 'a';
		h = h - c[x] * mul[x];
		c[x]++;
		h = h + c[x] * mul[x];
		
		if (hash_set.count(h)) return true;
	}
	
	return false;
}

int main() {
	cin >> A;
	cin >> B;
	n = A.size();
	m = B.size();
	
	mul[0] = 1;
	for_(i,1,4003) mul[i] = mul[i-1] * BASE;
	
	for_rev(i,min(n,m),0) {
		if (check(i)) {
			cout << i << endl;
			break;
		}
	}
}

Measured memory_bytes: 3344
#include <algorithm>
#include <bitset>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define MOD (1000000007l)
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)

using namespace std;

void solve() {
  ll N, W;
  cin >> N >> W;
  unsigned long long INF = -1;
  INF >>= 1;
  vector<ll> values(110000, INF);
  values[0] = 0;
  rep (n, N) {
    ll w, v;
    cin >> w >> v;
    for (ll i = 101000; i - v >= 0; i--) {
      if (values[i-v] == INF) continue;
      values[i] = min(values[i], values[i-v] + w);
    }
  }
  ll ans = 0;
  rep (i, 110000) if (values[i] <= W) ans = i;
  cout << ans << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  cout << fixed;
  solve();
  return 0;
}


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

using namespace std;
using ll = long long;

int main(){
    ll n;
    cin>>n;
    vector<ll> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    ll x = a[n-1];
    ll ans = 0;
    ll m = x;
    for(int i=0;i<n;i++){
        ll dif = min(abs(a[i] - x/2), abs(a[i] - (x -x/2)));
        if(dif<m){
            ans = a[i];
        }
        m = dif;
    }
    cout<<x<<" "<<ans<<endl;
}


Measured memory_bytes: 1024
using System;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());

        int[] x = new int[n];
        int[] y = new int[n];
        string[] strX = Console.ReadLine().Split(' ');
        string[] strY = Console.ReadLine().Split(' ');

        for(int i =0;i<n;i++)
        {
            x[i] = int.Parse(strX[i]);
            y[i] = int.Parse(strY[i]);
        }
        Calc calc = new Calc();
        Console.WriteLine("{0:f8}",calc.Manhattan(x,y,n));
        Console.WriteLine("{0:f8}",calc.Euclid(x,y,n));
        Console.WriteLine("{0:f8}",calc.Minkowski(x,y,n));
        Console.WriteLine("{0:f8}",calc.Chebyshev(x,y,n));
    }
}

class Calc
{
    //p=3?????¨????????????????????????????????¢
    // Dxy = (?£^n i=1 |x_i - y_i|^p)^1/p
    public double Minkowski(int[] x, int[] y,int n)
    {
        double d2 = 0;
        for(int i=0;i<n;i++)
        {
            double d = Math.Abs(x[i] - y[i]);
            double d1 = Math.Pow(d, 3);
            d2 = d2 + d1;
        }
        double p = 0.3333333333333;
        double d3 = Math.Pow(d2, p); 
        return d3;
    }
    //p=1?????¨?????????????????????????????¢
    // Dxy = (|x_1-y_1|)^2+(|x_n-y_n|)^2
    public double Manhattan(int[] x,int[] y, int n)
    {
        double d1=0;
        for (int i = 0; i < n;i++ )
        {
            d1 += Math.Abs((double)x[i]-(double)y[i]);
        }
            return d1;
    }
    //p= 2?????¨?????????????????????????????¢
    // Dxy^2 =(| x_1 - y_1|)^2 + (| x_n - y_n|)^2 
    public double Euclid(int[] x, int[] y, int n)
    {
        double d2 = 0,d=0;
        for (int i = 0; i < n; i++)
        {
            double temp = Math.Abs((double)x[i] - (double)y[i]);
            d = d + Math.Pow(temp, 2);
        }
        d2 = Math.Sqrt(d);
        return d2;
    }
    //p= ????????¨???????????§????????§????????¢
    // Dxy = max^n i=1 (|x_i - y_i|)
    public double Chebyshev(int[] x, int[] y, int n)
    {
        double max = 0;
        for (int i = 0; i < n;i++ )
        {
            double temp = Math.Abs(x[i] - y[i]);
            if (temp > max)
                max = temp;
        }
            return max;
    }
}

Measured memory_bytes: 9360
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
using namespace std;
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
#define chmax(a, b) (a = (a) < (b) ? (b) : (a))
#define chmin(a, b) (a = (a) > (b) ? (b) : (a))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define all(a) begin(a),end(a)
#define ifnot(a) if(not (a))
#define dump(x)  cerr << #x << " = " << (x) << endl
// #define int ll
#ifdef _MSC_VER
const bool test = true;
#else 
const bool test = false;
#endif


int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
const int INF = 1 << 28;
const ll INFL = (ll)1 << 58;
ll mod = (int)1e9 + 7;

//.....................
const int MAX = (int)2e5 + 5;

string s;

void solve() {
	cin >> s;
	for (auto& c : s) {
		if (c == ',') c = ' ';
	}
	cout << s << endl;
}

signed main() {
	int T = 10;
	cout << fixed << setprecision(15);
	rep(i, T) {
		char s[MAX];
		if (scanf("%s", s) == EOF) break;
		int n = strlen(s);
		for (int i = n - 1; i > -1; i--) {
			ungetc(s[i], stdin);
		}
		solve();
	}
	return 0;
}

Measured memory_bytes: 256