akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD=998244353;

int main(void){
    int n;
    cin>>n;
    Graph G(n);
    map<pair<int,int>,int> weight;
    rep(i,n-1){
        int u,v,w;
        cin>>u>>v>>w;
        u--;
        v--;
        G[u].push_back(v);
        G[v].push_back(u);
        weight[make_pair(u,v)]=w;
        weight[make_pair(v,u)]=w;
    }
    vector<int> dist(n,-1);
    queue<int> que;
    dist[0]=0;
    que.push(0);
    while(!que.empty()){
        int v=que.front();
        que.pop();
        for(int nv:G[v]){
            if(dist[nv]!=-1) continue;
            //cout<<v<<" "<<nv<<" "<<weight[make_pair(v,nv)]<<endl;
            if(weight[make_pair(v,nv)]%2==0) dist[nv]=dist[v];
            else dist[nv]=(dist[v]+1)%2;
            que.push(nv);
        }
    }
    rep(i,n) cout<<dist[i]<<endl;
    return 0;
}

Measured memory_bytes: 21700
/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-04-19 20:14:57
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <iomanip>
#include <random>
#include <utility>
#include <chrono>

using namespace std;

using int64 = long long;

template <class T> using binary_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T, class U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) { return os << '(' << p.first << ", " << p.second << ')'; }
template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) { int flag = 0; for (auto e : vec) os << (flag++ ? ", " : "{") << e; return os << '}'; }
template <class T> std::ostream& operator<<(std::ostream& os, const std::set<T>& st) { int flag = 0; for (auto e : st) os << (flag++ ? ", " : "{") << e; return os << '}'; }
template <class T, class U> std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) { int flag = 0; for (auto e : mp) os << (flag++ ? ", " : "{") << e; return os << '}'; }
template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& vec) { for (T& e : vec) is >> e; return is; }

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}

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

  string s; cin >> s;

  if (s.find("7") != string::npos) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 3644
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"
int main() {
	while (1) {
		int N; cin >> N;
		if (!N)break;
		string st; cin >> st;
		while (N--) {
			string newst;
			char pre = ' ';
			int num = 1;
			for (auto c : st) {
				if (c == pre) {
					num++;
				}
				else {
					if (pre != ' ') {
						newst += to_string(num);
						newst += pre;
					}
					pre = c;
					num = 1;
				}
			}
			newst += to_string(num);
			newst += pre;
			st = newst;
		}
		cout << st << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3320
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	for(int i=1;i<=100000;i++)
	{
		int c=i*0.08,d=i*0.1;
		if(c==a&&d==b)
		{
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<"-1";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main(){
  priority_queue < pair<int,int> > q;
  int n,p,a,v,N[1000001]={};
  cin>>n>>p;
  for(int i=1;i<=n;i++)q.push( make_pair(0,-i) );
  for(int i=0;i<p;i++){
    cin>>a>>v;
    N[a]+=v;
    q.push( make_pair(N[a],-a) );
    while(1){
      if(q.top().first!=N[-q.top().second]&&q.top().first!=0)q.pop();
      else break;
    }
    cout<<-q.top().second<<" "<<q.top().first<<endl;
  }
  return 0;
}

Measured memory_bytes: 23148
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <cstdlib>
#define INF 100000000
#define _INF -100000000
#define INFLL (long long)1e14
#define _INFLL (long long)-1e14
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> P;

struct node {
	bool done;
	vi ed, dist;
	int id, from;
	ll d;
	bool operator<(const node & another) const {
		return !(d != another.d ? d < another.d : id < another.id);
	}
};


void dijkstra(vector<node> nodes, int n, int start) {
	priority_queue<node> pq;
	nodes[start].d = 0;
	pq.push(nodes[start]);
	while (pq.size()) {
		node focus = pq.top(); pq.pop();
		if (nodes[focus.id].done) continue;
		Loop(i, focus.ed.size()) {
			if (nodes[focus.ed[i]].done) continue;
			if (focus.d + focus.dist[i] < nodes[focus.ed[i]].d) {
				nodes[focus.ed[i]].d = focus.d + focus.dist[i];
				nodes[focus.ed[i]].from = focus.id;
				pq.push(nodes[focus.ed[i]]);
			}
		}
		nodes[focus.id].done = true;
	}
	Loop(i, n) {
		if (nodes[i].d == INFLL) cout << "INF" << endl;
		else {
			cout << nodes[i].d;
			/*
			stack<int> stk;
			node focus = nodes[i];
			stk.push(i);
			while (focus.from != -1) {
			stk.push(focus.from);
			focus = nodes[focus.from];
			}
			while (stk.size()) {
			cout << " " << stk.top();
			stk.pop();
			}
			*/
			cout << endl;
		}
	}
	return;
}

int main() {
	int v, e, r; cin >> v >> e >> r;
	vector<node> nodes(v + 5);
	Loop(i, v) nodes[i] = { false,{},{}, i, -1, INFLL };
	Loop(i, e) {
		int s, t, d; cin >> s >> t >> d;
		nodes[s].ed.push_back(t);
		nodes[s].dist.push_back(d);
		/*
		nodes[t].ed.push_back(s);
		nodes[t].dist.push_back(d);
		*/
	}
	dijkstra(nodes, v, r);
}

Measured memory_bytes: 45256
#include <bits/stdc++.h>
#define ll long long


using namespace std;
double a[20000];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 int n;cin >>n;
 for(int i=0;i<n;i++)cin >> a[i];

 sort(a,a+n);
 double sum=(a[0]+a[1])/2;
 for(int i=2;i<n;i++)
     sum=(sum+a[i])/2;


 cout << sum;

}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <functional>
#include <cstring>
#include <regex>
#include <random>
#include <cassert>
#include <stack>
#include <climits>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, s, n) for (int i = (s); i < (int)(n); i++)
#define revrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define revrepr(i, s, n) for (int i = (n) - 1; i >= s; i--)
#define debug(x) cerr << #x << ": " << x << "\n"
#define popcnt(x) __builtin_popcount(x)

const double PI = acos(-1.0);

using ll = long long;
using P = pair<int, int>;

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

template<class T>
istream& operator >>(istream &is, vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++) cin >> v.at(i);
    return is;
}

template<class T, class U>
ostream& operator <<(ostream &os, pair<T, U> p) {
    cout << '(' << p.first << ", " << p.second << ')';
    return os;
}

template<class T>
void print(const vector<T> &v, const string &delimiter) { rep(i, v.size()) cout << (0 < i ? delimiter : "") << v.at(i); cout << endl; }

template<class T>
void print(const vector<vector<T>> &vv, const string &delimiter) { for (const auto &v: vv) print(v, delimiter); }


int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    rep(i, n) cin >> a[i] >> b[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    if (n % 2 == 0) {
        int l = a[(n - 1) / 2] + a[n / 2];
        int r = b[(n - 1) / 2] + b[n / 2];

        cout << r - l + 1 << endl;
    }
    else {
        int l = a[(n - 1) / 2];
        int r = b[(n - 1) / 2];

        cout << r - l + 1 << endl;
    }
}

Measured memory_bytes: 4828
X,Y,Z,K = gets.split.map &:to_i
A,B,C = (0...3).map{ gets.split.map(&:to_i).sort.reverse }
cands = [[0,0,0]]
used = {}
used[cands[0]] = 1
K.times {
  r = (0...cands.size).max_by{ |r|
    i,j,k = cands[r]
    A[i] + B[j] + C[k]
  }
  fail if !r
  #p cands[r]
  i,j,k = cands.delete_at(r)
  puts A[i] + B[j] + C[k]
  ns = []
  if i+1 < X
    ns << [i+1,j,k]
  end
  if j+1 < Y
    ns << [i,j+1,k]
  end
  if k+1 < Z
    ns << [i,j,k+1]
  end
  ns.reject{ |c| used[c] }.each{ |c|
    cands << c
    used[c] = 1
  }
}


Measured memory_bytes: 2680
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define INF 999999999
#define rep(i,n) for(int i=0;i<n;i++)
const int mod = 1000000007;
ll cnt = 0;
ll gcd(ll x,ll y){
   return y ? gcd( y , x%y ) : x;
}



int main(){
  int n;    cin >> n;
  
  map<ll,ll>mp;
  priority_queue<ll>que;
  rep(i,n){
      int a;
      cin >> a;
      mp[a]++;
      if(mp[a] > 0 && mp[a]%2==0){
        
          que.push(a);
      }
    }
    if(que.size() < 2){
        cout << 0 << endl;
        return 0;
    }
    ll c,d,ans;
    c = que.top();
    que.pop();
    d = que.top();
    ans = c*d;
    cout << ans << endl;

}

Measured memory_bytes: 6528
#include <iostream>
#include <map>
#include <string>
#include <algorithm>

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

using namespace std;

int main() {
    int n = 0;
    long double ret = 0;
    cin >> n;
    long double cnt = 0;
    for (int i = 1; i <= n; i++){
        if (i % 2 == 1){
            cnt++;
        }
    }
    ret = cnt / n;
    cout << ret << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int max(int x, int y){
    if(x > y) return x;
    else      return y;
}

int abs(int x){
    if(x < 0){
        x *= -1;
    }
    return x;
}

int main(void){

    int a, b, c, sum;

    scanf("%d %d %d", &a, &b, &c);

    sum = abs(a-b) + abs(b-c) + abs(a-c);
    //1,2 1,3 2,3

    sum -= max( max( abs(a-b), abs(b-c)),  abs(a-c));


    printf("%d\n",sum);

    return 0;
}


Measured memory_bytes: 128
# import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()
X, N = map(int,input().split())
try:
  p = list(map(int, input().split())) # 1行, 配列
  xm = X - 1
  xp = X + 1

  if X in p:
    while True:
      if xm in p:
        xm = xm - 1
      else:
        print(xm)
        break
      if(xp in p):
        xp = xp +1
      else:
        print(xp)
        break
  else:
    print(X)
except:
  print(X)



Measured memory_bytes: 61860
N, M, X = map(int, input().split())
A = list(map(int, input().split()))
front = 0

length = len(A)

for i in range(N+1):
    if A[i]<X:
        front +=1
    else:
        break

back = length - front

if front<back:
    print(front)
else:
    print(back)


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

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define RFOR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define LL long long
#define INF INT_MAX

const double EPS = 1e-14;
const double PI  = acos(-1.0);


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

  int t = int(1e6) + 2;
  bool d[t];
  REP (i, t) d[i] = false;

  int cnt = 0;
  while (true) {
    if (d[n]) break;
    d[n] = true;
    if (n % 2 == 0) n /= 2;
    else n = 3 * n + 1;

    cnt++;
  }
  cout << cnt + 1 << endl;
}


Measured memory_bytes: 1280
N, M = map(int, input().split())


sub = [list(input().split()) for _ in range(M)]

AC_set = set()
WA_dic = {}

AC_cnt = 0
WA_cnt = 0

for p, ans in sub:
    p = int(p)
    if ans == 'AC':
        if p not in AC_set:
            AC_cnt += 1
            AC_set.add(p)
    else:
        if p not in AC_set:
            if p not in WA_dic:
                WA_dic[p] = 1
            else:
                WA_dic[p] += 1

for p in AC_set:
    WA_cnt += WA_dic.get(p, 0)

print(AC_cnt, WA_cnt)


Measured memory_bytes: 34952
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>
 
using namespace std;
 
#define pb push_back
#define eb emplace_back
#define mp make_pair
#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...)
#endif
#define sz(x) ((int)(x).size())
#define forn(i, n) for (int i = 0; i < (n); i++)
 
#ifdef DEBUG
struct Timestamper {
  string msg;
  clock_t start;
 
  Timestamper(const string &_msg) : msg(_msg), start(clock()) {}
  ~Timestamper() {
    eprintf("[ %s ] Time=%.3lfs\n", msg.c_str(), (clock() - start) * 1.0 / CLOCKS_PER_SEC);
  }
} __timestamper("end");
#else
struct Timestamper {};
#endif
 
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
 
const int inf = 1e9;
 
int n;
vvi es;
vb isleaf;
 
void dfs1(int v, int par = -1) {
  int chi = 0;
  bool allLeaf = true;
  for (int b : es[v])
    if (b != par) {
      chi++;
      dfs1(b, v);
      allLeaf &= isleaf[b];
    }
  if (chi <= 1 && allLeaf)
    isleaf[v] = true;
}
 
int dfs2(int v, int par = -1) {
  if (isleaf[v]) return 1;
 
  int ans = 0;
  bool hasleaf = false;
  for (int b : es[v])
    if (b != par) {
      ans += dfs2(b, v);
      hasleaf |= isleaf[b];
    }
  if (hasleaf) ans--;
  return ans;
}
 
int main() {
  #ifdef DEBUG
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
  #endif
 
  while (scanf("%d", &n) >= 1) {
    es = vvi(n);
    forn (i, n - 1) {
      int a, b;
      scanf("%d%d", &a, &b);
      es[a].pb(b);
      es[b].pb(a);
    }
    int root = 0;
    while (root < n && sz(es[root]) <= 2) root++;
    if (root == n) {
      printf("1\n");
    } else {
      isleaf = vb(n, false);
      dfs1(root);
      int ans = dfs2(root);
      printf("%d\n", ans);
    }
  }
  return 0;
}


Measured memory_bytes: 9856
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
#include <numeric>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
//typedef pair<int, int>pint;
//typedef vector<int>vint;
//typedef vector<pint>vpint;
//typedef pair<pint, int> P1;
//typedef pair<int, pint> P2;
//typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };

typedef pair<int, int> P;

int R, C, sy = 0, sx = 0, gy , gx;
vector<string>slist;
int blackCnt = 0;



int main(void) {
	
	cin >> R >> C;

	gy = R - 1; gx = C - 1;

	for (int i = 0; i < R; i++) {
		string s;
		cin >> s;
		slist.push_back(s);
	}

	for (int i = 0; i < R; i++) 
		for (int j = 0; j < C; j++) 
			if (slist[i][j] == '#')blackCnt++;

	vector<vector<int>>mat(R, vector<int>(C, 999999));
	int yy[4] = { -1, 0, 1, 0 };
	int xx[4] = { 0, 1, 0, -1 };
	
	queue<P> qlist;
	mat[sy][sx] = 0;
	qlist.push(P(sy, sx));

	while ( qlist.size() > 0 )
	{
		P p = qlist.front();
		qlist.pop();

		if (p.first == gy && p.second == gx)break;

		for (int i = 0; i < 4; i++) {
			int ny = p.first + yy[i];
			int nx = p.second + xx[i];

			if (ny >= 0 && ny < R && 0 <= nx && nx < C && slist[ny][nx] == '.' && mat[ny][nx] == 999999) {
				mat[ny][nx] = mat[p.first][p.second] + 1;
				qlist.push(P(ny, nx));
			}

		}

	}

	if (mat[gy][gx] == 999999) {
		cout << -1 << endl;
	}
	else {
		cout << R * C - (mat[gy][gx] + 1) - blackCnt << endl;
	}

	return 0;
}

Measured memory_bytes: 3580
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        double x = sc.nextDouble();

        double y = x*x*Math.PI;
        double z = 2*x*Math.PI;

        System.out.printf("%f %f\n",y,z);
    }
}


Measured memory_bytes: 28188
n = int(input())
a = list(map(int,input().split()))
dic = {}
for i in a:
  if i in dic:
    dic[i] += 1
  else:
    dic[i] = 1
    
first = 0
second = 0
for i,j in dic.items():
  if j >= 2:
    if i > first :
      second = first
      first = i
    elif i > second:
      second = i
      
  if j >= 4:
    if i > first :
      second = first
      first = i
    elif i > second:
      second = i
  
print(first*second)

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

int main() {
  int N, A, B, x;
  cin >> N >> A >> B;
  if (N * A > B) {
    int x = B;
    cout << x << endl;
  }
  else if (N * A < B) {
    int x = N * A;
    cout << x << endl;
  }
  else {
    int x = B;
    cout << x << endl;
  }
}

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

int main() {
    int x, n, temp;
    cin >> x >> n;
    int p[102] = {};

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

    int i = 0;

    for (; x - i >= 0 || x + i <= 101; i++) {
        if (x - i >= 0 && p[x - i] == 0) {
            cout << x - i;
            return 0;
        } else if (x + i <= 101 && p[x + i] == 0) {
            cout << x + i;
            return 0;
        }
    }
    return 0;
}

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

int main() {
    int N, K;
    string str;

    cin >> N >> K;
    cin >> str;

    if ( str[K-1] == 'A' ){
            str[K-1] = 'a';
    }
        if ( str[K-1] == 'B' ){
            str[K-1] = 'b';
    }
        if ( str[K-1] == 'C' ){
            str[K-1] = 'c';
    }

    cout << str;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
//#define double long double
#define endre getchar();getchar();return 0
#define moder (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1)*x;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)*mod_pow(kai(x - y), moder - 2, moder) % moder*mod_pow(kai(y), moder - 2, moder) % moder;
}
/*--------Library Zone!--------*/


signed main() {
	int n, a, b;
	cin >> n >> a >> b;
	if (b < a || (n == 1 && a != b))cout << 0 << endl;
	else {
		cout << (a + b + (n - 2)*b) - (a + b + (n - 2)*a) + 1 << endl;
	}
	endre;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>				//Written by ThiDaiLoc
using namespace std;				//Team Three Wolves
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pll;
#define fu(i,a,b)   for(ll i=a;i<b;i++)
#define fd(i,b,a)   for(ll i=b;i>=a;i--)
#define ms(a,x)     memset(a, x, sizeof a)
#define prec(n)     fixed<<setprecision(n)
#define pb(i)       push_back(i)
#define popb()      pop_back()
#define sc(a)       cin>>a
#define sc2(a,b)    cin>>a>>b
#define pr(a)       cout<<a<<" "
#define pr2(a,b)    cout<<a<<" "<<b<<" "
#define lowb(a,n,x) lower_bound(a,a+n,x) -a
#define lowb2(a,x)  lower_bound(a.begin(),a.end(),x) -a.begin()
#define all(x)      (x).begin(), (x).end()
#define sz(a)       (ll)a.size()
#define le(s)       (ll)s.length()						
#define re          return 	
#define	mp(a,b)     make_pair(a,b)
#define se          second
#define fi          first 
#define debug(x)    cerr << #x << " = " << x << endl
#define INPUT       freopen("locin.txt", "r", stdin)
#define OUTPUT      freopen("locout.txt", "w", stdout)
void inline minize(ll& a,ll b){a=(a>b?b:a);};
void inline maxize(ll& a,ll b){a=(a<b?b:a);};

double const eps = 1e-6;
ll const Base=1e9+7,oo=1e17,MAXN=1e7;
ll arr[3][1000],c,d;

bool inline difmin(ll x,ll y,ll deltamin,ll deltamax){
	ll ymax,ymin,xmin,xmax;
	xmin=x+deltamin;
	xmax=x+deltamax;
	
	ymin=y-d; ymax=y-c;
	if(!(xmin>ymax or xmax<ymin))re 1;
	
	ymin=y+c; ymax=y+d;
	if(!(xmin>ymax or xmax<ymin))re 1;
	re 0;
}

ll Solves(){
	//INPUT;
	ll n,x,a,b,nega,posi,f;
	
	cin>>n>>a>>b>>c>>d;
	
	fu(i,0,n-2+1){
		nega=i;
		posi=n-2-i;
		f=difmin(a-c*nega+posi*c,b,-(d-c)*nega,(d-c)*posi);
		if(f)re cout<<"YES",0;
	}
	
	
	cout<<"NO";
	
	// Hack it if you can :)
}
int main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	Solves();
}

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

int main() {
    int A,B;
    cin >> A>>B;
    vec<string> c(100,string(100,'.'));
    rep(i,50) c[i] = string(100,'#');

    rep(i,A-1) c[(i/50)*2][(i%50)*2] = '.';
    rep(i,B-1) c[99-((i/50)*2)][(i%50)*2] = '#';
    
    cout << 100 << " " << 100 << endl;
    rep(i,100) cout << c[i] << endl;
}

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

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    ll N; cin >> N;
    string ans = "";

    if(N == 0){
        cout << 0 << endl;
        return 0;
    }

    ll radix = 1;
    ll div = 2;
    while(N != 0){
        if(N%div == 0){
            ans = '0'+ans;
        }
        else{
            ans = '1'+ans;
            N -= radix;
        }
        radix *= -2;
        div *= 2;

    }

    cout << ans << endl;
}

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

// 型名の省略
typedef unsigned int uint;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> P;
typedef pair<lint, lint> Plint;
 
const int MOD = 1000000007;
const int INF = 1<<18;
const lint INFLINT = 1LL << 60;
const double PI=acos(-1.0);
 
// cinとcoutの高速化
#define endl "\n"
struct cinacc{cinacc(){cin.tie(0);ios::sync_with_stdio(false);}}cinaccc;
struct coutacc{coutacc(){cout.setf(ios::fixed);cout.precision(12);}}coutaccc;
 
// 繰り返し
#define rep(i,n) for(lint i=0;i<(lint)(n);i++)
#define reps(i,n) for(lint i=0;i<=(lint)(n);i++)
#define rrep(i,n) for(lint i=(lint)(n)-1;i>0;i--)
#define rreps(i,n) for(lint i=(lint)(n)-1;i>=0;i--)

#define pb push_back

#define ALL(s) (s.begin(), s.end())
#define SZ(s) (s.size())

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

// Union-Find-Tree
class UnionFind {
	vector<int> par;
	UnionFind(int n):par(n){rep(i,n)par[i]=i;}
	int root(int x){if(par[x]==x)return x;return par[x]=root(par[x]);}
	void unite(int x,int y){int rx=root(x);int ry=root(y);if(rx==ry)return;par[rx]=ry;}
	bool same(int x,int y){return root(x)==root(y);}
};

int main() {
    int k, s;
    cin >> k >> s;
    
    lint ans;
    for(int x = 0; x <= k; x++) {
        for(int y = 0; y <= k; y++) {
            int z = s - x - y;
            if(0 <= z && z <= k) ans++;
        }
    }
    
    cout << ans;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
//increase stack size
#pragma comment(linker, "/STACK:16777216")

ll mxm() {return LLONG_MIN;}
template<typename... Args>
ll mxm(ll a, Args... args) { return max(a,mxm(args...)); }

ll mnm() {return LLONG_MAX;}
template<typename... Args>
ll mnm(ll a, Args... args) { return min(a,mnm(args...)); }

template<class T> ostream& operator<<(ostream& os,vector<T> V){
	os<<"[ ";for(auto v:V)os<<v<<" ";return os<<"]";
}
template<class L,class R> ostream& operator<<(ostream& os,pair<L,R> P){
	return os<<"("<<P.first<<","<<P.second<<")";
}

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__,__VA_ARGS__)
template<typename Arg1>
void __f(const char* name,Arg1&& arg1){
	cout<<name<<" : "<<arg1<<endl;
}
template <typename Arg1,typename... Args>
void __f(const char* names,Arg1&& arg1,Args&&... args){
	const char* comma=strchr(names+1,',');cout.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1,args...);
}
#else
#define trace(...) 1
#endif

#define ld long double
#define pll pair<ll,ll>
#define ii pair<int,int>
#define vll vector<ll>
#define vii vector<ii>
#define vi vector<int>
#define vpll vector<pll>
#define vld vector<ld>
#define vvld vector<vld>
#define vvi vector<vi>
#define vvll vector<vll>
#define vvpll vector<vpll>
#define vvii vector<vii>
#define I insert
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x)	x.begin(),x.end()

const int mod=1e9+7;
// 128 bit: __int128
inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int sub(int a,int b){a-=b;if(a<0)a+=mod;return a;}
inline int mul(int a,int b){return (a*1ll*b)%mod;}
inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
inline int inv(int a){return power(a,mod-2);}

struct compare{
	bool operator() (const int &a,const int &b) const{
		return a>b;
	}
};

ll pr(ll i, ll x){
	ll ans = 1;
	while(x--)
		ans *= i;
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
	ll n;
	cin >> n;
	ll rem = n;
	ll lst = 1;
	for(ll i = 1;; i++){
		if(pr(26, i) < rem)
			rem -= pr(26, i), lst++;
		else break;
	}
	string ans;
	for(ll i = 0; i < lst; i++){
		for(ll j = 0; j < 26; j++){
			if(pr(26, lst - i - 1) < rem)
				rem -= pr(26, lst - i - 1);
			else{
				ans += (char)(j + 'a');
				break;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
 
#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << a << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair
 
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    int n = si(s);
    ll ans = 0;
    {
        vector<char> ns;
        for (auto c : s) {
            if (c == '1' && !ns.empty() && ns.back() == '1') {
                ns.pop_back();
                ans += n;
                n -= 2;
            }
            else ns.push_back(c);
        }
        s = "";
        for (auto c : ns) s += c;
    }
    ll zeros = 0;
    n = si(s);
    dforsn(i,0,n) {
        if (s[i] == '1') {
            ans += (i+2)/2;
            ans += zeros;
        }
        else zeros++;
    }
    cout << ans;

    return 0;
}


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

int main(void) {
    int N, K;
    cin >> N >> K;
    vector< int > A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int a_max = 0;
    for (int i = 0; i < N; i++) {
        a_max = max(a_max, A[i]);
    }
    int l = 0, r = a_max, middle;
    while (l + 1 < r) {
        middle = (l + r) / 2;
        long long sum = 0;
        for (int i = 0; i < N; i++) {
            sum += (A[i] + middle - 1) / middle - 1;
        }
        if (sum > K) {
            l = middle;
        } else {
            r = middle;
        }
    }
    printf("%d\n", r);

    return 0;
}


Measured memory_bytes: 4016
import heapq

X,Y,A,B,C = map(int,input().split())
P = [int(v) for v in input().split()]
Q = [int(v) for v in input().split()]
R = [int(v) for v in input().split()]

P.sort(reverse=True)
Q.sort(reverse=True)
R.sort()

ans = 0
apples = []
for v in P[:X]: apples.append(v)
for v in Q[:Y]: apples.append(v)

apples.sort()

trans_apple = R.pop()


for i in range(len(apples)):
    if apples[i] < trans_apple:
        apples[i] = trans_apple
        if len(R) == 0: break
        trans_apple = R.pop()
    else:
        break

print(sum(apples))


Measured memory_bytes: 23120
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <iomanip> 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb;
typedef vector<ull> vul;
typedef vector<pair<ll, ll>> vpl;
typedef pair<ll, ll> pl;
#define For(i, n) for(ll i = 0; i < n; i++)
#define len(n) (ll)(n).size()
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())
ll g[1010][1010];
ll dp[1010][1010];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll h, w;
	char s;
	cin >> h >> w;
	For(i, h) {
		For(j, w) {
			cin >> s;
			if (s == '#') {
				g[i + 1][j + 1] = 1;
			}
		}
	}
	dp[1][1] = 1;
	for (ll i = 1; i <= h; i++) {
		for (ll j = 1; j <= w; j++) {
			if (g[i][j] == 0 && !(i == 1 && j == 1)) {
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % ((ll)1e9 + 7);
			}
			//cout << dp[i][j] << ' ' << i << ' ' << j << endl;
		}
	}
	cout << dp[h][w];
	return 0;
}

Measured memory_bytes: 19408
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace io{
	const int l=1<<20;
	char buf[l],*s,*t;
	inline char gc(){
		if(s==t){
			t=(s=buf)+fread(buf,1,l,stdin);
			return s==t?EOF:*s++;
		}
		return *s++;
	}
	char c;
	template<class IT>inline void gi(IT &x){
		x=0;c=gc();while(c<'0'||c>'9')c=gc();
		while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=gc();}
	}
};
using io::gi;
template<class IT>inline void cmin(IT &a,IT b){if(b<a)a=b;}
template<class IT>inline void cmax(IT &a,IT b){if(a<b)a=b;}
const ll p=998244353ll,inf=1000000000000000000ll;
const int N=200005;
int a[N];
int main(){
	int n,i;double b;
	scanf("%d",&n);
	for(i=1;i<=n;++i)scanf("%d",&a[i]);
	sort(a+1,a+n+1);b=a[1];
	for(i=2;i<=n;++i)b=(b+a[i])/2.0;
	printf("%lf",b);
	return 0;
}

Measured memory_bytes: 256
/*
coded by : Bissultanov Yedyge;
:)
¤
•
¦
§
*/
#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
 
#define mp make_pair
#define np next_permutation
 
#define bg begin()
#define ed end()
 
#define int long long
#define ioi return 0;
 
#define sz size()
#define fix fixed<<setprecision
 
#define lb lower_bound
#define ub upper_bound
 
#define fr first
#define sc second
 
#define pb push_back
#define ppb pop_back
 
#define pf push_front
#define ppf pop_front
 
typedef long double ld;
typedef unsigned long long ull;
 
const int N = (int)5e5 + 7;
const int inf = (int)1e9 + 7;
 
using namespace std;
 
int a , b , k;
int ans, cnt;
int c[N];

main(){
	ios
		cin >> a >> b >> k;
		for ( int i = 1 ; i <= 100 ; ++i ){
			if ( a % i == 0 && b % i == 0 ){
				c[i] = i;
			}
		}
		for ( int i = 100 ; i >= 1 ; --i ){
			if ( c[i] != 0 ){
				k--;
			}
			if ( k == 0 ){
				cout << c[i];
				ioi
			}
		}
	ioi	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<ll, ll>
#define SZ(x) ((int)(x).size())
//#define endl "\n"
#define vvi vector<vector<int> >
#define vvl vector<vector<long long> >
ll mod = 998244353;
const double pi = acos(-1.0);

ll n;

ll sear(ll l, ll r, ll i){
    //cout<<i<<endl;
    while(r>(l+1)){
        ll m = (l+r)/2;
        ll x = (i*m);
        if(x<n)
            l = m;
        else
            r = m;
        //cout<<l<<" "<<r<<endl;
    }
    return l;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout<<fixed;
    cout.precision(12);
    cin>>n;
    ll an = 0;
    for(ll i=1;i<=n-1;i++){
        an += sear(0, n, i);
    }
    cout<<an<<endl;
    return 0;
}


Measured memory_bytes: 3644
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const [a, b, x] = input[0].map(BigInt);

  if (a === 0n) {
    return (b / x + 1n).toString();
  } else {
    return (b / x - (a - 1n) / x).toString();
  }
};

console.log(main(read()));


Measured memory_bytes: 29640
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main() {
int a;
cin >> a;
for(int i=0;i<10;i++)
    {
    if(i*111>=a && (i-1)*111<a){
        cout << i*111 << endl;
        
    }
    }   
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
int a,b,c,d;
scanf("%d",&a);
scanf("%d",&b);
scanf("%d",&c);
 
if(a>b){
d = a ;
a = b;
b = d;
}

if(a<c && b>c){
printf("Yes");
}

else{
printf("No");
}
return 0;
}

Measured memory_bytes: 128
import java.util.Scanner

object Main {
  val sc = new Scanner(System.in)
  def main(args: Array[String]): Unit = {
    val ts = List.fill(5)(sc.nextInt)
    val (a,b) = ts.partition(_ % 10 == 0)

    val res = if (b.isEmpty) a.sum
    else {
      val bb = b.map( _ % 10)
      val bMin = bb.min
      val bbb = b.map(t => (t + 9)/10 * 10).sum - ((bMin + 9)/10 * 10) + bMin
      a.sum + bbb
    }

    println(res)
  }
}

Measured memory_bytes: 25552
#include <cstdio>

int h,w,Map[1005][1005];
char map[1005][1005];

int main(){
    scanf("%d %d",&h,&w);
    for(int i=0;i<h;i++)
            scanf("%s",map[i]);
    for(int i=0;i<h;i++,puts(""))
        for(int j=0;j<w;j++){
            int p=0;
            if(map[i][j]=='#'){
                printf("#");
                continue;
            }

            if(map[i+1][j]=='#') p++;
            if(i>0&&map[i-1][j]=='#') p++;
            if(map[i][j+1]=='#') p++;
            if(j>0&&map[i][j-1]=='#') p++;
            if(map[i+1][j+1]=='#') p++;
            if(i>0&&j>0&&map[i-1][j-1]=='#') p++;
            if(j>0&&map[i+1][j-1]=='#') p++;
            if(i>0&&map[i-1][j+1]=='#') p++;
            printf("%d",p);
        }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <stdlib.h>
#include <functional>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <bitset>
#include <set>
#include <queue>
#include <map>
using namespace std;
int main(){
	string s;
	cin>>s;
	int len=s.size();
	for(int i=0;i<4;i++){
		cout<<s[i];
	}
	cout<<" ";
	for(int i=4;i<len;i++){
		cout<<s[i];
	}
	cout<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
long double r, x, y, p[100], PI = 3.14159265358979l; int n;
struct Point { long double px, py; };
long double crs(const Point& a, const Point& b) { return a.px * b.py - a.py * b.px; }
long double area(vector<Point> v) {
	long double ret = 0.0L;
	for (int i = 0; i < v.size(); i++) ret += crs(v[i], v[(i + 1) % v.size()]);
	return ret / 2;
}
int main() {
	cin >> r >> x >> y >> n; long double s = 450.0l;
	for (int i = 0; i < n; i++) { cin >> p[i]; p[i] *= 3.6l; }
	for (int i = 0; i < n; i++) {
		if (i)cout << ' ';
		long double W1 = r*r*(p[i] / 360.0l)*PI;
		long double W3 = -p[i];
		Point p1 = { 0,0 };
		Point p2 = { r*cos(s*PI / 180.0l),r*sin(s*PI / 180.0l) };
		Point p3 = { x,y }; s += W3;
		Point p4 = { r*cos(s*PI / 180.0l),r*sin(s*PI / 180.0l) };
		long double W2 = area(vector<Point>{p1, p2, p3, p4});
		cout << (int)(100.0l*(W1 + W2) / W1);
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 3504
N,M,Q = gets.split.map(&:to_i)
ABCD = []
Q.times{|i| ABCD[i] = gets.split.map(&:to_i)}

def rec(n,arr)
  if(arr.size == N)
    return ABCD.inject(0){|s,(a,b,c,d)| s + (arr[b-1] - arr[a-1] == c ? d : 0)}
  end

  return (n..M).map{|i|
    rec(i,arr+[i])
  }.max
end

puts rec(1,[])

Measured memory_bytes: 14336
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const int INF = 1001001001001001LL;
const int MOD = 1000000007;

bool f(string s){
    int n = (int)s.size();
    if(s[0] != 'A') return false;

    bool flag = false;
    for(int i = 2; i < n - 1; i++){
        if(s[i] == 'C'){
            flag = true;
            break;
        }
    }

    int cnt = 0;
    for(int i = 0; i < n; i++){
        if('A' <= s[i] && s[i] <= 'Z') cnt++;
    }

    return flag && (cnt == 2);
}

signed main(){
    
    string s; cin >> s;
    int n = (int)s.size();

    if(f(s)) cout << "AC" << endl;
    else cout << "WA" << endl;
    return 0;
}



Measured memory_bytes: 256
N=int(input())
S=input()
count=0
if N%2==0:   
    M=int(float(N/2))
    for i in range(M):
       if S[i]==S[M+i]:
           count=count
       else:
           count=count+1
else:
    count=count+1
if count>0:
    print('No')
else:
    print('Yes')

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

class UnionFind{
    vector<int>p,r;
public:
    UnionFind(int n){
        p.resize(n,-1);
        r.resize(n,1);
    }
    int find(int x){
        if(p[x] == -1)return x;
        else return p[x] = find(p[x]);
    }
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y)return;
        if(r[x] > r[y])swap(x,y);
        if(r[x] == r[y])r[y]++;
        p[x] = y;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
};

int main(){
  int n,m;
  cin>>n>>m;
  UnionFind uf(n);
  rep(i,m){
    int a,b; cin>>a>>b;
    a--; b--;
    uf.unite(a,b);
  }
  set<int>se;
  rep(i,n)se.insert(uf.find(i));
  cout<<se.size()-1<<endl;
}

Measured memory_bytes: 7804
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld  = long double;
using pll = pair<ll, ll> ;
using pld = pair<ld, ld>;
const int INF=1e9+7;
const ll LINF=1LL<<60;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld EPS = 1e-9; //微調整用（EPSより小さいと0と判定など）
 
#define gcd __gcd //llは受け取ってくれない
int lcm(int a, int b){return a / gcd(a, b) * b;}
#define ALL(a) a.begin(),a.end() //sort(ALL(vec));
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define PB push_back
#define SZ(x) ((int)(x).size) //size()がunsignedなのでエラー避けに

//最大値、最小値を更新する。aよりbのが大きい（小さい）か等しければaを更新してtrueを返す。そうでなければ何もせずfalseを返す chmax(nowmax,x);
template<typename T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<typename T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}
// ----- template end ---- //
 
// ------- library ------- //



// ----- library end ----- //



int main() {

  int N;
  cin >> N;

  if (N<=2){
    cout << 1 << endl;
    return 0;
  }

  
  vector<ll> DP(N+1, 1); //DP[0]を入れる必要があるので0-indexed

  //color(0-indexed)が直前に登場した時の位置
  //(色番号(.at())は0-indexedで、格納する位置は1-indexed)
  vector<int> prev(200000, -1);

  int nowcolor;
  REP(i, 1, N+1){
    // iは1-indexed !!
    cin >> nowcolor;
    nowcolor -= 1;
    if (prev.at(nowcolor)==-1){
      //未登場なら前のDPを引き継ぐだけ
      DP.at(i) = DP.at(i-1);
    }
    else if (prev.at(nowcolor)==i-1){
      //直前に出たばかりなら、やはり前のDPを引き継ぐだけ
      DP.at(i) = DP.at(i-1);
    }
    else{
      //1つ以上前に出ていた場合、その時のDPも引き継ぐ
      DP.at(i) = (DP.at(i-1) + DP.at(prev.at(nowcolor))) % MOD;
    }
    prev.at(nowcolor) = i;
  }

  cout << DP.at(N) << endl;


// -- main() end -- //
}


Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define debug 0
int main(){
	/*
	J	先頭を最後尾に
	C	最後尾を先頭に
	E	前半と後半を入れ替える(文字列が奇数なら真ん中は残す)
	A	文字列をひっくり返す
	P	プラス
	M	マイナス
	*/
	int n;
	for(cin>>n;n>0;n--){
		string order,str;
		cin>>order>>str;
		if(debug)cout<<"$"<<str<<endl;
		for(int i=order.size()-1;i>=0;i--){
			if(order[i]=='J'){
				string tmp="";
				tmp+=str[str.size()-1];
				for(int j=0;j<str.size()-1;j++)tmp+=str[j];
				str=tmp;
			}
			if(order[i]=='C'){
				string tmp="";
				for(int j=1;j<str.size();j++)tmp+=str[j];
				tmp+=str[0];
				str=tmp;
			}
			if(order[i]=='E'){
				string tmp="";
				if(str.size()%2){//奇数文字列
					for(int j=str.size()/2+1;j<str.size();j++)tmp+=str[j];
					tmp+=str[str.size()/2];
					for(int j=0;j<str.size()/2;j++)tmp+=str[j];
				}
				else{
					for(int j=str.size()/2;j<str.size();j++)tmp+=str[j];
					for(int j=0;j<str.size()/2;j++)tmp+=str[j];
				}
				str=tmp;
			}
			if(order[i]=='A'){
				reverse(str.begin(), str.end());
			}
			if(order[i]=='P'){
				for(int j=0;j<str.size();j++){
					if('0'<str[j]&&str[j]<='9')str[j]--;
					else if(str[j]=='0')str[j]='9';
				}
			}
			if(order[i]=='M'){
				for(int j=0;j<str.size();j++){
					if('0'<=str[j]&&str[j]<'9')str[j]++;
					else if(str[j]=='9')str[j]='0';
				}
			}
			if(debug)cout<<"#"<<str<<endl;
		}
		cout<<str<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 1212
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<set>
#include<cctype>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const long long INF = 1LL << 60;

int main(void){
	ios::sync_with_stdio(false); cin.tie(0);
	
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if((abs(b-a)<=d&&abs(c-b)<=d)||(abs(c-a)<=d))cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	
	
	return 0;
}

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

int main(){
    int n,max=0,next=0;;
    cin>>n;
    vector<int>a(10000000);
    
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(max<=a[i]){
        	next=max;
        	max=a[i];
        }
        else {if(next<=a[i]){
        	next=a[i];
        }
        	
        }
    }
    for(int i=0;i<n;i++){
        if(max==a[i]){
            cout<<next<<endl;
        }
        else{
            cout<<max<<endl;
        }
    }

   return 0;
}

Measured memory_bytes: 40704
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
#define BIG 2000000007
 
#define MOD 1000000007
typedef unsigned long long ull;
typedef   signed long long sll;
 
typedef struct {
	int a;
	int b;
} hw;
 
#define N_MAX 100000
#define M_MAX 100000
 
ull n, m, k;
ull h, w;
// ull a[N_MAX];
sll a[N_MAX];
// ull b[N_MAX];
// ull dp[N_MAX][M_MAX + 1];
// char s[N_MAX + 1];
// char t[N_MAX + 1];
// hw arr[N_MAX];
 
void swap_adj(ull *a, ull *b){
	ull tmp = *b;
	*b = *a;
	*a = tmp;
	return;
}

ull divide(ull a, ull b){
	ull x = MOD - 2;
	ull ans = 1;
	while (x) {
		if (x & 1) ans = (ans * b) % MOD;
		b = (b * b) % MOD;
		x /= 2;
	}
	return (a * ans) % MOD;
}
 
int digits(ull x){
	int i = 1;
	while (x >= 10) {
		x /= 10;
		i++;
	}
	return i;
}
 
int min(ull x, ull y){
	return (x < y) ? x : y;
}
 
ull gcd(ull x, ull y){
	if (x < y) {
		return gcd(y, x);
	} else if (y == 0) {
		return x;
	} else {
		return gcd(y, x % y);
	}
}
 
ull bitpow(ull a, ull x){
	ull result = 1;
	while (x) {
		if (x & 1) {
			result *= a;
			result %= MOD;
		}
		x /= 2;
		a = (a * a) % MOD;
	}
	return result;
}

int comp(const void *left, const void *right){
	if ((*(int*)left) < (*(int*)right)) {
		return -1;
	} else if ((*(int*)left) > (*(int*)right)) {
		return +1;
	} else {
		return 0;
	}
}

// int nextroute(int arr[]){
// 	int i = n - 1;
// 	int j, x;
// 	while (arr[i - 1] > arr[i]) i--;

// 	x = n;
// 	for (j = i; j < n; j++) {
// 		if (arr[j] < arr[i - 1]) continue;
// 		if (x == n || arr[x] > arr[j]) x = j;
// 	}
// 	arr[i - 1] ^= arr[x];
// 	arr[x] ^= arr[i - 1];
// 	arr[i - 1] ^= arr[x];

// 	qsort(&arr[i], n - i, sizeof(int), comp);
// 	return 0;
// }

ull solve(){
	int i, j;
	sll maxx = 0;
	sll maybemaxx = 0;

	sll imos[M_MAX + 3] = {0};

	for (i = 0; i < n; i++) {
		imos[a[i]]++;
		imos[a[i] + 3]--;
	}
	for (i = 0; i < M_MAX + 2; i++) {
		maybemaxx += imos[i];
		if (maybemaxx > maxx) maxx = maybemaxx;
	}

	printf("%lld\n", maxx);

	return 0;
}
 
int main(void){
	int i, j;
	int x = 0;
 
	scanf("%llu", &n);
	for (i = 0; i < n; i++) {
		scanf("%lld", &a[i]); // signed
	}

	solve();
 
	return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define test ll t; t=1; while(t--)
typedef long long int ll;
int main() {
    FIO;
    test{
        ll n,i;
        cin>>n;
        ll a[n];
        for(i=0;i<n;i++){
            cin>>a[i];
        }
        ll dp[n+1];
        memset(dp,0,sizeof(dp));
        dp[1]=0;
        dp[2]=abs(a[1]-a[0]);
        for(i=3;i<=n;i++){
           dp[i]=min(dp[i-1]+abs(a[i-1]-a[i-2]),dp[i-2]+abs(a[i-1]-a[i-3])); 
        }
        cout<<dp[n]<<"\n";
    }
	return 0;
}


Measured memory_bytes: 1792
import math
a,b,h,m=map(int,input().split())

short = (h *(360/12)) + m *(1/2)
long  = m * (360/60)
rad = abs(long - short)
cosa = math.cos(math.radians(rad))
ans = a**2 + b**2 + (-2)*a*b*cosa
print(math.sqrt(ans))

Measured memory_bytes: 9412
S=input()
N = len(S)
S_o=[]
S_e=[]
for i in range(N):
    if i%2==0:
        S_o.append(S[i])
    else:
        S_e.append(S[i])
if 'L' in S_o or 'R' in S_e:
    print('No')
else:
    print('Yes')


Measured memory_bytes: 38384
/* This Code Is Nude */
#include <bits/stdc++.h>
     
#define pb push_back
#define ll long long
#define int long long
 
using namespace std;
     
const ll inf = 1e12 + 10;
const int maxn = 2e5 + 10;
const int MOD = 998244353;
 
int a[maxn];
 
int32_t main(){
	int n;
	cin >> n;
	int ans = (n/500) * 1000;
	n -= (n/500)*500;
	ans += n/5 * 5;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256