제출 #388273

#제출 시각아이디문제언어결과실행 시간메모리
388273ivan24로봇 (IOI13_robots)C++14
0 / 100
730 ms18516 KiB
#include "robots.h" #include <bits/stdc++.h> using namespace std; using ll = int; typedef vector<ll> vi; typedef vector<vi> vvi; typedef pair<ll,ll> ii; #define F first #define S second typedef vector<ii> vii; typedef vector<vii> vvii; class Solver{ private: ll a,b,t; vi x,y,w,s; vii szwt; bool works (ll mins){ //cout << mins << endl; if (mins*(a+b) < t) return 0; vi xcur, ycur; for (ll i = a-1; i >= 0; i--){ for (ll j = 0; mins > j; j++){ xcur.push_back(x[i]); if (xcur.size() == t) break; } if (xcur.size() == t) break; } for (ll i = b-1; i >= 0; i--){ for (ll j = 0; mins > j; j++){ ycur.push_back(y[i]); if (ycur.size() == t) break; } if (ycur.size() == t) break; } reverse(xcur.begin(),xcur.end()); reverse(ycur.begin(),ycur.end()); /* for (auto i: xcur) cout << i << ' '; cout << endl; for (auto i: ycur) cout << i << ' '; cout << endl; */ ll ptr = 0; priority_queue<ll> pq; for (ll i = 0; xcur.size() > i; i++){ while (t > ptr && xcur[i] > szwt[ptr].F){ pq.push(szwt[ptr].S); ptr++; } if (!pq.empty()){ //cout << xcur[i] << ": " << pq.top() << endl; pq.pop(); } } while (t > ptr){ pq.push(szwt[ptr].S); ptr++; } for (ll i = ycur.size()-1; i >= 0; i--){ if (!pq.empty() && ycur[i] > pq.top()){ pq.pop(); } } return pq.empty(); } public: Solver(ll _a, ll _b, ll _t, ll _x[], ll _y[], ll _w[], ll _s[]): a(_a), b(_b), t(_t){ x.resize(a); y.resize(b); w.resize(t); s.resize(t); szwt.resize(t); for (ll i = 0; a > i ;i++) x[i] = _x[i]; for (ll i = 0; b > i ;i++) y[i] = _y[i]; for (ll i = 0; t > i; i++){ w[i] = _w[i]; s[i] = _s[i]; szwt[i] = ii(w[i], s[i]); } } ll solve(){ sort(x.begin(),x.end()); sort(y.begin(),y.end()); sort(szwt.begin(),szwt.end()); for (auto i: szwt){ if (i.F >= x[a-1] && i.S >= y[b-1]) return -1; } ll lo = 1, hi = t, md; while (hi >= lo){ md = (lo+hi)/2; if (lo == hi) break; ll res = works(md); //cout << "md: " << md << " res: " << res << endl; if (res){ hi = md; }else{ lo = md+1; } } return md; } }; int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) { Solver mySolver(a,b,t,x,y,w,s); return mySolver.solve(); }

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

robots.cpp: In member function 'bool Solver::works(ll)':
robots.cpp:25:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   25 |                 if (xcur.size() == t) break;
      |                     ~~~~~~~~~~~~^~~~
robots.cpp:27:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   27 |             if (xcur.size() == t) break;
      |                 ~~~~~~~~~~~~^~~~
robots.cpp:32:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   32 |                 if (ycur.size() == t) break;
      |                     ~~~~~~~~~~~~^~~~
robots.cpp:34:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   34 |             if (ycur.size() == t) break;
      |                 ~~~~~~~~~~~~^~~~
robots.cpp:47:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   47 |         for (ll i = 0; xcur.size() > i; i++){
      |                        ~~~~~~~~~~~~^~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:107:27: warning: 'md' may be used uninitialized in this function [-Wmaybe-uninitialized]
  107 |     return mySolver.solve();
      |                           ^
#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...