Submission #59362

# Submission time Handle Problem Language Result Execution time Memory
59362 2018-07-21T19:15:13 Z Benq cmp (balkan11_cmp) C++11
100 / 100
2413 ms 83120 KB
#include "cmp.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

/*int tmp[10240];

void bit_set(int x) { tmp[x] = 1; }
int bit_get(int x) { return tmp[x]; }*/

void SET(int x) { bit_set(x+1); }
int GET(int x) { return bit_get(x+1); }

int sub(int n, int l, int r) {
	l = 11-l;

	int ans = 0;
	F0R(i,r) {
		ans *= 2;
		if (n&(1<<l)) ans ++;
		l --;
	}

	return ans;
}

void remember(int n) {
    // cout << "AH"
	SET(sub(n,0,6)); // first 6
	SET(64+sub(n,0,3)); // first 3
	SET(128+sub(n,6,3));
	SET(192+sub(n,9,3));
}

int compare(int b) {
	if (!GET(sub(b,0,6))) { // first 6 not equal
		int t = sub(b,0,3);
		if (!GET(64+t)) { // first 3 not equal
			if (t <= 3) {
				for (t-- ; t >= 0; t--) if (GET(64+t)) return 1;
				return -1;
			} else {
				for (t++; t <= 7; t++) if (GET(64+t)) return -1;
				return 1;
			}
		} else { 
			int t2 = sub(b,3,3);
			if (t2 <= 3) {
				for (t2 --; t2 >= 0; t2--) if (GET(8*t+t2)) return 1;
				return -1;
			} else {
				for (t2 ++; t2 <= 7; t2++) if (GET(8*t+t2)) return -1;
				return 1;
			}
		}
	} else {
	    // cout << "HI\n";
		int t = sub(b,6,3);
		if (!GET(128+t)) {
			if (t <= 3) {
				for (t --; t >= 0; t--) if (GET(128+t)) return 1;
				return -1;
			} else {
				for (t ++; t <= 7; t ++) if (GET(128+t)) return -1;
				return 1;
			}
		} else {
			int t2 = sub(b,9,3);
			if (GET(192+t2)) return 0;
			if (t2 <= 3) {
				for (t2 --; t2 >= 0; t2--) if (GET(192+t2)) return 1;
				return -1;
			} else {
				for (t2 ++; t2 <= 7; t2++) if (GET(192+t2)) return -1;
				return 1;
			}
		}
	}
}
# Verdict Execution time Memory Grader output
1 Correct 2413 ms 83120 KB Output is correct - maxAccess = 10, score = 100