Submission #339137

#	Time	Username	Problem	Language	Result	Execution time	Memory
339137		12tqian	Robots (IOI13_robots)	C++17	14 / 100	240 ms	5244 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 bzero(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 check = [&](int x) -> bool {
        f0r(i, A) {
            f0r(j, B) {
                if (!(X[i] <= A && Y[j] <= B)) return -1;
                if (T-(pre[X[i]][B]+pre[A][Y[j]]-pre[X[i]][Y[j]]) > (ll) (A-1-i+B-1-j) * x) return false;
            }
        }
        if (T > (ll) (A+B)*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;
    };

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


    tmp.clear();

    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 (B == 0) {
        return bzero(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 bzero(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:69:9: note: in expansion of macro 'f0r'
   69 |         f0r(i, A) {
      |         ^~~
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:70:13: note: in expansion of macro 'f0r'
   70 |             f0r(j, B) {
      |             ^~~
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:94:5: note: in expansion of macro 'f0r'
   94 |     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:95:5: note: in expansion of macro 'f0r'
   95 |     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:111:5: note: in expansion of macro 'f0r'
  111 |     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:116:5: note: in expansion of macro 'f0r'
  116 |     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:117:5: note: in expansion of macro 'f0r'
  117 |     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:122:5: note: in expansion of macro 'f0r'
  122 |     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:126:5: note: in expansion of macro 'f0r'
  126 |     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:127:5: note: in expansion of macro 'f0r'
  127 |     f0r(i, T) S[i] = get(S[i]);
      |     ^~~

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