akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#define ll long long int
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define PI 3.141592653589793
using namespace std;

int main() {
    int N,M;

    cin >> N >> M;
    int p, ACnum=0,WA[N],WAnum=0;
    string s;
    bool AC[N];

    REP(i,N) {
        AC[i] = false;
        WA[i] = 0;
    }

    REP(i,M){
        cin >> p >> s;
        if(AC[p-1]) continue;
        if(s == "AC") {
            AC[p-1] = true;
            ACnum++;
            WAnum += WA[p-1];
        } else if(s == "WA") {
            WA[p-1]++;
        }
    }

    cout << ACnum << " " << WAnum << endl;

    return 0;
}

Measured memory_bytes: 768
from bisect import bisect_left, bisect_right

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())
if N == 1:
  print(0)
  exit()
Fact = factorization(N) 

Counter=[1]
for i in range(2,10):
  Counter.append(Counter[-1]+i)


ans = 0
tmp = 0
for i in range(len(Fact)):
  tmp = Fact[i][1]
  ans += bisect_right(Counter, tmp)

print(ans)

Measured memory_bytes: 9508
#include <iostream>

using namespace std;

int main() {
	string s;
	char c;
	while (getline(cin, s)) {
		for (int i = 0; i < 26; i++) {
			if (s.find("the", 0) != string::npos ||
				s.find("this", 0) != string::npos ||
				s.find("that", 0) != string::npos) {
				cout << s << endl;
				break;
			}
			for (int j = 0; j < s.size(); j++) {
				c = s[j];
				if (!isalpha(c))
					continue;
				if (isalpha(c+1)) {
					s[j] = ++c;
				} else {
					s[j] = 'a';
				}
			}
		}
	}
	return 0;
}

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

struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) (1 + (int)((a) - 1)/(int)(b))
#define int long long

signed main() {
    int n; cin >> n;
    string ans = "Three";
    rep(i,n){
        char c; cin >> c;
        if(c=='Y') ans = "Four";
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.File;
import java.util.Scanner;

public class Main extends BaseExe {

    public static void main(String[] args) {
        new Main().exeSysIn();
    }

    @Override
    protected void execute(Scanner scan) {
        int[] num = new int[51];
        for (int a = 0; a <= 9; a++)
            for (int b = 0; b <= 9; b++)
                for (int c = 0; c <= 9; c++)
                    for (int d = 0; d <= 9; d++)
                        num[a + b + c + d]++;
        String ln = "";
        while (scan.hasNextLine() && !"".equals(ln = scan.nextLine()))
            System.out.println(num[Integer.parseInt(ln)]);
    }

}

abstract class BaseExe {

    public void exeSysIn() {
        try (Scanner scan = new Scanner(System.in)) {
            execute(scan);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public void exeFileIn(String inDataPath) {
        try (Scanner scan = new Scanner(new File(inDataPath))) {
            execute(scan);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    protected abstract void execute(Scanner scan);
}

Measured memory_bytes: 26384
#include<iostream>
using namespace std;
long long a[200010],b[200010];
int main()
{
    string a;
    int i;
    while(getline(cin,a))
    {
        cout<<a[0];
        for(i=1;a[i]!='\0';i++)
        {
            if(a[i]==' ') cout<<a[i+1];
        }
        cout<<endl;
    }
    return 0;
}


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

int n;
vector<int> a;

int main() {
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int x = *max_element(a.begin(), a.end());
    int y = -1;
    for (int i = 0; i < n; i++) {
        if (a[i] == x) continue;
        if (min(a[i], x - a[i]) > min(y, x - y)) {
            y = a[i];
        }
    }
    cout << x << " " << y << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
template<typename T> auto compare = [](T x, T y) -> bool{return (x < y);};
const int MOD = 1000000007;

ll m[200010];

signed main(){
    string S;
    cin >> S;
    int N = S.length();
    ll t = 10;
    reverse(ALL(S));
    map<ll, ll> mp;
    m[0] = S[0] - '0';
    mp[m[0]]++;
    FOR(i, 1, N){
        m[i] = ((m[i - 1]) + t * (S[i] - '0')) % 2019;
        t = (t * 10) % 2019;
        mp[m[i]]++;
    }
    ll ans = mp[0];
    for(auto p : mp){
        ans += p.second * (p.second - 1) / 2;
    }
    PRINT(ans);
    return 0;
}

Measured memory_bytes: 5284
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
#define rep(n, i) for(ll i = 0; i < n; ++i)
 
void solve(void) {
  ll N, M, X; cin >> N >> M >> X;
 
  vector<ll> price(N, 0);
  vector<vector<ll>> textbook(N, vector<ll>(M, 0));
  for(ll i = 0; i < N; ++i) {
    cin >> price[i];
    for(ll j = 0; j < M; ++j) cin >> textbook[i][j];
  }
 
  ll res = 10000000;
  for(ll bit = 0; bit < (1 << N); ++bit) {
 
    ll cost = 0;
    vector<ll> exp(M, 0);
    ll count = 0;
    for(ll i = 0; i < N; ++i) {
      if(bit & (1 << i)) {
        cost += price[i];
        for(ll j = 0; j < M; ++j) exp[j] += textbook[i][j];
      }
    } 
    for(ll mi = 0; mi < M; ++mi) {
      if (exp[mi] >= X) count++;
    }
    if(count == M) res = min(res, cost); 
  }
 
 
  if (res < 10000000) cout << res << endl;
  else cout << "-1" << endl;
}
 
int main(void) {
  solve();
  return 0;
}

Measured memory_bytes: 3604
#include<stdio.h>
int main(){
    int s,s1,s2,s3,i=0;
    scanf("%d",&s);
    s1=s%10;
    s=s/10;
    s2=s%10;
    s3=s/10;
    if(s1==1){
        i++;
    }
    if(s2==1){
        i++;
    }
    if(s3==1){
        i++;
    }
    printf("%d\n",i);
    return 0;
}


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

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

typedef vector<LL> Col;
typedef vector<Col> Matrix;
Matrix mul(const Matrix& A, const Matrix& B){
  const int R = A.size(), C = B[0].size(), sz = B.size();
  Matrix AB(R, Col(C));

  for(int i=0;i<R;++i)
    for(int j=0;j<C;++j)
      for(int k=0;k<sz;++k)
		(AB[i][j] += A[i][k] * B[k][j]) %= MOD;

  return AB;
}

// O(N^3 lgN)
Matrix powA(const Matrix& A, int n){
  const int N = A.size();
  Matrix p(N, Col(N, 0)), w = A;
  for(int i=0;i<N;++i) p[i][i] = 1;

  while(n>0){
	if(n&1)
	  p = mul(p, w);
	w = mul(w, w);
	n >>= 1;
  }

  return p;
}

void dump(const Matrix& A){
  REP(i,SZ(A)){
	REP(j,SZ(A[i]))
	  cout << A[i][j] << (j%5==4?" | ":" ");
	cout << endl;
	if(i%5==4)cout<<string(SZ(A)+20,'-')<<endl;
  }
}

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

  int N, K, C, T; cin >> N >> K >> C >> T;
  --C;
  VI as(K), bs(K), ts(K);
  Matrix A(5*N, Col(5*N));
  REP(i,N) REP(t,4)
	A[5*i+t][5*i+t+1]++;

  REP(i,K){
	cin >> as[i] >> bs[i] >> ts[i];
	--as[i];
	--ts[i];
	for(int k=0;k<bs[i];++k)
	  A[k*5+ts[i]][(as[i]+k)*5]++;
	for(int k=0;k<as[i];++k)
	  A[(bs[i]+k)*5+ts[i]][k*5]++;
	for(int k=as[i]+bs[i];k<N;++k)
	  A[5*k+ts[i]][5*k]++;
  }

  A = powA(A, T);
  cout << A[0][5*C] << endl;
  
  return 0;
}

Measured memory_bytes: 4168
program xor_sum_4
  implicit none
  integer(8), parameter :: md = 1000000007_8
  integer :: n, c(0:60) = 0, i, j
  integer(8) :: a(300000) = 0_8, s = 0_8, k
  read(*,*) n
  read(*,*) a(1:n)
  do i = 1, n
    s = mod(s+a(i),md)
    do j = 0, 60
      if (btest(a(i),j)) c(j) = c(j)+1
    end do
  end do
  s = mod(int(n,8)*s,md)
  do j = 0, 60
    k = mod(int(c(j),8)*int(c(j),8),md)
    s = modulo(s-k*mod(2_8**j,md),md)
  end do
  write(*,'(i0)') s
end program xor_sum_4

Measured memory_bytes: 3200
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
#include <map>
#include <queue>
#include <cctype>
using namespace std;
using ll = long long;
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[100001];
//char str[1010][1010];
//typedef pair<ll,ll> A;
//vector<A> pc;
//int ABS(int a){return max(a,-a);}
ll a[100000];
ll dom[100001];
 
ll gcd(ll a,ll b){
  if(b==0) return a;
  return gcd(b,a%b);
}

int main(){
  string s;
  int n;
  cin>>n;
  cin>>s;
  ll ans=0;
  int memo1[10]={0};
  for(int i=0;i<n;i++){
    char p[3];
    int memo2[10]={0};
    p[0]=s[i];
    if(memo1[p[0]-'0']==1) continue;
    memo1[p[0]-'0']++;
    //for(int q=0;q<10;q++) cout<<memo1[q];
    for(int j=i+1;j<n;j++){
      int memo3[10]={0};
      p[1]=s[j];
      //if(p[0]==p[1]) continue;
      if(memo2[p[1]-'0']==1) continue;
      memo2[p[1]-'0']++;
      //cout<<p[0]<<p[1]<<endl;
      for(int k=j+1;k<n;k++){
        p[2]=s[k];
        //if(p[2]==p[1]||p[2]==p[0]) continue;
        if(memo3[p[2]-'0']==1) continue;
        memo3[p[2]-'0']++;
        ans++;
      }
    }
    //cout<<endl;
  }
  cout<<ans;
  return 0;
}

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

using namespace std;
const int N = 1000005;

int n, a, b;

void init(){
	scanf("%d%d%d",&n,&a,&b);
	if(a > b){
		puts("0");
		return;
	}
	if(n == 1 and a != b){
		puts("0");
		return;
	}
	if(n == 1){
		puts("1");
		return;
	}
	long long mini = (long long) (n - 1) * a + b;
	long long maxi = (long long) (n - 1) * b + a;
	cout << maxi - mini + 1 << endl;
}

int main(){
	
	init();
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

    int H = scanner.nextInt();
    int W = scanner.nextInt();
    char[][] map = new char[H][W];
    for (int i = 0; i < H; i++) map[i] = scanner.next().toCharArray();
    int[][] dp = new int[H][W];
    dp[0][0] = map[0][0] == '#' ? 1 : 0;
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        if (i == 0 && j == 0) continue;
        int cost1;
        int cost2;
        if (i > 0) {
          cost1 = dp[i - 1][j];
          if (map[i - 1][j] == '.' && map[i][j] == '#') cost1++;
        } else {
          cost1 = 100000;
        }
        if (j > 0) {
          cost2 = dp[i][j - 1];
          if (map[i][j - 1] == '.' && map[i][j] == '#') cost2++;
        } else {
          cost2 = 100000;
        }
        dp[i][j] = Math.min(cost1, cost2);
      }
    }
    System.out.println(dp[H - 1][W - 1]);
  }
}


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

int main() {
	int n; int ans = 0;
	vector<int> value;
	vector<int> cost;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int v; cin >> v;
		value.push_back(v);
	}

	for (int i = 0; i < n; i++) {
		int c; cin >> c;
		cost.push_back(c);
	}

	for (int i = 0; i < n; i++) {
		int new_ans = ans + value[i] - cost[i];
		ans = max(ans, new_ans);
	}

	cout << ans;
	return 0;
}

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

int main(){
	const int MAX=100000;
	int n,a[MAX];
	int b=0,count=0;
	bool flag[MAX];
	
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<MAX;i++)flag[i]=false;
	flag[0]=true;
	while(!flag[1]){
		count++;
		if(flag[a[b]-1]){
			cout<<"-1"<<endl;
			return 0;
		}
		flag[a[b]-1]=true;
		b=a[b]-1;
	}
	cout<<count<<endl;
}

Measured memory_bytes: 768
import bisect

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

s=[-2*10**10]+[int(input()) for _ in range(a)]+[2*10**10]
t=[-2*10**10]+[int(input()) for _ in range(b)]+[2*10**10]
x=[int(input()) for _ in range(q)]

for i in range(q):
  j = bisect.bisect_left(s,x[i])
  al = x[i] - s[j-1]
  ar = s[j] - x[i]
  j = bisect.bisect_left(t,x[i])
  bl = x[i] - t[j-1]
  br = t[j] - x[i]
  l = min(max(al, bl), max(ar, br), 2*al+br, 2*ar+bl, 2*bl+ar, 2*br+al)
  print(l)


Measured memory_bytes: 16132
# ALDS1_4_B.pys

def is_ok(idx,key,target):
########## wirte criteria here ##########
    if target[idx] >= key:
        return True
    return False

def meguru_bisect(key,target):
    left = -1
    right = len(target)
    while (abs(right - left) > 1):
        mid = left + (right - left) // 2
        if is_ok(mid,key,target):
            right = mid
        else:
            left = mid
    if key == target[right]:
        return True
    return False

N = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))
ans = 0
for i in T:
    if meguru_bisect(i,S):
        ans += 1
print(ans)



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

int main()
{
	long long input;
	long long first = 0;
	long long second = 0;
	long long third = 0;
	
	for (int i = 0; i < 10; i++)
	{
		cin >> input;
		// Update the tallest 3 mountains
		if (input > first)
		{
			third = second;
			second = first;
			first = input;	
		}
		else if (input > second)
		{
			third = second;
			second = input;
		}
		else if (input > third)
			third = input;
	}
	
	cout << first << endl << second << endl << third << endl;
}

Measured memory_bytes: 1156
N,M = map(int,input().split())
students = [list(map(int,input().split()))for i in range(N)]
checkPoints = [list(map(int,input().split()))for i in range(M)]

for i in range(N):
    idx = -1
    mindis = 3*10**8
    sx,sy = students[i]
    for j in range(M):
        cx,cy = checkPoints[j]
        distance = abs(sx-cx)+ abs(sy-cy)
        if mindis > distance:
            idx = j+1
            mindis = distance
    print(idx)



Measured memory_bytes: 67804
import re

def gcd(x, y):
    if x == y:
        return x
    if x < y and y % x == 0:
        return x
    if x > y and x % y == 0:
        return y
    if x <= y:
        m = y % x
        return gcd(x, m)
    if x >= y:
        m = x % y
        return gcd(y, m)

    l = list(range(1, int(min(x, y) / 2) + 1))
    l.reverse()
    r = 1
    #for i in range(1, int(min(x, y) / 2) + 1):
    for i in l:
        if x % i == 0 and y % i == 0:
            return i
    return 1
 
x, y = map(int, re.split(' ', raw_input()))
print(gcd(x, y))

Measured memory_bytes: 6404
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
vector<int> c(26);
vector<vector<int>> s(365, vector<int>(26, 0));
vector<int> last(26, -1);
int main() {
    int d;
    cin >> d;
    for(int i = 0; i < 26; i++) {
        cin >> c[i];
    }
    for(int i = 0; i < d; i++) {
        for(int j = 0; j < 26; j++) {
            cin >> s[i][j];
        }
    }
    vector<int> t(d, -1);
    int score = 0;
    for(int i = 0; i < d; i++) {
        for(int j = 0; j < 26; j++) {
            score -= c[j] * (i - last[j]);
        }
        int ind = -1;
        int tmp = score;
        for(int k = 0; k < 26; k++) {
            if(tmp < score + s[i][k] + c[k] * (i - last[k])) {
                ind = k;
                tmp = tmp + s[i][k] + c[k] * (i - last[k]);
            }
        }
        t[i] = ind;
        last[t[i]] = i;
        score += s[i][t[i]];
    }
    for(int i = 0; i < d; i++) {
        cout << t[i] + 1 << endl;
    }
}

Measured memory_bytes: 3676
# -*- coding: utf-8 -*-
n,a,b,c,d = map(int, input().split())

def check(m):
    return c*(n-1-m)-d*m<=b-a<=-1*c*m+(n-1-m)*d

for m in range(n):
    if check(m):
        print("YES")
        exit()
print("NO")


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

int main(){

    string s;
    cin >> s;
    int sum = 700;
    if(s[0] == 'o') sum += 100;
    if(s[1] == 'o') sum += 100;
    if(s[2] == 'o') sum += 100;
    cout << sum << endl;
}

Measured memory_bytes: 3596
/*
Date: 2017/02/25 19:33:09 Saturday
*/
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define rep(i,a,n) for(int i=(a);i<=(n);++i)
#define dep(i,a,n) for(int i=(a);i>=(n);--i)
#define eps 1e-8
#define pi 3.1415926535897
#define sqr(x) ((x)*(x))
#define MAX(a,b) a=max(a,b)
#define MIN(a,b) a=min(a,b)
#define SZ(x) ((int)(x).size())
#define CPY(a,b) memcpy(a,b,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define POSIN(x,y) (1<=(x)&&(x)<=n&&1<=(y)&&(y)<=m)
#define all(x) (x).begin(),(x).end()
#define COUT(S,x) cout<<fixed<<setprecision(x)<<S<<endl
#define buli(x) (__builtin_popcountll(x))
#define bur0(x) (__builtin_ctzll(x))
#define bul2(x) (63-__builtin_clzll(x))
#define pw(x) ((ll(1))<<(x))
#define upmo(a,b) (((a)=((a)+(b))%mo)<0?(a)+=mo:(a))
#define mmo(a,b) (((a)=1ll*(a)*(b)%mo)<0?(a)+=mo:(a))
#define y0 y0z
#define y1 y1z
#define yn ynz
#define j0 j0z
#define j1 j1z
#define jn jnz
#define tm tmz
#ifdef LOCAL
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 
#endif
typedef long long ll;
typedef double lf;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<lf,lf> pff;
typedef complex<double> CD;
const int inf=0x3f3f3f3f;
const int mo=1000000007;
inline void gn(long long&x){
	int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');c=='-'?(sg=-1,x=0):(x=c-'0');
	while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';x*=sg;
}
inline void gn(int&x){long long t;gn(t);x=t;}
inline void gn(unsigned long long&x){long long t;gn(t);x=t;}
inline void gn(double&x){double t;scanf("%lf",&t);x=t;}
inline void gn(long double&x){double t;scanf("%lf",&t);x=t;}
template<class T1,class T2>inline void gn(T1&r,T2&s){gn(r),gn(s);}
template<class T1,class T2,class T3>inline void gn(T1&r,T2&s,T3&t){gn(r),gn(s),gn(t);}
template<class T1,class T2,class T3,class T4>inline void gn(T1&r,T2&s,T3&t,T4&u){gn(r),gn(s),gn(t),gn(u);}
inline void gs(char *s){scanf("%s",s);}
inline void gc(char &c){while((c=getchar())>126 || c<33);}
inline void pc(char c){putchar(c);}
const int DX[]={1,0,-1,0},DY[]={0,1,0,-1};
ll powmod(ll a,ll b) {ll res=1;a%=mo;for(;b;b>>=1){if(b&1)res=res*a%mo;a=a*a%mo;}return res;}
ll powmod(ll a,ll b,ll mo) {ll res=1;a%=mo;for(;b;b>>=1){if(b&1)res=res*a%mo;a=a*a%mo;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
//*******************************************

const int N=1111111,M=111111;
int l,m,n,t,C;
int a[N],c[N],d[N];
int main(){
#ifdef LOCAL
	freopen("A.in","r",stdin);//freopen("A.out","w",stdout);
#endif
	scanf("%d",&n);
	rep(i,1,n){scanf("%d",&a[i]);}
	rep(i,1,n)c[i]=max(0,i-1-((a[i-1])+1)/2)+1,c[i]=max(c[i],c[i-1]),d[c[i]]++;
	ll ans=1,p=0;
	rep(i,1,n){
		p+=d[i];
		//printf("%d %lld\n",i,p);
		ans=ans*p%mo;
		--p;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 4480
N,ma,mb = map(int,raw_input().split())

a=[]
b=[]
c=[]
for i in range(N):
	at,bt,ct=map(int,raw_input().split())

	a.append(at)
	b.append(bt)
	c.append(ct)
	

dp = [[[10**10 for i in range(400+1)] for j in range(400+1)] for k in range(N+1)]
dp[0][0][0]=0
for i in range(N):
	for j in range(401):
		for k in range(401):
			if(dp[i][j][k]<10**10):
				dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k])
				dp[i+1][j+a[i]][k+b[i]]=min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i])

ans=10**10

for i in range(1,401):
	for j in range(1,401):
		if i*mb==j*ma:
			ans=min(ans,dp[N][i][j])

if ans>=10**10:
	print -1
else:
	print ans
				


Measured memory_bytes: 60548
#include<stdio.h>
#include<string.h>
#include<queue>
#include<map>
#include<limits.h>
int main()
{
	int h,w,i,j,x,y,ax,ay,gx,gy,d[22][22],r,f,dx[]={1,0,-1,0,0},dy[]={0,1,0,-1,0};
	char m[22][22],g[15],*p;
	while(scanf("%d%d",&h,&w),h)
	{
		for(i=1;i<=h;++i)
		{
			scanf("%s",m[i]+1);
			if(p=strchr(m[i]+1,'A'))ax=p-m[i],ay=i;
			if(p=strchr(m[i]+1,'B'))gx=p-m[i],gy=i;
		}
		scanf("%s",g);

		for(i=0;i<h+1;++i)m[i][0]=m[i][w+1]='#';
		for(j=0;j<w+1;++j)m[0][j]=m[h+1][j]='#';
		//Aツつゥツづァツづ個催短ツ仰猟猟」ツづーツ出ツつキ
		for(i=0;i<22;++i)for(j=0;j<22;++j)d[j][i]=INT_MAX;
		typedef std::pair<int,int>P;
		std::queue<P>q;
		P _;
		q.push(P(ax,ay));
		q.push(P(-1,-1));
		r=0;
		while(q.size()>1)
		{
			_=q.front();q.pop();
			if(_.first<0){++r;q.push(_);continue;}
			if(m[_.second][_.first]=='#')continue;
			if(d[_.second][_.first]<=r)continue;
			d[_.second][_.first] = r;
			for(i=0;i<4;++i)q.push(P(_.first+dy[i],_.second+dx[i]));
		}int lx=-1,ly=-1;r=1;
		f=0;
		for(;;)
		{
			if(lx==gx && ly==gy && !f)
			{
				puts("impossible");
				goto E;
			}
			lx=gx;ly=gy;
			for(f=i=0;i<strlen(g);++i,++r)
			{
				int t[]={4,4,1,4,2,4,0,4,3};
				x=gx+dx[t[g[i]-'0']];
				y=gy+dy[t[g[i]-'0']];
				if(x>0&&x<=w&&y>0&&y<=h)gx=x,gy=y;
				if(d[gy][gx]!=INT_MAX)f=1;if(d[gy][gx]<=r)
				{
					printf("%d %d %d\n",r,gy-1,gx-1);
					goto E;
				}
			}
		}
E:;
	}
	return 0;
}

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

int main(){
    int n;
    cin>>n;
    ll ma=0;
    ll sum=0;
    rep(i,n){
        ll x;cin>>x;
        sum+=x;
        ma=max(ma,x);
    }
    cout<<sum-ma/2<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine(); //次の1行を読み取る
		int n = str.length();
		char[] c = str.toCharArray();

		for(int i = 0; i < n; i++) {
			if(65 <= (int)c[i] && (int)c[i] <= 90) {  //大文字の場合
				System.out.print((char)((int)c[i] + 32));
			}
			else if(97 <= (int)c[i] && (int)c[i] <= 122) {  //小文字の場合
				System.out.print((char)((int)c[i] - 32));
			}
			else System.out.print(c[i]);
		}
		System.out.println();
	}
}


Measured memory_bytes: 26924
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;



int main(){
	while (1) {
		int h, w;
		cin >> h >> w;
		if (h == 0 && w == 0)break;
		for (int i = 0; i < w; i++) {
			cout << '#';
		}
		cout << endl;
		for (int i = 0; i < h - 2; i++) {
			cout << '#';
			for (int i = 0; i < w - 2; i++) {
				cout << ".";
			}
			cout << '#' << endl;
		}
		for (int i = 0; i < w; i++) {
			cout << '#';
		}
		cout << endl;
		cout << endl;
	}
}


Measured memory_bytes: 3068
a, b = map(int, input().split())

def func2(m):
    n=m+1
    if n%4==0:
        return 0
    if n%2==0:
        return 1
    elif (n+1)%4 ==0:
        return n
    else:
        return n-1

def func(a,b):
    return func2(a-1) ^ func2(b)

print(func(a,b))

Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
#define INF 1e10
#define MOD 1e9+7
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; }
using Graph = vector<vector<int>>;
int fg(int k){
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}
signed main(){
  int a;
  string b;
  cin>>a>>b;
  int x=0;
  int y=0;
  int z=0;
  rep(i,a){
    if(b.at(i)=='R'){
      x++;
    }
    if(b.at(i)=='G'){
      y++;
    }
    if(b.at(i)=='B'){
      z++;
    }
  }
  int sum=x*y*z;
    rep1(j,(a-3)/2+1){
      for(int k=0;k<a-j*2;k++){
        if(b.at(k)!=b.at(k+j)&&b.at(k)!=b.at(k+j*2)&&b.at(k+j)!=b.at(k+j*2)){
          sum--;
      }
    }
  }
   cout<<sum; 
}


Measured memory_bytes: 3604
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
#include <cassert>
//#include <numeric>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;



void solve()
{
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);

    int i;
    for (i = 0; i < 1000; i++) {
        c -= b;
        if (c <= 0) {
            printf("Yes\n"); return;
        }
        a -= d;
        if (a <= 0) {
            printf("No\n"); return;
        }
    }

    return;
}

int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}



Measured memory_bytes: 1644
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)
#define delete _delete

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 1e6;
const ll mod = 1e9 + 7;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T> void vout(T s){cout << s << endl;exit(0);}

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

    ll n;
    cin >> n;

    multiset <ll> s;

    ll ans = 0;

    vector <ll> a(n + 1);

    for(int i = 1; i <= n; i++)cin >> a[i];

    for(int i = 1; i <= n; i++){
        if(s.empty() || *s.begin() >= a[i]){
            ans++;
            s.insert(a[i]);
        }else{
            ll val = *--s.lower_bound(a[i]);
            s.erase(s.find(val));
            s.insert(a[i]);
        }
    }

    cout << ans << "\n";

    cerr << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec" << endl;
    return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
    using namespace std;
    int main() {
     int n=0;
      cin >> n;
     vector<int> data(n);
     for(int i=0; i<n; i++){
      cin >> data.at(i); 
     }

      long ans = 0;
      int max = data.at(0);
      for(int i=1; i<n; i++){
        if(max < data.at(i)){
         max = data.at(i); 
        }else{
         ans += max-data.at(i); 
        }
      }
      
      cout << ans << endl;
    }

Measured memory_bytes: 3928
import sys
n = int(input())
c = 0
for i in range(n):
    d = list(map(int, input().split()))
    if d[0] == d[1]:
        c = c + 1
        if c >= 3:
            print('Yes')
            sys.exit()
    else:
        c = 0
if c >= 3:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 62328
#include<bits/stdc++.h>
using namespace std;
 
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,a,b)    for(int i=a;i<b;i++)
#define repn(i,a,b)   for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define vvi vector<vector<int>>;
#define mi  map<int,int>
#define mii map<pii,int>
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define sz(x) (int)x.size()
#define all(v) (v).begin(), (v).end()
#define ret(x) return cout<<x,0;
#define rety return cout<<"YES",0;
#define retn return cout<<"NO",0;
#define fl fflush(stdout)   
#define hell 1000000007  
#define hell2 998244353 
#define pi 3.14159265358979323846

int solve(){
    string s,t;
    cin>>s>>t;
    int n=sz(s),m=sz(t);
    int dp[n+1][m+1];
    memset(dp,0,sizeof dp);
    rep(i,1,n+1){
        rep(j,1,m+1){
            if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    /*rep(i,0,n+1){
        rep(j,0,m+1)cout<<dp[i][j]<<" ";
        cout<<"\n";
    }*/
    string v;int i=n,j=m;
    while(i>0&&j>0){
        if(dp[i][j]==dp[i-1][j])i--;
        else if(dp[i][j]==dp[i][j-1])j--;
        else{v.pb(s[i-1]);i--;j--;}
    }
    reverse(all(v));
    cout<<v;
    return 0;
}

signed main(){
    IOS;
    int t=1;
  
    //cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
} 

Measured memory_bytes: 73992
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename T,T MOD = 1000000007>
struct Mint{
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(int k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }
  
  Mint inv(){return pow(MOD-2);}
  
  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}
  
  Mint operator+(Mint a) const{return Mint(v)+=a;};
  Mint operator-(Mint a) const{return Mint(v)-=a;};
  Mint operator*(Mint a) const{return Mint(v)*=a;};
  Mint operator/(Mint a) const{return Mint(v)/=a;};

  Mint operator-(){return v?MOD-v:v;}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}

};

//INSERT ABOVE HERE
using M = Mint<int>;
const int MAX = 3030;
M dp[2][2][MAX];
signed main(){
  int n,m;
  cin>>n>>m;
  auto fl=[&](int f){
            for(int k=0;k<MAX;k++)
              dp[f][0][k]=dp[f][1][k]=M(0);
          };
  fl(0);fl(1);
  for(int k=0;k<=n;k++) dp[0][k==0][k]=M(1);

  for(int i=0;i<m;i++){
    int f=i&1;
    fl(!f);
    for(int j=0;j<2;j++){
      for(int k=0;k<=n;k++){
        int l=n-k;
        if(k){
          dp[!f][j||(k-1==0)][k-1]+=dp[f][j][k];//RR
          dp[!f][j||(k-1==0)][k-0]+=dp[f][j][k];//RB
        }
        if(l){
          dp[!f][j][k+0]+=dp[f][j][k];//BR
          dp[!f][j][k+1]+=dp[f][j][k];//BB
        }
      }
    }
  }
  
  M ans(0);
  for(int k=0;k<=n;k++) ans+=dp[m&1][1][k];
  cout<<ans.v<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    // input
    static int n;
    static int[] h;

    /**
     * input
     */
    static void input(){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        h = new int[n];
        for (int i=0;i<n;i++){
            h[i] = sc.nextInt();
        }
        sc.close();
    }
 
    /**
     * solver
     */
    static void solve(){
        int ans = 0;
        int maxHeight = 0;
        for(int i=0;i<n;i++){
            if (h[i]>=maxHeight) {
                maxHeight = h[i];
                ans++;
            }
        }
        System.out.println(ans);
    }

    public static void main(String args[]) {

        input();

        solve();
    }
}


Measured memory_bytes: 23508
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>


#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long
//#define lint long long

const int INF = 1e18;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで

using namespace std;

//typedef pair<int, int> P;
//priority_queue< P, vector<P>, greater<P> > q;//ダイクストラの時、greaterで小さい順
int s[20000];
int t[20000];

int dp[3000][3000];
int sum[3000][3000];
int now[200000];
signed main(){
  int n,m;
  cin >> n >> m;
  FOR(i,n){
    int k;
    cin >> k;
    s[i] = k;
  }
  FOR(i,m){
    int k;
    cin >> k;
    t[i] = k;
  }
  dp[0][0] = 1;
  sum[0][0] = 1;
  FOR(i,n) sum[i][0] = 1;
  FOR(i,m) sum[0][i] = 1;
  FOR(i,n){
    FOR(j,m){
      if(s[i]==t[j]) dp[i][j] = sum[i-1][j-1];
      dp[i][j] %= MOD;
      sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + dp[i][j];
    }
  }
  int ans = 0;
  REP(i,n+1){
    REP(j,m+1){
      ans += dp[i][j];
      ans %= MOD;
      //cout << i << " " << j << " " << dp[i][j] << " " <<  sum[i][j] <<endl;
    }
  }
  cout << ans <<endl;
  return 0;
}


Measured memory_bytes: 94848
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include <queue>
using namespace std;
#define lowbit(x) (x&(-x))
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
bool cmp(int x,int y)
{
    return x>y;
}
const int N=10005;
const int mod=1e9+7;
int a[10];
int prim(int n)
{
    int b,flag=1;
    while(n){
        b=n%10;
        if(a[b]){
            flag=0;
            break;
        }
        n/=10;
    }
    if(flag) return 1;
    return 0;
}
int main()
{
    std::ios::sync_with_stdio(false);
    int n,k,s,t;
    cin>>n>>k;
    mem(a);
    for(int i=0;i<k;i++){
        cin>>t;
        a[t]=1;
    }
    for(int i=n; ;i++){
        if(prim(i)){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 256
import math
x=[int(input()) for i in range(5)]
y=[i%10 for i in x]
#print(y)
ans=0
for i in range(5):
    ans+=math.ceil(x[i]/10)*10
#print(ans)
check=10
for i in range(5):
    if y[i]!=0:
        check=min(check,y[i])
if check==10:
    print(ans)
else:
    print(ans-(10-check))


Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<list>
#include<deque>
#include<cmath>
#include<unordered_map>
#include<unordered_set>
#include<numeric>

using namespace std;

using ll = int64_t;

/// <summary>
/// 単純なcoutの時に使う
/// </summary>
#define co(a) cout<<a<<"\n"


/// <summary>
/// [beg, end)の範囲を，添え字indexでループするfor文に置換します
/// </summary>
#define rep(i,a) for(ll i=0; i<a; ++i)
#define reps(i, a, b) for(ll i = a; i < b; ++i)

/// <summary>
/// 迷路等で使う方向のベクトル
/// </summary>
const vector<ll> dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };

/// <summary>
/// デバッグ時に使う
/// </summary>
#define DEBUG(x)     std::cout << #x << " : " << x << "\n"

///////////////////////////////////////////////////////////////////////////


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

	ll N;
	cin >> N;

	vector<ll> A (N);
	
	rep (i, N) {
		cin >> A[i];
	}

	ll m = 0, m2 = 0;

	for (ll i = 1;i < N; ++i) {
		if (A[i] > A[m]) {
			m2 = m;
			m = i;
		}
		else if (A[i] > A[m2]) {
			m2 = i;
		}
	}

	if (m == 0) {
		m2 = 1;
		for (ll i = 1; i < N; ++i) {
			if (A[i] > A[m2]) {
				m2 = i;
			}
		}
	}

	ll ans1 = A[m], ans2 = A[m2];

	rep (count, N) {
		if (count == m) {
			cout << ans2 << endl;
		}
		else {
			cout << ans1 << endl;
		}
	}
}


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

int main(){
  long long L,R; cin>>L>>R;
  
  if (R-L>2019) cout<<0<<endl;
  else{
    long long ans=2018;
    for (long long i=L;i<R;++i)
      for (long long j=i+1;j<=R;++j)
        ans = min(ans,(i*j)%2019);
    cout<<ans<<endl;
  }
}
  

Measured memory_bytes: 256
from math import sqrt

while True:
    n = int(input().strip())    
    if n == 0:
        break    
    scores = list(map(float, input().strip().split()))
    sum1 = 0 
    for i in scores:
        sum1 += i
    heikin = sum1 * 1 / n
    sum2 = 0
    for i in scores:
        sum2 += (i - heikin) ** 2
    a = sqrt(sum2 / n)
    print(a)
    

    



Measured memory_bytes: 5768
using System;
using System.Linq;

namespace Atcoder
{
    class Program
    {
        public static void Main(string[] args)
        {
            long[] input = Console.ReadLine().Split(" ").Select(i=>long.Parse(i)).ToArray();
            if (4 * input[0] - input[1] >= 0 && ((4 * input[0] - input[1]) % 2) == 0 && (4 * input[0] - input[1] <= 2 * input[0]))  
                Console.Write("Yes");
            else
                Console.Write("No");
        }
    }
}


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

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)
#define forall(it, c) for (__typeof(c.begin()) it = c.begin(); it != c.end(); ++ it)

template <typename T> inline void read(T &x) {
	x = 0; bool f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	for (;  isdigit(c); c = getchar()) x = x * 10 + (c & 15);
	if (!f) x = -x;
}

const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
int n;
ll a[maxn], b[maxn];
map <pair <ll, ll>, int> cnt;
set <vector <pair <ll, ll> > > used;
int pw[maxn];

int main() {
	rep(i, maxn) pw[i] = i ? 2LL * pw[i - 1] % mod : 1;
	read(n);
	rep(i, n) read(a[i]), read(b[i]);
	rep(i, n) {
		ll g = __gcd(abs(a[i]), abs(b[i]));
		if (g) a[i] /= g, b[i] /= g;
		++ cnt[mp(a[i], b[i])];
	}
	int ans = 1;
	forall(it, cnt) {
		pair <ll, ll> p = it->first;
		if (p.first == 0 && p.second == 0) continue;
		pair <ll, ll> p1 = mp(p.second, -p.first);
		pair <ll, ll> p2 = mp(-p.second, p.first);
		pair <ll, ll> p3 = mp(-p.first, -p.second);
		vector <pair <ll, ll> > xx;
		xx.pb(p); xx.pb(p1); xx.pb(p2); xx.pb(p3);
		sort(xx.begin(), xx.end());
		if (used.find(xx) == used.end()) used.insert(xx);
		else continue;
		vector <int> v;
		if (cnt.find(p) == cnt.end()) v.pb(0); else v.pb(cnt[p]);
		if (cnt.find(p3) == cnt.end()) v.pb(0); else v.pb(cnt[p3]);
		if (cnt.find(p1) == cnt.end()) v.pb(0); else v.pb(cnt[p1]);
		if (cnt.find(p2) == cnt.end()) v.pb(0); else v.pb(cnt[p2]);
		int tot = 0;
		rep(mask, 1 << 4) {
			bool ok = 1;
			rep(a, 2) rep(b, 2)
				ok &= !((mask >> a & 1) && (mask >> (b | 2) & 1));
			if (ok) {
				int cur = 1;
				rep(x, 4) if (mask >> x & 1) {
					cur = 1LL * (pw[v[x]] + mod - 1) * cur % mod;
				}
				(tot += cur) %= mod;
			}
		}
		ans = 1LL * ans * tot % mod;
	}
	(ans = ans + cnt[mp(0, 0)]) %= mod;
	printf("%d\n", (ans + mod - 1) % mod);
	return 0;
}


Measured memory_bytes: 48264
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define maxn 200010
using namespace std;
int n,k,a[maxn];
bool cmp(int c,int b)
{
	return c>b;
}
int main()
{
	scanf("%d%d",&n,&k);
	int v;
	for(int i=1;i<=n;++i)
	scanf("%d",&v),a[v]++;
	sort(a+1,a+maxn-10+1,cmp);
	int ans=0;
	for(int i=1;i<=k;++i)
	ans+=a[i];
	cout<<n-ans;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
 
/* data type, special numbers, defines */
//#define int ll //use if ded
#define ll long long
#define ld long double
const ll inf=LLONG_MAX;
//const ll mod=1e9+7;
const ll mod=998244353;
const ld pi=acos(-1.0);
#define all(v) v.begin(), v.end()
/* end data type and special numbers */
 
/* fast input.output */
#define gc getchar//_unlocked
#define pc putchar//_unlocked
#define endl pc('\n')
int get_i(){
	char c=gc(); bool neg=false;
	for(; c<'0'||'9'<c; c=gc())
		if(c=='-') neg=true;
	int rs=c-'0'; c=gc();
	for(; '0'<=c && c<='9'; c=gc())
		rs=(rs<<1)+(rs<<3)+(c-'0');
	if(neg) rs=-rs;
	return rs;
}
ll get_l(){
	char c=gc(); bool neg=false;
	for(; c<'0'||'9'<c; c=gc())
		if(c=='-') neg=true;
	ll rs=c-'0'; c=gc();
	for(; '0'<=c && c<='9'; c=gc())
		rs=rs*10ll+(c-'0');
	if(neg) rs=-rs;
	return rs;
}
string get_s(){
	char c=gc();
	for(; c<33 || 126<c; c=gc());
	string s=""; s+=c; c=gc();
	for(; 33<=c && c<=126; c=gc())
		s+=c;
	return s;
}
char get_c(){
	char c=gc();
	for(; c<33 || 126<c; c=gc());
	return c;
}
void print_i(int _n){
	bool neg=false; if(_n<0) {neg=true; _n=-_n;}
	if(neg) pc('-');
	int N=_n, rev, count=0;
	rev=N;
	if(N==0) {pc('0'); return;}
	while((rev%10)==0) {count++; rev/=10;}
	rev=0;
	while(N!=0) {rev=(rev<<3)+(rev<<1)+N%10; N/=10;}
	while(rev!=0) {pc(rev%10+'0'); rev/=10;}
	while(count--) pc('0');
}
void print_l(ll _n){
	ll N=_n, rev, count=0;
	rev=N;
	if(N==0) {pc('0'); return;}
	while((rev%10)==0) {count++; rev/=10;}
	rev=0;
	while(N!=0) {rev=rev*10ll+N%10; N/=10;}
	while(rev!=0) {pc(rev%10+'0'); rev/=10;}
	while(count--) pc('0');
}
void print_s(string a){
	for(int i=0; i<a.size(); i++)
		pc(a[i]);
}
#define endline pc('\n');
#define space pc(' ');
/* end fast input/output */

/*   E N D   O F   T E M P L A T E   */

bool ok(string a){
	int l=0, r=a.size()-1;
	bool yes=true;
	while(l!=a.size()-1){
		if(a[l]!=a[r]){
			yes=false; break;
		}
		l++; r--;
	}
	return yes;
}
int main(){
	string s=get_s(), a="", b="";
	for(int i=0; i<s.size(); i++){
		if(i<s.size()/2) a+=s[i];
		else if(i==s.size()/2);
		else b+=s[i];
	}
	if(ok(s) && ok(a)&& ok(b)) print_s("Yes\n");
	else print_s("No\n");
	return 0;
}


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

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

    string s, t;
    cin>>s>>t;

    int a, b;
    cin>>a>>b;

    string u;
    cin>>u;

    if (s == u)     a--;
    else            b--;
    cout<<a<<" "<<b<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<int, pii> pipii;

void solve() {
  int n;
  vector<int> a, b;
  cin >> n;
  for(int i = 0; i < n; i++) {
    a.push_back(20001 * (i+1));
    b.push_back(20001 * (i+1));
  }
  reverse(b.begin(), b.end());
  for(int i = 1; i <= n; i++) {
    int t;
    cin >> t;
    b[--t] += i;
  }
  for(int out: a) cout << out << " "; cout << "\n";
  for(int out: b) cout << out << " "; cout << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  /*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
}


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define ANS(n) cout << (n) << endl
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 m,k;
    cin >> m >> k;
    if(m == 0){
        if(k == 0){
            ANS("0 0");
        }else{
            ANS(-1);
        }
    }else if(m == 1){
        if(k == 0){
            ANS("0 0 1 1");
        }else{
            ANS(-1);
        }
    }else{
        if(pow(2,m) > k){
            REP(i,pow(2,m)){
                if(i != k)
                    cout << i << " ";
            }
            cout << k << " ";
            FORR(i,pow(2,m)-1,0){
                if(i != k)
                    cout << i << " ";
            }
            cout << k;
            cout << "\n";
        }else{
            ANS(-1);
        }
    }
    return 0;
}

Measured memory_bytes: 1792
import statistics
from bisect import bisect_left
N = int(input())
X = list(map(int,input().split()))
Y = sorted(X)
a,b = statistics.median_low(Y),statistics.median_high(Y)
for i in X:
    Z = bisect_left(Y,i)
    if Z<N//2:
        print(b)
    else:
        print(a)

Measured memory_bytes: 109528
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
typedef double db;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
#define w1 first
#define ls (x<<1)
#define w2 second
#define ins insert
#define rs (x<<1|1) 
#define mp make_pair
#define pb push_back
#define mid ((l+r)>>1)
#define sqr(x) ((x)*(x))
#define cle(x) ((x).clear())
#define lowbit(x) ((x)&(-x))
#define SZ(x) (int((x).size()))
#define ms(x,y) memset(x,y,sizeof (x))
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)]) 
#define Rep2(p,x) for(int (p)=cur[(x)];(p);(p)=nxt[(p)])
#define debegin printf("debug\nbegin\n")
#define deend printf("debug\nend\n")
#define isfind printf("find\n")
template<class T>inline void rread(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
inline int getgcd(int x,int y){if(!x)return y;return getgcd(y%x,x);}
inline int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=(ll)x*x%p)if(k&1)res=(ll)res*x%p;return res;}
const double pi=acos(-1);
inline void judge(){
	freopen("input.txt","r",stdin);
} 
//********************************head*************************************	
const int maxn=2e5+5;
int n,k,cnt;
int c[maxn];
ll q[maxn],a[maxn],ans;
void M(int x){
	for(;x<=cnt;x+=lowbit(x))c[x]++;
}
int Q(int x,int res=0){
	for(;x;x-=lowbit(x))res+=c[x];
	return res;
}
int main(){
	rread(n);rread(k);
	rep(i,1,n){
		rread(a[i]);
		a[i]=a[i]-k;
		a[i]=a[i]+a[i-1];
		q[i]=a[i];
	}
	q[n+1]=0;
	sort(q+1,q+(n+1)+1);
	cnt=unique(q+1,q+(n+1)+1)-q-1;
	M(lower_bound(q+1,q+cnt+1,0)-q);
	rep(i,1,n){
		a[i]=lower_bound(q+1,q+cnt+1,a[i])-q;
		ans+=Q(a[i]);
		M(a[i]);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 4096