제출 #765114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765114		fatemetmhr	Robots (IOI13_robots)	C++17	0 / 100	3057 ms	10288 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 <pair<int, int>> have[2];
int pt[2], ind[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;
    bool check = true;
    for(int i = av[id][ind[id]].fi; i <= max(n, m); i++){
        spen[id][i]++;
        check &= (spen[id][i] <= lim * i);
    }
    if(!check){
        int val = have[id].top().fi, v = have[id].top().se;
        have[id].pop();
        for(int i = val; i <= max(n, m); i++){
            spen[id ^ 1][i]++;
            if(spen[id ^ 1][i] > i * lim)
                return false;
        }
        for(int i = v; i <= max(n, m); i++)
            spen[id][i]--;
    }
    have[id].push({m - s[av[id][ind[id]].se], 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};
    }
    for(int i = 0; i <= max(n, m); i++)
        spen[0][i] = spen[1][i] = 0;
    sort(av[0], av[0] + pt[0]);
    sort(av[1], av[1] + pt[1]);
    ind[0] = ind[1] = 0;
    while(have[0].size())
        have[0].pop();
    while(have[1].size())
        have[1].pop();
    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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10