akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MOD = 1e9+7;

//0 -> S
//1 -> W
int main()
{
    int N;cin >> N;
    string str;cin >> str;
    for(int i = 0;i < 2;i++){
        for(int j = 0;j < 2;j++){
            vector<bool> v(N);
            v[0] = i;
            v[1] = j;
            for(int k = 2;k < N;k++){
                if(!v[k - 1] && str[k - 1] == 'o'){
                    v[k] = v[k - 2];
                }
                if(!v[k - 1] && str[k - 1] == 'x'){
                    v[k] = !v[k - 2];
                }
                if(v[k - 1] && str[k - 1] == 'o'){
                    v[k] = !v[k - 2];
                }
                if(v[k - 1] && str[k - 1] == 'x'){
                    v[k] = v[k - 2];
                }
            }
            bool result = true;
            for(int k = 0;k < N;k++){
                if(!v[k]){
                    if(k == 0){
                        if(str[k] == 'o'){
                            if(v.back() != v[1]){
                                result = false;
                            }
                        }else{
                            if(v.back() == v[1]){
                                result = false;
                            }
                        }
                    }else{
                        if(str[k] == 'o'){
                            if(v[k - 1] != v[(k + 1)%N]){
                                result = false;
                            }
                        }else{
                            if(v[k - 1] == v[(k + 1) %N]){
                                result = false;
                            }
                        }
                    }
                }else{
                    if(k == 0){
                        if(str[k] == 'o'){
                            if(v.back() == v[1]){
                                result = false;
                            }
                        }else{
                            if(v.back() != v[1]){
                                result = false;
                            }
                        }
                    }else{
                        if(str[k] == 'o'){
                            if(v[k - 1] == v[(k + 1)%N]){
                                result = false;
                            }
                        }else{
                            if(v[k - 1] != v[(k + 1) %N]){
                                result = false;
                            }
                        }
                    }
                }
            }
            if(result){
                for(auto a : v)cout<<(a ? 'W' : 'S');
                cout<<endl;
                return 0;
            }
        }
    }
    cout<<-1<<endl;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

int asort(const void *A,const void *B){
    return *(long long*)A>*(long long*)B?1:0;
}

int dsort(const void *A,const void *B){
    return *(long long*)A<*(long long*)B?1:0;
}

long long gcd(long long A,long long B){
    return B?gcd(B,A%B):A;
}

int main(void){
    int n;
    scanf("%d",&n);
    long long a[n];
    for (int i=0; i<n; i++){
        scanf("%lld",&a[i]);
    }
    qsort (a,n,sizeof(long long),dsort);
    long long ans=gcd(a[0],a[1]);
    for (int i=0; i<n; i++){
        ans=gcd(ans,a[i]);
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 1788
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	for i in range(K, N):
		if A[i] > A[i - K]:
			print("Yes")
		else:
			print("No")

if __name__ == '__main__':
	main()

Measured memory_bytes: 29592
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <stack>
#include <functional>
#include <queue>
#include <cmath>
#include <set>
#include <bitset>

#define rep(i,j,k) for(int i=j;i<k;i++)
#define Sort(x) sort((x).begin(),(x).end())
#define fi first
#define se second
#define vi vector<int>
#define INF 1000000000
#define MOD 1000000009
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef std::pair<int,int> pii;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

using namespace std;


int main(){
    vector<int> v(1001,0);
    int a,b;
    cin>>a>>b;
    v[a]++; v[b]--;
    int n;cin>>n;
    rep(i,0,n){
        int x,y;
        cin>>x>>y;
        v[x]++; v[y]--;
    }
    
    rep(i,1,1001){
        v[i]+=v[i-1];
        if(v[i]>1 || v[0]>1){
            cout<<1<<endl;
            return 0;
        }
    }
    
    cout<<0<<endl;
    
    return 0;
}




Measured memory_bytes: 3076
#include<iostream>
#include <algorithm>
#include <string>
#include<math.h>
using namespace std;

int main(){
    long int N;
    long int digit;
    int num_digit = 0;
    int num = 0;
    string ans = "";
    cin >> N;
    
    while(1){
        N = N-1;    
        digit = N%26;
        N = N/26;
        char letter = 'a' + digit;
        ans = letter + ans; 
        if (N==0) break;
    }
    cout << ans<< endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

int main(){
    ll n,p; cin >> n >> p;
    if(n == 1){
        cout << p << endl;
        return 0;
    }
    ll ans = 1;

    for(ll i=2;i*i<=p;i++){
        ll cnt = 0;
        while(p%i==0){
            p /= i;
            cnt++;
        }
        while(cnt>=n){
            cnt -= n;
            ans *= i;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
//include
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath> 
#include <iomanip>
#include <math.h>
#include <utility>
#include <functional>
#include <cstdlib>
//using
using namespace std;
using vl = vector <long long>;
using vs = vector <string>;
using vc = vector <char>;
using ll= long long;
using vvl = vector<vector<ll> >;
//vector<vector<char> > hyou(N, vector<char>(N));
using vd = vector <double>;
//define
//#define int long long
#define rep(i,n) for(int i=0; i<n; i++)
#define print(n) cout<<n<<endl;
#define sortp(d) sort(d.begin(),d.end()) //1234
#define sortm(d) sort(d.rbegin(),d.rend()) //4321
//素数判定　O(√A) 
bool is_prime(int x){
 if(x<=1) return false;
 for(int i=2;i*i<=x;i++)
 if(x%i==0) return false;
 return true;
 }
/*順列生成
do {
  // 順列に対する処理
} while (next_permutation(配列変数.begin(), 配列変数.end()));*/

//絶対値　abs()
//文字→数字　'0' アルファベット→数字　'a'　'A'が65番,'a'が97番だわ
//型キャスト　char('a'+1)

//グローバル変数宣言
 //ll p=0,q=0,r=0;
ll a=0,b=0,c=0;
int main()
{
  ll n;
  cin>>n;
  vl p(n);
  a=n;
  rep(i,n)
  {
    cin>>p[i];
    a=min(p[i],a);
    if(a==p[i])c++;
  }
  print(c);
}

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

using namespace std;

int main(void)
{
    int n1, n2, n3;

    cin >> n1 >> n2 >> n3;

    double a = (double)n1;
    double b = (double)n2;
    double x = (double)n3;

    if (0.5 * a * a * b <= x)
    {
        double rad = atan2(2.0 * b - (2.0 * x / a / a), a);
        cout << std::setprecision(12) << rad / M_PI * 180.0 << endl;
    }
    else
    {
        double rad = atan2(b, 2.0 * x / a / b);
        cout << std::setprecision(12) << rad / M_PI * 180.0 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define INF 1000000007
using namespace std;

int main()
{
	int N,W;
	cin>>N>>W;
	
	int val[N],wgt[N],tot=0;
	for(int i=0;i<N;i++)
	{
		cin>>wgt[i]>>val[i];
		tot+=val[i];
	}
	int ans=0;
	vector<vector<int>>dp(N+1,vector<int>(tot+1,INF));
	
	for(int i=1;i<=N;i++)
	{
	    dp[i-1][0]=0;
		for(int j=tot;j>=0;j--)
		{
		    if(j-val[i-1]>=0)
		        dp[i][j] = min(dp[i-1][j],dp[i-1][j-val[i-1]]+wgt[i-1]);
    // 			dp[i][j+val[i-1]] = min(dp[i-1][j+val[i-1]], dp[i-1][j]+wgt[i-1]);
			else
    			dp[i][j]=dp[i-1][j];
				
			//if(dp[i][j]<=W)
			//ans=j;
			//cout<<dp[i][j]<<" ";
		}
// 		cout<<endl;
	}
	
// 	for(int i=0;i<=N;i++)
// 	{
// 	    for(int j=0;j<=tot;j++)
// 	    cout<<(dp[i][j]==INF?"-":to_string(dp[i][j]))<<" ";
// 	    cout<<endl;
// 	}
	
	for(int i=0;i<=tot;i++)
	{
		if(dp[N][i]<=W)
		ans=max(ans,i);
	}
	
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 43008
N = int(input())
A = [int(input()) for _ in range(N)]

if A[0] != 0:
    print(-1)
    exit()

ans = 0
tmp = 0
for num in reversed(A):
    if tmp > 0:
        if num == tmp-1:
            tmp = num
        elif num >= tmp:
            ans += num
            tmp = num
        elif num < tmp-1:
            print(-1)
            exit()

    else:
        ans += num
        tmp = num
        

print(ans)

Measured memory_bytes: 11048
#include <bits/stdc++.h>
using namespace std;
int N;
long M;

struct Info {
    long long A;
    long long B;
};

bool cmp(const Info &left, const Info &right) {
    return left.A < right.A;
}

// 安いのから順に買い占めていく
int main() {
    cin >> N >> M;
    vector<Info> info(N);
    for(int i = 0; i < N; ++i) {
        cin >> info.at(i).A >> info.at(i).B;
    }

    sort(info.begin(), info.end(), cmp);

    long long total = 0;

    for(int i = 0; i < N; ++i) {
        if(M >= info.at(i).B) {
            total += info.at(i).A * info.at(i).B;
            M -= info.at(i).B;
        }else {
            total += M * info.at(i).A;
            break;
        }
    }

    cout << total << endl;
}

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

int main(){
    int n = 0;
    cin >> n;
    vector<int> h(n);
    rep(i,n) cin >> h[i];


    for(int i=1;i<n;i++){
        int diff = h[i] - h[i-1];
        if(diff>=1){
            h[i]-=1;
        }else if(diff==0){
            continue;
        }
        else{
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}

Measured memory_bytes: 640
N, K = map(int, input().split())

if K % 2 == 0:
    tmp1 = (N // K) ** 3
    if (N // K) * K + K / 2 <= N:
        tmp2 = ((N // K) + 1) ** 3
    else:
        tmp2 = (N // K) ** 3
    print(tmp1 + tmp2)

else:
    print((N // K) ** 3)


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

int main() {
  int n;
  cin >> n;
  int x = 0;  
  for (int i = 0; i < n; i++) {
    int l,r;
    cin >> l >> r;
    x += r - l + 1;
  }
  cout << x << endl;
    
}

Measured memory_bytes: 3588
N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))
diff = []
for i in range(N):
    diff.append(V[i]-C[i])
sum = 0
for i in range(N):
    if diff[i] > 0:
        sum += diff[i]
print(sum)


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;

int main(void) {
  int N;
  cin >> N;
  vi A(N);
  rep(i, N) cin >> A[i];

  double bunshi = 0.0;
  rep(i, N) bunshi += 1.0 / A[i];
  
  fin(1.0 / bunshi) ;
}

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

ll gcd(ll a, ll b){
    if(a < b) return gcd(b, a);
    ll r = a % b;
    while(r != 0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

int main(){
    ll N, X;
    cin >> N >> X;
    vector<ll> x(N+1);
    rep(i, 0, N) cin >> x[i];
    x[N] = X;
    sort(x.begin(), x.end());
    vector<ll> d(N);
    rep(i, 0, N) d[i] = x[i+1] - x[i];
    ll ans = d[0];
    rep(i, 1, N) ans = gcd(ans, d[i]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
n = int(input())
h = [int(i) for i in input().split()]

ans = 0
j = 10 ** 9
k = 0
for i in h:
    if j >= i:
        k += 1
    else:
        k = 1
    ans = max(ans, k)
    j = i
print(ans-1)

Measured memory_bytes: 63984
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(ll i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll ans=0;
vector<ll> badget(202000,0);
void Main(){
    ll n;cin>>n;
    ll d;cin>>d;
    ll a;cin>>a;
    vector<pair<ll,ll>> x(n);
    For(i,0,n)cin>>x[i].first>>x[i].second;
    sort(ALL(x));
    x.push_back(make_pair(ll(10000000000),ll(0)));
    For(i,0,n){
        if(i>0) badget[i]+=badget[i-1];
        if(x[i].second-badget[i]<=0) continue;
        else{
            ll hp=x[i].second-badget[i];
            ll bakugeki=(hp+a-1)/a;
            //cout<<"x = "<<x[i].first+d<<" num = "<<bakugeki<<endl;
            ans+=bakugeki;
            auto itr=upper_bound(ALL(x),make_pair(x[i].first+2*d,ll(10000000000)));
            ll right=itr-x.begin();
            ll left=i;
            badget[left]+=bakugeki*a;
            badget[right]-=bakugeki*a;
        }
    }
    cout<<ans<<endl;
}
int main(){
    Main();
    return 0;
}

Measured memory_bytes: 9728
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    string s;
    cin>>s;
    int q;
    cin>>q;
    int n=s.length();
    bool mirror=false;
    deque<char>qe;
    rep(i,n){
        qe.push_back(s[i]);
    }
    rep(i,q){
        int t;
        cin>>t;
        if(t==1){
            mirror=!mirror;
        }
        else{
            int f; char c;
            cin>>f>>c;
            if(f==1){
                if(mirror==false){
                    qe.push_front(c);
                }
                else{
                    qe.push_back(c);
                }
            }
            else{
                if(mirror==false){
                    qe.push_back(c);
                }
                else{
                    qe.push_front(c);
                }
            }
        }
    }
    if(mirror==true)reverse(qe.begin(),qe.end());
    for(auto&p:qe){
        cout<<p;
    }
}

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

string s;

int main(){
  cin >> s;
  int n = s.size();
  if(n == 26 && s == "zyxwvutsrqponmlkjihgfedcba"){
    cout << -1 << endl;
  }else if(n == 26){
    string t = s;
    next_permutation(s.begin(), s.end());
    rep(i, n){
      if(s.at(i) != t.at(i)){
        s = s.substr(0, i + 1);
        break;
      }
    }
    cout << s << endl;
  }else{
    int memo[30];
    rep(i, 30) memo[i] = 0;
    rep(i, n){
      memo[s.at(i) - 'a']++;
    }
    int c;
    rep(i, 30){
      if(memo[i] == 0){
        c = 'a' + i;
        break;
      }
    }
    cout << s << (char)c << endl;
  }
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
#include <numeric>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
//#define MOD 998244353
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=100050;
//↑templete
signed main(){
	int N;
	cin>>N;
	string S;
	cin>>S;

	unordered_map<string, int> pam;
	string init=to_string(S[0]-'0');
	//cout<<"!"<<init<<endl;
	pam[init]++;
	for(int i=1;i<S.length();i++){
		vector<string> vec;
		for(auto p:pam){
			string str;
			int a;
			tie(str, a)=p;

			if(str.length()<3)
				vec.pb(str+to_string(S[i]-'0'));
		}
		pam[to_string(S[i]-'0')]++;
		for(string str:vec){
			//cout<<str<<endl;
			pam[str]++;
		}
	}
	int ans=0;
	for(auto p:pam){
		string str;
		int a;
		tie(str, a)=p;

		if(str.length()==3)
			ans++;
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define PI 3.14159265358979323
#define ll long long int
#define vi vector <int>
#define vl vector <ll>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define watch(x) cout << (#x) << " is " << (x) << "\n"

ll power(ll a, ll b,ll MOD){//a^b
    ll res=1;
    a=a%MOD;
    while(b>0){
        if(b&1){res=(res*a)%MOD;b--;}
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}

ll gcd(ll a, ll b) {return (b == 0) ? a : gcd(b, a % b);}

int ans(int x) {
	int c = 0;
	while (x > 0) {
		x = x % __builtin_popcount(x);
		c++;
	}
	return c;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output.txt", "w", stdout);
#endif
	int n;
	cin >> n;
	string s;
	cin >> s;
	int x = 0;
	for (int i = n - 1; i >= 0; i--) {
		if(s[i]=='1')
			x++;

	}
	int r1,r2,r3;
	r1=r2=r3=0;
	int y=max(x-1,1);
	for (int i = 0;i<n; i++) {
		if(s[i]=='0'){
			r1=(2*r1)%x;
			r2=(2*r2)%(x+1);
			r3=(2*r3)%y;
		}
		else{
			r1=(2*r1+1)%x;
			r2=(2*r2+1)%(x+1);
			r3=(2*r3+1)%y;
		}
	}
	for(int i=0;i<n;i++){
		if(s[i]=='0'){
			cout<<ans((r2+(power(2,n-i-1,x+1)))%(x+1))+1<<"\n";
		}
		else{
		    if(x==1)
		        cout<<0<<"\n";
		    else
			    cout<<ans((r3-(power(2,n-i-1,x-1))+(x-1))%(x-1))+1<<"\n";
		}
	}
}


Measured memory_bytes: 3776
# disjoint setかと思いきやDFS
# したらTLEになったので根本的にやり方が間違ってるということ
# よくよく考えたらdfsなのでそこにたどり着いたときが最短距離だわ ムダに探索してた


import sys

sys.setrecursionlimit(10000000)

n = int(input())
graph = [[] for _ in range(n)]

for _ in range(n - 1):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append([b, c])
    graph[b].append([a, c])

q, k = map(int, input().split())
k = k - 1
# kからスタートしてぜんぶたどる
ans_list = [0 for _ in range(n)]


def dfs(node, weight):
    for data in graph[node]:
        if not used[data[0]]:
            used[data[0]] = True
            dfs(data[0], weight + data[1])
    ans_list[node] = weight


used = [False for _ in range(n)]
used[k] = True
dfs(k, 0)

for _ in range(q):
    a, b = map(lambda x: int(x) - 1, input().split())
    print(ans_list[a] + ans_list[b])


Measured memory_bytes: 140644
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  //C
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> a(n);

  for (int i = 0; i < n; i++) {
    cin >> a[i].first >> a[i].second;
  }
  sort(a.begin(), a.end());
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    if (m == 0) break;
    if (m < a[i].second) {
      ans += 1LL * a[i].first * m;
      m = 0;
    }
    if (m >= a[i].second) {
      m -= a[i].second;
      ans += 1LL * a[i].first * a[i].second;
    } 
  }
  cout << ans << endl;
  return 0;	
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
// typedef long double ldouble;

using Graph = vector<vector<int>>;

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

// int gcd(int a, int b){
//   int ma = max(a,b);
//   int mi = min(a,b);
//   if(mi == 0) return ma;

//   return gcd(mi, ma%mi);
// }

// llong POW(llong a, llong b){
//   if(b == 0) return 1;
//   else{
//     if(b%2 == 0) return POW(a * a % MOD, b / 2) % MOD;
//     else return a * POW(a * a % MOD, b / 2) % MOD;
//   }
// }

int main(){
  vector<int> num(3);
  for(int i=0; i<3; ++i) cin >> num[i];
  sort(num.rbegin(), num.rend());
  cout << num[0] * 10 + num[1] + num[2] << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[]args){
      Scanner sc = new Scanner(System.in);

      int a = sc.nextInt();
      int b = sc.nextInt();

      int max = 0;

      max = Math.max(a+b,a-b);

      max = Math.max(max,a*b);

      System.out.println(max);



  }
}

Measured memory_bytes: 23124
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.HashMap;

public class Main {

    public static void main(String[] args){
        new Main().solve();
    }

    void solve() {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[]p=new int[n];
        for(int i=0;i<n;i++)p[i]=sc.nextInt()-1;
        int count=0;
        for(int i=0;i<n-1;i++) {
        	if(p[i]==i && p[i+1]!=i) {
        		int temp=p[i];
        		p[i]=p[i+1];
        		p[i+1]=temp;
        		
        		count++;
        	}
        }
        if(p[n-1]==n-1)count++;
        System.out.println(count);      
    }
}

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

int main(){
  int a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;
  
  int sol, sug;
  double conc = 0.0;
  for (int i = 0; i <= f; i += 100 * a){
    for (int j = 0; j <= f - i; j += 100 * b){
      int rem = min(f - i - j, (i + j) / 100 * e);
      for (int k = 0; k <= rem; k += c){
        int l = d * ((rem - k) / d);
        if (i + j + k + k == 0) continue;
        double cur_conc = (double)(100 * (k + l)) / (i + j + k + l);
        if (conc <= cur_conc){
          conc = cur_conc;
          sug = k + l;
          sol = i + j + k + l;
        }
      }
    }
  }
  cout << sol << " " << sug << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <sstream>
#include <fstream>

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

using namespace std;
typedef long long unsigned int ll;

int main() {
  int N;
  cin >> N;
  int aCnt = 0, bCnt = 0, cCnt = 0;
  for (int i = 0; i < N; ++i) {
    int a;
    cin >> a;
    if (a % 4 == 0) {
      aCnt++;
    } else if (a % 2 == 0) {
      cCnt++;
    } else {
      bCnt++;
    }
  }
  if (cCnt == 0) {
    cout << (bCnt - aCnt <= 1 ? "Yes": "No") << endl;
  } else {
    cout << (bCnt - aCnt <= 0 ? "Yes": "No") << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string A, x, C;
    cin >> A >> x >> C;

    string ans = "ans";
    ans.at(0) = A.at(0);
    ans.at(1) = x.at(0);
    ans.at(2) = C.at(0);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MAX 200010
#define inf 1<<30
#define linf 1e16
#define eps (1e-8)
#define mod 1000000007
#define pi acos(-1)
#define phi (1.0+sqrt(5))/2.0
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef vector<int> vi;
typedef vector<pii> vpi;
const int dx[8]={1,0,-1,0,1,1,-1,-1};
const int dy[8]={0,1,0,-1,1,-1,1,-1};

int v,e,r;
vector<pii> g[MAX];

void dijkstra(){
  int d[MAX];
  priority_queue<pii,vector<pii>,greater<pii> > pq;
  fill(d,d+MAX,inf);
  d[r]=0;
  pq.push(mp(0,r));

  while(pq.size()){
    pii u=pq.top();
    pq.pop();
    if(d[u.s]<u.f)continue;

    FOR(i,0,g[u.s].size()){
      int next=g[u.s][i].f;
      int cost=d[u.s]+g[u.s][i].s;
      if(cost<d[next]){
        d[next]=cost;
        pq.push(mp(cost,next));
      }
    }
  }
  FOR(i,0,v){
    if(d[i]==inf)cout<<"INF"<<endl;
    else cout<<d[i]<<endl;
  }
  return;
}

int main()
{
  scanf("%d%d%d",&v,&e,&r);
  FOR(i,0,e){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    g[a].pb(mp(b,c));
  }
  dijkstra();
  return 0;
}

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

int a[100010],n;

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n);
    int count=unique(a,a+n)-a;
    printf("%d\n",count-(count%2==0?1:0));
    return 0;
}

Measured memory_bytes: 640
N,A,B = map(int, input().split())
S = input()
ok = 0
ok_b = 0

for i in range(N):
  if S[i] == 'a':
    if ok < A+B:
      print('Yes')
      ok += 1
    else:
      print('No')
  elif S[i] == 'b':
    if ok < A+B and ok_b < B:
      print('Yes')
      ok += 1
      ok_b += 1
    else:
      print('No')
  else:
    print('No')

Measured memory_bytes: 4016
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
long long dp[309][309][309], n, m, l[309], r[309], p[309], t[4][309], mod = 1000000007;
vector<pair<long long, long long>>x[309];

void senni(int p1, int p2, int p3, long long a) {
	dp[p1][p2][p3] += a; dp[p1][p2][p3] %= mod;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> l[i] >> r[i] >> p[i];
		x[r[i]].push_back(make_pair(l[i], p[i]));
	}
	dp[0][0][0] = 1;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				for (int l = 0; l < x[i].size(); l++) {
					int P = x[i][l].first;
					if (x[i][l].second == 1) {
						if (!(j < P && P <= i))dp[i][j][k] = 0;
					}
					if (x[i][l].second == 2) {
						if (!(k < P && P <= j))dp[i][j][k] = 0;
					}
					if (x[i][l].second == 3) {
						if (!(-1 < P && P <= k))dp[i][j][k] = 0;
					}
				}
				if (dp[i][j][k] == 0)continue;
				if (i != n) {
					senni(i + 1, j, k, dp[i][j][k]);
					senni(i + 1, i, k, dp[i][j][k]);
					senni(i + 1, i, j, dp[i][j][k]);
				}
			}
		}
	}
	long long P = 0;
	for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++)P += dp[n][i][j]; }
	cout << P % mod << endl;
	return 0;
}

Measured memory_bytes: 224768
package main

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

const (
	initialBufSize = 10000
	maxBufSize     = 1000000
)

var (
	sc *bufio.Scanner = func() *bufio.Scanner {
		sc := bufio.NewScanner(os.Stdin)
		buf := make([]byte, initialBufSize)
		sc.Buffer(buf, maxBufSize)
		sc.Split(bufio.ScanWords)
		return sc
	}()
	mod int = 1e9 + 7
)

type Graph struct {
	n     int
	edges [][]int
}

func NewGraph(n int) *Graph {
	g := &Graph{
		n:     n,
		edges: make([][]int, n),
	}
	return g
}

func (g *Graph) AddEdge(u, v int) {
	g.edges[v] = append(g.edges[v], u)
	g.edges[u] = append(g.edges[u], v)
}

func main() {
	N := getInt()
	M := getInt()
	K := getInt()

	friendGraph := NewGraph(N)

	for i := 0; i < M; i++ {
		a := getInt() - 1
		b := getInt() - 1
		friendGraph.AddEdge(a, b)
	}

	blockGraph := NewGraph(N)

	for i := 0; i < K; i++ {
		c := getInt() - 1
		d := getInt() - 1
		blockGraph.AddEdge(c, d)
	}

	visitedEdges := make([]map[int]struct{}, N)
	results := make([]int, N)

	for i := 0; i < N; i++ {
		visited := visitedEdges[i]
		if visited == nil {
			visited = map[int]struct{}{}
			dfs(i, friendGraph.edges, visited)
			for k := range visited {
				visitedEdges[k] = visited
			}
		}

		results[i] = len(visited) - len(friendGraph.edges[i]) - 1

		for _, node := range blockGraph.edges[i] {
			_, flag := visited[node]
			if flag {
				results[i]--
			}
		}
	}

	printIntArray(results)
}

func dfs(c int, edges [][]int, visited map[int]struct{}) {
	visited[c] = struct{}{}

	for _, v := range edges[c] {
		_, flag := visited[v]
		if flag {
			continue
		}
		dfs(v, edges, visited)
	}
}

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

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

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func pow(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func powMod(n, p int) int {
	if p == 0 {
		return 1
	} else if p%2 == 0 {
		t := powMod(n, p/2)
		return calcMod(t * t)
	} else {
		return n * powMod(n, p-1)
	}
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func printIntArray(array []int) {
	strArray := fmt.Sprint(array)
	fmt.Println(strArray[1 : len(strArray)-1])
}

func calcMod(x int) int {
	return x % mod
}


Measured memory_bytes: 32000
n,m=map(int,input().split())
X=list(map(int,input().split()))

if m==1 :
    print(0)
    exit()

X.sort()
D=[]
for i in range(1,m):
    D.append(X[i]-X[i-1])

D.sort(reverse=True)
d=0
if i>1:
    for i in range(min(n-1,m-1)):
        d += D[i]    

ans = sum(D)-d
print(ans)


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

int main() {
	ios_base::sync_with_stdio( false );

	int n, q;
	cin >> n >> q;

	vector<stack<int>> s( n );
	while( q-- > 0 ) {
		int cmd, t, x;
		cin >> cmd >> t;

		if( cmd == 0 ) {
			cin >> x;
			s[t].push( x );
		}
		else if( cmd == 1 && !s[t].empty() ) {
			cout << s[t].top() << '\n';
		}
		else if( cmd == 2 && !s[t].empty() ) {
			s[t].pop();
		}
	}

	return 0;
}



Measured memory_bytes: 4220
#include <stdio.h>
#include <string.h>
 
int main() {
 
  char str[1050] = {0};
  char ch[1050] = {0};
  char mei[30] = {0};
  char pl[1050]={0};
  int i,j,k,l,m,n,o,p;
 
  
  scanf("%s",str);
  scanf("%d",&n);
    
  for(i=0; i<7 ;i++) {
    ch[i] = str[i];
  }
 
  j=0;
  o=0;
  k=l=0;
 
  for ( i = 0; i < n; i++ ){
    scanf("%s", mei);
    scanf("%d %d", &k, &l);
    // printf("mei= %s",mei);
   
     
    if(mei[2] =='p') {
      
      scanf("%s", pl);
 
      for(m=0;m<l-k+1;m++) {
 
    //  printf("str[%d]%c = pl[%d]%c\n",m+k,str[m+k] ,m,pl[m]);
    str[m+k] = pl[m];   
      }
    }
 
    else if(mei[2] == 'v') {
       
      for(m=0; m<strlen(str);m++) {
    ch[m] = str[m];
      }
       
      for(m=0;m<l-k+1;m++) {
    //  printf("str[%d]%c = ch[%d]%c\n",k+m,str[k+m],l-m,ch[l-m]);
    str[k+m] = ch[l-m];
      }
     
    }
 
    else if(mei[0] = 'p') {   
       
      for(m=k; m<=l;m++) {
    printf("%c" ,str[m]);
      }
      printf("\n");
    }
     
  }
 
    
  return 0;
 
}


Measured memory_bytes: 2628
n,m = map(int,input().split())
X = set()
Y = set()
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        X.add(b)
    if b == n:
        Y.add(a) 
print("IMPOSSIBLE" if not X&Y else "POSSIBLE")

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

int main() {
    long long N;
    cin >> N;
    vector <long long> t(N+1, 0);
    vector <long long> x(N+1, 0);
    vector <long long> y(N+1, 0);
    for (long long i=1; i<=N; i++) {
        cin >> t.at(i) >> x.at(i) >> y.at(i);
    }
    bool ok=true;
    for (long long i=1; i<=N; i++) {
        long long dt, dx, dy;
        dt = t.at(i) - t.at(i-1);
        dx=abs(x.at(i)-x.at(i-1));
        dy=abs(y.at(i)-y.at(i-1));
        if(dt < dx+dy) ok=false;
        if((dt-dx-dy)%2 == 1) ok=false;
    }
    if (ok) cout << "Yes";
    else cout << "No";
}


Measured memory_bytes: 5444
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int,int> P;

int main(){
    int x,y,z;
    cin >> x >> y >> z;
    swap(x,y);
    swap(x,z);
    cout << x << " " << y << " " << z << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int N; cin >> N;
	int even = 0;
	int odd = 0;
	rep (i, N){
		int a; cin >> a;
		if (a % 2 == 0){
			++even;
		}else{
			++odd;
		} // end if
	} // end rep

	bool ok = true;
	even += odd / 2;
	odd -= (odd / 2) * 2;

	if (odd % 2 != 0){
		ok = false;
	} // end if

	cout << (ok ? "YES" : "NO") << endl;

	return 0;
}

Measured memory_bytes: 256
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define sz(s) ((int) ((s).size()))
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

#ifdef _WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif

typedef long long ll;
typedef long double ld;

const int inf = (int) 1e9 + 100;
const ld eps = 1e-11;
const ld pi = acos(-1.0L);

mt19937 mrand(random_device{} ());
int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int mod = (int) 1e9 + 7;

int mult(int a, int b) {
  return (ll) a * b % mod;
}

const int maxn = 1e5 + 100;
int n;
int t[maxn], a[maxn];

bool read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", t + i);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
  }
  return true;
}

void solve() {
  vector<int> know(n);
  vector<int> mx(n, 1e9 + 100);
  for (int i = 0; i < n; i++) {
    if (!i || t[i] > t[i - 1]) {
      know[i] = t[i];
    }
    mx[i] = min(mx[i], t[i]);
  }
  for (int i = n - 1; i >= 0; i--) {
    if (i == n - 1 || a[i] > a[i + 1]) {
      if (know[i] && know[i] != a[i]) {
        printf("0\n");
        return;
      }
      know[i] = a[i];
    }
    if (know[i] && know[i] > a[i]) {
      printf("0\n");
      return;
    }
    mx[i] = min(mx[i], a[i]);
  }
  int res = 1;
  for (int i = 0; i < n; i++) {
    if (!know[i]) {
      res = mult(res, mx[i]);
    }
  }
  printf("%d\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen("text.in", "r", stdin));
  assert(freopen("text.out", "w", stdout));
#endif

  while (true) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time: %.18f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}

Measured memory_bytes: 1920
#include<stdio.h>
#include<queue>
#include<map>
using namespace std;
int e[100000];
int d[100000];
queue<int> que;
int main(){
	int n,i;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&e[i]);
		d[i]=-1;
	}
	d[0]=0;
	que.push(0);
	while(!que.empty()){
		int p=que.front();que.pop();
		for(i=1;i<=6;i++){
			int q=p+i;
			if(q>=n)q=n-1;
			if(d[q]==-1){
				d[q]=d[p]+1;
				while(d[q+e[q]]==-1){
					d[q+e[q]]=d[q];
					q+=e[q];
				}
				if(e[q]==0)que.push(q);
			}
		}
	}
	printf("%d\n",d[n-1]);
	return 0;
}

Measured memory_bytes: 1836
import math

a, b, h, m = map(int, input().split())

ang = abs(h * 30 - m * 11/2)
angle = min(ang, 360-ang)

c = math.sqrt(a ** 2 + b ** 2 - 2 * a * b * math.cos(math.radians(angle)))

print(c)


Measured memory_bytes: 9508
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	int a[100005];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}	
	sort(a,a+n);
	int min=1000000000;
	for(int i=0;i<n-k+1;i++){
		if(a[i+k-1]-a[i]<min){
			min=a[i+k-1]-a[i];
		}
	}
	cout<<min<<endl;
} 

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
using namespace std;

int main(){
    int n ;
    cin >> n ;
    int64_t ans = 0;
    vector<vector<int> > t(10,vector<int>(10)) ;
    for (size_t i = 1; i < 10; i++)
    {
        for (size_t j = 1; j < 10; j++)
        {
            int count = 0 ;
            for (size_t k = 1; k < n+1; k++)
            {
                if (k % 10 == i)
                {
                    int copy = k ;
                    while (copy>= 10)
                    {
                        copy /=10 ;
                    }
                    if (copy == j)
                    {
                        count ++ ;
                    }
                    
                }
                
            }
            t.at(i).at(j) = count ;
        }
        
    }
    

    for (size_t i = 1; i < n+1; i++)
    {
        if (i % 10 == 0)
        {
            continue ;
        }
        int c = i ;
        int a = c % 10 ;
        while (c >= 10)
        {
            c /= 10 ;
        }
        int b = c ;
        ans += t.at(b).at(a) ;

    }
    cout << ans << endl ;
}    

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;
using ull = unsigned long long;
const ull HASH_BASE = 1234567891ull;

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	string s;
	cin >> n >> s;
	const string head = s.substr(0, n);
	const string tail = s.substr(n);
	unordered_map<ull, ull> mp;
	for(int i = 0; i < (1 << n); ++i){
		ull h = 0;
		for(int j = n - 1; j >= 0; --j){
			if(i & (1 << j)){ h = (h * HASH_BASE) + tail[j]; }
		}
		h = h * HASH_BASE;
		for(int j = 0; j < n; ++j){
			if(!(i & (1 << j))){ h = (h * HASH_BASE) + tail[j]; }
		}
		++mp[h];
	}
	ull answer = 0;
	for(int i = 0; i < (1 << n); ++i){
		ull h = 0;
		for(int j = 0; j < n; ++j){
			if(i & (1 << j)){ h = (h * HASH_BASE) + head[j]; }
		}
		h = h * HASH_BASE;
		for(int j = n - 1; j >= 0; --j){
			if(!(i & (1 << j))){ h = (h * HASH_BASE) + head[j]; }
		}
		const auto it = mp.find(h);
		if(it != mp.end()){ answer += it->second; }
	}
	cout << answer << endl;
	return 0;
}



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

int main()
{
    ll n, ans = 0;
    string s;
    cin >> n >> s;
    rep(i, n - 1)
    {
        if (s[i] != s[i + 1])
            ans++;
    }
    cout << ans + 1 << endl;
    return 0;
}

Measured memory_bytes: 3760
#include<bits/stdc++.h>
using namespace std;
 
constexpr int calc(int n, int c1, int c2, int s1, int s2, int options[],
               int d, int nt, int ot) {
  int b1(d-1), a1(d+1), b2(d-1), a2(d+1);
  while (b1 >= 0 && options[b1] != nt) b1--;
  while (b2 >= 0 && options[b2] != ot) b2--;
  while (a1 < n && options[a1] != nt) a1++;
  while (a2 < n && options[a2] != ot) a2++;
  int x1(d-b1-1), y1(a1-d-1), z1(a1-b1-1), x2(d-b2-1), y2(a2-d-1), z2(a2-b2-1);
  int diff1 = z1*(z1+1)/2-x1*(x1+1)/2-y1*(y1+1)/2;
  int diff2 = z2*(z2+1)/2-x2*(x2+1)/2-y2*(y2+1)/2;
  return diff1 * c1 - diff2 * c2 + s1 - s2;
}

static unsigned int myrand() {
	static unsigned int x=192047155,y=392751284,z=194681846,w=193571838;
    unsigned int t;
    t=(x^(x<<11));x=y;y=z;z=w; return w=(w^(w>>19))^(t^(t>>8));
}

constexpr bool check(int diff, int time) {
  return diff >= 0 || myrand() >= (-diff) * (clock()-time) * 1.4;
}

int main() {
  int n;
  cin >> n;
  int c[26], last[26], s[n][26], op[n];
  
  for (int i = 0; i < 26; ++i) {
    cin >> c[i];
    last[i] = -1;
  }
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < 26; ++j)
      cin >> s[i][j];
  
  int total(0);
  
  for (int i = 0; i < n; ++i) {
    int neg(0), test(-1), max_score(-1e9);
    for (int j = 0; j < 26; ++j) neg -= c[j] * (i - last[j]);
    for (int j = 0; j < 26; ++j) {
      int ss = s[i][j] + neg + c[j] * (i - last[j]);
      if (ss > max_score) {
        max_score = ss;
        test = j;
      }
    }
    total += max_score;
    op[i] = test;
    last[test] = i;
  }
  
  // stochastic
  time_t time = clock();
  while ((clock()-time)<=1.97*CLOCKS_PER_SEC) {
    if (myrand() & 1) {
      int dd(myrand() % n), ot(op[dd]), tt;
      do { tt = myrand() % 26; } while (ot == tt);
      
      op[dd] = tt;
      int ns = calc(n, c[tt], c[ot], s[dd][tt], s[dd][ot], op, dd, tt, ot);
      
      if (check(ns,time)) {
        total += ns;
      } else {
        op[dd] = ot;
      }
    } else {
      int dd1(myrand() % n), ot1(op[dd1]), dd2, ot2;
      do { dd2 = myrand() % n; ot2 = op[dd2]; } while (ot1 == ot2);
      
      op[dd1] = ot2;
      int ns1 = calc(n, c[ot2], c[ot1], s[dd1][ot2], s[dd1][ot1], op, dd1, ot2, ot1);
      op[dd2] = ot1;
      int ns2 = calc(n, c[ot1], c[ot2], s[dd2][ot1], s[dd2][ot2], op, dd2, ot1, ot2);
      
      if (check(ns1+ns2,time)) {
        total += ns1 + ns2;
      } else {
        op[dd1] = ot1;
        op[dd2] = ot2;
      }
    }
  }
  
  for (const int& i: op) cout << i + 1 << endl;
  
  return 0;
}


Measured memory_bytes: 3648
h,w = map(int,input().split())
grid = []
ans = []
for i in range(h):
    grid.append(list(map(int,input().split())))
cur = [0,0]
while True:
    y,x = cur[0],cur[1]
    if y % 2 == 0:
        if x != w-1:
            if grid[y][x] % 2 == 1:
                grid[y][x] -= 1
                grid[y][x+1] += 1
                ans.append((y+1,x+1,y+1,x+2))
            cur[1] += 1
        else:
            if y >= h-1:
                break
            if grid[y][x] % 2 == 1:
                grid[y][x] -= 1
                grid[y+1][x] += 1
                ans.append((y+1,x+1,y+2,x+1))
            cur[0] += 1
    else:
        if x != 0:
            if grid[y][x] % 2 == 1:
                grid[y][x] -= 1
                grid[y][x-1] += 1
                ans.append((y+1,x+1,y+1,x))
            cur[1] -= 1
        else:
            if y >= h-1:
                break
            if grid[y][x] % 2 == 1:
                grid[y][x] -= 1
                grid[y+1][x] += 1
                ans.append((y+1,x+1,y+2,x+1))
            cur[0] += 1
print(len(ans))
for i in ans:
    print(i[0],i[1],i[2],i[3])

Measured memory_bytes: 75228
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};


int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    rep(i, n) {
        cin >> a[i];
        mp[a[i]]++;
    }
    int ans = 0;
    for (auto m: mp) {
        if (m.second>=m.first) ans += m.second-m.first;
        else ans += m.second;
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 8208
n,m = map(int,input().split())
py = list()
for i in range(m):
    l = list(map(int,input().split()))
    l.append(i)
    py.append(l)
py.sort()
ret = list()
c = 1
la = -1
for x in py:
    if la != x[0]:
        c = 1 
    ret.append( (('{0:06d}'.format(x[0])+'{0:06d}'.format(c)),x[2]) )
    c+=1
    la = x[0]
ret.sort(key=lambda x:x[1])
for i in ret:
    print(i[0])


Measured memory_bytes: 46404
#include<bits/stdc++.h>
#define V vector
#define W V<long>
using namespace std;long E,M=2e17,a,b;W A;W S(V<W>p){if(!E)return{1,0};V<V<W>>T(2);for(W x:p){T[x[1]&1].push_back({x[0]/2,x[1]/2});if(x[0]&1)T[x[1]&1].push_back({x[0]/2,++x[1]/2});}for(long i;i<2;i++){a=0;for(W x:T[!i])a^=(2*x[0]+x[1])%3+1;if(!a){E--;A=S(T[i]);A[0]*=2;A[1]*=2;A[1]+=i;return A;}}for(W&v:p)v[0]++;A=S(p);A[0]--;return A;}int main(){cin>>E;V<W>p(E);E*=2;while(E--,cin>>a)p[E/2].push_back(a+M);E=70;A=S(p);cout<<A[0]-M<<" "<<A[1]-M;}

Measured memory_bytes: 62908
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main(){
long long int D, G; 
cin >> D >> G; 
long long int P[20]; 
long long int C[20]; 
for(int i = 1; i <= D; i++){
cin >> P[i] >> C[i]; 
}
long long int ans = 2018; // 最終的な答え

for (int bit = 0; bit < (1<<D); ++bit){
long long int A = 0; // ボーナス込みでとった点数の和
long long int B = 0; // 解いた問題数
  for (int i = 0; i < D; i++) {
if ((bit / (1<<i)) % 2 == 1) 
{A += 100 * (i+1) * P[i+1] + C[i+1];
 B += P[i+1]; 
}
  }

  for (int i = D-1; i >= 0; i--) {
   if(G <= A){break;
   }
   else if(((bit / (1<<i)) % 2 == 0) 
      && (G - A > (P[i+1] - 1) * 100 * (i+1)))
    {A += (P[i+1] - 1) * 100 * (i+1);
     B += P[i+1] - 1;  
     }
   else if(((bit / (1<<i)) % 2 == 0)
           && (G - A <= (P[i+1] - 1) * 100 * (i+1)))
    {B += (G - A + 100 * (i+1) - 1)/ (100 * (i+1)); 
     A += (G - A + 100 * (i+1) - 1)/ (100 * (i+1)) * 100 * (i+1);
    }
  }
if(G <= A){
  ans = min(B, ans); 
} 
}
cout << ans << endl; 
}

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

int main()
{
    int a=0,b=0,c=0;
    string s ;
    cin>>s ;
    int cont [100];
    for (int i=0;i<3;i++)
    {
     if(s[i]=='a')
            a++ ;
     else if(s[i]=='b')
            b++ ;
     else if(s[i]=='c')
            c++ ;
    }
    if (a==1&&b==1&&c==1)
     cout<<"Yes" ;
    else
        cout<<"No" ;

}


Measured memory_bytes: 256