Submission #339117

#	Time	Username	Problem	Language	Result	Execution time	Memory
339117		12tqian	Robots (IOI13_robots)	C++17	14 / 100	269 ms	7136 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 toys; f0r(i, T) toys.eb(W[i]);
    vi robots; f0r(i, A) robots.eb(X[i]);
    vi pre(A+1);
    sort(all(robots));
    sort(all(toys));
    f0r(i, T) {
        pre[toys[i]]++;
    }   
    f1r(i, 1, A+1) pre[i] += pre[i-1];
    auto check = [&](int x) -> bool {
        f0r(i, A) {
            if (T-pre[robots[i]] > (A-1-i)*x) return false;
        }
        if (T > A*x) return false;
        return true;
    };

    int lo = 1;
    int hi = A;
    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[]) {

    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());
    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) X[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:14: note: in expansion of macro 'f0r'
   22 |     vi toys; f0r(i, T) toys.eb(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:23:16: note: in expansion of macro 'f0r'
   23 |     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:27:5: note: in expansion of macro 'f0r'
   27 |     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:30:5: note: in expansion of macro 'f1r'
   30 |     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:32:9: note: in expansion of macro 'f0r'
   32 |         f0r(i, A) {
      |         ^~~
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:58:5: note: in expansion of macro 'f0r'
   58 |     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:59:5: note: in expansion of macro 'f0r'
   59 |     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:75:5: note: in expansion of macro 'f0r'
   75 |     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:79:5: note: in expansion of macro 'f0r'
   79 |     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:80:5: note: in expansion of macro 'f0r'
   80 |     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:84:5: note: in expansion of macro 'f0r'
   84 |     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:88:5: note: in expansion of macro 'f0r'
   88 |     f0r(i, B) X[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:89:5: note: in expansion of macro 'f0r'
   89 |     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