제출 #604116

#제출 시각아이디문제언어결과실행 시간메모리
604116AlperenT통행료 (IOI18_highway)C++17
0 / 100
213 ms262144 KiB
#include <bits/stdc++.h> #include "highway.h" using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = 9e4, K = 10; vector<pair<int, int>> graph[N]; vector<int> ones, zeros; void dfs(int v, int p, bool flag){ if(flag) ones.push_back(v); else zeros.push_back(v); for(auto e : graph[v]){ if(e.first != p){ dfs(e.first, v, flag ^ 1); } } } void find_pair(int n, vector<int> u, vector<int> v, int a, int b){ int m = u.size(), s = -1, t = -1; for(int i = 0; i < m; i++){ graph[u[i]].push_back({v[i], i}); graph[v[i]].push_back({u[i], i}); } vector<int> tmp(m, 0); long long dist = ask(tmp); dfs(0, -1, 0); if(zeros.size() > ones.size()) swap(zeros, ones); for(auto x : ones) cout << x << " "; cout << "\n"; for(auto x : zeros) cout << x << " "; cout << "\n"; tmp.assign(m, 0); for(auto v : ones){ for(auto e : graph[v]){ tmp[e.second] = 1; } } if(((ask(tmp) - dist) / (b - a)) % 2 == 1){ int l = 0, r = ones.size(), md; while(r - l > 1){ md = l + (r - l) / 2; tmp.assign(m, 0); for(int i = 0; i < md; i++){ int v = ones[i]; for(auto e : graph[v]) tmp[e.second] = 1; } if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md; else l = md; } s = ones[l]; l = 0, r = zeros.size(); while(r - l > 1){ md = l + (r - l) / 2; tmp.assign(m, 0); for(int i = 0; i < md; i++){ int v = zeros[i]; for(auto e : graph[v]) tmp[e.second] = 1; } if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md; else l = md; } t = zeros[l]; answer(s, t); return; } else{ for(int it = 0; it < K; it++){ shuffle(ones.begin(), ones.end(), rng); tmp.assign(m, 0); for(int i = 0; i <= (ones.size() - 1) / 2; i++){ int v = ones[i]; for(auto e : graph[v]) tmp[e.second] = 1; } if(((ask(tmp) - dist) / (b - a)) % 2 == 1){ vector<int> seta, setb; for(int i = 0; i <= (ones.size() - 1) / 2; i++) seta.push_back(ones[i]); for(int i = (ones.size() - 1) / 2 + 1; i < ones.size(); i++) setb.push_back(ones[i]); int l = 0, r = seta.size(), md; while(r - l > 1){ md = l + (r - l) / 2; tmp.assign(m, 0); for(int i = 0; i < md; i++){ int v = seta[i]; for(auto e : graph[v]) tmp[e.second] = 1; } if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md; else l = md; } s = seta[l]; l = 0, r = setb.size(); while(r - l > 1){ md = l + (r - l) / 2; tmp.assign(m, 0); for(int i = 0; i < md; i++){ int v = setb[i]; for(auto e : graph[v]) tmp[e.second] = 1; } if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md; else l = md; } t = setb[l]; answer(s, t); return; } } for(int it = 0; it < K; it++){ shuffle(zeros.begin(), zeros.end(), rng); tmp.assign(m, 0); for(int i = 0; i <= (zeros.size() - 1) / 2; i++){ int v = zeros[i]; for(auto e : graph[v]) tmp[e.second] = 1; } if(((ask(tmp) - dist) / (b - a)) % 2 == 1){ vector<int> seta, setb; for(int i = 0; i <= (zeros.size() - 1) / 2; i++) seta.push_back(zeros[i]); for(int i = (zeros.size() - 1) / 2 + 1; i < zeros.size(); i++) setb.push_back(zeros[i]); int l = 0, r = seta.size(), md; while(r - l > 1){ md = l + (r - l) / 2; tmp.assign(m, 0); for(int i = 0; i < md; i++){ int v = seta[i]; for(auto e : graph[v]) tmp[e.second] = 1; } if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md; else l = md; } s = seta[l]; l = 0, r = setb.size(); while(r - l > 1){ md = l + (r - l) / 2; tmp.assign(m, 0); for(int i = 0; i < md; i++){ int v = setb[i]; for(auto e : graph[v]) tmp[e.second] = 1; } if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md; else l = md; } t = setb[l]; answer(s, t); return; } } } assert(false); }

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

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:104:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for(int i = 0; i <= (ones.size() - 1) / 2; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:113:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 for(int i = 0; i <= (ones.size() - 1) / 2; i++) seta.push_back(ones[i]);
      |                                ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:114:58: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                 for(int i = (ones.size() - 1) / 2 + 1; i < ones.size(); i++) setb.push_back(ones[i]);
      |                                                        ~~^~~~~~~~~~~~~
highway.cpp:165:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |             for(int i = 0; i <= (zeros.size() - 1) / 2; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:174:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |                 for(int i = 0; i <= (zeros.size() - 1) / 2; i++) seta.push_back(zeros[i]);
      |                                ~~^~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:175:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |                 for(int i = (zeros.size() - 1) / 2 + 1; i < zeros.size(); i++) setb.push_back(zeros[i]);
      |                                                         ~~^~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...