| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 966710 |
2024-04-20T08:42:13 Z |
berr |
ICC (CEOI16_icc) |
C++17 |
|
6 ms |
604 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
vector<int> vis(101);
int que(vector<int> a, vector<int> b){
int x[a.size()], y[b.size()];
int siz_a = a.size(), siz_b=b.size();
for(int i=0; i<siz_a; i++){
x[i] = a[i];
}
for(int i=0; i<siz_b; i++){
y[i] = b[i];
}
return query(siz_a, siz_b, x, y);
}
void coz(vector<int> a, vector<int> b){
while(a.size()>1){
vector<int> pf;
for(int i=0; i<a.size()/2; i++){
pf.push_back(a[i]);
}
if(que(pf, b)){
a= pf;
}
else{
pf.clear();
for(int i=a.size()/2; i<a.size(); i++){
pf.push_back(a[i]);
}
a=pf;
}
}
while(b.size()>1){
vector<int> pf;
for(int i=0; i<b.size()/2; i++){
pf.push_back(b[i]);
}
if(que(a, b)){
b= pf;
}
else{
pf.clear();
for(int i=b.size()/2; i<b.size(); i++){
pf.push_back(b[i]);
}
b=pf;
}
}
vis[a[0]]=1; vis[b[0]]=1;
setRoad(a[0], b[0]);
}
void run(int n){
for(int i=0; i<=n; i++) vis[i]=0;
for(int i=0; i<n-1; i++){
vector<int> unvisited, visited;
for(int l=1; l<=n; l++){
if(vis[l]) visited.push_back(l);
else unvisited.push_back(l);
}
if(visited.size()==0 || !que(unvisited, visited)){
vector<int> all = unvisited;
vector<int> a, b;
int size_all = all.size();
for(int i=0; i<size_all; i++){
if(i<size_all/2) a.push_back(all[i]);
else b.push_back(all[i]);
}
if(que(a, b)){
break;
}
else{
vector<vector<int>> aa;
vector<vector<int>> bb;
aa.push_back(a);
bb.push_back(b);
while(1){
vector<vector<int>> new_aa;
vector<vector<int>> new_bb;
int sa=0, sb=0;
for(auto i: aa){
vector<int> ay, by;
for(int l=0; l<i.size(); l++){
if(l<i.size()/2){
ay.push_back(i[l]);
sa++;
}
else if(l==i.size()/2 && i.size()%2){
if(sa+1 <= sb+i.size()/2){
ay.push_back(i[l]);
sa++;
}
else{
by.push_back(i[l]);
sb++;
}
}
else{
by.push_back(i[l]);
sb++;
}
}
if(ay.size()==0||by.size()==0) continue;
else{
new_aa.push_back(ay);
new_bb.push_back(by);
}
}
for(auto i: bb){
vector<int> ay, by;
for(int l=0; l<i.size(); l++){
if(l<i.size()/2){
ay.push_back(i[l]);
sa++;
}
else if(l==i.size()/2 && i.size()%2){
if(sa+1 <= sb+i.size()/2){
ay.push_back(i[l]);
sa++;
}
else{
by.push_back(i[l]);
sb++;
}
}
else{
by.push_back(i[l]);
sb++;
}
}
if(ay.size()==0||by.size()==0) continue;
else{
new_aa.push_back(ay);
new_bb.push_back(by);
}
}
vector<int> ca, cb;
for(auto i: new_aa)
for(auto l: i) ca.push_back(l);
for(auto i: new_bb)
for(auto l: i)
cb.push_back(l);
if(que(ca, cb)){
int s=-1;
auto check=[&](int val){
vector<int> pf, fp;
for(int i=0; i<=val; i++){
for(auto l: new_aa[i]){
pf.push_back(l);
}
for(auto l: new_bb[i]){
fp.push_back(l);
}
}
if(que(pf, fp)) return 1;
return 0;
};
for(int j=6; j>=0; j--){
int tmp = s+(1<<j);
if(tmp <new_aa.size()-1){
if(check(tmp)) continue;
s = tmp;
}
}
a=new_aa[s+1]; b=new_bb[s+1];
break;
}
else{
aa=new_aa; bb=new_bb;
}
}
}
coz(a, b);
}
else{
coz(visited, unvisited);
}
}
}
Compilation message
icc.cpp: In function 'void coz(std::vector<int>, std::vector<int>)':
icc.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int i=0; i<a.size()/2; i++){
| ~^~~~~~~~~~~
icc.cpp:35:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i=a.size()/2; i<a.size(); i++){
| ~^~~~~~~~~
icc.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0; i<b.size()/2; i++){
| ~^~~~~~~~~~~
icc.cpp:54:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=b.size()/2; i<b.size(); i++){
| ~^~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:105:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int l=0; l<i.size(); l++){
| ~^~~~~~~~~
icc.cpp:106:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | if(l<i.size()/2){
| ~^~~~~~~~~~~
icc.cpp:110:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | else if(l==i.size()/2 && i.size()%2){
| ~^~~~~~~~~~~~
icc.cpp:111:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | if(sa+1 <= sb+i.size()/2){
| ~~~~~^~~~~~~~~~~~~~~~
icc.cpp:136:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int l=0; l<i.size(); l++){
| ~^~~~~~~~~
icc.cpp:137:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | if(l<i.size()/2){
| ~^~~~~~~~~~~
icc.cpp:141:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | else if(l==i.size()/2 && i.size()%2){
| ~^~~~~~~~~~~~
icc.cpp:142:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | if(sa+1 <= sb+i.size()/2){
| ~~~~~^~~~~~~~~~~~~~~~
icc.cpp:194:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | if(tmp <new_aa.size()-1){
| ~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
Not all edges were guessed! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Not all edges were guessed! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
604 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
600 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
