Submission #384146

#	Time	Username	Problem	Language	Result	Execution time	Memory
384146		mehrdad_sohrabi	Robots (IOI13_robots)	C++14	100 / 100	507 ms	37204 KiB

robots

#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,inf=1e9;
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 (B==0) return ans;
   // 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>min(inf/d,mid)*d){
                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>min(inf/d,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
*/

Compilation message (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:64:25: warning: division by zero [-Wdiv-by-zero]
   64 |     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++){
      |                      ~^~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10