Submission #793184

#	Time	Username	Problem	Language	Result	Execution time	Memory
793184		PixelCat	Teams (IOI15_teams)	C++14	21 / 100	30 ms	8396 KiB

teams

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include "teams.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 100;

int n;
pii a[MAXN + 10];  // {mn, mx}
int ps[MAXN + 10][MAXN + 10];

int sum(int u, int d, int l, int r) {
    d--; l--;
    return ps[r][u] + ps[l][d] - ps[l][u] - ps[r][d];
}

pii find_pos(int u, int d, int l, int r, int &rem){
    For(y, d, u) For(x, l, r) {
        int s = sum(y, y, x, x);
        if(rem < s) return pii(x, y);
        rem -= s;
    }
    assert(false);
}

void init(int N, int A[], int B[]) {
    n = N;
    memset(ps, 0, sizeof(ps));
    For(i, 1, n) {
        a[i] = pii(A[i - 1], B[i - 1]);
        ps[A[i - 1]][B[i - 1]]++;
    }
    For(i, 1, n) For(j, 1, n) {
        ps[i][j] += ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1];
    }
    sort(a + 1, a + n + 1);
    // Forr(y, n, 1) For(x, 1, n) cerr << sum(y, y, x, x) << " \n"[x == n];
}

struct Ayaya {
    int l, u, d, minus;
};

int can(int M, int K[]) {
    sort(K, K + M);
    vector<Ayaya> stk;
    stk.eb((Ayaya){ 1, n, 1, 0 });

    // auto out = [&]() {
    //     for(auto &i:stk) {
    //         cerr << i.l << " " << i.u << "~" << i.d << " (-" << i.minus << ")\n";
    //     }
    // };

    bool fail = false;
    For(iter, 0, M - 1) {
        int x = K[iter];
        while(sz(stk) && (stk.back().u < x || stk.back().l > x)) stk.pop_back();
        if(stk.empty()) {
            fail = true;
            goto END;
        }
        if(stk.back().d < x) stk.back().d = x;
        // out();

        int rem = x;
        while(rem > 0) {
            if(stk.empty()) {
                fail = true;
                goto END;
            }
            Ayaya aya = stk.back();
            stk.pop_back();

            int su = sum(aya.u, aya.d, aya.l, x) - aya.minus;
            if(su <= rem) {
                // cerr << su << " " << rem << "  take all\n";
                rem -= su;
                continue;
            }

            rem += aya.minus;
            pii pos = find_pos(aya.u, aya.d, aya.l, x, rem);
            if(pos.S < aya.u) stk.eb((Ayaya){ aya.l, aya.u, pos.S + 1, 0 });
            stk.eb((Ayaya){ pos.F, pos.S, pos.S, rem });
            rem = 0;
        }

        if(stk.empty()) stk.eb((Ayaya){ x + 1, n, 1, 0 });
        else if(stk.back().d > 1) stk.eb((Ayaya){ x + 1, stk.back().d - 1, 1, 0 });
    }
END:
    // cerr << "--- end of test ---\n";
    if(fail) return 0;
    return 1;
}

• Subtask 1: 21 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23