| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58420 |
2018-07-17T19:30:08 Z |
MatheusLealV |
ICC (CEOI16_icc) |
C++17 |
|
253 ms |
928 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] ++;
}
}
pii Find_Pair(vector<int> esq, vector<int> dir)
{
//cout<<ni<<" "<<esq.size()<<" "<<dir.size()<<"\n";
int ini = 0, fim = dir.size() - 1, mid, best1 = -1, best2 = -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() - 1, 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;
}
//cout<<"ACHEI "<<best1<<" "<<best2<<"\n";
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);
}
}
pii P = Find_Pair(esq, dir);
if(P.f != -1 and P.s != -1)
{
// cout<<"ROAD "<<P.f<<" "<<P.s<<"\n";
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:54: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:56: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:78:39: warning: right operand of comma operator has no effect [-Wunused-value]
ini = 0, fim = esq.size() - 1, mid;
^
icc.cpp:82: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:52: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:133: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 |
11 ms |
504 KB |
Ok! 130 queries used. |
| 2 |
Correct |
11 ms |
648 KB |
Ok! 130 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
648 KB |
Ok! 576 queries used. |
| 2 |
Correct |
66 ms |
704 KB |
Ok! 791 queries used. |
| 3 |
Correct |
63 ms |
724 KB |
Ok! 773 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
160 ms |
780 KB |
Ok! 1525 queries used. |
| 2 |
Correct |
197 ms |
796 KB |
Ok! 1793 queries used. |
| 3 |
Correct |
172 ms |
796 KB |
Ok! 1738 queries used. |
| 4 |
Correct |
173 ms |
848 KB |
Ok! 1651 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
872 KB |
Ok! 1659 queries used. |
| 2 |
Correct |
176 ms |
872 KB |
Ok! 1667 queries used. |
| 3 |
Correct |
215 ms |
872 KB |
Ok! 1737 queries used. |
| 4 |
Correct |
171 ms |
872 KB |
Ok! 1581 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
185 ms |
872 KB |
Ok! 1696 queries used. |
| 2 |
Correct |
253 ms |
928 KB |
Ok! 1736 queries used. |
| 3 |
Correct |
184 ms |
928 KB |
Ok! 1762 queries used. |
| 4 |
Correct |
182 ms |
928 KB |
Ok! 1750 queries used. |
| 5 |
Correct |
161 ms |
928 KB |
Ok! 1572 queries used. |
| 6 |
Correct |
171 ms |
928 KB |
Ok! 1657 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
169 ms |
928 KB |
Too many queries! 1747 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
