QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#834368	#2759. The Big Prize	Max_s_xaM	100 ✓	20ms	9652kb	C++17	2.0kb	2024-12-27 16:08:10	2024-12-27 16:08:10

Judging History

This is the latest submission verdict.

[2024-12-27 16:08:10]
Judged

Verdict: 100
Time: 20ms
Memory: 9652kb

Show

[2024-12-27 16:08:10]
Submitted

answer

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <random>
#include <ctime>
#include <chrono>
#include <numeric>
#include <iomanip>
#include <cassert>
#include "prize.h"

typedef long long ll;
typedef double lf;
typedef unsigned long long ull;

using namespace std;

const int MAXN = 2e5 + 10;

typedef vector <int> pr;

pr sv[MAXN];
int sum[MAXN];
pr Ask(int x) { if (sv[x].size()) return sv[x]; sv[x] = ask(x - 1), sum[x] = sv[x][0] + sv[x][1]; return sv[x]; }

int find_best(int n)
{
    if (n <= 5000)
    {
        int res = -1;
        for (int i = 1; i <= 5000; i++)
        {
            Ask(i);
            if (!sum[i]) { res = i; break; }
        }
        return res - 1;
    }
    int B = sqrt(n) - 5, mx = 0;
    for (int i = 1; i <= n; i += B) Ask(i), mx = max(mx, sum[i]);
    for (int i = 1; i <= n; i += B)
    {
        int l = i + 1, r = min(n, i + B - 1);
        while (sum[l - 1] < mx && l <= r) Ask(l++);
        while (sum[r + 1] < mx && l <= r) Ask(r--);
        if (l > r) continue;
        int cnt = sv[r + 1][0] - sv[l - 1][0];
        vector <int> vec, mns;
        for (int j = l; j <= r; j++) vec.push_back(j);
        mns.resize(vec.size());
        while (cnt)
        {
            int L = 0, R = vec.size() - 1, mid, pos = -1;
            while (L <= R)
            {
                mid = L + R >> 1, Ask(vec[mid]);
                if (sum[vec[mid]] < mx) { pos = mid; break; }
                if (sv[vec[mid]][0] - mns[mid] != sv[l - 1][0]) R = mid - 1;
                else L = mid + 1;
            }
            assert(pos != -1);
            for (int i = pos; i + 1 < vec.size(); i++) vec[i] = vec[i + 1], mns[i] = mns[i + 1];
            for (int i = pos; i + 1 < vec.size(); i++) mns[i]++;
            vec.pop_back(), mns.pop_back(), cnt--;
        }
    }
    for (int i = 1; i <= n; i++)
        if (sv[i].size() && !sum[i]) return i - 1;
    return -1;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20

Accepted

Test #1:

score: 20

Accepted

time: 5ms

memory: 9200kb

input:

output:

result:

ok

Test #2:

score: 20

Accepted

time: 2ms

memory: 9336kb

input:

output:

result:

ok

Test #3:

score: 20

Accepted

time: 0ms

memory: 9196kb

input:

output:

result:

ok

Test #4:

score: 20

Accepted

time: 0ms

memory: 9348kb

input:

output:

result:

ok

Test #5:

score: 20

Accepted

time: 5ms

memory: 9276kb

input:

output:

result:

ok

Test #6:

score: 20

Accepted

time: 0ms

memory: 9216kb

input:

output:

result:

ok

Test #7:

score: 20

Accepted

time: 0ms

memory: 9164kb

input:

output:

result:

ok

Test #8:

score: 20

Accepted

time: 5ms

memory: 9392kb

input:

output:

result:

ok

Test #9:

score: 20

Accepted

time: 0ms

memory: 9276kb

input:

output:

result:

ok

Test #10:

score: 20

Accepted

time: 0ms

memory: 9468kb

input:

output:

result:

ok

Subtask #2:

score: 80

Accepted

Test #11:

score: 80

Accepted

time: 5ms

memory: 9436kb

input:

output:

result:

ok

Test #12:

score: 80

Accepted

time: 3ms

memory: 9288kb

input:

output:

result:

ok

Test #13:

score: 80

Accepted

time: 2ms

memory: 9284kb

input:

output:

result:

ok

Test #14:

score: 80

Accepted

time: 3ms

memory: 9336kb

input:

output:

result:

ok

Test #15:

score: 80

Accepted

time: 0ms

memory: 9284kb

input:

output:

result:

ok

Test #16:

score: 80

Accepted

time: 6ms

memory: 9340kb

input:

output:

result:

ok

Test #17:

score: 80

Accepted

time: 7ms

memory: 9280kb

input:

output:

result:

ok

Test #18:

score: 80

Accepted

time: 0ms

memory: 9244kb

input:

output:

result:

ok

Test #19:

score: 80

Accepted

time: 5ms

memory: 9532kb

input:

output:

result:

ok

Test #20:

score: 80

Accepted

time: 3ms

memory: 9428kb

input:

output:

result:

ok

Test #21:

score: 80

Accepted

time: 11ms

memory: 9348kb

input:

output:

result:

ok

Test #22:

score: 80

Accepted

time: 10ms

memory: 9208kb

input:

output:

result:

ok

Test #23:

score: 80

Accepted

time: 4ms

memory: 9348kb

input:

output:

result:

ok

Test #24:

score: 80

Accepted

time: 0ms

memory: 8936kb

input:

output:

result:

ok

Test #25:

score: 80

Accepted

time: 19ms

memory: 9396kb

input:

output:

result:

ok

Test #26:

score: 80

Accepted

time: 20ms

memory: 9284kb

input:

output:

result:

ok

Test #27:

score: 80

Accepted

time: 13ms

memory: 9444kb

input:

output:

result:

ok

Test #28:

score: 80

Accepted

time: 0ms

memory: 9392kb

input:

output:

result:

ok

Test #29:

score: 80

Accepted

time: 6ms

memory: 9496kb

input:

output:

result:

ok

Test #30:

score: 80

Accepted

time: 4ms

memory: 8928kb

input:

output:

result:

ok

Test #31:

score: 80

Accepted

time: 19ms

memory: 9308kb

input:

output:

result:

ok

Test #32:

score: 80

Accepted

time: 9ms

memory: 9360kb

input:

output:

result:

ok

Test #33:

score: 80

Accepted

time: 4ms

memory: 9264kb

input:

output:

result:

ok

Test #34:

score: 80

Accepted

time: 10ms

memory: 9252kb

input:

output:

result:

ok

Test #35:

score: 80

Accepted

time: 11ms

memory: 9440kb

input:

output:

result:

ok

Test #36:

score: 80

Accepted

time: 9ms

memory: 9584kb

input:

output:

result:

ok

Test #37:

score: 80

Accepted

time: 3ms

memory: 9464kb

input:

output:

result:

ok

Test #38:

score: 80

Accepted

time: 9ms

memory: 9384kb

input:

output:

result:

ok

Test #39:

score: 80

Accepted

time: 4ms

memory: 9376kb

input:

output:

result:

ok

Test #40:

score: 80

Accepted

time: 8ms

memory: 9400kb

input:

output:

result:

ok

Test #41:

score: 80

Accepted

time: 0ms

memory: 9448kb

input:

output:

result:

ok

Test #42:

score: 80

Accepted

time: 9ms

memory: 9548kb

input:

output:

result:

ok

Test #43:

score: 80

Accepted

time: 0ms

memory: 8540kb

input:

output:

A 0
A 1
A 2
A 3
B 3

result:

ok

Test #44:

score: 80

Accepted

time: 7ms

memory: 9312kb

input:

output:

result:

ok

Test #45:

score: 80

Accepted

time: 3ms

memory: 9284kb

input:

output:

result:

ok

Test #46:

score: 80

Accepted

time: 11ms

memory: 9652kb

input:

output:

result:

ok

Test #47:

score: 80

Accepted

time: 8ms

memory: 9340kb

input:

output:

result:

ok

Test #48:

score: 80

Accepted

time: 2ms

memory: 9284kb

input:

output:

result:

ok

Test #49:

score: 80

Accepted

time: 0ms

memory: 9584kb

input:

output:

result:

ok

Test #50:

score: 80

Accepted

time: 0ms

memory: 9560kb

input:

output:

result:

ok

Test #51:

score: 80

Accepted

time: 16ms

memory: 9512kb

input:

output:

result:

ok

Test #52:

score: 80

Accepted

time: 0ms

memory: 9600kb

input:

output:

result:

ok

Test #53:

score: 80

Accepted

time: 6ms

memory: 9392kb

input:

output:

result:

ok

Test #54:

score: 80

Accepted

time: 8ms

memory: 9468kb

input:

output:

result:

ok

Test #55:

score: 80

Accepted

time: 19ms

memory: 9440kb

input:

output:

result:

ok

Test #56:

score: 80

Accepted

time: 14ms

memory: 9580kb

input:

output:

result:

ok

Test #57:

score: 80

Accepted

time: 12ms

memory: 9448kb

input:

output:

result:

ok

Test #58:

score: 80

Accepted

time: 4ms

memory: 9436kb

input:

output:

result:

ok

Test #59:

score: 80

Accepted

time: 7ms

memory: 9440kb

input:

output:

result:

ok

Test #60:

score: 80

Accepted

time: 3ms

memory: 9284kb

input:

output:

result:

ok

Test #61:

score: 80

Accepted

time: 0ms

memory: 9448kb

input:

output:

result:

ok

Test #62:

score: 80

Accepted

time: 0ms

memory: 9464kb

input:

output:

result:

ok

Test #63:

score: 80

Accepted

time: 2ms

memory: 9336kb

input:

output:

result:

ok

Test #64:

score: 80

Accepted

time: 3ms

memory: 9292kb

input:

output:

result:

ok

Test #65:

score: 80

Accepted

time: 4ms

memory: 9508kb

input:

output:

result:

ok

Test #66:

score: 80

Accepted

time: 8ms

memory: 9572kb

input:

output:

result:

ok

Test #67:

score: 80

Accepted

time: 7ms

memory: 9504kb

input:

output:

result:

ok

Test #68:

score: 80

Accepted

time: 17ms

memory: 9452kb

input:

output:

result:

ok

Test #69:

score: 80

Accepted

time: 11ms

memory: 9448kb

input:

output:

result:

ok

Test #70:

score: 80

Accepted

time: 5ms

memory: 9596kb

input:

output:

result:

ok

Test #71:

score: 80

Accepted

time: 4ms

memory: 9152kb

input:

output:

result:

ok

Test #72:

score: 80

Accepted

time: 8ms

memory: 9248kb

input:

output:

result:

ok

Test #73:

score: 80

Accepted

time: 3ms

memory: 9332kb

input:

output:

result:

ok

Test #74:

score: 80

Accepted

time: 7ms

memory: 9340kb

input:

output:

result:

ok

Test #75:

score: 80

Accepted

time: 9ms

memory: 9336kb

input:

output:

result:

ok

Test #76:

score: 80

Accepted

time: 6ms

memory: 9292kb

input:

output:

result:

ok

Test #77:

score: 80

Accepted

time: 9ms

memory: 9292kb

input:

output:

result:

ok

Test #78:

score: 80

Accepted

time: 9ms

memory: 9320kb

input:

output:

result:

ok

Test #79:

score: 80

Accepted

time: 2ms

memory: 9316kb

input:

output:

result:

ok

Test #80:

score: 80

Accepted

time: 0ms

memory: 9236kb

input:

output:

result:

ok

Test #81:

score: 80

Accepted

time: 15ms

memory: 9612kb

input:

output:

result:

ok

Test #82:

score: 80

Accepted

time: 7ms

memory: 9548kb

input:

output:

result:

ok

Test #83:

score: 80

Accepted

time: 10ms

memory: 9404kb

input:

output:

result:

ok

Test #84:

score: 80

Accepted

time: 10ms

memory: 9300kb

input:

output:

result:

ok

Test #85:

score: 80

Accepted

time: 8ms

memory: 9336kb

input:

output:

result:

ok

Test #86:

score: 80

Accepted

time: 5ms

memory: 9444kb

input:

output:

result:

ok

Test #87:

score: 80

Accepted

time: 9ms

memory: 9560kb

input:

output:

result:

ok

Test #88:

score: 80

Accepted

time: 3ms

memory: 9284kb

input:

output:

result:

ok

Test #89:

score: 80

Accepted

time: 5ms

memory: 9380kb

input:

output:

result:

ok

Test #90:

score: 80

Accepted

time: 0ms

memory: 9576kb

input:

output:

result:

ok

Test #91:

score: 80

Accepted

time: 11ms

memory: 9304kb

input:

output:

result:

ok

Test #92:

score: 80

Accepted

time: 7ms

memory: 9400kb

input:

output:

result:

ok

Test #93:

score: 80

Accepted

time: 0ms

memory: 9340kb

input:

output:

result:

ok

Test #94:

score: 80

Accepted

time: 9ms

memory: 9516kb

input:

output:

result:

ok

Test #95:

score: 80

Accepted

time: 19ms

memory: 9308kb

input:

output:

result:

ok

Test #96:

score: 80

Accepted

time: 0ms

memory: 9228kb

input:

output:

result:

ok

Test #97:

score: 80

Accepted

time: 0ms

memory: 9340kb

input:

output:

result:

ok

Test #98:

score: 80

Accepted

time: 5ms

memory: 9496kb

input:

output:

result:

ok

Test #99:

score: 80

Accepted

time: 1ms

memory: 9140kb

input:

output:

result:

ok

Test #100:

score: 80

Accepted

time: 6ms

memory: 9384kb

input:

output:

result:

ok

Test #101:

score: 80

Accepted

time: 3ms

memory: 9288kb

input:

output:

result:

ok

Test #102:

score: 80

Accepted

time: 11ms

memory: 9356kb

input:

output:

result:

ok

Test #103:

score: 80

Accepted

time: 6ms

memory: 9280kb

input:

output:

result:

ok

Test #104:

score: 80

Accepted

time: 6ms

memory: 9204kb

input:

output:

result:

ok

Test #105:

score: 80

Accepted

time: 0ms

memory: 9268kb

input:

output:

result:

ok

Test #106:

score: 80

Accepted

time: 6ms

memory: 9440kb

input:

output:

result:

ok

Test #107:

score: 80

Accepted

time: 0ms

memory: 9380kb

input:

output:

result:

ok

Extra Test:

score: 0

Extra Test Passed