| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58424 |
2018-07-17T19:49:54 Z |
MatheusLealV |
ICC (CEOI16_icc) |
C++17 |
|
235 ms |
880 KB |
#include "icc.h"
#define N 105
#define f first
#define s second
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
set<int> grafo[N];
int pai[N], peso[N], ni;
vector<int> el[N];
int Find(int x)
{
if(x == pai[x]) return x;
return pai[x] = Find(pai[x]);
}
void join(int a, int b)
{
a = Find(a), b = Find(b);
if(a == b) return;
if(peso[a] > peso[b])
{
pai[b] = a;
for(auto x: el[b]) el[a].push_back(x);
}
else if(peso[a] <= peso[b])
{
pai[a] = b;
for(auto x: el[a]) el[b].push_back(x);
if(peso[a] == peso[b]) peso[b] ++;
}
}
inline pii Find_Pair(vector<int> esq, vector<int> dir)
{
int ini = 0, fim = dir.size() - 2, mid, best1 = dir.size() - 1, best2 = esq.size() - 1;
int A[N], idl = 0, aux[N], idaux = 0;
for(int i = 0; i < esq.size(); i++) A[idl] = esq[i], idl ++;
for(int i = 0; i < dir.size(); i++) aux[i] = dir[i];
if(!query((int)esq.size(), (int) dir.size(), A, aux)) return {-1, -1};
while(fim >= ini)
{
mid = (ini + fim)/2;
int B[N], idr = 0;
for(int i = 0; i <= mid; i++) B[idr] = dir[i], idr ++;
if(query(idl, idr, A, B))
{
best1 = mid;
fim = mid - 1;
}
else ini = mid + 1;
}
ini = 0, fim = esq.size() - 2, mid;
idl = 0;
for(int i = 0; i < dir.size(); i++) A[idl] = dir[i], idl ++;
while(fim >= ini)
{
mid = (ini + fim)/2;
int B[N], idr = 0;
for(int i = 0; i <= mid; i++) B[idr] = esq[i], idr ++;
if(query(idl, idr, A, B))
{
best2 = mid;
fim = mid - 1;
}
else ini = mid + 1;
}
if(best1 == -1 and best2 == -1) return {-1, -1};
return {dir[best1], esq[best2]};
}
void run(int n)
{
ni = n;
for(int i = 1; i <= n; i++) pai[i] = i, el[i].push_back(i);
for(int i = 1; i < n; i++)
{
set<int> aux; vector<int> val;
for(int i = 1; i <= n; i++) aux.insert(Find(i));
for(auto x: aux) val.push_back(x);
vector<int> bits;
for(int k = 0; k < 7; k++) bits.push_back(k);
random_shuffle(bits.begin(), bits.end());
for(auto k: bits)
{
vector<int> esq, dir;
for(int i = 0; i < val.size(); i++)
{
if(i & (1<<k))
{
int x = val[i];
for(auto v: el[x]) esq.push_back(v);
}
else
{
int x = val[i];
for(auto v: el[x]) dir.push_back(v);
}
}
if(esq.size() == 0 or dir.size() == 0) continue;
pii P = Find_Pair(esq, dir);
if(P.f != -1 and P.s != -1)
{
setRoad(P.f, P.s);
join(P.f, P.s);
break;
}
}
}
}
Compilation message
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
#define s second
^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
#define s second
^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
#define s second
^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
#define s second
^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
#define s second
^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
#define s second
^
icc.cpp: In function 'pii Find_Pair(std::vector<int>, std::vector<int>)':
icc.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < esq.size(); i++) A[idl] = esq[i], idl ++;
~~^~~~~~~~~~~~
icc.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < dir.size(); i++) aux[i] = dir[i];
~~^~~~~~~~~~~~
icc.cpp:75:39: warning: right operand of comma operator has no effect [-Wunused-value]
ini = 0, fim = esq.size() - 2, mid;
^
icc.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < dir.size(); i++) A[idl] = dir[i], idl ++;
~~^~~~~~~~~~~~
icc.cpp:49:32: warning: unused variable 'idaux' [-Wunused-variable]
int A[N], idl = 0, aux[N], idaux = 0;
^~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:128:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < val.size(); i++)
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
504 KB |
Ok! 106 queries used. |
| 2 |
Correct |
9 ms |
612 KB |
Ok! 105 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
664 KB |
Ok! 532 queries used. |
| 2 |
Correct |
54 ms |
740 KB |
Ok! 690 queries used. |
| 3 |
Correct |
55 ms |
740 KB |
Ok! 680 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
848 KB |
Ok! 1474 queries used. |
| 2 |
Correct |
173 ms |
848 KB |
Ok! 1701 queries used. |
| 3 |
Correct |
173 ms |
848 KB |
Ok! 1641 queries used. |
| 4 |
Correct |
177 ms |
848 KB |
Ok! 1548 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
167 ms |
880 KB |
Ok! 1505 queries used. |
| 2 |
Correct |
196 ms |
880 KB |
Ok! 1605 queries used. |
| 3 |
Correct |
229 ms |
880 KB |
Ok! 1637 queries used. |
| 4 |
Correct |
178 ms |
880 KB |
Ok! 1508 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
880 KB |
Ok! 1647 queries used. |
| 2 |
Correct |
192 ms |
880 KB |
Ok! 1662 queries used. |
| 3 |
Correct |
193 ms |
880 KB |
Ok! 1674 queries used. |
| 4 |
Correct |
181 ms |
880 KB |
Ok! 1652 queries used. |
| 5 |
Correct |
235 ms |
880 KB |
Ok! 1528 queries used. |
| 6 |
Correct |
193 ms |
880 KB |
Ok! 1585 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
880 KB |
Too many queries! 1650 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
