Submission #339142

#	Time	Username	Problem	Language	Result	Execution time	Memory
339142		12tqian	Robots (IOI13_robots)	C++17	90 / 100	246 ms	16640 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

#define f0r(i, a) f1r(i, 0, a)
#define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)

#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define mp make_pair
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

int zero(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    vi robots; f0r(i, A) robots.eb(X[i]);
    vi pre(A+1);
    sort(all(robots));
    f0r(i, T) {
        pre[W[i]]++;
    }   
    f1r(i, 1, A+1) pre[i] += pre[i-1];
    auto check = [&](int x) -> bool {
        f0r(i, A) {
            if (T-pre[robots[i]] > (ll) (A-1-i)*x) return false;
        }
        if (T > (ll) A*x) return false;
        return true;
    };

    int lo = 1;
    int hi = T;
    while (hi-lo>1) {
        int mid = (lo+hi)/2;
        if (check(mid)) {
            hi = mid;
        } else {
            lo = mid+1;
        }
    }
    if (check(lo)) return lo;
    if (check(hi)) return hi;
    return -1;
}
int smallsolve(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    vector<vi> pre(A+1, vi(B+1));
    f0r(i, T) {
        if (W[i] > A || S[i] > B) return -1;
    }
    f0r(i, T) pre[W[i]][S[i]]++;
    f0r(i, A+1) {
        int run = 0;
        f0r(j, B+1) {
            int tmp = pre[i][j];
            pre[i][j] += run;
            if (i) pre[i][j] += pre[i-1][j];
            run += tmp;
        }
    }
    sort(X, X+A);
    sort(Y, Y+B);
    auto rect = [&](int lx, int rx, int ly, int ry) -> int {
        int res = pre[rx][ry];
        if (lx) res -= pre[lx-1][ry];
        if (ly) res -= pre[rx][ly-1];
        if (lx && ly) res += pre[lx-1][ly-1];
        return res;
    };
    auto check = [&](int x) -> bool {
        f0r(i, A+1) {
            f0r(j, B+1) {
                if (i == A && j == B) {
                    if (T > (ll) (A+B)*x) return false;
                } else if (i == A) {
                    if (rect(0, A, Y[j]+1, B) > (ll) (A+B-1-j) * x) return false;
                } else if (j == B) {
                    if (rect(X[i]+1, A, 0, B) > (ll) (B+A-1-i) * x) return false;
                } else {
                    if (rect(X[i]+1, A, Y[j]+1, B) > (ll) (A-1-i+B-1-j) * x) return false;
                }
            }
        }
        return true;
    };
    int lo = 1;
    int hi = T;
    while (hi-lo>1) {
        int mid = (lo+hi)/2;
        if (check(mid)) {
            hi = mid;   
        } else {
            lo = mid+1;
        }
    }
    if (check(lo)) return lo;
    if (check(hi)) return hi;

    return -1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    f0r(i, A) X[i]--;
    f0r(i, B) Y[i]--;

    vi tmp;
    auto get = [&](int x) -> int {
        int l = 0;
        int r = sz(tmp)-1;
        while (r-l>1) {
            int m = (l+r)/2;
            if (tmp[m] == x) return m;
            else if (tmp[m] < x) l = m+1;
            else r = m;
        }
        if (tmp[l] >= x) return l;
        return r;
    };

    if (A) {
        f0r(i, A) tmp.pb(X[i]);
        sort(all(tmp));
        tmp.erase(unique(all(tmp)), tmp.end());
        tmp.pb(tmp.back()+1);
        f0r(i, A) X[i] = get(X[i]);
        f0r(i, T) W[i] = get(W[i]);
    }

    tmp.clear();

    if (B) {
        f0r(i, B) tmp.pb(Y[i]);
        sort(all(tmp));
        tmp.erase(unique(all(tmp)), tmp.end());
        tmp.pb(tmp.back()+1);
        f0r(i, B) Y[i] = get(Y[i]);
        f0r(i, T) S[i] = get(S[i]);
    }

    if (A == 0) {
        return zero(B, A, T, Y, X, S, W);
    } else if (B == 0) {
        return zero(A, B, T, X, Y, W, S);
    } else if (A + B <= 1000) {
        return smallsolve(A, B, T, X, Y, W, S);
    }
    return 42;
}

Compilation message (stderr)

robots.cpp: In function 'int zero(int, int, int, int*, int*, int*, int*)':
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:22:16: note: in expansion of macro 'f0r'
   22 |     vi robots; f0r(i, A) robots.eb(X[i]);
      |                ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:25:5: note: in expansion of macro 'f0r'
   25 |     f0r(i, T) {
      |     ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:28:5: note: in expansion of macro 'f1r'
   28 |     f1r(i, 1, A+1) pre[i] += pre[i-1];
      |     ^~~
robots.cpp: In lambda function:
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:30:9: note: in expansion of macro 'f0r'
   30 |         f0r(i, A) {
      |         ^~~
robots.cpp: In function 'int smallsolve(int, int, int, int*, int*, int*, int*)':
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:53:5: note: in expansion of macro 'f0r'
   53 |     f0r(i, T) {
      |     ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:56:5: note: in expansion of macro 'f0r'
   56 |     f0r(i, T) pre[W[i]][S[i]]++;
      |     ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:57:5: note: in expansion of macro 'f0r'
   57 |     f0r(i, A+1) {
      |     ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:59:9: note: in expansion of macro 'f0r'
   59 |         f0r(j, B+1) {
      |         ^~~
robots.cpp: In lambda function:
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:76:9: note: in expansion of macro 'f0r'
   76 |         f0r(i, A+1) {
      |         ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:77:13: note: in expansion of macro 'f0r'
   77 |             f0r(j, B+1) {
      |             ^~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:107:5: note: in expansion of macro 'f0r'
  107 |     f0r(i, A) X[i]--;
      |     ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:108:5: note: in expansion of macro 'f0r'
  108 |     f0r(i, B) Y[i]--;
      |     ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:125:9: note: in expansion of macro 'f0r'
  125 |         f0r(i, A) tmp.pb(X[i]);
      |         ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:129:9: note: in expansion of macro 'f0r'
  129 |         f0r(i, A) X[i] = get(X[i]);
      |         ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:130:9: note: in expansion of macro 'f0r'
  130 |         f0r(i, T) W[i] = get(W[i]);
      |         ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:136:9: note: in expansion of macro 'f0r'
  136 |         f0r(i, B) tmp.pb(Y[i]);
      |         ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:140:9: note: in expansion of macro 'f0r'
  140 |         f0r(i, B) Y[i] = get(Y[i]);
      |         ^~~
robots.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                               ^
robots.cpp:5:19: note: in expansion of macro 'f1r'
    5 | #define f0r(i, a) f1r(i, 0, a)
      |                   ^~~
robots.cpp:141:9: note: in expansion of macro 'f0r'
  141 |         f0r(i, T) S[i] = get(S[i]);
      |         ^~~

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