oj.uz

Submission #894572

# Submission time Handle Problem Language Result Execution time Memory
894572 2023-12-28T13:01:13 Z boris_mihov Library (JOI18_library) C++17
100 / 100
 111 ms 1224 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 712 KB # of queries: 1522
2 Correct 12 ms 464 KB # of queries: 1516
3 Correct 11 ms 712 KB # of queries: 1587
4 Correct 14 ms 724 KB # of queries: 1584
5 Correct 15 ms 600 KB # of queries: 1597
6 Correct 10 ms 724 KB # of queries: 1592
7 Correct 16 ms 460 KB # of queries: 1585
8 Correct 14 ms 712 KB # of queries: 1494
9 Correct 12 ms 716 KB # of queries: 1590
10 Correct 10 ms 596 KB # of queries: 949
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 600 KB # of queries: 1
13 Correct 0 ms 344 KB # of queries: 3
14 Correct 0 ms 344 KB # of queries: 7
15 Correct 1 ms 344 KB # of queries: 61
16 Correct 1 ms 344 KB # of queries: 132

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 712 KB # of queries: 1522
2 Correct 12 ms 464 KB # of queries: 1516
3 Correct 11 ms 712 KB # of queries: 1587
4 Correct 14 ms 724 KB # of queries: 1584
5 Correct 15 ms 600 KB # of queries: 1597
6 Correct 10 ms 724 KB # of queries: 1592
7 Correct 16 ms 460 KB # of queries: 1585
8 Correct 14 ms 712 KB # of queries: 1494
9 Correct 12 ms 716 KB # of queries: 1590
10 Correct 10 ms 596 KB # of queries: 949
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 600 KB # of queries: 1
13 Correct 0 ms 344 KB # of queries: 3
14 Correct 0 ms 344 KB # of queries: 7
15 Correct 1 ms 344 KB # of queries: 61
16 Correct 1 ms 344 KB # of queries: 132
17 Correct 104 ms 724 KB # of queries: 10318
18 Correct 100 ms 716 KB # of queries: 10174
19 Correct 94 ms 876 KB # of queries: 10288
20 Correct 92 ms 976 KB # of queries: 9620
21 Correct 90 ms 724 KB # of queries: 9036
22 Correct 98 ms 728 KB # of queries: 10301
23 Correct 111 ms 724 KB # of queries: 10271
24 Correct 37 ms 704 KB # of queries: 4786
25 Correct 95 ms 984 KB # of queries: 10060
26 Correct 84 ms 724 KB # of queries: 9408
27 Correct 37 ms 716 KB # of queries: 4769
28 Correct 96 ms 740 KB # of queries: 9966
29 Correct 101 ms 712 KB # of queries: 9955
30 Correct 92 ms 1224 KB # of queries: 9966