Submission #259767

#	Time	Username	Problem	Language	Result	Execution time	Memory
259767		Kastanda	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	40 ms	512 KiB

chameleon

// M
#include<bits/stdc++.h>
#include "chameleon.h"
#define pb push_back
using namespace std;

const int N = 505 * 2;
int M[N], MC[N];
vector < int > V[N];

void Recur(vector < int > vec)
{
        for (int i = 0; i < (int)vec.size(); i ++)
                if (V[vec[i]].size() == 3)
                        swap(vec[i], vec.back()), vec.pop_back(), i --;
        if (!vec.size())
                return ;

        /*printf("Now : ");
        for (int i : vec)
                printf("%d ", i);
        printf("\n");
        fflush(stdout);*/

        vector < int > tmp, bad;
        tmp.pb(vec[0]);
        for (int i = 1; i < (int)vec.size(); i ++)
        {
                tmp.pb(vec[i]);
                if (Query(tmp) == (int)tmp.size())
                        continue;
                else
                        bad.pb(vec[i]), tmp.pop_back();
        }
        assert((int)tmp.size() >= (int)vec.size() / 4);
        for (int i : bad)
        {
                int le = 0, ri = (int)tmp.size(), md;
                while (true)
                {
                        vector < int > ff(tmp.begin() + le, tmp.begin() + ri);
                        ff.pb(i);
                        if (le > 0 && Query(ff) == (int)ff.size())
                                break;
                        while (ri - le > 1)
                        {
                                md = (le + ri) >> 1;
                                ff = vector < int > (tmp.begin() + le, tmp.begin() + md);
                                ff.pb(i);
                                if (Query(ff) == (int)ff.size())
                                        le = md;
                                else
                                        ri = md;
                        }
                        V[i].push_back(tmp[le]);
                        V[tmp[le]].push_back(i);

                        le ++;
                        ri = (int)tmp.size();
                }
        }
        Recur(bad);
}

void Solve(int n)
{
        vector < int > vec;
        for (int i = 1; i <= n + n; i ++)
                vec.push_back(i);
        Recur(vec);

        for (int i = 1; i <= n + n; i ++)
                if (V[i].size() == 1) // Part of a cycle of length 2
                {
                        MC[i] = V[i][0];
                        MC[V[i][0]] = i;
                }

        for (int i = 1; i <= n + n; i ++)
                if (MC[i] == 0)
                {
                        assert((int)V[i].size() == 3);
                        vector < int > All;
                        memset(M, 0, sizeof(M));
                        M[i] = 1;
                        for (int a : V[i])
                                M[a] = 1;
                        for (int v = 1; v <= n + n; v ++)
                                if (!M[v])
                                        All.pb(v);

                        for (int a : V[i])
                        {
                                vector < int > tmp(All.begin(), All.end());
                                for (int b : V[i])
                                        if (a != b)
                                                tmp.pb(b);
                                if (Query(tmp) < n)
                                {
                                        MC[i] = a;
                                        MC[a] = i;
                                        break;
                                }
                        }
                        assert(MC[i]);
                }
        for (int i = 1; i <= n + n; i ++)
                if (i < MC[i])
                        Answer(i, MC[i]);
}

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