제출 #404688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
404688		ly20	로봇 (IOI13_robots)	C++17	90 / 100	3071 ms	37560 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1123456;
//x -> w
//y -> s
int x[MAXN], y[MAXN];
pair <int, int> v[MAXN];
int n, a, b;
int marca[MAXN], marcb[MAXN];
multiset <pair <int, int> > :: iterator it;
bool teste(int t) {
    if(b == 0) {
        int pt = a - 1, at = 0;
        for(int i = n - 1; i >= 0; i--) {
            if(v[i].first >= x[pt] || pt == -1) {
                return false;
            }
            else {
                at++;
                if(at == t) {
                    pt--;
                    at = 0;
                }
            }
        }
        return true;
    }
    multiset <pair <int, int> > sa;
    multiset <pair <int, int> > sb;
    multiset <int> sz;
    for(int i = 0; i < a; i++) sa.insert(make_pair(x[i], i));
    for(int i = 0; i < b; i++) sb.insert(make_pair(y[i], i));
    for(int i = n - 1; i >= 0; i--) {
        it = sa.upper_bound(make_pair(v[i].first, MAXN));
        sz.insert(v[i].second);
        if(it == sa.end()) {
            int a = *(sz.begin());
            sz.erase(sz.begin());
            it = sb.upper_bound(make_pair(a, MAXN));
            if(it == sb.end()) return false;
            else {
                pair <int, int> temp = *it;
                marcb[temp.second]++;
                if(marcb[temp.second] == t) sb.erase(it);
            }
        }
        else {
            pair <int, int> temp = *it;
            marca[temp.second]++;
            if(marca[temp.second] == t) sa.erase(it);
        }
    }
    return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    n = T;
    a = A; b = B;
    for(int i = 0; i < T; i++) {
        v[i] = make_pair(W[i], S[i]);
    }
    sort(v, v + n);
    for(int i = 0; i < a; i++) x[i] = X[i];
    for(int i = 0; i < b; i++) y[i] = Y[i];
    sort(x, x + a); sort(y, y + b);
    int ini = 1, fim = MAXN;
    while(ini < fim) {
        for(int i = 0; i < a; i++) marca[i] = 0;
        for(int i = 0; i < b; i++) marcb[i] = 0;
        int m = (ini + fim) / 2;
        if(teste(m)) {
            fim = m;
        }
        else ini = m + 1;
    }
    if(ini == MAXN) ini = -1;
    return ini;
}

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