akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int N,K;
	cin>>N>>K;
	vector<bool> snuke(N,false);
	rep(i,K){
		int d; cin>>d;
		rep(i,d){
			int t; cin>>t;
			--t;
			snuke[t] = true;
		}
	}
	int ans = 0;
	rep(i,N)if(snuke[i] == false)ans ++;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3628
<?php
    fscanf(STDIN,"%d %d %d %d", $a, $b, $c, $d);
    $ac = abs($a - $c);
    $ab = abs($a - $b);
    $bc = abs($b - $c);
    if($ac <= $d){
      echo 'Yes';
    }elseif($ac > $d && $ab <= $d && $bc <= $d){
      echo 'Yes';
    }else{
      echo 'No';
    } 
    
  ?>

Measured memory_bytes: 4604
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
 
template <class T> using V = vector<T>;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
 
 
#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(b);i>(ll)(a);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) __lcm(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
 
 
ll sum(ll n) {
  ll m=0;
  FOR(i,0,12){
    m+=n%10;
    n/=10;
  }
  return m;
}
 
 
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  st s;
  	ci(s);
  ll ans=0;
  FOR(i,0,4){
    if(s[i]=='-'){
      ans--;
    }
    else{
      ans++;
    }
  }
  co(ans)
    
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int M = 2e5 + 50;
int a[M];
int main(){
	int n,q,k;
	scanf("%d%d%d",&n,&k,&q);
	for(int i = 0; i < q; i++){
		int d;
		scanf("%d",&d);
		a[d]++;
	}
	for(int i = 1; i <= n; i++){
		if(k-(q-a[i]) > 0)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}


Measured memory_bytes: 1024
N = int(input())
m = []
for i in range(N):
  x,y = map(int,input().split())
  m.append((x,y))

dp = [ [0]*N for _ in range(N) ]
for i in range(N):
  dp[i][i] = 0

for L in range(1,N): 
  for i in range(N-L): 
    j = i+L
    dp[i][j] = float('inf')
    for k in range(i,j):
      m0,m1,m2 = m[i],m[k],m[j]
      # print(i,j,k,m0,m1,m2)
      dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+m0[0]*m1[1]*m2[1])

print(dp[0][-1])



Measured memory_bytes: 5720
#[macro_use]
mod input {

use std;
use std::io;

const SPLIT_DELIMITER: char = ' ';

#[macro_export]
#[allow(unused_macros)]
macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

#[allow(dead_code)]
pub fn input_line_str() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
pub fn p<T>(t: T)
where
    T: std::fmt::Display,
{
    println!("{}", t);
}

#[allow(dead_code)]
pub fn input_vector2d<T>(line: usize) -> Vec<Vec<T>>
where
    T: std::str::FromStr,
{
    let mut v: Vec<Vec<T>> = Vec::new();

    for _ in 0..line {
        let vec_line = input_vector();
        v.push(vec_line);
    }
    v
}

#[allow(dead_code)]
pub fn input_vector<T>() -> Vec<T>
where
    T: std::str::FromStr,
{
    let mut v: Vec<T> = Vec::new();

    let s = input_line_str();
    let split_result = s.split(SPLIT_DELIMITER);
    for z in split_result {
        let buf = match z.parse() {
            Ok(r) => r,
            Err(_) => panic!("Parse Error"),
        };
        v.push(buf);
    }
    v
}

#[allow(dead_code)]
pub fn str2vec(s: &str) -> Vec<char> {
    let mut v: Vec<char> = Vec::new();
    for c in s.chars() {
        v.push(c);
    }
    v
}
}

use input::*;

fn main() {
    let mut s = str2vec(&input_line_str());
    if s.len() == 3 {
        s.reverse();
    }
    for z in s {
        print!("{}", z);
    }
    println!("");
}

Measured memory_bytes: 4352
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(a,b) (a > b) ? a : b
#define MIN(a,b) (a < b) ? a : b
const int inf = 1000000000; // 10^9

int main(){
   char s[100000];scanf("%s",s);
   
   for(int i = 0;i < 'z'-'a'+1;i++){
      int flag = 0;
      for(int j = 0;j < strlen(s);j++){
         if(s[j] == 'a'+ i)flag = 1;
      }
      if(flag==0){
         printf("%c",'a'+i);
         return 0;
      }
   }
   printf("None\n");
}


Measured memory_bytes: 256
defmodule Main do
  def main do
    list = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)
    k = IO.read(:line) |> String.trim() |> String.to_integer()

    solve(list, k)
    |> IO.puts()
  end

  @doc ~S"""
  https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_b

  ## Examples

      iex> MSolutions2020B.solve([7, 2, 5], 3)
      "Yes"
      iex> MSolutions2020B.solve([7, 4, 2], 3)
      "No"

  """
  def solve([r, g, b], _) when g > r and b > g, do: "Yes"

  def solve(list, k) do
    1..k
    |> Enum.reduce_while([list], fn _i, acc_list_of_lists ->
      list_of_lists =
        acc_list_of_lists
        |> Enum.flat_map(fn [a, b, c] ->
          [[2 * a, b, c], [a, 2 * b, c], [a, b, 2 * c]]
        end)

      empty? =
        list_of_lists
        |> Enum.filter(fn [r, g, b] -> g > r && b > g end)
        |> Enum.empty?()

      if empty?, do: {:cont, list_of_lists}, else: {:halt, "Yes"}
    end)
    |> (fn result -> if is_list(result), do: "No", else: result end).()
  end
end

Measured memory_bytes: 30664
#include <stdio.h>

int main() {
    long long int n, s = 0;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        if ((i % 3) == 0 || (i % 5) == 0) {
            s = s;
        } else {
            s += i;
        }
    }
    printf("%lld", s);
}

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

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n;i >= 0;--i)
#define FOR(i, a, b) for(int i = a;i < b;++i)
#define ALL(x) (x).begin(),(x).end()
#define INF 999999999
using namespace std;
#define lint long long

int main()
{
  int N = 3;
  int out =0;
  //cin >> N;
  string S;
  cin >> S;
  vector<int> a(N);
  FOR(i,1,N){
    if(S[i-1] != S[i]){
      out = 1;
    }
  }
  if(out) cout << "Yes";
  else cout << "No";
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#define pb push_back
#define ll long long
#define mp make_pair
#define rep(i,n) for(int i=0;i<n;i++)
#define re return
#define fi first
#define se second
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(),(x).end()
#define sqr ((x)*(x))
#define y0 y3487465
#define y1 y8687969
using namespace std;
int a,b; 
int main(){
	cin>>a>>b;
	if(a+b==15) 
   	cout<<"+";
	else if(a*b==15) 
   	cout<<"*";
	else if(a+b!=15&&a*b!=15) 
   	cout<<"x";
system ("pause");
return 0;
}



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

# define rep(i, n) for(int(i)=0;(i)<(n);(i)++)
# define reps(i, n) for(int(i)=1;(i)<=(n);(i)++)
# define rrep(i, n) for(int i=((int)(n)); i>0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>=0; --i)
# define ALL(v) v.begin(), v.end()
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<typename T> void dump(T e){std::cout << e << std::endl;}
template<typename T> void dump(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void dump(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ dump(v); } }
template <typename T>
void dump_stack(std::stack<T>& stack) {
  std::stack<T> temp;
  while (!stack.empty()) {
    T top = stack.top(); stack.pop();
    std::cout << top << " ";
    temp.push(top);
  }
  std::cout << endl;
  while (!temp.empty()) {
    T top = temp.top(); temp.pop();
    stack.push(top);
  }
}
template <typename T>
void dump_queue(std::queue<T>& queue) {
  std::queue<T> temp;
  while (!queue.empty()) {
    T top = queue.front(); queue.pop();
    std::cout << top << " ";
    temp.push(top);
  }
  std::cout << endl;
  while (!temp.empty()) {
    T top = temp.front(); temp.pop();
    queue.push(top);
  }
}

typedef long long ll;




int main(){
  int n; cin >>n;
  map<string, int> mp;
  string op,v;
  rep(i,n) {
    cin >> op >> v;
    if(op=="insert") {
      mp[v] = 1;
    } else {
      if(mp[v]==1) {
        cout << "yes" << endl;
      } else {
        cout << "no" << endl;
      }
    }
  }
//  for (auto t : mp)
//    cout << t.first << " " << t.second << " " << endl;
}



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

int main(){
    int x;
    cin >> x;
    
    if(x >= 400 && x <= 599) cout << 8 << endl;
    if(x >= 600 && x <= 799) cout << 7 << endl;
    if(x >= 800 && x <= 999) cout << 6 << endl;
    if(x >= 1000 && x <= 1199) cout << 5 << endl;
    if(x >= 1200 && x <= 1399) cout << 4 << endl;
    if(x >= 1400 && x <= 1599) cout << 3 << endl;
    if(x >= 1600 && x <= 1799) cout << 2 << endl;
    if(x >= 1800 && x <= 1999) cout << 1 << endl;
}

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

int main() {
  int w, a, b;
  cin >> w >> a >> b;
  if (a < b) {
    if (b < a + w) cout << 0 << '\n';
    else cout << b - a - w << '\n';
  } else if (a > b) {
    if (a < b + w) cout << 0 << '\n';
    else cout << a - b - w << '\n';
  } else {
    cout << 0 << '\n';
  }
  return 0;
}


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

int main() {
  string s;cin>>s;
  int cnt=0;
  rep(i,s.size()){
    cnt+=s[i]-'0';
  }
  if(cnt%9==0)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<string>> vvs;
typedef vector<vector<char>> vvc;
typedef vector<vector<bool>> vvb;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define vrep(v,n) for(int i=0;i<n;i++){cin >> v.at(i);} 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repn(i, n) for (int i = 0; i <= (int)(n); i++)
#define srep(i, l, n) for (int i = l; i < (int)(n); i++)
#define srepn(i, l, n) for (int i = l; i <= (int)(n); i++)
#define pb push_back 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int mod = 1000000007;
const int inf = 1e9;
#define PI 3.14159265369;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};

int main(){
	int n, k;
	cin >> n >> k;
	for(int i = k-n+1; i <=k+n-1; i++){
		cout << i  << " ";
	}
}

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

int main(){

  long long n, a, b, ma=0, mi=1000000000;

  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a>>b;
    ma=max(ma, a);
    mi=min(mi, b);
  }

  cout<<ma+mi<<endl;

  return 0;
}


Measured memory_bytes: 256
from heapq import heapify, heappop, heappush

N=int(input())
V=[int(v) for v in input().split()]
V.sort()
heapify(V)

for _ in range(N-1):
  heappush(V, (heappop(V)+heappop(V))/2)

print(heappop(V))

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <cmath>
#include <climits>
#include <cstdint>
#include <map>
#include <string>
using namespace std;

inline namespace atcoder {
    using i32 = int32_t; using u32 = uint32_t;
    using i64 = int64_t; using u64 = uint64_t;
    using f32 = float; using f64 = double;

    template <typename T, size_t Depth>
    struct vector_helper { using type = vector<typename vector_helper<T, Depth - 1>::type>; };
    template <typename T>
    struct vector_helper<T, 0> { using type = T; };
    template <typename T, size_t Depth>
    using vector_t = typename vector_helper<T, Depth>::type;

    template <typename T> using vec = vector_t<T, 1>;
    template <typename T> using vvec = vector_t<T, 2>;
    template <typename T> using vvvec = vector_t<T, 3>;
}

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

    map<string, int> counter;
    while (n--) {
        string s; cin >> s;
        ++counter[s];
    }

    int l = 0;
    for (const auto &[k, v] : counter) {
        l = max(l, v);
    }

    for (const auto &[k, v] : counter) {
        if (v == l) {
            cout << k << endl;
        }
    }
}



Measured memory_bytes: 19208
from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

n,m,k = map(int,input().split())
tree = UnionFind(n)
len_group = [0] * (n+1)
num_friend = [0] * (n+1)
num_block_sametree = [0] * (n+1)
root_ls = [0] * (n+1)
# 友達だったらブロックじゃない

for i in range(m):
    a,b = map(int,input().split())
    tree.union(a,b)
    num_friend[a] += 1
    num_friend[b] += 1
for i in range(k):
    c,d = map(int,input().split())
    if tree.same_check(c,d):
        num_block_sametree[c] += 1
        num_block_sametree[d] += 1
# 根を格納するハッシュ
for node in range(1,n+1):
    root = tree.find(node)
    root_ls[node] = root
    len_group[root] += 1

ans_ls = [0] * (n+1)
for node in range(1,n+1):
    root = root_ls[node]
    ans_ls[node] = len_group[root] - 1 - num_friend[node] - num_block_sametree[node]
ans_ls = list(map(str, ans_ls))
print(' '.join(ans_ls[1:]))
    






Measured memory_bytes: 21816
#include <bits/stdc++.h>
#include<math.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define INF 2000000000
#define Min(a,b) (a<b?a:b)
#define Max(a,b) (a>b?a:b)
#define PI 3.1415926535897932
using namespace std;






int main()
{
string s,t;
cin>>s>>t;
int n,m; 
n=s.size(); m=t.size();
int dp[n+1][m+1];
for(int i=0 ; i<=m; i++){
	dp[0][i]=0;
}
for(int i=0 ; i<=n; i++){
	dp[i][0]=0;
}
for(int i=1; i<=n;i++){
	for(int j=1; j<=m;j++){
		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]);
	}
}

int i=n; int j=m;
string ans="";
while(i>=1 && j>=1){

	if(dp[i][j]!=dp[i][j-1] && dp[i][j]!=dp[i-1][j]){
		ans+=s[i-1];
		i--;
		j--;
	}
	else if(dp[i][j]==dp[i-1][j])
	{
		i--;
	}
	else
	{
		j--;
	}
}


reverse(ans.begin(),ans.end());
cout<<ans;
return 0;

}



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

int main() {
  int n;
  vector<int> d;
  int count=0;
  int non_count=0;
  int result=0;
  int chuo=0;
  
  cin>>n;
  for(int i=0;i<n;i++){
    int b;
    cin>>b;
    d.push_back(b);
  }
  
  
  sort(d.begin(),d.end());
  
  chuo=(d.size())/2;
  cout<<d.at(chuo)-d.at(chuo-1)<<endl;
  
}


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

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    int a,b; cin >> a >> b;
    cout << (a>b?a-1:a) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  string s;
  cin>>s;
  vector<int>v;
  v.push_back(0);
  int x=0;
  for(int i=0;i<n;i++)
  {
    if(s[i]=='I')
    {
      x+=1;
    }
    else{
      x-=1;
    }
    v.push_back(x);
  }
  sort(v.begin(), v.end());
  cout<<v[v.size()-1];
}  


Measured memory_bytes: 3592
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <bitset>

using namespace std;

int main()
{
    unsigned int x, y;
    cin >> x >> y;

    bitset<32> a(x), b(y);

    cout << (a & b) << endl;
    cout << (a | b) << endl;
    cout << (a ^ b) << endl;

}


Measured memory_bytes: 3140
package main

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

var sc = bufio.NewScanner((os.Stdin))

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	l := nextLine()
	i, e := strconv.Atoi(l)
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	N, A, B := nextInt(), nextInt(), nextInt()

	fmt.Printf("%d\n", ABC083B(N, A, B))
}

// ABC083B ...
func ABC083B(N, A, B int) int {
	res := 0

	for n := 1; n <= N; n++ {
		s := 0
		for tmp := n; tmp != 0; tmp /= 10 {
			s += tmp % 10
			if s > B {
				break
			}
		}

		if A <= s && s <= B {
			res += n
		}
	}

	return res
}


Measured memory_bytes: 1772
// Walk and Teleport
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n,a,b;
LL x[100000];

int main(){
    cin>>n>>a>>b;
    LL ans=0;
    for(LL i=0;i<n;i++) cin>>x[i];
    for(LL i=0;i<n-1;i++){
        ans+=min(a*(x[i+1]-x[i]),b);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
from sys import setrecursionlimit
setrecursionlimit(1<<30)
mod=pow(10,9)+7
def f(x,p):
  if z[x][0]==-1:
    z[x][0]=z[x][1]=1
    for y in v[x]:
      if y!=p:
        f(y,x)
      	z[x][0]=(z[x][0]*z[y][1])%mod
        z[x][1]=(z[x][1]*(z[y][0]+z[y][1]))%mod
n=int(input())
v=[[] for _ in range(n)]
for x,y in [map(int,raw_input().split()) for _ in range(n-1)]:
  v[x-1].append(y-1)
  v[y-1].append(x-1)
z=[[-1,-1] for _ in range(n)]
f(0,-1)
print sum(z[0])%mod

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

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

using namespace std;
using lint=long long;

class union_find{
	int n;
	vector<int> p;
public:
	union_find(int n):n(n),p(n,-1){}
	int find(int u){ return p[u]<0?u:p[u]=find(p[u]); }
	void unite(int u,int v){
		u=find(u); v=find(v);
		if(u!=v){
			if(p[v]<p[u]) swap(u,v);
			p[u]+=p[v]; p[v]=u; n--;
		}
	}
	bool is_same(int u,int v){ return find(u)==find(v); }
	int size()const{ return n; }
	int size(int u){ return -p[find(u)]; }
};

int main(){
	int n,m; scanf("%d%d",&n,&m);
	union_find U(n);
	rep(i,m){
		int u,v; scanf("%d%d",&u,&v); u--; v--;
		U.unite(u,v);
	}

	lint k=min(U.size(0),U.size(1));
	printf("%lld\n",k*(k-1)/2+(n-k)*(n-k-1)/2-m);

	return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
#include<string.h>

int main(){
int a,b,c;
char x;
  char Sa[100],Sb[100],Sc[100];
  scanf("%s",Sa);
  scanf("%s",Sb);
  scanf("%s",Sc);
  a = strlen(Sa);
  b = strlen(Sb);
  c = strlen(Sc);
  x = Sa[0];
  a--;
  while(1){
    if(a == -1 || b == -1 || c == -1){
      break;
    }
    if(x == 'a'){
      if(a > 0){
        x = Sa[strlen(Sa)-a];
      }a--;
  }
    if(x == 'b'){
      if(b > 0){
        x = Sb[strlen(Sb)-b];
      }
      b--;
  }
    if(x == 'c'){
     if(c > 0){
       x = Sc[strlen(Sc)-c];
     }
      c--;
  }
  }
  if(a == -1){
    printf("A");
  }
  if(b == -1){
    printf("B");
  }
  if(c == -1){
    printf("C");
  }
  return 0;
}

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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(int i = x ; i < n ; ++i)
#define rep(i, n) for(int i = 0 ; i < n ; ++i)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; --i)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort((x).begin(), (x).end())

const int IINF = 1e9 + 10;
const long long LLINF = (long long)1e18 + 10;
const long long MOD = (long long)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

vector< vector<int> > g;
set<int> st;
vector<bool> done;
bool flag = false;
int loops = -1;

void dfs(int now, int prev){
    done[now] = true;
    rep(i, g[now].size()){
        if(g[now][i] != prev){
            if(done[g[now][i]] && !st.count(g[now][i])){
                flag = true;
                st.insert(now);
                st.insert(g[now][i]);
                loops = g[now][i];
            }else if(!st.count(g[now][i])){
                dfs(g[now][i], now);
                if(now == loops){
                    flag = false;
                }
                if(flag){
                    st.insert(now);
                }
            }
            if(flag){
                break;
            }
        }
    }
    return;
}

int main(){
    int n;
    cin >> n;
    g.resize(n);
    done.resize(n);
    rep(i, n){
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(0, -1);
    int q;
    cin >> q;
    rep(i, q){
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        if(st.count(a) && st.count(b)){
            cout << 2 << endl;
        }else{
            cout << 1 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 17668
// https://atcoder.jp/contests/abc099/tasks/abc099_a
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

void solve() {
  ll N;
  cin >> N;
  string res;

  if (N >= 1000) {
    res = "ABD";
  } else {
    res = "ABC";
  }

  cout << res << endl;
}

#ifndef TEST
int main() {
 	cin.tie(0);
 	ios::sync_with_stdio(false);
  solve();
  return 0;
}
#endif


Measured memory_bytes: 256
def main():
    md = 10 ** 9 + 7
    n = int(input())
    s = input()
    a = [c == "B" for c in s]
    B = True
    W = False
    a = [b if i % 2 else not b for i, b in enumerate(a)]
    if sum(a) != n:
        print(0)
        exit()
    ans = 1
    cnt_W = 0
    for b in a:
        if b == W:
            cnt_W += 1
        else:
            ans = (ans * cnt_W) % md
            cnt_W -= 1
            if ans == 0:
                print(0)
                exit()
    fac_n = 1
    for i in range(1, n + 1):
        fac_n = (fac_n * i) % md
    print((ans * fac_n) % md)

main()


Measured memory_bytes: 6756
#include <iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<limits.h>

#define MOD 1000000007


using namespace std;

long long int modpow(long long int a, int n) {

	if (n == 0)return 1;
	if (n == 1) return a;

	long long int wk = modpow(a, n / 2);

	long long int ret = 0;
	if (n % 2 == 0) {
		ret = 1;
	}
	else {
		ret = a;
	}

	return (((ret * wk) % MOD) * wk) % MOD;

}

long long int gcd(long long int a, long long int b) {
	long long int tmp;
	if (a < b) {
		tmp = a;
		a = b;
		b = tmp;
	}

	long long int r = a % b;

	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}

	return b;
}

long long int lcm(long long int a, long long int b) {

	long long int wk_int;

	wk_int = (a * b) % MOD;
	
	long long int ret;

	ret = (wk_int * modpow(gcd(a, b), MOD - 2)) % MOD;

	return ret;

}

bool isPrime(int n) {
	if (n == 1)return false;
	if (n == 2)return true;

	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}

	return true;
}








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

	vector<int> p(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}

	int ans = 0;
	int tmp;
	for (int i = 0; i < n - 1; i++) {
		if (p[i] == i + 1) {
			ans++;
			tmp = p[i];
			p[i] = p[i + 1];
			p[i + 1] = tmp;
		}
	}

	if (p[n - 1] == n)ans++;



	cout << ans << endl;

	return 0;

}



Measured memory_bytes: 640
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-9;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

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

	cin >> N >> M >> K;
	vector<int>cost(N);
	vector<vector<int>>box(N, vector<int>(M));
	for (int i = 0; i < N; i++) {
		cin >> cost[i];
		for (auto &j : box[i])cin >> j;
	}
	int ans = MOD;
	for (int i = 0; i < 1 << N; i++) {
		int c = 0;
		vector<int>num(M);
		for (int j = 0; j < N; j++) {
			if ((i >> j) & 1) {
				c += cost[j];
				for (int k = 0; k < M; k++) {
					num[k] += box[j][k];
				}
			}
		}
		if (*min_element(num.begin(), num.end()) >= K) {
			ans = min(ans, c);
		}
	}
	if (ans == MOD)ans = -1;
	cout << ans << endl;
}

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

int main(){
    int A,B,C;
    cin>>A>>B>>C;
    if((A==B&&(A!=C||B!=C))||(B==C&&(B!=A||C!=A))||(A==C&&(B!=A||B!=C))){
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
    return 0;
}

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


#define rep(i, s, c) for (int i = s; i < c; i++)
#define rep_neg(i, c) for (int i = c - 1; i > -1; i--)
#define MOD 1000000000 + 7



int main(){
    int N;
    cin >> N;
    int A[N];
    int sum_a = 0;
    rep(i, 0, N){
        cin >> A[i];
        sum_a += A[i];
    }
    int X[N];
    X[0] = sum_a / 2;
    rep(i, 0, N) if (i % 2 == 1) X[0] -= A[i];

    rep(i, 1, N) X[i] = A[i - 1] - X[i - 1];
    rep(i, 0, N) cout << 2 * X[i] << " ";
}

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;

  if ((A+B) > (C+D)) {
    cout << "Left" << endl;
  }
  
  else if ((A+B) == (C+D)) {
    cout << "Balanced" << endl;
  }
  
  else if ((A+B) < (C+D)) {
    cout << "Right" << endl;
  }
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define DEBUG if(0)
#define lli long long int
#define ldouble long double
using namespace std;

const int maxN = 1e6;
bool notPrime[maxN + 1];
vector<int> primes;
vector<pair<lli, int>> primeFactors[maxN + 1];

vector<pair<lli, int>> getPrimeFactors(lli num)
{
  if (num <= maxN) return primeFactors[num];
  vector<pair<lli, int>> pf;
  for (lli i: primes)
  {
    if (i > num) break;
    if (num % i == 0)
    {
      int p = 0;
      while (num % i == 0) num /= i, p ++;
      pf.push_back({i, p});
    }
  }
  if (num != 1)
    pf.push_back({num, 1});
  return pf;
}

int n;

lli allComb(vector<pair<lli, int>> &pf, int i = 0)
{
  if (i == pf.size()) return 1;

  lli all = allComb(pf, i + 1);
  all += allComb(pf, i + 1) * pf[i].second;

  return all;
}

int main()
{
  notPrime[0] = notPrime[1] = true;
  for (int i = 2; i <= maxN; i ++)
  {
    if (!notPrime[i]) primes.push_back(i), primeFactors[i].push_back({i, 1});
    for (int j = 0; i*primes[j] <= maxN; j ++)
    {
      notPrime[i*primes[j]] = true;
      int p = 0, num = i * primes[j];
      while (num % primes[j] == 0) num /= primes[j], p ++;
      primeFactors[i * primes[j]].push_back({primes[j], p});
      primeFactors[i * primes[j]].insert(primeFactors[i * primes[j]].end(), primeFactors[num].begin(), primeFactors[num].end());
      if (i % primes[j] == 0) break;
    }
  }

  while (scanf("%d", &n) != EOF)
  {
    lli ans = 1;
    for (int i = 1; i < n - 1; i++)
    {
      int nn = n - i;
      vector<pair<lli, int>> pf = getPrimeFactors(nn);
      ans += allComb(pf);
    }
    printf("%lld\n", ans);
  }
  
  return 0;
}

Measured memory_bytes: 88420
#abc044 b
s=input()
moji=dict()
flag=True
for i in s:
    if i not in moji:
        moji[i]=1
    else:
        moji[i]+=1

for i in moji.values():
    if i%2==1:
        flag=False
        break
print("Yes" if flag else "No")

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

int main(){
  int a, b;
  cin >> a >> b;
 
  int n=1;
  int i;
  for(i=1; i<=20; i++){
    if(b==1){
      i = 0;
      break;
    }
    n += a - 1;
    if(n>=b) break;
  }
  
  cout << i << endl;
  return 0;
}

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

using namespace std;

int main() {
  int N;
  string S;
  cin >> N >> S;

  vector<int> E(N),W(N);
  for (int i = 0; i != N-1; ++i) {
    if (S[i]=='E') {
      E[i+1] = E[i];
    } else {
      E[i+1] = E[i]+1;
    }
    if (S[N-i-1]=='W') {
      W[N-i-2] = W[N-i-1];
    } else {
      W[N-i-2] = W[N-i-1]+1;
    }
  }

  int ans {N};
  for (int i = 0; i !=N; ++i) {
    ans = min(ans,E[i]+W[i]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 6168
import java.util.Scanner;

public class Main {
  static boolean[] generatePrimes() {
    boolean[] isPrime = new boolean[1000001];
    for (int i = 0; i <= 1000000; i++)
      isPrime[i] = true;

    for (int i = 2; i <= 1000000; i++)
      if (isPrime[i] == true)
        for (int j = 2*i; j <= 1000000; j += i)
          isPrime[j] = false;

    return isPrime;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    boolean[] isPrime = generatePrimes();

    while (true) {
      int n = sc.nextInt();
      int x = sc.nextInt();
      if (n == 0 && x == 0)
        return;

      int[] dishes = new int[n];
      for (int i = 0; i < n; i++) {
        dishes[i] = sc.nextInt();
      }

      boolean[] dp = new boolean[x+1];
      dp[0] = true;

      // total payment table->
      for (int i = 0; i <= x; i++) {
        // each dish
        for (int j = 0; j < n; j++) {
          if (dp[i] == true && i+dishes[j] <= x) {
            dp[i+dishes[j]] = true;
          }
        }
      }

      int ans = 0;
      for (int i = 0; i <= x; i++) {
        if (isPrime[i] && dp[i])
          ans = i;
      }
      if (ans == 0)
        System.out.println("NA");
      else
        System.out.println(ans);
    }
  }
}

Measured memory_bytes: 59480
#include "bits/stdc++.h"
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define mFOR(i, a, b) for (int i = a; i > b; i--)
#define MP make_pair
#define PB push_back
#define ALL(v) v.begin(), v.end()
#define N 100007
#define INF 1000000007
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll fceil(ll a, ll b) { return (a % b == 0 ? a / b : a / b + 1); }
int main()
{
   int a, b, ans;
   cin >> a >> b;
   cout << (a > 9 || b > 9 ? -1 : a * b) << endl;
   return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<iostream>
#include<cmath>
#include<math.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
const double PI=M_PI;
signed main(){
    ll n,m;cin>>n>>m;
    vector<vector<ll> >G(n);
    rep(i,m){
        ll a,b;cin>>a>>b;
        a--;b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    vector<ll>visited(n);
    vector<ll>ans(n);
    queue<ll>q;
    q.push(0);
    visited[0]=1;
    while(!q.empty()){
        ll k=q.front();
        q.pop();
        for(auto e:G[k]){
            if(visited[e])continue;
            visited[e]=1;
            q.push(e);
            ans[e]=k;
        }
    }
    cout<<"Yes"<<endl;
    REP(i,1,n){
        cout<<ans[i]+1<<endl;
    }
}

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(n);
    rep(i,n) {
        cin >> a[i] >> b[i];
    }
    vector<PP> ab(n);
    rep(i,n) {
        ab[i] = make_pair(a[i], b[i]);
    }
    sort(ab.begin(), ab.end());

    ll cost = 0;
    rep(i,n) {
        int buy = min(m, ab[i].second);
        cost += (ll)buy * ab[i].first;
        m -= buy;
    }
    cout << cost << endl;

    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

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

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

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

  int n;
  while(cin >> n){
    vector<int> a(n); cin >> a;

    vector<int> l(n+1);
    REP(i,n) l[i+1] = max(l[i], a[i]);

    reverse(ALL(a));
    vector<int> r(n+1);
    REP(i,n) r[i+1] = max(r[i], a[i]);

    REP(i,n){
      int ans = max(l[i], r[n-i-1]);

      cout << ans << "\n";
    }
  }
  
  
  return 0;
}


Measured memory_bytes: 3968
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define Graph vector<vector<ll>>
#define INF (1ll<<60)
#define mod 1000000007

void pre_process(vector<ll> &a,vector<ll> &s){//累積和のvector
    ll n=(ll)a.size();
    s.assign(n+1,0);
    for(ll i=0;i<n;i++){
        s[i+1]=s[i]+a[i];
    }
}
ll query(ll i,ll j,vector<ll> &s){//区間[i,j]の和
    return (s[j]-s[i]);
}

int main(){
    ll h,w,k;cin>>h>>w>>k;
    vector<string> choco(h);
    Graph choco_num(h,vector<ll>(w,0));
    Graph choco_sum(h,vector<ll>());//累積和
    
    rep(i,h) cin>>choco[i];//割って'1'の数をk以下にする

    rep(i,h){
        rep(j,w) if(choco[i][j]=='1') choco_num[i][j]=1;
    }

    rep(i,h){
        pre_process(choco_num[i],choco_sum[i]);
    }

    //縦は全部割るパターン試せる
    ll num=(1<<(h-1)),ans=INF;
    rep(i,num){
        ll cnt=0,key=0,cant=0;
        rep(j,w+1){
            if(cant>=w) break;   
        
            ll tate=0,white=0,MAX=0;
            rep(tate,h){
                if((i>>tate)&1 || tate==h-1){
                    white+=query(key,j,choco_sum[tate]);
                    MAX=max(MAX,white);

                    if(MAX>k){
                        key=j-1;
                        j--;
                        cant++;
                        cnt++;
                        break;
                    }
                    white=0;
                }else{
                    white+=query(key,j,choco_sum[tate]);
                }
                
            }
        }

        if(cant<w) ans=min(ans,cnt+__builtin_popcount(i));
    }

    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3792
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,k,x,y;

int main(){
  ll ans=0;
  cin >> n ;
  vi a(n);
  REP(i,n) cin>>a[i];

  ll myno=1;
  REP(i,n){
    if (a[i]==myno){
      myno++;
    }
  }


  if (myno!=1){
    cout<<n-myno+1<<endl;
  }else{
    cout<<-1<<endl;
  }
  return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int x = sc.nextInt();

        int answer = 0;

        for (int gohyaku=0; gohyaku <= a; gohyaku++){
            if(gohyaku * 500 == x){
                answer++;
                break;
            }else if (gohyaku * 500 > x){
                break;
            }

            for(int hyaku=0; hyaku <= b; hyaku++){
                if (gohyaku * 500 + hyaku * 100 == x){
                    answer++;
                    break;
                }
                else if (gohyaku * 500 + hyaku * 100 > x){
                    break;
                }

                for (int gozyu = 0; gozyu <= c; gozyu++){
                    // 合計値比較
                    if (gohyaku * 500 + hyaku * 100 + gozyu * 50 == x){
                        answer++;
                        break;
                    }
                }
            }
        }

        System.out.println(answer);


    }
}


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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

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

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

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

    vector<pair<int,int>> a(N);

    int max_a = -1;
    REP(i,N){
        cin >> a[i].second;
        chmax(max_a,a[i].second);
    }

    REP(i,N){
        a[i].first = min(max_a-a[i].second,a[i].second);
        a[i].second *= -1;
    }

    sort(all(a),greater<>());


    cout << max_a << " " << a[0].second*-1 << endl;

    return 0;
}


Measured memory_bytes: 1024
import sys
INFTY=sys.maxsize
#INFTY=2*10**7+1

def readinput():
    nv,ne=list(map(int,input().split()))
    nMap=[]
    for i in range(nv):
        l=[]
        for _ in range(nv):
            l.append(INFTY)
        nMap.append(l)
        nMap[i][i]=0
    for _ in range(ne):
        s,t,d=list(map(int,input().split()))
        nMap[s][t]=d
    return nv,ne,nMap

def warshalFloyd(nv, nMap):
    for k in range(nv):
        for i in range(nv):
            if(nMap[i][k]==INFTY):
                continue
            for j in range(nv):
                if(nMap[k][j]==INFTY):
                    continue
                nMap[i][j] = min(nMap[i][j], nMap[i][k]+nMap[k][j])
    return nMap

def main(nv,ne,nMap):
    nMap=warshalFloyd(nv,nMap)
    #print(nMap)
    isNegative=False
    for i in range(nv):
        if nMap[i][i]<0:
            isNegative=True
    if isNegative==True:
        print('NEGATIVE CYCLE')
    else:
        for i in range(nv):
            for j in range(nv):
                #print(nMap[i][j],INFTY, nMap[i][j]==INFTY)
                if(nMap[i][j]==INFTY):
                    print('INF',end='')
                else:
                    print(nMap[i][j], end='')
                if j==nv-1:
                    print('')
                else:
                    print(' ',end='')
                        

if __name__=='__main__':
    nv,ne,nMap=readinput()
    #print(nMap)
    main(nv,ne,nMap)





Measured memory_bytes: 6816
# 2019-11-12 15:53:47(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    nm, *lines = sys.stdin.readlines()
    n, m = [int(x) for x in nm.split()]
    likes = [[int(x) for x in line.split()] for line in lines]
    menu = set(range(1, m+1))
    res = menu
    for i in range(n):
        res &= set(likes[i][1:])
    
    print(len(res))

if __name__ == "__main__":
    main()


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

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#define dumpv(...)
#endif

#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n + 1);
  a[0] = 0;
  rep(i, n) cin >> a[i + 1];
  dump(n, a);
  map<int, int> mp;
  function<int(int)> check = [&](int k) {
    dump(k);
    mp.clear();
    for (int i = 1; i <= n; i++) {
      // if (i == 1) mp[a[i] - 1] = 0;
      if (a[i - 1] < a[i]) {
        // 何もしない
      } else {
        auto it = mp.lower_bound(a[i]);
        // auto it = mp.upper_bound(a[i] - 1);
        mp.erase(it, mp.end());
        int j = a[i] - 1;
        if (k == 1) {
          j = -1;
        } else {
          while (mp[j] + 1 >= k) {
            mp[j] = 0;
            j--;
          }
        }
        if (0 <= j) {
          mp[j] += 1;
        } else {
          dump("false", mp);
          return false;
        }
      }
      dump(mp);
    }
    return true;
  };
  int ans = 0;
  // index=0が条件を満たすこともあるので、leftの初期値は-1
  int left = 0;
  // index=a.size()-1が条件を満たさないこともあるので、rightの初期値はa.size()
  int right = n;
  while (right - left > 1) {
    int mid = left + (right - left) / 2;
    if (check(mid))
      right = mid; // 例えば(key<=a[mid])など
    else
      left = mid;
  }
  // leftは条件を満たさない最大の値、rightは条件を満たす最小の値になっている
  ans = right;
  dump(ans);
  cout << ans << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  // freopen("temp.1", "r", stdin);
  solve();
  return 0;
}

Measured memory_bytes: 1152