# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
231137 | summitwei | cmp (balkan11_cmp) | C++17 | 2949 ms | 96224 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "cmp.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define INF 0x3f3f3f3f
#define MOD 1000000007LL
#define f first
#define s second
#define pb push_back
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define F0R(i, a) for(int i=0; i<a; ++i)
#define MN 10250
#define MM 4100
/*bool data[MM][MN];
int x;
int cnt1;
void bit_set(int addr){
assert(addr >= 1 && addr <= 10240);
++cnt1;
data[x][addr] = true;
}
int cnt2;
bool bit_get(int addr){
assert(addr >= 1 && addr <= 10240);
++cnt2;
return data[x][addr];
}*/
int p4[6] = {1024, 256, 64, 16, 4, 1};
int off[6] = {1, 5, 31, 95, 351, 1366};
void remember(int a){
int res[6];
F0R(i, 6){
res[i] = (a/p4[i])%4;
}
int amts[6];
F0R(i, 6){
int sm = 0;
F0R(j, i+1){
sm += res[j]*p4[j];
}
amts[i] = sm/p4[i]+off[i];
}
/*F0R(i, 6){
cout << res[i] << " ";
}
cout << "\n";
F0R(i, 6){
cout << amts[i] << " ";
}
cout << "\n";*/
F0R(i, 6){
bit_set(amts[i]);
}
}
int compare(int b){ //-1 = b less. 1 = b more
int res[6];
F0R(i, 6){
res[i] = (b/p4[i])%4;
}
int amts[6];
F0R(i, 6){
int sm = 0;
F0R(j, i+1){
sm += res[j]*p4[j];
}
amts[i] = sm/p4[i]+off[i];
}
/*F0R(i, 6){
cout << res[i] << " ";
}
cout << "\n";
F0R(i, 6){
cout << amts[i] << " ";
}
cout << "\n";*/
int l = -1, r = 6;
while(l+1<r){
int mid = (l+r)/2;
//cout << "checking " << mid << "\n";
if(bit_get(amts[mid])){
l = mid;
} else{
r = mid;
}
}
//cout << "r is " << r << "\n";
//r represents the first bit that they are different
if(r == 6) return 0;
if(res[r] == 0) return -1;
if(res[r] == 3) return 1;
if(res[r] == 1){
if(bit_get(amts[r]-1)) return 1;
else return -1;
}
if(res[r] == 2){
if(bit_get(amts[r]+1)) return -1;
else return 1;
}
//cout << "bruh how are you not done\n";
return 0;
}
/*int main(){
int mxa = 0;
F0R(i, 1<<12){
//cout << "doing " << i << "\n";
cnt1 = 0;
x = i;
remember(i);
mxa = max(mxa, cnt1);
}
int mxb = 0;
F0R(i, 1<<12){
F0R(j, 1<<12){
cnt2 = 0;
x = i;
//cout << "doing " << i << " " << j << "\n";
int res = compare(j);
if((res==-1&&j<i) || (res==0&&j==i) || (res==1&&j>i)){
mxb = max(mxb, cnt2);
} else{
cout << "you suck lol\n" << i << " " << j << "\n";
return 0;
}
}
}
cout << mxa << " " << mxb << " " << mxa+mxb << "\n";
/*int a, b;
cin >> a >> b;
remember(a);
int res = compare(b);
if((res==-1&&b<a) || (res==0&&b==a) || (res==1&&b>a)){
cout << "yay " << cnt1 << " " << cnt2 << "\n";
} else{
cout << "oh no\n";
}
}
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |