Submission #392205

#	Time	Username	Problem	Language	Result	Execution time	Memory
392205		cpp219	Robots (IOI13_robots)	C++14	39 / 100	2408 ms	11836 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<<" "; 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.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 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<<" "; exit(0);
      |     ^~~
robots.cpp:24:39: 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<<" "; exit(0);
      |                                       ^~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:50:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   50 |     for (ll i = 0;i < A;i++) weak.push_back(X[i]); sort(weak.begin(),weak.end());
      |     ^~~
robots.cpp:50:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   50 |     for (ll i = 0;i < A;i++) weak.push_back(X[i]); sort(weak.begin(),weak.end());
      |                                                    ^~~~
robots.cpp:51:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   51 |     for (ll i = 0;i < B;i++) small.push_back(Y[i]); sort(small.begin(),small.end());
      |     ^~~
robots.cpp:51:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   51 |     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: 0 / 37
• Subtask 5: 0 / 10