제출 #80941

#제출 시각아이디문제언어결과실행 시간메모리
80941wzy로봇 (IOI13_robots)C++14
76 / 100
287 ms20744 KiB
#include "robots.h" #include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define pb push_back #define F first #define S second // think about the toys as points (W[i] , S[i]) , robots as lines : // robot A type is a vertical line in X[i] // robot B type is a horizontal line in Y[i] // let R[i] be the leftmost type A robot that dominate vector<int> hold[2][50005]; bool used[100005]; int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { vector<int> vert, hori; for(int i = 0 ; i < A ; i++){ vert.push_back(X[i]); } for(int i = 0 ; i < B; i++){ hori.push_back(Y[i]); } sort(vert.begin() , vert.end()); sort(hori.begin() , hori.end()); for(int i = 0 ; i < T ; i++){ int l = 0 , r = vert.size(); r--; int ansj = -1; while(l<=r){ int mid = (l+r)/2; if(vert[mid] > W[i]){ ansj = mid; r = mid - 1; } else l = mid + 1; } if(ansj>=0){ hold[0][ansj].push_back(i); } l = 0 , r = hori.size(); r--; ansj = -1; while(l<=r){ int mid = (l+r)/2; if(hori[mid] > S[i]){ ansj = mid; r = mid - 1; } else l = mid + 1; } if(ansj>=0){ hold[1][ansj].push_back(i); } } int l = 1 , r = (int) 1e6; int ansj = -1; while(l<=r){ int mid = (l+r)/2; bool can = true; for(int i = 0 ; i <= T ;i ++){ used[i] = false; } int lol = 0; // solve now // pega os caras pra X priority_queue<pii> pq; for(int i = 0 ; i < A ; i++){ for(int j = 0 ; j < hold[0][i].size() ; j++) pq.push(pii(S[hold[0][i][j]] , hold[0][i][j])); int cnt = mid; while(cnt-- && pq.size()){ pii u = pq.top(); pq.pop(); used[u.S] = true; lol++; } } while(!pq.empty()) pq.pop(); for(int i = 0 ; i < B ; i++){ for(int j = 0 ; j < hold[1][i].size() ; j++){ if(used[hold[1][i][j]]) continue; pq.push(pii(W[hold[1][i][j]] , hold[1][i][j])); } int cnt = mid; while(cnt-- && pq.size()){ pii u = pq.top(); pq.pop(); used[u.S] = true; lol++; } } if(lol != T) can = false; if(can){ ansj = mid; r = mid - 1; } else l = mid + 1; } return ansj; }

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

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < hold[0][i].size() ; j++) pq.push(pii(S[hold[0][i][j]] , hold[0][i][j]));
                    ~~^~~~~~~~~~~~~~~~~~~
robots.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < hold[1][i].size() ; j++){
                    ~~^~~~~~~~~~~~~~~~~~~
#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...