QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#273884#7880. Streak Manipulationucup-team1766#WA 4ms4052kbC++2310.2kb2023-12-03 05:17:002023-12-03 05:17:01

Judging History

你现在查看的是最新测评结果

  • [2023-12-03 05:17:01]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:4052kb
  • [2023-12-03 05:17:00]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

//Safe lowerbound for 1 second is 10^8 operations

#define f0r(a, b) for (long long a = 0; a < b; a++)
#define f1r(a, b, c) for (long long a = b; a < c; a++)
#define r0f(a, b) for (long long a = b - 1; a >= 0; a--)
#define r1f(a, b, c) for (long long a = c - 1; a >= b; a--)
#define pb push_back
#define f first
#define s second

#define mp make_pair
#define t third
#define pll pair<ll, ll>
#define pii pair<int, int>

/* For Debugging Purposes */
#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
#else
#define DEBUG(...) 6
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << "\033[1;35m" << s << "\033[0;32m = \033[33m" << x << "\033[0m\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
        if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;35m" << s.substr(0, i) << "\033[0;32m = \033[33m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}

/* Variartic Macros and Functions so max(a, b, c, d, ... z) works out of box */
template<typename T> constexpr const inline T& _max(const T& x, const T& y) {return x<y?y:x;}
template<typename T> constexpr const inline T& _min(const T& x, const T& y) {return x<y?x:y;}
template<typename T,typename ...S>constexpr const inline T& _max(const T& m, const S&...s){return _max(m,_max(s...));}
template<typename T,typename ...S>constexpr const inline T& _min(const T& m, const S&...s){return _min(m,_min(s...));}
#define max(...) _max(__VA_ARGS__)
#define min(...) _min(__VA_ARGS__)

#define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void usaco(string filename) {
    io;
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

#include <chrono>
using namespace std::chrono;
struct timer {
    high_resolution_clock::time_point begin;

    timer() {}
    timer(bool b) {
        if (b) start();
    }

    void start() {
        begin = high_resolution_clock::now();
    }

    void print() {
        cout << "Time taken: " << duration_cast<duration<double>>(high_resolution_clock::now() - begin).count() << " seconds" << endl;
    }

    double report() {
        return duration_cast<duration<double>>(high_resolution_clock::now() - begin).count();
    }
};
// Start of main put tin, end of main put tpr (tgt gives you value not printed)
#define tin timer __timer__(1);
#define tpr __timer__.print();
#define tgt __timer__.report()

mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// rng() gives a better random unsigned 32 bit number

ll q, Q, T, k, l, r, x, y, z;
int n, m;

void solve();

vector<int> num_zeros_v; // [0] is before the start
vector<int> zero_index;
map<int, int> closest_lefter_zero;
string s;
vector<int> num_zeros_v_r; // [0] is before the start
vector<int> zero_index_r;
map<int, int> closest_righter_zero;

// both inclusive
ll num_zeros(int left, int right, bool dp_l) {
    DEBUG("num_zeros", left, right);
    if (dp_l) {
        return num_zeros_v[right + 1] - num_zeros_v[left];
    } else {
        return num_zeros_v_r[right + 1] - num_zeros_v_r[left];
    }
}

vector<vector<ll>> dp_left(int x) {
    /* dp left */
    vector<vector<ll>> dp_l(k + 1, vector<ll>(zero_index.size(), INT_MAX));
    // dp_l[0] is useless, if 0 groups achieved so far, clearly cost is 0
    for (int i = 0; i < zero_index.size(); i++) dp_l[0][i] = 0;

    // dp_l[k][i] is the minimum cost to achieve k groups to the left (non-inclusive) of the ith zero index

    // dp_l[1][0]
    if (zero_index[0] >= x) {
        dp_l[1][0] = 0;
    }
//    DEBUG(dp_l[1][0]);

    for (int k_ind = 1; k_ind < k + 1; k_ind++) {
        deque<int> dq;
//        DEBUG(k_ind);

        // if there is a 1 at the start
//        if (s[0] == '1') dq.pb(0);
        dq.pb(0);
        for (int i = 0; i < zero_index.size(); i++) {
//            DEBUG(i, dq);

//            DEBUG(zero_index[i], dq.front(), x);
            // check new transition
            while (!dq.empty() && zero_index[i] - dq.front() >= x) {
                int front = dq.front();
                dq.pop_front();

                if (front == 0 && k_ind > 1) {
                    // cannot have more than one group if we are at the start
                    continue;
                } else if (front == 0 && k_ind == 1) {
                    ll cost = num_zeros(front, zero_index[i] - 1, true);

                    dp_l[k_ind][i] = min(dp_l[k_ind][i], cost);
                    continue;
                }

                ll cost = num_zeros(front, zero_index[i] - 1, true) + dp_l[k_ind - 1][closest_lefter_zero[front]];
                dp_l[k_ind][i] = min(dp_l[k_ind][i], cost);
            }
            dq.pb(zero_index[i] + 1);
            if (i < zero_index.size() - 1) {
                // push DP
                dp_l[k_ind][i + 1] = dp_l[k_ind][i];
            }
        }
    }

    return dp_l;
}

vector<vector<ll>> dp_right(int x) {
    vector<vector<ll>> dp_r(k + 1, vector<ll>(zero_index_r.size(), INT_MAX));
    // dp_l[0] is useless, if 0 groups achieved so far, clearly cost is 0
    for (int i = 0; i < zero_index_r.size(); i++) dp_r[0][i] = 0;

    // dp_r[k][i] is the minimum cost to achieve k groups to the left (non-inclusive) of the ith zero index

    // dp_r[1][0]
    if (zero_index_r[0] >= x) {
        dp_r[1][0] = 0;
    }
    DEBUG(dp_r[1][0]);

    for (int k_ind = 1; k_ind < k + 1; k_ind++) {
        deque<int> dq;
        DEBUG(k_ind);

        // if there is a 1 at the start

        /* END */
//        if (s[n - 1] == '1') {
//            dq.pb(0);
//        } else {
//            dq.pb(-1);
//        }
        dq.pb(0);
        for (int i = 0; i < zero_index_r.size(); i++) {
            DEBUG(i, dq);

            DEBUG(zero_index_r[i], dq.front(), x);
            // check new transition
            while (!dq.empty() && zero_index_r[i] - max(0, dq.front()) >= x) {
                int front = dq.front();
                front = max(0, front);
                dq.pop_front();

                if (front == 0 && k_ind > 1) {
                    // cannot have more than one group if we are at the start
                    continue;
                } else if (front == 0 && k_ind == 1) {
                    ll cost = num_zeros(front, zero_index_r[i] - 1, false);

                    dp_r[k_ind][i] = min(dp_r[k_ind][i], cost);
                    continue;
                }

//                ll cost =
                DEBUG("getting le cost", k_ind - 1, closest_righter_zero[front], zero_index_r[i], i);
                ll broken_zeros = num_zeros(front, zero_index_r[i] - 1, false);
                DEBUG("broken_zeros", broken_zeros);
                DEBUG("dp_r[k_ind - 1][closest_righter_zero[front]]", dp_r[k_ind - 1][closest_righter_zero[front]]);
                ll cost = num_zeros(front, zero_index_r[i] - 1, false) + dp_r[k_ind - 1][closest_righter_zero[front]];
                dp_r[k_ind][i] = min(dp_r[k_ind][i], cost);
            }
            dq.pb(zero_index_r[i] + 1);
            if (i < zero_index_r.size() - 1) {
                // push DP
                dp_r[k_ind][i + 1] = dp_r[k_ind][i];
            }
        }
    }

    return dp_r;
}

bool solve(int x) {
    vector<vector<ll>> dp_l = dp_left(x);
    DEBUG("got dp_l");
    vector<vector<ll>> dp_r = dp_right(x);

    DEBUG("got dp_l and dp_r");

    for (int i = 0; i < dp_l.size(); i++) {
        DEBUG(dp_l[i]);
    }
    for (int i = 0; i < dp_r.size(); i++) {
        DEBUG(dp_r[i]);
    }

    if (k > 1) {
        for (int k_ind = 1; k_ind < k; k_ind++) { // start at 1, end at k instead of k + 1. this is because you have to use at least 1 from left and right, separated by a zero
            // - 1, since I need a 0 separating the left group and the right group since you need multiple groups
            for (int i = 0; i < zero_index.size() - 1; i++) {
                // if left + right <= m, return true

                // left is DP[k_ind][i]
                // right is DP[k - k_ind][zero_index.size() - i - 1]

                ll left_cost = dp_l[k_ind][i];
                ll right_cost = dp_r[k - k_ind][zero_index_r.size() - i - 1];

                if (left_cost + right_cost <= m) {
                    DEBUG(k_ind, k - k_ind);
                    DEBUG(k_ind, i, left_cost, right_cost);
                    return true;
                }
            }
        }
    } else {
        // k == 1
        DEBUG(dp_l[k][zero_index.size() - 1]);
        if (dp_l[k][zero_index.size() - 1] <= m) {
            return true;
        }
    }

    return false;
}

// Problem URL:
int main() {
    io;
    cin >> n >> m >> k;
    num_zeros_v = vector<int>(n + 1);
    num_zeros_v_r = vector<int>(n + 1);

    cin >> s;

    int last_zero = -1;
    for (int i = 0; i < n; i++) {
        num_zeros_v[i + 1] = num_zeros_v[i] + (s[i] == '0');
        if (s[i] == '0') {
            zero_index.pb(i);
            last_zero++; // not the direct ind, but the zero_index ind
        } else {
            closest_lefter_zero[i] = last_zero;
        }
    }

    string s_rev = s;
    reverse(s_rev.begin(), s_rev.end());
    last_zero = -1;
    for (int i = 0; i < n; i++) {
        num_zeros_v_r[i + 1] = num_zeros_v_r[i] + (s_rev[i] == '0');
        if (s_rev[i] == '0') {
            zero_index_r.pb(i);
            last_zero++; // not the direct ind, but the zero_index ind
        } else {
            closest_righter_zero[i] = last_zero;
        }
    }

    DEBUG("finished IO");

    bool ret = solve(1);
    DEBUG(ret);
    int l = 1;
    int r = n;
    int res = -1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (solve(m)) {
            res = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    cout << res << endl;
}


詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3700kb

input:

8 3 2
10110110

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

12 3 3
100100010011

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

4 4 4
0000

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 2ms
memory: 3772kb

input:

1000 200 5
0001001000101001110010011001101010110101101100010100111110111111010010001100100111100101011100011101011001110010111100100100011001010011000100011111010110100001101110101001110000001000111010000111110100111101100110011010011111000111101001010011000111010111010100101111100000100001011001010...

output:

99

result:

ok 1 number(s): "99"

Test #5:

score: -100
Wrong Answer
time: 4ms
memory: 4052kb

input:

1000 200 5
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

-1

result:

wrong answer 1st numbers differ - expected: '40', found: '-1'