akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector <int> construct(vector <int> d) {
  vector<int> res;
  int n=d.size();
  int m=0;
  int t[100]={};
  queue<int> q[100];
  for(int i=0;i<n;i++){
    t[d[i]]++;
    q[d[i]].push(i);
    m=max(m,d[i]);
  }
  //cout<<m<<endl;
  bool f=1;
  for(int i=0;i<(m+1)/2;i++) f&=t[m-i]>=2;
  //cout<<f<<endl;
  if(m%2) f&=t[m/2+1]==2;
  else f&=t[m/2]==1;
  //cout<<f<<endl;
  for(int i=0;i<n;i++){
    if(m%2) f&=d[i]>=m/2+1;
    else f&=d[i]>=m/2;
  }
  //cout<<f<<endl;
  if(!f) return res;
  //puts("a");
    
  bool used[100]={};

  int b[100][2]={};

  if(m%2){
    for(int i=0;i<=m/2;i++){
      b[m-i][0]=q[m-i].front();q[m-i].pop();
      b[m-i][1]=q[m-i].front();q[m-i].pop();
      used[b[m-i][0]]=1;
      used[b[m-i][1]]=1;
      if(i){
	res.push_back(b[m-i+1][0]);
	res.push_back(b[m-1][0]);
	res.push_back(b[m-i+1][1]);
	res.push_back(b[m-1][1]);
      }
      if(i==m/2){
	res.push_back(b[m-i][0]);
	res.push_back(b[m-i][1]);
      }
    }
    for(int i=0;i<n;i++){
      if(used[i]) continue;
      res.push_back(i);
      res.push_back(b[d[i]-1][0]);
    }
  }else{
    for(int i=0;i<m/2;i++){
      b[m-i][0]=q[m-i].front();q[m-i].pop();
      b[m-i][1]=q[m-i].front();q[m-i].pop();
      used[b[m-i][0]]=1;
      used[b[m-i][1]]=1;
      if(i){
	res.push_back(b[m-i+1][0]);
	res.push_back(b[m-1][0]);
	res.push_back(b[m-i+1][1]);
	res.push_back(b[m-1][1]);
      }
    }
    b[m/2][0]=q[m/2].front();q[m/2].pop();
    used[b[m/2][0]]=1;
    res.push_back(b[m/2+1][0]);
    res.push_back(b[m/2][0]);
    res.push_back(b[m/2+1][1]);
    res.push_back(b[m/2][0]);
      
    for(int i=0;i<n;i++){
      if(used[i]) continue;
      res.push_back(i);
      res.push_back(b[d[i]-1][0]);
    }
  }
  return res;
}
int main(){
  int n;
  cin>>n;
  vector<int> d(n);
  for(int i=0;i<n;i++) cin>>d[i];
  vector<int> ans=construct(d);
  cout<<(ans.size()?"Possible":"Impossible")<<endl;
  return 0;
}


Measured memory_bytes: 256
/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Coder:LCJ
Prob:Boxes :AtCoder - 2303
Type:math
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <list>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <sstream>
#define MEM(a,b) memset(a,b,sizeof(a)) 
#define sint(x) scanf("%d",&(x))
#define sint2(x,y) scanf("%d%d",&(x),&(y))
#define rep(x,y,z) for(int (x)=(y);(x)<(z);++(x))
using namespace std;
typedef long long ll;
const int maxn=10000000+10;
const int mod=1000000007;
bool flag;
ll n,sum,s;
ll a[100005];
int main()
{
	flag=true;
	scanf("%lld",&n);
	for(ll i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	if(sum%(((n+1)*n)/2))
	{
		flag=false;
		printf("NO\n");
	}
	else
	{
		s=sum/(((n+1)*n)/2);
		for(ll i=0;i<n;i++)
		{
			ll j=(i+1)>=n?0:i+1;
			if( (s-(a[j]-a[i]))<0 || (s-(a[j]-a[i]))%n )
			{
				flag=false;
				printf("NO\n");
				break;
			}
		}
	}
	if(flag)
	printf("YES\n");
    return 0;
} 

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

int main(){

  string str;
  cin>>str;

  for(int i=0;i<str.length();i++){
    if(str[i]=='1'){
      cout<<'9';
    }else if(str[i]=='9'){
      cout<<'1';
    }
  }

  cout<<endl;
  

  return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>

using std::vector;
using std::printf;
using std::cout;
using std::endl;
using std::string;
using std::cin;
using std::pair;

#define i64t long long int
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

template<typename T>
void dump(vector<T> vec) {
    for (auto x : vec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

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

const i64t MOD = 1000000007;

int main() {
    int N, Q;
    string S;
    cin >> N >> Q;
    cin >> S;

    vector< pair<int,int> > lrs;
    int t1, t2;
    for (int i = 0; i < Q; ++i) {
        cin >> t1 >> t2;
        lrs.push_back( pair<int,int>(t1, t2) );
    }

    vector<int> num_ac(N+1, 0);
    int cnt = 0;
    for (int i = 1; i < N; ++i) {
        if ((S[i-1] == 'A') && (S[i] == 'C')) {
            cnt++;
        }
        num_ac[i] = cnt;
    }
    num_ac[N] = cnt;

    // dump<int>(num_ac);

    for (int i = 0; i < Q; ++i) {
        printf("%d\n", num_ac[lrs[i].second-1] - num_ac[lrs[i].first-1]);
    }
    
}

Measured memory_bytes: 2292
using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static void Main()
    {
        var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var N = vals[0];
        var max = vals[1];
        var Q = vals[2];
        var quads = new long[Q][];
        for (int i = 0; i < Q; i++)
        {
            quads[i] = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        }

        var A = new int[N + 1];
        A[0] = 1;

        long GetBest(int index)
        {
            if (index > N)
            {
                long score = 0;
                foreach (var q in quads)
                {
                    if (A[q[1]] - A[q[0]] == q[2])
                    {
                        score += q[3];
                    }
                }
                return score;
            }

            var min = A[index - 1];
            long best = 0;
            for (int i = min; i <= max; i++)
            {
                A[index] = i;
                best = Math.Max(best, GetBest(index + 1));
            }
            return best;
        }

        var bestScore = GetBest(1);
        Console.WriteLine(bestScore);
    }
}

Measured memory_bytes: 28332
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,x;cin>>n>>x;
  vector<int> a(n);
  int i=0;
  for(i=0;i<n;i++)cin>>a[i];
  sort(a.begin(),a.end());
  int c=0;
  for(i=0;i<n;i++){
    x-=a[i];
    if(x<0)break;
    c++;
  }
  if(i!=n&&x!=0){
    x+=a[i];
    for(int j=i;j<n;j++){
      if(a[j]==x)c++;
    }
  }
  if(i==n&&x!=0)c--;
  cout<<c;
}

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; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

/*
テストケース全てに目を通す
テストケースが2個以下だったらなんかある
N最小のコーナーケースがないか調べる
制約をしっかりと確認する（1からNまでの順列、全て異なる値などの制約も含め）
操作の逆順を考える
 */

int main() {
    //ll N; cin >> N;
    //ll N,M; cin >> N >> M;
    //string S; cin >> S;
    //ll H,W; cin >> H >> W;
    int n;
    cin >> n;
  	int x=(n+1)/2;
  	double ans=(double)x/(double)n;
	cout << ans;
    


}

/*



 */



Measured memory_bytes: 256
//写経
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
using ll = long long;
using itn = int;
const int MAX_N = 110000;
using namespace std;
int memo[MAX_N];
int rec(int n){
    //終了条件
    if(n==0) return 0;
    //すでに探索済みならmemoを返す
    if(memo[n] != -1) return memo[n];
    int res = n;
    //6^iを試す
    for(int pow6=1; pow6 <= n; pow6*=6){
        res = min(res, rec(n-pow6)+1);
    }
    //9^iを試す
    for(int pow9=1; pow9 <= n; pow9*=9){
        res = min(res, rec(n-pow9)+1);
    }
    return memo[n] = res;
}
using namespace std;
int main(){
    int N;
    cin >> N;
    //貪欲じゃ溶けないからメモ化再帰
    for(int i=0; i<MAX_N; i++){
        memo[i] = -1;
    }

    cout << rec(N) << endl;

}

Measured memory_bytes: 3840
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <fstream>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long ll;
#define REP(i, N) for (int i = 0; i < (int)N; i++)

vector<vector<int>> adjacentList;
vector<bool> visited;
stack<int> sorted;

void visit(int i) {
  if(visited[i]) return;
  visited[i] = true;
  for(int nn: adjacentList[i]) {
    visit(nn);
  }
  sorted.push(i);
}

int main () {
  int V, E;
  cin >> V >> E;

  adjacentList = vector<vector<int>>(V, vector<int>());
  visited = vector<bool>(V, false);

  REP(i,E) {
    int s, t;
    cin >> s >> t;
    adjacentList[s].push_back(t);
  }

  REP(i, V) visit(i);

  while(!sorted.empty()) {
    cout << sorted.top() << endl;
    sorted.pop();
  }

  return 0;
}

Measured memory_bytes: 1880
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)

int main()
{
    int N;
    cin >> N;
    vector<int> W(N + 1);
    for (int i = 1; i <= N; i++)
    {
        cin >> W[i];
    }
    int S1 = 0, S2 = 0;
    int ptr_left = 1, ptr_right = N;
    while (ptr_right >= ptr_left)
    {
        if (S1 < S2)
        {
            S1 += W[ptr_left];
            ptr_left++;
        }
        else
        {
            S2 += W[ptr_right];
            ptr_right--;
        }
    }
    cout << abs(S1 - S2) << endl;
}

Measured memory_bytes: 256
//ABC102B
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
#include <unordered_map>
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin >> a.at(i);
	}
	sort(a.begin(),a.end());
	int ans = a.at(n-1)-a.at(0);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
let scan4 f = stdin.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1], a.[2], a.[3]))

let rot vx vy = -vy,vx 
let nextp x0 y0 x1 y1 =
  let dx,dy = rot (x1-x0) (y1-y0)
  x1+dx, y1+dy

let x1,y1,x2,y2 = scan4 int
let x3,y3 = nextp x1 y1 x2 y2 
let x4,y4 = nextp x2 y2 x3 y3
printfn "%d %d %d %d" x3 y3 x4 y4


Measured memory_bytes: 11996
A, B, C, D = map(int, input().split())

def mul(head, tail, x):
    length = tail - head + 1
    ans = length // x
    if x - (head % x) <= length % x - 1:
        return ans+1
    return ans

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(a, b):
	return a * b // gcd (a, b)

print(B - A + 1 - (mul(A, B, C) + mul(A, B, D) - mul(A, B, lcm(C, D))))


Measured memory_bytes: 38256
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100001;
int n;
struct Graph
{
    struct Edge
    {
        int to,next;
    }edge[N<<1];   
    int head[N],cnt;
    void add_edge(int u,int v)
    {
        cnt++;
        edge[cnt].to=v;
        edge[cnt].next=head[u];
        head[u]=cnt;
        return;
    }
}g1,g2,g;
int a[N],b[N];
int a1[N],a2[N];
int st[N],top;
bool book[N];
int color[N];
void dfs1(int u)
{
    for(int i=g1.head[u];i;i=g1.edge[i].next)
    {
        int v=g1.edge[i].to;
        dfs1(v);
    }
    if(a1[u]) st[++top]=u;
    while(top>=2)
    {
        g.add_edge(st[top],st[top-1]);
        g.add_edge(st[top-1],st[top]);
        top-=2;
    }
    return;
}
void dfs2(int u)
{
    for(int i=g2.head[u];i;i=g2.edge[i].next)
    {
        int v=g2.edge[i].to;
        dfs2(v);
    }
    if(a2[u]) st[++top]=u;
    while(top>=2)
    {
        g.add_edge(st[top],st[top-1]);
        g.add_edge(st[top-1],st[top]);
        top-=2;
    }
    return;
}
void dfs(int u,int col)
{
    color[u]=col;
    book[u]=true;
    for(int i=g.head[u];i;i=g.edge[i].next)
    {
        int v=g.edge[i].to;
        if(book[v]) continue;
        dfs(v,-col);
    }
    return;
}
int main()
{
    scanf("%d",&n);
    int rt1,rt2;
    for(int i=1;i<=n;i++)
        a1[i]=a2[i]=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==-1) rt1=i;
        else
        {
            g1.add_edge(a[i],i);
            a1[a[i]]^=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
        if(b[i]==-1) rt2=i;
        else
        {
            g2.add_edge(b[i],i);
            a2[b[i]]^=1;
        }
    }
    for(int i=1;i<=n;i++)
        if(a1[i]!=a2[i])
        {
            printf("IMPOSSIBLE\n");
            return 0;
        }
    printf("POSSIBLE\n");
    top=0;
    dfs1(rt1);
    top=0;
    dfs2(rt2);
    for(int i=1;i<=n;i++)
        if(!book[i]) dfs(i,1);
    for(int i=1;i<=n;i++)
        if(!a1[i]) printf("0 ");
        else printf("%d ",color[i]);
    return 0;
}

Measured memory_bytes: 10624
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int[] count = new int[n+1];
		int[][] cities = new int[m][3];
		String[] res = new String[m];
		
		for (int i = 0; i < m; i++) {
			int P = sc.nextInt();
			int Y = sc.nextInt();
			
			cities[i] = new int[]{P, Y, i};
		}
		
		Arrays.sort(cities, (a, b) -> (a[1] - b[1]));
		
		for (int i = 0; i < m ; i++) {
			//System.out.println(Arrays.toString(cities[i]));
			count[cities[i][0]]++;
			String s = String.format("%06d%06d", cities[i][0], count[cities[i][0]]);
			res[cities[i][2]] = s;
		}
		
		for (String s: res) {
			System.out.println(s);
		}
	}
  
    static class FastReader {
	    BufferedReader br;
	    StringTokenizer st;
	
	    public FastReader() {
	      br = new BufferedReader(new InputStreamReader(System.in));
	    }
	  
	    String next() { 
	      while (st == null || !st.hasMoreElements()) {
	        try {
	          st = new StringTokenizer(br.readLine());
	        } catch (IOException  e) {
	          e.printStackTrace();
	        }
	      }
	      return st.nextToken();
	    }
	
	    int nextInt() {
	      return Integer.parseInt(next());
	    }
	
	    long nextLong() {
	      return Long.parseLong(next());
	    }
	
	    double nextDouble() { 
	      return Double.parseDouble(next());
	    }
	
	    String nextLine() {
	      String str = "";
	        try{
	            str = br.readLine();
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
	        return str;
	      }
	  }
}

Measured memory_bytes: 114092
#include <vector>
#include <iostream>
#include <map>
#include <string>

using namespace std;
int main(){
  long long int n; cin >> n;
  map<long long int, long long int> cnt;
  for(int i=0;i<n;i++){
    long long int a; cin >> a;
    cnt[a]++;
  }
  auto itr =cnt.begin();
  auto itr1=cnt.begin(); itr1++;
  auto itr2=cnt.begin(); itr2++; itr2++;

  string ans;
  if(cnt.size()==1) ans=(itr->first==0) ? "Yes":"No";
  else if(cnt.size()==2){
    if(itr->first==0) ans=(itr->second*2==itr1->second) ? "Yes":"No";
    // else if(itr1->first==0) ans=((itr->second)==itr1->second*2) ? "Yes":"No";
	else ans="No";
  }
  else if(cnt.size()==3){
    if(itr->second==itr1->second 
       && itr1->second==itr2->second){
      ans=((itr->first^itr1->first)==itr2->first) ? "Yes":"No";
    }
    else ans="No";
  }
  else ans="No";
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,-1,0,1},dy={1,0,-1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,d;cin >> n >> d;
	vector<vector<int>> x(n,vector<int>(d));
	rep(i,n) rep(j,d) cin >> x[i][j];
	vector<bool> a(100000,false);
	for(int i=1;i*i<=100000;++i){
		a.at(i*i)=true;
	}
	int ans=0;
	rep(i,n){
		for(int j=i+1;j<n;++j){
			int sum=0;
			rep(k,d){
				sum+=int(pow(x[i][k]-x[j][k],2));
			}
			if(a.at(sum)) ans++;
		}
	}
	cout << ans << endl;
}


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

int N;
vector<int> a;

int main() {
    cin >> N; a.resize(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    int index = max_element(a.begin(), a.end()) - a.begin();
    sort(a.begin(), a.end(), greater<int>());
    for (int i = 0; i < N; i++) {
        if (i == index) cout << a[1] << endl;
        else cout << a[0] <<endl;
    }
    return 0;
}

Measured memory_bytes: 2432
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] ss = Console.ReadLine().Split(' ');
            int r = int.Parse(ss[0]);
            int D = int.Parse(ss[1]);
            int x2k = int.Parse(ss[2]);
            int xi = x2k;
            for (int i = 0; i < 10; i++)
            {
                xi = r * xi - D;
                Console.WriteLine(xi);
            }
        }
    }
}


Measured memory_bytes: 11092
#include <iostream>
#include <cmath>
using namespace std;
//using ll=long long;

int main(){
    int N;
    cin >> N;
    int max_itr = int(log2(N)) + 1;
    int tmp = 1;
    for(int i = 2; i <= N; i++){
        for(int j = 2; j <= max_itr; ++j){
            if(pow(i,j) <= N){
                if(tmp < pow(i,j)){
                    tmp = pow(i,j);
                }
            } else break;
        }
    }
    cout << tmp << endl;
    
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <vector>
#include <cstdlib>
#include <queue>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define STEP(i, n, step) for(int i=0; i < n; i+=step)
#define RANGE(n) for(int _=0; _<n ; _++)
#define FOR(i, m, n) for(int i = m; i < n; i++)

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

const long long INF = 1LL << 60;
const int INT_INF = 1 << 29;

const int MAX = 100010;

void solve() {
  int N, counter=0;
  int D1[110], D2[110];
  cin >> N;
  REP(i,N){
    cin >> D1[i] >> D2[i];
  }
  REP(i,N){
    if(counter >=3) break;
    if(D1[i] == D2[i]){
      counter++;
    }else{
      counter = 0;
    }
  }

  if(counter >=3 ) cout << "Yes" << endl;
  else cout << "No" << endl;
  return;
}
 
int main() {
    solve();
    return 0;
}




Measured memory_bytes: 3632
/*--ILRS-- sr4saurabh  */
#include <bits/stdc++.h>
using namespace std; 
typedef long long int ll;
#define pb push_back 
#define popb pop_back
#define mp make_pair
#define ve vector
#define vii vector < int >
#define vll vector < ll > 
#define pii pair < int , int >
#define pll pair < ll , ll >
#define vpl vector < pll >
#define fi first
#define sz size 
#define len length 
#define se second 
//const ll mod=998244353;
const ll mod = 1000000000+7;
const ll N=10000000+6;
#define M_PI           3.14159265358979323846
vii adj[100001];
int visited[100001]={0};
int d[100001]={0};
void dfs(int node)
{
  //cout<<node<<endl;
  visited[node]=1;
  for(int v: adj[node])
  {
    if(!visited[v])
    {
       dfs(v);
       
    }
    d[node]=max(d[node],d[v]+1);
  }
    d[node]=max(1,d[node]);
}
void bfs(int node)
{
  queue<int> q;
  q.push(node);
  visited[node]=1;
  while(!q.empty())
  {
    int v=q.front();
    //cout<<v<<endl;
    q.pop();
    
    for(int g:adj[v])
      if(!visited[g])
      {
        visited[g]=1;
        q.push(g);
      }

  }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //#ifndef ONLINE_JUDGE
      // freopen ("INPUT.txt" , "r" , stdin);
       //freopen ("OUTPUT.txt", "w" , stdout);
    //#endif
       //for(int i=0;i<=100000;i++)
        //visited[i]=0;

    int n,m;
    cin>>n>>m;
    while(m--)
    {
      int u,v;
      cin>>u>>v;
      adj[u].pb(v);
      //adj[v].pb(u);
    }
    for(int j=1;j<=n;j++)
    {
      if(!visited[j])
      dfs(j);  
    }
    int ans=0;
    for(int j=1;j<=n;j++)
    {
      ans=max(ans,d[j]);
    }
    cout<<ans-1;
    














return 0;
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
template<typename T>
ostream& operator+(ostream& out, const vector<T> &vec){
    for(const auto &x : vec){
        out<<x<<" ";
    }
    out<<"\n";
    return out;
}
template<typename T>
ostream& operator*(ostream& out, const vector<T> &vec){
    for(const auto &x : vec){
        out+x;
    }
    return out;
}
template<typename T>
istream& operator>>(istream& in, vector<T> &vec){
    for(auto &x : vec){
        in>>x;
    }
    return in;
}
template<typename T>
struct segment_tree {
    int n;
    vector<T> segtree;
    function<T(const T&,const T&)> join;
    T base = T();
    segment_tree(int n, function<T(const T&,const T&)> join, T base = T()) : n(n), join(join), base(base){
        segtree.resize(n << 1, base);
    }
    void build() {
        for (int i = n - 1; i > 0; --i) {
            segtree[i] = join(segtree[(i << 1)], segtree[(i << 1) | 1]);
        }
    }
    segment_tree(vector<T> seq, function<T(const T&,const T&)> join, T base = T()) : n(seq.size()), join(join), base(base){
        segtree.resize(n << 1, base);
        for (int i = 0; i < n; i++) {
            segtree[n + i] = seq[i];
        }
        build();
    }
    T query(int pos){
        pos += n;
        ll ans = segtree[pos];
        pos >>= 1;
        while (pos) {
            ans = join(ans, segtree[pos]);
            pos >>= 1;
        }
        return ans;
    }
    void update(int l, int r, T val) {
        l += n;
        r += n + 1;
        while (l < r) {
            if (l & 1) {
                segtree[l] = join(val, segtree[l]);
                ++l;
            }
            if (r & 1) {
                --r;
                segtree[r] = join(segtree[r], val);
            }
            l >>= 1;
            r >>= 1;
        }
    }
    void debug(){
        for(int i=0;i<n;i++){
            cout<<query(i)<<" ";
        }
        cout<<"\n";
    }
};
void solve(){
    int n,q;
    cin>>n>>q;
    segment_tree<int> row(n, [&](const int &x, const int &y){
        return x>y ? y : x;
    }, n-1);
    segment_tree<int> col(n, [&](const int &x, const int &y){
        return x>y ? y : x;
    }, n-1);
    ll ans = ll(n-2)*(n-2);
    for(int i=0;i<q;i++){
        int type;
        cin>>type;
        if(type==1){
            int x;
            cin>>x;
            --x;
            int y = col.query(x);
            ans-=y-1;
            row.update(0, y, x);
        }
        else{
            int y;
            cin>>y;
            --y;
            int x = row.query(y);
            ans-=x-1;
            col.update(0, x, y);
        }
        //row.debug();col.debug();cout<<"\n";
    }
    cout<<ans<<"\n";   
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Measured memory_bytes: 6344
#include <iostream>
#include<vector>
#include<cmath>
using namespace std;
long long solve(int n,vector<long long> a,long long r){
	long long ans=0;
	long long sum=0;
	for(int i=0;i<n;i++){
		sum+=a[i];
		if(r*sum<=0){
			if(sum>r){
				ans+=sum-r;
			}else{
				ans+=r-sum;
			}
			sum=r;
		}
		r*=-1;
	}
	return ans;
}

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


//	if(a[0]==0){
//		ans++;
//		int flag=-1;
//		for(int i=1;i<n;i++){
//			if(a[i]){
//				if(a[i]>0){
//					break;
//				}else{
//					flag*=-1;
//					break;
//				}
//			}
//			flag*=-1;
//		}
//		if(flag){
//			a[0]=1;
//		}else{
//			a[0]=-1;
//		}
//	}
//	long long r=-1;
//	if(a[0]<0)r=1;
//	long long sum=a[0];
//	for(int i=1;i<n;i++){
//		sum+=a[i];
//		if(r*sum<=0){
//			if(sum>r){
//				ans+=sum-r;
//			}else{
//				ans+=r-sum;
//			}
//			sum=r;
//		}
//		r*=-1;
//	}
//	cout<<ans<<endl;

	return 0;
}

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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(20);

  int n, m;
  cin >> n >> m;
  vector<long> v(m);
  rep(i, m) {
    long p, y;
    cin >> p >> y;
    v[i] = (p << 32) | y;
  }

  vector<long> sorted_v(v);
  sort(sorted_v.begin(), sorted_v.end());

  vector<vector<long>::iterator> head(n+1, sorted_v.end());
  rep(i, m) {
    const long p = v[i] >> 32;
    if (head[p] == sorted_v.end()) {
      head[p] = lower_bound(sorted_v.begin(), sorted_v.end(), p << 32);
    }
    auto it2 = lower_bound(head[p], sorted_v.end(), v[i]);
    auto d = distance(head[p], it2);
    printf("%06ld%06ld\n", p, d + 1); 
  }
  return 0;
}


Measured memory_bytes: 3840
// A.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	bool ans = (a[0] == a[1] && a[1] != a[2]) || (a[0] != a[1] && a[1] == a[2]);
	cout << (ans ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main()
{
    while (1){
        int n;

        scanf(" %d", &n);
        if (n == 0){
            break;
        }

        int s[n];

        for (int i = 0; i < n; i++){
            scanf(" %d", &s[i]);
        }

        int sum = 0;
        double h;
       
        for (int i = 0; i < n; i++){
            sum += s[i];
        }
        
        h = (double)sum / n;

        double a = 0;

        for (int i = 0; i < n; i++){
            a += pow(s[i] - h, 2);
        }

        printf("%lf\n", sqrt(a/n));
    }

    return 0;
}


Measured memory_bytes: 2128
#include "bits/stdc++.h"

using namespace std;
 
const int inf = 1e8;
#define ll long long
#define fr(i,a,n) for (int i=a;i<n;i++)
#define rfr(i,n,a) for (int i=n;i>=a;i--)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll> 
#define endl "\n"
typedef vector<int> VI;
typedef vector<ll> VL;


long double n,m,k;

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);	
	cin >> n >> m;
	k = (long double)1 / (long double)((long double)4 * m);
	long double tot = 0;
	vector <long double> v(n);
	for (auto &x:v) {
		cin >> x;
		tot += x;
	}
	long double cnt = 0;
	for (auto x:v) {
		if ((x / tot) >= k) {
			cnt += (long double)1.0;
		}
	}
	if (cnt >= m)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
w, d, n = gets.chomp.split.map(&:to_i)
measured = []
n.times{measured << gets.chomp.split.map(&:to_i)}
no = false
for i in (0..(n - 2))
    for j in ((i + 1)..(n - 1))
        if (measured[i][0] - measured[j][0]).abs + (measured[i][1] - measured[j][1]).abs < (measured[i][2] - measured[j][2]).abs
            no = true
            break
        end
    end
    break if no
end
if no
    puts "No"
else
    top = nil
    map = Array.new(d){[]}
    altitude = Hash.new{|h, k| h[k] = []}
    measured.each{|x, y, z|
        map[y - 1][x - 1] = z
        altitude[z] << [x, y]
        top = z if top.nil? || top < z
    }
    while !altitude.empty?
        altitude[top].each{|x, y|
            [[0, 1], [0, -1], [1, 0], [-1, 0]].each{|addx, addy|
                if (x + addx).between?(1, w) && (y + addy).between?(1, d) && map[y+addy-1][x+addx-1].nil?
                    map[y+addy-1][x+addx-1] = top - 1
                    altitude[top - 1] << [x+addx, y+addy]
                end
            } 
        }
        altitude.delete(top)
        top -= 1
    end
    total = 0
    map.each{|mp| total += mp.inject(:+)}
    puts total
end



Measured memory_bytes: 8916
#include <stdio.h>
int main(){
    long N, A, B;
    scanf("%ld%ld%ld", &N, &A, &B);
    long w = N / (A + B);
    long a = N % (A + B);
    long ans = w * A;
    if(a < A){
        ans += a;
    }else{
        ans += A;
    }
    printf("%ld\n", ans);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back
#define P pair<int,int>
#define vp vector<P>
#define PP pair<P,int>
#define vpp vector<PP>
#define fi first
#define se second
#define INF INT_MAX
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define all(x) (x).begin(),(x).end()
int main(){
    int n;
    cin>>n;
    int ans=INF;
    REP(i,n){
        int a,b;
        cin>>a>>b;
        ans=min(ans,a+b);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> v(N);
  for(int i = 0;i < N; i++){
    cin >> v[i];}
  long long ans = 0;
  int Max = 0;
  for(int i=0; i<N; i++){
	Max = max(Max,v[i]);
    int Bi = Max;
    ans += Bi - v[i];
  }
  cout << ans << endl; 
}



Measured memory_bytes: 3992
#include <bits/stdc++.h>
#define bear ryan
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define ends ' '
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll inf = 1e9;

int main(void) {
    fastio;
    int x, y, z;    cin >> x >> y >> z;
    cout << z << ends << x << ends << y;
    return 0;
}

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

class Radix {
private:
  const char* s;
  int a[128];
public:
  Radix(const char* s = "0123456789ABCDEF") : s(s) {
    int i;
    for(i = 0; s[i]; ++i)
      a[(int)s[i]] = i;
  }
  std::string to(long long p, int q) {
    int i;
    if(!p)
      return "0";
    char t[64] = { };
    for(i = 62; p; --i) {
      t[i] = s[p % q];
      p /= q;
    }
    return std::string(t + i + 1);
  }
  std::string to(const std::string& t, int p, int q) {
    return to(to(t, p), q);
  }
  long long to(const std::string& t, int p) {
    int i;
    long long sm = a[(int)t[0]];
    for(i = 1; i < (int)t.length(); ++i)
      sm = sm * p + a[(int)t[i]];
    return sm;
  }
};

int main() {
    // ifstream in("data1.txt");
    // cin.rdbuf(in.rdbuf());
    int N, K;
    cin >> N >> K;
    Radix r;
    // 10 進数を n 進文字列に
    std::cout << r.to(N, K).length() << std::endl; // => "255"
    return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/10;
    public static final int inf = Integer.MAX_VALUE/10;

    public static boolean[][] use1, use2;
    public static long[][] dp1, dp2;
    public static int[] a;
    public static int n;
    static void solve(InputReader in, PrintWriter out){
        n = in.ni();
        a = in.ni(n);
        dp1 = new long[n][n];
        dp2 = new long[n][n];
        use1 = new boolean[n][n];
        use2 = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(use1[i], false);
            Arrays.fill(use2[i], false);
        }
        for (int i = 0; i < n; i++) {
            dp1[i][i] = a[i];
            dp2[i][i] = -a[i];
            use1[i][i] = true;
            use2[i][i] = true;
        }
        out.println(dfs(0, n-1, true));
    }
    public static long dfs(int i, int j, boolean first){
        if(first){
            if(!use1[i][j]){
                long val1 = a[i]+dfs(i+1,j, false);
                long val2 = a[j]+dfs(i,j-1, false);
                dp1[i][j] = Math.max(val1, val2);
                use1[i][j] = true;
            }
            return dp1[i][j];
        }else{
            if(!use2[i][j]){
                long val1 = dfs(i+1,j, true)-a[i];
                long val2 = dfs(i,j-1, true)-a[j];
                dp2[i][j] = Math.min(val1, val2);
                use2[i][j] = true;
            }
            return dp2[i][j];
        }
    }

    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public Double nd(){
            return Double.parseDouble(ns());
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 248028
package main

import (
  "fmt"
)

func main() {

  var a, b int

  fmt.Scan(&a, &b)

  if a > 12 {
    fmt.Println(b)
  } else if a >= 6  {
    fmt.Println(b / 2)
  } else {
    fmt.Println(0)
  }
  
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class MainClass
{
	public const long Giri = 1000000007;

	public static void Main(string[] args)
	{
		var n = Console.ReadLine().ToInt();
		var a = Input().ToInt();
		
		long cnt = 99999999999;
		for(int i = 0; i < n; i++)
		{
			int j = 0;
			for(j = 0; j < 99; j++)
			{
				if(((a[i] >> j) & 1) == 1)
				{
					break;
				}
			}
			cnt = Math.Min(cnt, j);
		}
		
		Console.WriteLine(cnt);
	}
	

	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(' '); }
	public static int Clamp(int val, int max, int min = 0) { return Math.Min(max, Math.Max(min, val)); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}



Measured memory_bytes: 11092
#include<stdio.h>
#include<string.h>
int main(void){
    char s[4], t[4];
    int count=0;
    scanf("%s", s);
    scanf("%s", t);
    for(int i=0; i<3; i++){
        if(s[i]==t[i]){
            count++;
        } 
    }
    printf("%d", count);
    return 0;
}

Measured memory_bytes: 128
///
// File:  b.cpp
// Author: ymiyamoto
//
// Created on Tue Oct  3 20:10:49 2017
//

#include <cstdint>
#include <iostream>
#include <string>

using namespace std;
static uint32_t counts[26];

int32_t main()
{
  string str;
  cin >> str;
  for (uint32_t i = 0; i < str.size(); i++) {
    counts[str[i] - 'a']++;
  }

  for (uint32_t i = 0; i < 26; i++) {
    if (counts[i] % 2 != 0) {
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
	
	int i,j,flag=1,n,a[100],b,count=0;
	
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	
	while(flag){
		flag=0;
		for(i=n-1;i>=0;i--){
			b=a[i];
			if(a[i]<a[i-1]){
				a[i]=a[i-1];
				a[i-1]=b;
				flag=1;
				count++;
			}
		}
	}
	for(i=0;i<n;i++){
		printf("%d",a[i]);
		if(i<n-1){
			printf(" ");
		}
	}
	puts("");
	printf("%d\n",count);
	return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

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

  	REP(i, 3){
      if(S[i] == S[i+1]){
        cout << "Bad" << endl;
        return 0;
      }
    }
    cout << "Good" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <math.h>
#include <cmath>
#include <set>   

using namespace std;


int main() {

	int n, a, x;
	cin >> n >> a;

	x = n % 500;

	if (a >= x) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;

	}



		
}

Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)






int main() {
	string X,Y;
	cin >>X>>Y ;
	string h = "NO";
	if (X.at(0)==Y.at(2)&& X.at(1) == Y.at(1)&& X.at(2) == Y.at(0)) {
			h = "YES";
	}
	
	cout <<h<< endl;
}


Measured memory_bytes: 256
unittest
{
	assert( [ "3 3", "1 3 4", "1 3 6" ].parse.expand.solve == 60 );
	assert( [ "6 5", "-790013317 -192321079 95834122 418379342 586260100 802780784", "-253230108 193944314 363756450 712662868 735867677" ].parse.expand.solve == 835067060 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	input.popFront;
	auto xs = input.front.split.to!( long[] );
	input.popFront;
	auto ys = input.front.split.to!( long[] );
	return tuple( xs, ys );
}

auto solve( long[] xs, long[] ys )
{
	// すべての長方形の横辺の長さの合計を計算
	auto xt = 0L;
	for( auto i = 1L; i < xs.length.signed; i++ )
	{
		xt = xt.addMod( xs[ i ].subMod( xs[ i - 1 ] ).mulMod( i ).mulMod( xs.length.signed - i ) );
	}
	
	// すべての長方形の縦辺の長さの合計を計算
	auto yt = 0L;
	for( auto i = 1L; i < ys.length.signed; i++ )
	{
		yt = yt.addMod( ys[ i ].subMod( ys[ i - 1 ] ).mulMod( i ).mulMod( ys.length.signed - i ) );
	}
	
	// 横辺 * 縦辺
	return xt.mulMod( yt );
}

// 足し算
auto addMod( long MOD = 10L ^^ 9 + 7 )( long x, long y )
{
	return ( x + y ) % MOD;
}

// 引き算
auto subMod( long MOD = 10L ^^ 9 + 7 )( long x, long y )
{
	return ( x + MOD - y ) % MOD;
}

// 掛け算
auto mulMod( long MOD = 10L ^^ 9 + 7 )( long x, long y )
{
	return x * y % MOD;
}


Measured memory_bytes: 11916
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
//#define fill(x,y) memset(x,y,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()

using namespace std;
typedef pair<int, int>P;

int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int dxx[8] = { 0,0,1,1,1,-1,-1,-1 };
int dyy[8] = { 1,-1,0,1,-1,0,1,-1 };


const int MAX = 500010;
const int MOD = (ll)1e9+7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;

bool cmp(const P& p1, const P&p2) {
	return p1.second < p2.second;
}



ll ans[200020];
vector<P>v;
vector<ll>vec[200020];//色とその位置
ll color[200020];
vector<ll>C;
ll dp[200020];
signed main() {
	ll N; cin >> N;
	REP(i, N) {
		cin >> color[i];
	}
	vec[color[0]].pb(1);
	C.pb(color[0]);
	int cnt = 1;
	FOR(i,1, N) {
		if (color[i] != color[i - 1]) {
			cnt++;
			C.pb(color[i]);
			vec[color[i]].pb(cnt);
			//pe(color[i]); print(cnt);
		}
	}
	m0(dp);
	dp[0] = 1;
	FOR(i, 1, cnt + 1) {
		(dp[i] += dp[i - 1])%=MOD;
		auto itr = lb(vec[C[i-1]],i);
		if (itr - vec[C[i - 1]].begin() > 0) {
			itr--;
			(dp[i] += dp[*itr])%=MOD;
		}
	}
	print(dp[cnt]);
}

Measured memory_bytes: 16240
#include <bits/stdc++.h>
#define REP(i,n) for(int64_t i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REV(c) reverse((c).begin(),(c).end())
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define COUTDOUBLE(d,i) cout << setprecision((i)) << (d) << endl;
#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}
#define MREP(i,m) for(auto i=(m).begin(); i != (m).end(); ++i) // auto key = i->first;auto value = i->second;

using namespace std;
typedef int64_t I;
typedef pair<I,I> P;
typedef vector<I> V;

I MOD = pow(10,9)+7;
I MAX = LONG_MAX;
I MIN = LONG_MIN;

// 最大公約数
I gcd(I a, I b) {
  return b != 0 ? gcd(b, a % b) : a;
}

// 最小公倍数
I lcm(I a, I b) {
  return a * b / gcd(a, b);
}

int ctoi(char c){
  return c - '0';
}

template<class Abel> struct UnionFind {
    vector<I> par;
    vector<I> rank;
    vector<Abel> diff_weight;

    UnionFind(I n = 1, Abel SUM_UNITY = 0) {
        init(n, SUM_UNITY);
    }

    void init(I n = 1, Abel SUM_UNITY = 0) {
        par.resize(n); rank.resize(n); diff_weight.resize(n);
        for (I i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
    }

    I root(I x) {
        if (par[x] == x) {
            return x;
        }
        else {
            I r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = r;
        }
    }

    Abel weight(I x) {
        root(x);
        return diff_weight[x];
    }

    bool issame(I x, I y) {
        return root(x) == root(y);
    }

    bool merge(I x, I y, Abel w) {
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y), w = -w;
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }

    Abel diff(I x, I y) {
        return weight(y) - weight(x);
    }
};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  I n,m;
  cin >> n >> m;
  UnionFind<int> uf(n+1);
  REP(i,m){
    I l,r,d;
    cin >> l >> r >> d;
    if (uf.issame(l,r)){
      if (uf.diff(l,r) == d){
      }else{
        No;
        return 0;
      }
    }else{
      uf.merge(l,r,d);
    }
  }
  Yes;
  return 0;
}



Measured memory_bytes: 2176
n,x=map(int,input().split())
patty=[1]
barger=[1]
ans=0
for i in range(n):
  patty.append(2*patty[-1]+1)
  barger.append(2*barger[-1]+3)
i=n
while x>0:
  for _ in range(n):
    if x>=barger[i]:
      x-=barger[i]
      ans+=patty[i]
      if x>0:
        ans+=1
        x-=1
      break
    i-=1
    x-=1
print(ans)

Measured memory_bytes: 9064
#include <bits/stdc++.h>
using namespace std;
char a[200001];
int b[200002],w[200002];
int main()
{
	int n,i,ans=INT_MAX;
	scanf("%d",&n);
	getchar();
	for(i=1;i<=n;i++)
	{
		b[i]=b[i-1];
		scanf("%c",&a[i]);
		if(a[i]=='#')
			b[i]++;
	}
	for(i=n;i>=1;i--)
	{
		w[i]=w[i+1];
		if(a[i]=='.')
			w[i]++;
	}
	for(i=1;i<=n;i++)
	{
		//printf("%d,%d\n",b[i],w[i]);
		if(a[i]=='#')
		{
			ans=min(ans,b[i-1]+w[i+1]);
			//printf("%d\n",b[i-1]+w[i+1]);
		}
	}
	printf("%d",min(min(ans,b[n]),w[1]));
	return 0;
}

Measured memory_bytes: 2048
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
#define int long long


signed main(void){
  char a[9][9];
  int h,w;
  cin >> h >> w;

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

  int i = 0;
  int j = 0;
  while(true){
    a[i][j] = '.';
    if(j<w-1 && a[i][j+1] == '#'){
      j++;
      continue;
    }else if(i < h-1 && a[i+1][j] == '#'){
      i++;
      continue;
    }else{
      break;
    }
  }

  bool ret = true;
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(a[i][j]=='#'){
        ret = false;
      }
    }
  }

  if(ret)cout << "Possible\r\n";
  else cout << "Impossible\r\n";
}


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

int main()
{
ll t ;
cin >> t ;
rep(i,t){
  ll n ;
  cin >> n ;
  ll a , b , c , d ;
  cin >> a >> b >> c >> d ;
  map<ll,ll> m;
  m[0]=INF;
  queue<ll> q;
  q.push(n);
  m[n]=1;
  while(!q.empty()){
    ll p=q.front();
    q.pop();
    if(m[p/2]==0||m[p/2]>m[p]+a+(p%2)*d ){
      m[p/2]=m[p]+a+(p%2)*d;
      q.push(p/2);
    }
    if(m[p/3]==0||m[p/3]>m[p]+b+(p%3)*d ){
      m[p/3]=m[p]+b+(p%3)*d;
      q.push(p/3);
    }
    if(m[p/5]==0||m[p/5]>m[p]+c+(p%5)*d ){
      m[p/5]=m[p]+c+(p%5)*d;
      q.push(p/5);
    }
    if(m[(p+1)/2]==0||m[(p+1)/2]>m[p]+a+(2-p%2)*d ){
      m[(p+1)/2]=m[p]+a+(2-p%2)*d;
      q.push((p+1)/2);
    }
    if(m[(p+2)/3]==0||m[(p+2)/3]>m[p]+b+(3-p%3)*d ){
      m[(p+2)/3]=m[p]+b+(3-p%3)*d;
      q.push((p+2)/3);
    }
    if(m[(p+4)/5]==0||m[(p+4)/5]>m[p]+c+(5-p%5)*d ){
      m[(p+4)/5]=m[p]+c+(5-p%5)*d;
      q.push((p+4)/5);
    }
    if(p/2==0)m[0]=min(m[0],m[p]+(p%2)*d);
    if(p/3==0)m[0]=min(m[0],m[p]+(p%3)*d);
    if(p/5==0)m[0]=min(m[0],m[p]+(p%5)*d);
    if(p<INF/d)m[0]=min(m[0],m[p]+p*d);
  }
  cout << m[0]-1 << endl;
}

return 0;
}

Measured memory_bytes: 4344