Submission #734242

#	Time	Username	Problem	Language	Result	Execution time	Memory
734242		Ronin13	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	89 ms	948 KiB

chameleon

#include "chameleon.h"
#include <vector>
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second

using namespace std;
namespace {

int variable_example = 1;

}  // namespace

const int nmax = 20001;
vector <vector <int> > g(nmax);

vector <vector <int> > col(2);
vector <bool> used(nmax);

void dfs(int v, int c){
    col[c].pb(v);
    used[v] = true;
    for(int to : g[v]){
        if(used[to]) continue;
        dfs(to, c ^ 1);
    }
}

bool ask(int a, int b, int x){
    vector <int> vec;
    for(int to : col[b]){
        if(vec.size() < x)
            vec.pb(to);
    }
    vec.pb(a);
    return Query(vec) == vec.size();
}

void Solve(int N) {
    int n = N;
    for(int i = 1; i <= 2 * n; i++){
        for(int j= 1; j < i; j++)
            if(!used[j]) dfs(j, 0);
        for(int j= 1;j <= i; j++)
            used[j] = false;
        for(int x = 0; x < 2; x++){
            //cout << col[x].size() << "\n";
            while(!ask(i, x, col[x].size())){
                int l = -1, r = col[x].size();
                while(l + 1 < r){
                    int mid = (l + r) / 2;
                    if(!ask(i, x, mid + 1)) r = mid;
                    else l = mid;
                }
                if(r == col[x].size()) break;
                g[i].pb(col[x][r]);
                g[col[x][r]].pb(i);
                while(r < (int)col[x].size() - 1)
                    swap(col[x][r], col[x][r + 1]), r++;
                col[x].pop_back();
            }
        }
        col[0].clear();
        col[1].clear();
    }

    //vector <bool> used(nmax);
    vector <int> love(nmax);
    for(int i = 1; i <= 2 * n; i++){
        if(g[i].size() == 1){
            if(!used[i])Answer(i, g[i][0]);
            used[i] = used[g[i][0]] = true;
        }
        else{
            vector <pii> vec;
            for(int x = 0; x < 3; x++){
                for(int y = x + 1; y < 3; y++){
                    if(Query({i, g[i][x], g[i][y]}) == 2)
                        vec.pb({x, y});
                }
            }
            int cnt[3];
            fill(cnt, cnt + 3, 0);
            for(auto to : vec)
                cnt[to.f]++, cnt[to.s]++;
            for(int j = 0; j < 3; j++){
                if(cnt[j] == 2)
                    love[i] = g[i][j];
            }
        }
    }

    for(int i= 1; i <= n * 2; i++){
        if(used[i]) continue;
        for(int j = 0; j < 3; j++){
            if(love[g[i][j]] != i && love[i] != g[i][j]){
                used[g[i][j]] = true, used[i] = true;
                Answer(g[i][j], i);
            }
        }
    }
}

Compilation message (stderr)

chameleon.cpp: In function 'bool ask(int, int, int)':
chameleon.cpp:34:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         if(vec.size() < x)
      |            ~~~~~~~~~~~^~~
chameleon.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     return Query(vec) == vec.size();
      |            ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 if(r == col[x].size()) break;
      |                    ~~^~~~~~~~~~~~~~~~
chameleon.cpp: At global scope:
chameleon.cpp:12:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   12 | int variable_example = 1;
      |     ^~~~~~~~~~~~~~~~

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