#include <cstdio>
#include <vector>
#include <algorithm>
#include "library.h"
typedef struct cc cc;
struct cc
{
std::vector<int> v;
};
std::vector<cc> All;
std::vector<int> M;
int test(int N, int s, int e, int exclude, int i)
{
int j, k;
for (j = 0; j < N; j++)
M[j] = 0;
for (j = s; j <= e; j++)
{
if (j == exclude) continue;
for (k = 0; k < All[j].v.size(); k++)
M[All[j].v[k]] = 1;
}
M[i] = 1;
int cnt = Query(M);
if (cnt <= (e - s + 1) - (exclude != -1))
return 1;
else
return 0;
}
int checkend(int N, int p, int i)
{
int j, k;
for (j = 0; j < N; j++)
M[j] = 0;
M[All[p].v.back()] = 1;
M[i] = 1;
int cnt = Query(M);
if (cnt == 1)
return 1;
else
return 0;
}
void Solve(int N)
{
int CCo = 0, CCn;
int i, j, k;
for (i = 0; i < N; i++)
M.push_back(0);
cc nothing;
int mn, md, mx, t;
for (i = 0; i < N; i++)
{
// printf("i%d\n", i);
for (j = 0; j <= i; j++)
M[j] = 1;
for (j = i + 1; j < N; j++)
M[j] = 0;
// M[i] = 1;
CCn = Query(M);
if (CCn > CCo)
{
All.push_back(nothing);
All.back().v.push_back(i);
}
else if (CCn == CCo)
{
mn = 0;
mx = All.size() - 1;
while (mn != mx)
{
md = (mn + mx)/2;
if (test(N, mn, md, -1, i))
{
mx = md;
}
else
{
mn = md + 1;
}
}
if (All[mn].v.size() == 1)
All[mn].v.push_back(i);
else
{
if (!checkend(N, mn, i))
std::reverse(All[mn].v.begin(), All[mn].v.end());
All[mn].v.push_back(i);
}
}
else
{
mn = 0;
mx = All.size() - 1;
while (mn != mx)
{
md = (mn + mx)/2;
if (test(N, mn, md, -1, i))
{
mx = md;
}
else
{
mn = md + 1;
}
}
if (All[mn].v.size() == 1)
All[mn].v.push_back(i);
else
{
if (!checkend(N, mn, i))
std::reverse(All[mn].v.begin(), All[mn].v.end());
All[mn].v.push_back(i);
}
t = mn;
// printf("t %d\n", t);
mn = 0;
mx = All.size() - 1;
while (mn != mx)
{
md = (mn + mx)/2;
if (test(N, mn, md, t, i))
{
mx = md;
}
else
{
mn = md + 1;
}
}
if (All[mn].v.size() == 1)
{
for (j = 0; j < All[mn].v.size(); j++)
All[t].v.push_back(All[mn].v[j]);
// printf("ok?\n");
All[mn].v.clear();
All.erase(All.begin() + mn);
// printf("ok?\n");
}
else
{
if (checkend(N, mn, i))
std::reverse(All[mn].v.begin(), All[mn].v.end());
for (j = 0; j < All[mn].v.size(); j++)
All[t].v.push_back(All[mn].v[j]);
// printf("ok?\n");
All[mn].v.clear();
All.erase(All.begin() + mn);
// printf("ok?\n");
}
}
// printf("CC %d\n", CCn);
CCo = CCn;
// printf("All.size() %d\n", All.size());
// for (j = 0; j < All.size(); j++)
// {
// for (k = 0; k < All[j].v.size(); k++)
// printf("%d ", All[j].v[k]);
// printf("\n");
// }
}
std::vector<int> res(N);
for (i = 0; i < N; i++)
{
res[i] = All[0].v[i] + 1;
}
Answer(res);
}
Compilation message
library.cpp: In function 'int test(int, int, int, int, int)':
library.cpp:20:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (k = 0; k < All[j].v.size(); k++)
~~^~~~~~~~~~~~~~~~~
library.cpp: In function 'int checkend(int, int, int)':
library.cpp:32:9: warning: unused variable 'k' [-Wunused-variable]
int j, k;
^
library.cpp: In function 'void Solve(int)':
library.cpp:133:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < All[mn].v.size(); j++)
~~^~~~~~~~~~~~~~~~~~
library.cpp:144:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < All[mn].v.size(); j++)
~~^~~~~~~~~~~~~~~~~~
library.cpp:46:12: warning: unused variable 'k' [-Wunused-variable]
int i, j, k;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1610 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1610 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
