제출 #734242

#제출 시각아이디문제언어결과실행 시간메모리
734242Ronin13카멜레온의 사랑 (JOI20_chameleon)C++14
100 / 100
89 ms948 KiB
#include "chameleon.h" #include <vector> #include <bits/stdc++.h> #define pb push_back #define pii pair<int,int> #define f first #define s second using namespace std; namespace { int variable_example = 1; } // namespace const int nmax = 20001; vector <vector <int> > g(nmax); vector <vector <int> > col(2); vector <bool> used(nmax); void dfs(int v, int c){ col[c].pb(v); used[v] = true; for(int to : g[v]){ if(used[to]) continue; dfs(to, c ^ 1); } } bool ask(int a, int b, int x){ vector <int> vec; for(int to : col[b]){ if(vec.size() < x) vec.pb(to); } vec.pb(a); return Query(vec) == vec.size(); } void Solve(int N) { int n = N; for(int i = 1; i <= 2 * n; i++){ for(int j= 1; j < i; j++) if(!used[j]) dfs(j, 0); for(int j= 1;j <= i; j++) used[j] = false; for(int x = 0; x < 2; x++){ //cout << col[x].size() << "\n"; while(!ask(i, x, col[x].size())){ int l = -1, r = col[x].size(); while(l + 1 < r){ int mid = (l + r) / 2; if(!ask(i, x, mid + 1)) r = mid; else l = mid; } if(r == col[x].size()) break; g[i].pb(col[x][r]); g[col[x][r]].pb(i); while(r < (int)col[x].size() - 1) swap(col[x][r], col[x][r + 1]), r++; col[x].pop_back(); } } col[0].clear(); col[1].clear(); } //vector <bool> used(nmax); vector <int> love(nmax); for(int i = 1; i <= 2 * n; i++){ if(g[i].size() == 1){ if(!used[i])Answer(i, g[i][0]); used[i] = used[g[i][0]] = true; } else{ vector <pii> vec; for(int x = 0; x < 3; x++){ for(int y = x + 1; y < 3; y++){ if(Query({i, g[i][x], g[i][y]}) == 2) vec.pb({x, y}); } } int cnt[3]; fill(cnt, cnt + 3, 0); for(auto to : vec) cnt[to.f]++, cnt[to.s]++; for(int j = 0; j < 3; j++){ if(cnt[j] == 2) love[i] = g[i][j]; } } } for(int i= 1; i <= n * 2; i++){ if(used[i]) continue; for(int j = 0; j < 3; j++){ if(love[g[i][j]] != i && love[i] != g[i][j]){ used[g[i][j]] = true, used[i] = true; Answer(g[i][j], i); } } } }

컴파일 시 표준 에러 (stderr) 메시지

chameleon.cpp: In function 'bool ask(int, int, int)':
chameleon.cpp:34:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         if(vec.size() < x)
      |            ~~~~~~~~~~~^~~
chameleon.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     return Query(vec) == vec.size();
      |            ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 if(r == col[x].size()) break;
      |                    ~~^~~~~~~~~~~~~~~~
chameleon.cpp: At global scope:
chameleon.cpp:12:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   12 | int variable_example = 1;
      |     ^~~~~~~~~~~~~~~~
#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...