Submission #216277

#	Time	Username	Problem	Language	Result	Execution time	Memory
216277		combi1k1	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	115 ms	552 KiB

chameleon

#include "chameleon.h"
#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 1e3 + 5;

typedef pair<int,int>   ii;
typedef vector<int>     vi;

void EndProgram(string encode)  {
    cerr << "Wrong ";
    cerr << encode;
    exit(0);
}

int gender[N];
int colour[N];
int sameC[N];
int lover[N];
bool invec[N];
int n;
int c[N];

vector<int> g[N];

int ask(vector<int> vec)    {
    if (vec.size() == 0)    return  0;
    if (vec.size() == 1)    return  1;

    static int Count = 0;

    Count++;

    if (Count > 20000)
        EndProgram("3");

    sort(all(vec));
    vec.erase(unique(all(vec)),vec.end());

    for(int x : vec)
        if (x < 1 || x > n + n)
            EndProgram("1");

    #ifndef LOCAL
    return  Query(vec);
    #endif // LOCAL

    set<int> S;

    for(int x : vec)    invec[x] = 1;
    for(int x : vec)    {
        if (invec[lover[x]])
            S.insert(colour[lover[x]]);
        else
            S.insert(colour[x]);
    }
    for(int x : vec)    invec[x] = 0;

    return  S.size();
}
map<ii,bool> called;

void Report(int x,int y)    {
    #ifndef LOCAL
    Answer(x,y);
    return;
    #endif // LOCAL

    if (x < 1 || x > n + n) EndProgram("4");
    if (y < 1 || y > n + n) EndProgram("4");

    if (x > y)  swap(x,y);
    if (called.count(ii(x,y)))  EndProgram("5");
    if (colour[x] != colour[y]) EndProgram("6");
    if (x == y) EndProgram("ngu vl");
}

void Solve(int _n)  {
    n = _n;

    for(int i = 1 ; i <= n + n ; ++i)   {
        vector<vi>  vec(2);

        for(int j = 1 ; j < i ; ++j)    c[j] = -1;
        for(int j = 1 ; j < i ; ++j)    {
            if (c[j] < 0)   {
                c[j] = 0;
                queue<int>  qu; qu.push(j);

                while (qu.size())   {
                    int u = qu.front(); qu.pop();

                    for(int v : g[u])   {
                        if (c[v] < 0)   {
                            c[v] = c[u] ^ 1;
                            qu.push(v);
                        }
                        if (c[v] == c[u])
                            EndProgram("Ngu vl");
                    }
                }
            }
            vec[c[j]].pb(j);
        }
        for(vi  tmp : vec)    {
            vi  nxt = tmp;
            nxt.pb(i);

            while (ask(nxt) != sz(nxt)) {
                int l = 1;
                int r = sz(tmp);

                while (l < r)   {
                    int m = (l + r) / 2;

                    nxt = vi(tmp.begin(),tmp.begin() + m);
                    nxt.pb(i);

                    if (ask(nxt) == sz(nxt))
                        l = m + 1;
                    else
                        r = m;
                }
                int x = tmp[l - 1];

                g[i].pb(x);
                g[x].pb(i);

                nxt = vector<int>(tmp.begin() + l,tmp.end());
                tmp = nxt;
                nxt.pb(i);
            }
        }
    }
    for(int i = 1 ; i <= n + n ; ++i)   {
        //g[i] contains the chameleons which are:
        //  -   have the same color as i-th chameleon
        //  -   love the i-th chameleon
        //  -   is loved by the i-th chameleon
        if (sz(g[i]) == 1)  {
            sameC[i] = g[i][0];
            continue;
        }
        while (ask({i, g[i][0], g[i][1]}) > 1)
            rotate(g[i].begin(),g[i].begin() + 1,g[i].end());

        lover[i] = g[i][2];
    }
    for(int i = 1 ; i <= n + n ; ++i)   {
        if (lover[g[i][0]] == i)
            sameC[i] = g[i][1];
        else
            sameC[i] = g[i][0];
    }
    for(int i = 1 ; i <= n + n ; ++i)
        if (i < sameC[i])
            Report(i,sameC[i]);
}

//int main()  {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//
//    for(int i = 1 ; i < 9 ; ++i)    cin >> gender[i];
//    for(int i = 1 ; i < 9 ; ++i)    cin >> colour[i];
//    for(int i = 1 ; i < 9 ; ++i)    cin >> lover[i];
//
//    Solve(4);
//}
///*
//1 0 1 0 0 1 1 0
//4 4 1 2 1 2 3 3
//4 3 8 7 6 5 2 1
//*/

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