oj.uz

Submission #868197

# Submission time Handle Problem Language Result Execution time Memory
868197 2023-10-30T18:15:18 Z borisAngelov Library (JOI18_library) C++17
0 / 100
 53 ms 948 KB 
#include "library.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1005;

int n;

vector<int> g[maxn];

bool visited[maxn];

void Solve(int N)
{
    n = N;

    int startingNode = -1;

    for (int i = 1; i <= n; ++i)
    {
        int l = 1;
        int r = n;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            vector<int> takenBooks(n, false);
            int cnt = 0;

            for (int j = 0; j < mid; ++j)
            {
                ++cnt;
                takenBooks[j] = true;
            }

            int answerWithoutCurrent, answerWithCurrent;

            if (takenBooks[i - 1] == true)
            {
                answerWithCurrent = Query(takenBooks);
                takenBooks[i - 1] = false;
                --cnt;
                answerWithoutCurrent = (cnt == 0 ? 0 : Query(takenBooks));
            }
            else
            {
                answerWithoutCurrent = (cnt == 0 ? 0 : Query(takenBooks));
                takenBooks[i - 1] = true;
                ++cnt;
                answerWithCurrent = Query(takenBooks);
            }

            if (answerWithCurrent <= answerWithoutCurrent)
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }

        //cout << "connecting " << i << " with " << l << endl;

        g[i].push_back(l);

        int l2 = l + 1;
        int r2 = n;

        while (l2 <= r2)
        {
            int mid = (l2 + r2) / 2;

            vector<int> takenBooks(n, false);
            int cnt = 0;

            for (int j = l; j < mid; ++j)
            {
                ++cnt;
                takenBooks[j] = true;
            }

            int answerWithoutCurrent, answerWithCurrent;

            if (takenBooks[i - 1] == true)
            {
                answerWithCurrent = Query(takenBooks);
                takenBooks[i - 1] = false;
                --cnt;
                answerWithoutCurrent = (cnt == 0 ? 0 : Query(takenBooks));
            }
            else
            {
                answerWithoutCurrent = (cnt == 0 ? 0 : Query(takenBooks));
                takenBooks[i - 1] = true;
                ++cnt;
                answerWithCurrent = Query(takenBooks);
            }

            if (answerWithCurrent <= answerWithoutCurrent)
            {
                r2 = mid - 1;
            }
            else
            {
                l2 = mid + 1;
            }
        }

        if (l2 == n + 1)
        {
            startingNode = i;
        }
        else
        {
            //cout << "connecting " << i << " with " << l2 << endl;
            g[i].push_back(l2);
        }
    }

    vector<int> ans;

    int currentNode = startingNode;

    while (ans.size() < n)
    {
        //cout << "now on " << currentNode << endl;

        ans.push_back(currentNode);
        visited[currentNode] = true;

        for (int i = 0; i < g[currentNode].size(); ++i)
        {
            int to = g[currentNode][i];

            if (visited[to] == false)
            {
                currentNode = to;
                break;
            }
        }
    }

    Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:127:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |     while (ans.size() < n)
      |            ~~~~~~~~~~~^~~
library.cpp:134:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for (int i = 0; i < g[currentNode].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 692 KB # of queries: 5580
2 Correct 53 ms 452 KB # of queries: 5582
3 Correct 46 ms 948 KB # of queries: 5864
4 Correct 45 ms 692 KB # of queries: 5904
5 Correct 42 ms 460 KB # of queries: 5890
6 Correct 51 ms 708 KB # of queries: 5894
7 Correct 39 ms 460 KB # of queries: 5886
8 Correct 42 ms 460 KB # of queries: 5630
9 Correct 46 ms 708 KB # of queries: 5862
10 Correct 27 ms 456 KB # of queries: 3446
11 Incorrect 0 ms 344 KB Wrong Answer [5]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 692 KB # of queries: 5580
2 Correct 53 ms 452 KB # of queries: 5582
3 Correct 46 ms 948 KB # of queries: 5864
4 Correct 45 ms 692 KB # of queries: 5904
5 Correct 42 ms 460 KB # of queries: 5890
6 Correct 51 ms 708 KB # of queries: 5894
7 Correct 39 ms 460 KB # of queries: 5886
8 Correct 42 ms 460 KB # of queries: 5630
9 Correct 46 ms 708 KB # of queries: 5862
10 Correct 27 ms 456 KB # of queries: 3446
11 Incorrect 0 ms 344 KB Wrong Answer [5]
12 Halted 0 ms 0 KB -