akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_V 3000
#define INF 1e9
 
struct edge{ int to,cap,rev; };
 
vector<edge> G[MAX_V];
int level[MAX_V],iter[MAX_V];
 
void add_edge(int from,int to,int cap){
    G[from].push_back((edge){to,cap,G[to].size()});
    G[to].push_back((edge){from,0,G[from].size()-1});
}
 
void bfs(int s){
    memset(level,-1,sizeof(level));
    queue<int> Q;
    level[s] = 0;
    Q.push(s);
    while(!Q.empty()){
	int v = Q.front(); Q.pop();
	for(int i = 0 ; i < (int)G[v].size() ; i++){
	    edge &e = G[v][i];
	    if(e.cap > 0 && level[e.to] < 0){
		level[e.to] = level[v] + 1;
		Q.push(e.to);
	    }
	}
    }
}
 
int dfs(int v,int t,int f){
    if(v == t) return f;
    for(int &i = iter[v] ; i < (int)G[v].size() ; i++){
	edge &e = G[v][i];
	if(e.cap > 0 && level[v] < level[e.to]){
	    int d = dfs(e.to,t,min(f,e.cap));
	    if(d > 0){
		e.cap -= d;
		G[e.to][e.rev].cap += d;
		return d;
	    }
	}
    }
    return 0;
}
 
int max_flow(int s,int t){
    int flow = 0;
    for(;;){
	bfs(s);
	if(level[t] < 0) return flow;
	memset(iter,0,sizeof(iter));
	int f;
	while((f = dfs(s,t,INF)) > 0){
	    flow += f;
	}
    }
}
 
int main(){
    int N;
    while(cin >> N,N){
	for(int i = 0 ; i < MAX_V ; i++){
	    G[i].clear();
	}
	int k,x,n;
	cin >> n;
	int S = N+n,T = S+1;
	map<int,int> mp;
	for(int i = 0 ; i < n ; i++){
	    cin >> x;
	    mp[x] = i;
	}
	map<int,int>::iterator it;
	for(it = mp.begin() ; it != mp.end() ; ++it){
	    add_edge(S,it->second,1);
	}
	for(int i = 0 ; i < N ; i++){
	    cin >> k;
	    for(int j = 0 ; j < k ; j++){
		cin >> x;
		if(mp.find(x) != mp.end()){
		    add_edge(mp[x],n+i,1);
		}
	    }
	    add_edge(n+i,T,1);
	}
	cout << max_flow(S,T) << endl;
    }
    return 0;
}

Measured memory_bytes: 1532
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

int main()
{   
  int X, A, B;
  cin >> X >> A >> B;
  if(B-A <= 0){
      cout << "delicious" << endl;
  }
  else if(B-A <= X){
      cout << "safe" << endl;
  }else{
      cout << "dangerous" << endl;
  }
}

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

int main (){
  int a;
  int b;
  
  cin >> a;
   
  cin >> b;
  
  if (a<b){
    cout << "a < b" << endl; 
  }
  else if (a>b){
      cout << "a > b" << endl;
  } else if (a==b){
      cout << "a == b" <<endl;
  }
  
}


Measured memory_bytes: 3056
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.next());
        int[] a = new int[n+1];
        for(int i = 1; i <= n; i++){
            a[i] = Integer.parseInt(sc.next());
        }
        
        boolean[] b = new boolean[n+1];
        for(int i = n; i >= 1; i--){
            int x = 0;
            for(int j = 2; i*j <= n; j++){
                if(b[i*j]){
                    x++;
                }
            }
            if(x%2 != a[i]){
                b[i] = true;
            }
        }
        
        int m = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= n; i++){
            if(b[i]){
                m++;
                sb.append(i).append(" ");
            }
        }
        
        if(m == 0){
            System.out.println(0);
        }else{
            System.out.println(m);
            System.out.println(sb);
        }
    }
}

Measured memory_bytes: 49828
def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

def factorize(n):
    a = 2
    lst = []
    while a * a <= n:
        if n % a == 0:
            n = n / a
            lst.append(a)
        else:
            a += 1
    if n > 1:
        lst.append(n)
    return lst

A, B = [int(x) for x in input().split()]
lst = factorize(gcd(A, B))
print(len(set(lst)) + 1)

Measured memory_bytes: 3064
/*
author: diradon
25-Aug-19
17:50:52
*/

#include<bits/stdc++.h>
#define INF 1e9
typedef long long int ll;
using namespace std;

int main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    int h[n+5];
    int a[n+5];
    for (int i = 1; i <= n; i++)
    {
         cin >> h[i];
         a[i] = INF;
    }

    a[1] = 0;
    for (int i = 1; i <= k && i+1 <= n; i++)
    {
        a[i+1] = abs(h[i+1] - h[1]);
    }

    for (int i = k+1; i <= n; i++)
        for (int j = 1; j <= k; j++)
            a[i] = min(a[i], a[i-j] + abs(h[i-j] - h[i]));
            
    cout << a[n] << "\n";       

}

Measured memory_bytes: 1024
import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nms = lambda: map(str, sys.stdin.readline().split())
nl = lambda: list(nm())

n = ni()
h = nl()
INF = 10 ** 9
dp = [INF for i in range(n)]
dp[0] = 0
dp[1] = abs(h[0] - h[1])
for i in range(2, n):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[-1])

Measured memory_bytes: 14012
#include <iostream>

int main() {
	int n;
	while( std::cin >> n ) {
		int ans = 0;
		for( int a=0; a<10; ++a )
			for( int b=0; b<10; ++b )
				for( int c=0; c<10; ++c )
					for( int d=0; d<10; ++d )
						ans += (a+b+c+d==n)?1:0;
		std::cout << ans  << std::endl;
	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int qh(LL n)
{
    int sum = 0;
    while(n > 0)
    {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
LL t,n;
int main()
{
    LL cnt = 1;
    cin >> n;
    int ans = qh(n);
    t = n;
    while(t >= 10)
    {
        t /= 10;
        cnt *= 10;
    }
    ans = max(ans,qh(n / cnt * cnt - 1));
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
import math
N, D = list(map(int, input().split()))
result = 0
list = []
count = 0
for i in range(N):
    X, Y = map(int, input().split())
    result = math.sqrt(X**2 + Y**2)
    list.append(result)
for j in list:
    if j <= D:
        count += 1
print(count)

Measured memory_bytes: 17020
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

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

using namespace std;
typedef long long ll;

int main()
{
    // Input
    int x;
    cin >> x;

    if (x == 0) {
        cout << 1;
    } else {
        cout << 0;
    }

    return 0;
}


Measured memory_bytes: 3188
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10

    #H*W - 最短経路の距離 - 黒いマスの数　- スタート分の1
    H,W = LMIIS()
    grid = []
    num_black = 0
    for i in range(H):
        line = list(input())
        grid.append(line)
        num_black += line.count('#')

    
    #bfs
    target_queue = deque()
    
    visited = []
    for i in range(H):
        visited.append([-1]*W)
    visited[0][0] = 0
    target_queue.append((0,0))

    while target_queue:
        y,x = target_queue.popleft()
        if y == H-1 and x == W-1:
            break
        next_distance = visited[y][x] + 1
        if y > 0 and grid[y-1][x] != '#' and visited[y-1][x] == -1:
            visited[y-1][x] = next_distance
            target_queue.append((y-1,x))
        if y + 1 < H and grid[y+1][x] != '#' and visited[y+1][x] == -1:
            visited[y+1][x] = next_distance
            target_queue.append((y+1,x))
        if x > 0 and grid[y][x-1]!= '#' and visited[y][x-1] == -1:
            visited[y][x-1] = next_distance
            target_queue.append((y,x-1))
        if x+1 < W and grid[y][x+1]!='#' and visited[y][x+1] == -1:
            
            visited[y][x+1] = next_distance
            target_queue.append((y,x+1))
    
    if visited[H-1][W-1] == -1:
        print(-1)
    else:
        print(H*W - num_black - visited[H-1][W-1] -1)
    





        
    
main()

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

const int MAX_N = 1000010;
int G[MAX_N];

int main()
{
    int N;
    cin >> N;
    fill_n(G, N, 0);
    for (int i = 1; i < N; i++)
    {
        int number;
        cin >> number;
        number--;
        G[number]++;
    }

    for (int i = 0; i < N; i++)
    {
        cout << G[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 4404
import java.util.Arrays;
import java.util.Scanner;
 
class Main{
    public static void main(String args[]){ 
        Scanner scan = new Scanner(System.in);
 
        int n;
         
        boolean flag = false;
         
        n = scan.nextInt();
         
        int a[][];
         
        a = new int[n][7];
         
        for(int j = 0; j < n; j++){
            for(int i = 1; i < 7; i++){  
                a[j][i] = scan.nextInt();
            }
        }
         
        for(int i = 0; i < n-1; i++){
            for(int j = i+1; j < n; j++){
                if(flag) break;
                flag = dice(a[i], a[j]);
            }
        }
        if(flag){
            System.out.println("No");
        }else{
            System.out.println("Yes");
        }
         
    }
    public static boolean dice(int a[], int b[]){
    int h = 0;
        boolean flag = false;
     
 
        for(int i = 0; i < 6; i++){
            for(int j = 0; j < 4; j++){
                if(flag == true)break;
                    h = a[2];
                    a[2] = a[3];
                    a[3] = a[5];
                    a[5] = a[4];
                    a[4] = h;
                    flag = Arrays.equals(a,b);
 
            }
            if(i == 0 || i == 4){
                h = a[1];
                a[1] = a[3];
                a[3] = a[6];
                a[6] = a[4];
                a[4] = h;
            }else{
                h = a[1];
                a[1] = a[2];
                a[2] = a[6];
                a[6] = a[5];
                a[5] = h;
            }
        }
         
        return flag;
    }
     
}


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

int main(void){
  ll l,r; cin >> l >> r;
  if(r - l > 2019){
    cout << 0 << endl;
  }
  else{
    ll mn = 2100;
    for(ll i = l; i < r; i++){
      for(ll j = i + 1; j <= r; j++){
        mn = min(mn,(i*j)%2019);
      }
    }
    cout << mn << endl;
  }
  return 0;
}


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

int main(){
    int n;
    scanf("%d",&n);
    long long t = 1, a = 1;
    int T, A;
    for(int i=0;i<n;i++){
        scanf("%d%d",&T,&A);
        long long tmp = max(max(t%T?t/T+1:t/T,a%A?a/A+1:a/A),1ll);
        t = tmp*T;
        a = tmp*A;
    }
    printf("%lld\n",t+a);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;
typedef pair<Pii, int> PPi;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);

struct edge{int to, cost;};

class Graph
{
public:
    int V;
    vector<vector<edge>> G;

    Graph(int V): V(V){
        G = vector<vector<edge>>(V, vector<edge>(0));
    }

    void add_edge(int from, int to, int cost){
        G[from].push_back(edge({to, cost}));
    }

    void add_edge2(int v1, int v2, int cost){
        add_edge(v1, v2, cost);
        add_edge(v2, v1, cost);
    }

    void dfs(int v, int g, vec &group){
        if(group[v] != -1) return;
        group[v] = g;
        REP(k, G[v].size()) dfs(G[v][k].to, g, group); 
    }

};

signed main(){

    int N, K, L;
    cin >> N >> K >> L;
    int p, q;
    Graph R(N), T(N);
    REP(i, K){
        cin >> p >> q;
        R.add_edge2(p - 1, q - 1, 0);
    }
    REP(i, L){
        cin >> p >> q;
        T.add_edge2(p - 1, q - 1, 0);
    }

    vec groupR(N, -1), groupT(N, -1);
    vector<PPi> group(N);

    int g = 0;
    REP(i, N){
        if(groupR[i] == -1){
            R.dfs(i, g, groupR);
            g++;
        }
    }
    g = 0;
    REP(i, N){
        if(groupT[i] == -1){
            T.dfs(i, g, groupT);
            g++;
        }
    }

    REP(i, N) group[i] = PPi(Pii(groupR[i], groupT[i]), i);
    SORT(group);

    vec ans(N);
    int s = 0, n = 1;
    REP(i, N){
        if(i == N - 1 || group[i].first != group[i + 1].first){
            FOR(j, s, i + 1) ans[group[j].second] = n;
            s = i + 1;
            n = 1;
        }else{
            n++;
        }
    }
    REP(i, N) cout << ans[i] << " ";
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Measured memory_bytes: 28288
#include<cstdio>
#include<cstring>
int main() {
	char s[201], p[101];
	scanf("%s%s", s, p);
	int l = strlen(s), i, j;
	for (i = l; i >= 0; i--)s[i + l] = s[i];
	for (i = 0; i < l; i++) {
		for (j = 0; j < strlen(p); j++) {
			if (s[i + j] != p[j])break;
		}
		if (j == strlen(p)) {
			printf("Yes\n");
			return 0;
		}
	}
	printf("No\n");
	return 0;
}


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

int main()
{
    int i,j,k,n;

    cin>>n;
    int a[n],b[n];
    memset(b,0,sizeof b);
    for(i=0; i<n; i++)
        cin>>a[i];
    for(i=0; i<n-1; i++)
    {
        b[i+1]=b[i]+max(0,a[i]-a[i+1]);
        if(a[i]-a[i+1]>=0)
            b[i+1]=b[i]+a[i]-a[i+1];
        else
            b[i+1]=0;
        if(b[i+1]>1)
        {
            cout<<"No\n";
            return 0;
        }
    }
    cout<<"Yes\n";
    return 0;
}


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

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  int a, b;
  cin >> a >> b;
  int res = a * b;
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define INF 1e18
#define MOD 1000000007
#define N 1000005
#define BB(V) V[V.size()-2]
#define ex(V) return printf(V),0
using namespace std;
char a[100005];
int n;
deque<int>dq;
bool check(int x){
	for(int i=0;i<=n-x;i++){
		if(dq.front()+x<=i)dq.pop_front();
		if((dq.size()&1)^(a[i]=='1'))dq.pb(i);
	}
	for(int i=n-x+1;i<x;i++){
		if(dq.front()+x<=i)dq.pop_front();
		if((dq.size()&1)^(a[i]=='1'))return false;
	}
	return true;
}
int BS(int s,int e){
	if(s==e)return s;
	int m=s+e>>1;
	if(check(m+1))return BS(m+1,e);
	return BS(s,m);
}
int main(){
	scanf("%s",a);
	n=strlen(a);
	printf("%d",BS(1,n));
}

Measured memory_bytes: 2048
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>

using namespace std;
typedef long long ll;

int main()
{
	int L;
	scanf("%d", &L);
	
	float V = L * L * L;
	V = V / 27.0;
	
	printf("%f\n", V);
	
	return 0;
}

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

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

  int n = s.size();
  while(n){
    if(n>=5 && s.substr(n-5)=="dream"){       
      s.erase(n-5); n = s.size();
    } else if(n>=5 && s.substr(n-5)=="erase"){
      s.erase(n-5); n = s.size();
    } else if(n>=6 && s.substr(n-6)=="eraser"){
      s.erase(n-6); n = s.size();
    } else if(n>=7 && s.substr(n-7)=="dreamer"){
      s.erase(n-7); n = s.size();
    } else break;
  }
  if(s=="") cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 512
l, r = gets.split.map(&:to_i)

lrange = l % 2019
rrange = r % 2019

minrange = [lrange, rrange].min
maxrange = [lrange, rrange].max

if minrange == maxrange
  puts 0
elsif l / 2019 != r / 2019
  puts 0
else
  ans = 2100
  (minrange..maxrange-1).each do |i|
    ((minrange+1)..maxrange).each do |j|
      ans = [ans, i * j % 2019].min
    end
  end
  puts ans
end


Measured memory_bytes: 1788
N,X,Y = map(int,input().split())

dp = [0]*N

for i in range(1,N+1):
    for j in range(i+1,N+1):
        m = min(j-i,abs(j-Y)+abs(X-i)+1)
        dp[m-1]+=1
        # print(i,j,m)
for i in dp[:-1]:
    print(i)



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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> a(N);
    rep(i, N) cin >> a[i];
    sort(a.begin(), a.end());
    vector<ll> s(N + 1);
    rep(i, N) s[i + 1] = s[i] + a[i];

    auto calc = [&](int x) {
        ll total = 0, num = 0;
        rep(i, N) {
            int j = lower_bound(a.begin(), a.end(), x - a[i]) - a.begin();
            num += N - j;
            total += s[N] - s[j];
            total += a[i] * (N - j);
        }
        return make_pair(total, num);
    };

    int l = 0, r = 200005;
    while (r - l > 1) {
        int c = (r + l) / 2;
        if (calc(c).second >= M) l = c;
        else r = c;
    }
    auto p = calc(l);
    ll ans = p.first;
    ans -= (p.second - M) * l;
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <assert.h>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

int main(){
  string s;
  cin>>s;
  rep(i,0,s.sz){
    if(s[i]=='?'){
      cout << "D";
    }
    else{
      cout << s[i];
    }
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 3756
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <sstream>
#include <cstdlib>
using namespace std;
int main(){
	int N,M,i,a[1000],b[1000],j,count=0;
	while(cin>>N>>M){
		if(N==0&&M==0)break;
		//??\???
		for(i=0;i<N;i++){
			cin>>a[i];
		}
		for(j=0;j<M;j++){
			cin>>b[j];
		}
		//??????
		for(i=0;i<M;i++){
			count+=b[i];
			count+=a[count];
			if(count>=N-1){
				cout<<i+1<<endl;
				count=0;
				break;
			}
		}
	}

	return 0;
}

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

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

bool binarySearch(int a[], int n, int x)
{
  int mid;
  int left = 0;
  int right = n;
  while(left < right){
    mid = (left + right) / 2;
    if(a[mid] == x)
      return true;
    else if(x < a[mid])
      right = mid;
    else
      left = mid + 1;
  }
  return false;
}
		   

int main()
{
  int n, q, ans = 0;
  cin >> n;
  int S[n];
  REP(i, n)
    cin >> S[i];
  cin >> q;
  int T[q];
  REP(i, q)
    cin >> T[i];
  REP(i, q)
    if(binarySearch(S, n, T[i]))
      ans++;
  cout << ans << endl;
}

Measured memory_bytes: 1744
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

int main(){
  ll a,b,k;
  cin>>a>>b>>k;
  ll d = min(a,k);
  a -= d;
  k -= d;
  b -= k;
  if(b<0){
    cout << 0 << " " << 0 << endl;
  }
  else{
    cout << a << " " << b << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    x,n = LI()
    if x < n:
        print(0)
    else:
        print(10)
    return

#B
def B():
    n,x = LI()
    l = LI()
    d = 0
    ans = 1
    for i in range(n):
        d += l[i]
        if d <= x:
            ans += 1
    print(ans)
    return

#C
def C():
    w,h,x,y = LI()
    ans = w*h/2
    k = 0
    if x == w/2 and y == h/2:
        k = 1
    print(ans,k)
    return

#D
def D():
    n,k = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    b.insert(0,0)
    ans = 0
    for l in range(n):
        r = bisect.bisect_left(b,b[l]+k)
        ans += n-r+1
    print(ans)
    return

#E
def E():
    n,m = LI()
    s = LI()
    t = LI()
    dp = [[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    for j in range(m+1):
        dp[0][j] = 1
    for i in range(1,n+1):
        for j in range(1,m+1):
            if s[i-1] == t[j-1]:
                dp[i][j] += dp[i-1][j]+dp[i][j-1]
            else:
                dp[i][j] += dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
            if dp[i][j] >= mod or 0 > dp[i][j]:
                dp[i][j] %= mod
    print(dp[n][m])
    return

#F
def F():
    n = I()
    x = [None for i in range(n)]
    y = [None for i in range(n)]
    f = [None for i in range(n)]
    for i in range(n):
        a,b,d = LS()
        a = int(a)
        b = int(b)
        x[i] = a
        y[i] = b
        if d == "R":
            f[i] = (1,0)
        elif d == "L":
            f[i] = (-1,0)
        elif d == "U":
            f[i] = (0,1)
        else:
            f[i] = (0,-1)
    dx = max(x)-min(x)
    dy = max(x)-min(y)
    ans = dx*dy
    if ans == 0:
        print(0)
        quit()
    l = 0
    r = 100000000
    while r-l > 0.5:
        m = (l+r)/2
        px = [x[i]+f[i][0]*m for i in range(n)]
        py = [y[i]+f[i][1]*m for i in range(n)]
        dx = max(x)-min(x)
        dy = max(x)-min(y)
        if dx*dy < ans:
            ans = dx*dy

    return

#Solve
if __name__ == "__main__":
    E()


Measured memory_bytes: 76636
N, M = map(int, input().split())
MOD = 10**9 + 7

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2,5*10**5+1): # <- どこまでfor文を回すかは問題次第, 2*10**6くらいまでならpypyなら間に合う
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

def comb(n, r, mod=MOD):
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

def perm(n, r, mod=MOD):
    return  g1[n] * g2[n-r] % mod


base = ans = perm(M, N, MOD)

for n in range(1, N+1):
    temp = (comb(N, n) * perm(M-n, N-n)) % MOD
    if n%2:
        base -= temp
    else:
        base += temp

print((ans*base) % MOD)

Measured memory_bytes: 68228
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <cassert>
#include <unordered_map>

#define _(x) { cout << #x << " = " << x << " "; }

const double E = 1e-8;
const double PI = acos(-1);
const int INF = 1e6;

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i) cin >> v[i];
    int min_cos = INF;
    vector<int> dp(n);
    if (n <= 1) {
        cout << 0 << endl;
        return 0;
    }

    dp[0] = 0;
    dp[1] = abs(v[1]-v[0]);
    for (int i = 2; i < n; ++i) {
        dp[i] = min(abs(v[i]-v[i-1])+dp[i-1], abs(v[i]-v[i-2])+dp[i-2]);
    }
    cout << dp[n-1] << '\n';
    return 0;
}



Measured memory_bytes: 3928
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define endl "\n"
#define all(a) a.begin(),a.end()
#define debug(x) cout << x << endl;
#define int long long
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

using namespace __gnu_pbds;
using namespace std;
using LD = long double;

const int N = 1e7+1;
const int mod = 1e9+7;
const int INF = 1e18;

void solve() {
	string s;
	cin >> s;
	cout << s.substr(0,3) << endl;
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1,i = 1;
    //cin >> t;
    while(t--) {
        //cout << "Case #" << i << ": ";
        solve();
        //i++;
    }
    return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;

int n, m;
double prob[20][20];
double dp[20][1 << 20];

double f(int opp, int rem) {
	if(dp[opp][rem] != -1) {
		return dp[opp][rem];
	}
	if(opp == n) {
		return dp[opp][rem] = 1.0;
	}
	if(rem == 0) {
		return dp[opp][rem] = 0.0;
	}

	double ret = 0;
	for(int i = 0; i < m; i++) {
		if((rem >> i) & 1) {
			double win = 1.0;
			double res = 0;
			for(int j = opp; j <= n; j++) {
				res += win * (1.0 - prob[i][j]) * f(j, rem ^ (1 << i));
				win *= prob[i][j];
			}
			ret = max(ret, res);
		}
	}

	return dp[opp][rem] = ret;
}

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


	cin >> m >> n;
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n; j++) {
			cin >> prob[i][j];
		}
	}

	for(int i = 0; i < n + 1; i++) {
		for(int j = 0; j < 1 << m; j++) {
			dp[i][j] = -1;
		}
	}

	cout << fixed << setprecision(15) << f(0, (1 << m) - 1) << endl;
}

Measured memory_bytes: 12076
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <stdlib.h>
#include <algorithm>
#include <functional>
 
using namespace std;

bool isPrime(int num){
    double sqrtNum = sqrt(num);
    if (num < 2){
        return false;
    }
    else if (num == 2){
        return true;
    }
    else if (num % 2 == 0){
        return false;
    }
    
    for (int i = 3; i <= sqrtNum; i += 2){
        if (num % i == 0){
            return false;
        }
    }
    return true;
}
int main(void) {
    unsigned long int X = 0;
    cin >> X;
    
    if(X % 2 == 0 && X != 2){
        X++;
    }
    while(!isPrime(X)){
        X += 2;
    }
    cout << X << endl;
    return 0;
}

Measured memory_bytes: 256
#pragma gcc optimize("Ofast")

#include "bits/stdc++.h"
using namespace std;
typedef int64_t lld;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
typedef pair<int,pll> pip;
typedef pair<pll,int> ppi;
typedef pair<lld,pll> plp;
typedef pair<pll,lld> ppl;
typedef pair<pll,pll> ppp;
template<typename T>
using maxHeap = priority_queue<T,vector<T>,less<T>>;
template<typename T>
using minHeap = priority_queue<T,vector<T>,greater<T>>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define jizz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
inline void input(int &_x) {
    _x = 0;
    int _tmp = 1; char _tc = getchar();
    while((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
    if(_tc == '-') _tc = getchar(), _tmp = -1;
    while(_tc >= '0' && _tc <= '9') _x = _x*10+(_tc-48), _tc = getchar();
    _x *= _tmp;
}
inline void output(int _x) {
    char _buff[20]; int _f = 0;
    if(_x == 0)putchar('0');
    while(_x > 0)
    {
        _buff[_f++] = _x%10+'0';
        _x /= 10;
    }
    for(_f-=1; _f >= 0; _f--)
        putchar(_buff[_f]);
    putchar('\n');
}
template<typename Iter>
ostream& _out(ostream &s, Iter b, Iter e) {
    //s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    //s<<"]";
    return s;
}
template<class T1,class T2>
ostream& operator<<(ostream& out, pair<T1,T2> p) {
    return out << '(' << p.first << ", " << p.second << ')';
}
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) {
     return _out(s,c.begin(),c.end());
 }
#ifdef erd1
    #define pprint(x) cerr<<__PRETTY_FUNCTION__<<":"<<__LINE__<<" - "<<(#x)<<"="<<(x)<<endl
#else
    #define pprint(x)
#endif

// code starts here
vector<int> a;
vector<pii> v;
signed main(){
    int n;
    cin >> n;
    a.resize(n*n);
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        v.pb({x-1, i});

    }
    sort(all(v));
    int ptr = 0;
    for(auto p: v){
        for(int cnt = p.ss; cnt > 0; ptr++){
            if(ptr >= p.ff)return cout << "No" << endl, 0;
            if(!a[ptr])a[ptr] = p.ss+1, cnt--;
        }
        a[p.ff] = p.ss+1;
    }
    reverse(all(v));
    //cout << a << endl;
    ptr = n*n-1;
    for(auto p: v){
        for(int cnt = n-p.ss-1; cnt > 0; ptr--){
            if(ptr <= p.ff)return cout << "No" << endl, 0;
            if(!a[ptr])a[ptr] = p.ss+1, cnt--;
        }
    }
    cout << "Yes" << endl << a << endl;
}


Measured memory_bytes: 2176
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x3f3f3f3f
#define mod 998244353
#define maxn 2010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static char buf[20];
	int len=0;
	if(x<0)putchar('-'),x=-x;
	for(;x;x/=10)buf[len++]=x%10+'0';
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]);
}
inline void writesp(ll x){write(x); putchar(' ');}
inline void writeln(ll x){write(x); putchar('\n');}
ll fac[2*maxn],inv[2*maxn];
int n,k;
ll power(ll a,ll b)
{
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)ans=ans*a%mod;
	return ans;
}
ll C(int n,int m){return (n<0||m<0||m>n)?0:fac[n]*inv[m]%mod*inv[n-m]%mod;}
ll calc(int n,int m,int k)
{
	ll tot=0;
	for(int i=0;i<=k;i++)
		tot+=C(k,i)*power(2,i)%mod*C(n+m-1,n-i)%mod;
	// printf("%d %d %d : %lld\n",n,m,k,tot);
	return tot%mod;
}
int main()
{
	k=read(); n=read();
	fac[0]=inv[0]=1;
	for(int i=1;i<=n+k;i++){
		fac[i]=fac[i-1]*i%mod;
		inv[i]=power(fac[i],mod-2);
	}
	for(int i=2;i<=2*k;i++){
		int cnt=std::min((i-1)/2,(2*k+1-i)/2);
		if(i&1)writeln(calc(n,k-2*cnt,cnt));
		else writeln((calc(n,k-1-2*cnt,cnt)+calc(n-1,k-1-2*cnt,cnt))%mod);
	}
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        int n = sc.NextInt();
        int[] a = sc.IntArray();

        int answer = a.Sum() - a.Count();

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 28708
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=lst(n)

b = Counter(arr)
ak=list(b.keys())
av=list(b.values())

am=max(av)
ans=[]
for i in range(len(ak)):
    if av[i]==am:
      ans.append(ak[i])
ans.sort()
for i in ans:
    print(i)


Measured memory_bytes: 120016
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>

using namespace std;
#define int long
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

signed main() 
{
	string S;
	cin >> S;
	int count = 0;
	for (int i = 0; i < S.size() / 2; i++)
	{
		if (S[i] != S[S.size() - 1 - i])
		{
			count++;
		}
	}
	cout << count;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Q2
{
    class Program
    {
        static void Main(string[] args)
        {
            string line = Console.ReadLine();
            int N = int.Parse(line);
            line = Console.ReadLine();
            int R = 0, B = 0;
            foreach(char c in line)
            {
                if (c == 'R') R++;
                else B++;

            }
            if (R>B)Console.WriteLine("Yes");
            else Console.WriteLine("No");

        }
    }
}


Measured memory_bytes: 11092
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var stdInScanner = bufio.NewScanner(os.Stdin)

func nextInt() int {
	stdInScanner.Scan()
	i, _ := strconv.Atoi(stdInScanner.Text())
	return i
}

func main() {
	stdInScanner.Split(bufio.ScanWords)
	X := nextInt()

	loopEnabled := true
	for i := -118; i <= 119 && loopEnabled; i++ {
		for j := -119; j <= 118 && loopEnabled; j++ {
			if X == (int(math.Pow(float64(i), 5.0)) - int(math.Pow(float64(j), 5.0))) {
				fmt.Println(i, j)
				loopEnabled = false
			}
		}
	}
}


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

char word[100100];

main()
{
	scanf("%s",word);
	for(int i=1;word[i];i++)
	{
		if(word[i]==word[i-1])
		{
			printf("%d %d\n",i,i+1);
			return 0;
		}
		if(i>=2&&word[i]==word[i-2])
		{
			printf("%d %d\n",i-1,i+1);
			return 0;
		}
	}
	printf("-1 -1\n");
}

Measured memory_bytes: 384
#include<stdio.h>
int main(void) {
	
	long long int i,o,t,j,l,s,z,ansa=0,ansb=0;
	scanf("%lld %lld %lld %lld %lld %lld %lld", &i, &o, &t, &j, &l, &s, &z);
	ansa += o;
	ansb += o;
	ansa += (i / 2)*2;
	ansa += (j / 2)*2;
	ansa += (l / 2) * 2;
	i--; j--; l--; ansb += 3;
	ansb += (i / 2) * 2;
	ansb += (j / 2) * 2;
	ansb += (l / 2) * 2;
	if (i < 0 || j < 0 || l < 0) { ansb = 0; }
	if (ansa < ansb) { ansa = ansb; }
	printf("%lld", ansa);
	return 0;
}

Measured memory_bytes: 128
#素因数分解、計算量はO(√N)
from collections import defaultdict
def factorize(n):
  b = 2
  dic = defaultdict(lambda: 0)
  while b * b <= n:
    while n % b == 0:
      n //= b
      dic[b] += 1
    b = b + 1
  if n > 1:
    dic[n] += 1
  return dic
N = int(input())
fct = factorize(2*N)
lis = []
for k,v in fct.items():
  lis.append(pow(k,v))
ans = 10**18
from itertools import groupby, accumulate, product, permutations, combinations
for pro in product([0,1],repeat=len(lis)):
  if sum(pro)==0:
    continue
  prod1 = 1
  for i,p in enumerate(pro):
    if p==1:
      prod1 *= lis[i]
  prod2 = (N*2)//prod1
  if prod1<prod2:
    prod1,prod2 = prod2,prod1
  
  for i in range(1,prod2+1):
    if prod1*i>ans:
      break
    if (prod1*i-1)%prod2==0:
      ans = min(ans, prod1*i-1)
      break
    if (prod1*i+1)%prod2==0:
      ans = min(ans, prod1*i)
      break

print(ans)



Measured memory_bytes: 68860
#include <iostream>
#include <math.h>
using namespace std;
int a,b,c,d;
int main(){
    cin >> a >> b >> c >> d;
    if((a-c)*(a-c) <= d*d){
        cout << "Yes" << endl;
    }else if(((a-b)*(a-b)) <= d*d && ((b-c)*(b-c) <= d*d)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;

typedef modint998244353 mint;

const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
//const ll MOD = 1e9 + 7;
const ll MOD = 998244353;

const ll MAX = 1e9 + 5;


int main() {
	string s;
	cin >> s;
	vector<int> sa = suffix_array(s);
	ll l = s.length();
	ll ans = l * (l + 1) / 2;
	for (auto x : lcp_array(s, sa)) {
		ans -= x;
	}
	cout << ans << endl;
}

Measured memory_bytes: 15636
S = input()
N = len(S)

def is_kaibun(s):
    return list(s) == list(reversed(s))

print("Yes" if is_kaibun(S) and is_kaibun(S[:int((N-1)/2)]) and is_kaibun(S[int((N+3)/2)-1:]) else "No")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int A,B,X;
    cin >> A >> B >> X;
    if (A > X || A+B < X) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}


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

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

long long f(long long n, long long x)
{
    if (n >= 0) {
        return n / x + 1;
    } else {
        return 0;
    }
}
int main()
{
    long long a, b, x;
    cin >> a >> b >> x;

    cout << f(b, x) - f(a - 1, x) << endl;
}


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

int F[102][102];

void
DFS (int Y, int X, int A)
{
  if (F[Y][X] != A)
    return;

  F[Y][X] = 7;

  DFS (Y - 1, X, A);
  DFS (Y, X + 1, A);
  DFS (Y + 1, X, A);
  DFS (Y, X - 1, A);
}

int
main ()
{
  int w, h;
  int xs, ys;
  int xg, yg;
  int n;
  int c, d, x, y;

  while (true)
    {
      cin >> w >> h;
      if (w == 0 && h == 0)
	break;
      cin >> xs >> ys;
      cin >> xg >> yg;
      cin >> n;

      for (int i = 0; i < n; i++)
	{
	  cin >> c >> d >> x >> y;
	  if (d == 0)
	    {
	      for (int a = 0; a < 4; a++)
		{
		  for (int b = 0; b < 2; b++)
		    {
		      F[y + b][x + a] = c;
		    }
		}

	    }
	  else
	    {
	      for (int a = 0; a < 2; a++)
		{
		  for (int b = 0; b < 4; b++)
		    {
		      F[y + b][x + a] = c;
		    }
		}
	    }

	}


      if (F[ys][xs] == 1 || F[ys][xs] == 2 || F[ys][xs] == 3
	  || F[ys][xs] == 4 || F[ys][xs] == 5)
	{
	  DFS (ys, xs, F[ys][xs]);
	}

      if (F[yg][xg] == F[ys][xs])
	{
	  cout << "OK" << endl;
	}
      else
	{
	  cout << "NG" << endl;
	}


    }

  return 0;
}

Measured memory_bytes: 2988
S=gets.chomp

flag=true
S.length.times do |i|
  str = S[i]
  if (i+1) % 2 == 0
    if str!="L" && str!="U" && str!="D"
      flag = false
      break
    end
  else
    if str!="R" && str!="U" && str!="D"
      flag = false
      break
    end
  end
end

if flag
  puts "Yes"
else
  puts "No"
end

Measured memory_bytes: 1788
n=int(input())
p=list(map(int,input().split()))
a=0
for i in range (1,n-1):
    if p[i]!=max(p[i-1],p[i],p[i+1]) and p[i]!=min(p[i-1],p[i],p[i+1]):
        a+=1
    else:
        pass
print(a)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define ull unsigned long long
#define dd double
#define oo 1001007000
#define ff float
#define ooo 1000000100000000000
#define iii pair<ll,ll>
#define vii vector<ll>
#define viii vector<iii>
#define sss pair<str,str>
#define str string
#define sii set<ll>
#define siii set<iii>
#define st size_t
#define r0 return 0
#define pb push_back
#define sz size
using namespace std;

const char E='\n';
const int N=10005;
const int NN=1000000;
const ll md=998244353;

ll gcd(ll a,ll b){
    while (a>0 && b>0){
        if (a>b)a%=b;else b%=a;
    }
    return a+b;
}

int main(){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
    ll n;
    cin >> n;
    ll ans=0;
    for (ll i=1;i<=n;i++){
        for (ll j=1;j<=n;j++){
            for (ll o=1;o<=n;o++){
                ans+=gcd(gcd(i,j),o);
            }
        }
    }
    cout << ans << E;
    r0;
}
/*














*/


Measured memory_bytes: 3652
#include<iostream>

using namespace std;

int main(void){
  int x, y, z, w, u, v;
  cin >> x >> y >> z >> w;
  u = z - x;
  v = w - y;
  cout << z - v << " " << w + u << " " << x - v << " " << y + u << endl;
  return 0;
}


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


int main() {
  stack<int> S;
  int a, b, x;
  string s;

  while (cin >> s) {
    if (s[0]=='+') {
      b = S.top(); 
      S.pop();
      a = S.top(); 
      S.pop();
      S.push(a + b);
    } else if (s[0]=='-') {
      b = S.top(); 
      S.pop();
      a = S.top(); 
      S.pop();
      S.push(a - b);      
    } else if (s[0] == '*') {
      b = S.top(); 
      S.pop();
      a = S.top(); 
      S.pop();
      S.push(a * b);        
    } else {
      S.push(atoi(s.c_str()));
    }
  }
  cout << S.top() << endl;


  return 0;
}


Measured memory_bytes: 3200
#include "bits/stdc++.h"
using namespace std;
int main(){
    int N,M,i,j,min,dist,goal;
    cin >> N >> M;
    vector<int> a(N),b(N),c(M),d(M);
    for(i=0;i<N;i++) cin >> a.at(i) >> b.at(i);
    for(j=0;j<M;j++) cin >> c.at(j) >> d.at(j);
    for(i=0;i<N;i++){
        min = 400000001;
        for(j=0;j<M;j++){
            dist = abs(a.at(i)-c.at(j))+abs(b.at(i)-d.at(j));
            if(dist < min){
                min = dist;
                goal = j+1;
            }
        }
        cout << goal << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a[3];
	for (int i = 0; i < 3; i++)cin >> a[i];
	sort(a, a + 3);
	if (a[0] == 5 && a[1] == 5 && a[2] == 7)cout << "YES\n";
	else cout << "NO\n";
}

Measured memory_bytes: 256
import numpy as np
N,Y = map(int, input().split())

count = 0
for a in range(0,N+1):
    res_b =  (Y - 1000*N - 9000*a)%4000
    if res_b > 0:
        continue
    else:
        b = (Y - 1000*N - 9000*a)//4000
        c = N - a - b
        if (b>=0)&(b<=N)&(c>=0)&(c<=N):
            print('{} {} {}'.format(a,b,c))
            count += 1
            break
if count == 0:
    print('{} {} {}'.format(-1,-1,-1))

Measured memory_bytes: 12428
import math
from math import factorial

n = int(input())
X, Y = [],[]
for i in range(n):
  x, y = map(int, input().split())
  X.append(x)
  Y.append(y)
D = [[0] * n for _ in range(n)]
def ncr(n,r):
  return factorial(n) / factorial(r) / factorial(n - r)

def getD(x1, y1, x2, y2):
  return math.sqrt((x1-x2)**2 + (y1-y2)**2)

for i in range(n):
  for j in range(i+1,n):
    D[i][j] = getD(X[i],Y[i],X[j],Y[j])
sum = 0
mt = factorial(n-1) * 2
for i in range(n):
  for j in range(i+1,n):
    sum += D[i][j] * mt
ans = sum / factorial(n)
print(ans)

Measured memory_bytes: 3064
N,L = map(int,input().split())
A = list(map(int,input().split()))

last = 0
for i in range(N-1):
  if A[i] + A[i+1] >= L:
    last = i+1
    break
if last == 0:
  print('Impossible')
else:
  print('Possible')
  for i in range(1,last):
    print(i)
  for i in range(N-1,last-1,-1):
    print(i)


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

int bubbleSort(int A[], int N) {
  int sw = 0;
  bool flag = 1;
  for ( int i = 0; flag; i++ ) {
    flag = 0;
    for ( int j = N - 1; j >= i + 1; j-- ) {
      if ( A[j] < A[j - 1] ) {
        swap(A[j], A[j - 1]);
        flag = 1;
        sw++;
      }
    }
  }
  return sw;
}

int main() {
  int A[100], N, sw;

  cin >> N;
  for ( int i = 0; i < N; i++ ) cin >> A[i];

  sw = bubbleSort(A, N);

  for ( int i = 0; i < N; i++ ) {
    if (i) cout << " ";
    cout << A[i];
  }
  cout << endl;
  cout << sw << endl;

  return 0;
}

Measured memory_bytes: 3064
#! /usr/bin/ruby -w
# encoding: utf-8
#

class Array
  def disp
    sep = ""
    self.each do |e|
      print sep
      print e
      sep = " "
    end
    puts
  end
end

if $0 == __FILE__
  n = gets.to_i
  g = []
  n.times {
    row = Array.new(n, 0)
    info = gets.split.map(&:to_i)
    outdegree = info[1]
    outdegree.times do |t|
      adj = info[t + 2]
      row[adj - 1] = 1
    end
    g << row
  }
  g.each { |row| row.disp }
end



Measured memory_bytes: 6972