oj.uz

Submission #1091115

# Submission time Handle Problem Language Result Execution time Memory
1091115 2024-09-19T20:48:56 Z raphaelp Library (JOI18_library) C++14
100 / 100
 182 ms 696 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
/*vector<int> Tab;
void Answer(vector<int> V)
{
    for (auto val : V)
        cout << val << ' ';
}
int Query(vector<int> V)
{
    int tot = 0;
    for (int i = 0; i < Tab.size(); i++)
    {
        if (V[Tab[i] - 1] && (i == 0 || V[Tab[i - 1] - 1] == 0))
            tot++;
    }
    return tot;
}*/
void Solve(int N)
{
    vector<vector<int>> groups;
    groups.push_back({0});
    vector<int> test(N, 0);
    test[0] = 1;
    for (int i = 1; i < N; i++)
    {
        test[i] = 1;
        int nb = Query(test);
        if (nb == groups.size() + 1)
        {
            groups.push_back({i});
            continue;
        }
        int L = 0, R = groups.size() * 2;
        while (L != R)
        {
            int m = (L + R) / 2;
            vector<int> test2(N);
            int buff = 0, exp = 0;
            for (int j = L; j <= m; j++)
            {
                if (j % 2 == 0)
                    test2[groups[j / 2][0]] = 1;
                else
                {
                    for (int k = 1; k < groups[j / 2].size(); k++)
                        test2[groups[j / 2][k]] = 1;
                    if (groups[j / 2].size() == 1)
                        test2[groups[j / 2][0]] = 1;
                }
            }
            test2[i] = 1;
            int exp2 = ceil((double)(m + 1) / 2) - L / 2;
            int res = Query(test2);
            if (res == exp2 + 1)
                L = m + 1;
            else
                R = m;
        }
        int adj = L;
        vector<int> temp;
        if (adj % 2 == 0)
            reverse(groups[adj / 2].begin(), groups[adj / 2].end());
        for (int j = 0; j < groups[adj / 2].size(); j++)
            temp.push_back(groups[adj / 2][j]);
        swap(groups[adj / 2], groups.back());
        groups.pop_back();
        temp.push_back(i);
        L = 0, R = groups.size() * 2;
        if (nb == groups.size())
        {
            while (L != R)
            {
                int m = (L + R) / 2;
                vector<int> test2(N);
                int buff = 0, exp = 0;
                for (int j = L; j <= m; j++)
                {
                    if (j % 2 == 0)
                        test2[groups[j / 2][0]] = 1;
                    else
                    {
                        for (int k = 1; k < groups[j / 2].size(); k++)
                            test2[groups[j / 2][k]] = 1;
                        if (groups[j / 2].size() == 1)
                            test2[groups[j / 2][0]] = 1;
                    }
                }
                test2[i] = 1;
                exp = ceil((double)(m + 1) / 2) - L / 2;
                int res = Query(test2);
                if (res == exp + 1)
                    L = m + 1;
                else
                    R = m;
            }
        }

        if (nb == groups.size())
        {
            if (L % 2 == 1)
                reverse(groups[L / 2].begin(), groups[L / 2].end());
            for (int j = 0; j < groups[L / 2].size(); j++)
                temp.push_back(groups[L / 2][j]);
            swap(groups[L / 2], groups.back());
            groups.pop_back();
        }
        groups.push_back(temp);
    }
    for (int i = 0; i < N; i++)
        groups[0][i]++;
    Answer(groups[0]);
}
/*int main()
{
    int N;
    cin >> N;
    Tab.assign(N, 0);
    for (int i = 0; i < N; i++)
        cin >> Tab[i];
    Solve(N);
}*/

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         if (nb == groups.size() + 1)
      |             ~~~^~~~~~~~~~~~~~~~~~~~
library.cpp:47:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |                     for (int k = 1; k < groups[j / 2].size(); k++)
      |                                     ~~^~~~~~~~~~~~~~~~~~~~~~
library.cpp:40:17: warning: unused variable 'buff' [-Wunused-variable]
   40 |             int buff = 0, exp = 0;
      |                 ^~~~
library.cpp:40:27: warning: unused variable 'exp' [-Wunused-variable]
   40 |             int buff = 0, exp = 0;
      |                           ^~~
library.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int j = 0; j < groups[adj / 2].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         if (nb == groups.size())
      |             ~~~^~~~~~~~~~~~~~~~
library.cpp:84:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                         for (int k = 1; k < groups[j / 2].size(); k++)
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~~
library.cpp:77:21: warning: unused variable 'buff' [-Wunused-variable]
   77 |                 int buff = 0, exp = 0;
      |                     ^~~~
library.cpp:100:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         if (nb == groups.size())
      |             ~~~^~~~~~~~~~~~~~~~
library.cpp:104:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for (int j = 0; j < groups[L / 2].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 416 KB # of queries: 1338
2 Correct 8 ms 344 KB # of queries: 1316
3 Correct 15 ms 436 KB # of queries: 1386
4 Correct 14 ms 440 KB # of queries: 1386
5 Correct 19 ms 420 KB # of queries: 1380
6 Correct 17 ms 592 KB # of queries: 1372
7 Correct 15 ms 436 KB # of queries: 1374
8 Correct 18 ms 444 KB # of queries: 1327
9 Correct 13 ms 344 KB # of queries: 1387
10 Correct 8 ms 440 KB # of queries: 820
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 3
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 1 ms 344 KB # of queries: 10
15 Correct 1 ms 344 KB # of queries: 56
16 Correct 2 ms 344 KB # of queries: 118

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 416 KB # of queries: 1338
2 Correct 8 ms 344 KB # of queries: 1316
3 Correct 15 ms 436 KB # of queries: 1386
4 Correct 14 ms 440 KB # of queries: 1386
5 Correct 19 ms 420 KB # of queries: 1380
6 Correct 17 ms 592 KB # of queries: 1372
7 Correct 15 ms 436 KB # of queries: 1374
8 Correct 18 ms 444 KB # of queries: 1327
9 Correct 13 ms 344 KB # of queries: 1387
10 Correct 8 ms 440 KB # of queries: 820
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 3
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 1 ms 344 KB # of queries: 10
15 Correct 1 ms 344 KB # of queries: 56
16 Correct 2 ms 344 KB # of queries: 118
17 Correct 156 ms 444 KB # of queries: 9127
18 Correct 164 ms 592 KB # of queries: 9037
19 Correct 176 ms 440 KB # of queries: 9137
20 Correct 155 ms 600 KB # of queries: 8562
21 Correct 136 ms 592 KB # of queries: 8039
22 Correct 182 ms 692 KB # of queries: 9170
23 Correct 159 ms 696 KB # of queries: 9150
24 Correct 47 ms 344 KB # of queries: 4216
25 Correct 147 ms 448 KB # of queries: 8934
26 Correct 153 ms 444 KB # of queries: 8374
27 Correct 48 ms 680 KB # of queries: 4210
28 Correct 50 ms 344 KB # of queries: 2997
29 Correct 44 ms 344 KB # of queries: 2994
30 Correct 48 ms 344 KB # of queries: 2997