제출 #441576

#제출 시각아이디문제언어결과실행 시간메모리
441576blueLibrary (JOI18_library)C++17
100 / 100
383 ms576 KiB
#include "library.h" #include <vector> #include <iostream> using namespace std; const int maxN = 1000; int N1; int ask_vector(vector<int> Q) { vector<int> M(N1, 0); for(int q:Q) M[q-1] = 1; return Query(M); } vector<int> neighbors[1+maxN]; bool neighboring(int i, int j) { bool flag = 0; for(int x: neighbors[i]) if(x == j) flag = 1; return flag; } void find_neighbors(int I, vector<int> Q, int lo, int hi) { // cerr << "find_neighbors " << I << ", "; // for(int q:Q) cerr << q << ' '; // cerr << '\n'; if(Q.size() == 0) return; else if(hi == 0) return; else if(neighbors[I].size() == 2) return; else if(Q.size() == 1) { if (lo >= 1 || ask_vector(vector<int>{I, Q[0]}) == 1) { neighbors[I].push_back(Q[0]); neighbors[Q[0]].push_back(I); } } else { vector<int> Q1, Q2; for(int i = 0; i < Q.size()/2; i++) Q1.push_back(Q[i]); for(int i = Q.size()/2; i < Q.size(); i++) Q2.push_back(Q[i]); int noI = ask_vector(Q1); Q1.push_back(I); int withI = ask_vector(Q1); Q1.pop_back(); int neighbors_of_I = noI - withI + 1; find_neighbors(I, Q1, neighbors_of_I, neighbors_of_I); find_neighbors(I, Q2, max(0, lo - neighbors_of_I), hi - neighbors_of_I); } } void Solve(int N) { N1 = N; for(int i = 1; i <= N; i++) { if(neighbors[i].size() == 2) continue; vector<int> Q; for(int j = 1; j <= N; j++) { if(i != j && !neighboring(i, j)) Q.push_back(j); } find_neighbors(i, Q, 0, 2); } vector<int> visit(N+1, 0); vector<int> res; for(int i = 1; i <= N; i++) { if(neighbors[i].size() <= 1) { res.push_back(i); visit[i] = 1; break; } } for(int i = 0; i < N; i++) { int u = res[i]; for(int v: neighbors[u]) { if(visit[v]) continue; visit[v] = 1; res.push_back(v); } } // for(int r:res) cerr << r << ' '; // cerr << '\n'; for(int r:res) cerr << r << ' '; cerr << '\n'; Answer(res); }

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

library.cpp: In function 'void find_neighbors(int, std::vector<int>, int, int)':
library.cpp:45:26: 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 < Q.size()/2; i++) Q1.push_back(Q[i]);
      |                        ~~^~~~~~~~~~~~
library.cpp:46:35: 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 = Q.size()/2; i < Q.size(); i++) Q2.push_back(Q[i]);
      |                                 ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...