Submission #894572

#	Time	Username	Problem	Language	Result	Execution time	Memory
894572		boris_mihov	Library (JOI18_library)	C++17	100 / 100	111 ms	1224 KiB

library

#include "library.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 1024;
const int INF  = 1e9;

int cnt[MAXN];
std::vector <int> chain;
std::vector <int> g[MAXN];

void getChain(int node, int par)
{
    chain.push_back(node + 1);
    for (const int &u : g[node])
    {
        if (u == par)
        {
            continue;
        }

        getChain(u, node);
    }
}

void Solve(int n)
{
    if (n == 1)
    {
        Answer({1});
        return;
    }
    
    chain.clear();
    for (int i = 0 ; i < n ; ++i)
    {
        cnt[i] = 0;
        g[i].clear();
    }

    std::vector <int> v(n, 0);
    int last = 0;
    for (int i = 1 ; i < n ; ++i)
    {
        std::fill(v.begin(), v.end(), 0);
        for (int j = 0 ; j <= i ; ++j)
        {
            v[j] = 1;
        }

        v[i] = 1;
        int count = i + 1 - Query(v);

        if (count >= last + 1)
        {
            int l = -1, r = i - 1, mid;
            while (l < r - 1)
            {
                mid = (l + r) / 2;
                std::fill(v.begin(), v.end(), 0);
                for (int j = 0 ; j <= mid ; ++j)
                {
                    v[j] = 1;
                }

                v[i] = 1;
                int res = mid + 2 - Query(v) - cnt[mid];
                assert(res >= 0);

                if (res < 1) l = mid;
                else r = mid;
            }

            g[i].push_back(r);
            g[r].push_back(i);
        }

        if (count >= last + 2)
        {
            int l = -1, r = i - 1, mid;
            while (l < r - 1)
            {
                mid = (l + r) / 2;
                std::fill(v.begin(), v.end(), 0);
                for (int j = 0 ; j <= mid ; ++j)
                {
                    v[j] = 1;
                }

                v[i] = 1;
                int res = mid + 2 - Query(v) - cnt[mid];
                assert(res >= 0);

                if (res < 2) l = mid;
                else r = mid;
            }

            g[i].push_back(r);
            g[r].push_back(i);
        }

        cnt[i] = count;
        last = count;
    }

    for (int i = 0 ; i < n ; ++i)
    {
        if (g[i].size() == 1)
        {
            getChain(i, -1);
            break;
        }
    }   

    Answer(chain);
}

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