Submission #339111

#	Time	Username	Problem	Language	Result	Execution time	Memory
339111		12tqian	Robots (IOI13_robots)	C++17	14 / 100	523 ms	18900 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+T);
        sort(all(robots));
        sort(all(toys));
        f0r(i, T) {
            pre[toys[i]]++;
        }   
        f1r(i, 1, A+T) 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-1;
            }
            if (tmp[l] == x) return l;
            return r;
        };
        map<int, int> conv;
        int cnt = 0;

        f0r(i, A) tmp.pb(X[i]);
        f0r(i, T) tmp.pb(W[i]);
        sort(all(tmp));
        tmp.erase(unique(all(tmp)), tmp.end());
        f0r(i, A) X[i] = get(X[i]);
        f0r(i, T) W[i] = get(W[i]);

        tmp.clear(), conv.clear(), cnt = 0;

        f0r(i, B) tmp.pb(Y[i]);
        f0r(i, T) tmp.pb(S[i]);
        sort(all(tmp));
        tmp.erase(unique(all(tmp)), tmp.end());
        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:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:22:18: note: in expansion of macro 'f0r'
   22 |         vi toys; f0r(i, T) toys.eb(W[i]);
      |                  ^~~
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:23:20: note: in expansion of macro 'f0r'
   23 |         vi robots; f0r(i, A) robots.eb(X[i]);
      |                    ^~~
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:27:9: note: in expansion of macro 'f0r'
   27 |         f0r(i, T) {
      |         ^~~
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:30:9: note: in expansion of macro 'f1r'
   30 |         f1r(i, 1, A+T) pre[i] += pre[i-1];
      |         ^~~
robots.cpp: In lambda function:
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:32:13: 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:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:57:9: note: in expansion of macro 'f0r'
   57 |         f0r(i, A) X[i]--;
      |         ^~~
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:58:9: note: in expansion of macro 'f0r'
   58 |         f0r(i, B) Y[i]--;
      |         ^~~
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: 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) tmp.pb(X[i]);
      |         ^~~
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:77:9: note: in expansion of macro 'f0r'
   77 |         f0r(i, T) tmp.pb(W[i]);
      |         ^~~
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:80:9: note: in expansion of macro 'f0r'
   80 |         f0r(i, A) X[i] = get(X[i]);
      |         ^~~
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:81:9: note: in expansion of macro 'f0r'
   81 |         f0r(i, T) W[i] = get(W[i]);
      |         ^~~
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:85:9: note: in expansion of macro 'f0r'
   85 |         f0r(i, B) tmp.pb(Y[i]);
      |         ^~~
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:86:9: note: in expansion of macro 'f0r'
   86 |         f0r(i, T) tmp.pb(S[i]);
      |         ^~~
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:89:9: note: in expansion of macro 'f0r'
   89 |         f0r(i, B) X[i] = get(Y[i]);
      |         ^~~
robots.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 |     #define f1r(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
      |                                   ^
robots.cpp:5:23: note: in expansion of macro 'f1r'
    5 |     #define f0r(i, a) f1r(i, 0, a)
      |                       ^~~
robots.cpp:90:9: note: in expansion of macro 'f0r'
   90 |         f0r(i, T) S[i] = get(S[i]);
      |         ^~~
robots.cpp:74:13: warning: variable 'cnt' set but not used [-Wunused-but-set-variable]
   74 |         int cnt = 0;
      |             ^~~

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