akhauriyash/Code-Regression huggingface dataset:
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         fozubaoyou    pass System Test!
*/


//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(){
    int k,a,b;
    cin >> k;
    cin >> a >> b;
    // int x = a / k;
    // if(k == 1){
    //     cout << "OK" << endl;
    // }else if(k > b / 2 && k < a){
    //     cout << "NG" << endl;
    // }else{
    //     if(x * k + k <= b){
    //         cout << "OK" << endl;
    //     }else{
    //         cout << "NG" << endl;
    //     }
    // }
    int n = 1000 / k;
    int s = 0;
    REP(i,n){
        if(k * (i + 1) >= a && k * (i + 1) <= b){
            cout << "OK" << endl;
            s = 1;
            break;
        }
    }
    if(s == 0) cout << "NG" << endl;
    return 0;
}


Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();

        if ( b - a == c - b) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}


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

int main()
{
    string s,t;

    cin>>s;
    cin>>t;
    int LCS[s.length()+1][t.length()+1];

    for(int i=0;i<=s.length();i++)
        for(int j=0;j<=t.length();j++)
    {
        if(i==0 || j==0)
            LCS[i][j] = 0;
        else
        {
            if(s[i-1] == t[j-1])
                LCS[i][j] = 1 + LCS[i-1][j-1];
            else
                LCS[i][j] = max(LCS[i-1][j],LCS[i][j-1]);
        }
    }
    int i = s.length();
    int j = t.length();
    string ans = "";
    while(i>0 && j>0)
    {
        if(s[i-1] == t[j-1])
        {
            ans+=s[i-1];
            i--;
            j--;
        }
        else if(LCS[i-1][j]>LCS[i][j-1])
            i--;
        else
            j--;
    }
    
    if(ans.length() == 0)
        cout<<" ";
    else
    for(int i=ans.length()-1;i>=0;i--)
        cout<<ans[i];
    return 0;
}


Measured memory_bytes: 35456
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iterator>
using namespace std;

/*
const int MAX_E=2*(100-1);
const int MAX_V=100;
const long long int INF=100000000;
struct edge { int from,to,cost;};
edge es[MAX_E];
//int d[MAX_V];
int V,E;
void shortest_path(int s,int e,vector<int>& d);
int main(){
	int n,k;
	while(cin >> n >> k&&n!=0&&k!=0){
		int V=n;
		int E=2*(n-1);
		vector<int> land(V);
		int l=0;
		for(int i=0; i<E; ++i){
			es[i].cost=-1;
			es[i].from=-1;
			es[i].to=-1;
		}
		for(int i=0; i<k; ++k){
			int m;
			cin >> m;
			if(m==0){
				int a,b;
				cin >> a >> b;
				shortest_path(a,b,land);
				cout << land[b] << "\n";
			} else if(m==1){
				int c,d,e;
				cin >> c >> d >> e;
				es[l].from=c;
				es[l].to=d;
				es[l].cost=e;
				es[l+1].from=d;
				es[l+1].to=c;
				es[l+1].cost=e;
				l+=2;
			}
		}
	}
	return 0;
}
*/

int main(){
	int n;
	cin >> n;
	map<string,int> names;
	for(int i=0; i<n; ++i){
		int a;
		string b;
		cin >> b >> a;
		names[b]+=a;
	}
	for(int i=1; i<=5; ++i){
		for(map<string,int>::iterator itpairstri=names.begin(); itpairstri!=names.end(); ++itpairstri){
			if(i==itpairstri->first.size())cout << itpairstri->first << " " << itpairstri->second << "\n";
		}
	}
	return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF 1145141919364364
#define int long long
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n, a[100];
bool ans = true;

signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if ((!(a[i] % 2)) && (a[i] % 3) && (a[i] % 5))ans = false;
	}
	if (ans)cout << "APPROVED" << endl;
	else cout << "DENIED" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  int m,n,l,t;
  
  while(scanf("%d %d",&m,&n)!=EOF)
    {
      l=1;
      if(m<n)
	{
	  t=m;
	  m=n;
	  n=t;
}
      while(l!=0)
	{
	  l=m%n;
	  m=n;
	  n=l;
	}
      printf("%d\n",m);
    }
  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<queue>	
#include<functional>
#include<climits>
#include<tuple>

using namespace std;

//define
#define ALL(a) a.begin(),a.end()
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define debug(x) if(1)cout<<#x<<":"<<x<<endl;
#define DEBUG(x) if(1)cout<<#x<<":"<<x<<endl;
#define ll long long
#define pb push_back
#define PB push_back
#define lb lower_bound
#define LB lower_bound
#define ub upper_bound
#define UB upper_bound


//constant
const int MOD = 1000000007;
const int INF = INT_MAX / 2-1;
const double EPS = 1e-9;
const int dx4[4] = { 1,0,-1,0 };
const int dy4[4] = { 0,1,0,-1 };

//typedef
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;


int main() {
	ll n;
	ll x;
	cin >> n >> x;
	ll res = n;
	ll a = n - x, b = x;
	for (;;) {
		if (a%b == 0) {
			res += (2 * (a / b ) -1)*b;
			break;
		}
		res += (2 * (a / b))*b;
		ll t;
		t = b;
		b = a%b;
		a=t;

	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
// Ryo Kamoi

#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>

using namespace std;

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

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

int INF = 1000000000;

int n, k;
string s;
int main(){
  cin >> n >> k;
  cin >> s;

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

  cout << s << endl;
}


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

int main()
{
	int N, Z, W, S = 0;
	vector<int>v;
	cin >> N >> Z >> W;

	for (int i = 0; i < N; i++)
	{
		int t;
		cin >> t;
		v.push_back(t);
	}
	
	if (N == 1)
	{
		cout << abs(W - v[0]) << endl;
		return 0;
	}
	cout << max(abs(W-v[N-1]),abs(v[N-2]-v[N-1])) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repv(i,a,b) for(ll i=b-1;i>=a;i--)
#define MAXN 300005
#define endl "\n"

ll n,a,b;
vector<pair<ll,ll> > v;

ll gcd(ll a,ll b){if(b==0) return a; else return gcd(b,a%b);}
ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=res*x;y=y>>1;x=x*x;}return res;}

bool trick(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
    if(a.ss<b.ss) return true;
    else if(a.ss>b.ss) return false;
    else return a.ff>b.ff;
}

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(ll i=0;i<n;i++)
    {
        cin>>a>>b;
        v.pb(mp(a,b));
    }
    sort(v.begin(),v.end(),trick);
    ll sum=0,flag=0;
    for(ll i=0;i<v.size();i++)
    {
        sum+=v[i].ff;
        if(sum>v[i].ss)
        {
            flag=1;
            break;
        }
    }
    if(flag==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 6384
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()
#define MOD 1000000007

int main() {
	int N, C, K;
	cin >> N >> K >> C;
	string S;
	cin >> S;
	
	vector<int> op = { -MOD };
	for (int i = 0;i < N;i++) {
		if (S[i] == 'o')op.push_back(i);
	}
	op.push_back(MOD);
	int ops = op.size();
	vector<int> R(N, 0), L(N, 0), RR(N, 0), LR(N, 0);
	for (int i = 0;i < N;i++) {
		if (S[i] == 'x')continue;
		auto it = upper_bound(all(op), i + C);
		R[i] = *it;
		it = lower_bound(all(op), i - C);
		it--;
		L[i] = *it;
	}

	for (int i = 0;i < N;i++) {
		if (S[i] == 'x')continue;
		if (L[i] == -MOD) {
			LR[i] = 1;
		}
		else {
			LR[i] = LR[L[i]] + 1;
		}
	}

	for (int i = N - 1;i >= 0;i--) {
		if (S[i] == 'x')continue;
		if (R[i] == MOD) {
			RR[i] = 1;
		}
		else {
			RR[i] = RR[R[i]] + 1;
		}
	}

	int cnt = 0;
	for (int i = 0;i < N;i++) {
		if (S[i] == 'x')continue;
		cnt = 0;
		auto it = upper_bound(all(op), i);
		if (*it != MOD)cnt += RR[*it];
		it = lower_bound(all(op), i);
		it--;
		if (*it != -MOD)cnt += LR[*it];

		if (cnt < K)cout << i + 1 << endl;
	}
}

Measured memory_bytes: 5752
#include <stdio.h>
#include <limits.h>

/** Application main entry point. */
int main (
  int     argc,
  char  * argv[ ]
  )
{
  int i;

  for ( ; ; )
  {
    unsigned char ttbl[ UCHAR_MAX + 1 ];
    unsigned char from, to;
    int n;

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

    for ( i = 0; i <= UCHAR_MAX; ++i )
    {
      ttbl[ i ] = i;
    }
    for ( i = 0; i < n; ++i )
    {
      scanf ( " %c %c", &from, &to );
      ttbl[ from ] = to;
    }
    
    scanf ( " %d", &n );
    for ( i = 0; i < n; ++i )
    {
      scanf ( " %c", &from );
      putchar ( ttbl[ from ] );
    }
    puts ( "" );
  }

  return ( 0 );
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main() {
    int r,g,b,n,ans=0;
    cin>>r>>g>>b>>n;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++) {
            int tmp=n-r*i-g*j;
            if(tmp>=0 &&tmp%b==0)ans++;
        }
    }
    cout<<ans<<endl;
}


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

int main(void)
{
    int n;
    cin >> n;
    string s[n];
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    int ac = 0;
    int wa = 0;
    int tle = 0;
    int re = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == "AC")
        {
            ac++;
        }
        else if (s[i] == "WA")
        {
            wa++;
        }
        else if (s[i] == "TLE")
        {
            tle++;
        }
        else
        {
            re++;
        }
    }
    cout << "AC x " << ac << endl;
    cout << "WA x " << wa << endl;
    cout << "TLE x " << tle << endl;
    cout << "RE x " << re << endl;
    return 0;
}


Measured memory_bytes: 6712
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>

using namespace std;

#define ll long long
#define ld long double
#define v vector

#define rep(i, n)      for (int i = 0; i < (int)(n); ++i)
#define rep3(i, m, n)  for (int i = (m); i < (int)(n); ++i)
#define rrep(i, n)     for (int i = (int)(n)-1; i >= 0; --i)
#define rrep3(i, m, n) for (int i = (int)(n)-1; i >= (m); --i)
#define all(x) begin(x), end(x)
#define rall(x) end(x), begin(x)

#define endl '\n'
const string YES = "Yes";
const string NO = "No";

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

bool solve(ll X, ll Y) {
  Y -= X;
  Y -= X;
  if (Y < 0) return false;
  if (Y%2 != 0) return false;
  if (Y/2 <= X) return true;
  else return false;
}

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

  ll X, Y;
  cin >> X >> Y;

  auto ans = solve(X, Y);
  cout << (ans ? YES : NO) << endl;

  return 0;
}


Measured memory_bytes: 3104
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};

int main(){

    string s;
    cin >> s;

    bool all_flg = false;

    for(int i=0; i<s.size(); i++){
        int sum = 0;
        char tmp_s = s[i];
        bool flg = false;
        for(int j=0; j<s.size(); j++){
            if(s[j] == tmp_s) sum += 1;
        }

        if(sum % 2 == 0) flg = true;
        else flg = false;

        if(flg) all_flg = true;
        else{
            all_flg = false;
            break;
        }
    }

    if(all_flg) cout << "Yes" << endl;
    else cout << "No" << endl;


}

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

int main(){
  int h, w;
  cin >> h >> w;
  vector<vector<char>> table(h, vector<char>(w));
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> table[i][j];
    }
  }
  vector<bool> row(h, false);
  vector<bool> col(w, false);
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (table[i][j] == '#') {
				row[i] = true;
				col[j] = true;
			}
		}
	}
  for(int i=0;i<h;i++){
    if(row[i]){
      for(int j=0;j<w;j++){
        if(col[j]){
          cout << table[i][j];
        }
      }
      cout << endl;
    }
  }
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
	public void solve() {
		String s = next();
		int K = nextInt();

		char[] c = s.toCharArray();
		int N = c.length;
		for(int i = 0;i < N;i++){
			char tmp = c[i];
			int k = 0;
			while(c[i] != 'a'){
				c[i] = c[i] + 1 > 'z' ? 'a' : (char)(c[i] + 1);
				k++;
			}

			if(k <= K){
				K -= k;
			}else{
				c[i] = tmp;
			}
		}

		if(K >= 1){
			c[N - 1] = (char)((c[N - 1]) + K % 26);
		}

		out.println(String.valueOf(c));
	}

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

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 10708
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf=1e9+7;
int main(){
    int n;cin>>n;
    vector<int> b(n),k(0);
    bool f=false;
    rep(i,n)cin>>b[i];
    while(n){
        int a=0;
        f=false;
        for(int i=n-1;i>=0;i--){
            if(i+1==b[i]){
                k.push_back(b[i]);
                f=true;
              b[i]=a;
                break;
            }
            int t=b[i];
            b[i]=a;
            a=t;
        }
        if(f){
            n--;
            continue;
        }else{
            break;
        }
    }
    if(f){
        for(int i=k.size()-1;i>=0;i--){
            cout<<k[i]<<endl;
        }
    }else{
        cout<<-1<<endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#define rep(i,n) for (int i = 0; i < (n); ++i) 
#define MAX 100000
#define SENTINEL 2000000000
typedef long long ll;
using namespace std;

struct Card { char suit; int num; };

Card L[MAX/2 + 2], R[MAX/2 + 2];

int partition(Card A[], int p, int r)
{
    int x = A[r].num;
    int i = p - 1;

    for (int j = p; j < r; ++j){
        if(A[j].num <= x){
            ++i;
            Card t = A[i]; A[i] = A[j]; A[j] = t;
        }
    }
    Card t = A[i+1]; A[i+1] = A[r]; A[r] = t;

    return i+1;
}

void quickSort(Card A[], int p, int r)
{
    if(p < r){
        int pivot = partition(A, p, r);
        quickSort(A, p, pivot-1);
        quickSort(A, pivot, r);
    }
}

void merge(Card B[], int left, int mid, int right)
{
    int n1 = mid - left;
    int n2 = right - mid;
    rep(i, n1) L[i] = B[left+i];
    rep(i, n2) R[i] = B[mid+i];
    L[n1].num = R[n2].num = SENTINEL;

    int i = 0;
    int j = 0;
    for(int k = left; k < right; ++k){
        if(L[i].num <= R[j].num) B[k] = L[i++];
        else B[k] = R[j++];
    }
}

void mergeSort(Card B[], int left, int right)
{
    if(left + 1 < right){
        int mid = (left + right) / 2;
        mergeSort(B, left, mid);
        mergeSort(B, mid, right);
        merge(B, left, mid, right);
    }
}


int main()
{
    int n;
    Card A[MAX], B[MAX];
    cin >> n;
    rep(i, n) cin >> A[i].suit >> A[i].num;
    rep(i, n) {
        B[i] = A[i];
    }

    quickSort(A, 0, n-1);
    mergeSort(B, 0, n);

    bool stable = 1;
    rep(i, n){
        if(A[i].suit != B[i].suit) stable = 0;
    }
    if (stable) puts("Stable");
    else puts("Not stable");

    rep(i, n){
        cout << A[i].suit << " " << A[i].num << endl;
    }

    return 0;
}


Measured memory_bytes: 5448
#include<stdlib.h> 
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
#include <string>
using namespace std;

void merge(int arr[], int l, int m, int r) 
{ 
  int i, j, k; 
  int n1 = m - l + 1; 
  int n2 =  r - m; 
  
  /* create temp arrays */
  int L[n1], R[n2]; 
  
  /* Copy data to temp arrays L[] and R[] */
  for (i = 0; i < n1; i++) 
    L[i] = arr[l + i]; 
  for (j = 0; j < n2; j++) 
    R[j] = arr[m + 1+ j]; 
  
  /* Merge the temp arrays back into arr[l..r]*/
  i = 0; // Initial index of first subarray 
  j = 0; // Initial index of second subarray 
  k = l; // Initial index of merged subarray 
  while (i < n1 && j < n2) 
    { 
      if (L[i] <= R[j]) 
        { 
	  arr[k] = L[i]; 
	  i++; 
        } 
      else
        { 
	  arr[k] = R[j]; 
	  j++; 
        } 
      k++; 
    } 
  /* Copy the remaining elements of L[], if there 
     are any */
  while (i < n1) 
    { 
      arr[k] = L[i]; 
      i++; 
      k++; 
    } 
  /* Copy the remaining elements of R[], if there 
     are any */
  while (j < n2) 
    { 
      arr[k] = R[j]; 
      j++; 
      k++; 
    } 
}

void mergeSort(int arr[], int l, int r) 
{ 
  if (l < r) 
    { 
      // Same as (l+r)/2, but avoids overflow for 
      // large l and h 
      int m = l+(r-l)/2; 
  
      // Sort first and second halves 
      mergeSort(arr, l, m); 
      mergeSort(arr, m+1, r); 
  
      merge(arr, l, m, r); 
    } 
}  

int main(){
  int N;
  int x;
  cin >> N >> x;
  int a[N];
  for(int i=0;i<N;i++){
    cin >> a[i];
  }
  
  mergeSort(a,0,N-1);

  int sum=0;
  for(int i=0;i<N;i++){
    sum +=a[i];
    if (sum > x){
      cout << i <<endl;
      return 0;
    }
  }
  if (sum == x){
    cout << N << endl;
  }
  else cout << N-1 << endl;
  return 0;
}


Measured memory_bytes: 256
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

dp = [0 for i in range(N+1)]
dp[0] = 1
dp[1] = 1

for i in range(2,N+1):
    dp[i] = dp[i-1] + dp[i-2]

ans = 1
a = -1
for i in range(M):
    b = int(input())
    c = b - a - 2
    if c < 0:
        print (0)
        sys.exit()
    else:
        ans = (ans * dp[c]) % mod
        a = b

ans = (ans * dp[N-a-1]) % mod

print(ans)

Measured memory_bytes: 522316
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
int main(void){
    long long h,w,n,d=1000000000,c[10]={0};
    unordered_map<long long,int> m{};
    cin>>h>>w>>n;
    for(int i=0;i<n;i++){
        long long a,b;
        cin>>a>>b;
        a--;
        b--;
        for(int j=-1;j<=1;j++){
            for(int k=-1;k<=1;k++){
                if(a+j>=0&&a+j<h&&b+k>=0&&b+k<w){
                    m[(a+j)*d+b+k]++;
                    //cout<<a+j<<","<<b+k<<":"<<m[(a+j)*d+b+k]<<endl;
                }
            }
        }
        
    }
    for(auto x=m.begin();x!=m.end();x++){
        long long a=(x->first)/d,b=(x->first)%d;
        if(a>=1&&a<=h-2&&b>=1&&b<=w-2){
            c[x->second]++;
            c[0]++;
        }
    }
    cout<<(h-2)*(w-2)-c[0]<<endl;
    for(int i=1;i<=9;i++){
        cout<<c[i]<<endl;
    }
}


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

using namespace std;

int main(void) {
  int a, b, c, d;
  cin >> a >> b >> c >> d;

  int l = a + b, r = c + d;
  if (l > r) {
    cout << "Left\n";
  } else if (l < r) {
    cout << "Right\n";
  } else {
    cout << "Balanced\n";
  }

  return 0;
}

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

int main(){
    string s;
    cin >> s;
    for(int i=0;i<4;i++)cout << s[i];
    cout << " ";
    for(int i=4;i<12;i++)cout << s[i];
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <iomanip> 

using ll = long long;
using ull = unsigned long long;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;(i) < ((int)(n));++(i))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

// const int dx[4] = { 1, 0, -1, 0 };
// const int dy[4] = { 0, 1, 0, -1 };

const int dx[8] = {1, 1, 0,-1,-1,-1, 0, 1};
const int dy[8] = {0, 1, 1, 1, 0,-1,-1,-1};

int inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;} // 桁数
template<typename T>inline T SUM(vector<T> vec){return accumulate(all(vec),(T)0);} // vectorの中身を全部足す
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);} // 最大公約数
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;} // 最小公倍数
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;} // 累乗
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T>inline void print(T&& x){cout<<setprecision(32)<<x<<endl;}

// TODO: write
int main() {
  int n;cin>>n;
  vector<pair<int,pair<int,int>>> a(n);
  rep(i,n){
    int l,r;cin>>l>>r;
    a[i].fi = l+r;
    a[i].se.fi = l;
    a[i].se.se = r;
  }
  sort(all(a),[](auto l,auto r){return l.fi > r.fi;});
  ll l = 0,r = 0;
  rep(i,n){
    if(i%2){
      r += a[i].second.second;
    }else{
      l += a[i].second.first;
    }
  }
  print(l-r);
  return 0;
}

Measured memory_bytes: 4584
#include<iostream>
using namespace std;
#define int long long int
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int x;
	cin>>x;
	for(int y=1;y<=360;y++)
	{
		if((x*y)%360==0)
		{
			cout<<y<<endl;
			exit(0);
		}
	}
}


Measured memory_bytes: 3608
w,h,n = map(int, input().split())
b = [[0]*(w+1) for _ in range(h+1)]

for _ in range(n):
    x,y,a = map(int, input().split())
    if a <= 2:
        f = 0 if a == 1 else x
        t = x if a == 1 else w
        b[0][f] += 1
        b[0][t] -= 1
    else:
        f = 0 if a == 3 else y
        t = y if a == 3 else h
        b[f][0] += 1
        b[t][0] -= 1

ans = 0
for i in range(w):
    for j in range(h):
        b[j+1][i] += b[j][i]
for j in range(h):
    for i in range(w):
        b[j][i+1] += b[j][i]
        if b[j][i] == 0:
            ans += 1
print(ans)


Measured memory_bytes: 3064
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        long a = Long.parseLong(scanner.next());
        long b = Long.parseLong(scanner.next());
        scanner.close();
        long count = 0;
        long sum = (b - a + 1) / 2;

        if((b - a + 1) % 2 != 0) sum += a % 2;
        if(sum % 2 != 0) count += 1;
        for (long i = 2; i < b*2; i *= 2) {
            long c = 0;
            long r1 = a % (i * 2);
            if(r1 >= i) c += (i*2) - r1;
            long r2 = b % (i * 2);
            if(r2 >= i) c += r2 - (i * 2 - 1);
            if(c % 2 != 0){
                count += i;
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 21972
#include <iostream>

using namespace std;

long long int euclid(long long int C, long long int D) {
    long long int dst;
    long long int a, b;

    if(C > D) {
        dst = C;
        C = D;
        D = dst;
    }

    while(C != 0) {
        a = C;
        b = D % C;
        D = a;
        C = b;
    }

    return D;

}

int main() {
    long long int A, B, C, D;
    cin >> A;
    cin >> B;
    cin >> C;
    cin >> D;
    long long int count = 0;
    long long int g, l;

    count = B - A + 1;
    if(A % C == 0) {
        count -= - A / C + B / C + 1;
    } else {
        count -= - A / C + B / C;        
    }
    if(A % D == 0) {
        count -= - A / D + B / D + 1;
    } else {
        count -= - A / D + B / D;        
    }
    
    g = euclid(C, D);

    l = C * D / g;

    if(A % l == 0) {
        count += - A / l + B / l + 1;
    } else {
        count += - A / l + B / l;        
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define pr1(a) (#a)<<"="<<(a)
#define pr2(a,b) pr1(a)<<", "<<pr1(b)
#define pr3(a,b,c) pr2(a,b)<<", "<<pr1(c)
#define pr4(a,b,c,d) pr3(a,b,c)<<", "<<pr1(d)
#define pr5(a,b,c,d,e) pr4(a,b,c,d)<<", "<<pr1(e)
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}

int n;
vector<int> A;
int used[N],mem[N];

int dfs(int idx){
  if(idx == (int)A.size()) return 0;
  if(used[idx]++) return mem[idx];
  return mem[idx] = abs(A[idx] - A[idx+1]) + dfs(idx+1);
}

signed main(){
  cin>>n;
  A.resize(n);
  cin>>A;
  A.push_back(0);
  A.insert(A.begin(),0);
  int cost = 0;
  for(int i=1;i<=n;i++){
    int ans = abs(A[i-1] - A[i+1]) + dfs(i+1) + cost;
    cout<<ans<<endl;
    if(i != n) cost += abs(A[i-1] - A[i]);
    
  }
  
  return 0;
}


Measured memory_bytes: 6640
/*..........AAKASH GOYAL............*/
/*............DAIICT................*/
 
#include <bits/stdc++.h>
using namespace std;

#define    int                      long long int

#define    f(i,j,n)                 for(int i = j; i <= n; i++)
#define    r(i,n,j)                 for(int i = n; i >= j; i--)
#define    mod                      1000000007
#define    speed                    ios_base::sync_with_stdio(false);
#define    upp                      cin.tie(NULL);
#define    pb                       push_back
#define    mp                       make_pair
#define    T                        int tt; cin >> tt; while(tt--)
#define    ff                       first
#define    ss                       second
#define    all(container)           container.begin() , container.end()
#define    sz(container)            (int)container.size()
#define    pii                      pair <int , int>
#define    ppi                      pair <int , pii>               
#define    sp(x)                    setprecision(x)

int32_t main()
{
    speed upp
    int n,ff=1;
    string s;
    cin>>s;
    n=sz(s);
    int j=n-1;
    f(i,0,n-1)
    {
        if(s[i]!=s[j])
            ff=0;
        j--;
    }
    j=(n-1)/2 -1;
    f(i,0,(n-1)/2 -1)
    {
        if(s[i]!=s[j])
            ff=0;
        j--;
    }
    j=n-1;
    f(i,(n+3)/2 -1,n-1)
    {
        if(s[i]!=s[j])
            ff=0;
        j--;
    }
    if(ff)
        cout<<"Yes";
    else
        cout<<"No";
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int M = sc.nextInt();
		int maxL = 0;
		int minR = 100000;
		for (int i = 0; i < M; i++) {
			int L = sc.nextInt();
			if (L > maxL) {
				maxL = L;
			}
			int R = sc.nextInt();
			if (R < minR) {
				minR = R;
			}
		}
		int ans = 0;
		if (minR >= maxL) {
			ans = minR - maxL + 1;
		}
		System.out.println(ans);		
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

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

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

    int ans = 0;

    rep(i, t.length()) {
        if (t[i] == '?') {
            t[i] = 'D';
        }
    }
    rep(i, t.length()) {
        cout << t[i];
    }

    return 0;
}

Measured memory_bytes: 3752
from sys import stdin


def main():
    A, B, C, K = [int(x) for x in stdin.readline().rstrip().split()]
    a = min(A, K)
    b = min(B, K - a)
    c = min(C, K - a - b)
    print(a - c)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9168
import std.stdio;

immutable int NA = -1;

long solve (int n)
{
	auto a = new int [n];
	foreach (ref c; a)
	{
		readf (" %s", &c);
	}
	a ~= NA;
	if (a[0] > 0)
	{
		return NA;
	}
	long res = 0;
	foreach_reverse (i; 0..n - 1)
	{
		if (a[i + 1] > a[i] + 1)
		{
			return NA;
		}
		else if (a[i + 2] != a[i + 1] + 1)
		{
			res += a[i + 1];
		}
	}
	return res;
}

void main ()
{
	int n;
	while (readf (" %s", &n) > 0)
	{
		writeln (solve (n));
	}
}


Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
//T+N
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

signed main() {
    //ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    string a;
    cin >> a;
    k --;
    if(a[k] >= 'A' && a[k] <= 'Z') {
        a[k] = (a[k] - 'A') + 'a';
    }
    cout << a << endl;
    return 0;
}




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

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


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

from math import *
from decimal import Decimal

N = int(input())
T, A = 1, 1

for i in range(N):
	t, a = list(map(int, input().split()))
	n = Decimal(max(ceil(T / t), ceil(A / a)))
	T = n * t
	A = n * a

print(T + A)



Measured memory_bytes: 5076
import sys
sys.setrecursionlimit(100001)

def dfs(node,w):
  weight = w
  for l in tree[node]:
    if color[l[0]] > -1:
      continue
    if l[1]%2 == 0:
      color[l[0]] = color[node]
    else:
      color[l[0]] = int(not color[node])
    dfs(l[0],l[1])
    


N = int(input())
tree = {}
color = [-1]*(N+1)

for i in range(1,N+1):
  tree[i] = []
for i in range(N-1):
  u,v,w = map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
  
color[1] = 0
dfs(1,0)
color = [c  if c>-1 else 0 for c in color]
print('\n'.join(map(str,color[1:])))

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

int main()
{
  int n;
  cin>>n;
  int A[n];
  int count =0;
  for(int i=0;i<n;i++)
    cin>>A[i];

  for(int i=0;i<n;i++)
    for(int j=n-1;j>i;j--)
      {
	if(A[j]<A[j-1])
	  {
	    swap(A[j],A[j-1]);
	    count++;
	  }
      }
   for(int i=0;i<n;i++)
     {
       cout<<A[i];
       if(i==n-1)
	 cout<<endl;
       else
	 cout<<" ";
     }
   cout<<count<<endl;
}

Measured memory_bytes: 1164
#include<stdio.h>
int main()
{
  int i,j,N,A[100],x,n=0,minj;

  scanf("%d",&N);
  for(i=0;i<N;i++)
    {
      scanf("%d",&A[i]);
    }

  for(i=0;i<=N-1;i++)
    {
      minj=i;
      for(j=i;j<=N-1;j++)
	{
	  if(A[j]<A[minj])
	    {
	      minj=j;
	            	    }
	}

      x=A[i];
      A[i]=A[minj];
      A[minj]=x;
      if(A[i]<A[minj]) n++;

    }
  for(i=0;i<N-1;i++)
    {
      printf("%d ",A[i]);
    }
  printf("%d\n%d\n",A[N-1],n);

  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define fi first
#define se second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using v_bool = vector<bool>;
using v_Pii = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;



signed main(){

    int T; cin >> T;
    REP(_, T){
        int N; cin >> N;
        vec A(N); cin >> A;
        string S; cin >> S;

        vec v(60, -1);
        bool ans = true;
        IREP(i, N){

            int a = A[i];
            int k0 = -1;
            REP(k, 60){
                if((a >> k) & 1){
                    if(v[k] == -1){
                        k0 = k;
                        break;
                    }else{
                        a ^= v[k];
                    }
                }
            }
            if(k0 == -1) continue;
            if(S[i] == '0') v[k0] = a;
            else{
                ans = false;
                break;
            }
        }
        Ans(ans, 0, 1);
    }

    return 0;
}


Measured memory_bytes: 3620
N = int(input())
A = list(map(int, input().split()))

Abs_A = list(map(abs, A))
sum_Abs = sum(Abs_A)
count = 0

for i in range(N):
    if A[i] < 0:
        count += 1

if count % 2 == 0:
        print(sum_Abs)
else:
        print(sum_Abs - min(Abs_A) * 2)


Measured memory_bytes: 14412
/* ex4_1 melo */
#include <stdio.h>
int main(void){
    int Num,Watchman,Min_WM;
    scanf("%d %d",&Num,&Watchman);
    Min_WM=((Num+(2*Watchman+1)-1) / (2*Watchman+1));
    printf("%d\n",Min_WM);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int n,a[3][3],b[3][3];
int main()
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			cin>>a[i][j];
	cin>>n;
	for(int ii=0;ii<n;ii++)
	{
		int num;
		cin>>num;
		for(int i=0;i<3;i++)
			for(int j=0;j<3;j++)
				if (a[i][j]==num)
					b[i][j]=1;
	}
	for(int i=0;i<3;i++)
	{
		if (b[i][0]&&b[i][1]&&b[i][2])
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	for(int j=0;j<3;j++)
		if (b[0][j]&&b[1][j]&&b[2][j])
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	if (b[0][0]&&b[1][1]&&b[2][2])
		{
			cout<<"Yes"<<endl;
			return 0;
		}	
	if (b[0][2]&&b[1][1]&&b[2][0])
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	cout<<"No"<<endl;
	return 0;	
} 

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional> // greater など
#include <cmath>      // abs など
#include <numeric>    // accumulate, gcd など
#include <cassert>    // assert
#include <stdexcept>
#include <bitset>
using namespace std;

// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
// typedef int128_t ll;
// typedef cpp_int ll;

// GCC, 配列のアクセスなど
#define _GLIBCXX_DEBUG
// Clang, 配列のアクセスなど
#define _LIBCPP_DEBUG 0

//////////////// //////////////// //////////////// //////////////// ////////////////
//////////////// //////////////// //////////////// //////////////// ////////////////

// constexpr inline ll mod = 1'000'000'007;
// constexpr int max_n = 200'000 + 5;

int main()
{
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(15); // 浮動小数の表示の精度

    int n,m; cin>>n>>m;
    cout << n * (n - 1) / 2 + m * (m - 1) / 2 << endl;

    return 0;
}


Measured memory_bytes: 3640
n, m = map(int, input().split())
h = list(map(int, input().split()))
l = [1] * n
for i in range(m):
    a, b = map(int, input().split())
    if h[a - 1] < h[b - 1] and l[b - 1] != 0:
        l[b - 1] += 1
        l[a - 1] = 0
    elif h[a - 1] > h[b - 1] and l[a - 1] != 0:
        l[a - 1] += 1
        l[b - 1] = 0
    else:
        l[a - 1] = 0
        l[b - 1] = 0
c = 0        
for i in range(n):
    if l[i] != 0:
        c += 1
print(c)

Measured memory_bytes: 19972
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())

cost = [0,2,5,5,4,5,6,3,7,6]
A =list(map(int, input().split()))
dp = [-1]*(N+1)
dp[0] = 0

for i in range(N):
    if dp[i] == -1:
        continue
    for c,a in zip( [cost[a] for a in A], A):
        if i + c <= N:
            dp[i+c] = dp[i]+1

# print(dp)
i = N
ans = ""
A = sorted(A, reverse=True)
while i > 0:
    for c,a in zip([cost[a] for a in A], A):
        if i-c >= 0 and dp[i-c] == dp[i]-1:
            ans += str(a)
            i -= c
            break # difficult !! 

print(ans)
        


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

bool solve(int64_t m, int64_t k, vector<pair<int64_t, int>> &vaff) {
    int i = 0;
    int64_t training = 0;
    while (-vaff[i].first > m) {
        training += ((-vaff[i].first - m) + (vaff[i].second - 1)) / vaff[i].second;
        if (training > k) {
            return false;
        }
        i++;
    }
    return true;
}

int main() {
    int n;
    int64_t k;
    cin >> n >> k;
    vector<int> va;
    vector<int> vf;
    vector<pair<int64_t, int>> vaff;
    rep(i,n) {
        int a;
        cin >> a;
        va.push_back(a);
    }
    rep(i,n) {
        int f;
        cin >> f;
        vf.push_back(f);
    }
    sort(va.begin(), va.end());
    sort(vf.begin(), vf.end(), greater<int>());
    rep(i,n) {
        int64_t af = (int64_t)va[i] * vf[i];
        vaff.push_back(make_pair(-af, vf[i]));
    }
    sort(vaff.begin(), vaff.end());
    //めぐる式二分探索
    int64_t ok = -vaff[0].first; //解が存在する値
    int64_t ng = -1;    //解が存在しない値
    while (abs(ok - ng) > 1) {
        int64_t mid = (ok + ng) / 2;
        if (solve(mid, k, vaff)) {
            ok = mid;
        }
        else {
            ng = mid;
        }
    }
    cout << ok << endl;
}

Measured memory_bytes: 8048
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

sx, sy, tx, ty = map(int, input().split())

ans = []

for i in range(tx - sx):
    ans.append("R")

for i in range(ty - sy):
    ans.append("U")

for i in range(tx - sx):
    ans.append("L")

for i in range(ty - sy):
    ans.append("D")

ans.append("D")

for i in range(tx - sx + 1):
    ans.append("R")

for i in range(ty - sy + 1):
    ans.append("U")

ans.append("L")

ans.append("U")

for i in range(tx - sx + 1):
    ans.append("L")

for i in range(ty - sy + 1):
    ans.append("D")

ans.append("R")

print("".join(ans))

Measured memory_bytes: 40176