Submission #1164662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164662		who	Library (JOI18_library)	C++20	0 / 100	16 ms	468 KiB

library

#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include "library.h"
#define pb push_back
using namespace std;

template<class T> ostream& operator << (ostream& out, const vector<T>& v)
{
    out << "{";
	for (int i=0; i<v.size(); i++)
    {
        out << v[i];
        if (i != v.size() - 1) out << ", ";
    }

    out << "}";
	return out;
}

const int N = 1e3;

int n;
vector<int> adj[N+5];

int ask(const vector<int>& nodes)
{
    if (nodes.empty()) return 0;

    vector<int> M(n, 0);
    for (int i : nodes) M[i-1] = 1;

    //cerr << nodes << ": " << M << endl;

    return Query(M);
}

int countEdges(int node, vector<int>& test)
{
    int withoutNode = ask(test);
    test.pb(node);

    int withNode = ask(test);
    test.pop_back();

    //cerr << withoutNode << ' ' << withNode << "..." << endl;
    return withoutNode - withNode + 1;
}

void createEdge(int x, vector<int> y, int edges)
{
    if (edges == 0) return;
    //cerr << x << ' ' << y << ": " << edges << endl;
    if (y.empty()) return;
    if (y.size() == 1)
    {
        adj[x].pb(y.front());
        adj[y.front()].pb(x);

        return;
    }

    int l=1, r=y.size();
    int mid = (l+r) >> 1;
    vector<int> left(y.begin(), y.begin() + mid), right(y.begin() + mid, y.end());

    int leftEdges = countEdges(x, left);

    if (leftEdges == 0) createEdge(x, right, edges);
    else
    {
        createEdge(x, left, leftEdges);
        if (edges - leftEdges) createEdge(x, right, edges - leftEdges);
    }
}

void Solve(int N)
{
    n = N;

    //cerr << "..." << endl;
    for (int i=1; i<=n; i++)
    {
        vector<int> nodes;
        for (int j=i+1; j<=n; j++) nodes.pb(j);
        //cerr << countEdges(i, nodes) << "!!!" << endl;
        createEdge(i, nodes, countEdges(i, nodes));
    }

//    for (int i=1; i<=n; i++)
//    {
//        for (int j : adj[i]) cerr << i << ' ' << j << "!" << endl;
//    }

    vector<bool> used(n+5, false);
    vector<int> res;
    for (int i=1; i<=n; i++)
    {
        if (adj[i].size() == 1)
        {
            while (res.size() < n)
            {
                res.pb(i);
                used[i] = true;
                for (int j : adj[i])
                {
                    if (used[j]) continue;
                    i = j;
                    break;
                }
            }

            break;
        }
    }

    for (int i : res) cerr << i << ' ';
    cerr << endl;

	Answer(res);
}

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