akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
using namespace std;
// 型シノニム
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
// 定数
constexpr ll INF   = 1e16;
constexpr ll INM   = 114514;
constexpr ll MOD   = 1e9 + 7;
constexpr ld EPS   = 1e-12;
constexpr ll dx[4] = {1, 0, -1, 0};
constexpr ll dy[4] = {0, 1, 0, -1};
// 便利関数
void IOS() { ios::sync_with_stdio(false), cin.tie(0); }
template <typename T>
void dump(T x) { cout << x << endl; }
void dumpf(ld x, ll t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
inline ll mod(ll a, ll mod) {
	if (a > 0) return a % mod;
	if (a % mod == 0) return 0;
	ll x = -a / mod + 1;
	a += x * mod;
	return a % mod;
}
ll powm(ll a, ll b, ll m) {
	if (b == 0) {
		return 1;
	} else if (b % 2 == 0) {
		ll d = powm(a, b / 2, m);
		return (d * d) % m;
	} else {
		return (powm(a, b - 1, m) * a) % m;
	}
}

// 本体

int main() {
	IOS();
	ll n;
	ll ans = 1;
	ll inf = 1;
	for (int i = 0; i < 18; i++) {
		inf *= 10;
	}
	cin >> n;
	vector<ll> a(n);
	bool isz = false;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		isz = isz || a[i] == 0;
	}
	if (isz) {
		dump(0);
		return 0;
	}
	for (int i = 0; i < n; i++) {
		if (a[i] > inf / ans) {
			dump(-1);
			return 0;
		}
		ans *= a[i];
	}
	dump(ans);
  // kusosugi
}

Measured memory_bytes: 3928
#include<bits/stdc++.h>
#define int long long int
#define fr(i,x,y) for(int i=x;i<y;i++)
#define f(n) for(int i=0;i<n;i++)
#define ff(m) for(int j=0;j<m;j++)
#define F(x) for(auto it:x)
#define in insert
#define pb push_back
#define pi pair<int,int>
#define si second
#define fi first
#define show_(x) cerr<<"-> "<<#x<<endl;F(x){cerr<<it<<" ";}cout<<endl;
#define show(x) cerr<<#x<<"-> "<<x<<endl;
//#define start_routine cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int begtime = clock();
//#define end_routine int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0;
#define FILEIO freopen("F:\\inout\\input.txt", "r", stdin); freopen("F:\\inout\\output.txt", "w", stdout);
using namespace std;
void print(int a[],int n){f(n){cout<<a[i]<<" ";}cout<<endl;}
int m(int x){return x%1000000007;} 
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
int p(int a,int b){if(b==0)return 1;int t=p(a,b/2); if(b%2==0)return t*t; else return a*t*t; } 
//strlen(s.c_str());  set <int, greater<int>> s; numeric_limits<double>::max()
//---------------------------------------------------------------------------------------------------------------------------------------------
 int t[100000];


signed main(){
	//FILEIO
	//cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin>>n;
	int a[n];
	f(n){
		cin>>a[i];
	}
	int count=0;
	f(n){
		if(i==0 || i==n-1){
			continue;
		}
		if(a[i]<a[i-1] && a[i]>a[i+1]){
			count++;
			continue;
		}
		if(a[i]>a[i-1] && a[i]<a[i+1]){
			count++;
			continue;
		}
	}
	cout<<count<<endl;

	

	
	
	






	return 0;
}



Measured memory_bytes: 256
w=int(input())
n=int(input())
v=list(range(1,w+1))
for i in range(n):
    a,b=map(int,input().split(","))
    v[a-1],v[b-1]=v[b-1],v[a-1]
for i in range(w):
    print(v[i])

Measured memory_bytes: 7480
#include <bits/stdc++.h>
using namespace std;
#define mod 100000007
#define SIZE 500006
int vec[SIZE];

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

      int t,i,n,a,b,sum=0,j;

      cin>>t;
      int ara[t];
      for(i=0;i<t;i++)
      {
          cin>>ara[i];
      }
      for(i=0;i<t;i++)
      {
        for(j=1+i;j<t;j++)
        {
            sum+=(ara[i]*ara[j]);
        }

      }
       cout<<sum<<"\n";

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

namespace ABC133B
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int[] nd = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[][] x = new int[nd[0]][];
            for (int i = 0; i < nd[0]; i++)
            {
                x[i] = Console.ReadLine().Split().Select(int.Parse).ToArray();
            }
            int cnt = 0;
            for (int i = 0; i < nd[0]-1; i++)
            {
                for (int j = i+1; j < nd[0]; j++)
                {
                    var sum = 0.0;
                    for (int k = 0; k < nd[1]; k++)
                    {
                        sum += Math.Pow(x[i][k] - x[j][k], 2);
                    }
                    for (int l = 0; l <= sum; l++)
                    {
                        if (l * l == sum) cnt++;
                    }
                }
            }
            Console.WriteLine(cnt);
        }
    }
}


Measured memory_bytes: 13396
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long  fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y){
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] >= key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = (int)meguru.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) right = mid;
		else left = mid;
	}
	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	int number = 1;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (a != number) {
			ans++;
		}
		else {
			number++;
		}
	}
	if (number == 1) {
		cout << -1;
	}
	else {
		cout << ans;
	}
}

Measured memory_bytes: 256
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
ll c[26];
ll d[400][26];

ll calc(vector<int> &contest){
	ll last[26];
	
	memset(last,-1,sizeof(last));
	
	ll res=0;
	rep(x,0,n){
		res+=d[x][contest[x]];
		last[contest[x]]=x;
		
		rep(y,0,26) res-=c[y]*(x-last[y]);
	}
	
	return res;
}

//store curr best
ll best;
vector<int> ans;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	//freopen("sample2.in","r",stdin);
	
	auto begin_time=chrono::steady_clock::now().time_since_epoch().count();
	
	cin>>n;
	rep(x,0,26) cin>>c[x];
	
	rep(x,0,n){
		rep(y,0,26) cin>>d[x][y];
	}
	
	vector<int> curr;
	rep(x,0,n){
		curr.push_back(0);
	}
	
	ll val=calc(curr);
	
	best=val;
	ans=curr;
	
	while (chrono::steady_clock::now().time_since_epoch().count()-begin_time<1900000000){
		rep(zzz,0,200){ //try a few times to go to a smaller place
			int idx=rng()%n;
			int type=curr[idx];
			
			curr[idx]=rng()%26;
		
			ll temp=calc(curr);
			if (temp>val){
				val=temp;
				
				if (best<val){
					best=val;
					ans=curr;
				}
				
				goto ok;
			}
			else{
				curr[idx]=type;
			}
		}
		
		//cout<<"reached "<<val<<endl;
		
		//almost maxima. screw around
		rep(x,0,3){
			curr[rng()%n]=rng()%26;
			val=calc(curr);
		}
		
		ok:;
	}
	
	//pls uncomment later
	rep(x,0,n) cout<<ans[x]+1<<endl;
	
	//cout<<"debug: "<<best<<endl;
}


Measured memory_bytes: 3728
#include <iostream>

int main() {
    int H, W, s = 1;
    std::cin >> H >> W;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            char t;
            std::cin >> t;
            if (t == '#') s++;
        }
    }

    std::cout << (s == H + W ? "Possible" : "Impossible") << std::endl;
}


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

#define         pb         push_back
#define         sf(x)      scanf("%d",&x)
#define         sfl(x)     scanf("%lld",&x)
#define         pf(x)      printf("%d\n",x)
#define         pfl(x)     printf("%lld\n",x)
#define         endl       '\n'
#define         pii        pair<int,int>
#define         mapii      map<int,int>
#define         mapll      map<ll,ll>
#define         mapci      map<char,int>
#define         mapcl      map<char,ll>
#define         mapsi      map<string,int>
#define         mapsl      map<string,ll>
#define         pll        pair<ll,ll>
#define         vi         vector<int>
#define         vl         vector<ll>
#define         vd         vector<double,double>
#define         all(c)     c.begin(),c.end()
#define         F          first
#define         S          second
#define         mp         make_pair
#define        ftc(x)      cerr << #x << ": " << x << " " << endl;
#define         PI         acos(-1)
#define         lcm(a,b)   ((a*b)/__gcd(a,b))
#define        optimize    ios_base::sync_with_stdio(false);cin.tie(NULL);
#define        sqr(a)       ((a)*(a))
#define         MOD     2019

ll binPow(ll a, ll q)
{
    a %= MOD;
    if (q == 0) return 1;
    return ((q % 2 == 1 ? a : 1) * binPow(a * a, q / 2)) % MOD;
}
mapll mpp;
int main()
{
    ll i,j,k,l,m,n;

    string s;

    cin >> s;

    n = s.size();

    ll rem[n+10],ans=0;
reverse(all(s));
    rem[0] = (binPow(10,0) * (s[0]-'0'))%MOD;
    mpp[rem[0]]++;
    for(i=1; i<n; i++)
    {
        rem[i] = (rem[i-1] + (binPow(10,i) * (s[i]-'0'))%MOD)%MOD;
        if(rem[i]==0)ans++;
        ans += mpp[rem[i]];
        mpp[rem[i]]++;

    }

    cout << ans << endl;


}


Measured memory_bytes: 5268
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

int gcd(int a,int b){
    if(a%b==0) return b;
    return gcd(b,a%b);
}

signed main()
{
    int A,B,C;
    cin>>A>>B>>C;

    if(C%gcd(A,B)==0)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vchar = vector<char>;
using vvchar = vector<vchar>;
using vp = vector<P>;
using vpp = vector<pair<P, P>>;
using vvp = vector<vp>;

#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
istream &operator>>(istream &is, P &a)
{
    return is >> a.first >> a.second;
}
ostream &operator<<(ostream &os, const P &a) { return os << "(" << a.first << "," << a.second << ")"; }

template <typename T>

void view(const std::vector<T> &v)
{
#ifndef ONLINE_JUDGE
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
#endif
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion

int main()
{
    int n;
    cin >> n;
    vll a(n);
    rep(i, n) cin >> a[i];
    vll neg;
    ll ans = 0;
    rep(i, n)
    {
        if (a[i] <= 0)
        {
            neg.emplace_back(abs(a[i]));
        }
        ans += abs(a[i]);
    }
    int k = neg.size();

    if (k % 2)
    {
        ll sml = 10000000000;
        rep(i, n) sml = min(sml, abs(a[i]));
        ans -= sml * 2;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 5032
import java.util.Arrays;
import java.util.Scanner;

public class Main implements Runnable {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        // Run with 32MB stack
        Thread thread = new Thread(null, new Main(), "", 32 * 1024 * 1024);
        thread.start();
    }

    @Override
    public void run() {
        final Scanner scanner = new Scanner(System.in);
        solve(scanner);
    }

    static void solve(Scanner scanner) {
        int N = scanner.nextInt();
        int Q = scanner.nextInt();
        scanner.nextLine();

        SegTree segTree = new SegTree(N, new Min());
        for (int i = 0; i < Q; i++) {
            int[] q = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            if (q[0] == 0) {
                segTree.update(q[1], q[2]);
            } else {
                System.out.println(segTree.query(q[1], q[2]));
            }
        }
    }

}

class SegTree {

    class Node {
        long val;
    }

    int size;
    Operation op;
    Node[] nodes;

    public SegTree(int size, Operation op) {
        this.size = Integer.highestOneBit(size);
        if (size > this.size) {
            this.size <<= 1;
        }
        this.op = op;
        nodes = new Node[this.size * 2];
        for (int i = 1; i < this.size * 2; i++) {
            nodes[i] = new Node();
            nodes[i].val = op.getInit();
        }
    }

    public void update(int index, int val) {
        update(index, val, true);
    }

    public void update(int index, int val, boolean overwrite) {
        index += size;
        nodes[index].val = overwrite ? val : op.calc(nodes[index].val, val);
        while ((index >>= 1) > 0) {
            nodes[index].val = op.calc(nodes[2 * index].val, nodes[2 * index + 1].val);
        }
    }

    public long query(int fromInc, int toInc) {
        fromInc += size;
        toInc += size;
        long left = op.getInit();
        long right = op.getInit();
        while (fromInc <= toInc) {
            if ((fromInc & 1) > 0)
                left = op.calc(left, nodes[fromInc++].val);
            if ((toInc & 1) == 0)
                right = op.calc(right, nodes[toInc--].val);
            fromInc >>= 1;
            toInc >>= 1;
        }
        return op.calc(left, right);
    }
}

abstract class Operation {
    abstract public long getInit();

    abstract public long calc(long x, long y);
}

class Min extends Operation {

    @Override
    public long getInit() {
        return Integer.MAX_VALUE;
    }

    @Override
    public long calc(long x, long y) {
        return Math.min(x, y);
    }
}



Measured memory_bytes: 181684
from bisect import bisect_left

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

def count(x):
    ret = 0
    for a in A:
        ret += N - bisect_left(A, x - a)
    return ret

overEq = 0
less = 10**7
while less - overEq > 1:
    mid = (less + overEq) // 2
    if count(mid) >= M:
        overEq = mid
    else:
        less = mid

ans = 0
cnt = [0] * N
for a in A:
    i = (N - bisect_left(A, overEq - a))
    ans += i * a
    if i > 0:
        cnt[-i] += 1
for i in range(1, N):
    cnt[i] += cnt[i - 1]
for a, c in zip(A, cnt):
    ans += a * c

ans -= overEq * (count(overEq) - M)

print(ans)


Measured memory_bytes: 14324
import java.util.Scanner;

class Main {
  public static final int INF = 10000;
  public static int N;

  public static void main(String... args) {
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    int[][] roots = new int[N][N];
    Node[] nodes = new Node[N];

    for (int i = 0; i < N; i++) {
      nodes[i] = new Node();
      for (int j = 0; j < N; j++) {
        roots[i][j] = sc.nextInt();
      }
    }

    nodes[0].cost = 0;

    int min;
    int u = 0;
    while (true) {
      min = INF;

      for (int i = 0; i < N; i++) {
        if (!nodes[i].selected && nodes[i].cost < min) {
          min = nodes[i].cost;
          u = i;
        }
      }

      if (min == INF) {
        break;
      }

      nodes[u].selected = true;

      for (int v = 0; v < N; v++) {
        if (!nodes[v].selected && roots[u][v] != -1) {
          if (roots[u][v] < nodes[v].cost) {
            nodes[v].cost = roots[u][v];
          }
        }
      }
    }

    int result = 0;
    for (Node node : nodes) {
      result += node.cost;
    }

    System.out.println(result);
  }
}

class Node {
  public static final int INF = 10000;
  public int cost = INF;
  public boolean selected;

  public Node() { }
}



Measured memory_bytes: 40856
#include <bits/stdc++.h>
using LL = long long;
using namespace std;
#define DBG(x) cerr<<#x<<" = "<<x<<endl

int W,H;
char c;

int main() {
	cin >> W >> H >> c;
	
	vector<vector<char>>ans(H, vector<char>(W, '.'));
	for (int i = 0; i < W; ++i) ans[0][i] = ans[H - 1][i] = '-';
	for (int i = 0; i < H; ++i) ans[i][0] = ans[i][W - 1] = '|';
	ans[0][0] = ans[0][W - 1] = ans[H - 1][0] = ans[H - 1][W - 1] = '+';
	ans[H/2][W/2]=c;
	
	for(int i=0;i<H;++i){
		for(int j=0;j<W;++j){
			cout << ans[i][j];
		}
		cout << std::endl;
	}
	return 0;
}


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

int value[301];

int pow(int x, int n) {
  int ans = 1;
  for(int i = 0; i < n; i++) {
    ans *= x;
  }
  return ans;
}

bool isHeiho(int x) {
  return (double)((int)sqrt(x)) == sqrt(x);
}

void rec(int minI, int x, int maxX) {
  if(x == 0) {
    value[maxX]++;
    return;
  }
  for(int i = minI; i <= 17; i++) {
    int tmp = pow(i, 2);
    if(tmp <= x) rec(i, x-tmp, maxX);
    if(tmp > x) break;
  }
}

int main() {
  for(int i = 1; i <= 30; i++) {
    value[i] = 0;
  }

  while(1) {
    int price;
    cin >> price;
    if(price == 0) break;
    if(value[price] == 0) {
      rec(1, price, price);
    }
    cout << value[price] << endl;
  }
  return 0;
}

Measured memory_bytes: 868
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cstdio>

using namespace std;

#define rep(i, n) for(long int i = 0; i < n; i++)
#define P pair<long int, long int>

int main(){
    int n;
    cin >> n;
    int p[n];
    rep(i, n) cin >> p[i];
    int mn = 1000000;
    int ans = 0;
    for (int i = 0; i < n; i++){
        if (mn > p[i]){
            ans++;
            mn = p[i];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
bool contain(int mask, int position){
    if((mask & (1 << position)) != 0) return true;
    else return false;
}
void solve() {
  int a;
  const int n = 3;
  cin >> a;
  string s = to_string(a);
  while (s.size() != 4) {
    s = "0" + s;
  }

  string ans;
  for (int bit = 0;bit < (1 << n); ++bit) {
    int temp = stoi(s.substr(0, 1));
    ans = s.substr(0, 1);
    for (int i = 0; i < n; ++i) {
      if (contain(bit, i)) {
        temp += stoi(s.substr(i + 1, 1));
        ans = ans + "+" +s.substr(i + 1, 1);
      } else {
        temp -= stoi(s.substr(i + 1, 1));
        ans = ans + "-" + s.substr(i + 1, 1);
      }
    }
    if (temp == 7) {
      cout << ans + "=7" << endl;
      break;
    }
  }
}

int main() {
  solve();
  return 0;
}


Measured memory_bytes: 256
/**
 *    author:  otera    
**/
#include<iostream>
#include<string> 
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm> 
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }

void solve() {
	string s; cin >> s;
    if(s.size() == 3) reverse(all(s));
    cout << s << endl; 
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<map>
#define all(x) (x).begin(),(x).end()
#define print(x) cout << (x) << endl
typedef long long ll;
const ll MOD = 1000000007;
 
using namespace std;

int main(){
    string X;   cin >> X;
    int l = X.length();
    int cnt = 0;
    queue<int> que;
    for(int i=0; i<l; i++){
        if(i == 0)  cnt++;
        else{
            if(X[i] == 'S'){
                if(X[i-1] == 'T'){
                    que.push(cnt);
                    cnt = 0;
                }
                cnt++;
            }else{
                if(X[i-1] == 'S'){
                    que.push(cnt);
                    cnt = 0;
                }
                cnt++;
            }
        }
    }
    que.push(cnt);
    int s, t, cs;
    if(X[0] == 'T'){
        t = que.front();
        que.pop();
    }
    cnt = 0;
    cs = 0;
    while(!que.empty()){
        s = que.front();
        que.pop();
        if(!que.empty()){
            t = que.front();
            que.pop();
            cnt += (s-t);
            cs += s;
            if(cnt <= 0){
                l -= 2*cs;
                cs = 0;
                cnt = 0;
            }
        }else{
            break;
        }
    }
    l -= 2*(cs-cnt);
    cout << l << endl;
    return 0;
}

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

int main(){
    int N;
    long long ans = 1<<30;
    cin >> N;
    vector<int> vec(N);
    for(int i=0;i<N;i++) cin >> vec[i];

    int min = *min_element(vec.begin(), vec.end());
    int max = *max_element(vec.begin(), vec.end());

    for(int P=min;P<=max;P++){
        long long n = 0;
        for(int i:vec){
            n += pow(P-i, 2);
        }
        if(n<ans) ans = n;
    }
    cout << ans << endl;
} 


Measured memory_bytes: 256
N = int(input())

memo = [0]*(N+1)
for i in range(1,150):
  for j in range(1,150):
    for k in range(1,150):
      n = (i+j)**2 + (j+k)**2 + (k+i)**2
      if n <= 2*N and n%2 == 0:
        memo[n//2] += 1
        
for i in memo[1:]:
  print(i)

Measured memory_bytes: 74572
package main

import (
	"fmt"
	"math/big"
)

func main() {
	var n, v int
	fmt.Scanln(&n)
	ans := 0
	for ; n > 0; n-- {
		fmt.Scanln(&v)
		x := big.NewInt(int64(v))
		if x.ProbablyPrime(100) {
			ans++
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 6148
#include <bits/stdc++.h>
typedef long long ll;
#define fr(i,a,b) for(ll i=a; i<b; i++)
#define rf(i,a,b) for(ll i=a; i>=b; i--)
typedef std::vector<long long > vi ;
#define F first
#define S second
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 1000000007
#define PB push_back
#define MP make_pair
#define PI 3.14159265358979323846
#define all(a) a.begin(),a.end()
#define mx(a) *max_element(all(a))
#define mn(a) *min_element(all(a))
#define endl '\n'
#define show(a) for(auto el:a)cout<<el<<" "
const ll INF=LLONG_MAX/2;
const ll N=2e5+1;
#define yesno(f) yes(f);no(f);
#define yes(f) if(f)cout<<"YES\n";
#define no(f) if(!f)cout<<"NO\n";
using  namespace std;
ll pow1(ll n,ll p)
{
	if(p==0)	return 1;
	ll x=pow1(n, p/2);
	x=(x*x);
	if(p%2==0)
		return x;
	else
		return (x*n);
}
int main()
{
    fast;
   ll t=1;
    //std::cin >> t;
   while(t--)
   {
       ll n,w,x=0,sum=0,a,b,c;
       std::cin >> a>>b>>c;
       if(a==b&&b!=c)
       {
           cout<<"Yes\n";
       }
       else if(a==c&&a!=b)
       {
           cout<<"Yes\n";
       }
       else if(b==c&&a!=b)
       {
           cout<<"Yes\n";
       }
       else
       cout<<"No\n";
   }
}

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

int main(){
	int n,cont = 0,res = 0;
	cin>>n;
	int vals[n];
	for (int k = 0; k <n;k++){
		cin >> vals[k];
		cont += vals[k];
	}
	//cout<<cont<<endl;
	cont = round((float)cont/(float)n);
	//cout<<cont<<endl;
	for (int k = 0; k <n;k++){
		res += (cont-vals[k])*(cont-vals[k]);
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 512
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    S = list(input())
    
    x = 0
    ans = 0
    for i in S:
        if i == "I":
            x += 1
        else:
            x -= 1
        ans = max(ans,x)
        
    print(ans)
    
if __name__ == "__main__":
	main()


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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

const ll MAX = 1e5 + 10;
const ll MOD = 1e9 +  7;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  COMinit();

  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    a[i] = -1;
  }

  ll tmp;
  ll pos1, pos2;
  for(int i = 0; i < n+1; i++){
    cin >> tmp;
    tmp--;
    if(a[tmp] >= 0){
      pos1 = a[tmp];
      pos2 = i;
    }else{
      a[tmp] = i;
    }
  }

  ll Nout = pos1 + n - pos2;

  vector<ll> ans(n+1);
  for(int i = 0; i < n+1; i++){
    ans[i] = 0LL;
  }

  for(int i = 0; i < n+1; i++){
    // (i+1)個選ぶ方法
    // まず、n-1個からi+1個選ぶ方法を足す
    ans[i] = (ans[i] + COM(n-1, i+1)) % MOD;

    // 次に、Nout個からi個選ぶ方法
    ll comout = COM(Nout, i);
    
    ans[i] = (ans[i] + comout) % MOD;

    ans[i] = (ans[i] + (((COM(n-1, i) + MOD - comout) % MOD) * 2) % MOD) % MOD;

    ans[i] = (ans[i] + COM(n-1, i-1)) % MOD;

  }

  for(int i = 0; i < n+1; i++){
    cout << ans[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 4736
N = int(input())
A = []
for i in range(N):
  temp = int(input())
  A.append(temp)
if A[0] != 0:
  print(-1)
  exit()
ans = 0
prev = 0

for i in range(1,N+1):
  #print(prev,A[-i],ans)
  if A[-i] > N-i:
    print(-1)
    exit()
  if prev == 0:
    prev = A[-i]
    ans += A[-i]
  else:
    if A[-i] == prev-1:
      prev = A[-i]
    elif A[-i] > prev-1:
      prev = A[-i] #- (prev-1)
      ans += prev
    else:
      print(-1)
      exit()
print(ans)


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

int main()
{
	int n,x,t;
	cin>>n>>x>>t;
	int ans=0;
	
	if(n%x==0) ans=n/x;
	else ans=n/x+1;
	
	cout<<ans*t<<endl;
	return 0;
	
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

double pi = acos(-1.0);


int main(){
    
    ll a, b, x; cin >> a >> b >> x;
    ll volume = a*a*b;
    if(2*x > volume){
        x = volume-x;
        double theta = atan((2.0*x)/(a*a*a));
        double deg = theta*180/pi;
        printf("%.6f\n", deg);
    }
    else{
        double theta = atan((2.0*x)/(b*b*a));
        double deg = theta*180/pi;
        printf("%.6f\n", 90-deg);       
    }
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#define endl "\n"
using namespace std;

int main()
{
    string s;
    map <char, int> mp;

    cin >> s;

    int i;
    for(i = 0; i < 4; i ++)
    	mp[s[i]] ++;

    if(mp.size() != 2)
    	cout << "No" << endl;
    else if(mp[s[0]] != 2)
    	cout << "No" << endl;
    else
    	cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#define int long long

const int MaxN = 5e5 + 10;
const int Mod = 1e9 + 7;

const int Next[10][2] = {{2, 1}, {4, 3}, {6, 5}, {3, 3}, {7, 1}, {2, 1}, {2, 2}, {4, 4}};

char S[MaxN];
int F[MaxN][10];
int N;

main() {
	scanf("%s", S + 1); F[0][0] = 1;
	for(int i = 1; S[i]; N++, i++);
	for(int i = 0; i < N; i++) 
		for(int j = 0; j <= 7; j++) {
			if(S[i + 1] != '0') F[i + 1][Next[j][1]] = (F[i + 1][Next[j][1]] + F[i][j]) % Mod;
			if(S[i + 1] != '1') F[i + 1][Next[j][0]] = (F[i + 1][Next[j][0]] + F[i][j]) % Mod;
		}
	printf("%lld", (F[N][1] + F[N][3]) % Mod) ;
} 

Measured memory_bytes: 25088
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <regex>
#include <random>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exout(x) printf("%.10f\n", x)
const double pi = acos(-1.0);
const ll MOD = 1000000007;
const ll INF = 1e10;
const ll MAX_N = 1010;

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

ll w[110];
ll v[110];
ll dp[101010][110];

//long longしか使わない
//素数は1より大きい
int main() {
	ll N, W;
	cin >> N >> W;
	rep(i, N) {
		cin >> w[i] >> v[i];
	}
	rep(i, 110) {
		rep(j, 101010) {
			dp[j][i] = INF;
		}
	}
	rep(i, N) {
		dp[0][i] = 0;
	}
	rep(i, N) {
		rep(j, 101000) {
			if (j - v[i] >= 0) {
				dp[j][i + 1] = min(dp[j][i], dp[j - v[i]][i] + w[i]);
			}
			else {
				dp[j][i + 1] = dp[j][i];
			}
		}
	}
	for (ll i = 100000;i >= 0;--i) {
		if (dp[i][N] <= W) {
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 87040
#include <stdio.h>
int main() {
    char s[11],t[12];	
    scanf("%s ",&s);	
    scanf("%s ",&t);
  
    int i;
    for (i = 0;s[i] != '\0';i++){
        if (s[i] != t[i]){
            printf("No");
            return 0;
        }
    }
 
    printf("Yes");
    return 0;
}


Measured memory_bytes: 2156
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	char d1[5];
	char d2[5];
	
	while (1){
		int s, b;
		
		s = b = 0;
		scanf("%s%s", d1, d2);
		if (atoi(d1) == 0){
			break;
		}
		
		for (int i = 0; i < 4; i++){
			if (d1[i] == d2[i]){
				s++;
			}
			else {
				for (int j = 0; j < 4; j++){
					if (d1[i] == d2[j]){
						b++;
					}
				}
			}
		}
		
		printf("%d %d\n", s, b);
	}
	
	return (0);
}

Measured memory_bytes: 0
def findLR(x, arr)
    if x < arr[0]
        return [nil, arr[0]]
    elsif x > arr[-1]
        return [arr[-1], nil]
    end

    r = arr.bsearch_index{|xi|xi > x}
    return [arr[r-1], arr[r]]
end


def calc(x, s, t)
    sLR = findLR(x, s)
    tLR = findLR(x, t)

    result = nil

    sl = sLR[0]
    sr = sLR[1]
    tl = tLR[0]
    tr = tLR[1]

    if sl && tl
        result = [x - sl, x - tl].max
    end
    if sl && tr
        hoge = (x - sl) * 2 + (tr - x)
        huga = (tr - x) * 2 + (x - sl)
        if result
            result = [hoge, result, huga].min
        else
            result = [hoge,huga].min
        end
    end
    if sr && tl
        hoge = (x - tl) * 2 + (sr - x)
        huga = (sr - x) * 2 + (x - tl)
        if result
            result = [hoge, result, huga].min
        else
            result = [hoge,huga].min
        end
    end
    if sr && tr
        hoge = [sr - x, tr - x].max
        if result
            result = [hoge, result].min
        else
            result = hoge
        end
    end

    return result
end

a,b,q = gets.split.map &:to_i

s = []
a.times do |i|
    s[i] = gets.to_i
end

t = []
b.times do |i|
    t[i] = gets.to_i
end

q.times do |i|
    puts calc(gets.to_i, s, t)
end


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

#define int long long
#define INF ((int)1e18)
#define MOD ((int)(1e9) + 7)


signed main(){
  int a, b, d;
  while(true){
    pair<int,int> ans;
    ans.first = ans.second = INF;
    
    cin>>a>>b>>d;

    if(!a&&!b&&!d) break;

    for(int i = 0; i <= 50000; i++){
      int e, f;
      if((d + b*i)%a == 0){
	if((d + b*i)/a + i < ans.first + ans.second){
	  ans.first = (d + b*i)/a ;
	  ans.second = i;
	} else if ((d + b*i)/a + i == ans.first + ans.second){
	  if((d + b*i) + i*b < ans.first*a + ans.second*b){
	    ans.first = (d + b*i)/a ;
	    ans.second = i;
	  }
	}
      }
      if((d - b*i)%a == 0){
	if(abs(d - b*i)/a + i < ans.first + ans.second){
	  ans.first = abs(d - b*i)/a ;
	  ans.second = i;
	} else if (abs(d - b*i)/a + i == ans.first + ans.second){
	  if(abs(d - b*i) + i*b < ans.first*a + ans.second*b){
	    ans.first = abs(d - b*i)/a ;
	    ans.second = i;
	  }
	}
      }
    }

    cout<<ans.first<<" "<<ans.second<<endl;
  }
}



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

using namespace std;
using ll =long long;

#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cout << #x << " = " << (x) << endl;
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}

const ll INF = 1LL << 60;

int N,M,H,W,K,A,B;
string S;
//ここから書き始める


struct Edge {
	int to, id;
};
vector<vector<Edge>> g;
vector<int> ans;

void dfs(int v, int c=-1 , int p = -1){
	int k = 1;
	//vが今見てるとこ、頂点、cが,親から来た色,pが、親の頂点
	rep(i,g[v].size()){//繋がってる数だけ色を付けていく
		int u = g[v][i].to ;
		int ei = g[v][i].id;//
		if( u == p) continue; //親のところには作らなくていい
		if ( k == c) k++;
		ans[ei] = k ;
		k ++ ;
		dfs(u,ans[ei],v);
	}
}
	int main()
	{
		cout << setprecision(10);
		int n;
		cin >> n;

		g.resize(n);
		rep(i,n-1){
			int a, b;
			cin >> a >> b; 
			a--;b--;

			g[a].push_back((Edge){b,i});
			g[b].push_back((Edge){a,i});
		}
		ans.resize(n-1);//i本目の辺の色を入れていく
	//	rep(i,n){
	//		cout << i <<": " ;
	//		rep(j,g[i].size()){
	//			cout << g[i][j].to <<" " ;
	//		}
	//		cout << endl;
	//	}
	//	cout << endl;

		dfs(0);
		int mx = 0 ;
		rep(i,n) mx = max(mx, int(g[i].size()));
		cout << mx << endl;
		rep(i,n-1){
			cout << ans[i] << endl;
		}
	}


Measured memory_bytes: 8320
#pragma GCC optimize "03"
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define ld long double
#define pi pair<int, int>
#define pb push_back
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#ifndef LOCAL
#define endl '\n'
#endif

const int N = 3e2 + 5;
const int mod = 1e9 + 7;

int n;
ld dp[N][N][N];

ld rec(int c1, int c2, int c3){
	//cout << c1 << " " << c2 << " " << c3 << endl;
	if(c1 < 0 || c2 < 0 || c3 < 0)
		return 0;
	if(dp[c1][c2][c3] != -1)
		return dp[c1][c2][c3];
	if(c1 == 0 && c2 == 0 && c3 == 0)
		return 0;
	ld ans = c1*rec(c1-1, c2, c3) + c2*rec(c1+1, c2-1, c3) + c3*rec(c1, c2+1, c3-1) + n;
	ans /= (c1+c2+c3);
	return dp[c1][c2][c3] = ans;
}

signed main() {
	#ifdef LOCAL
		freopen("input.txt","r",stdin);
	#endif
	IOS;
	fill(&dp[0][0][0], &dp[0][0][0] + N*N*N, -1);
	cin >> n;
	int a = 0, b = 0, c = 0;
	for(int i = 1; i <= n; i++){
		int p; 	cin >> p;
		if(p == 1)	a++;
		else if(p == 2)	b++;
		else	c++;
	}
	cout << setprecision(10) << fixed << rec(a, b, c);
	return 0;
}

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

#define endl '\n'

using namespace std;

int main(){

  cin.tie(0);     // cout と cin の同期を切る
  ios::sync_with_stdio(false);  /* cの stdioストリーム (printfとか)と*/

  int N;

  int A,B;

  cin>>N>>A>>B;

  int p[101];

  int a=0,b=0,c=0;
  
  for(int i=0;i<N;i++){
    cin>>p[i];

    if(p[i]<=A){
      a++;
    }else if(p[i]>A&&p[i]<=B){
      b++;
    }else{
      c++;
    }
  }

  cout<<min(min(a,b),c)<<endl;
  
  return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <vector>

using namespace std;
using ll = long long;

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b /* % MOD */;
    if (n % 2 == 0) {
        return mypow(b * b /* % MOD */, n / 2);
    } else {
        return mypow(b, n - 1) * b /* % MOD */;
    }
}

vector<ll> primes, cubes;

// 10^5以下の素数と、10^10以下の立方数を列挙する
void precalc() {
    bool isp[100010];
    fill(isp, isp + 100010, true);

    for (ll i = 2; i * i < 1e10; ++i) {
        if (!isp[i]) continue;
        primes.push_back(i);
        for (ll j = 2; i * j <= 100000; ++j) isp[i * j] = false;
    }

    for (ll p : primes) {
        if (p * p * p > 1e10) break;
        cubes.push_back(p * p * p);
    }
}

// 標準形に変換
ll delcube(ll n) {
    for (ll c : cubes) {
        while (n % c == 0) n /= c;
    }
    return n;
}

// 標準形の補数を求める
ll anticube(ll n) {
    ll ret = 1;

    for (ll p : primes) {
        if (p * p > n) break;
        if (n % p > 0) continue;

        int c = 0;
        while (n % p == 0) {
            n /= p;
            ++c;
        }
        ret *= mypow(p, 3 - c);
    }

    // 最後に残ったnは素数か1
    // 素数なら指数は1
    ret *= mypow(n, 2);
    return ret;
}

int main() {
    precalc();

    int N;
    cin >> N;

    // 標準形をキーに、その個数を保持する
    map<ll, int> cnt;
    for (int i = 0; i < N; ++i) {
        ll s;
        cin >> s;
        s = delcube(s);
        if (cnt.count(s) == 0) cnt[s] = 0;
        ++cnt[s];
    }

    int ans = 0;
    for (auto p : cnt) {
        if (p.second == 0) continue;
        if (p.first == 1) {  // 立方数の集合は例外
            ++ans;
            continue;
        }

        ll opp = anticube(p.first);

        // 補数集合と、大きい方を選ぶ
        if (cnt.count(opp)) {
            ans += max(cnt[p.first], cnt[opp]);
            cnt[p.first] = cnt[opp] = 0;
        } else {
            ans += cnt[p.first];
        }
    }

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


Measured memory_bytes: 6656
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef pair<int, int> pi;

const int INF = 1e9;
int main() {
  int n, k;
  cin >> n >> k;
  vi x(n);
  rep(i, n) cin >> x[i];


  ll mdis = INF;

  rep(l, n-k+1){
    int r=k-1+l;
    ll dis;
    if ((x[r] <= 0 and x[l] <= 0)){
      dis = -x[l];
    }else if((x[r] >= 0 and x[l] >= 0)){
      dis = x[r];
    }else{
      dis = max(-x[l], x[r]);
      dis += 2 * min(-x[l], x[r]);
    }
    mdis = min(dis, mdis);
  }
  cout << mdis << endl;


  return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	
	Scanner sc = new Scanner(System.in);
	int[] sosuu = new int[1300000];
	public void run() {
		calcSosuu(1300000);
		while(sc.hasNext()){
			int n = sc.nextInt();
			if(n == 0) break;
			calc(n);
		}
	}
	public void calc(int n){
		int sum = 0;
		if(sosuu[n] == -1) System.out.println(0);
		else{
			for(int i = n; i < 1300000; i++){
				if(sosuu[i] == 1) sum++;
				else if(sosuu[i] == -1) break;
			}
			for(int i = n - 1; i >= 0; i--){
				if(sosuu[i] == 1) sum++;
				else if(sosuu[i] == -1) break;
			}
			System.out.println(sum + 1);
		}
	}

	public void calcSosuu(int t){
		sosuu[0] = 1;
		sosuu[1] = 1;
		for(int i = 0; i < t; i++){
			if(sosuu[i] == 0){
				sosuu[i] = -1;
				for(int j = i * 2; j < t; j = j + i){
					sosuu[j] = 1;
				}
			}
		}
	}
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 28640
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 300000 + 10;
const int maxt = maxn << 2;
 
int W, H, n;
struct point{
  int x, y;
  point() {}
  point(int _x, int _y):x(_x), y(_y) {}
   
  friend bool operator <(point a, point b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
  }
}p[maxn];
 
//sgt
int tr[maxt], lazy[maxt];
 
inline void pushup(int u) {
  int ls = u << 1, rs = u << 1 | 1;
  tr[u] = max(tr[ls],tr[rs]) + lazy[u];
}
 
void updata(int u, int l, int r, int p, int q, int k) {
  if(p <= l && r <= q) {
    tr[u] += k;
    lazy[u] += k;
    return;
  }
  int mid =(l + r) >> 1;
  if(p <= mid) updata(u << 1,l,mid,p,q,k);
  if(mid + 1 <= q) updata(u << 1 | 1,mid + 1,r,p,q,k);
  pushup(u);
}
 
int s1[maxn], s2[maxn], ans;
inline void work() {
  sort(p + 1,p + n + 1);
  memset(tr,0,sizeof(tr));
  memset(lazy,0,sizeof(lazy));
  updata(1,1,n,1,n,H);
  int t1, t2;
  t1 = t2 = 0;
  s1[t1] = s2[t2] = 1;
  for(int i = 2;i <= n;i ++) {
    updata(1,1,n,1,i - 1,(p[i].x - p[i - 1].x));
    ans = max(ans,2*tr[1]);
    if(p[i].y >=(H >> 1)) {
      updata(1,1,n,s1[t1],i - 1,(p[i].y - H));
      while(t1 && p[s1[t1]].y >= p[i].y) {
        updata(1,1,n,s1[t1 - 1],s1[t1] - 1,(p[i].y - p[s1[t1]].y));
        t1 --;
      }
      s1[++ t1] = i;
    }
    else {
      updata(1,1,n,s2[t2],i - 1,-p[i].y);
      while(t2 && p[s2[t2]].y <= p[i].y) {
        updata(1,1,n,s2[t2 - 1],s2[t2] - 1,(p[s2[t2]].y - p[i].y));
        t2 --;
      }
      s2[++ t2] = i;
    }
  }
}
 
int main() {
  scanf("%d%d%d", &W, &H, &n); n ++;
  p[1] = point(0,0); p[n + 1] = point(W,H);
  for(int i = 2;i <= n;i ++) {
    int x, y;
    scanf("%d%d", &x, &y);
    p[i] = point(x,y);
  }
  n ++;
  ans = 2 *(max(W,H) + 1);
  work();
  for(int i = 1;i <= n;i ++) swap(p[i].x,p[i].y);
  swap(W,H);
  work();
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 12800
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N,K = map(int,input().split())

P = tuple(map(lambda x: int(x)-1,input().split()))
C = tuple(map(int,input().split()))

Q = min2(N,K)

acc = [0]*N
visited = [-1]*N
last = [0]*N


res = -10**9

for p in range(N):
    c = 0
    v = P[p]
    for j in range(Q):
        if visited[v] == j:
            break
        visited[v] = j
        acc[v] = c
        c += C[v]
        last[v] = j
        v = P[v]
        res = max2(c,res)

    i = last[v]
    j += 1

    delta = c - acc[v]
    # print(i,j,delta)
    if delta > 0:
        remaining = K - i
        cycle = j-i
        if remaining < cycle:
            c = acc[v]
            for _ in range(remaining):
                c += C[v]
                res = max2(res, c)
                v = P[v]
        else:
            c = acc[v]+(remaining//cycle - 1)*delta
            remaining = cycle + remaining%cycle
            for _ in range(remaining):
                c += C[v]
                res = max2(res, c)
                v = P[v]

print(res)

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

using namespace std;

int main() {
	int n;
	cin >> n;
	int k = int(sqrt(n * 8 + 1) + 1) / 2;
	if (k*(k - 1) != n * 2) {
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes\n" << k << '\n';
	vector<pair<int, int>> a;
	vector<int> b[1000];
	for (int i = 0; i < k - 1; i++)
		for (int j = i + 1; j < k; j++)
			a.emplace_back(i, j);
	for (int i = 0; i < a.size(); i++) {
		b[a[i].first].push_back(i);
		b[a[i].second].push_back(i);
	}
	for (int i = 0; i < k; i++) {
		cout << k - 1;
		for (int j = 0; j < k - 1; j++)
			cout << ' ' << b[i][j] + 1;
		cout << '\n';
	}
	cout << flush;
	return 0;
}


Measured memory_bytes: 3060
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools
import heapq
#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)


def main():
    n=list(input())
    ans="No"
    for i in n:
        if i=="7":
            ans="Yes"
    print(ans)



if __name__ == "__main__":

    main()

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

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

using namespace std;

struct Data { int a,e,r; };
struct Obj {
  int damage,exp,cnt;
  bool operator < ( const Obj &obj) const {
    return cnt > obj.cnt;
  }
};
const int IINF = INT_MAX;
int dp[110][110];

int main(){
  int D,N;
  while(cin >> D >> N, D|N ){
    vector<Data> arr(N);
    rep(i,N) cin >> arr[i].a >> arr[i].e >> arr[i].r;
    rep(i,110) rep(j,110) dp[i][j] = IINF; 
    dp[0][0] = 0;
    priority_queue<Obj> Q;
    Q.push((Obj){0,0,0});
    bool found = false;
    while( !Q.empty() ){
      Obj obj = Q.top(); Q.pop();
      if( obj.damage == D ) { cout << obj.cnt << endl; found = true; break; }
      rep(i,N) if( obj.exp >= arr[i].r ){
        int damage = min(D,obj.damage + arr[i].a);
        int exp    = min(100,obj.exp+arr[i].e);
        int cnt    = obj.cnt + 1;
        if( dp[damage][exp] > cnt ) {
          dp[damage][exp] = cnt;
          Q.push((Obj){damage,exp,cnt});
        }
      }
    }
    if( !found ) puts("NA");
  }
  return 0;
}

Measured memory_bytes: 1312