제출 #384133

#제출 시각아이디문제언어결과실행 시간메모리
384133mehrdad_sohrabi로봇 (IOI13_robots)C++14
14 / 100
199 ms48108 KiB
#include <bits/stdc++.h> #include "robots.h" /// 500 485 462 A4 using namespace std; typedef int ll; typedef complex<double> point; typedef long double ld; #define pb push_back #define pii pair < ll , ll > #define F first #define S second //#define endl '\n' //#define int long long #define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #define kill(x) return cout<<x<<'\n', 0; const int N=1e6+10; ll t[N]; ll f[N]; ll a[N]; ll b[N]; vector <int> id[N]; ll par[N]; ll getpar(ll v){ if (par[v]==v) return v;return par[v]=getpar(par[v]); } ll h[N]; int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { for (int i=0;i<T;i++) W[i]++,S[i]++; sort(X,X+A); sort(Y,Y+B); vector <pii> w; for (int i=0;i<T;i++){ if ((A==0 || (A && W[i]>X[A-1])) && (B==0 || (B && S[i]>Y[B-1]))) return -1; ll p1=A; ll p2=B; if (A && W[i]<=X[A-1]){ ll z=lower_bound(X,X+A,W[i])-X; t[z]++; p1=z; } if (B && S[i]<=Y[B-1]){ ll z=lower_bound(Y,Y+B,S[i])-Y; if (p1==A) f[z]++; id[p1].pb(z); p2=z; } if (p1!=A && p2!=B) w.pb({p2,p1}); // cout << p1 << " " << p2 << endl; } ll ans=0; ll cn=0,dd=0; for (int i=A-1;i>-1;i--){ cn+=t[i]; dd++; ans=max(ans,(cn+dd-1)/dd); } sort(w.begin(),w.end()); if (w.size()) cout << 1/0; ll l=-1,r=N; if (ans>N) cout << 1/0; while(r-l>1){ for (int i=0;i<A;i++) h[i]=0,par[i]=i; for (int i=0;i<A;i++) a[i]=t[i]; for (int i=0;i<B;i++) b[i]=f[i]; ll mid=(r+l)/2; ll cnt=0,d=0; ll p1=0; ll th=0; for (int i=A-1;i>-1;i--){ cnt+=a[i]; d++; if (cnt>mid*d){ p1=1; th+=cnt-d*mid; h[i]=cnt-d*mid; } cnt=min(cnt,d*mid); } // cout << "UH" << endl; for (int i=0;i<w.size();i++){ if (th==0) break; ll z=w[i].S; // cout << z << " rjf" << endl; // cout << getpar(z) << " " << h[z] << endl; while(getpar(z)!=0 && h[getpar(z)]==0){ // cout << z << " " << getpar(z) << endl; par[getpar(z)]=getpar(z)-1; } z=getpar(z); if (h[z]){ h[z]--; th--; b[w[i].F]++; } } if (th>0) p1=1; cnt=0,d=0; for (int i=B-1;i>-1;i--){ cnt+=b[i]; d++; if (cnt>mid*d) p1=1; } if (p1) l=mid; else r=mid; } return r; } /* ll x[N],y[N],W[N],S[N]; int main(){ ll A,B,T; cin >> A >> B >> T; for (int i=0;i<A;i++) cin >> x[i]; for (int i=0;i<B;i++) cin >> y[i]; for (int i=0;i<T;i++) cin >> W[i] >> S[i]; // for (int i=0;i<T;i++) cin >> S[i]; cout << putaway(A,B,T,x,y,W,S); } 2 1 3 2 5 2 3 1 5 3 2 2 3 2 10 6 2 9 4 7 4 6 8 5 2 3 7 9 1 8 5 1 3 3 8 7 7 6 10 5 */

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

robots.cpp: In function 'll getpar(ll)':
robots.cpp:25:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   25 |     if (par[v]==v) return v;return par[v]=getpar(par[v]);
      |     ^~
robots.cpp:25:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   25 |     if (par[v]==v) return v;return par[v]=getpar(par[v]);
      |                             ^~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:61:28: warning: division by zero [-Wdiv-by-zero]
   61 |     if (w.size()) cout << 1/0;
      |                           ~^~
robots.cpp:63:25: warning: division by zero [-Wdiv-by-zero]
   63 |     if (ans>N) cout << 1/0;
      |                        ~^~
robots.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int i=0;i<w.size();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...