Submission #565509

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

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
namespace {
    int BKSZA = 50;
    int BKSZB = 10;
    int _N;
    int adjmat[1005][1005];
    vector<int> adjlist[1005];
    int done[1005];
    int qcount = 0;
    int QMAX = 20000;
    vector<int> v;
    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;
}
int getadj(int x){
    //printf("trying to find %d\n",x);
    for (int i = 0; i <= _N/BKSZA; i++){
        vector<int> QQ;
        int l = BKSZA*i+1, r = min(_N,BKSZA*(i+1));
        //printf("bucket %d %d %d\n",i,l,r);
        if (isin(l,r,x)){
            //printf("something is in bucket (%d,%d)\n",l,r);
            for (int j = 0; j <= BKSZA/BKSZB; j++){
                vector<int> QQ;
                int L = l+BKSZB*j, R = min(_N,l+min(BKSZA,BKSZB*(j+1))-1);
                //printf("minibucket %d %d %d\n",j,L,R);
                if (L > _N || R > _N) break;
                if (isin(L,R,x)){
                    //printf("something is in minibucket (%d,%d)\n",L,R);
                    for (int k = L; k <= R; k++){
                        if (q({k,x}) == 1){
                            //printf("found %d\n",k);
                            adjlist[k].push_back(x);
                            adjlist[x].push_back(k);
                        }
                    }
                }
            }
        }
    }
}
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){
            //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);
            for (auto y : adjlist[x]){
                //printf("maybe %d %d\n",x,y);
                int num1 = 0;
                for (auto z : adjlist[y]){
                    if (z != x && q({x,y,z}) == 1){
                        num1++;
                    }
                }
                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:59:1: warning: no return statement in function returning non-void [-Wreturn-type]
   59 | }
      | ^
chameleon.cpp: At global scope:
chameleon.cpp:9:9: warning: '{anonymous}::adjmat' defined but not used [-Wunused-variable]
    9 |     int adjmat[1005][1005];
      |         ^~~~~~

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