akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict
H,W,K = map(int,input().split())
S = [0] * H
for i in range(H):
    S[i] = input()

INF = H + W - 2

def bi(x):
    global H
    o = [0]*(H-1)
    i = 0
    while x != 0:
        o[i] = x % 2
        i += 1
        x //= 2
    return o

def hoge(n):
    global K
    b = bi(n)
    d = defaultdict(set)
    j = 0
    for i in range(H):
        d[j].add(i)
        if i == H - 1:
            break
        if b[i]:
            j += 1
    dlen = len(d)
    T = [0]*dlen
    for k,V in d.items():
        T[k] = [0]*W
        for i in range(W):
            for v in V:
                T[k][i] += int(S[v][i])
            if T[k][i] > K:
                return INF
    ans = dlen - 1
    U = [T[x][0] for x in range(dlen)]
    for i in range(1,W):
        flag = 0
        for k in range(dlen):
            U[k] += T[k][i]
            if U[k] > K:
                flag = 1
        if flag == 1:
            ans += 1
            for k in range(dlen):
                U[k] = T[k][i]
    return ans

ANS = INF
for i in range(2**(H-1)):
    ANS = min(ANS,hoge(i))

print(ANS)

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

using namespace std;

template<class M, class F = std::function<M(M, M)>>
class SegmentTree{
private:
  std::vector<M> data;
  F op;
  M e;
  int length;

public:
  SegmentTree(int n, const F op, const M& e) : op(op), e(e){
    length = 1;
    while(length < n) length <<= 1;
    data = std::vector<M>((length << 1) - 1, e);
  }

  void set(int index, const M& x){
    index += length - 1;
    data[index] = x;

    while(index){
      (--index) >>= 1;
      data[index] = op(data[(index << 1) + 1], data[(index << 1) + 2]);
    }
  }

  M get(int left, int right){
    M l = e, r = e;

    for(left += length - 1, right += length - 1; left < right; (--left) >>= 1, (--right) >>= 1){
      if(!(left & 1)) l = op(data[left++], l);
      if(!(right & 1)) r = op(data[--right], r);
    }

    return op(l, r);
  }
};

template<typename T, typename U>
T gcd(T a, U b){
  if(a < b){
    a ^= b;
    b ^= a;
    a ^= b;
  }

  T r;
  while(b){
    r = a % b;
    a = b;
    b = r;
  }

  return a;
}


int main(){
  int N;
  cin >> N;
  
  SegmentTree<int> segTree(N, [](int a, int b){return gcd(a, b);}, 0);
  
  for(int i = 0; i < N; i++){
    int A;
    cin >> A;
    segTree.set(i, A);
  }
  
  int max_gcd = max(segTree.get(1, N), segTree.get(0, N - 1));
  for(int i = 1; i < N - 1; i++){
    max_gcd = max(gcd(segTree.get(0, i), segTree.get(i + 1, N)), max_gcd);
  }
  
  cout << max_gcd << endl;
  
  return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <random>
#include <fstream>
#include <string>
#include <tuple>
#include <deque>
#include <set>
#include <map>
#include <stack>

#define REP(i, N) for(int i = 0; i< N; i++)
using namespace std;
#define ll long long
const int INF = 1 << 29;
const ll llINF = 10000000000000000;

const int MOD = 1000000007;

#define MAX_N 100100
typedef pair<int, int> P;

ll threesteps(){
    vector<int> gurafu[MAX_N];
    stack<int> st;
    int migihidari[MAX_N] = {0};
    ll N, M;
    cin >> N >> M;
    REP(i, M){
        int A, B;
        cin >> A >> B;
        A--;
        B--;
        gurafu[A].push_back(B);
        gurafu[B].push_back(A);
    }
    bool nibu = true;
    int genzaichi = 0;
    ll migihidarikazu[2] = {0};
    migihidari[0] = 1;
    migihidarikazu[1] = 1;
    do{
        if(gurafu[genzaichi].empty()){
            if(st.empty())break;
            genzaichi = st.top();
            st.pop();
            continue;
        }
        int tuginogenzaichi = gurafu[genzaichi].back();
        if(migihidari[tuginogenzaichi] == migihidari[genzaichi])nibu = false;
        if(migihidari[tuginogenzaichi] == 0){
            migihidari[tuginogenzaichi] = -migihidari[genzaichi];
            migihidarikazu[(1 + 2 * migihidari[tuginogenzaichi]) / 2]++;
        }
        gurafu[genzaichi].pop_back();
        if(!gurafu[genzaichi].empty())st.push(genzaichi);
        genzaichi = tuginogenzaichi;
    }while(1);
    
    if(nibu)return migihidarikazu[0] * migihidarikazu[1] - M;
    else return N * (N - 1) / 2 - M;
}

int main(){
    printf("%lld\n", threesteps());
}



Measured memory_bytes: 6400
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		opi(a);
		for (int i = 0; i < n -1; i++)
			System.out.print(a[i] + " ");
		System.out.println(a[n-1]);
		sc.close();
	}

	static void opi(int[] x) {
		for (int i = 0; i < x.length / 2; i++) {
			int j = x.length - 1 - i;
			int temp = x[i];
			x[i] = x[j];
			x[j] = temp;
		}
	}
}


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

struct edge{int to,cap,rev;};

const int INF=1e9;
int N,M;
vector<edge>G[100];

void add_edge(int from,int to,int cap){
    G[from].push_back((edge){to,cap,G[to].size()});
    G[to].push_back((edge){from,0,G[from].size()-1});
}

bool used[100];
int dfs(int p,int t,int f){
    if(p==t)return f;
    used[p]=true;

    for(int i=0;i<G[p].size();i++){
        edge &e=G[p][i];
        if(used[e.to]||e.cap==0)continue;
        int _f=dfs(e.to,t,min(f,e.cap));
        if(_f){
            e.cap-=_f;
            G[e.to][e.rev].cap+=_f;
            return _f;
        }
    }

    return 0;
}

int max_flow(int s,int t){
    int flow=0;
    while(true){
        fill_n(used,N,false);
        int f=dfs(s,t,INF);
        if(f)flow+=f;
        else return flow;
    }
}
int main(){
    cin>>N>>M;
    for(int i=0;i<M;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add_edge(a,b,c);
    }

    cout<<max_flow(0,N-1)<<endl;
    return 0;
}

Measured memory_bytes: 1264
n = int(input())
a = input()

w_count = [0]
e_count = [0]

a_r = list(reversed(a))

for i in range(1, n+1):
    if a[i-1] == 'W':
        w_count.append(w_count[i-1] + 1)
    else:
        w_count.append(w_count[i-1])
    if a_r[i-1] == 'E':
        e_count.append(e_count[i-1] + 1)
    else:
        e_count.append(e_count[i-1])

w = w_count[1:]
e = list(reversed(e_count[1:]))

sum = 10000000
for i in range(0, n):
    if sum > w[i] + e[i]:
        sum = w[i] + e[i]

print(sum-1)


Measured memory_bytes: 27384
using System;

namespace Sample101
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                var line = Console.ReadLine().ToCharArray();
                if (line.Length == 1 && line[0] == '0')
                {
                    return;
                }

                var result = 0;
                for (int i = 0; i < line.Length; i++)
                {
                    result += int.Parse(line[i].ToString());
                }

                Console.WriteLine(result);
            }
        }
    }
}


Measured memory_bytes: 15864
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main(void) {
  double a, b, C;
  double c;
  double S, L, h;
  cin >> a >> b >> C;
  C = C * M_PI / 180;
  h = b * sin(C);
  S = a * h / 2;
  c = sqrt(a * a + b * b - 2 * a * b * cos(C));
  L = a + b + c;
  cout << setprecision(11) << S << " " << L << " " << h << endl;
  return 0;
}



Measured memory_bytes: 3592
#include<iostream>
#include<cmath>

bool prime(int n){
    if(n == 2){
        return true;
    }else if(n < 2 || n % 2 == 0){
        return false;
    }

    double sqrtNum = sqrt(n);
    for(int i = 3; i <= sqrtNum; i += 2){
        if(n % i == 0){
            return false;
        }
    }

    return true;
}

int main(){
    int x;
    std::cin >> x;

    bool ans;
    do{
        ans = prime(x);
        x++;
    }while(!ans);

    std::cout << x - 1 << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char cf[]="CF";
string in;
int main(){
    cin>>in;
    int top=0;
    for(int i=0;i<in.length();++i){
        if(in[i]==cf[top]){
            ++top;
            if(top==2){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    
    int max = sc.nextInt();
    int gcd = max;
    for (int i = 0; i < N-1; i++) {
      int A = sc.nextInt();
      gcd = calcGcd(gcd, A);
      max = Math.max(max, A);
    }
    System.out.println(K <= max && K%gcd == 0 ? "POSSIBLE" : "IMPOSSIBLE");
  }
  
  private static int calcGcd(int a, int b) {
    if (b == 0) return a;
    return calcGcd(b, a%b);
  }
}

Measured memory_bytes: 48460
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func main() {
    anntenas := make([]int,5)
  	for i := 0; i< 5; i++{
    	anntenas[i], _ = strconv.Atoi(nextLine())
  	}
    dist, _ := strconv.Atoi(nextLine())
  sort.Sort(sort.IntSlice(anntenas))
  if (anntenas[len(anntenas)-1] - anntenas[0]) > dist {
    fmt.Println(":(")
  } else {
    fmt.Println("Yay!")
  }
}

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

int main() {
	string s, p;
	cin >> s >> p;

	s += s;

	for(int i=0; i<s.size(); i++) {
		if(s.substr(i, p.size())==p) {
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3212
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = 1e9 + 7;

vector<ll> a;
bool isOK(int index, ll key)
{
  if (a[index] >= key)
    return true;
  else
    return false;
}
int binary_search(ll key)
{
  int ng = -1;
  int ok = (int)a.size();
  while (abs(ok - ng) > 1)
  {
    int mid = (ok + ng) / 2;
    if (isOK(mid, key))
      ok = mid;
    else
      ng = mid;
  }
  return ok;
}

ll repeatSquaring(ll n, ll p)
{
  if (p == 0)
    return 1;
  if (p % 2 == 0)
  {
    ll t = repeatSquaring(n, p / 2);
    return t * t;
  }
  return n * repeatSquaring(n, p - 1);
}

vector<ll> memo;

int main()
{
  int n;
  cin >> n;
  for (ll i = 0; i < 40; ++i)
  {
    memo.push_back(repeatSquaring(2, i));
  }
  unordered_map<ll, ll> mp;
  for (int i = 0; i < n; ++i)
  {
    ll tmp;
    cin >> tmp;
    mp[tmp]++;
    a.push_back(tmp);
  }
  sort(a.begin(), a.end());
  int cnt = 0;
  for (int i = a.size() - 1; i > -0; --i)
  {
    if (!mp[a[i]])
      continue;

    for (int j = memo.size() - 1; j >= 0; --j)
    {
      ll key = memo[j] - a[i];
      if (key > a[a.size() - 1] || key < 0)
        continue;
      int itr;
      itr = binary_search(key);
      if (itr >= a.size() || a[itr] != key || a[i] == a[itr])
        continue;
      if (itr < a.size() && a[i] + a[itr] == memo[j] && i != itr && mp[a[itr]] && mp[a[i]])
      {
        ll diff = mp[a[itr]] < mp[a[i]] ? mp[a[itr]] : mp[a[i]];
        cnt += diff;
        mp[a[itr]] -= diff, mp[a[i]] -= diff;
        break;
      }
    }
  }
  for (auto &e : mp)
  {
    for (int i = 0; i < memo.size(); ++i)
    {
      if (2 * e.first == memo[i])
      {
        cnt += e.second / 2;
        break;
      }
    }
  }
  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 10044
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ll = long long int;

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

  // 移動のステップ
  vector<int> ans(s.size(), 0);

  for (int i = 0; i < s.size(); i++) {
    // L が出てくるまで進む
    int l = 0;
    while (s[i + l] != 'L') {
      l++;
    }
    if (l == 0) {
      continue;
    }

    for (int j = 0; j < l; j++) {
      if (abs(l - j) % 2 == 0) {
        ans[i + l]++;
      } else {
        ans[i + l - 1]++;
      }
    }
    i += l;
  }

  for (int i = s.size() - 1; i >= 0; i--) {
    // R が出てくるまで進む
    int r = 0;
    while (s[i - r] != 'R') {
      r++;
    }

    for (int j = 0; j < r; j++) {
      if (abs(r - j) % 2 == 0) {
        ans[i - r]++;
      } else {
        ans[i - r + 1]++;
      }
    }
    i -= r;    
  }

  for (size_t i = 0; i < s.size(); i++) {
    cout << ans[i];
    if (i == s.size() - 1) {
      cout << endl;
    } else {
      cout << " ";
    }
  }
}

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

int main(){
	int n,k;
	cin >> n >> k;
	int a[n];
	for(int i =0;i<n;i++)
		cin >> a[i];
	sort(a,a+n);
	int dp[k+1];
	dp[0] = 0;
	int i = 1;
	while(i<a[0]){
		dp[i] = 0;
		i++;
	}

	for(int i=a[0];i<=k;i++){
		dp[i] = 0;
		for(int j =0;j<n;j++){
			if((i-a[j]>=0) && !dp[i-a[j]])
				dp[i]|=1;
		}
	}
	cout << (dp[k]?"First":"Second") << endl;

}

Measured memory_bytes: 640
def main():
    A = int(input())
    B = int(input())
    C = int(input())
    X = int(input())
    count = 0
    for i in range(A+1):
        for j in range(B+1):
            for k in range(C+1):
                if 500*i + 100*j + 50*k == X:
                    count += 1
    print(count)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();
    
    for (int a = 1; a <= 9; a ++) {
      for (int b = 1; b <= 9; b ++) {
        if (a*b == N) {
          System.out.println("Yes");
          return;
        }
      }
    }
    System.out.println("No");
    return;
  }
}

Measured memory_bytes: 23892
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
//typedef __int64 LL;
typedef long long int LL;
typedef pair<int,int> P;

const int MOD=1000000007;

int main()
{
	LL n,k;
	cin>>n>>k;
	
	LL x=n/k,y=(n+k/2)/k;
	if(k%2==1)cout<<x*x*x<<"\n";
	else
	{
		cout<<x*x*x+y*y*y<<"\n";	
	}	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    string a;
    cin >> a;
    int ans = 0;

    for (int i = 0; i < 3; i++) {
        if (a[i] == '1') {
            ans++;
        }
    }

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

Measured memory_bytes: 3584
program main

  implicit none
  character(len=100) S
  integer :: lnS, i

  read(*,*) S

  lnS = len(trim(S))

  ! check odd
  do i = 1,lnS,2
     if ( S(i:i) == "L") then
        write(*,'(a)') "No"
        stop
     end if
  end do
  ! check even
  do i = 2,lnS,2
     if ( S(i:i) == "R") then
        write(*,'(a)') "No"
        stop
     end if
  end do

  write(*,'(a)') "Yes"

end program main


Measured memory_bytes: 768
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	public static void main(final String[] args) {
		@SuppressWarnings("resource")
		final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		final int N = in.nextInt();
		final int M = in.nextInt();
		final int X[] = new int[M];
		final int Y[] = new int[M];
		final int Z[] = new int[M];
		for (int i = 0; i < M; ++i) {
			X[i] = in.nextInt();
			Y[i] = in.nextInt();
			Z[i] = in.nextInt();
		}
		int cost = solve(N, M, X, Y, Z);
		System.out.println(cost);
	}

	public static class UnionFind {
		final int[] parent;
		final int[] rank;
		int disjointCount;

		public UnionFind(final int N) {
			this.parent = new int[N];
			this.rank = new int[N];
			for (int i = 0; i < N; ++i) {
				parent[i] = i;
			}
			this.disjointCount = N;
		}

		public int find(final int i) {
			if (parent[i] == i)
				return i;
			int top = find(parent[i]);
			parent[i] = top;
			return top;
		}

		public void unite(int i, int j) {
			i = find(i);
			j = find(j);
			if (i == j)
				return;
			--disjointCount;
			if (rank[i] < rank[j]) {
				parent[i] = j;
			} else {
				parent[j] = i;
				if (rank[i] == rank[j])
					++rank[i];
			}
		}

		public boolean same(int i, int j) {
			return find(i) == find(j);
		}

		public int disjointCount() {
			return disjointCount;
		}
	}

	public static int solve(int N, int M, int[] X, int[] Y, int[] Z) {
		final UnionFind uf = new UnionFind(N);
		for (int i = 0; i < M; ++i) {
			uf.unite(X[i] - 1, Y[i] - 1);
		}
		return uf.disjointCount();
	}
}


Measured memory_bytes: 94068
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include <queue>
 
using namespace std;
using ll=long long;
#define rep(i,n)  for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()
 
int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n)cin >> a[i];
    
    int ans = 0;
    for(int i=1; i<n; ++i){
        if(a[i-1]==a[i])a[i]=-1, ans++;
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
# https://atcoder.jp/contests/abc160/submissions/11310424

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    def dist(a, b):
        return min(
            abs(a - b),
            abs(a - X) + abs(b - Y) + 1,
            abs(a - Y) + abs(b - X) + 1
        )

    ctr = [0] * N
    for b in range(N):
        for a in range(b):
            d = dist(a, b)
            ctr[d] += 1

    print(*ctr[1:], sep='\n')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;
#define rep(i,n) for(ll i=0;i<n;i++)

int main(){
	double a,b,x;cin>>a>>b>>x;
	if(x>=a*a*b/2){
		double z=2*(b-x/(a*a))/a;
		double ans=atan(z)*180/pi;
		cout<<fixed<<setprecision(15)<<ans<<"\n";
	}

	else{
		double z=a*b*b/(2*x);
		double ans=atan(z)*180/pi;
		cout<<fixed<<setprecision(15)<<ans<<"\n";
	}

}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define int         long long
#define endl        "\n"
#define P           pair<int, int>
#define dint        long double



void solve() {
    int n; cin >> n;
    int a[n];
    for(int i=0; i<n; i++) cin >> a[i];
    map<int, int> cnt;
    int ans = 0;
    for(int i=0; i<n; i++) {
        int cur = i - a[i];
        if(cur > 0) {
            ans += cnt[cur];
        }
        cnt[i + a[i]]++;
    }
    cout << ans << endl;
}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(12);

    int T = 1;
    //cin >> T;
    for(int i=1; i<=T; i++) {
        solve();
    }
    return 0;

}



Measured memory_bytes: 18980
#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 1000000;

int main(){
	vector<int> tetrahedral, odd_tetrahedral;
	for(int i = 0; ; ++i){
		int y = i * (i + 1) * (i + 2) / 6;
		if(y > MAX_N){ break; }
		tetrahedral.push_back(y);
		if(y % 2 == 1){ odd_tetrahedral.push_back(y); }
	}
	vector<int> dp(MAX_N, -1), odd_dp(MAX_N, -1);
	dp[0] = odd_dp[0] = 0;
	for(int i = 0; i < MAX_N; ++i){
		for(int j = 0; j < tetrahedral.size(); ++j){
			int next = i + tetrahedral[j];
			if(next >= MAX_N){ break; }
			if(dp[next] < 0){
				dp[next] = dp[i] + 1;
			}else if(dp[next] > dp[i] + 1){
				dp[next] = dp[i] + 1;
			}
		}
		for(int j = 0; j < odd_tetrahedral.size(); ++j){
			int next = i + odd_tetrahedral[j];
			if(next >= MAX_N){ break; }
			if(odd_dp[next] < 0){
				odd_dp[next] = odd_dp[i] + 1;
			}else if(odd_dp[next] > odd_dp[i] + 1){
				odd_dp[next] = odd_dp[i] + 1;
			}
		}
	}
	while(true){
		int n;
		cin >> n;
		if(n == 0){ break; }
		cout << dp[n] << " " << odd_dp[n] << endl;
	}
	return 0;
}

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

int main(){
    int d, n, m;

    while (cin >> d, d) {
        cin >> n >> m;
        
        vector<int> v;
        v.push_back(0);
        v.push_back(d);

        int di;
        for (int i=0; i<n-1; ++i) {
            cin >> di;
            v.push_back(di);
            v.push_back(di+d);
        }
        sort(v.begin(), v.end());
        
        long long sum = 0;
        int k;
        for (int i=0; i<m; ++i) {
            cin >> k;
            auto j = lower_bound(v.begin(), v.end(), k) - v.begin();
            sum += min(v[j]-k, k-v[j-1]);
        }

        cout << sum << endl;
    }

    return 0;
}


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

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
  int n;
  cin >> n;
  string s;
  cin >> s;
  if(n % 2 != 0) {
      cout << "No" << endl;
      return 0;
  }
  rep(i, 0, n / 2) {
      if(s[i] != s[n / 2 + i]) {
          cout << "No" << endl;
          return 0;
      }
  }
  cout << "Yes" << endl;

}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int check[100];
int main(){
  int n,k,a,t;
  cin >> n >> k;
  for(int i = 0;i<k;i++){
    cin >> a;
    for(int j=0;j<a;j++){
      cin >> t;
      check[--t]++;
    }
  }
  int c=0;
  for(int i=0;i<n;i++){
    if( !check[i] ) c++;
  }
  printf("%d\n",c);
}


Measured memory_bytes: 3764
#include "bits/stdc++.h"
using namespace std;
#define int long long

int n;
signed main() {
	cin >> n;
	vector<int> a(n);
	for (size_t i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	int cnt = 0;
	for (size_t i = 1; i < n; i++)
	{
		if (a[i] == a[i - 1]) {
			a[i] = -1;
			cnt++;
		}
	}
	cout << cnt << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,temp,key;
    cin>>a>>b;
    map<int,int >m;
    map<int,int>::iterator it;
    for(int i=0;i<a;i++)
    {
        cin>>temp;
        while(temp--)
        {
            cin>>key;
            m[key]++;
        }
    }
    int count=0;
    for(it=m.begin();it!=m.end();it++)
    {
        if(it->second==a)
        count++;
    }
    cout<<count<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
using namespace std;

typedef long long ll;

int main() {
    int H,W;
    cin >> H >> W;
    vector< vector <int> > cost(10, vector<int> (10)), A(H, vector<int> (W));
    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            cin >> cost[i][j];
        }
    }
    for(int h=0; h<H; h++){
        for(int w=0; w<W; w++){
            cin >> A[h][w];
        }
    }
    int cnt=0;
    while(cnt!=10){
        for(int from=0; from<10; from++){
            for(int to=0; to<10; to++){
                for(int via=0; via<10; via++){
                    cost[from][to]=min(cost[from][to], cost[from][via]+cost[via][to]);
                }
            }
        }
        cnt++;
    }
    int ans=0;
    for(int h=0; h<H; h++){
        for(int w=0; w<W; w++){
            if(A[h][w]!=-1){
                ans+=cost[A[h][w]][1];
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 384
N, X = map(int, input().split())
x = list(map(int, input().split()))

if N == 1:
    print(abs(x[0]-X))
    exit()

dif = [abs(X-i) for i in x]

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
ans = 0
a = dif[0]

for d in dif[1:]:
    ans = gcd(a, d)
    a = ans

print(ans)

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

using namespace std;
typedef long long ll;

int main()
{
    int N;
    cin >> N;
    ll ans = 0;
    int keta=1, r, l;
    for(int a=1;a<=N;++a){
        if(a == 10) keta = 10;
        else if(a == 100) keta = 100;
        else if(a == 1000) keta = 1000;
        else if(a == 10000) keta = 10000;
        else if(a == 100000) keta = 100000;
        r = a / keta;
        l = a % 10;
        if(l == r){
            ++ans;
        }
        for(int k=10;k<=N;k*=10){
            if(l != 0){
                for(int i=0; l*k+r+i<=N && i<k; i+=10){
                    ++ans;
                }
            }
        }
    }
    cout << ans << endl;
}


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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

ll f(ll n, ll m) {
	return (n * n) % m;
}

int main() {
	ll N, X, M; cin >> N >> X >> M;
	ll A, preA, ans = 0;
	ll loopcnt = 0, cnt = 0, sum_loop = 0, rec_A;
	vector<int> visit(1000000);
	bool dub = false;
	for(int i = 1; i <= N; i++) {
		if(i == 1) {
			A = X;
			ans += A;
			visit[A] = 1;
			cnt++;
			continue;
		}
		preA = A;
		A = f(A, M);
		if(dub) {
			if(A == rec_A) break;
			ans += A; sum_loop += A; loopcnt++; cnt++;
		}
		else {
			if(visit[A]) {
				dub = true; rec_A = A; sum_loop += A; loopcnt++;
			}
			ans += A;
			cnt++;
			visit[A] = 1;
		}
	}
	A = preA;
	if(dub) {
		ans += sum_loop * ((N - cnt) / loopcnt);
		ll rem = (N - cnt) % loopcnt;
		for(int i = 0; i < rem; i++) {
			A = f(A, M);
			ans += A;
		}
	}
	cout << ans << endl;
	return 0;
}


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

using namespace std;

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

void intarrayinput(int sz,int a[]){for(int ___=0;___<sz;++___)scanf("%d",a+___);}
void intarrayoutput(int sz,int a[]){for(int ___=0;___<sz;++___)printf("%d ",a[___]);printf("\n");}
template<class T>T emin(T& t1,T t2){if(t1>t2)return t1=t2;else return t1;}
template<class T>T emax(T& t1,T t2){if(t1<t2)return t1=t2;else return t1;}
template<class T1,class T2>ostream& operator<<(ostream& out,pair<T1,T2> _p){out<<_p.first<<" "<<_p.second;return out;}
template<class T>ostream& operator<<(ostream& out,vector<T> _v){for(int i=0;i<_v.size();++i)out<<_v[i]<<(i+1==_v.size()?"":" ");return out;}
template<class T>void byebye(T t){cout<<t<<endl;exit(0);}

int n;
map<vector<int>,int> mp;
char s[15];
ll ans;

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;++i){
		scanf("%s",s);
		vector<int> v;
		v.resize(26);
		for(int j=0;s[j];++j)v[s[j]-'a']++;
		ans+=ll(mp[v]);
		mp[v]++;
	}
	printf("%lld\n",ans);
	return 0;
}




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

int r[1024][10];
int bd[10][10000],R,C;

void set(){
	for(int i=0;i<1<<10;i++){
		int k=i;
		for(int j=0;j<10;j++){
			r[i][j] = k%2; k=k/2;
		}
	}
}

void solve(){
	int ans=0;
	for(int n=0;n<1<<R;n++){
		int wholesum=0;
		for(int i=0;i<R;i++){
			if(r[n][i]){
				for(int j=0;j<C;j++) bd[i][j]=!bd[i][j];
			}
		}
		for(int j=0;j<C;j++){
			int sum=0;
			for(int i=0;i<R;i++) sum+=bd[i][j];
			wholesum+=max(sum,R-sum);
		}
		ans=max(ans,wholesum);
		for(int i=0;i<R;i++){
			if(r[n][i]){
				for(int j=0;j<C;j++) bd[i][j]=!bd[i][j];
			}
		}
	}
	printf("%d\n",ans);
}

int main(){
	set();
	while(1){
		scanf("%d %d",&R,&C);
		if(R==0 && C==0) break;
		for(int i=0;i<R;i++){
			for(int j=0;j<C;j++){
				scanf(" %d",&bd[i][j]);
			}
		}
		solve();
	}
	return 0;
}

Measured memory_bytes: 1456
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_ 
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

template <class T, class W> 
class rerooting {
private:
    struct edge {
        ll to, rev;
        W w;
    };

    const ll n;
    vector<vector<edge>> g;
    vector<vector<T>> ldp, rdp;
    vector<ll> lptr, rptr;
    const function<T(T,T)> merge;
    const function<T(T,W)> add;
    const T id;

    T dfs(ll v, ll p) {
        while(lptr[v] != p && lptr[v] < (ll)g[v].size()) {
            edge &e = g[v][lptr[v]];
            ldp[v][lptr[v]+1] = merge(ldp[v][lptr[v]], add(dfs(e.to, e.rev), e.w));
            lptr[v]++;
        }
        while(rptr[v] != p && rptr[v] >= 0) {
            edge &e = g[v][rptr[v]];
            rdp[v][rptr[v]] = merge(add(dfs(e.to, e.rev), e.w), rdp[v][rptr[v]+1]);
            rptr[v]--;
        }
        if(p < 0) return rdp[v][0];
        return merge(ldp[v][p], rdp[v][p+1]);
    }

public:
    rerooting(ll n, function<T(T,T)> merge, function<T(T,W)> add, T id) : n(n), g(n), ldp(n), rdp(n), lptr(n), rptr(n), merge(merge), add(add), id(id) {}

    void add_edge(ll u, ll v, W w) {
        g[u].push_back({v, (ll)g[v].size(), w});
        g[v].push_back({u, (ll)g[u].size()-1, w});
    }

    vector<T> build() {
        REP(i, n) {
            ldp[i].assign(g[i].size()+1, id);
            rdp[i].assign(g[i].size()+1, id);
            lptr[i] = 0;
            rptr[i] = (ll)g[i].size()-1;
        }
        vector<T> ans;
        REP(i, n) ans.emplace_back(dfs(i, -1));
        return ans;
    }
};

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

    auto merge = [&](ll l, ll r) { return max(l, r); };
    auto add = [&](ll v, ll w) { return v+w; };
    rerooting<ll, ll> graph(n, merge, add, 0);

    REP(i, n-1) {
        ll u, v;
        cin >> u >> v;
        u--, v--;
        graph.add_edge(u, v, 1);
    }
    auto ans = graph.build();

    REP(i, n) cout << 2*(n-1) - ans[i] << "\n";

    return 0;
}


Measured memory_bytes: 54536
import heapq
from collections import defaultdict
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # xの根となる要素番号を返す
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def isSame(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    N, M = map(int, input().split())

    A = list(map(int, input().split()))

    uf = UF_tree(N)
    for _ in range(M):
        x, y = map(int, input().split())
        uf.unite(x, y)

    d = defaultdict(list)
    for i in range(N):
        heapq.heappush(d[uf.find(i)], A[i])

    if M == N - 1:
        print(0)
        exit()
    elif N < 2 * (N - M - 1):
        print("Impossible")
        exit()

    nodes = 2 * (N - M - 1)
    ans = 0
    tmp = []
    for k, v in d.items():
        ans += heapq.heappop(v)
        tmp.extend(v)
        nodes -= 1

    tmp.sort()
    ans += sum(tmp[:nodes])
    print(ans)


Measured memory_bytes: 31140
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {

		//    	File file = new File("src/in.txt");
		//    	Scanner sc = new Scanner(file);

		Scanner sc = new Scanner(System.in);

		String S = sc.next();
		String T = sc.next();

		char[] s = S.toCharArray();
		char[] t = T.toCharArray();

		int ls = S.length();
		int lt = T.length();

		int ans = lt;

		for(int i=0;i<=ls-lt;i++) {
			int cnt = 0;
			for(int j=0;j<lt;j++) {
					if(t[j]!=s[i+j]) {
						cnt++;
					}
			}
			if(cnt<ans) {
				ans = cnt;
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 35516
#include <stdio.h>

int main(){
    int i,n;
    double a[110],b[110],sum=0,res;
    
    scanf("%d",&n);
    
    for(i=0;i<n;i++){
        scanf("%lf",&a[i]);
        b[i]= 1/a[i];
    }
    
    for(i=0;i<n;i++){
        sum=sum+b[i];
    }
    
    res=1/sum;
    
    printf("%lf\n",res);
    
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <map>
std::string s;
int main(){
  std::cin>>s;
  std::map<char,int> m;
  for(int i =0;i<4;i++){
    m[s[i]]++;
  }
  for(int i =0;i<4;i++){
    if(m[s[i]]!=2){
      std::cout<<"No"<<std::endl;
      return 0;
    }
  }
  std::cout<<"Yes"<<std::endl;
  return 0;
}

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

typedef long long ll;
#define mod 1000000007


int main() 
{
   ll n;
   cin>>n;
   vector<ll> arr(n);
   for(ll i=0;i<n;i++)
   {
      cin>>arr[i];
   }
   vector<ll> csum(n+1,0);
   for(ll i=1;i<=n;i++)
   {
      csum[i]=(csum[i-1]%mod+arr[i-1]%mod)%mod;
   }
   ll ans=0;
   for(ll i=0;i<n-1;i++)
   {
      ans=(ans%mod+(arr[i]%mod*(csum[n]-csum[i+1]+mod)%mod)%mod)%mod;
   }
   cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 6432
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8, pi = acos(-1.0);
bool eq(ld a, ld b){return (abs(b-a)<eps);}
ld dot(Point a, Point b){return real(conj(a)*b);}
ld cross(Point a, Point b){ return imag(conj(a)*b);}
int ccw(Point a, Point b, Point c){
  b-=a;c-=a;
  if(cross(b,c)>eps) return 1;//countor_crockwise
  if(cross(b,c)<-eps) return -1;//crockwise
  if(dot(b,c)<0) return 2;//c,a,b
  if(norm(b)<norm(c)) return -2;//a,b,c
  return 0;//a,c,b
}

const int MAX_N=51;
const int MAX_M=10;

int ccws[MAX_N][MAX_M];
ld lengths[MAX_N][MAX_M];
Point points[MAX_M];
int main(){ _;
  int n,m,m0,x,y;
  while(cin>>n,n!=0){
    REP(i,n+1){
      cin>>m;
      REP(j,m){
	cin>>x>>y;
	points[j]=Point(x,y);
	if(j>=2)
	  ccws[i][j]=ccw(points[j-2],points[j-1],points[j]);
	if(j>=1)
	  lengths[i][j]=abs((points[j-1]-points[j]).real())+abs((points[j-1]-points[j]).imag());
      }
      if(i==0)m0=m;
      else if(m0!=m) continue;
      if(i>0){
	bool s=true,t=true;
	for(int j=2;j<m;j++)
	  if(ccws[0][j]!=ccws[i][j] ||
	     lengths[0][1]*lengths[i][j]!=lengths[i][1]*lengths[0][j])
	    {s=false;break;}
	for(int j=2;j<m;j++)
	  if(ccws[0][j]!=-ccws[i][m+1-j] ||
	     lengths[0][1]*lengths[i][m-j]!=lengths[i][m-1]*lengths[0][j])
	    {t=false;break;}
	if(s||t)
	  cout<<i<<endl;
      }
    }
    cout<<"+++++"<<endl;
  }
}

Measured memory_bytes: 1212
w, h, n = gets.chomp.split.map(&:to_i)
arr = []
n.times{arr << gets.chomp.split.map(&:to_i)}
prev_x, prev_y, sum = arr[0][0], arr[0][1], 0
arr[1..-1].each{|x, y|
    d_x = x - prev_x
    d_y = y - prev_y
    sum += d_x.abs + d_y.abs
    sum -= [d_x.abs, d_y.abs].min if d_x * d_y > 0
    prev_x, prev_y = x, y
}
puts sum


Measured memory_bytes: 6872
#include <bits/stdc++.h>
#define fst first
#define snd second
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define repeat_reverse_from_to(i, m, n) for(lint i = (m); (i) >= (lint)(n); --(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std;
using lint = long long;
using ld = long double;

// バイナリーインデクスドツリー
//sum(l,r) = [l, r)の和, add(i, a) = 0-indexedでi番目の要素にaを足す
template <class T>
struct binary_indexed_tree {
    int n;
    vector<T> x;
    binary_indexed_tree(int n_ = 0) : n(n_), x(n + 1, 0) {}
    int size() const { return n; }
    T sum(int r) const {
        T S = 0;
        for (r = r - 1; r >= 0; r = (r & (r + 1)) - 1) S += x[r];
        return S;
    }
    T sum(int l, int r) const { return sum(r) - sum(l); }
    void add(int k, const T &a) {
        for (; k < n; k |= k + 1) x[k] += a;
    }
    void set(int k, const T &a) { add(k, a - sum(k, k + 1)); }
};

int main(void) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    binary_indexed_tree<int> w(n), e(n);
    repeat (i, n) {
        if (s[i] == 'W') {
            w.add(i, 1);
        }
        else {
            e.add(i, 1);
        }
    }
    
    int ans = 1e9;
    repeat (i, n) {
        if (i == 0) {
            ans = min(ans, e.sum(i+1, n));
        }
        else if(i == n-1) {
            ans = min(ans, w.sum(0, n-1));
        }
        else {
            ans = min(ans, w.sum(0, i) + e.sum(i+1, n));
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3076
//#include<bits\stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 1000000000
#define ldb long double
#define pb push_back
#define get(x) x=read()
#define gt(x) scanf("%d",&x)
#define gi(x) scanf("%lf",&x)
#define put(x) printf("%d\n",x)
#define putl(x) printf("%lld\n",x)
#define gc(a) scanf("%s",a+1)
#define rep(p,n,i) for(RE ll i=p;i<=n;++i)
#define go(x) for(ll i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define fep(n,p,i) for(RE ll i=n;i>=p;--i)
#define pii pair<ll,ll>
#define mk make_pair
#define RE register
#define P 1000000007
#define mod 998244353
#define S second 
#define F first
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define ull unsigned long long
#define ui unsigned
#define zz p<<1
#define yy p<<1|1
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline ll read()
{
    register ll x=0,f=1;register char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const ll MAXN=252;
signed main()
{
	//freopen("1.in","r",stdin);
	int A,B,C,D;
	get(A);get(B);
	if(B>=A)puts("unsafe");
	else puts("safe");
	return 0;
}


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

int main(){
    int N;
    cin >> N;
    long long H[N];
    for(int i = 0; i < N; i++){
        cin >> H[i];        
    }
    int temp = 0;
    int ans = 0;
    for(int i = 1; i < N; i++){
        if(H[i]<=H[i-1]){
            temp++;
        }else{
            ans = max(ans, temp);
            temp = 0;
        }
    }
    ans = max(ans, temp);
    cout << ans << endl;
}

Measured memory_bytes: 1024
class Line:
    def __init__(self,p1,p2):
        if p1[1] < p2[1]:self.s=p2;self.e=p1
        elif p1[1] > p2[1]:self.s=p1;self.e=p2
        else:
            if p1[0] < p2[0]:self.s=p1;self.e=p2
            else:self.s=p2;self.e=p1

def cross(a,b):return a[0]*b[1] - a[1]*b[0]
def CrossPoint(l,m):
    crsl = cross(l.s,l.e)
    crsm = cross(m.s,m.e)
    det = (l.s[1] - l.e[1])*(m.e[0] - m.s[0]) - (l.e[0]-l.s[0])*(m.s[1]-m.e[1])
    x = (m.s[0] - m.e[0]) * crsl + (l.e[0] - l.s[0]) * crsm
    y = (m.s[1] - m.e[1]) * crsl + (l.e[1] - l.s[1]) * crsm
    return [x/det,y/det]

q = int(input())
for i in range(q):
    x0,y0,x1,y1,x2,y2,x3,y3 = [int(i) for i in input().split()]
    l = Line([x0,y0],[x1,y1])
    m = Line([x2,y2],[x3,y3])
    P = CrossPoint(l,m)
    print(P[0],P[1])

Measured memory_bytes: 7808
#include<set>
#include<algorithm>
#include<iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    set<int> s1, s2, s;
    for (int i = 0; i < n ;i++) {
        int t;cin >> t;
        s1.insert(t);
    }
    cin >> n;
    for (int i = 0;i < n; i++) {
        int t;cin >> t;
        s2.insert(t);
    }
    set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(s, s.begin()));
    for(auto it : s) {
        cout << it << endl;
    }
    return 0;
}


Measured memory_bytes: 40592
#include <bits/stdc++.h>
/*
                 ,,ggddY888Ybbgg,,
          ,agd8""'   .d8888888888bga,
       ,gdP""'     .d88888888888888888g,
     ,dP"        ,d888888888888888888888b,
   ,dP"         ,8888888888888888888888888b,
  ,8"          ,8888888P"""88888888888888888,
 ,8'           I888888I    )88888888888888888,
,8'            `8888888booo8888888888888888888,
d'              `88888888888888888888888888888b
8                `"8888888888888888888888888888
8                  `"88888888888888888888888888
8                      `"8888888888888888888888
Y,                        `8888888888888888888P
`8,                         `88888888888888888'
 `8,              .oo.       `888888888888888'
  `8a             8888        88888888888888'
   `Yba           `""'       ,888888888888P'
     "Yba                   ,88888888888'
       `"Yba,             ,8888888888P"'
          `"Y8baa,      ,d88888888P"'
               ``""YYba8888P888"'
*/
using namespace std;
#define int long long
#define KOD ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define sz size()
#define S second
#define X(a,b) a = ((b) > (a)) ? (b) : (a);
#define N(a,b) a = ((b) > (a)) ? (a) : (b);
#define F first
#define SORT(x) sort(x.begin(),x.end())
#define Rev(a) reverse(a.begin() , a.end());
#define pb push_back
#define pre(x) cout.precision(0);
#define bit(x) __builtin_popcount(x)
#define is(a) insert(a);
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef unordered_map<int,int> wi;
typedef unordered_set<int> si;
const int M = 1e5+2;
const int inf = 1e18;
main(){
	int a , b , c , d;
	cin >> a ;
	set<string>st;
	while(a--){
		string s;
		cin >> s;
		st.is(s);	
	}
	cout << st.sz;
}


Measured memory_bytes: 19176
# -*- coding: utf-8 -*-

import sys

rom = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
for line in sys.stdin:
    ans = 0
    for i in range(len(line)-2):
        if rom[line[i]] < rom[line[i+1]]:
            ans -= rom[line[i]]
        else:
            ans += rom[line[i]]
    ans += rom[line[len(line)-2]]
    print ans

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

using namespace std;
//using namespace __gnu_pbds;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

const int MOD = 1000000007;
double PI = 4*atan(1);

ll ans[1000000], cum[1000000];

int main() {
	ll n; cin >> n; ans[n-1] = n, cum[n-1] = n;
	
	for (int i = n-2; i >= 0; --i) {
		ans[i] = (ans[i]+(n-1) * (n-1)) % MOD;
		ans[i] = (ans[i]+ans[i+1]) % MOD;
		
		ans[i] = (ans[i]+(n+1-max((ll)2,n-1-i))) % MOD;
		if (i+3 < n) ans[i] = (cum[i+3]+ans[i]) % MOD;
		cum[i] = (cum[i+1]+ans[i]) % MOD;
	}
	
	cout << ans[0];
}

Measured memory_bytes: 15872
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        C solver = new C();
        solver.solve(1, in, out);
        out.close();
    }

    static class C {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int n = Integer.parseInt(in.next());
            int d[] = new int[n];
            for (int i = 0; i < n; i++) {
                d[i] = Integer.parseInt(in.next());
            }
            Arrays.sort(d);
            int mid = n / 2;
            if (d[mid] - d[mid - 1] == 0) {
                out.println(0);
            } else {
                // 出力
                out.println(d[mid] - d[mid - 1]);
            }

        }

    }
}



Measured memory_bytes: 49060
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>

using namespace std;

int main() {
  long A,B,K;
  cin >> A >> B >> K;


  for (int i=0; i<K; i++) {
    if (i%2 == 0) {
      if (A % 2 == 1) A--;
      A /= 2;
      B += A;
    } else {
      if (B % 2 == 1) B--;
      B /= 2;
      A += B;
    }

  }
  cout << A << " " << B << endl;
}


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

bitset<25600> dp[81][81];
int a[81][81], b[81][81];

int main() {
  int h, w;
  cin >> h >> w;
  for (int i = 1; i <= h; i++)
    for (int j = 1; j <= w; j++)
      cin >> a[i][j];
  for (int i = 1; i <= h; i++)
    for (int j = 1; j <= w; j++)
      cin >> b[i][j];
  dp[1][1][b[1][1] - a[1][1] + 12800] = true;
  dp[1][1][a[1][1] - b[1][1] + 12800] = true;

  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      int d = abs(b[i][j] - a[i][j]);
      if (i > 1) {
        dp[i][j] |= dp[i - 1][j] >> d;
        dp[i][j] |= dp[i - 1][j] << d;
      }
      if (j > 1) {
        dp[i][j] |= dp[i][j - 1] >> d;
        dp[i][j] |= dp[i][j - 1] << d;
      }
    }
  }

  int ans = 99999;
  for (int i = 0; i < 25600; i++)
    if (dp[h][w][i] && abs(i - 12800) < ans)
      ans = abs(i - 12800);
  cout << ans << endl;
}

Measured memory_bytes: 20608