Submission #565511

#	Time	Username	Problem	Language	Result	Execution time	Memory
565511		dantoh000	Chameleon's Love (JOI20_chameleon)	C++14	0 / 100	753 ms	524288 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
namespace {
    int _N;
    vector<int> adjlist[1005];
    int done[1005];
    int qcount = 0;
    int QMAX = 30000;
    vector<int> v;
    int BUCKETS = 4;
    map<vector<int>, int> M;
}  // namespace
int q(vector<int> p) {
    sort(p.begin(),p.end());
    if (M[p] != 0) return M[p];
    if (++qcount > QMAX) assert(false);
    return M[p] = Query(p);
}
int isin(int L, int R, int x){
    vector<int> QQ;
    for (int j = L; j <= R; j++){
        QQ.push_back(j);
    }
    int q1 = q(QQ);
    QQ.push_back(x);
    int q2 = q(QQ);
    return q1-q2+1;
}
int msb(int x){
    int K = 31-__builtin_clz(x);
    return 1<<K;
}
void search(int L, int R, int x){
    int d = R-L+1;
    if (d <= BUCKETS){
        for (int k = L; k <= R; k++){
            if (q({k,x})){
                adjlist[k].push_back(x);
                adjlist[x].push_back(k);
            }
        }
        return;
    }
    int STEP = d/BUCKETS;
    int l = L, r = l+STEP;
    for (int i = 0; i < BUCKETS; i++){
        if (isin(l,r,x)) search(l,r,x);
        l = r+1; r = min(R,l+STEP);
    }
}
int getadj(int x){
    //printf("searching for %d\n",x);
    search(1,_N,x);
}
bool cmp(int a, int b){
    return adjlist[a].size() < adjlist[b].size();
}
void Solve(int N) {
    _N = N;
    memset(done,0,sizeof(done));
    vector<ii> ans;
    for (int i = N+1; i <= N*2; i++){
        getadj(i);
        if (adjlist[i].size() == 1 && !done[i]){
            //printf("FOUND %d with %d\n",i,adjlist[i][0]);
            ans.push_back({i,adjlist[i][0]});
            done[i] = done[adjlist[i][0]] = 1;
        }
    }
    for (int i = 1; i <= 2*N; i++){
        //printf("%d %d\n",i,adjlist[i].size());
        //assert(adjlist[i].size() == 1 || adjlist[i].size()==3);
        if (adjlist[i].size() == 1 && !done[i]){
            //printf("FOUND %d with %d\n",i,adjlist[i][0]);
            ans.push_back({i,adjlist[i][0]});
            done[i] = done[adjlist[i][0]] = 1;
        }
    }
    printf("used %d so far\n",qcount);
    for (int x = 1; x <= N; x++){
        if (done[x]) continue;
        else{
            //printf("settling %d\n",x);
            sort(adjlist[x].begin(),adjlist[x].end(),cmp);
            for (auto y : adjlist[x]){
                if (y == adjlist[x].back() || adjlist[y].size() == 1){
                    ans.push_back({x,y});
                    done[x] = done[y] = 1;
                    break;
                }
                //printf("maybe %d %d\n",x,y);
                int num1 = 0;
                for (auto z : adjlist[y]){
                    if (z != x && q({x,y,z}) == 1){
                        num1++;
                    }
                }
                if (num1 == 0) continue;
                for (auto w : adjlist[x]){
                    if (w != y && q({x,y,w}) == 1){
                        num1++;
                    }
                }
                //printf("%d %d -> %d\n",x,y,num1);
                if (num1 == 2){
                    ans.push_back({x,y});
                    done[x] = done[y] = 1;
                    break;
                }
            }
        }
    }

    assert((int)ans.size() == N);
    for (auto x : ans){
        //printf("%d %d\n",x.first,x.second);
        Answer(x.first,x.second);
    }
}

Compilation message (stderr)

chameleon.cpp: In function 'int getadj(int)':
chameleon.cpp:56:1: warning: no return statement in function returning non-void [-Wreturn-type]
   56 | }
      | ^

• Subtask 1: 0 / 4
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36