Submission #231137

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
231137	2020-05-12T20:43:40 Z	summitwei	cmp (balkan11_cmp)	C++17	100 / 100	2949 ms	96224 KB

cmp

#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

cmp.cpp:143:5: warning: "/*" within comment [-Wcomment]
     /*int a, b;

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2949 ms	96224 KB	Output is correct - maxAccess = 10, score = 100