Submission #392214

#	Time	Username	Problem	Language	Result	Execution time	Memory
392214		cpp219	Robots (IOI13_robots)	C++14	76 / 100	3093 ms	22064 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];
multiset<LL> s;

void out(){
    for (auto i : s) cout<<i.fs<<" "<<i.sc<<"\n"; exit(0);
}

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});// out();
    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.lower_bound({now + 1,-inf});
        if (p == s.end()) continue;
        LL cur = *p;
        //if (i == 2){
            //cout<<"?\n"; cout<<now + 1; exit(0);
            //cout<<cur.fs<<" "<<cur.sc<<"\n";
        //}
        if (cur.sc == m) continue;
        s.erase(p); taked[i] = 1;
        if (cur.sc + 1 < m) s.insert({cur.fs,cur.sc + 1});
    }
    //out();
}

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 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;
    }
    if (l <= n) return l;
    return -1;
}

Compilation message (stderr)

robots.cpp: In function 'void out()':
robots.cpp:24:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   24 |     for (auto i : s) cout<<i.fs<<" "<<i.sc<<"\n"; exit(0);
      |     ^~~
robots.cpp:24:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   24 |     for (auto i : s) cout<<i.fs<<" "<<i.sc<<"\n"; exit(0);
      |                                                   ^~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:57:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   57 |     for (ll i = 0;i < A;i++) weak.push_back(X[i]); sort(weak.begin(),weak.end());
      |     ^~~
robots.cpp:57:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   57 |     for (ll i = 0;i < A;i++) weak.push_back(X[i]); sort(weak.begin(),weak.end());
      |                                                    ^~~~
robots.cpp:58:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   58 |     for (ll i = 0;i < B;i++) small.push_back(Y[i]); sort(small.begin(),small.end());
      |     ^~~
robots.cpp:58:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |     for (ll i = 0;i < B;i++) small.push_back(Y[i]); sort(small.begin(),small.end());
      |                                                     ^~~~

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