제출 #765067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765067		fatemetmhr	Robots (IOI13_robots)	C++17	28 / 100	1388 ms	14844 KiB

robots

//  ~ Be Name Khoda ~  //

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

//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e6   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

bool mark[maxn5];

int n, m, t;
priority_queue <int> have[2];
int pt[2], last[2], ind[2], lastlev[2], spen[2][maxn5];
pair <int, int> av[2][maxn5];

inline bool addone(int id, ll lim, int m, int *s){
    //cout << "here we have " << id << ' ' << lim << ' ' << last[id] << ' ' << av[id][ind[id]].fi << endl;
    if(last[id] + 1 > (av[id][ind[id]].fi) * lim){
        int val = have[id].top();
        if(spen[id ^ 1][val] + 1 > (val) * lim)
            return false;
        have[id].pop();
        for(int i = val; i <= lastlev[id ^ 1]; i++)
            spen[id ^ 1][i]++;
        last[id ^ 1]++;
        have[id].push(m - s[av[id][ind[id]].se]);
        spen[id][av[id][ind[id]].fi] = last[id];
        lastlev[id] = av[id][ind[id]].fi;
        ind[id]++;
    }
    else{
        have[id].push(m - s[av[id][ind[id]].se]);
        last[id]++;
        spen[id][av[id][ind[id]].fi] = last[id];
        lastlev[id] = av[id][ind[id]].fi;
        ind[id]++;
    }
    return true;
}

inline bool check(ll lim, int *x, int *y, int *w, int *s){
    //cout << "checkkkkkkkkkkkkkkkkk " << lim << endl;
    pt[0] = pt[1] = 0;
    for(int i = 0; i < t; i++){
        //cout << "hen? " << i << ' ' << w[i] << ' ' << n - w[i] << endl;
        av[n - w[i] < m - s[i]][pt[n - w[i] < m - s[i]]++] = {max(n - w[i], m - s[i]), i};
    }
    sort(av[0], av[0] + pt[0]);
    sort(av[1], av[1] + pt[1]);
    last[0] = last[1] = 0;
    ind[0] = ind[1] = 0;
    while(have[0].size())
        have[0].pop();
    while(have[1].size())
        have[1].pop();
    lastlev[0] = lastlev[1] = 0;
    while(ind[0] < pt[0] || ind[1] < pt[1]){
        //cout << "here " << ind[0] << ' ' << pt[0] << ' ' << ind[1] << ' ' << pt[1] << endl;
        if(ind[0] < pt[0] && (ind[1] == pt[1] || av[0][ind[0]].fi < av[1][ind[1]].fi)){
            if(!addone(0, lim, m, s))
                return false;
        }
        else{
            if(!addone(1, lim, n, w))
                return false;
        }
    }
    return true;
}

int putaway(int a, int b, int T, int x[], int y[], int w[], int s[]) {
    n = a;
    m = b;
    t = T;
    sort(x, x + n);
    sort(y, y + m);
    for(int i = 0; i < t; i++){
        if(w[i] >= x[n - 1] && s[i] >= y[m - 1])
            return -1;
        w[i] = upper_bound(x, x + n, w[i]) - x;
        s[i] = upper_bound(y, y + m, s[i]) - y;
    }
    int lo = 0, hi = t;
    while(hi - lo > 1){
        int mid = (hi + lo) >> 1;
        if(check(mid, x, y, w, s))
            hi = mid;
        else
            lo = mid;
    }
    return hi;
}

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