oj.uz

Submission #894556

# Submission time Handle Problem Language Result Execution time Memory
894556 2023-12-28T12:46:06 Z boris_mihov Library (JOI18_library) C++17
0 / 100
 18 ms 980 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)
{
    std::vector <int> v(n, 0);
    std::vector <int> order;
    order.push_back(0);

    v[0] = 1;
    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;
        order.push_back(i);
        last = count;
    }

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

    Answer(chain);
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 724 KB # of queries: 1522
2 Correct 10 ms 972 KB # of queries: 1516
3 Correct 10 ms 716 KB # of queries: 1587
4 Correct 10 ms 980 KB # of queries: 1584
5 Correct 11 ms 976 KB # of queries: 1597
6 Correct 13 ms 716 KB # of queries: 1592
7 Correct 18 ms 468 KB # of queries: 1585
8 Correct 10 ms 724 KB # of queries: 1494
9 Correct 10 ms 972 KB # of queries: 1590
10 Correct 6 ms 724 KB # of queries: 949
11 Incorrect 0 ms 344 KB Wrong Answer [4]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 724 KB # of queries: 1522
2 Correct 10 ms 972 KB # of queries: 1516
3 Correct 10 ms 716 KB # of queries: 1587
4 Correct 10 ms 980 KB # of queries: 1584
5 Correct 11 ms 976 KB # of queries: 1597
6 Correct 13 ms 716 KB # of queries: 1592
7 Correct 18 ms 468 KB # of queries: 1585
8 Correct 10 ms 724 KB # of queries: 1494
9 Correct 10 ms 972 KB # of queries: 1590
10 Correct 6 ms 724 KB # of queries: 949
11 Incorrect 0 ms 344 KB Wrong Answer [4]
12 Halted 0 ms 0 KB -