Submission #212423

#TimeUsernameProblemLanguageResultExecution timeMemory
212423RayaabualjamalChameleon's Love (JOI20_chameleon)C++14
Compilation error
0 ms0 KiB
//To build sub vectors easily: vector <int> sub_vector(int b, int e, vector <int>& f){ vector <int> r(e-b); rep(i,0,e-b){ r[i]=f[i+b]; } return r; } //To binary search: int binary(int s, int ee, int e, vector <int>& curr){ int start=s, end = ee; while(start<end-1) { int middle = (start+end)/2; vector <int> sub = sub_vector(middle,e, curr); // for(int i:sub){ // cout << i << " "; // } //cout << endl; int see = Query(sub); if(sub.size()==see) end=middle; else start=middle; } return start; } //visited is to not Answer the same couple twice vector <bool> visited; //verti is where I keep the special vertices for each vertex vector <vector <int> > verti; vector <pair <int, int> > graph; //dfs to build the graph: void dfs(int p){ vector <int> ch = {0,0,0}; if(graph[p].first!=-1&&graph[p].second!=-1){ return ; } rep(i,0,3){ bool f = 0; rep(j,i+1,3){ if(i==j)continue; vector <int> ctry = {p, verti[p][i], verti[p][j]}; if(Query(ctry)==1){ ch[i]++; ch[j]++; f = 1; break; } } if(f)break; } rep(i,0,3){ if(ch[i]==0){ graph[p].second = verti[p][i]; graph[verti[p][i]].first = p; dfs(verti[p][i]); } } return ; } void Solve(int N) { int n=N*2; vector <vector <int> > v(4); verti.resize(n+1); visited.assign(n+1,0); graph.assign(n+1,{-1,-1}); // loop thro all vertices: rep(i,1, n+1){ vector <int> curr; vector<int> which= {-1,-1,-1,-1}; //find all special vertices for this vertex: rep(j,0,4){ curr = v[j]; curr.push_back(i); int check = Query(curr); //if it has no special vertices in this vector store it's size: if(check==curr.size()){ which[j]=curr.size(); continue; } int start = 0, end = curr.size(); //binary seach all possible special vertices that is in this vector: while(check!=curr.size()){ int remov = binary(start, end, curr.size(), curr); verti[i].push_back(curr[remov]); verti[curr[remov]].push_back(i); end = remov; curr.erase (curr.begin()+remov); //check if there is still a special vertex: check = Query(curr); } } //choose the place that has the least size to insert 'i' in it int place = 5, capasity = 0; rep(i,0,4){ if(which[i]!=-1&& capasity<which[i]){ place=i; } } v[place].push_back(i); } rep(i,1,n+1){ //if already done skip if(visited[i])continue; //if it has a only one kid if(verti[i].size()==1){ Answer(i,verti[i][0]); visited[i]=1; visited[verti[i][0]]=1; } else if(verti[i].size()>1&& graph[i].first!=-1){ //if it's graph was built: get the answer rep(j,0,3){ if(verti[i][j]!=graph[i].first&& verti[i][j]!=graph[i].second){ Answer(i,verti[i][j]); visited[i]=1; visited[verti[i][j]]=1; } } } else if(verti[i].size()>1){ //if it's graph was not built: build the graph then answer dfs(i); rep(j,0,3){ if(verti[i][j]!=graph[i].first&& verti[i][j]!=graph[i].second){ Answer(i,verti[i][j]); visited[i]=1; visited[verti[i][j]]=1; } } } } }

Compilation message (stderr)

chameleon.cpp:2:1: error: 'vector' does not name a type
 vector <int> sub_vector(int b, int e, vector <int>& f){
 ^~~~~~
chameleon.cpp:10:34: error: 'vector' has not been declared
 int binary(int s, int ee, int e, vector <int>& curr){
                                  ^~~~~~
chameleon.cpp:10:41: error: expected ',' or '...' before '<' token
 int binary(int s, int ee, int e, vector <int>& curr){
                                         ^
chameleon.cpp: In function 'int binary(int, int, int, int)':
chameleon.cpp:15:9: error: 'vector' was not declared in this scope
         vector <int> sub = sub_vector(middle,e, curr);
         ^~~~~~
chameleon.cpp:15:17: error: expected primary-expression before 'int'
         vector <int> sub = sub_vector(middle,e, curr);
                 ^~~
chameleon.cpp:20:25: error: 'sub' was not declared in this scope
         int see = Query(sub);
                         ^~~
chameleon.cpp:20:19: error: 'Query' was not declared in this scope
         int see = Query(sub);
                   ^~~~~
chameleon.cpp: At global scope:
chameleon.cpp:29:1: error: 'vector' does not name a type
 vector <bool> visited;
 ^~~~~~
chameleon.cpp:31:1: error: 'vector' does not name a type
 vector <vector <int> > verti;
 ^~~~~~
chameleon.cpp:32:1: error: 'vector' does not name a type
 vector <pair <int, int> > graph;
 ^~~~~~
chameleon.cpp: In function 'void dfs(int)':
chameleon.cpp:35:5: error: 'vector' was not declared in this scope
     vector <int> ch = {0,0,0};
     ^~~~~~
chameleon.cpp:35:13: error: expected primary-expression before 'int'
     vector <int> ch = {0,0,0};
             ^~~
chameleon.cpp:36:8: error: 'graph' was not declared in this scope
     if(graph[p].first!=-1&&graph[p].second!=-1){
        ^~~~~
chameleon.cpp:39:9: error: 'i' was not declared in this scope
     rep(i,0,3){
         ^
chameleon.cpp:39:5: error: 'rep' was not declared in this scope
     rep(i,0,3){
     ^~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:64:5: error: 'vector' was not declared in this scope
     vector <vector <int> > v(4);
     ^~~~~~
chameleon.cpp:64:21: error: expected primary-expression before 'int'
     vector <vector <int> > v(4);
                     ^~~
chameleon.cpp:65:5: error: 'verti' was not declared in this scope
     verti.resize(n+1);
     ^~~~~
chameleon.cpp:66:5: error: 'visited' was not declared in this scope
     visited.assign(n+1,0);
     ^~~~~~~
chameleon.cpp:67:5: error: 'graph' was not declared in this scope
     graph.assign(n+1,{-1,-1});
     ^~~~~
chameleon.cpp:69:9: error: 'i' was not declared in this scope
     rep(i,1, n+1){
         ^
chameleon.cpp:69:5: error: 'rep' was not declared in this scope
     rep(i,1, n+1){
     ^~~