Submission #384119

#	Time	Username	Problem	Language	Result	Execution time	Memory
384119		mehrdad_sohrabi	Robots (IOI13_robots)	C++14	76 / 100	3077 ms	33764 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;
ll t[N];
ll f[N];
ll a[N];
ll b[N];
ll w[N];
vector <int> id[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);
    for (int i=0;i<T;i++){
        if (W[i]>X[A-1] && S[i]>Y[B-1]) return -1;
        ll p1=A;
        ll p2=B;
        if (W[i]<=X[A-1]){
            ll z=lower_bound(X,X+A,W[i])-X;
            t[z]++;
            p1=z;
        }
        if (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;
        }
      //  cout << p1 << " " << p2 << endl;
        w[i]=p1;
    }
    ll l=0,r=N;
    while(r-l>1){
        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;
        multiset <int> s;
        ll p1=0;
        for (int i=A-1;i>-1;i--){
            for (auto u : id[i]) s.insert(u);
            cnt+=a[i];
            d++;
            if (cnt-s.size()>mid*d){
                p1=1;
                break;
            }
            while(cnt>mid*d){
                ll u=*s.begin();
                b[u]++;
                cnt--;
                s.erase(s.begin());
            }
        }
        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
*/

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:31:12: warning: variable 'p2' set but not used [-Wunused-but-set-variable]
   31 |         ll p2=B;
      |            ^~
robots.cpp:60:29: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   60 |             if (cnt-s.size()>mid*d){
      |                 ~~~~~~~~~~~~^~~~~~

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