| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58421 |
2018-07-17T19:32:03 Z |
MatheusLealV |
ICC (CEOI16_icc) |
C++17 |
|
204 ms |
852 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)
{
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;
}
//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++)
{
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)
{
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:52: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:54: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:76:39: warning: right operand of comma operator has no effect [-Wunused-value]
ini = 0, fim = esq.size() - 2, mid;
^
icc.cpp:80: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:50: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:127: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! 94 queries used. |
| 2 |
Correct |
12 ms |
616 KB |
Ok! 101 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
616 KB |
Ok! 542 queries used. |
| 2 |
Correct |
64 ms |
724 KB |
Ok! 687 queries used. |
| 3 |
Correct |
68 ms |
724 KB |
Ok! 681 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
186 ms |
728 KB |
Ok! 1471 queries used. |
| 2 |
Correct |
204 ms |
768 KB |
Ok! 1704 queries used. |
| 3 |
Correct |
178 ms |
828 KB |
Ok! 1592 queries used. |
| 4 |
Correct |
172 ms |
828 KB |
Ok! 1544 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
828 KB |
Ok! 1574 queries used. |
| 2 |
Correct |
187 ms |
828 KB |
Ok! 1583 queries used. |
| 3 |
Correct |
177 ms |
828 KB |
Ok! 1614 queries used. |
| 4 |
Correct |
166 ms |
828 KB |
Ok! 1497 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
184 ms |
828 KB |
Ok! 1615 queries used. |
| 2 |
Correct |
175 ms |
828 KB |
Ok! 1614 queries used. |
| 3 |
Correct |
187 ms |
852 KB |
Ok! 1614 queries used. |
| 4 |
Correct |
170 ms |
852 KB |
Ok! 1657 queries used. |
| 5 |
Correct |
167 ms |
852 KB |
Ok! 1486 queries used. |
| 6 |
Correct |
176 ms |
852 KB |
Ok! 1564 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
852 KB |
Ok! 1614 queries used. |
| 2 |
Incorrect |
184 ms |
852 KB |
Too many queries! 1704 out of 1625 |
