akhauriyash/Code-Regression huggingface dataset:
# https://atcoder.jp/contests/abc157/submissions/10475457

import sys
readline = sys.stdin.readline

N, M, K = map(int, readline().split())

F = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, readline().split())
    F[a].append(b)
    F[b].append(a)

B = [[] for _ in range(N + 1)]
for _ in range(K):
    c, d = map(int, readline().split())
    B[c].append(d)
    B[d].append(c)

seen = [-1] * (N + 1)
group = 0


def dfs(graph, s):
    stack = [s]
    seen[s] = group
    n_connection = 1

    while stack:
        u = stack.pop()
        for v in graph[u]:
            if seen[v] == -1:
                n_connection += 1
                seen[v] = group
                stack.append(v)

    return n_connection


union = {}
for i in range(1, N + 1):
    if seen[i] == -1:
        n = dfs(F, i)
        union[group] = n
        group += 1

ans = []
for i in range(1, N + 1):
    tmp = 0
    tmp += union[seen[i]] - 1
    tmp -= len(F[i])
    for j in B[i]:
        if seen[j] == seen[i]:
            tmp -= 1
    ans.append(tmp)

print(" ".join(map(str, ans)))


Measured memory_bytes: 51732
import fractions
import math

N, M = list(map(int, input().split()))
a = list(map(int, input().split()))

z = a[0]
for x in a[1:]:
    g = fractions.gcd(z, x)
    l = z / g
    m = x / g

    if l % 2 == 1 and m % 2 == 1:
        z = l * m * g
    else:
        print(0)
        exit()

print(round((M + 1) / z))

Measured memory_bytes: 16280
#include<bits/stdc++.h>
using namespace std;
int h,w,tmp;
char b[10];
int a[10][10];
void dfs(int x,int y){
    if(x==h-1&&y==w-1){
        for(int i=0;i<h;i++)
			for(int j=0;j<w;j++){
            if(a[i][j])return;
        }
        tmp=1;
        return;
    }
     if(a[x+1][y]){
        a[x+1][y]=0;
        dfs(x+1,y);
        a[x+1][y]=1;
    }
    if(a[x][y+1]){
        a[x][y+1]=0;
        dfs(x,y+1);
        a[x][y+1]=1;
    }
}
int main(){
    scanf("%d%d",&h,&w);
    for(int i=0;i<=h;i++){
        gets(b);
        for(int j=0;j<w;j++)
        if(b[j]=='#')a[i-1][j]=1;
    }
    if(a[0][0]){
        a[0][0]=0;
        dfs(0,0);
    }
    if(tmp)cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
    return 0;
} 

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

int main()
{
    ll N,K=0,x,sum=0,c=0;
    cin>>N;
    set<ll>s;
    ll ara[N];
    for(int i=0; i<N; i++)
    {
        cin>>x;
        s.insert(x);
    }

   cout<<s.size()<<endl;
}




Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <new>

using namespace std;

int main(){
    char S[10];
    cin >> S;
    if(S[0] == S[1] && S[1] != S[2] && S[2] == S[3])
    cout << "Yes" << endl;
    else if(S[0] == S[2] && S[1]!=S[2] && S[1]==S[3])
    cout << "Yes" << endl;
    else if(S[0]==S[3]&&S[1]==S[2]&&S[0]!=S[1])
    cout << "Yes" <<endl;
    else cout << "No" <<endl;
	return 0;
}


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

int main() {
    //input
    int x,a,b;
    cin >> x >> a >> b;
    if(b <= a){
        cout << "delicious" << endl;
    }else if (b <= a+x){
        cout << "safe" << endl;
    }else{
        cout << "dangerous" << endl;
    }

    return 0;
}

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

bool comp(int x, int y)
{
  return x > y;
}

int main()
{
  int n; cin >> n;
  vector<int> a(n);
  rep(i, n)
    cin >> a[i];
  vector<int> last;
  last.push_back(a[0]);
  for (int i=1; i<n; i++)
  {
    auto itr = upper_bound(last.begin(), last.end(), a[i], comp);
    if (itr == last.end())
      last.push_back(a[i]);
    else
      *itr = a[i];
  }
  cout << last.size() << endl;
}

Measured memory_bytes: 1276
let a,b,k = Scanf.scanf "%d %d %d\n" @@ fun a b c -> a, b, c
let rec f x max i =
  if i = k || x > max then [] else x :: f (x+1) max (i+1)
let rec g x min i lst =
  if i = k || x < min then [] else if List.mem x lst then g (x-1) min (i+1) lst
  else x :: g (x-1) min (i+1) (x :: lst)
let ans = let l = (f a b 0) in List.fast_sort compare (l @ (g b a 0 l))
let () = List.iter (fun x -> print_endline (string_of_int x)) ans

Measured memory_bytes: 512
package main

import "fmt"

func ifAllValuesAreEven(a []int) bool {
	for _, v := range a {
		if v%2 == 1 {
			return false
		}
	}
	return true
}

func countUp(cnt int, a []int) int {
	if ifAllValuesAreEven(a) {
		for i := range a {
			a[i] /= 2
		}
		cnt = countUp(cnt+1, a)
	}
	return cnt
}

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	cnt := countUp(0, a)
	fmt.Println(cnt)
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
using namespace std;

long long int atime(const long long int l, const long long int r) {
	if (l > LLONG_MAX / r) {
		return LLONG_MAX;
	}
	else {
		return l*r;
	}
}
long long int powint(long long int a, long long int b) {
	if (!b)return 1;
	else {
		return atime(a, powint(a, b - 1));
	}
}

long long int aplus(const long long int l, const long long int r) {
	if (l > LLONG_MAX / 3 || r > LLONG_MAX)return LLONG_MAX;
	else return l + r;
}

void getans(const vector<long long int>& sums,const vector<long long int>&tickets, const int now, long long int &ans,const long long int rest) {
	if (now == tickets.size()) {
		ans = min(ans, rest);
		return;
	}
	if (ans < rest - sums[now])return;
	
	if (rest >= tickets[now]) {
		getans(sums, tickets, now + 1, ans, rest - tickets[now]);
	}
	else {
		ans = min(ans, tickets[now] - rest);
	}
	getans(sums, tickets, now + 1, ans, rest);
}
int main() {
	long long int N, M, A, B, P, Q; 
	cin >> N >> M >> A >> B >> P >> Q;
	if (A > B) {
		swap(A, B);
		swap(P, Q);
	}
	assert(A <= B);
	if (A == 1 && B == 1) {
		long long int ticdis = P + Q;
		if (atime(ticdis,N) <= M) {
			cout << M - atime(ticdis, N) << endl;
		}
		else {
			cout << min(ticdis-M%ticdis,M%ticdis) << endl;
		}
	}
	else {
		vector<long long int>tickets;
		long long	int ans = M;
		for (int k = 0; k < N; ++k) {
			long long int tic =aplus( atime(P, powint(A, k)), atime(Q, powint(B, k)));
			if (tic > M) {
				ans = min(ans, tic - M);
				break;
			}
			else {
				tickets.emplace_back(tic);
			}
		}
		reverse(tickets.begin(), tickets.end());
		vector<long long int>sums(tickets);
		for (int i = sums.size()-1; i >0; --i) {
			sums[i - 1] += sums[i];
		}
		getans(sums, tickets, 0, ans, M);
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3148
#include <stdio.h>

int main(void) {

  long k,a,b;
  scanf("%ld %ld %ld", &k, &a, &b);
  long biscuit = 1+k;
  if (b > a+2) {
    long operation = 0;
    biscuit = 1;
    if (biscuit < a) {
      if (k-operation < a-biscuit) {
        biscuit += k-operation;
        operation = k;
      } else {
        operation = a-biscuit;
        biscuit = a;
      }
    }
    biscuit += (k-operation)/2*(b-a);
    biscuit += (k-operation)%2;
  }
  printf("%ld\n", biscuit);

  return 0;
}

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

int main() {
  int n,ans=0;
  cin >> n;
  int a[n];
  r(i,n)cin>>a[i];
  r(i,n-1){
    if(a[i]==i+1){
      swap(a[i],a[i+1]);
      ans++;
    }
  }
  if(a[n-1]==n)ans++;
  cout<<ans<<endl;
}

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

//int from[1009];

int main()
{ 
  ll dp[100009];
  for(int i=1;i<=100005;i++)
    dp[i] = 10000000000000ll;
  ll w[109];
  int v[109];
  dp[0]= 0;
  int n;
  ll cap;
  ll sum = 0;
  cin >> n >> cap; 
  for(int i=0;i<n;i++){
    cin >> w[i] >> v[i];
    sum = sum + v[i]; 
  }
  //cout << sum << endl;
  for(int i=0;i<n;i++){

      int current = sum - v[i];
      for(int j = current; j>=0;j--){
        int index = j + v[i];
          //cout << j << " " << dp[index] << " " << dp[j]+w[i] << endl;
        dp[index] = min(dp[index],dp[j]+w[i]);
      
      }
      
      //cout << endl;
    
  }

  int ans = 0;
  for(int i=0;i<=sum;i++){
    if(dp[i]<=cap)
      ans = max(i,ans);
  }
  cout << ans << endl;

}

Measured memory_bytes: 1152
#include <cstdio>
#include <iostream> 
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
 
using namespace std;
using ll = long long;
using ull = unsigned long long;
 
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(int i = 0; i < n; i++)
#define RREP(i, n) for(int i = n - 1; i >= 0; i--)
#define REP2(i, n, k) for(int i = 0; i < n; i += k)


ll POW(ll n){
    if(n == 0)return 1;
    else if(n % 2 == 0){
        return POW(n / 2) * POW(n / 2) % MOD;
    }
    else{
        return 2 * POW(n - 1) % MOD;
    }
}

int main()
{
    ll n;
    map<ll, ll> m;

    cin >> n;
    REP(i, n){
        ll a;
        cin >> a;
        m[a]++;
    }

    for(auto x : m){
        if(x.second % 2 != 0){
            if(n % 2 == 0 || x.first != 0){
                cout << 0 << endl;
                return 0;
            }
        }
    }

    if(n % 2 == 1)n--;

    cout << POW(n / 2) << endl;
}

Measured memory_bytes: 4224
from itertools import product

N = int(input())
S = input()

cnt = 0
for i, j, k in product("0123456789", repeat=3):
    try:
        x = S.index(i)
        y = S.index(j, x + 1)
        z = S.index(k, y + 1)
    except:
        continue
    cnt += 1

print(cnt)

Measured memory_bytes: 3060
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <utility>

using namespace std;

int main() {

	int N, W;
	scanf("%d %d", &N, &W);
	pair<int, int> items[N];
	for (int i = 1; i <= N; ++i) {
		int v, w;
		scanf("%d %d", &v, &w);
		items[i] = make_pair(v, w);
	}
	int V[N + 1][W + 1];
	for (int i = 0; i <= N; ++i) {
		V[i][0] = 0;
	}
	for (int i = 0; i <= W; ++i) {
		V[0][i] = 0;
	}
	for (int i = 1; i <= N; ++i) {
		for (int w = 1; w <= W; ++w) {
			if (items[i].second <= w) {
				if (items[i].first + V[i - 1][w - items[i].second] > V[i - 1][w]) {
					V[i][w] = items[i].first + V[i - 1][w - items[i].second];
				} else {
					V[i][w] = V[i - 1][w];
				}
			} else {
				V[i][w] = V[i - 1][w];
			}
		}
	}

	int maxv = 0;
	for (int i = 0; i <= W; ++i) {
		maxv = max(maxv, V[N][i]);
	}

	cout << maxv << endl;

	return 0;
}

Measured memory_bytes: 7156
#include<bits/stdc++.h>
#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif

using namespace std;
typedef vector<int> VI;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int maxn = 2e5 + 10; 

int main()
{
	fastIO;
	ll n,d;
	cin >> n >> d;
	int ans = 0;
	d *= d;
	for(int i = 0; i < n; ++i)
	{
		ll y,x;
		cin >> x >> y;
		x *= x, y *= y;
		if(x + y <= d) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;


int main() {
    int a, b;
    cin >> a >> b;

    if (a < 10 and b < 10) {
        cout << a * b << endl;
    }
    else {
        cout << -1 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] button = new int[N];
		for(int i=0; i<N; i++) {
			button[i] = sc.nextInt();
		}

		int p = 0;
		for (int i = 0; i < N; i++ ) {
			int num = button[p];
			if(num == 2) {
				System.out.println(i+1);
				return;
			}
			p = num-1;
		}
		System.out.println(-1);
	}
}


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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<P> a(n);
	rep(i,n){
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a.begin(), a.end());
	int ans = 0;
	rep(i,n){
		if(a[i].second%2 != i%2) ++ans;
	}
	ans /= 2;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3972
import sys
input = sys.stdin.readline

N = int(input())
nt, na = map(int, input().split())

for _ in range(N-1):
    t, a = map(int, input().split())
    c = max((nt+t-1)//t, (na+a-1)//a)
    nt = c*t
    na = c*a

print(nt+na)

Measured memory_bytes: 63912
N, M = gets.split.map(&:to_i)
h = []
h = gets.split.map(&:to_i)
a = []
b = []
ma = []
ma = ma.fill(0,0..N-1)
M.times do |i|
  a[i], b[i] = gets.split.map(&:to_i)
  ma[a[i]-1] = [ h[b[i]-1], ma[a[i]-1] ].max
  ma[b[i]-1] = [ h[a[i]-1], ma[b[i]-1] ].max
end
ans = 0
N.times do |i|
  if ma[i] < h[i]
    ans += 1
  end
end
puts ans

Measured memory_bytes: 23192
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using v = vector<ll>;
using p = pair<ll,ll>;

int main(){
    ll n,m; cin >> n >> m;
    auto xy = vector<p>(m,p(0,0));
    for(auto &i:xy) {
        cin >> i.first >> i.second;
        i.first--;
        i.second--;
    }
	auto ball = vector<pair<ll,bool> >(n,p(1,false));
    ball[0] = p(1,true);
    for(auto i:xy){
        bool &red = ball[i.first].second;
        ll &num = ball[i.first].first;
        ball[i.second].first++;
        ball[i.second].second |= red;
        if(num==1&&red){
            red = false;
        }
      	num--;
    }
    cout << accumulate(ball.begin(),ball.end(),0,[](ll sum, pair<ll,bool> i){
        return sum +=i.second ? 1:0; 
    });
    return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
#define F first
#define S second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define len(s) s.length()
#define all(v) v.begin(),v.end()
const ll INF = INT_MAX;
const int N = 2e5 + 5;
const ll mod = 1000000007 ;
using namespace std;

int main() {


	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);


	ll tc = 1;
	// cin >> tc;
	while (tc--) {

		ll n, m, l, r;
		ll i, j;
		ll x, y;

		string s;
		cin >> s;
		n = len(s);

		for (i = 0; i < n; i++) {
			if (s[i] == '?') s[i] = 'D';
		}





		cout << s << endl;
	}
}

Measured memory_bytes: 3704
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
using namespace std;

//////全探索したいときに開けよ////////
vector<vector<int>> fspattern;
vector<int> fspattern_draft;
int fspcnt = 0;

void setfspattern_core(int floor,int number,int degree){
  if(floor==degree){
    fspattern.at(fspcnt) = fspattern_draft;
    fspcnt++;
  }else{
    rep(i,number){
      fspattern_draft.at(floor) = i;
      setfspattern_core(floor+1,number,degree);
    }
  }
}

void setfspattern(int number,int degree){
  int64_t array_num = 1;
  rep(i,degree){
    array_num *= number;
  }
  fspattern = vector<vector<int>>(array_num,vector<int>(degree));
  fspattern_draft = vector<int>(degree);
  setfspattern_core(0,number,degree);
}

//////nCrのmodを求めたいときに開けよ/////////
//int64_t univMod = 1000000007;
//int64_t factnum = 100000
//vector<int64_t> modfact(factnum);
//vector<int64_t> modinvfact(factnum);

/*void setmodfact(){
  for(int i=0;i<factnum;i++){
    if(i == 0){
      modfact.at(i) = 1;
    }else{
      modfact.at(i) = (modfact.at(i-1)*i)%univMod;
    }
  }
}

int64_t calcmodpower(int64_t a,int64_t n){
  int64_t res = 1;
  while(n != 0){
    if(n & 1){
      res = (res * a) % univMod;
    }
    a = (a*a) % univMod;
    n = n >> 1;
  }
  return res;
}

int64_t calcinverse(int64_t n){
	return calcmodpower(n,univMod-2);
}

void setmodinvfact(){
  for(int i=0;i<factnum;i++){
    if(i==0){
      modinvfact.at(i) = 1;
    }else{
      modinvfact.at(i) = calcmodpower(modfact.at(i),univMod-2);
    }
  }
}

int64_t calcmodcomb(int64_t n,int64_t r){
  return (((modfact.at(n)*modinvfact.at(r))%univMod)*modinvfact.at(n-r))%univMod;
}

int64_t calcmodpositive(int64_t n){
  return (n + ((abs(n)+univMod-1)/univMod)*univMod)%univMod;
}
  
    */


/*
int64_t calcGCD(int64_t a,int64_t b){
	int64_t p = a;
	int64_t q = b;
	int64_t c = a%b;
	while(c != 0){
		p = q;
		q = c;
		c = p%q;
	}
	return q;
}
*/

int main(){
  int n;
  cin >> n;
  vector<int> a(2*n);
  rep(i,2*n){
    cin >> a.at(i);
  }
  sort(a.begin(),a.end());
  int sum = 0;
  rep(i,n){
    sum += min(a.at(2*i),a.at(2*i+1));
  }
  cout << sum << endl;
    
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
int n, m, q;
struct node{
    int a, b, c, d;
}lim[55];
int mrk[20], ans;
void dfs(int now){
    if (now == n+1){
        int tmp = 0;
        //for (int i = 1; i <= n; ++i) printf("%d ", mrk[i]); printf("\n");
        for (int i = 1; i <= q; ++i){
            if (mrk[lim[i].b]-mrk[lim[i].a] == lim[i].c) tmp += lim[i].d;
        }
        //debug(tmp);
        ans = max(ans, tmp); return;
    }
    for (int i = mrk[now-1]; i <= m; ++i){
        mrk[now] = i; dfs(now+1);
    }
}
int main(void){
    IOS;
    cin >> n >> m >> q;
    for (int i = 1; i <= q; ++i){
        cin >> lim[i].a >> lim[i].b >> lim[i].c >> lim[i].d;
    }
    mrk[0] = 1;
    dfs(1);
    cout << ans << endl;
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (a < b) {
    ll tmp = a;
    a = b;
    b = tmp;
  }
  ll r = a%b;
  while(r != 0) {
    a = b;
    b = r;
    r = a%b;
  }
  return b;
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}

int main() {
    ll w, h, x, y, r;
    cin >> w >> h >> x >> y >> r;
    string ans = "Yes";
    if (x-r<0 || x+r>w || y-r<0 || y+r>h) ans = "No";
    cout << ans << endl;
}


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

int n, k;
vector<pair<int, int>> v;
int main() {
  cin >> n >> k;
  
  if (k > (n - 1) * (n - 2) / 2) {
   cout << "-1" << endl;
    
    return 0;
    
  } else {
    
    cout << n*(n-1)/2-k << endl;
    int ans = 0;
    
    for (int i = 1; i <= n; ++i) {
      
      for (int j = i + 1; j <= n; ++j) {
        
        cout << i << " " << j << endl;
        
        ans++;
        
        if (ans == n*(n-1)/2-k) return 0;
      }
    }
  }
}


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

int main(){
  string s;
  long long x,y,cnt=0;
  cin >> s >> x >> y;
  vector<long long> yoko, tate;
  bool f=true;
  for(size_t i=0;i<s.size();i++){
    if(s[i]=='T'){
      if(f){
        yoko.push_back(cnt);
        f=false;
      }else{
        tate.push_back(cnt);
        f=true;
      }
      cnt=0;
    }else{
      cnt++;
    }
  }
  if(s[s.size()-1]=='F'){
    if(f){
      yoko.push_back(cnt);
    }else{
      tate.push_back(cnt);
    }
  }
  int hosei=8000;
  bool dpx[yoko.size()+5][16005],dpy[tate.size()+5][16005];
  dpx[0][0+hosei]=true; dpy[0][0+hosei]=true;
  for(size_t i=0;i<yoko.size();i++){
    if(i==0){
      dpx[i+1][yoko[i]+hosei] = true;
      continue;
    }
    for(int j=-8000;j<8005;j++){
      dpx[i+1][j+hosei] = ((j-yoko[i]+hosei>=0?dpx[i][j-yoko[i]+hosei]:false) or (j+yoko[i]<=8000?dpx[i][j+yoko[i]+hosei]:false));
    }
  }
  for(size_t i=0;i<tate.size();i++){
    for(int j=-8000;j<8005;j++){
      dpy[i+1][j+hosei] = ((j-tate[i]+hosei>=0?dpy[i][j-tate[i]+hosei]:false) or (j+tate[i]<=8000?dpy[i][j+tate[i]+hosei]:false));
    } 
  }
  if(dpx[yoko.size()][x+hosei] and dpy[tate.size()][y+hosei]){
    cout << "Yes\n";
  }else{
    cout << "No\n";
  }
  return 0;
}

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

int main() {
  int N;
  int K;
  
  
  cin>>N>>K;
  
 vector<int> h(N);
for (int i = 0; i < N; i++) {
  cin >> h.at(i);
}
   sort(h.begin(), h.end());
   
  
  /*vector<int> m(K);
  for (int i = 0; i < N-K+1; i++) {
  m.at(i)=h.at(i+K-1)-h.at(i);
}

  int min = *std::min_element(m.begin(), m.end());*/
  
  
  int a=1000000000;
  //int b;
  //int c;
  for (int i = 0; i < N-K+1; i++) {
    if(h.at(i+K-1)-h.at(i)<a){
      a=h.at(i+K-1)-h.at(i);
    }
  //b=min(h.at(i+K-1)-h.at(i),h.at(i+K)-h.at(i+1));
  //  c=b;
    
}
  
  cout<<a<<endl;
  
  
  
}

Measured memory_bytes: 640
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define PRN(n) printf("%d\n",n)
#define PRF(n) printf("%lf\n",n)
#define PRL(n) printf("%lld\n",n)
#define PRS(s) printf("%s\n",s)
#define PRC(c) printf("%c",c)
#define mod 1000000007
typedef long long int ll;
ll dp[100001];
int q(const void *a, const void *b){
    return *(ll*)a-*(ll*)b;
}
int min(int a,int b){
  if(a>b)return b;
  return a;
}
int max(int a,int b){
  if(a>b)return a;
  return b;
}
int gcd(int a,int b){
  if(!b)return a;
  return gcd(b,a%b);
}
int main(void) {
  int a,b;
  scanf("%d %d",&a,&b);
  PRN(a/b+a%b);
  return 0;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define itn int

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


int main()
{
  int a,b;
  cin >> a >> b;
  int res = a;
  if(a > b)res--;
  cout << res << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
void *wmem;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
struct unionFind{
  int M, N, *d;
  inline void malloc(int n){
    d = (int*)std::malloc(n*sizeof(int));
    M = n;
  }
  inline void *walloc(int n, void **mem=&wmem){
    d = (int*)(*mem);
    (*mem) = (d+n);
    M = n;
  }
  inline void init(int n){
    int i;
    N = n;
    for(i=0;i<n;i++){
      d[i] = -1;
    }
  }
  inline void init(void){
    init(M);
  }
  inline int get(int a){
    int k, t=a;
    while(d[t]>=0){
      t=d[t];
    }
    while(d[a]>=0){
      k=d[a];
      d[a]=t;
      a=k;
    }
    return a;
  }
  inline int connect(int a, int b){
    if(d[a]>=0){
      a=get(a);
    }
    if(d[b]>=0){
      b=get(b);
    }
    if(a==b){
      return 0;
    }
    if(d[a] < d[b]){
      d[a] += d[b];
      d[b] = a;
    }
    else{
      d[b] += d[a];
      d[a] = b;
    }
    return 1;
  }
  inline int operator()(int a){
    return get(a);
  }
  inline int operator()(int a, int b){
    return connect(a,b);
  }
  inline int& operator[](int a){
    return d[a];
  }
  inline int sizeList(int res[]){
    int i, sz=0;
    for(i=0;i<N;i++){
      if(d[i]<0){
        res[sz++] = -d[i];
      }
    }
    return sz;
  }
}
;
char memarr[96000000];
int N;
int M;
int X[100000];
int Y[100000];
int Z[100000];
int main(){
  int i, res;
  unionFind uf;
  wmem = memarr;
  rd(N);
  rd(M);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<M;Lj4PdHRW++){
      rd(X[Lj4PdHRW]);
      rd(Y[Lj4PdHRW]);
      rd(Z[Lj4PdHRW]);
    }
  }
  uf.malloc(N);
  uf.init(N);
  res = N;
  for(i=0;i<M;i++){
    res -= uf(X[i]-1, Y[i]-1);
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190601-1

// --- original code ---
// int N, M, X[1d5], Y[1d5], Z[1d5];
// {
//   int i, res;
//   unionFind uf;
//   
//   rd(N,M,(X,Y,Z)(M));
// 
//   uf.malloc(N);
//   uf.init(N);
//   
//   res = N;
//   rep(i,M) res -= uf(X[i]-1, Y[i]-1);
// 
//   wt(res);
// }


Measured memory_bytes: 1920
/**
 *      ABC 82 C
 *      author  : kyomukyomupurin
 *      created : 2018-09-16 10:12:58
**/

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

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

    int N; cin >> N;
    int a[N] = {};
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    sort(a, a + N);

    int answer = 0; 
    int begin = 0;

    while (begin < N){
        int end = begin;
        while (end + 1 < N && a[end + 1] == a[begin]){
            ++end;
        }
        int len = end - begin + 1;
        if (len >= a[end]){
            answer += (len - a[end]);
        }
        else {
            answer += len;
        }
        
        begin = end + 1;
    }
    cout << answer << endl;

    return 0;
}

Measured memory_bytes: 640
#define	_USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <set>
#include <complex>
#include <utility>
#include <numeric>
#define  rep(i,n) for(int i=0;i<(n);i++)
#define  REP(i,a,n) for(int i=a;i<(n);i++)
#define  rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define  VI	vector<int>
#define	 VS vector<string>
#define  all(a) (a).begin(),(a).end()
#define  debug(x) cout<<#x<<": "<<x<<endl
using namespace std;
typedef long long ll;

const int INF=1e9;
char fi[101][101];
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};
double EPS = 1e-10;
int N,M;
int sx,sy;
int gx,gy;
int w,h;
int ans;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
const int MAX_V=100;
const int MAX_N=100;
char o[3]={'+','-','*'};
#define md 1000003


int dp[353][353]={0};
int bow[353][353]={0};
double add(double a,double b){
	if(abs(a+b)<EPS*(abs(a)+abs(b)))
	return 0;
	return a+b;
}

struct P{
	double x,y;
	P(){}
		P(double x,double y):x(x),y(y){
		}
		P operator + (P p){
			return P(add(x,p.x),add(y,p.y));
		}
		P operator - (P p){
			return P(add(x,-p.x),add(y,-p.y));
		}
		P operator *(double d){
			return P(x*d,y*d);
		}
		double dot(P p){
			return add(x*p.x,y*p.y);
		}
		double det(P p){
			return add(x*p.y,-y*p.x);
		}
};

bool cmp_x(const P& p,const P& q){
	if(p.x!=q.x) return p.x<q.x;
	return p.y<q.y;
}

vector<P> convex_hull(P* ps, int n){
	sort(ps,ps+n,cmp_x);
	int k=0;
	vector<P> 	qs(n*2);
	
	rep(i,n){
		while(k>1&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)
			k--;
		qs[k++]=ps[i];
	}
	for(int i=n-2,t=k;i>=0;i--){
		while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)
		k--;
		qs[k++]=ps[i];
	}
	qs.resize(k-1);
	return qs;
}

int n,m;
vector<double> p;
P ps[101];
char c[520][520];
long long mod=1000000007;
long long pow(ll i,ll j){
	ll tmp=1;
	while(j){
		if(j%2) tmp=tmp*i%mod;
		i=i*i%mod;
		j/=2;
	}
	return tmp;
}
int main(){
	
	int n,r;
	cin>>n>>r;
	
	int minv=r;
	int maxv=-INF;
	
	for(int i=1;i<n;++i){
		cin>>r;
		maxv=max(maxv,(r-minv));
		minv=min(minv,r);
	}
	cout<<maxv<<endl;
}

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

int main() {
  int a , b ;
  cin >> a >> b;
  int c=a*b;
  c%=2;
  if( c == 1 ){
    cout << "Odd" << endl;
  }else{
    cout << "Even" << endl;
  }
  
}

Measured memory_bytes: 256
n, w = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(n)]

dp = [[-1 for _ in range(w + 5)] for _ in range(n + 5)]
dp[0][0] = 0

for i in range(n):
    for j in range(w + 1):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if j - item[i][0] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - item[i][0]] + item[i][1])

print(max(dp[n][: w + 1]))


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

int main() {
    int x,
        i = 0;
    while(true){
        cin >> x;
        if(x == 0){
            break;
        }
        else{
            cout << "Case " << i + 1 << ": " << x << endl;
        }
        i++;
    }
}


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

//#define DEBUG
#define int long long
#define REP(i,n) for(int i=0;i<n;i++)
#define RND(x,y) for(int x=-2;x<=2;x++)for(int y=-2;y<=2;y++)
int n;
int a[114514];
int s[114514];

int b(int x){
  return distance(s,lower_bound(s,s+n,x));
}

int mod(int x,int y){
  return (x%y+y)%y;
}

signed main(){
  cin>>n;
  REP(i,n){
    cin>>a[i];
    s[i+1]=a[i]+s[i];
  }
  int ans=0;
  int S=s[n];
  REP(i,n){
    int p=b((S/3+s[i])%S);
    int q=b((S*2/3+s[i])%S);
    RND(x,y){
      int px=(p+x)%n;
      int qy=(q+y)%n;
      int w1=mod(s[px]-s[i],S);
      int w2=mod(s[qy]-s[px],S);
      int w3=mod(s[i]-s[qy],S);
      if(w1+w2+w3!=S)continue;
      #ifdef DEBUG
      cout<<(i)<<" "<<(px)<<" "<<(qy)<<":";
      cout<<w1<<" "<<w2<<" "<<w3<<endl;
      #endif
      int wm=min({w1,w2,w3});
      ans=max(ans,wm);
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4624
import operator as op
from functools import reduce
 
def npr(n, r):
    numer = 1
    for k in range(r):
        numer = numer * (n - k)
        numer %= q
    return numer


N, K = list(map(int, input().split()))
q = 1000000007

child_num = [0 for i in range(N)]
for k in range(N - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    child_num[a] += 1
    child_num[b] += 1

for i in range(1, N):
    child_num[i] -= 1

# calculate
min_child = min(child_num)
if K < min_child:
    print(0)
else:
    ans = (K * npr(K - 1, child_num[0])) % q
    for i in range(1, N):
        val = npr(K - 2, child_num[i]) % q
        ans = (ans * val) % q
    print(ans)

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

#define REF 1000000007

int main() {
    long N;
    cin >> N;
    long res = 1;
    for (long i = 1; i < N+1; i++) {
        res *= i;
        res %= REF;
    }
    cout << res << endl;
    return 0;
}


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

int main(){
  char ch;

  while(1){
    scanf("%c", &ch);

    if('a' <= ch && ch <= 'z'){
      printf("%c", ch-32);
    } else if('A' <= ch && ch <= 'Z'){
      printf("%c", ch+32);
    } else {
      printf("%c", ch);
    }

    if(ch == '\n') break;
  }
}



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

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) ll(x.size()) //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define Umap unordered_map
#define Uset unordered_set

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    int now = 0;
    int is = false;
    for (int i = 0; i < 11; i++){
        if (i * 1000 >= n){
            is = true;
            now = i;
            break;
        }
    }
    cout << now * 1000 -n<< endl;
}

Measured memory_bytes: 3196
#include<cstdio>

int gcd_euclidean(int u, int v){
    if(v==0)  return u;
    return gcd_euclidean(v, u%v);
}

int lcm(int u, int v){
    return u*(v/gcd_euclidean(u,v));
}

int main(int argc, char const *argv[])
{
    int a, b;
    while(~scanf("%d %d", &a, &b)){
        printf("%d %d\n", gcd_euclidean(a,b), lcm(a,b));
    }
    return 0;
}



Measured memory_bytes: 2660
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define LL long long
#define INF 1000000001
#define mod 1000000007
using namespace std;
int keta(int n,int k){return (n/int(pow(10,double(k-1)))) % 10;} //nの下からk桁目
ll gcd(ll n,ll m){
	if(n<m){ll a=m;m=n;n=a;}
	ll r=n%m;
	while(r!=0){
		n=m;
		m=r;
		r=n%m;
	}
	return m;
}
ll lcm(ll n,ll m){
	return n*m/gcd(n,m);
}


int main(){

	int n,m;
	cin>>n;
	vector<int> d(n);
	rep(i,n){
		cin>>d[i];
	}
	cin>>m;
	vector<int> t(m);
	rep(j,m){
		cin>>t[j];
	}
	sort(d.begin(),d.end());
	sort(t.begin(),t.end());
	
	int i=0,j=0;
	while(j<m){
		int T=t[j];
		while(1){
			if(d[i]==T){
				j++;
				i++;
				break;
			}else if(d[i]>T){
				cout<<"NO"<<endl;
				return 0;
			}else{
				i++;
			}
			if(i==n){			
				cout<<"NO"<<endl;
				return 0;
			}
		}
	}
	cout<<"YES"<<endl;
}

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

int main() {
  vector<vector<int>> c(3, vector<int>(3));
  rep(i,3) rep(j,3) cin>>c[i][j];
  bool flag=true;
  rep(i,2){
    rep(j,2){
      if (!(c[i][j+1]-c[i][j]==c[i+1][j+1]-c[i+1][j])) flag=false;
      if (!(c[j+1][i]-c[j][i]==c[j+1][i+1]-c[j][i+1])) flag=false;
    }
  }
  if(flag) puts("Yes");
  else puts("No");
  return 0;
}


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

struct Knapsack01{
    int N, W;
    vector<int> v, w, dp;
    Knapsack01(vector<int> v, vector<int> w, int W): v(v), w(w), W(W){
        N = v.size();
        dp.resize(W + 1);
    }
    int build(){
        for(int i = 0; i < N; i++){
            for(int j = W; j >= w[i]; j--){
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        int ret = 0;
        for(int i = 0; i <= W; i++) ret = max(ret, dp[i]);
        return ret;
    }
};

signed main(){
    int N, W;
    cin >> N >> W;
    vector<int> v(N), w(N);
    for(int i = 0; i < N; i++) cin >> w[i] >> v[i];
    Knapsack01 a(v, w, W);
    cout << a.build() << endl;
}


Measured memory_bytes: 1024
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

const int N=1010;

char s[105][105];
int dp[N][1<<12],r,c,HPi,HPm,T,S,P,n,dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int dam[30],pot[15],hash[300],rot[N];

void input(){
    cin>>r>>c;
    for(int i=1;i<=r;i++) scanf("%s",s[i]+1);
    cin>>T;
    for(int i=0;i<T;i++){
        char key[5];

        int x;
        scanf("%s%d",key,&x);
        dam[key[0]-'A']=x;
    }
    n=0;
    cin>>S;
    for(int i=0;i<S;i++){
        char key[5];
        int x;
        scanf("%s%d",key,&x);
        for(int j=0;j<x;j++) rot[++n]=hash[key[0]];
    }
    cin>>P;
    for(int i=0;i<P;i++) scanf("%d",&pot[i]);
    memset(dp,0,sizeof(dp));
}

void init(){
    hash['U']=0;
    hash['D']=1;
    hash['L']=2;
    hash['R']=3;
}

void DP(){
    int x=1,y=1;
    dp[0][0]=HPi;
    for(int i=1;i<=n;i++){
        x+=dx[rot[i]],y+=dy[rot[i]];
        int hr=dam[s[x][y]-'A'];
        for(int j=0;j<(1<<P);j++){
            if(!dp[i-1][j]) continue;
            dp[i][j]=max(dp[i][j],dp[i-1][j]-hr);
            for(int k=0;k<P;k++){
                if(j&(1<<k)) continue;
                int hp=min(HPm,pot[k]+dp[i-1][j]);
                hp=max(0,hp);
                dp[i-1][j|(1<<k)]=max(dp[i-1][j|(1<<k)],hp);
            }
        }
    }
    bool ok=false;
    for(int i=0;i<(1<<P);i++) if(dp[n][i]>0) ok=true;
    if(ok) puts("YES");
    else puts("NO");
}

int main(){
   // freopen("in","r",stdin);
    init();
    while(cin>>HPi>>HPm){
        if(HPi+HPm==0) break;
        input();
        DP();
    }
    return 0;
}

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

using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
#define repc(i,s,e) for(int i=(s); i<(e); i++)
#define pb(n) push_back((n))
#define mp(n,m) make_pair((n),(m))
#define all(r) r.begin(),r.end()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


int main() {

	vi v(300100, 1);

	for (int i = 0; i < 300100; i++) {
		if (v[i] == 1) {
			if ((i - 8 >= 0 && (i - 8) % 7 == 0) || (i - 6 >=0 && (i - 6) % 7 == 0)) {
				for (int j = 2; i*j < 300100; j++) {
					v[i*j] = 0;
				}
			}
			else {
				v[i] = 0;
			}
		}
	}

	int n;
	while (cin >> n && n > 1) {
		cout << n << ":";
		for (int i = 2; i <= n; i++) {
			if (v[i] && n%i == 0 ) {
				cout << " " << i;
			}
		}
		cout << endl;
	}
}

Measured memory_bytes: 2328
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef pair<ll, ll> P;

class Graph{
    struct edge{
        int vertice;
        ll weight;
    };

    vector<vector<edge>> g;
    unsigned int n;

public:
    Graph(unsigned int n): n{n}{
        g.resize(n);
    }

    void add_edge(int u, int v){
        g[u].emplace_back(edge{v, 1});
    };

    void add_edge(int u, int v, ll w){
        g[u].emplace_back(edge{v, w});
    }

    vector<edge>& get_edge(int v){
        return g[v];
    }

    unsigned int get_num_vertices(){
        return n;
    }

    vector<edge>& operator[](int v){
        return get_edge(v);
    }
};


void dfs(int v, int prev, Graph& g, vector<int>& res, ll dis){
    res[v] = dis % 2;
    for(auto e: g[v]){
        if(e.vertice == prev)   continue;
        dfs(e.vertice, v, g, res, dis + e.weight);
    }
}


int main(){
    int n;  cin >> n;
    Graph g(n);
    for(int i = 0; i < n-1; i++){
        ll u, v, w; cin >> u >> v >> w;
        u--; v--;
        g.add_edge(u, v, w);
        g.add_edge(v, u, w);
    }

    vector<int> res(n);
    dfs(0, 0, g, res, 0);
    for(int i = 0; i < n; i++){
        cout << res[i] << endl;
    }

    
    return 0;
}


Measured memory_bytes: 11264
#include<bits/stdc++.h>
using namespace std;
#define ff              first
#define ss              second
#define rep(i,n)        for(int i=0;i<n;i++)
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define Sort(v)         sort(v.begin(), v.end(), sortbysec)
#define setbits(x)      __builtin_popcountll(x)
#define rightmostbit(x) __builtin_ffsll(x)
#define leftzeros(x)    __builtin_clzll(x)
#define rightzeros(x)   __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         cout << fixed; cout << setprecision(x); cout << y;
#define pi              3.141592653589793238
#define mk(a,n)         int n;cin>>n;int a[n];for(int i=0;i<n;i++) cin>>a[i]
#define w(x)            int x; cin>>x; while(x--)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b)
{	return (a.second < b.second);
	// sorted by 2nd element in ascending order
}
void g_b()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
#endif
}
int32_t main()
{
	int a; cin >> a;
	int p = a * a;
	int q = p * a;
	cout << a + p + q;
	return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int n, k;
vector<long long> V(55, 0);

int main() {
    cin >> n >> k;
    for(int i = 0; i < n; ++i) cin >> V.at(i);

    int limit = min(n, k);
    long long vans = 0;
    for(int left = 0; left <= limit; ++left) {
        priority_queue <long long, vector<long long>, greater<long long>> pque;
        for(int i = 0; i < left; ++i) {
            pque.push(V.at(i));
        }

        for(int right = 0; right <= limit-left; ++right) {
            priority_queue<long long, vector<long long>, greater<long long>> ansque;
            ansque = pque;
            for(int j = 0; j < right; ++j) {
                ansque.push(V.at(n-1-j));
            }

            int dust = k-left-right;
            long long sum = 0;
            int now = 0;
            while(!ansque.empty() && now < dust) {
                if(ansque.top() < 0) {
                    ansque.pop();
                    now++;
                }else break;
            }

            while(!ansque.empty()) {
                sum += ansque.top();
                ansque.pop();
            }

            chmax(vans, sum);
        }
    }

    cout << vans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

int main(int argc, char const *argv[])
{
	std::string input;
	std::cin >> input;
	int times ;
	std::cin >> times;
	std::string op;
	for(int i = 0 ; i < times ; i ++){
		std::cin >> op;
		if(op == "replace"){
			int s,e;
			std::cin >> s >> e;
			std::string rep;
			std::cin >> rep;
			input.replace(s,e-s+1,rep);
		}else if(op == "reverse"){
			int s,e;
			std::cin >> s >> e;
			std::string rev = "";
			for(int i = e ; i >= s ; i --){
				rev.push_back(input.at(i));
			}
			input.replace(s,e-s+1,rev);
		}else if(op == "print"){
			int s,e;
			std::cin >> s >> e;
			std::cout << input.substr(s,e-s+1) << std::endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3212
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
LL mod = 1e9+7;

int main(){
    int N;
    cin >> N;
    string s1, s2;
    cin >> s1 >> s2;
    s1 += " ";
    vector<int> vp;
    for(int i = 0;i < s1.size()-1;i++){
        if(s1[i] == s1[i+1]){
            vp.push_back(0);
            i++;
        }else{
            vp.push_back(1);
        }
    }
    vector<LL>  dp(vp.size());
    if(!vp[0])   dp[0] = 6;
    else    dp[0] = 3;
    for(int i = 1;i < vp.size();i++){
        if(!vp[i]){
            if(!vp[i-1])    dp[i] = dp[i-1]*3%mod;
            else    dp[i] = dp[i-1]*2%mod;
        }else{
            if(!vp[i-1]) dp[i] = dp[i-1];
            else    dp[i] = dp[i-1]*2%mod;
        }
    }
    cout << dp[vp.size()-1] << endl;
}

Measured memory_bytes: 256
m, d = map(int, input().split())
ans = 0
for i in range(1, m + 1):
    for j in range(min(22, d), d + 1):
        if j // 10 * (j % 10) == i and j % 10 > 1:
            # print(j// 10, j % 10, i)
            ans += 1
print(ans)

Measured memory_bytes: 39860
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
struct UnionFind {
    vector<int> data;

    UnionFind(int sz) { data.assign(sz, -1); }

    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y)
            return (false);
        if(data[x] > data[y])
            swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return (true);
    }

    int find(int k) {
        if(data[k] < 0)
            return (k);
        return (data[k] = find(data[k]));
    }
    bool isSame(int x, int y) { return find(x) == find(y); }
    ll size(int k) { return (-data[find(k)]); }
};
int main() {
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        uf.unite(a - 1, b - 1);
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        ans = max<int>(ans, uf.size(i));
    }
    cout << ans << endl;
}

Measured memory_bytes: 4044
//shan61916
#include <bits/stdc++.h>
  using namespace std;
typedef   long long ll;
typedef   unsigned long long ull ;
typedef   double dll ;

#define   mp make_pair
#define   pb push_back
#define   ff first 
#define   ss second
#define   IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define   endl "\n" 
#define   pll pair<ll, ll>
#define   all(x) x.begin(), x.end()
#define   vll vector<ll> 

const ll inf = (ll)(1e17 + 17);
const ll mod = (ll)(1e9 + 7);


int main(){
 IOS
#ifdef SHAN
    freopen("input.txt" , "r" , stdin);  
#endif
  ll n;
  cin >> n;
  string s, t;
  cin >> s >> t;
  for(ll i = 0; i < n; i++) {
    cout << s[i] << t[i];
  }
  return 0;
} //good night.

Measured memory_bytes: 256
/* ex8_2 
melo */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 1000001
typedef struct node{
    char elem;//文字
    struct node *next;//次のノードへのパス
} node;
void push(node **first,char elem);//スタックにelemを格納
char pop(node **first);//スタックの一番上から取り出す

int main(void){
    int i,count=0;//for文用,キューブの数
    char color[SIZE];//キューブの色の配列
    node *first=NULL;//最初のノードのさす先
    scanf("%s",color);//
    for(i=0;i<strlen(color);i++){//
        if(first==NULL){//スタックに何も入っていないとき
            push(&first,color[i]);//スタックにcolor[i]を格納
        }
        else if(color[i]==first->elem){//真上の色と一緒だった場合
            push(&first,color[i]);//スタックにcolor[i]を格納
        }
        else{//色が違った場合
            pop(&first);//取り除く
            count+=2;//キューブを二つ取り除く
        }
    }
    printf("%d\n",count);//何個キューブを取り除いたか
    return 0;//正常終了
}

void push(node **first,char elem){
    node *new =calloc(1,sizeof(node));//追加する分の領域を確保
    if(new==NULL)exit(1);//確保できなかった場合
    new->elem=elem; //要素を一番上に追加
    new->next=*first;
    *first=new;
}
char pop(node **first){
    char elem;//取り出す要素
    node *tmp =*first;//一番上
    if(tmp==NULL)exit(1);//何も入っていなかったとき
    elem=tmp->elem;//
    *first=tmp->next;//一番上を一つ下げる
    free(tmp);//取り出したノードのメモリを解放
    return elem;//取り出した要素を返す
}

Measured memory_bytes: 4828