Submission #212405

#TimeUsernameProblemLanguageResultExecution timeMemory
212405RayaabualjamalChameleon's Love (JOI20_chameleon)C++14
44 / 100
64 ms424 KiB
#include <iostream> #include <string> #include <vector> #include <map> #include <set> #include <algorithm> #include <cmath> #include <queue> #include <iomanip> #define rep(i, a, b) for (int i = a; i < b; i++) #define per(j, a, b) for (int j = a; j >= b; j--) #include "chameleon.h" #include <cstdio> #include <cstdlib> using namespace std; 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; } 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); int see = Query(sub); if(sub.size()==see) end=middle; else start=middle; } return start; } vector <bool> visited; vector <vector <int> > verti; vector <pair <int, int> > 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){ rep(j,i+1,3){ if(i==j)continue; vector <int> ctry = {p, verti[p][i], verti[p][j]}; if(Query(ctry)==2){ ch[i]++; ch[j]++; } } } rep(i,0,3){ if(ch[i]==2){ 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}); rep(i,1, n+1){ vector <int> curr; bool flag = false; rep(j,0,4){ curr = v[j]; curr.push_back(i); int check = Query(curr); if(check==curr.size()&& !flag){ v[j].push_back(i); flag = true; continue; } while(check!=curr.size()){ int remov = binary(0, curr.size(), curr.size(), curr); verti[i].push_back(curr[remov]); verti[curr[remov]].push_back(i); curr.erase (curr.begin()+remov); check = Query(curr); } } } // rep(i,0,4){ // cout << i << ": "; // rep(j,0,v[i].size()){ // cout << v[i][j] << " "; // } // cout << endl; // } // rep(i,1,n+1){ // cout << i << ": "; // rep(j,0,verti[i].size()){ // cout << verti[i][j] << " "; // } // cout << endl; // } rep(i,1,n+1){ if(visited[i])continue; if(verti[i].size()==1){ //cout << " 1 "<< i << " " << verti[i][0] << endl; Answer(i,verti[i][0]); visited[i]=1; visited[verti[i][0]]=1; } else if(verti[i].size()>1&& graph[i].first!=-1){ rep(j,0,3){ if(verti[i][j]!=graph[i].first&& verti[i][j]!=graph[i].second){ //cout << " 2 " << i << " " << verti[i][j] << endl; Answer(i,verti[i][j]); visited[i]=1; visited[verti[i][j]]=1; } } } else if(verti[i].size()>1){ dfs(i); rep(j,0,3){ if(verti[i][j]!=graph[i].first&& verti[i][j]!=graph[i].second){ //cout << " 3 " << i << " " << verti[i][j] << endl; Answer(i,verti[i][j]); visited[i]=1; visited[verti[i][j]]=1; } } } } }

Compilation message (stderr)

chameleon.cpp: In function 'int binary(int, int, int, std::vector<int>&)':
chameleon.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(sub.size()==see)
            ~~~~~~~~~~^~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:80:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(check==curr.size()&& !flag){
                ~~~~~^~~~~~~~~~~~~
chameleon.cpp:85:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(check!=curr.size()){
                   ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...