Submission #444302

#	Time	Username	Problem	Language	Result	Execution time	Memory
444302		qwerasdfzxcl	Robots (IOI13_robots)	C++14	Compilation error	0 ms	0 KiB

robots

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int a[100100], b[100100], cnt[100100], n, x, y;
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(n);
    ///
    for (int i=0;i<n;i++){
        int tmp = dsu._end(c[i].second);
        //if (m==2) 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<x-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;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d %d %d", &x, &y, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:65:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     for (int i=0;i<x;i++) scanf("%d", a+i);
      |                           ~~~~~^~~~~~~~~~~
robots.cpp:66:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     for (int i=0;i<y;i++) scanf("%d", b+i);
      |                           ~~~~~^~~~~~~~~~~
robots.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d %d", &c[i].first, &c[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccrzkwsK.o: in function `main':
robots.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccYLNhEJ.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccYLNhEJ.o: in function `main':
grader.c:(.text.startup+0x1b1): undefined reference to `putaway'
collect2: error: ld returned 1 exit status