| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1026043 |
2024-07-17T13:20:51 Z |
faruk |
ICC (CEOI16_icc) |
C++17 |
|
1 ms |
604 KB |
#include "icc.h"
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> pii;
vector<vector<int> > components;
bool query(vector<int> a, vector<int> b) {
int a_niz[a.size()], b_niz[b.size()];
for (int i = 0; i < a.size(); i++)
a_niz[i] = a[i];
for (int i = 0; i < b.size(); i++)
b_niz[i] = b[i];
return query(a.size(), b.size(), a_niz, b_niz);
}
void merge_components(int a, int b) {
if (a > b)
swap(a, b);
vector<int> neww_component = components[a];
neww_component.insert(neww_component.end(), all(components[b]));
components.erase(components.begin() + b);
components.erase(components.begin() + a);
components.push_back(neww_component);
}
bool components_query(vector<int> a, vector<int> b) {
vector<int> newa, newb;
for (int i : a)
newa.insert(newa.end(), all(components[i]));
for (int i : b)
newb.insert(newb.end(), all(components[i]));
return query(newa, newb);
}
pii find_edge_from_true_query(vector<int> a, vector<int> b) {
pii out;
int l = 0, r = a.size();
while (l < r) {
int mid = (l + r) / 2;
if (query(vector<int>(a.begin(), a.begin() + mid + 1), b))
r = mid, out.first = mid;
else
l = mid + 1;
}
l = 0, r = b.size();
while (l < r) {
int mid = (l + r) / 2;
if (query(a, vector<int>(b.begin(), b.begin() + mid + 1)))
r = mid, out.second = mid;
else
l = mid + 1;
}
return out;
}
void run(int n) {
for (int i = 1; i <= n; i++)
components.push_back(vector<int>(1, i));
for (int i = 0; i < n - 1; i++) {
vector<int> find_a, find_b;
for (int bit = 0; bit < 23; bit++)
{
vector<int> cmp1, cmp2;
for (int i = 0; i < components.size(); i++)
{
if (i & (1 << bit))
cmp1.push_back(i);
else
cmp2.push_back(i);
}
if (components_query(cmp1, cmp2)) {
find_a = cmp1, find_b = cmp2;
break;
}
}
pii edge = find_edge_from_true_query(find_a, find_b);
setRoad(edge.first, edge.second);
merge_components(edge.first, edge.second);
}
}
Compilation message
icc.cpp: In function 'bool query(std::vector<int>, std::vector<int>)':
icc.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
icc.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for (int i = 0; i < b.size(); i++)
| ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:70:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i = 0; i < components.size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
Query cities not in range [1, n] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
Query cities not in range [1, n] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Query cities not in range [1, n] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Query cities not in range [1, n] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Query cities not in range [1, n] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Query cities not in range [1, n] |
| 2 |
Halted |
0 ms |
0 KB |
- |
