| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 605240 |
2022-07-25T14:33:23 Z |
chirathnirodha |
ICC (CEOI16_icc) |
C++17 |
|
30 ms |
428 KB |
#include "icc.h"
#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define I insert
using namespace std;
int n;
int uni[101];
vector<int> v[101];
void solve(vector<int> vc){
set<int> s;s.I(-1);s.I(vc.size()-1);
vector<int> a,b;
while(true){
vector<int> v1,v2,v3;
a.clear();b.clear();
auto itr=s.begin();
while(true){
int l=*itr;l++;
itr++;if(itr==s.end())break;
int r=*itr;
int m=(l+r)/2;
v3.PB(m);
for(int i=l;i<=m;i++){
a.PB(vc[i]);
for(int j=0;j<v[vc[i]].size();j++)v1.PB(v[vc[i]][j]);
}
for(int i=m+1;i<=r;i++){
b.PB(vc[i]);
for(int j=0;j<v[vc[i]].size();j++)v1.PB(v[vc[i]][j]);
}
}
int arr1[v1.size()],arr2[v2.size()];
for(int i=0;i<v1.size();i++)arr1[i]=v1[i];
for(int i=0;i<v2.size();i++)arr2[i]=v2[i];
bool bl=query(v1.size(),v2.size(),arr1,arr2);
if(bl)break;
for(int i=0;i<v3.size();i++)s.I(v3[i]);
}
while(true){
if(a.size()==1 && b.size()==1)break;
vector<int> v1,v2,v3;
if(a.size()<b.size()){
vector<int> c;
for(int i=0;i<a.size();i++)c.PB(a[i]);
a.clear();
for(int i=0;i<b.size();i++)a.PB(b[i]);
b.clear();
for(int i=0;i<c.size();i++)b.PB(c[i]);
}
int m=(0+a.size()-1)/2;
for(int i=0;i<=m;i++){
for(int j=0;j<v[a[i]].size();j++)v1.PB(v[a[i]][j]);
}
for(int i=0;i<b.size();i++){
for(int j=0;j<v[b[i]].size();j++)v2.PB(v[b[i]][j]);
}
int arr1[v1.size()],arr2[v2.size()];
for(int i=0;i<v1.size();i++)arr1[i]=v1[i];
for(int i=0;i<v2.size();i++)arr2[i]=v2[i];
bool bl=query(v1.size(),v2.size(),arr1,arr2);
if(bl)for(int i=0;i<=m;i++)v3.PB(a[i]);
else for(int i=m+1;i<a.size();i++)v3.PB(a[i]);
a.clear();
for(int i=0;i<v3.size();i++)a.PB(v3[i]);
}
setRoad(a[0],b[0]);
for(int i=0;i<n;i++){
if(uni[i]==uni[b[0]]){
uni[i]=uni[a[0]];
v[uni[a[0]]].PB(i);
}
}
v[b[0]].clear();
}
void run(int N){
n=N;
for(int i=1;i<=n;i++){
uni[i]=i;
v[i].PB(i);
}
for(int i=0;i<n-1;i++){
vector<int> remu;
for(int i=0;i<n;i++)if(v[i].size()>0)remu.PB(i);
solve(remu);
}
}
Compilation message
icc.cpp: In function 'void solve(std::vector<int>)':
icc.cpp:27:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int j=0;j<v[vc[i]].size();j++)v1.PB(v[vc[i]][j]);
| ~^~~~~~~~~~~~~~~~
icc.cpp:31:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int j=0;j<v[vc[i]].size();j++)v1.PB(v[vc[i]][j]);
| ~^~~~~~~~~~~~~~~~
icc.cpp:35:22: 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=0;i<v1.size();i++)arr1[i]=v1[i];
| ~^~~~~~~~~~
icc.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i=0;i<v2.size();i++)arr2[i]=v2[i];
| ~^~~~~~~~~~
icc.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0;i<v3.size();i++)s.I(v3[i]);
| ~^~~~~~~~~~
icc.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0;i<a.size();i++)c.PB(a[i]);
| ~^~~~~~~~~
icc.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=0;i<b.size();i++)a.PB(b[i]);
| ~^~~~~~~~~
icc.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0;i<c.size();i++)b.PB(c[i]);
| ~^~~~~~~~~
icc.cpp:54:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int j=0;j<v[a[i]].size();j++)v1.PB(v[a[i]][j]);
| ~^~~~~~~~~~~~~~~
icc.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i=0;i<b.size();i++){
| ~^~~~~~~~~
icc.cpp:57:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int j=0;j<v[b[i]].size();j++)v2.PB(v[b[i]][j]);
| ~^~~~~~~~~~~~~~~
icc.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i=0;i<v1.size();i++)arr1[i]=v1[i];
| ~^~~~~~~~~~
icc.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=0;i<v2.size();i++)arr2[i]=v2[i];
| ~^~~~~~~~~~
icc.cpp:65:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | else for(int i=m+1;i<a.size();i++)v3.PB(a[i]);
| ~^~~~~~~~~
icc.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i=0;i<v3.size();i++)a.PB(v3[i]);
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
340 KB |
Number of queries more than 3000 out of 1500 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
400 KB |
Number of queries more than 5000 out of 2500 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
340 KB |
Number of queries more than 4500 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
428 KB |
Number of queries more than 4000 out of 2000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
340 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
428 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
