akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
    public static void sort(int array[], int array2[], int left, int right){
        if(left <= right){
            int p = array[(left + right) >>> 1];
            int l = left;
            int r = right;
            while(l <= r){
                while (array[l] < p){
                    l++;
                }
                while (array[r] > p){
                    r--;
                }
                if (l <= r){
                    int tmp = array[l];
                    array[l] = array[r];
                    array[r] = tmp;
                    
                    int tmp2 = array2[l];
                    array2[l] = array2[r];
                    array2[r] = tmp2;
                    l++;
                    r--;
                }
            }
            Main.sort(array, array2, left, r);
            Main.sort(array, array2, l, right);
        }
    }
    
    public static void main(String args[]){
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        int c[] = new int[26];
        int s[][] = new int[n][26];
        int ind[] = new int[26];
        
        for(int i = 0; i < 26; i++){
            c[i] = stdIn.nextInt();
            ind[i] = i;
        }
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 26; j++){
                s[i][j] = stdIn.nextInt();
            }
        }
        
        Main.sort(c, ind, 0, 25);
        
        int rev[] = new int[26];
        
        for(int i = 25; i >= 0; i--){
            rev[i] = ind[25 - i] + 1;
        }
        
        int count = 0;
        boolean endFlag = false;
        
        while(true){
            for(int i = 13; i < n; i++){
                System.out.println(rev[i % 26]);
                count++;
                if(count == 365){
                    endFlag = true;
                    break;
                }
            }
            
            if(endFlag){
                break;
            }
            
            for(int i = 0; i < n; i++){
                System.out.println(rev[i % 26]);
                count++;
                if(count == 365){
                    endFlag = true;
                    break;
                }
            }
            
            if(endFlag){
                break;
            }
        }
        //System.out.println("XXXXXXXX");
    }
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define vec vector
#define pb push_back
#define ft first
#define sd second
#define all(vec) vec.begin(), vec.end()
#define endl "\n"

typedef pair<int, int> P;

const int MOD = 1e9 + 7;
const int INF = 1e9;
const int dx[4] = {1, 0,-1, 0};
const int dy[4] = {0, 1, 0,-1};

// char to int
int ctoi(char c) {if (c >= '0' && c <= '9') {return c - '0';}return 0;}

//--------------------------------------------------------//



int main(){

	//input and initialization//
	int x;
	cin >> x;

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



	return 0;
}

Measured memory_bytes: 3636
/*
   AOJ - ALDS_1_5_a
Date: 20181220
Author: Mikoron * ♡mikoiwate_351♡
*/

#include<stdio.h>


short solve(short p, short t);
short n, q, A[2000], Mi[2000];

int main(void) {
        short i;

        scanf("%hd", &n);
        for(i = 0; i < n; i++) {
                scanf("%hd", &A[i]);
        }

        scanf("%hd", &q);
        for(i = 0; i < q; i++) {
                scanf("%hd", &Mi[i]);
        }

        for(i = 0; i < q; i++) {
                if(solve(0,Mi[i]) == 1) printf("yes\n");
                else printf("no\n");
        }

        return 0;
}

short solve(short p, short t) {
        short res;

        //printf("before p = %hd : t = %hd : A[p] = %hd\n", p, t, A[p]);
        //printf("t - A[p] = %hd \n" ,t-A[p]);

        if(t == 0) {
                //printf("yes\n");
            return 1;
        }
        if(p > n) {
                //printf("no\n");
                return 0;
        }

        //printf("p = %hd : t = %hd : A[p] = %hd\n", p, t, A[p]);
        res = (solve(p + 1, t) || solve(p + 1, t - A[p]));
        return res;
}



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

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

int main(){
    int r, D, x;
    cin >> r >> D >> x;

    for(int i = 0;i < 10;i++){
        x = r * x - D;
        cout << x << endl;
    }
}

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


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

  int n,k,c;
  cin >> n >> k >> c;
  string s;
  cin >> s;
  vector<pair<int,int> > pre(n);  //働いた日数 最後に働いた日
  int cnt = 0;
  int lday = -10*c - 100;
  rep(i,n){
    if(s[i] == 'o') {
      cnt++;
      lday = i;
      int ind = -1;
      while(ind++ < c && (i < n)){
        pre[i++] = {cnt,lday};
      }
      i--;
    }
    else{
      pre[i] = {cnt,lday};
    }
  }
  vector<pair<int,int> > post(n);
  lday = n + 10*c + 100;
  cnt = 0;
  for(int i = n-1; i>=0;i--){
    if(s[i] == 'o') {
      cnt++;
      lday = i;
      int ind = -1;
      while(ind++ < c && (i >= 0)){
        post[i--] = {cnt,lday};
      }
      i++;
    }
    else{
      post[i] = {cnt,lday};
    }
  }

  rep(i,n){
    if(s[i]=='x') continue;
  //  cout << "day " << i+1 << endl;
    ll tot = 0;
    ll lday = -10 *c -100;
    if(i!=0){
       tot += pre[i-1].first;
       lday = pre[i-1].second;
       //cout << pre[i-1].first << endl;
    }
    if(i!=n-1){
      tot += post[i+1].first;
//      cout <<  post[i+1].first << endl;
      if(post[i+1].second - lday <=c){
        tot--;
//        cout << "out " << i+1 << endl;
      } 
    }
//    cout << tot << endl;
    if(tot < k) cout << i+1 << endl;
  }

  return 0;
    

}


Measured memory_bytes: 5012
END { load __FILE__ unless $stdin.eof? }

n = gets.to_i
x = gets.chomp.chars.map!(&:to_i)

c = x.count(1)
c0 = c + 1
m0 = x.inject(0) { |result, bit| (result * 2 + bit) % c0 }
c1 = c - 1
m1 = x.inject(0) { |result, bit| (result * 2 + bit) % c1 } if c1 > 0

y0 = 1
y1 = 1
x = x.reverse!.map! do |xi|
  xi = (
    if xi == 0
      (m0 + y0) % c0
    else
      (m1 - y1) % c1 if c1 > 0
    end
  )

  y0 = y0 * 2 % c0
  y1 = y1 * 2 % c1 if c1 > 0

  xi
end.reverse!

$table = [0]
def f(num)
  $table[num] ||= f(num % num.digits(2).count(1)) + 1
end

x.each { |xi| puts xi ? f(xi) + 1 : 0 }


Measured memory_bytes: 27724
/*
  A - ABC/ARC
  Contest 054
  Rakesh Kumar --> 04/08/2020
 */

#include <bits/stdc++.h>

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

    int a = 0, b = 0;
    std::cin >> a >> b;
    if (a == 1) a = 14;
    if (b == 1) b = 14;
    if (a > b)
        std::cout << "Alice" << std::endl;
    else if (a < b)
        std::cout << "Bob" << std::endl;
    else
        std::cout << "Draw" << std::endl;

    return 0;
}


Measured memory_bytes: 3640
n=int(input())
plan=[list(map(int,input().split())) for i in range(n)]
pret=0
prexy=0
for t,x,y in plan:
  t_diff=t-pret
  xy_diff=abs((x+y)-prexy)
  if t_diff>=xy_diff:
    if t_diff%2==0 and xy_diff%2==0:
      pass
    elif t_diff%2==1 and xy_diff%2==1:
      pass
    else:
      print('No')
      exit()
  else:
    print('No')
    exit()
  pret=t
  prexy=x+y
print('Yes')

Measured memory_bytes: 27380
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, D: int, X: int, A: "List[int]"):
    ans = 0
    for i in range(N):
        ans += 1 + (D-1)//A[i]
    print(ans+X)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, D, X, A)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define pi acos(-1)
#define ll long long
#define pii pair<ll,ll>
#define debug(a) cout<<a<<'\n'
#define maxn 100009 /// Look at me please ... that's what she said
#define MOD 1000000007
using namespace std;
const int INF = 1e6 + 9;
int main(){
    ios::sync_with_stdio(false);
    //cin.tie(0); ///activate when submit
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    int pos=0;
    vector<int> ans;
    for(int i=1;i<=n;i++){
        if(s[i]=='0'){
            ans.push_back(i-pos);
            pos=i;
        }
    }
    vector<int> ans2;
    bool can=true;
    // for(auto e: ans)cout<<e<<" ";
    // cout<<endl; 
    while(ans.size()>0){
        if(ans.back()>m){
            can=false;
            break;  
        }
        else if((int)ans.size()>1 && ans.back()+ans[(int)ans.size()-2]<=m){
            ll som=ans.back()+ans[(int)ans.size()-2];
            ans.pop_back();
            ans.pop_back();
            ans.push_back(som);
        }
        else{
            ans2.push_back(ans.back());
            ans.pop_back();
        }
    }
    if(!can)cout<<-1<<endl;
    else{
        reverse(ans2.begin(),ans2.end());
        for(auto e: ans2)cout<<e<<" ";
        cout<<endl;
    }
    return 0;
}    

Measured memory_bytes: 1480
// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2e5+5;
int n, x, q, ans;
int p[N], vis[N];
int main()
{
    scanf("%d%d", &n, &x);
    if(x == 1||x == 2*n-1) return puts("No"), 0;
    puts("Yes"); 
    p[n] = x, p[n-1] = x == 2?x+1:x-1, p[n+1] = x == 2?x-1:x+1, p[n+2] = x == 2?x+2:x-2;
    vis[x] = vis[x+1] = vis[x-1] = vis[x == 2?x+2:x-2] = 1;
    for(int i = 1, j = 1; i <= 2*n-1; ++i)
    {
        if(p[i]) continue; while(vis[j]) ++j;
        p[i] = j, vis[j] = 1;
    }
    for(int i = 1; i <= 2*n-1; ++i) printf("%d ", p[i]);
    return 0;
}

Measured memory_bytes: 2944
import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class Main {
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter syso = new PrintWriter(System.out);
		int n=sc.nextInt();
		long d=sc.nextLong();
		int c=0;
		for(int i=0;i<n;i++) {
			long a=sc.nextLong();
			long b=sc.nextLong();
			if((a*a+b*b)<=d*d)c++;
		}
		syso.println(c);
        syso.close();
    }
    
 
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;
 
		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
 
		public Scanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
		public int[] nextArr(int n) throws IOException{
			int arr[]=new int[n];
			for(int i=0;i<n;i++)arr[i]=nextInt();
			return arr;
		}
		public BigInteger BigInteger(String s) throws IOException{
			BigInteger a=new BigInteger(s);
			return a;
		}
 
	}
}

Measured memory_bytes: 46528
#include<iostream>
#include<vector>
#include<map>
using namespace std;

typedef long long int ll;
ll MOD = 1e9 + 7;

map<ll,ll> prime_factor(int N){
  map<ll,ll> res;
  for(int j = 2 ; j <= N ; j++){
    ll n = j;
    for(int i = 2 ; i * i <= j ; i++){
      while(n % i == 0){
	++res[i];
	n /= i;
      }      
    }
    if(n != 1)res[n]++;
  }
  return res;
}


int main(){
  int N;
  cin >> N;
  map<ll,ll>primes = prime_factor(N);
  ll res = 1LL;
  for(map<ll,ll>::iterator it = primes.begin() ; it != primes.end() ; ++it){
    res = (res * (it->second + 1LL))%MOD;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#define MAX_T 1440
using namespace std;
 
typedef pair<int, string> pis;
 
int main()
{
  while(1){
    int N;
    cin >> N;
    if(N == 0){
      break;
    }else{
      multimap<int, string> m;
      multimap<int, string>::iterator ite;
      vector<string> f;
      int P, ans = 0;
      bool flag = false;
      for(int i = 0; i < N; i++){
        string n, s;
        int w, x;
        cin >> n >> w >> s;
        if(s.size() == 3)
          x = (s[0] - '0') * 60 + (s[1] - '0') * 10 + (s[2] - '0');
        else
          x = ((s[0] - '0') * 10 + (s[1] - '0')) * 60 + (s[2] - '0') * 10 + (s[3] - '0');
        m.insert(pis(w * MAX_T + x, n));
      }
      cin >> P;
      for(int i = 0; i < P; i++){
        string s;
        cin >> s;
        f.push_back(s);
      }
      sort(f.begin(), f.end());
      int n = f.size();
      for(int i = 0; i < n; i++){
        if(f.empty() || flag)
          break;
        for(ite = m.begin(); ite != m.end(); ++ite){
          if(ite->second == f[i]){
            int x = ite->first;
            multimap<int, string>::iterator start;
            multimap<int, string>::iterator end;
            start = m.upper_bound(x - 30);
            end = m.lower_bound(x + 30);
            //if(start == m.end())
            //start = ite;
            m.erase(start, end);
            f.erase(f.begin());
            ans++;
            i = -1;
            break;
          }
          ite++;
          if(ite == m.end())
            flag = true;
          ite--;
        }
      }
      if(flag){
        cout << "-1" << endl;
      }else{ 
        while(!m.empty()){
          multimap<int, string>::iterator start;
          multimap<int, string>::iterator end;
          start = m.begin();
          end = m.lower_bound(start->first + 30);
          m.erase(start, end);
          ans++;
        }
        cout << ans << endl;
      }
    }
  }
}

Measured memory_bytes: 1296
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String []args) throws IOException {
    	FastScanner in  = new FastScanner(System.in);
    	PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false);
    	solve(in, out);
    	in.close();
    	out.close();
    }
    static long gcd(long a, long b){ return (b==0) ? a : gcd(b, a%b); }
    static int gcd(int a, int b){ return (b==0) ? a : gcd(b, a%b); }
    private static int fact(int n) { int ans=1; for(int i=2;i<=n;i++) ans*=i; return ans; }
    static class FastScanner{
	BufferedReader reader;
	StringTokenizer st;
	FastScanner(InputStream stream){reader=new BufferedReader(new InputStreamReader(stream));st=null;}
	String next(){while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;}
	     st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();}
	String nextLine()  {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;}
	int    nextInt()   {return Integer.parseInt(next());}
	long   nextLong()  {return Long.parseLong(next());}
	double nextDouble(){return Double.parseDouble(next());}
	char   nextChar()  {return next().charAt(0);}
	int[]  nextIntArray(int n)         {int[] arr= new int[n];   int i=0;while(i<n){arr[i++]=nextInt();}  return arr;}
	long[] nextLongArray(int n)        {long[]arr= new long[n];  int i=0;while(i<n){arr[i++]=nextLong();} return arr;}
	int[]  nextIntArrayOneBased(int n) {int[] arr= new int[n+1]; int i=1;while(i<=n){arr[i++]=nextInt();} return arr;}
	long[] nextLongArrayOneBased(int n){long[]arr= new long[n+1];int i=1;while(i<=n){arr[i++]=nextLong();}return arr;}
	void   close(){try{reader.close();}catch(IOException e){e.printStackTrace();}}
    }
    
    /********* SOLUTION STARTS HERE ************/
    
    private static void solve(FastScanner in, PrintWriter out){
        long cnt=0;
        // Scanner sc = new Scanner(System.in);
        // int n = sc.nextInt();
        int n = in.nextInt();
        int a[][] = new int[n][26];
        HashMap<String, Integer> map = new HashMap<>();
        for(int i=0;i<n;i++){
            char s[] = in.nextLine().trim().toCharArray();
            Arrays.sort(s);
            String tmp = new String(s);
            if(!map.containsKey(tmp)){
                map.put(tmp, 1);
            }else{
                int x = map.get(tmp);
                cnt += x;
                map.put(tmp, x + 1);
            }
        }
        out.println(cnt);
    }
    public static boolean same(int a[],int b[]){
        for(int i=0;i<26;i++) if(a[i]!=b[i]) return false;
        return true;
    }
    
    /************* SOLUTION ENDS HERE **********/
}

Measured memory_bytes: 64256
from collections import deque,defaultdict
n = int(input())
data = [[] for _ in range(n)]
sides = []
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    data[a].append(b)
    data[b].append(a)
    sides.append((a,b))
I = defaultdict(lambda:0)
cs = [0]*n
used = [0]*n
q = deque([0])
used[0]=1
k = 0
while q:
    u = q.popleft()
    if k < len(data[u]):
        k = len(data[u])
    cur = 1
    for v in data[u]:
        if used[v]:continue
        if cur==cs[u]:cur+=1
        cs[v] = cur
        I[(u,v)] = cur
        I[(v,u)] = cur
        cur += 1
        used[v] = 1
        q.append(v)
print(k)
for i,j in sides:
    print(I[(i,j)])

Measured memory_bytes: 61120
#include <bits/stdc++.h> 
 
#define INF (1<<31)//INT_MAX/2
#define MOD 1000000007
 
using ll  = long long;
using ull = unsigned long long;

int get_digit(int num) {
    int sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }

    return sum;
}

int main(int argc, char *argv[])
{
    int N;
    std::cin >> N;
    
    int min = 100000000;
    for (int i = 1; i < N; i++) {
        int A = i;
        int B = N - i;
        int sumA = get_digit(A);
        int sumB = get_digit(B);

        int sum = sumA + sumB;
        if (sum < min) {
            min = sum;
        }
    }

    std::cout << min << std::endl;
    return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

#[allow(unused_macros)]
macro_rules! debug {($($a:expr),*) => {println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);}}
#[allow(unused_macros)]
macro_rules! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);
impl<T: PartialEq> Eq for Total<T> {}
impl<T: PartialOrd> Ord for Total<T> { fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering { self.0.partial_cmp(&other.0).unwrap() }}

#[allow(dead_code)]
const MAX:usize = 100006;
#[allow(dead_code)]
const INF_U32:u32 = 1 << 31;
#[allow(dead_code)]
const INF_I32:i32 = 1 << 30;
#[allow(dead_code)]
const INF_U64:u64 = 1 << 63;
#[allow(dead_code)]
const INF_I64:i64 = 1 << 62;
#[allow(dead_code)]
const MOD:i64 = 1e9 as i64 + 7;

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}


#[allow(unused_imports)]
use std::f64;


fn main() {
    input!{n:usize, a:[i64;n]};
    let b:HashSet<_> = a.iter().cloned().collect();
    println!("{}", if b.len() == a.len() {"YES"} else {"NO"});
}

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


class Vec:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return '({}, {})'.format(self.x, self.y)

    def __add__(self, other):
        return Vec(self.x+other.x, self.y+other.y)

    def __sub__(self, other):
        return Vec(self.x-other.x, self.y-other.y)

    def __mul__(self, k):
        return Vec(self.x*k, self.y*k)

    def __truediv__(self, k):
        return Vec(self.x/k, self.y/k)

    def abs(self):
        return (self.x**2 + self.y**2)**.5


def dist(p, q):
    return (p-q).abs()


# returns a list of the intersections of two circles
# if they are outside of each other or one contains the other entirely, returns an empty list
def intersection_circles(c1, r1, c2, r2):
    d = (c1-c2).abs()

    # if the circles are outside of each other
    if r1 + r2 < d:
        return []

    # if one contains the other entirely
    if d < abs(r2 - r1):
        return []

    x = (r1**2-r2**2+d**2) / (2*d)
    y = (r1**2-x**2)**.5
    e1 = (c2-c1) / (c2-c1).abs()
    e2 = Vec(-e1.y, e1.x)
    p1 = c1 + e1*x + e2*y
    p2 = c1 + e1*x - e2*y
    return [p1, p2]


N, K = map(int, input().split())
center = [None] * N
cost = [0] * N
for i in range(N):
    x, y, c = map(int, input().split())
    center[i] = Vec(x, y)
    cost[i] = c
lb = 0
ub = 10**6
EPS = 10**(-8)
while ub - lb > EPS:
    mid = (lb + ub) / 2
    r = [mid / c for c in cost]
    points = list(center)
    for i in range(N-1):
        for j in range(i+1, N):
            points += intersection_circles(center[i], r[i], center[j], r[j])
    cnt = 0
    for p in points:
        tmp = 0
        for i in range(N):
            if dist(p, center[i]) < r[i] + EPS:
                tmp += 1
        cnt = max(cnt, tmp)
    if cnt >= K:
        ub = mid
    else:
        lb = mid
print(lb)


Measured memory_bytes: 74076
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


N, M = MI()
d = {i: 0 for i in range(N)}
for _ in range(M):
    a, b = MI()
    d[a - 1] += 1
    d[b - 1] += 1
for i in range(N):
    print(d[i])


Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  string s;
  cin >> s;

  bool ng = false;
  REP(i, n + 1) {
    if (s[i] == '1') {
      int count = 1;
      FOR(j, i + 1, n + 1) {
        if (s[j] == '1') {
          count++;
        } else {
          if (count >= m) {
            ng = true;
          }
          i = j;
          break;
        }
      }
    }
  }
  if (ng) {
    cout << -1 << endl;
    return 0;
  }

  vi rm(n + 1);
  REP(i, n + 1) { rm[i] = (s[n - i] - '0'); }

  vi ans;
  int cur = 0;
  while (cur < n) {
    for (int i = m; i > 0; i--) {
      if (cur + i > n)
        continue;
      if (rm[cur + i] == 0) {
        ans.push_back(i);
        cur += i;
        break;
      }
    }
  }

  for (int i = ans.size() - 1; i >= 0; i--) {
    cout << ans[i];
    if (i != 0) {
      cout << " ";
    }
  }
  cout << endl;
}


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

int dx[] = { 0, 1, 0, -1, 0, 1, 1, -1, -1, 2, 0, -2, 0 };
int dy[] = { 0, 0, 1, 0, -1, -1, 1, 1, -1, 0, 2, 0, -2 };

int main()
{
	int map[10][10];
	memset(map, 0, sizeof(map));
	int x, y, d;
	char c;

	while (cin >> x >> c >> y >> c >> d)
	{
		for (int i=0; i<=4*d; i++)
		{
			int tx = x + dx[i];
			int ty = y + dy[i];
			if (0 <= tx && tx < 10 && 0 <= ty && ty <= 10)
				map[ty][tx]++;
		}
	}

	int cnt = 0;
	int MAX = 0;
	for (int i=0; i<10; i++)
	for (int k=0; k<10; k++)
		if (map[i][k] == 0)
			cnt++;
		else if (map[i][k] > MAX)
			MAX = map[i][k];

	cout << cnt << endl;
	cout << MAX << endl;
}

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

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

    int N_len = N.length();
    N_len--;

    if(N[N_len] == '2' or N[N_len] == '4' or N[N_len] == '5' or N[N_len] == '7' or N[N_len] == '9')
    {
        cout<<"hon"<<endl;
        return 0;
    }
    else if(N[N_len] == '0' or N[N_len] ==  '1' or N[N_len] == '6' or N[N_len] == '8')
    {
        cout<<"pon"<<endl;
        return 0;
    }
    else
    {
        cout<<"bon"<<endl;
        return 0;
    }
    
    return 0;
}

Measured memory_bytes: 3620
#include<stdio.h>
int main(void){
    int l[50],n,k,i,j,ans,max,maxi;
    scanf("%d %d",&n,&k);
    for(i=0;i<50;i++){
        l[i]=0;
    }
    for(i=0;i<n;i++){
        scanf("%d",&l[i]);
    }
    ans=0;
    for(j=0;j<k;j++){
        max=-1;
        maxi=-1;
        for(i=0;i<n;i++){
            if(max<l[i]){
                max=l[i];
                maxi=i;
            }
        }
        ans+=max;
        l[maxi]=0;
    }
    printf("%d\n",ans);
    return 0;
}




Measured memory_bytes: 128
import bisect
S=list(input())
T=list(input())
sT=set(T)
N=len(S)
TI={}
for i in range(N):
  s=S[i]
  if s in sT:
    if s in TI:
      TI[s].append(i)
    else:
      TI[s]=[i]

i=-1
for t in T:
  if t not in TI:
    print(-1)
    exit()
  else:
    ni=TI[t][(bisect.bisect_right(TI[t],i%N))%len(TI[t])]
    if ni>i%N:
      i+=ni-i%N
    else:
      i+=N-i%N+ni
print(i+1)

Measured memory_bytes: 8928
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

int main(void) {
  cout.precision(12);

  long N;
  cin >> N;
  cout << (180 * (N - 2)) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
int gcd(int x,int y){
	if(x%y == 0)return y;
	return gcd(y%x,x);
}
signed main(){
	int a,b,c,d;cin >> a >> b >> c >> d;
	int ret = b-a+1;
	auto f = [&](int x,int y){
		return x/y;
	};
	int  p = c*d/gcd(c,d);
	ret -= f(b,c) - f(a-1,c);
	ret -= f(b,d) - f(a-1,d);
	ret += f(b,p) - f(a-1,p);
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 3548
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

//vector string deque break continue
#define forn(i, s, f) for (int i = (int)s; i < (int)f; i++)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define fs first
#define sc second
#define pf push_front
#define pb push_back
#define pop_f pop_front
#define pop_b pop_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

template <typename T> istream& operator>>(istream& in, vector <T>& a) {for (auto& i : a) in >> i; return in;}
template <typename T> ostream& operator<<(ostream& out, vector <T>& a)  {for (auto& i : a) out << i << " "; return out;}
template <typename T, typename U> void chkmin(T& a, U b) {if (a > b) a = b;}
template <typename T, typename U> void chkmax(T& a, U b) {if (a < b) a = b;}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    string s;
    cin >> s;
    for (int i = 0; i < sz(s); i += 2)
        if (s[i] != 'h')
            return cout << "No", 0;
    for (int i = 1; i < sz(s); i += 2)
        if (s[i] != 'i')
            return cout << "No", 0;
    if (sz(s) % 2)
        return cout << "No", 0;
    cout << "Yes";
    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 count = Integer.parseInt(sc.next());
		int[] givingNumbers = new int[count];
		
		// Read Numbers
		for(int i = 0; i< count;i++){
			
			givingNumbers[i] = Integer.parseInt(sc.next());
			
		}
		
		// Reversing Numbers
		for(int i = count-1; 0 <= i;i--){
			
			System.out.print(givingNumbers[i]);
			
			if(i > 0){
				System.out.print(" ");
			}
			
			
		}
		
		System.out.println();
		
		sc.close();
	}

}


Measured memory_bytes: 26096
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    ll a, b;
    cin >> a >> b;
    vector<ll> ret;
    for(ll i = 1; i*i <= a; i++){
        if(a % i == 0){
            if(b % i == 0)ret.push_back(i);
            if(i * i != a && b % (a/i) == 0)ret.push_back(a/i);
        }
    }
    sort(all(ret));
    ll ans = 0, num = 1;
    rep(i, ret.size()){
        if(__gcd(num, ret[i]) == 1){
            num *= ret[i];
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
N=int(input())
L=list(map(int,input().split()))
s2,s4=0,0 #s2は２で割れる数、s4は４で割れる数の個数
for j in L:
  if j%4==0:
    s4+=1
  elif j%2==0:
    s2+=1
if s2==0:
  if (N-s2-s4)<=s4+1:
    print("Yes")
  else:
    print("No")
else:
  if (N-s2-s4)<=s4:
    print("Yes")
  else:
    print("No")


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

using namespace __gnu_pbds;
using namespace std;

using ll = long long;
using ld = long double;

#define mp make_pair

typedef tree<
        pair<int, int>,
        null_type,
        less<pair<int, int>>,
        rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set;


const int p = 1e9 + 7;


int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int add(int a, int b) {
    int s = (a+b);
    if (s>=p) s-=p;
    return s;
}

int sub(int a, int b) {
    int s = (a+p-b);
    if (s>=p) s-=p;
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}


mt19937 rnd(time(0));




/*
const int N = 1200000;

vector<int> facs(N), invfacs(N);

void init()
{
    facs[0] = 1;
    for (int i = 1; i<N; i++) facs[i] = mul(facs[i-1], i);
    invfacs[N-1] = inv(facs[N-1]);
    for (int i = N-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
}

int C(int n, int k)
{
    if (n<k) return 0;
    return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}
*/

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

    int x;
    cin>>x;
    cout<<360/__gcd(360, x);

}



Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do {(t*=10)+=ch-'0';ch=getchar();} while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int maxn=(2e5)+10;
int n;
ll x,s[maxn],ans,sum;
int main() {
	//freopen("1.txt","r",stdin);
	read(n); read(x);
	for (int i=1;i<=n;i++) {
		read(s[i]); s[i]+=s[i-1];
	}
	ans=1LL<<62;
	for (int i=1;i<=n;i++) {
		sum=x*i;
		for (int j=1,l=0,r=n;r&&sum<ans;j++,r=l-1) {
			l=max(r-i+1,1);
			if (j==1) sum+=5*(s[r]-s[l-1]);
			else sum+=(j*2+1)*(s[r]-s[l-1]);
		}
		ans=min(ans,sum);
	}
	printf("%lld\n",ans+x*n);
	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2e5+5;
int a[maxn],n;
bool b[maxn];
bool check(){
    int i,m=n-1;
    for (i=0;i<n-1;i++){
        if (b[m-i]==b[m-i-1]) return b[m-i];
        if (b[m+i]==b[m+i+1]) return b[m+i];
    }
    return b[0];
}
int sear(int l,int r){
    if (l+1==r) return l;
    int m=(l+r)/2;
    int i;
    for (i=0;i<2*n-1;i++) b[i]=(a[i]<=m);
    if (check()) return sear(l,m);
    else return sear(m,r);
}
int main(){
    int i;
    scanf("%d",&n);
    for (i=0;i<2*n-1;i++) scanf("%d",&a[i]);
    printf("%d",sear(1,2*n)+1);
    return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    int s=max(a,max(b,c));
    int t=3*s-a-b-c;
    if(t%2)
        cout<<(t+3)/2;
    else cout<<t/2;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP2(i, m, n) for (int i = (m); i < (int)(n); ++i)
#define REPR(i, n) for (int i = (n)-1; i >= 0; --i)
#define REPR2(i, m, n) for (int i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a) sort(ALL(a), greater<int>())
#define REVERSE(a) reverse(ALL(a))
#define bit_search(bit, n) REP(bit, 1<<(n))
#define bit_check(bit, i) (bit>>(i)) & 1
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REP(i, a.size()) cin >> a[i];
#define INPUTP(a) REP(i, a.size()) cin >> a[i].first >> a[i].second;
#define OUTPUT_PERMUTATION(n) do{VI v(n); iota(ALL(v), 1); do{REPx(x, v) cout << x << " "; ENDL} while(next_permutation(ALL(v)));} while(0);
#define MAKE_PERMUTATION(n) do{VVI a(fact(n), VI(n)); int idx = 0; VI v(n); iota(ALL(v), 1); do{REP(i, n) a[idx][i] = v[i]; idx++; PER = a;} while(next_permutation(ALL(v)));} while(0); // int fact(), VVI PERを宣言しておく
#define ENDL cout << endl;
using namespace std;
using LL = long long;
using LD = long double;
using PII = pair<int, int>;
using VPII = vector<PII>;
using PLL = pair<LL, LL>;
using VPLL = vector<PLL>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VC = vector<char>;
using VS = vector<string>;
using VB = vector<bool>;
using VD = vector<double>;
const int INF = 1e9;
const LL MOD = 1e9 + 7;

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

void END(){cout << 1 << endl; exit(0);}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  cout << (n+1)/2;

  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>
#include<iomanip>
#include<functional>

using namespace std;
typedef long long int ll;

#define C(I) cout<<(I)<<endl

ll n,m,a,b,c,x,y,z,aa[100010],ba[100010];
bool r,ra,rb,rc;
string s,sa,sb,sc;
char ca,cb,cc;
vector<ll> va,vb,vc;


int main(){
    cin>>x>>y>>z;
    a=0;
    while(y*a+a*z+z<=x){
        a++;
    }
    C(a-1);
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if((a % 2 == 0) || (b % 2 == 0)){
            System.out.println("Even");
        }else{
            System.out.println("Odd");
        }
    }
}

Measured memory_bytes: 21844
#include<stdio.h>
int main()
{
    long long int n,i,sum,min,d;
    sum=min=0;
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
            sum=sum+i;
        if(i%3==0 || i%5==0){
            min=min+i;
        }

    }
    d=sum-min;
    printf("%lld\n",d);
    return 0;
}


Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))

typedef long long ll;
typedef __int128_t lll;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
void dout(double d){printf("%.12f\n",d);}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

const int N = 1e5;
int DP[N], h[N], n, k;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> k;
  FOR(i, 0, n) cin >> h[i];
  Fill(DP, IINF);
  DP[0] = 0;
  FOR(i, 1, n) FOR(j, 1, k+1) if(i-j >= 0) mins(DP[i], DP[i-j] + abs(h[i]-h[i-j]));
  cout << DP[n-1] << endl;
}

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

int main() {
  int N;
  cin >> N;
  vector<int64_t> data(N);
  int64_t min = INT64_MAX;
  for (int i = 0; i < N; i++) {
    cin >> data[i];
    if (min > data[i]) {
      min = data[i];
    }
  }

  while (min > 1) {
    int64_t next = min;
    for (int64_t &n : data) {
      int64_t d = n % min;
      if (min != n && d > 0) {
        n = d;
        if (d < next) {
          next = d;
        }
      }
    }
    if (min == next) {
      break;
    }
    min = next;
  }

  cout << min << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
int N, K;
const int MOD = 1000000007;

long long bfs() {
    long long ret = K;
    vector<bool> visited(N, false);
    visited[0] = true;
    queue<int> Q;
    for(int j=0; j<G[0].size(); ++j) {
        ret = (ret * (K - 1 - j)) % MOD;
        visited[G[0][j]] = true;
        Q.push(G[0][j]);
    }

    while(!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        if(G[cur].size() > 1) {
            for(int j=0; j+1<G[cur].size(); ++j) {
                ret = (ret * (K - 2 - j)) % MOD;
            }
            for(int to : G[cur]) {
                if(!visited[to]) {
                    visited[to] = true;
                    Q.push(to);
                }
            }
        }
    }
    return ret;
}

int main() {
    cin >> N >> K;
    G.resize(N);
    for(int i=0; i+1<N; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    cout << bfs() << endl;
}

Measured memory_bytes: 6520
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <string>
#include <iostream>
#include <complex>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <stack>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <random>
#include <set>
#include <vector>
#include <unordered_map>
#include <bitset>
#include <unordered_set>
#include <array>
#include <forward_list>
//#include <chrono>
#include <iomanip>
#include <utility>
#include <assert.h>

#pragma GCC optimize("Ofast")
#pragma target("sse", "sse1")

#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

mt19937 gen(34);

int n;
vector <pair <int, int>> a[15];

bool check(int mask)
{
	int sos[15];
	for (int i = 0; i < n; i++)
	{
		sos[i] = 0;
		if (mask & (1 << i))
			sos[i] = 1;
	}
	for (int i = 0; i < n; i++)
		if (mask & (1 << i))//true
			for (int j = 0; j < a[i].size(); j++)
				if (sos[a[i][j].first] == 0)
					if (a[i][j].second == 1)
						return false;
					else
						sos[a[i][j].first] = a[i][j].second;
				else
					if (sos[a[i][j].first] != a[i][j].second)
						return false;
	return true;
}

int kolvobit(int mask)
{
	int res = 0;
	while (mask)
	{
		res += (mask & 1);
		mask >>= 1;
	}
	return res;
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//	freopen("memory.in", "r", stdin);
	//	freopen("memory.out", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		a[i].resize(x);
		for (int j = 0; j < x; j++)
		{
			cin >> a[i][j].first >> a[i][j].second;
			a[i][j].first--;
			if (a[i][j].second == 0)
				a[i][j].second = -1;
		}
	}
	const int maxmask = (1 << n) - 1;
	int ans = -1;
	for(int mask = 0; mask <= maxmask; mask++)
		if (check(mask))
				ans = max(ans, kolvobit(mask));
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    string s, a = "bdpq";
    cin >> s;
    auto t = s;
    reverse(t.begin(),t.end());
    for (int i = 0; i < t.size(); ++i) {
        for (int j = 0; j < 4; ++j) {
            if(t[i] == a[j]){
                t[i] = a[j^1];
                break;
            }
        }
    }
    puts(s == t ? "Yes" : "No");
    return 0;
}

Measured memory_bytes: 512
import sys
INF = 10**10
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)
from functools import lru_cache
from itertools import permutations

def main():
    n,t = map(int,input().split())
    a = list(map(int,input().split()))

    cummin = [0] * n
    cummax = [0] * n
    cummin[0] = a[0]
    cummax[-1] = a[-1]
    for i in range(1,n):
        cummin[i] = min(a[i],cummin[i - 1])
        cummax[- i - 1] = max(a[- i - 1],cummax[-i])
    
    ben = 0   
    for i in range(1,n):
        ben = max(ben,cummax[i] - cummin[i - 1])
    
    cnt = 0
    flag = True
    for i in range(1,n):
        if ben == cummax[i] - cummin[i - 1]:
            if flag:
                cnt += 1
                flag = False
            
        else:
            flag = True
    
    print(cnt)

if __name__=='__main__':
    main() 

Measured memory_bytes: 15196