#include "library.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n;
vector<int> g[maxn];
bool visited[maxn];
struct DSU
{
int par[maxn];
vector<int> components[maxn];
void build(int n)
{
for (int i = 1; i <= n; ++i)
{
par[i] = i;
components[i].push_back(i);
}
}
int root(int node)
{
if (node == par[node])
{
return node;
}
return par[node] = root(par[node]);
}
};
DSU dsu;
int divideAndConquer1(int l, int r, const vector<int>& componentRoots, int node)
{
if (l == r)
{
return componentRoots[l];
}
int mid = (l + r) / 2;
vector<int> leftNodes;
for (int i = l; i <= mid; ++i)
{
for (int j = 0; j < dsu.components[componentRoots[i]].size(); ++j)
{
leftNodes.push_back(dsu.components[componentRoots[i]][j]);
}
}
vector<int> takenBooks(n, false);
for (int i = 0; i < leftNodes.size(); ++i)
{
takenBooks[leftNodes[i] - 1] = true;
}
takenBooks[node - 1] = true;
int result = Query(takenBooks);
if (result == mid - l + 1)
{
return divideAndConquer1(l, mid, componentRoots, node);
}
else
{
return divideAndConquer1(mid + 1, r, componentRoots, node);
}
}
pair<int, int> divideAndConquer2(int l, int r, const vector<int>& componentRoots, int node)
{
//cout << "now " << l << " to " << r << endl;
int mid = (l + r) / 2;
vector<int> leftNodes;
for (int i = l; i <= mid; ++i)
{
for (int j = 0; j < dsu.components[componentRoots[i]].size(); ++j)
{
leftNodes.push_back(dsu.components[componentRoots[i]][j]);
}
}
vector<int> takenBooks(n, false);
for (int i = 0; i < leftNodes.size(); ++i)
{
//cout << "adding " << leftNodes[i] << endl;
takenBooks[leftNodes[i] - 1] = true;
}
//cout << "adding " << node << endl;
takenBooks[node - 1] = true;
int result = Query(takenBooks);
//cout << "result = " << result << " :: " << l << " and " << mid << " -> " << mid - l + 1 << endl;
if (result == (mid - l + 1) - 1)
{
return divideAndConquer2(l, mid, componentRoots, node);
}
else if (result == (mid - l + 1) + 1)
{
return divideAndConquer2(mid + 1, r, componentRoots, node);
}
else
{
//cout << "here" << endl;
return make_pair(divideAndConquer1(l, mid, componentRoots, node), divideAndConquer1(mid + 1, r, componentRoots, node));
}
}
void Solve(int N)
{
n = N;
dsu.build(n);
for (int i = 2; i <= n; ++i)
{
vector<int> componentRoots;
for (int j = 1; j <= i - 1; ++j)
{
if (dsu.root(j) == j)
{
//cout << j << " it a root" << endl;
componentRoots.push_back(j);
}
}
vector<int> takenBooks(n, false);
for (int j = 0; j < componentRoots.size(); ++j)
{
for (int k = 0; k < dsu.components[componentRoots[j]].size(); ++k)
{
takenBooks[dsu.components[componentRoots[j]][k] - 1] = true;
}
}
takenBooks[i - 1] = true;
int componentsWith = Query(takenBooks);
int componentsWithout = componentRoots.size();
//cout << "on " << i << " :: " << componentsWith << " and " << componentsWithout << endl;
if (componentsWith == componentsWithout)
{
int whichComponentRoot = divideAndConquer1(0, componentRoots.size() - 1, componentRoots, i);
int firstNode = -1;
int secondNode = -1;
for (int j = 0; j < dsu.components[whichComponentRoot].size(); ++j)
{
int node = dsu.components[whichComponentRoot][j];
if (g[node].size() <= 1)
{
if (firstNode == -1)
{
firstNode = node;
}
else
{
secondNode = node;
}
}
}
vector<int> currentQuery(n, false);
currentQuery[i - 1] = true;
currentQuery[firstNode - 1] = true;
if (Query(currentQuery) == 1)
{
//cout << "connect " << i << " and " << firstNode << endl;
// connect i and first node
g[firstNode].push_back(i);
g[i].push_back(firstNode);
dsu.components[whichComponentRoot].push_back(i);
dsu.par[i] = whichComponentRoot;
}
else
{
//cout << "connect " << i << " and " << secondNode << endl;
// connect i and second node
g[secondNode].push_back(i);
g[i].push_back(secondNode);
dsu.components[whichComponentRoot].push_back(i);
dsu.par[i] = whichComponentRoot;
}
}
else if (componentsWith == componentsWithout - 1)
{
//cout << "before divide and conquer " << endl;
pair<int, int> whichComponentRoots = divideAndConquer2(0, componentRoots.size() - 1, componentRoots, i);
//cout << "after divide and conquer" << endl;
int firstNode = -1;
int secondNode = -1;
for (int j = 0; j < dsu.components[whichComponentRoots.first].size(); ++j)
{
int node = dsu.components[whichComponentRoots.first][j];
if (g[node].size() <= 1)
{
if (firstNode == -1)
{
firstNode = node;
}
else
{
secondNode = node;
}
}
}
vector<int> currentQuery(n, false);
currentQuery[i - 1] = true;
currentQuery[firstNode - 1] = true;
if (Query(currentQuery) == 1)
{
//cout << "connect " << i << " and " << firstNode << endl;
// connect i and first node
g[firstNode].push_back(i);
g[i].push_back(firstNode);
dsu.components[whichComponentRoots.first].push_back(i);
dsu.par[i] = whichComponentRoots.first;
}
else
{
//cout << "connect " << i << " and " << secondNode << endl;
// connect i and second node
g[secondNode].push_back(i);
g[i].push_back(secondNode);
dsu.components[whichComponentRoots.first].push_back(i);
dsu.par[i] = whichComponentRoots.first;
}
currentQuery[i - 1] = false;
currentQuery[firstNode - 1] = false;
firstNode = -1;
secondNode = -1;
for (int j = 0; j < dsu.components[whichComponentRoots.second].size(); ++j)
{
int node = dsu.components[whichComponentRoots.second][j];
if (g[node].size() <= 1)
{
if (firstNode == -1)
{
firstNode = node;
}
else
{
secondNode = node;
}
}
}
currentQuery[i - 1] = true;
currentQuery[firstNode - 1] = true;
if (Query(currentQuery) == 1)
{
//cout << "connect " << i << " and " << firstNode << endl;
// connect i and first node
g[firstNode].push_back(i);
g[i].push_back(firstNode);
dsu.components[whichComponentRoots.second].push_back(i);
dsu.par[i] = whichComponentRoots.second;
}
else
{
//cout << "connect " << i << " and " << secondNode << endl;
// connect i and second node
g[secondNode].push_back(i);
g[i].push_back(secondNode);
dsu.components[whichComponentRoots.second].push_back(i);
dsu.par[i] = whichComponentRoots.second;
}
dsu.par[whichComponentRoots.second] = dsu.par[whichComponentRoots.first];
for (int j = 0; j < dsu.components[whichComponentRoots.second].size(); ++j)
{
dsu.components[whichComponentRoots.first].push_back(dsu.components[whichComponentRoots.second][j]);
}
}
}
int currentNode = -1;
for (int i = 1; i <= n; ++i)
{
if (g[i].size() <= 1)
{
currentNode = i;
break;
}
}
vector<int> ans;
while (ans.size() < n)
{
//cout << "on " << currentNode << endl;
ans.push_back(currentNode);
visited[currentNode] = true;
for (int i = 0; i < g[currentNode].size(); ++i)
{
int nxt = g[currentNode][i];
if (visited[nxt] == false)
{
currentNode = nxt;
break;
}
}
}
Answer(ans);
}
Compilation message
library.cpp: In function 'int divideAndConquer1(int, int, const std::vector<int>&, int)':
library.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int j = 0; j < dsu.components[componentRoots[i]].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int i = 0; i < leftNodes.size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~
library.cpp: In function 'std::pair<int, int> divideAndConquer2(int, int, const std::vector<int>&, int)':
library.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int j = 0; j < dsu.components[componentRoots[i]].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int i = 0; i < leftNodes.size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:147:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for (int j = 0; j < componentRoots.size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
library.cpp:149:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for (int k = 0; k < dsu.components[componentRoots[j]].size(); ++k)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:169:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for (int j = 0; j < dsu.components[whichComponentRoot].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:223:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for (int j = 0; j < dsu.components[whichComponentRoots.first].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:274:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
274 | for (int j = 0; j < dsu.components[whichComponentRoots.second].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:319:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
319 | for (int j = 0; j < dsu.components[whichComponentRoots.second].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:339:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
339 | while (ans.size() < n)
| ~~~~~~~~~~~^~~
library.cpp:345:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
345 | for (int i = 0; i < g[currentNode].size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
752 KB |
# of queries: 1196 |
| 2 |
Correct |
9 ms |
500 KB |
# of queries: 1192 |
| 3 |
Correct |
11 ms |
764 KB |
# of queries: 1256 |
| 4 |
Correct |
8 ms |
752 KB |
# of queries: 1277 |
| 5 |
Correct |
12 ms |
1008 KB |
# of queries: 1247 |
| 6 |
Correct |
10 ms |
1264 KB |
# of queries: 1252 |
| 7 |
Correct |
12 ms |
748 KB |
# of queries: 1262 |
| 8 |
Correct |
12 ms |
760 KB |
# of queries: 1176 |
| 9 |
Correct |
11 ms |
760 KB |
# of queries: 1264 |
| 10 |
Correct |
5 ms |
744 KB |
# of queries: 726 |
| 11 |
Correct |
0 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
344 KB |
# of queries: 2 |
| 13 |
Correct |
0 ms |
344 KB |
# of queries: 4 |
| 14 |
Correct |
0 ms |
344 KB |
# of queries: 7 |
| 15 |
Correct |
1 ms |
344 KB |
# of queries: 48 |
| 16 |
Correct |
1 ms |
484 KB |
# of queries: 110 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
752 KB |
# of queries: 1196 |
| 2 |
Correct |
9 ms |
500 KB |
# of queries: 1192 |
| 3 |
Correct |
11 ms |
764 KB |
# of queries: 1256 |
| 4 |
Correct |
8 ms |
752 KB |
# of queries: 1277 |
| 5 |
Correct |
12 ms |
1008 KB |
# of queries: 1247 |
| 6 |
Correct |
10 ms |
1264 KB |
# of queries: 1252 |
| 7 |
Correct |
12 ms |
748 KB |
# of queries: 1262 |
| 8 |
Correct |
12 ms |
760 KB |
# of queries: 1176 |
| 9 |
Correct |
11 ms |
760 KB |
# of queries: 1264 |
| 10 |
Correct |
5 ms |
744 KB |
# of queries: 726 |
| 11 |
Correct |
0 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
344 KB |
# of queries: 2 |
| 13 |
Correct |
0 ms |
344 KB |
# of queries: 4 |
| 14 |
Correct |
0 ms |
344 KB |
# of queries: 7 |
| 15 |
Correct |
1 ms |
344 KB |
# of queries: 48 |
| 16 |
Correct |
1 ms |
484 KB |
# of queries: 110 |
| 17 |
Correct |
95 ms |
1068 KB |
# of queries: 8533 |
| 18 |
Correct |
97 ms |
1308 KB |
# of queries: 8413 |
| 19 |
Correct |
91 ms |
1056 KB |
# of queries: 8433 |
| 20 |
Correct |
80 ms |
1836 KB |
# of queries: 7900 |
| 21 |
Correct |
82 ms |
1052 KB |
# of queries: 7467 |
| 22 |
Correct |
91 ms |
1588 KB |
# of queries: 8518 |
| 23 |
Correct |
80 ms |
1080 KB |
# of queries: 8524 |
| 24 |
Correct |
35 ms |
1020 KB |
# of queries: 3875 |
| 25 |
Correct |
86 ms |
1596 KB |
# of queries: 8304 |
| 26 |
Correct |
91 ms |
1060 KB |
# of queries: 7750 |
| 27 |
Correct |
31 ms |
1276 KB |
# of queries: 3872 |
| 28 |
Correct |
23 ms |
1040 KB |
# of queries: 1998 |
| 29 |
Correct |
22 ms |
1292 KB |
# of queries: 1996 |
| 30 |
Correct |
19 ms |
1056 KB |
# of queries: 1998 |
