oj.uz

Submission #1079917

# Submission time Handle Problem Language Result Execution time Memory
1079917 2024-08-29T03:29:35 Z Thanhs Library (JOI18_library) C++14
100 / 100
 914 ms 78472 KB 
#include<library.h>
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
 
// #define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define aint(x) x.begin(), x.end()
 
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 1e3 + 5;

int N;
vector<int> g[NM];
set<int> s;
map<vector<int>, int> mp;

// int Query(vector<int>& v)
// {
//     cout << "? ";
//     for (int i = 0; i < N; i++)
//         if (v[i])
//             cout << i + 1 << ' ';
//     cout << endl;
//     int res;
//     cin >> res;
//     return res;
// }

// void Answer(vector<int>& v)
// {
//     cout << "! ";
//     for (int t : v)
//         cout << t << ' ';
//     cout << endl;
// }

vector<int> t;

int ask(int x, int y)
{
    fill(t.begin(), t.end(), 0);
    if (y)
        t[y - 1] = 1;
    auto it = s.begin();
    for (int i = 1; i <= x; i++, it = next(it))
        t[*it - 1] = 1;
    if (t.size() == 1)
        return 1;
    if (mp.find(t) != mp.end())
        return mp[t];
    int res = Query(t);
    mp[t] = res;
    return mp[t];
}

int get(int x)
{
    auto it = s.begin();
    x--;
    while (x--)
        it = next(it);
    return *it;
}

void Solve(int n)
{
    N = n;
    t.resize(N, 0);
    if (n == 1)
    {
        vector<int> res(1, 1);
        Answer(res);
        return;
    }
    for (int i = 1; i <= n; i++)
        s.insert(i);
    for (int i = 1; i <= n; i++)
    {
        vector<int> tmp;
        s.erase(i);
        // cout << "LMAO " << i << ' ' << s.size() << endl;
        while (g[i].size() < 2)
        {
            if (s.empty())
                break;
            if (ask(s.size(), i) > ask(s.size(), 0))
                break;
            int l = 0, r = s.size();
            while (l < r - 1)
            {
                int m = l + r >> 1;
                if (ask(m, i) <= ask(m, 0))
                    r = m;
                else 
                    l = m;
            }
            int t = get(r);
            g[i].push_back(t);
            g[t].push_back(i);
            // cout << "EDGE " << i << ' ' << t << endl;
            tmp.push_back(t);
            s.erase(t);
        }
        for (int t : tmp)
            s.insert(t);
    }
    for (int i = 1; i <= n; i++)
        if (g[i].size() == 1)
        {
            vector<int> res;
            s.insert(i);
            int u = i;
            while (1)
            {
                res.push_back(u);
                bool b = 0;
                for (auto v : g[u])
                    if (s.find(v) == s.end())
                    {
                        b = 1;
                        u = v;
                        break;
                    }
                s.insert(u);
                if (!b)
                    break;
            }
            Answer(res);
            return;
        }
}

// int main()
// {
//     int n;
//     cin >> n;
//     Solve(n);
// }

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:100:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |                 int m = l + r >> 1;
      |                         ~~^~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2852 KB # of queries: 2823
2 Correct 42 ms 2632 KB # of queries: 2761
3 Correct 42 ms 2916 KB # of queries: 2916
4 Correct 53 ms 2872 KB # of queries: 2917
5 Correct 51 ms 2972 KB # of queries: 2934
6 Correct 37 ms 2896 KB # of queries: 2894
7 Correct 42 ms 2896 KB # of queries: 2910
8 Correct 41 ms 2940 KB # of queries: 2784
9 Correct 40 ms 2892 KB # of queries: 2934
10 Correct 21 ms 1360 KB # of queries: 1732
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 0 ms 344 KB # of queries: 11
15 Correct 1 ms 344 KB # of queries: 91
16 Correct 2 ms 344 KB # of queries: 218

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2852 KB # of queries: 2823
2 Correct 42 ms 2632 KB # of queries: 2761
3 Correct 42 ms 2916 KB # of queries: 2916
4 Correct 53 ms 2872 KB # of queries: 2917
5 Correct 51 ms 2972 KB # of queries: 2934
6 Correct 37 ms 2896 KB # of queries: 2894
7 Correct 42 ms 2896 KB # of queries: 2910
8 Correct 41 ms 2940 KB # of queries: 2784
9 Correct 40 ms 2892 KB # of queries: 2934
10 Correct 21 ms 1360 KB # of queries: 1732
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 0 ms 344 KB # of queries: 11
15 Correct 1 ms 344 KB # of queries: 91
16 Correct 2 ms 344 KB # of queries: 218
17 Correct 860 ms 77472 KB # of queries: 19239
18 Correct 813 ms 76004 KB # of queries: 19055
19 Correct 835 ms 78472 KB # of queries: 19349
20 Correct 752 ms 68860 KB # of queries: 18080
21 Correct 662 ms 61360 KB # of queries: 17015
22 Correct 807 ms 78332 KB # of queries: 19352
23 Correct 849 ms 77776 KB # of queries: 19297
24 Correct 229 ms 19200 KB # of queries: 8871
25 Correct 914 ms 74352 KB # of queries: 18844
26 Correct 774 ms 65880 KB # of queries: 17640
27 Correct 332 ms 19144 KB # of queries: 8895
28 Correct 737 ms 62568 KB # of queries: 15473
29 Correct 787 ms 62304 KB # of queries: 15454
30 Correct 727 ms 62752 KB # of queries: 15473