akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll mod = 998244353;
class SegmentTree {
private:
    int n;
    vector<ll> node, lazy;
public:
    SegmentTree(int N) {
        n = 1;
        while (n < N) n *= 2;
        node.resize(2 * n - 1, 0);
        lazy.resize(2 * n - 1, 0);
    }

    void update(int i, int l, int r) {
        node[i] += lazy[i];
        node[i] %= mod;
        if (r - l > 1) {
            lazy[2 * i + 1] += lazy[i] / 2;
            lazy[2 * i + 2] += lazy[i] / 2;
        }
        lazy[i] = 0;
    }

    void add(int a, int b, ll x, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        update(k, l, r);
        if (b <= l || r <= a) return;
        
        if (a <= l && r <= b) {
            lazy[k] += (r - l) * (x);
            update(k, l, r);
        } else {
            add(a, b, x, 2 * k + 1, l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = (node[2 * k + 1] + node[2 * k + 2]) % mod;
        }
    }

    ll query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        update(k, l, r);
        if (b <= l || r <= a) return 0;        
        if (a <= l && r <= b) return node[k] % mod;

        ll sum_l = query(a, b, 2 * k + 1, l, (l + r) / 2);
        ll sum_r = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return (sum_l + sum_r) % mod;
    }

    void disp() {
        for (int i : node) {
            cout << i << " ";
        }
        cout << "\n";
    }

};

int main() {
    //cin.tie(0);
    //ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    int L[K], R[K];
    for (int i = 0; i < K; i++) {
        cin >> L[i] >> R[i];
    }

    SegmentTree st(N + 1);
    st.add(1, 2, 1);
    
    for (int i = 1; i < N; i++) {
        ll x = st.query(i, i + 1);
        for (int j = 0; j < K; j++) {
            int l = i + L[j];
            int r = i + R[j] + 1;
            
            st.add(min(l, N + 1), min(r, N + 1), x);
            //st.add(l, r, x);
        }
        //cout << x << "\n";
    }

    cout << st.query(N, N + 1) << "\n";

    return 0;
}

Measured memory_bytes: 11440
# /user/bin/python
# -*- coding: utf-8 -*-
import sys
 

class UnionFind():
  def __init__(self, size):
    self.par = [-1] * size

  def root(self, x):
    if self.par[x] < 0:
      return x
    else:
      return self.root(self.par[x])

  def issame(self, x, y):
    if self.root(x) == self.root(y):
      return True
    else:
      return False
  
  def merge(self, x, y):
    x, y = [self.root(x), self.root(y)]
    if x == y:
      return False
    if self.par[x] > self.par[y]:
      x, y = y, x
    self.par[x] += self.par[y]
    self.par[y] = x
    return True

  def size(self, x):
    return -self.par[self.root(x)]

  def out(self):
    return self.par

if __name__ == "__main__":
  n,m = map(int, sys.stdin.readline().rstrip().split())
  p = list(map(int, sys.stdin.readline().rstrip().split()))

  uf = UnionFind(n)
  for i in range(m):
    x,y = list(map(int, sys.stdin.readline().rstrip().split()))
    x, y = x-1, y-1
    if not uf.issame(x,y):
      uf.merge(x,y)

  ans = 0
  for i in range(n):
    if uf.issame(i, p[i]-1):
      ans += 1
  print(ans)

Measured memory_bytes: 13812
def selection_sort(n, nums):
    cnt = 0
    for i in range(n):
        minj = i
        for j in range(i, n):
            if nums[j] <  nums[minj]:
                minj=j
        if i != minj:              
            tmp = nums[i]
            nums[i] = nums[minj]
            nums[minj] = tmp
            cnt += 1
            
    print(' '.join(map(str, nums)))
    print(cnt)

def main():
    n = int(input())
    line = input()
    nums = list(map(int, line.split()))

    selection_sort(n, nums)

if __name__ == "__main__":
    main()


Measured memory_bytes: 5600
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <string>
#include <queue>
#include <list>
#include <stack>

using namespace std;

/* constant */

const int INF = 1 << 30;
const int mod = 1000000007;

/* typedef */

typedef long long ll;

/* global variables */

/* function */

/* main */
int main() {

    int W, H, x, y, r;
    cin >>  W >> H >> x >> y >> r;
    
    int x_max = x + r;
    int x_min = x - r;
    int y_max = y + r;
    int y_min = y - r;

    if (0 <= x_min && x_max <= W && 0 <= y_min && y_max <= H) {
        cout << "Yes" <<'\n';
    }
    else {
        cout << "No" << '\n';
    }
}



Measured memory_bytes: 3100
/*                        ______
 _______   /\     |``\   |        |  /
    |     /  \    |__/   |____    |/
    |    / _ _\   |  \   |        |\
    |   /      \  |   \  |______  |  \

            Dept. of CSE
        Comilla  University

*/
#include<bits/stdc++.h>
#define pi 2*acos(0.0)
#define ll long long
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Node struct node
#define spc " "
#define  E  2.71828182845904523536
#define pb push_back
#define pp pop_back
#define valid(nx,ny) nx>=0 && nx<n && ny>=0 && ny<m
#define ee endl
#define pii pair<int,int>
#define infinity 10000000000000000
#define mod 1000000007
int fx[]={0,0,+1,-1};
int fy[]={+1,-1,0,0};

using namespace std;
///check n=1;
///check corner case;
const int maX=1e5+1;
vector<ll>Graph[maX],cost[maX];
ll visit[maX];
ll x[10];
ll y[10];

int main()
{
    ll n,i,j,cc=0,mn=1111111111LL;
    string str;
    cin>>str;
    for(i=0;i<str.size()-2;i++){
        ll x=str[i]-'0';
        for(j=i+1;j<=i+2;j++){
        x=x*10+(str[j]-'0');
        }
        ll y=abs(753-x);
        if(y<mn){
            mn=y;
        }
    }
    cout<<mn<<endl;
return 0;
}


Measured memory_bytes: 4992
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <queue>
#include <numeric>
#include <deque>
#include <cstring>
#include <iterator>
#include <map>
#include <cstdlib>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <complex>
#include <bitset>
#include <chrono>
#include <random>
#include <assert.h>

using namespace std;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define eb emplace_back
#define el '\n'
typedef  long long  ll;
typedef  unsigned long long  ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<string> vs;

ll inf=(ll)2e18;
const int mod=1000000007;
//const int mod=998244353;

int n,m;
const int N=2e5+10;

ll ho[1<<15][15],ver[1<<15][15];
ll dp[1<<15];

struct node{
    ll x, y;
    ll p;
};
int main()
{   ios_base::sync_with_stdio(false);cin.tie(NULL);
    int q,t,k,u,v;
    ll x,a,b,c,d,y,p,z;
    cin >> n;
    vector<node> vv(n);
    for(int i=0; i<n; i++){
        cin >> vv[i].x >> vv[i].y >> vv[i].p;
    }
    for(int i=0; i<1<<n; i++){
        for(int j=0; j<n; j++){
            ho[i][j]=abs(vv[j].y);
            ver[i][j]=abs(vv[j].x);
        }
        for(int j=0; j<n; j++){
            if(i>>j&1){
                for(int k=0; k<n; k++){
                    ho[i][k]=min(ho[i][k],abs(vv[k].y-vv[j].y));
                    ver[i][k]=min(ver[i][k],abs(vv[k].x-vv[j].x));
                }
            }
        }
    }
    vll ans(16,inf);
    for(int i=0; i<1<<n; i++){
        for(int j=i; j>=0; j=(j-1)&i){
            int p=j;
            vll mn(15,inf);
            for(int k=0; k<n; k++){
                mn[k]=min({mn[k],ho[p][k],ver[i^p][k]});
            }
            a=0;
            for(int k=0; k<n; k++){
                a+=vv[k].p*mn[k];
            }
            ans[__builtin_popcount(i)]=min(ans[__builtin_popcount(i)],a);
            if(!j){
                break;
            }
        }
    }
    for(int i=0; i<=n; i++){
        cout << ans[i] << el;
    }
    return 0;
}





Measured memory_bytes: 11304
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

		int N_senbei = scan.nextInt();

		int K_people = scan.nextInt();

		int ans = N_senbei % K_people == 0 ? 0 : 1;

		System.out.println(ans);
	}

	//***********************以下共通関数************************************************
	/**
	 * 文字列を反転して返す
	 * @param pStr 文字列
	 * @return 反転した文字列
	 */
	public static String myReverse(String pStr) {
		if (pStr.length() < 1) {
			return "";
		}

		StringBuffer sb = new StringBuffer(pStr);
		return sb.reverse().toString();
	}

	/**
	 * 余りを求める。
	 * @param a
	 * @param b
	 * @return 余り。余りがマイナスの時はプラスで返す。
	 */
	public static long myMod(long a, long b) {
		long ret = 0;

		ret = a % b;

		if (ret < 0) {
			ret += b;
		}

		return ret;
	}

	/**
	 * 乗数を求める ※mod対応
	 * @param kisu 基数
	 * @param josu 乗数
	 * @param primeNumMod_0 法 mod値 使わない場合は「0」
	 * @return
	 */
	public static long myPowWithMod(long kisu, long josu, long primeNumMod_0) {

		long ans = 1;

		//乗数が0の場合→1
		if (josu == 0)
			return 1;

		if (primeNumMod_0 == 0) {
			//modを使わないとき

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= kisu;
					josu = josu / 2;
				} else {
					//累乗が奇数の時
					ans *= kisu;
					josu--;
				}
			}

			return ans;

		} else {
			//modを使うとき

			//初めに桁を落とす
			kisu = myMod(kisu, primeNumMod_0);

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= myMod(kisu, primeNumMod_0);
					josu = josu / 2;

				} else {
					//累乗が奇数の時
					ans *= myMod(kisu, primeNumMod_0);
					josu--;

				}
			}

			return myMod(ans, primeNumMod_0);

		}

	}

}


Measured memory_bytes: 27040
#include <bits/stdc++.h>
using namespace std;
int main(void){
  string s,t;
  cin>>s;
  cin>>t;
  int m=0;
  for(int i=0;i<3;i++){
    if(s[i]==t[i])m++;
  }
  cout<<m<<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 i = sc.nextInt();
		int rc = i * (i - 1) / 2;
		int ten[] = new int[i];
		for(int j = 0; j < i; j++){
			ten[j] = 0;
		}
		for(int j = 0; j < rc; j++){
			int team1 = sc.nextInt();
			int team2 = sc.nextInt();
			int score1 = sc.nextInt();
			int score2 = sc.nextInt();
			if(score1 > score2){
				ten[team1-1] = ten[team1-1] + 3;
			}else if(score1 < score2){
				ten[team2-1] = ten[team2-1] + 3;
			}else if(score1 == score2){
				ten[team1-1] = ten[team1-1] + 1;
				ten[team2-1] = ten[team2-1] + 1;
			}
		}
		for(int j = 0; j < i; j++){
			int rank = i;
			for(int k = 0; k < i; k++){
				if(j == k){
					continue;
				}else if(ten[j] >= ten[k]){
					rank = rank - 1;
				}
			}
			System.out.println(rank);
		}
	}
}

Measured memory_bytes: 42264
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,n) for (int i = 0; i < (n); ++i)
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 ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;cin >> n >> k;
    vector<vector<ll>> a(n);
    for(int i=0;i<n;i++){
        ll t,d;cin >> t >> d;
        t--;
        a[t].push_back(d);
    } 
    for(int i=0;i<n;i++){
        if(a[i].size()!=0){
            sort(a[i].begin(),a[i].end(),greater<ll>());
        }
        else{
            a[i].push_back(-inf);
        }
    }
    sort(a.begin(),a.end(),[&](auto x,auto y){return x[0]>y[0];});
    priority_queue<ll> pq;
    ll sum=0;
    for(int i=0;i<k;i++){
        sum+=a[i][0];
        for(int j=1;j<a[i].size();j++){
            pq.push(a[i][j]);
        }
    }
    for(int i=k;i<n;i++){
        for(int j=0;j<a[i].size();j++){
            pq.push(a[i][j]);
        }
    }
    ll ans=sum+k*k;
    for(ll i=k-1;i>=1;i--){
        ll u=a[i][0],v=pq.top();
        if(u<v){
            pq.pop();
            pq.push(u);
            sum+=v;
            sum-=u;
        }
        chmax(ans,sum+i*i);
    }
    cout << ans << endl;
}

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

class Procon {
  public Procon () { }
  static void Main (string[] agrs) {
    new Procon ().Do ();
  }

  Scanner cin;

  public void Do () {
    cin = new Scanner ();
    int H = cin.nextInt ();
    int W = cin.nextInt ();
    int h = cin.nextInt ();
    int w = cin.nextInt ();

    Console.WriteLine ((H - h) * (W - w));
  }
}

class Scanner {
  string[] s;
  int i;
  int max_i;

  public Scanner () {
    s = new string[0];
    max_i = 0;
    i = 0;
  }

  public string nextString () {
    if (i >= s.Length) {
      s = Console.ReadLine ().Split (' ');
      max_i = s.Length;
      i = 0;
      if (max_i == 0) {
        return "";
      }
      return s[i++];
    } else {
      return s[i++];
    }
  }

  public int nextInt () {
    return int.Parse (nextString ());
  }

  public long nextLong () {
    return long.Parse (nextString ());
  }

  public double nextDouble () {
    return double.Parse (nextString ());
  }

  public string[] arrayString () {
    return Console.ReadLine ().Split (' ');
  }

  public int[] arrayInt () {
    string[] str = Console.ReadLine ().Split (' ');
    int[] array = new int[str.Length];
    for (int i = 0; i < str.Length; i++) {
      array[i] = int.Parse (str[i]);
    }
    return array;
  }

  public long[] arrayLong () {
    string[] str = Console.ReadLine ().Split (' ');
    long[] array = new long[str.Length];
    for (int i = 0; i < str.Length; i++) {
      array[i] = long.Parse (str[i]);
    }
    return array;
  }

  public double[] arrayDouble () {
    string[] str = Console.ReadLine ().Split (' ');
    double[] array = new double[str.Length];
    for (int i = 0; i < str.Length; i++) {
      array[i] = double.Parse (str[i]);
    }
    return array;
  }
}

Measured memory_bytes: 13140
//! ----------------------------------------------
//! Framework <https://github.com/vain0x/procon>
//!
//! See the bottom of file for solution.
//! ----------------------------------------------

#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Display, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

/// Print values to standard error if debug mode.
#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), stderr());
            writeln!(err, "\x1B[33m{}\x1B[0m = {:?}", e, $e).unwrap()
        })*
    };
}

/// Read from standard input and parse each word.
/// - `read!(T, U, ..)` parses a line as a tuple of words.
/// - `read![[T]]` parses a line as an array of words.
/// - `read![..; N]` parses `N` lines, using `read!(..)` repeatedly.
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

/// Read a line from standard input.
#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();

    #[allow(deprecated)]
    buf.trim_right().to_owned()
}

// -----------------------------------------------
// Solution
// -----------------------------------------------

pub fn gcd(x: i64, y: i64) -> i64 {
    if y == 0 {
        x.abs()
    } else {
        gcd(y, x % y)
    }
}

fn main() {
    let (N, X) = read!(usize, i64);
    let x = read![[i64]];

    let mut g = 0;
    for i in 0..N {
        g = gcd(g, (x[i] - X).abs());
    }

    println!("{}", g)
}


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

mod = 10**9+7

tmp = 0
for i in range(N):
    tmp += A[i]
    tmp = tmp % mod
all = (tmp % mod)**2
all = all % mod

tmp = 0
for i in range(N):
    tmp += (A[i]* A[i]) % mod
di = tmp % mod

ans = all - di
ans *= (mod + 1) // 2
ans %= mod

print(ans)

Measured memory_bytes: 30992
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{


	public static void main(String[] args){

		BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));

		try{
		for(int i=1;;i++){
			int x=Integer.parseInt(reader.readLine());
			if(x==0)break;
			System.out.println("Case "+i+": "+x);

		}
		}catch(IOException e){
			System.out.println("??¨??????:"+e);

		}

	}

}

Measured memory_bytes: 32008
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

N, M = MAP()

LR = [LIST() for _ in range(M)]
LR = np.transpose(LR)

print(min(LR[1]) - max(LR[0]) + 1 if min(LR[1]) >= max(LR[0]) else 0)

Measured memory_bytes: 38844
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (1<<25)

struct P{
	int x,y;
	P(int a,int b){x = a , y = b;}
	P(){}
};
struct NODE{
	int x,y,cost,cur,id;
	NODE(P a,int c,int d,int b){
		x = a.x , y = a.y , cost = c , cur = d , id = b;
	}
};
bool operator<(const NODE &a,const NODE &b){
	return a.cost > b.cost;
}
#define next(n) ((n+1)%5)

int getCost(P a,P b){
	return abs(a.x-b.x)+abs(a.y-b.y);
}
int main(){
	int W,H;
	while(cin >> W >> H,W){
		vector<P> pos[5];
		P goal,start;
		rep(i,H)rep(j,W){
			char c;
			cin >> c;
			if(c == 'S')start = P(j,i);
			else if(c == 'G')goal = P(j,i);
			else if(c != '.')pos[c-'1'].push_back(P(j,i));
		}
		int ans = INF , choice = -1;
		rep(X,5){
			queue<NODE> Q;
			Q.push(NODE(start,0,X,1023));
			int memo[5][1024];
			rep(i,5)rep(j,1024) memo[i][j] = INF;
			while(Q.size()){
				NODE q = Q.front(); Q.pop();
				
				if(q.cost > memo[q.cur][q.id] )continue;
				if(next(q.cur) == X){
					int lastCost = q.cost+getCost(P(q.x,q.y),goal);
					if( lastCost < ans ){
						ans = lastCost;
						choice = X;
					}
					continue;
				}
				
				if( next(q.cur) == X){
					Q.push(NODE(goal,q.cost+getCost(P(q.x,q.y),goal),-1,1023));
					continue;
				}
				rep(i,pos[next(q.cur)].size()){
					NODE t = NODE(pos[next(q.cur)][i] , q.cost+getCost(P(q.x,q.y),pos[next(q.cur)][i]) , next(q.cur) , i);
					if( t.cost < memo[t.cur][t.id]){
						memo[t.cur][t.id] = t.cost;
						Q.push(t);
					}
				}
			}
		}
		if(~choice)cout << choice+1 << " " << ans << endl;
		else cout << "NA" << endl; 
	}
}

Measured memory_bytes: 2004
#include<stdio.h>

int main(){
    int a,i,j,n,x;
    for(;;){
    int b=0;
    scanf("%d%d",&n,&x);
    if(n==0&&x==0)break;

    for(i=1;i<n-1;i++){
	for(j=i+1;j<n;j++){
	    a =x-i-j;
	    if(j<a&&a<=n)b+=1;
	}
    }
    printf("%d\n",b);
    }
    return 0;
}




Measured memory_bytes: 2056
n,q=map(int, input().split())

tasks=[]

for i in range(n):
  task, time =input().split()
  time=int(time)
  tasks.append([task, time])

total_time=0

flag=1
while flag==1:
  flag=0
  del_index=[]
  for i in range(len(tasks)):
    if tasks[i][1]>q:
      tasks[i][1]-=q
      flag=1
      total_time+=q  
    else:
      total_time+=tasks[i][1]
      tasks[i][1]=0
      print(tasks[i][0], total_time)
      del_index.append(i)
  for i in reversed(del_index):
    del tasks[i]


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

ll mod_pow(ll x, ll p, int MOD){
	ll res=1;
	ll n=x;
	while(p>0){
		if(p&1==1)res=(res*n)%MOD;
		n=(n*n)%MOD;
		p=(p>>1);
	}
	return res;
}

int main() {
    int K;
    cin>>K;
    if(K%2==0||K%5==0){
        cout<<-1<<endl;
        return 0;
    }
    if(K%7==0)K/=7;
    for (int i = 1; i <= K; i++){
        int MOD=K*9;
        if((mod_pow(10,i,MOD)-1)%MOD==0){
            cout<<i<<endl;
            break;
        }
    }
}

Measured memory_bytes: 3572
def way7(ball, box):
    """ball: True / box: False / constraints: None
    -> ans = B(ball, box)  Bはベル数 / 計算量 O(ball * box)
    """
    # B[i][j] := S[i][j] + S[i][j - 1] + ... + S[i][0]
    # S[i][j] := i個(区別する)をkグループ(区別しない)に分ける場合の数
    S = [[0] * (box + 1) for i in range(ball + 1)] 
    S[0][0] = 1
    for i in range(ball):
        for j in range(box):
            S[i + 1][j + 1] = S[i][j] + S[i][j + 1] * (j + 1)
            S[i + 1][j + 1] %= MOD

    B_ij = sum(S[ball][0:box + 1]) % MOD
    return B_ij


n, k = map(int, input().split())
MOD = 10 ** 9 + 7

print(way7(n, k))


Measured memory_bytes: 29356
import sys

input = sys.stdin.readline


def main():
    N, H, W = map(int, input().split())
    ans = 0
    for _ in range(N):
        A, B = map(int, input().split())
        if H <= A and W <= B:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9124
#include<bits/stdc++.h>
using namespace std;
#define stop exit(0)
#define pb push_back
#define skip continue
#define ll long long
long long a,b,c,d=0,e=0,i,f=0,g=0,j,k=0,l=0,r,z,m,p,df[101],mod=1000000007;
string t,x,q,s;
//double ;
vector<ll>v,u,w,dv[101];
//vector<string>;
map<string,ll>n;
set<ll>y;
void dfs(ll x){
    df[x]=1;
    for(ll i=0;i<dv[x].size();i++){
        if(df[dv[x][i]]==0){
            df[dv[x][i]]=1;
            dfs(dv[x][i]);
        }
    }
}
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin>>a;
    if(a==1){
        cout<<0;
        stop;
    }
    d=1;
    for(i=1;i<=a;i++){
        d=d*10%mod;
    }
    e=1;
    f=1;
    //0,9 ogui 64
    //0 ogui 81
    //9 ogui 81
    for(i=1;i<=a;i++){
        e=e*8%mod;
        f=f*9%mod;
    }
    f=((f+mod)-e)%mod;
    f=f*2%mod;
    e=(e+f)%mod;
    cout<<(d+mod-e)%mod;
}

Measured memory_bytes: 3640
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define fi first
#define se second
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	int n, k, q;
	cin >> n >> k >> q;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	int ans = INF;
	rep(i, n) {
		vector<int> ok;
		multiset<int> st;
		rep(j, n) {
			if (a[j] < a[i]) st.clear();
			else {
				st.insert(a[j]);
				if (st.size() >= k) {
					auto p = st.begin();
					ok.pb(*p);
					p = st.erase(p);
				}
			}
		}
		if (ok.size() >= q) {
			sort(all(ok));
			chmin(ans, ok[q - 1] - ok[0]);
		}
	}
	cout << ans << endl;
}

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

const int M = 1e9+7;
typedef vector<int> row;
typedef vector<row> matrix;

matrix operator*(const matrix&a, const matrix &b) {
    int n = a.size();
    int p = b.size();
    int m = b[0].size();

    matrix ans(n, row(m));
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            for (int k=0; k<p; k++)
                ans[i][j] = (ans[i][j] + 1LL*a[i][k]*b[k][j])%M;
    return ans;
}

matrix unit(int n) {
    matrix ans(n, row(n));
    for (int i=0; i<n; i++)
        ans[i][i] = 1;
    return ans;
}

matrix power(const matrix &a, long long p) {
    if (p == 0)     return unit(a.size());
    matrix ans = power(a, p/2);
    ans = ans * ans;
    if (p%2)        ans = ans*a;
    return ans;
}

const int N = 1005;
string s[N];

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

    int n, m;
    long long k;
    cin>>n>>m>>k;

    for (int i=0; i<n; i++)     cin>>s[i];

    int black = 0, hor = 0, ver = 0, wraphor = 0, wrapver = 0;

    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (s[i][j] == '.') continue;
            black++;
            if (i)      ver += s[i-1][j]=='#';
            else        wrapver += s[n-1][j] == '#';
            if (j)      hor += s[i][j-1]=='#';
            else        wraphor += s[i][m-1] == '#';
        }
    }

    if (k == 0)             cout<<1<<endl;
    else if (wraphor && wrapver) cout<<1<<endl;
    else {
        matrix base(2, row(2));
        base[0][0] = black;

        if (wraphor == 0)   hor = 0;
        if (wrapver == 0)   ver = 0;

        if (wraphor) {
            base[0][1] = M-hor;
            base[1][1] = wraphor;
        }
        else {
            base[0][1] = M-ver;
            base[1][1] = wrapver;
        }
        matrix ans = power(base, k-1);

        cout<<(ans[0][0] + ans[0][1])%M;
    }
}


Measured memory_bytes: 4744
<?php
$card_count = trim(fgets(STDIN));
$card_array_s = array("S 1","S 2","S 3","S 4","S 5","S 6","S 7","S 8","S 9","S 10","S 11","S 12","S 13");
$card_array_h = array("H 1","H 2","H 3","H 4","H 5","H 6","H 7","H 8","H 9","H 10","H 11","H 12","H 13");
$card_array_c = array("C 1","C 2","C 3","C 4","C 5","C 6","C 7","C 8","C 9","C 10","C 11","C 12","C 13");
$card_array_d = array("D 1","D 2","D 3","D 4","D 5","D 6","D 7","D 8","D 9","D 10","D 11","D 12","D 13");
while($input = trim(fgets(STDIN))){
    sscanf($input,'%c %d',$kind,$number);
    switch ($kind) {
        case 'S':
            unset($card_array_s[$number-1]);
            break;
        case 'H':
            unset($card_array_h[$number-1]);
            break;
        case 'C':
            unset($card_array_c[$number-1]);
            break;
        case 'D':
            unset($card_array_d[$number-1]);
            break;
    }
}
if (count($card_array_s)>0) echo implode($card_array_s,PHP_EOL),PHP_EOL;
if (count($card_array_h)>0) echo implode($card_array_h,PHP_EOL),PHP_EOL;
if (count($card_array_c)>0) echo implode($card_array_c,PHP_EOL),PHP_EOL;
if (count($card_array_d)>0) echo implode($card_array_d,PHP_EOL),PHP_EOL;

Measured memory_bytes: 15348
#include <stdio.h>
int main(){
  int po[100][3],to[100],num=-1;
  int i,j;
  while(1){
    num=num+1;
    scanf("%d %d %d",&po[num][0],&po[num][1],&po[num][2]);
    if(po[num][0]==-1&&po[num][1]==-1&&po[num][2]==-1)break;
  }
  for(i=0; i<num; i++){
    to[i]=po[i][0]+po[i][1];
    if((po[i][0]+po[i][1])<30||po[i][0]==-1||po[i][1]==-1)printf("%c\n",'F');
    else if((po[i][0]+po[i][1])>=80)printf("%c\n",'A');
    else if(to[i]>=65&&to[i]<80)printf("%c\n",'B');
    else if(to[i]>=50&&to[i]<65)printf("%c\n",'C');
    else if(to[i]>=30&&to[i]<50&&po[i][2]>=50)printf("%c\n",'C');
    else printf("%c\n",'D');
  }
  return 0;
}



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

int n, k;
int a[10];
int v[10000] = {};
int s;

void set_vec(int t, int f, int sum) {
	if(t>=k) {
		v[s] = sum;
		s++;
	}else {
		for(int i=0;i<n;i++) {
			if((1<<i) & f)continue;
			set_vec(t+1, f+(1<<i), sum*(a[i]<10?10:100)+a[i]);
		}
	}
}

int main() {
	
	while(1) {
		scanf("%d", &n);
		scanf("%d", &k);
		if(n==0 && k==0)break;
		s = 0;
		for(int i=0;i<n;i++) {
			scanf("%d", &a[i]);
		}
		
		set_vec(0, 0, 0);
		
		sort(v, v+s);
		
		int t = 0;
		int sum = 0;
		
		for(int i=0;i<s;i++) {
			if(t==v[i])continue;
			sum++;
			t=v[i];
		}
		
		printf("%d\n", sum);
		
	}
	
	return  0;
}

Measured memory_bytes: 1064
def swap(m, n, items):
    x = items[n]
    items[n] = items[m]
    items[m] = x
    

ABC = input().split()

if ABC[0] > ABC[1]:
    swap(0, 1, ABC)
    if ABC[1] > ABC[2]:
        swap(1, 2, ABC)
        if ABC[0] > ABC[1]:
            swap(0, 1, ABC)
elif ABC[1] > ABC[2]:
    swap(1, 2, ABC)
    if ABC[0] > ABC[1]:
        swap(0, 1, ABC)
print(ABC[0], ABC[1], ABC[2])

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

typedef long long ll;
const int MAX_N = 60;

int n, k;

int X1[60], Y1[60], Z1[60];
int X2[60], Y2[60], Z2[60];

vector<ll> x, y, z;

int main()
{
  cin >> n >> k;
  for (int i = 0; i < n; i++){
    cin >> X1[i] >> Y1[i] >> Z1[i] >> X2[i] >> Y2[i] >> Z2[i];
    x.push_back(X1[i]);
    x.push_back(X2[i]);
    y.push_back(Y1[i]);
    y.push_back(Y2[i]);
    z.push_back(Z1[i]);
    z.push_back(Z2[i]);
  }

  sort(x.begin(), x.end());
  sort(y.begin(), y.end());
  sort(z.begin(), z.end());

  ll ans = 0;
  for (int X = 0; X < x.size() - 1; X++){
    for (int Y = 0; Y < y.size() - 1; Y++){
      for (int Z = 0; Z < z.size() - 1; Z++){
        int cnt = 0;
        for (int i = 0; i < n; i++){
          if (X1[i] <= x[X] && x[X + 1] <= X2[i] &&
              Y1[i] <= y[Y] && y[Y + 1] <= Y2[i] &&
              Z1[i] <= z[Z] && z[Z + 1] <= Z2[i]) cnt++;
        }

        if (cnt >= k){
          ans += (x[X + 1] - x[X]) * (y[Y + 1] - y[Y]) * (z[Z + 1] - z[Z]);
        }
      }
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 3100
#include <bits/stdc++.h>
#define ll long long
#define cwk freopen("D:\\c++\\in.txt","r",stdin),freopen("D:\\c++\\out.txt","w",stdout)
using namespace std;
const int N=1e6+10;
int gs[N];
int arr[N];
ll cnt[N];
int n;
ll js(int x) {
	return 1ll*x*(x-1)/2;
}
int main()
{
	//cwk;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&arr[i]);
	}
	for(int i=2;i<=n;i++) {
		gs[arr[i]]++;
	}
	ll ans=0;
	for(int i=1;i<=n;i++) {
		cnt[i]=js(gs[i]);
		ans+=cnt[i];
	}
	printf("%lld\n",ans);
	for(int i=2;i<=n;i++) {
		int id1=arr[i-1],id2=arr[i];
		ans-=js(gs[id1]);
		gs[id1]++;
		ans+=js(gs[id1]);
		ans-=js(gs[id2]);
		gs[id2]--;
		ans+=js(gs[id2]);
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 12288
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i, n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i, n) for(ll i=(ll)(n-1);i>=0;i--)
#define FOR(i, a, b) for(ll i=(ll)(a); i<=(ll)(b); i++)
#define RFOR(i, a, b) for(ll i=(ll)(a);i>=(ll)(b); i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

ll dp[111111];

signed main()
{
	int N, K;
	cin >> N >> K;
	vector<ll> h(N);
	REP(i, N){
		cin >> h[i];
		dp[i] = INF;
	}
	dp[0] = 0;
	FOR(i, 1, N-1){
		FOR(k, 1, K){
			if(i-k<0)break;
			dp[i] = min(dp[i], dp[i-k]+abs(h[i]-h[i-k]));
		}
	}
	cout << dp[N-1] << endl;
}


Measured memory_bytes: 4840
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <complex>
#include <bitset>
#include <functional>

using namespace std;
using ll=long long int;

int main() {
    int h, w, k;
    cin >> h >> w >> k;
    vector<string> m(h);
    for (auto &e: m) cin >> e;

    vector<vector<int>> ans(h, vector<int>(w));
    auto draw = [&](int x, int y1, int y2, int n) {
        for (int i = y1; i < y2; ++i) ans[x][i] = n;
    };

    vector<int> par(h+1);
    par[0] = 0;
    vector<vector<int>> ss(h+1);
    for (int i = 1; i <= h; ++i) {
        if (count(m[i-1].begin(), m[i-1].end(), '#') == 0) par[i] = par[i-1];
        else par[i] = i;
        ss[par[i]].push_back(i);
    }

    int fs = find_if(par.begin(), par.end(), [](int x){return x != 0;}) - par.begin();
    for (auto &e: ss[0]) ss[fs].push_back(e);

    int id = 1;
    for (int i = 0; i < h; ++i) {
        int last = -1;
        if (par[i+1] != i+1) continue;
        for (int j = 0; j < w; ++j) {
            if (m[i][j] != '#') continue;
            draw(i, last+1, j+1, id);
            for (auto &e: ss[i+1]) draw(e-1, last+1, j+1, id);
            last = j;
            id++;
        }
        draw(i, last+1, w, id-1);
        for (auto &e: ss[i+1]) draw(e-1, last+1, w, id-1);
    }

    for (auto &r: ans) {
        for (auto &e: r) cout << e << " ";
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 1280
// #include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <map>
#include <math.h>
#include <algorithm> // std::sort, std::min, std::next_permutation, std::lower_bound
#include <iomanip> // std::setprecision
#include <cmath> // std::ceil
#include <numeric> // std::gcd, std::lcm
#include <limits> // std::numeric_limits<long int>::max()
#include <unordered_map>
#include <map>
#include <cmath> // std::atan2

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

int main() {
  ll N;
  cin >> N;
  vector<ll> a(N + 1);
  for (int i=1; i<N+1; ++i) cin >> a[i];

  ll M = 0;
  vector<ll> b(N + 1, 0);
  for (int i=N; i>0; --i) {
    ll j = i;
    ll sumj = 0;
    while (j < N+1) {
      sumj += b[j];
      j += i;
    }
    if (sumj%2 == a[i]) {
      b[i] = 0;
    }
    else {
      b[i] = 1;
      M += 1;
    }
  }
  
  cout << M << endl;
  for(int i=1; i<N+1; ++i) {
    if (b[i] == 1) cout << i <<" ";
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 3968
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

namespace io {
#define gc() (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
	const int SIZ = 1 << 21 | 1;
	char *iS, *iT, ibuff[SIZ], obuff[SIZ], *oS = obuff, *oT = oS + SIZ - 1, fu[110], c;
	int fr;
	inline void out() {
		fwrite(obuff, 1, oS - obuff, stdout);
		oS = obuff;
	}
	template<class Type>
	inline void read(Type &x) {
		x = 0;
		Type y = 1;
		for (c = gc(); (c > '9' || c < '0') && c != '-'; c = gc());
		c == '-' ? y = -1 : x = (c & 15);
		for (c = gc(); c >= '0' && c <= '9'; c = gc())
			x = x * 10 + (c & 15);
		x *= y;
	}
	template<class Type>
	inline void print(Type x, char text = '\n') {
		if (x < 0)
			*oS++ = '-', x *= -1;
		if (x == 0)
			*oS++ = '0';
		while (x)
			fu[++fr] = x % 10 + '0', x /= 10;
		while (fr)
			*oS++ = fu[fr--];
		*oS++ = text;
		out();
	}
}
using namespace io;
#define ll long long
const int maxn = 100010;

int n, m, a, b;
int col[maxn + 5], lnk[maxn + 5], son[maxn << 1], nxt[maxn << 1];
int u;

inline void Add(int x, int y) {
	son[++u] = y;
	nxt[u] = lnk[x];
	lnk[x] = u;
}

void dfs(int x, int now = 0, int fa = 0) {
	col[x] = now; now ^= 1;
	for (int j = lnk[x]; j; j = nxt[j]) {
		if (col[son[j]] == -1)
			dfs(son[j], now, x);
		if (col[son[j]] != now)
			print((ll)n*(n - 1) / 2 - m), exit(0);
	}
}

int main() {
	read(n);
	read(m);
	memset(col, 255, sizeof(col));
	for (int i = 1, x, y; i <= m; i++)
		read(x), read(y), Add(x, y), Add(y, x);
	dfs(1);
	for (int i = 1; i <= n; i++)
		col[i] ? ++a : ++b;
	print((ll)a * b - m);
	return 0;
}

Measured memory_bytes: 6656
from collections import deque
def main():
    h,w = map(int,input().split())
    grid = []
    dq = deque([])
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    ans = 0
    d = [[-1 for i in range(w)] for j in range(h)]
    for i in range(h):
        maze = list(input())
        for j in range(w):
            if maze[j] == "#":
                dq.append((j,i))
                d[i][j] = 0
        grid.append(maze)
    while dq:
        x,y = dq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx <= w-1 and 0 <= ny <= h-1 and grid[ny][nx] != "#" and d[ny][nx] == -1:
                dq.append((nx,ny))
                d[ny][nx] = d[y][x] + 1
                ans = max(ans,d[ny][nx])
    print(ans)
main()

Measured memory_bytes: 125020
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;

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

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main(){
  int n, w;
  cin >> n >> w;
  vector<int> a(n), b(n);
  rep(i,n) cin >> a[i] >> b[i];
  vector<vector<int>> dp(n+1, vector<int>(1e5+1, 1e9+1));
  dp[0][0]=0;
  for(int i=1; i<=n; i++){
    rep(j,1e5+1){
      chmin(dp[i][j], dp[i-1][j]);
      if(j-b[i-1]>=0)
        chmin(dp[i][j], dp[i-1][j-b[i-1]]+a[i-1]);
    }
  }
  int ans=0;
  rep(i,1e5+1){
    if(dp[n][i] <= w)
      ans = max(ans, i);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 40192
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define vl vector<long long int>
#define vvl vector<vector<ll> > 
#define fo(i,a,b) for(int i=a;i<b;i++)
#define rof(i,a,b)  for(int i=b;i>=a;i--)
#define mod 1000000007
using namespace std;
int main()
{
    ios_base:: sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
    ll n,k;cin>>n>>k;
    ll a[n+1],dp[n+1][k+1];
    memset(dp,0,sizeof(dp));
    fo(i,1,n+1)
        cin>>a[i],dp[i][0]=1;
    dp[0][0]=1;
    fo(i,1,n+1)
    {
        for(ll j=1;j<=k;j++)
        {
            dp[i][j] = (dp[i-1][j]+dp[i][j-1])%mod;
            if(j>a[i])
                dp[i][j]= (dp[i][j] - dp[i-1][j-a[i]-1]+mod)%mod;
            if(dp[i][j]<0)
                dp[i][j]=0;
            //cout << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    cout << dp[n][k];
}



Measured memory_bytes: 82420
N = gets.to_i
D, X = gets.split.map(&:to_i)
A = N.times.map{gets.to_i}

dp = Array.new(D + 1, 0)
dp[0] = X
A.each do |a|
  (0 .. D).each do |x|
    break if a * x + 1 > D
    dp[a * x + 1] += 1
  end
end
puts dp.inject(0, &:+)


Measured memory_bytes: 1916
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
using namespace std;

typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vint;
typedef vector<uint> vuint;
typedef vector<ull> vull;
typedef vector<ll> vll;

#define init(type,var) type var;cin>>var;
#define vinit(type,var,n) vector<type> var((uint)n);loop(i,0,n)cin>>var[i];
#define linit(type,var,n) list<type> var;loop(i,0,n){type _v;cin>>_v;var.push_back(_v);}
#define range(container) container.begin(),container.end()
#define loop(i,first,end) for(ull i=(first);i<(end);i++)
#define outl(out) cout<<(out)<<endl;

const ull INF = (ull)(-1LL);

typedef ull aint;

typedef vector<aint> vaint;
typedef list<aint> laint;

int main(void){
	init(aint, h);
	init(aint, w);
	init(aint, k);
	vector<vaint> cake(h, vaint(w, 0));

	aint _k = 0;
	loop(i, 0, h){
		loop(j, 0, w){
			char c;
			cin >> c;
			if (c == '#')cake[i][j] = (++_k);
		}
	}

	vector<bool> checked(k + 1);
	checked[0] = true;

	loop(i, 0, h){
		loop(j, 0, w){
			if(checked[cake[i][j]])continue;
			ll _j;
			_j = j;
			while (--_j >= 0 && cake[i][_j] == 0)cake[i][_j] = cake[i][j];
			_j = j;
			while (++_j < w && cake[i][_j] == 0)cake[i][_j] = cake[i][j];
			j = _j - 1;
			ll _i = i;
			bool e = true;
			while (e && (++_i) < h){
				for (_j = j; e && _j >= 0 && cake[i][_j] == cake[i][j]; _j--)e = (cake[_i][_j] == 0);
				if (e)for (_j = j; e && _j >= 0 && cake[i][_j] == cake[i][j]; _j--)cake[_i][_j] = cake[i][j];
				else break;
			}
			_i = i;
			e = true;
			while (e && (--_i) >= 0){
				for (_j = j; e && _j >= 0 && cake[i][_j] == cake[i][j]; _j--)e = (cake[_i][_j] == 0);
				if (e)for (_j = j; e && _j >= 0 && cake[i][_j] == cake[i][j]; _j--)cake[_i][_j] = cake[i][j];
				else break;
			}
			checked[cake[i][j]] = true;
		}
	}
	
	loop(i, 0, h){
		loop(j, 0, w){
			cout << cake[i][j] << ' ';
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,a[666],cnt,dp[2][666][666],la,nw;
bool u[666],c[666];
long long ans;
void add(int &a,int b)
{
	a+=b;
	if (a>=mod) a-=mod;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=2*n;i++) scanf("%d",&a[i]);
	for (int i=1;i<2*n;i+=2)
	{
		if (a[i]==-1 && a[i+1]==-1) cnt++;
		else if (a[i]!=-1 && a[i+1]!=-1)
		{
			u[a[i]]=u[a[i+1]]=1;
		}
		else if (a[i]!=-1) c[a[i]]=1;
		else c[a[i+1]]=1;
	}
	nw=1;
	dp[la][0][0]=1;
	for (int i=2*n;i>=1;i--)
	{
		if (u[i]) continue;
		memset(dp[nw],0,sizeof(dp[nw]));
		for (int j=0;j<=2*n;j++)
		{
			for (int k=0;k<=2*n;k++)
			{
				if (!dp[la][j][k]) continue;
				if (c[i])
				{
					add(dp[nw][j][k+1],dp[la][j][k]);
					if (j>=1) add(dp[nw][j-1][k],dp[la][j][k]);
				}
				else
				{
					add(dp[nw][j+1][k],dp[la][j][k]);
					if (j>=1) add(dp[nw][j-1][k],dp[la][j][k]);
					if (k>=1) add(dp[nw][j][k-1],(long long)k*(long long)dp[la][j][k]%mod);
				}
			}
		}
		nw^=1;la^=1;
	}
	ans=(long long)dp[la][0][0];
	for (long long i=1;i<=cnt;i++) ans=ans*i%mod;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3712
{-# LANGUAGE BangPatterns #-}
import Data.Int
import Control.Monad
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as VM

solve :: Int -> Int -> V.Vector (Int,Int) -> V.Vector Int64
solve n m edges = V.create $ do
  -- m 番目の島から順番に島同士が「繋がっていく」と考える

  -- j = assocs ! i : i 番目の島の親が j
  -- assocs <- VM.new n
  -- forM_ [0..n-1] $ \i -> VM.write assocs i i
  assocs <- V.thaw $ V.enumFromN 0 n

  -- numberOfElements ! i : i番目の島と同じ連結成分に属する島の個数
  numberOfElements <- VM.replicate n 1

  rank <- VM.replicate n (0 :: Int)

  let getRoot i xs = do
        j <- VM.read assocs i
        if i == j
          then forM_ xs (\l -> VM.write assocs l i) >> return i
          else getRoot j (i:xs)

      -- i 番目の島と j 番目の島を繋いで、新たに繋がった組み合わせの個数を返す
      unify i j = do
        i' <- getRoot i []
        j' <- getRoot j []
        if i' == j'
          then return 0
          else do
          ri <- VM.read rank i'
          rj <- VM.read rank j'
          k <- case compare ri rj of
                 EQ -> do VM.write rank i' (ri + 1)
                          return i'
                 LT -> return j'
                 GT -> return i'
          VM.write assocs i' k
          VM.write assocs j' k
          n1 <- VM.read numberOfElements i'
          n2 <- VM.read numberOfElements j'
          VM.write numberOfElements k (n1 + n2)
          return $! n1 * n2
  result <- VM.new m
  VM.write result (m-1) $ fromIntegral n * (fromIntegral n - 1) `quot` 2
  forM_ [m-1,m-2..1] $ \i -> do
    let (a,b) = edges V.! i
    convenience <- unify a b
    prevInconveniences <- VM.read result i
    VM.write result (i-1) (prevInconveniences - convenience)
  return result

main = do
  [n,m] <- map read . words <$> getLine -- 2 <= n <= 10^5, 1 <= m <= 10^5
  edges <- V.replicateM m $ do
    [a,b] <- map read . words <$> getLine
    return (a-1, b-1)
  -- maxIncovenience < n * (n - 1) / 2 < 10^10 (2^32 < 10^10)
  let result = solve n m edges
  V.forM_ result print


Measured memory_bytes: 7036
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define _LIBCPP_DEBUG 0
using namespace std;
int64_t MOD = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int64_t a, b, k;
  cin >> a >> b >> k;
  if(k <= a) cout << a - k << " " << b << endl;
  else if(k <=  a + b) cout << 0 << " " << b - (k - a) << endl;
  else cout << 0 << " " << 0 << endl;
  return 0;
}
//templete by private_yusuke

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod = 1000000007;
char grid[1002][1002];
int solve(int n , int m){
    int dp[n+1][m+1];  // number of paths starting at (i , j) and ending at (n , m)
    dp[n][m] = 1;
    for(int i=n ; i>=1 ; i--){
        for(int j=m ; j>=1 ; j--){
            if(i==n && j==m){
                continue;
            }
            if(grid[i][j] == '#'){
                dp[i][j] = 0;
            }else{
                dp[i][j] = (((i == n)? 0 : dp[i+1][j]) + ((j == m)? 0 : dp[i][j+1]))%mod;
            }
        }
    }
    return dp[1][1];
}
int main(){
    int n , m;
    cin>>n>>m;
    for(int i=1;  i<=n ; i++){
        for(int j=1 ; j<=m ; j++){
            cin>>grid[i][j];
        }
    }
    cout<<solve(n , m);
return 0;
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int MAXN = 100100;

int K, N;

pair <int, int> pp[MAXN];

int main()
{
    ios_base::sync_with_stdio(0);
    cin >> K >> N;
    if (N > (K + 1) / 2)
    {
        cout << "-1\n";
        return 0;
    }

    int lo = K / 2;
    for (int i = 0; i < lo; i++)
    {
        int nv = (i + K - lo) + (N + K);
        pp[i] = make_pair (nv + i + N, i + N);
    }
    for (int i = lo; i < K; i++)
    {
        int nv = (i - lo) + (N + K);
        pp[i] = make_pair (nv + i + N, i + N);
    }

    sort (pp, pp + K);
    for (int i = 0; i < K; i++)
    {
        cout << pp[i].second << " " << pp[i].first - pp[i].second << " " << (N + 2 * K + i) << "\n";
    }
}

Measured memory_bytes: 3072