Submission #392171

#	Time	Username	Problem	Language	Result	Execution time	Memory
392171		cpp219	Robots (IOI13_robots)	C++14	0 / 100	1 ms	1232 KiB

robots

#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e6 + 9;
const ll inf = 1e9 + 7;
#include "robots.h"

LL a[N];
ll sz;
vector<ll> weak,small;

bool lf(LL x,LL y){
    return x.sc > y.sc;
}

bool taked[N];
set<LL> s;
void oper(ll cond,ll m){
    s.clear();
    if (!cond) for (auto i : weak) s.insert({i,0});
    else for (auto i : small) s.insert({i,0});
    for (ll i = 0;i < sz;i++){
        if (taked[i]) continue;
        ll now = a[i].fs; if (cond) now = a[i].sc;
        auto p = s.upper_bound({now,inf});
        if (p == s.end()) continue;
        LL cur = *p; if (cur.sc == m) continue;
        s.erase(p); taked[i] = 1; s.insert({cur.fs,cur.sc + 1});
    }
}

bool chk(ll m){
    memset(taked,0,sizeof(taked));
    oper(0,m); oper(1,m);
    //for (ll i = 0;i < sz;i++) cout<<taked[i]<<" "; exit(0);
    for (ll i = 0;i < sz;i++) if (!taked[i]) return 0;
    return 1;
}

ll putaway(ll A,ll B,ll n,ll X[],ll Y[],ll W[],ll S[]){
    for (ll i = 0;i < A;i++) weak.push_back(X[i]); sort(weak.begin(),weak.end());
    for (ll i = 0;i < B;i++) small.push_back(Y[i]); sort(small.begin(),small.end());
    for (ll i = 0;i < n;i++){
        a[i] = {W[i],S[i]};
        ll v1 = 0,v2 = 0;
        if (A) v1 = weak[A - 1]; if (B) v2 = small[B - 1];
        if (W[i] >= v1 && S[i] >= v2) return -1;
    }
    ll l,m,h; l = 1; h = n; sz = n; sort(a,a + n,lf);
        //cout<<chk(1); exit(0);
    while(l <= h){
        m = (l + h)/2;
        if (!chk(m)) l = m + 1;
        else h = m - 1;
    }
    return l;
}
/*
ll A,B,n,X[N],Y[N],W[N],S[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>A>>B>>n;
    for (ll i = 0;i < A;i++) cin>>X[i];
    for (ll i = 0;i < B;i++) cin>>Y[i];
    for (ll i = 0;i < n;i++) cin>>W[i]>>S[i];
    cout<<putaway(A,B,n,X,Y,W,S);
}
*/

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:45:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   45 |     for (ll i = 0;i < A;i++) weak.push_back(X[i]); sort(weak.begin(),weak.end());
      |     ^~~
robots.cpp:45:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   45 |     for (ll i = 0;i < A;i++) weak.push_back(X[i]); sort(weak.begin(),weak.end());
      |                                                    ^~~~
robots.cpp:46:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   46 |     for (ll i = 0;i < B;i++) small.push_back(Y[i]); sort(small.begin(),small.end());
      |     ^~~
robots.cpp:46:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   46 |     for (ll i = 0;i < B;i++) small.push_back(Y[i]); sort(small.begin(),small.end());
      |                                                     ^~~~
robots.cpp:50:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   50 |         if (A) v1 = weak[A - 1]; if (B) v2 = small[B - 1];
      |         ^~
robots.cpp:50:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   50 |         if (A) v1 = weak[A - 1]; if (B) v2 = small[B - 1];
      |                                  ^~

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