Submission #868197

#	Time	Username	Problem	Language	Result	Execution time	Memory
868197		borisAngelov	Library (JOI18_library)	C++17	0 / 100	53 ms	948 KiB

library

#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 (stderr)

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
• Subtask 2: 0 / 81