Submission #211865

#	Time	Username	Problem	Language	Result	Execution time	Memory
211865		3zp	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	69 ms	512 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
int f[1009],g[1009], n;
int ask(vector<int> a, int b){
    a.push_back(b);
    return Query(a);
}
bool check(int a, int b){
    vector<int> v;
    for(int i = 1; i <= 2*n; i++)
        if(i != a && i != b)
            v.push_back(i);
    return Query(v) != n;
}
int solve(vector<int> v, int x, int d){

    int lo = 0, hi = v.size()-1;
    while(lo < hi){
        int mid = (lo + hi)/2;
        vector<int> w;
        for(int i = 0; i <= mid; i++)
            w.push_back(v[i]);
        w.push_back(x);
        if(Query(w) <= mid + 1 - d)
            hi = mid;
        else lo = mid + 1;
    }
    return v[lo];
}
void ans(int x, int y){
    g[x] = 1; g[y] = 1;
    Answer(x, y);
}
void Solve(int N) {
    n = N;
    vector<vector<int> > A,B;
    for(int i = 1; i <= 2*N; i++){
        int j = -1;
        for(int k = 0; k < A.size(); k++){
            if(ask(A[k], i) == A[k].size()+1){
                j = k;
                break;
            }
        }
        if(j != -1){
            A[j].push_back(i);
            f[i] = j;
            continue;
        }
        A.push_back({i});
        f[i] = A.size()-1;
    }
    for(auto x : A)
        B.push_back(x),
        reverse(B.back().begin(), B.back().end());
    for(int i = 1; i <= 2*N; i++){
        if(g[i]) continue;
        vector<int> imp;
        int x = -1;
        for(int j = 0; j < A.size(); j++){
            if(j == f[i]) continue;
            int q = ask(A[j], i);
            if(q == A[j].size()-1)
                {x = j; break;}
            if(q == A[j].size())
                imp.push_back(j);
        }
        if(x != -1){
            vector<int> a = {0,1,2,3};
            random_shuffle(a.begin(),a.end());
            for(int t : a){
                int y;
                if(t == 0)
                    y = solve(A[x], i, 0);
                if(t == 1)
                    y = solve(A[x], i, 1);
                if(t == 2)
                    y = solve(B[x], i, 0);
                if(t == 3)
                    y = solve(B[x], i, 1);
                if(t == a.back() || check(i, y)){
                    ans(i, y);
                    break;
                }
            }
        }
        else{

            vector<int> pos;
            random_shuffle(imp.begin(),imp.end());
            for(int x : imp){
                int a = solve(A[x], i, 0);
                if(check(i, a)){
                    Answer(i, a);
                    g[a] = 1;
                    break;

                };
                 a = solve(B[x], i, 0);
                if(check(i, a)){
                    Answer(i, a);
                    g[a] = 1;
                    break;

                }
            }
        }
    }

}

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:40:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int k = 0; k < A.size(); k++){
                        ~~^~~~~~~~~~
chameleon.cpp:41:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(ask(A[k], i) == A[k].size()+1){
                ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
chameleon.cpp:61:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < A.size(); j++){
                        ~~^~~~~~~~~~
chameleon.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(q == A[j].size()-1)
                ~~^~~~~~~~~~~~~~~~
chameleon.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(q == A[j].size())
                ~~^~~~~~~~~~~~~~
chameleon.cpp:32:20: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
     g[x] = 1; g[y] = 1;
               ~~~~~^~~
chameleon.cpp:73:21: note: 'y' was declared here
                 int y;
                     ^

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