Submission #288179

#	Time	Username	Problem	Language	Result	Execution time	Memory
288179		Kastanda	Library (JOI18_library)	C++11	100 / 100	377 ms	672 KiB

library

// M
#include<bits/stdc++.h>
#include "library.h"
using namespace std;
const int N = 1009;
vector < int > Adj[N];

void Solve(int n)
{
        for (int i = 1; i <= n; i ++)
        {
                if ((int)Adj[i].size() == 2)
                        continue;
                vector < int > vec;
                for (int j = i + 1; j <= n; j ++)
                        vec.push_back(j);
                if (!vec.size())
                        continue;

                int le = -1, ri = (int)vec.size() - 1, md;

                vector < int > M(n, 0);
                for (int j : vec)
                        M[j - 1] = 1;
                int wq1 = Query(M);
                M[i - 1] = 1;
                int wq2 = Query(M);
                if (wq1 < wq2)
                        continue;
                while (ri - le > 1)
                {
                        md = (le + ri) >> 1;
                        M = vector < int > (n, 0);
                        for (int j = 0; j <= md; j ++)
                                M[vec[j] - 1] = 1;
                        int t1 = Query(M);
                        M[i - 1] = 1;
                        int t2 = Query(M);
                        if (t1 < t2)
                                le = md;
                        else
                                ri = md;
                }
                Adj[i].push_back(vec[ri]);
                Adj[vec[ri]].push_back(i);
                if (wq1 == wq2)
                        continue;
                assert(wq1 > wq2);
                int id = ri;
                le = ri; ri = (int)vec.size() - 1;
                assert(id < ri);
                while (ri - le > 1)
                {
                        md = (le + ri) >> 1;
                        M = vector < int > (n, 0);
                        for (int j = id + 1; j <= md; j ++)
                                M[vec[j] - 1] = 1;
                        int t1 = Query(M);
                        M[i - 1] = 1;
                        int t2 = Query(M);
                        if (t1 < t2)
                                le = md;
                        else
                                ri = md;
                }
                Adj[i].push_back(vec[ri]);
                Adj[vec[ri]].push_back(i);
        }

        int nw = -1;
        for (int i = 1; i <= n; i ++)
                if ((int)Adj[i].size() == 1)
                        nw = i;
        if (n == 1)
                nw = 1;
        assert(nw != -1);
        int last = -1;
        vector < int > Rs = {nw};
        for (int i = 1; i < n; i ++)
        {
                int tobe = Adj[nw][0];
                if (tobe == last)
                        tobe = Adj[nw][1];
                last = nw;
                nw = tobe;
                Rs.push_back(nw);
        }
        Answer(Rs);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81