Submission #444318

#	Time	Username	Problem	Language	Result	Execution time	Memory
444318		qwerasdfzxcl	Robots (IOI13_robots)	C++14	100 / 100	602 ms	21588 KiB

robots

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

typedef long long ll;
using namespace std;
int cnt[100100], n, x, y;
int *a, *b;
pair<int, int> c[1001000];
bool col[1001000];
struct DSU{
    int path[100100], e[100100], h[100100], sz;
    void init(int n){
        sz = n;
        for (int i=0;i<n;i++) path[i] = e[i] = i, h[i] = 0;
    }
    int find(int s){
        if (s==path[s]) return s;
        return path[s] = find(path[s]);
    }
    void update(int s){e[s] = s+1;}
    void merge(int s, int v){
        int x = find(s), y = find(v);
        if (x==y) return;
        if (h[x]>h[y]) swap(x, y);
        path[x] = y;
        e[y] = max(e[x], e[y]);
        if (h[x]==h[y]) h[y]++;
    }
    int _end(int s){
        if (s==sz) return s;
        return e[find(s)];
    }
}dsu;

bool solve(int m){
    ///init
    for (int i=0;i<x;i++) cnt[i] = 0;
    for (int i=0;i<n;i++) col[i] = 0;
    dsu.init(y);
    ///
    for (int i=0;i<n;i++){
        int tmp = dsu._end(c[i].second);
        //if (m==3) printf("%d\n", tmp);
        if (tmp==y) continue;
        cnt[tmp]++;
        col[i] = 1;
        if (cnt[tmp]==m){
            dsu.update(tmp);
            if (tmp>0 && cnt[tmp-1]==m) dsu.merge(tmp-1, tmp);
            if (tmp<y-1 && cnt[tmp+1]==m) dsu.merge(tmp, tmp+1);
        }
    }

    int pt = x-1;
    for (int i=0;i<y;i++) cnt[i] = 0;
    for (int i=0;i<n;i++) if (!col[i]){
        if (pt<c[i].first) return 0;
        cnt[pt]++;
        if (cnt[pt]==m) pt--;
    }

    return 1;
}

/*int main(){
    scanf("%d %d %d", &x, &y, &n);
    for (int i=0;i<x;i++) scanf("%d", a+i);
    for (int i=0;i<y;i++) scanf("%d", b+i);
    sort(a, a+x); sort(b, b+y);
    for (int i=0;i<n;i++){
        scanf("%d %d", &c[i].first, &c[i].second);
        c[i].first = upper_bound(a, a+x, c[i].first) - a;
        c[i].second = upper_bound(b, b+y, c[i].second) - b;
        if (c[i].first==x && c[i].second==y){
            printf("-1\n"); return 0;
        }
    }
    sort(c, c+n, greater<pair<int, int>>());
    //for (int i=0;i<n;i++) printf(" %d %d\n", c[i].first, c[i].second);

    int l = 1, r = 1001000, ans = 1001000;
    while(l<r){
        int m = (l+r)>>1;
        if (solve(m)) r = m, ans = m;
        else l = m+1;
    }
    assert(ans!=1001000);
    printf("%d\n", ans);
    return 0;
}*/


int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    x = A, y = B, n = T;
    a = X, b = Y;
    swap(x, y);
    swap(a, b);
    sort(a, a+x); sort(b, b+y);
    for (int i=0;i<n;i++){
        c[i].first = W[i], c[i].second = S[i];
        swap(c[i].first, c[i].second);
        c[i].first = upper_bound(a, a+x, c[i].first) - a;
        c[i].second = upper_bound(b, b+y, c[i].second) - b;
        if (c[i].first==x && c[i].second==y){
            return -1;
        }
    }
    sort(c, c+n, greater<pair<int, int>>());
    //for (int i=0;i<n;i++) printf(" %d %d\n", c[i].first, c[i].second);

    int l = 1, r = 1001000, ans = 1001000;
    while(l<r){
        int m = (l+r)>>1;
        if (solve(m)) r = m, ans = m;
        else l = m+1;
    }
    assert(ans!=1001000);
    return ans;
}

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