Submission #1091115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091115		raphaelp	Library (JOI18_library)	C++14	100 / 100	182 ms	696 KiB

library

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

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