QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#140388	#4565. Rarest Insects	somethingnew^#	65.49	34ms	4120kb	C++20	3.9kb	2023-08-15 20:52:54	2024-07-04 01:44:42

Judging History

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

[2024-07-04 01:44:42]
评测

测评结果：65.49
用时：34ms
内存：4120kb

查看

[2023-08-15 20:52:54]
提交

answer

//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#include "random"
#define all(x) x.begin(), x.end()
using namespace std;
#include "insects.h"
mt19937 rnd;
int min_cardinality(int N) {
    vector<int> iba(N);
    for (int i = 0; i < N; ++i) {
        iba[i] = i;
    }
    vector<int> ex(N, 1);
    for (int i = 0; i < N; ++i) {
        swap(iba[i], iba[rnd() % N]);
    }
    int cnt = 0;
    int gcnt = 0;
    int prvl = 2;
    int lstch = 0;
    for (int i = 0; i < N; ++i) {
        move_inside(iba[i]);
        if (press_button() == 2) {
            move_outside(iba[i]);
        } else {
            cnt++;
            lstch = i;
            //cerr << "ADD " << i << ' ' << press_button() << endl;
            ex[i] = 0;
        }
    }
    gcnt = cnt;
    for (int i = (lstch + 1) % N; i != lstch; i = (i + 1) % N) {
        //cerr << i << endl;
        if (ex[i]) {
            //cerr << i << endl;
            move_inside(iba[i]);
            if (prvl != press_button()) {
                move_outside(iba[i]);
            } else {
                ex[i] = 0;
                cnt--;
                lstch = i;
                if (cnt == 0) {
                    cnt = gcnt;
                    prvl++;
                }
            }
        }
    }
    return prvl - 1;
}
#ifdef __APPLE__

static inline constexpr int kMaxQueries = 40000;

static int N;
// Insect types are compressed to colors in the range [0, N).
static std::vector<int> color;
static std::vector<bool> in_box;

static std::vector<int> color_occurrences;
static std::multiset<int> max_occurrences;

static std::vector<int> op_counter(3, 0);

static inline void protocol_violation(std::string message) {
    printf("Protocol Violation: %s\n", message.c_str());
    exit(0);
}

void move_inside(int i) {
    if (i < 0 || i >= N) {
        protocol_violation("invalid parameter");
    }
    ++op_counter[0];
    if (op_counter[0] > kMaxQueries) {
        protocol_violation("too many calls");
    }
    if (!in_box[i]) {
        in_box[i] = true;
        max_occurrences.erase(max_occurrences.find(color_occurrences[color[i]]));
        ++color_occurrences[color[i]];
        max_occurrences.insert(color_occurrences[color[i]]);
    }
}

void move_outside(int i) {
    if (i < 0 || i >= N) {
        protocol_violation("invalid parameter");
    }
    ++op_counter[1];
    if (op_counter[1] > kMaxQueries) {
        protocol_violation("too many calls");
    }
    if (in_box[i]) {
        in_box[i] = false;
        max_occurrences.erase(max_occurrences.find(color_occurrences[color[i]]));
        --color_occurrences[color[i]];
        max_occurrences.insert(color_occurrences[color[i]]);
    }
}

int press_button() {
    ++op_counter[2];
    if (op_counter[2] > kMaxQueries) {
        protocol_violation("too many calls");
    }
    return *(max_occurrences.rbegin());
}

int main() {
    assert(1 == scanf("%d", &N));
    color.resize(N);
    in_box.assign(N, false);

    std::map<int, int> type_to_color;
    for (int i = 0; i < N; ++i) {
        int Ti;
        assert(1 == scanf("%d", &Ti));
        if (type_to_color.find(Ti) == type_to_color.end()) {
            int new_color = type_to_color.size();
            type_to_color[Ti] = new_color;
            max_occurrences.insert(0);
        }
        color[i] = type_to_color[Ti];
    }

    color_occurrences.assign(type_to_color.size(), 0);

    int answer = min_cardinality(N);
    int Q = *std::max_element(op_counter.begin(), op_counter.end());
    printf("%d\n", answer);
    printf("%d\n", Q);
    return 0;
}
#endif

源文件, 语言: C++20

詳細信息

Subtask #1:

score: 10

Accepted

Test #1:

score: 10

Accepted

time: 1ms

memory: 4092kb

input:

output:

result:

ok

Test #2:

score: 0

Accepted

time: 1ms

memory: 4096kb

input:

output:

result:

ok

Test #3:

score: 0

Accepted

time: 0ms

memory: 3872kb

input:

2
1
1

output:

result:

ok

Test #4:

score: 0

Accepted

time: 1ms

memory: 3800kb

input:

output:

result:

ok

Test #5:

score: 0

Accepted

time: 1ms

memory: 4092kb

input:

output:

result:

ok

Test #6:

score: 0

Accepted

time: 1ms

memory: 4092kb

input:

output:

result:

ok

Test #7:

score: 0

Accepted

time: 3ms

memory: 3816kb

input:

output:

result:

ok

Test #8:

score: 0

Accepted

time: 1ms

memory: 3748kb

input:

output:

result:

ok

Test #9:

score: 0

Accepted

time: 1ms

memory: 3800kb

input:

output:

result:

ok

Test #10:

score: 0

Accepted

time: 0ms

memory: 3776kb

input:

output:

result:

ok

Test #11:

score: 0

Accepted

time: 1ms

memory: 3804kb

input:

output:

result:

ok

Test #12:

score: 0

Accepted

time: 2ms

memory: 3808kb

input:

output:

result:

ok

Test #13:

score: 0

Accepted

time: 3ms

memory: 3868kb

input:

output:

result:

ok

Test #14:

score: 0

Accepted

time: 0ms

memory: 3796kb

input:

output:

result:

ok

Test #15:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok

Test #16:

score: 0

Accepted

time: 4ms

memory: 4100kb

input:

output:

result:

ok

Test #17:

score: 0

Accepted

time: 5ms

memory: 3868kb

input:

output:

result:

ok

Test #18:

score: 0

Accepted

time: 4ms

memory: 3804kb

input:

output:

result:

ok

Test #19:

score: 0

Accepted

time: 0ms

memory: 4096kb

input:

output:

result:

ok

Test #20:

score: 0

Accepted

time: 4ms

memory: 3808kb

input:

output:

result:

ok

Test #21:

score: 0

Accepted

time: 3ms

memory: 3800kb

input:

output:

result:

ok

Test #22:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok

Test #23:

score: 0

Accepted

time: 1ms

memory: 4064kb

input:

output:

result:

ok

Subtask #2:

score: 15

Accepted

Test #24:

score: 15

Accepted

time: 0ms

memory: 3756kb

input:

output:

result:

ok

Test #25:

score: 0

Accepted

time: 4ms

memory: 3816kb

input:

output:

result:

ok

Test #26:

score: 0

Accepted

time: 9ms

memory: 3808kb

input:

output:

result:

ok

Test #27:

score: 0

Accepted

time: 3ms

memory: 3812kb

input:

output:

result:

ok

Test #28:

score: 0

Accepted

time: 0ms

memory: 3896kb

input:

output:

result:

ok

Test #29:

score: 0

Accepted

time: 4ms

memory: 3808kb

input:

output:

result:

ok

Test #30:

score: 0

Accepted

time: 0ms

memory: 4104kb

input:

output:

result:

ok

Test #31:

score: 0

Accepted

time: 4ms

memory: 4100kb

input:

output:

result:

ok

Test #32:

score: 0

Accepted

time: 4ms

memory: 4064kb

input:

output:

result:

ok

Test #33:

score: 0

Accepted

time: 5ms

memory: 4088kb

input:

output:

result:

ok

Test #34:

score: 0

Accepted

time: 11ms

memory: 3812kb

input:

output:

result:

ok

Test #35:

score: 0

Accepted

time: 12ms

memory: 4100kb

input:

output:

result:

ok

Test #36:

score: 0

Accepted

time: 15ms

memory: 4096kb

input:

output:

result:

ok

Test #37:

score: 0

Accepted

time: 5ms

memory: 3756kb

input:

output:

result:

ok

Test #38:

score: 0

Accepted

time: 0ms

memory: 4100kb

input:

output:

result:

ok

Test #39:

score: 0

Accepted

time: 6ms

memory: 4096kb

input:

output:

result:

ok

Test #40:

score: 0

Accepted

time: 0ms

memory: 3812kb

input:

output:

result:

ok

Test #41:

score: 0

Accepted

time: 3ms

memory: 3808kb

input:

output:

result:

ok

Test #42:

score: 0

Accepted

time: 10ms

memory: 3808kb

input:

output:

result:

ok

Subtask #3:

score: 40.49

Acceptable Answer

Test #43:

score: 75

Accepted

time: 1ms

memory: 3800kb

input:

output:

result:

ok

Test #44:

score: 75

Accepted

time: 1ms

memory: 4104kb

input:

2
1
1

output:

result:

ok

Test #45:

score: 75

Accepted

time: 1ms

memory: 3872kb

input:

output:

result:

ok

Test #46:

score: 75

Accepted

time: 1ms

memory: 3880kb

input:

output:

result:

ok

Test #47:

score: 75

Accepted

time: 0ms

memory: 3816kb

input:

output:

result:

ok

Test #48:

score: 75

Accepted

time: 11ms

memory: 3816kb

input:

output:

result:

ok

Test #49:

score: 75

Accepted

time: 0ms

memory: 3852kb

input:

output:

result:

ok

Test #50:

score: 58.59

Acceptable Answer

time: 18ms

memory: 3816kb

input:

output:

result:

points 0.78120 points  0.78120

Test #51:

score: 61.56

Acceptable Answer

time: 22ms

memory: 4108kb

input:

output:

result:

points 0.82080 points  0.82080

Test #52:

score: 75

Accepted

time: 15ms

memory: 3704kb

input:

output:

result:

ok

Test #53:

score: 75

Accepted

time: 7ms

memory: 3820kb

input:

output:

result:

ok

Test #54:

score: 75

Accepted

time: 10ms

memory: 3896kb

input:

output:

result:

ok

Test #55:

score: 75

Accepted

time: 0ms

memory: 3828kb

input:

output:

result:

ok

Test #56:

score: 63.28

Acceptable Answer

time: 19ms

memory: 3824kb

input:

output:

result:

points 0.84373333330 points  0.84373333330

Test #57:

score: 40.49

Acceptable Answer

time: 9ms

memory: 4072kb

input:

output:

result:

points 0.53986666670 points  0.53986666670

Test #58:

score: 52.93

Acceptable Answer

time: 9ms

memory: 4072kb

input:

output:

result:

points 0.70573333330 points  0.70573333330

Test #59:

score: 55.43

Acceptable Answer

time: 22ms

memory: 3852kb

input:

output:

result:

points 0.73906666670 points  0.73906666670

Test #60:

score: 60.21

Acceptable Answer

time: 19ms

memory: 3820kb

input:

output:

result:

points 0.80280 points  0.80280

Test #61:

score: 42.71

Acceptable Answer

time: 34ms

memory: 3896kb

input:

output:

result:

points 0.56946666670 points  0.56946666670

Test #62:

score: 64.85

Acceptable Answer

time: 5ms

memory: 3820kb

input:

output:

result:

points 0.86466666670 points  0.86466666670

Test #63:

score: 67.06

Acceptable Answer

time: 15ms

memory: 3792kb

input:

output:

result:

points 0.89413333330 points  0.89413333330

Test #64:

score: 75

Accepted

time: 5ms

memory: 4112kb

input:

output:

result:

ok

Test #65:

score: 75

Accepted

time: 0ms

memory: 3816kb

input:

output:

result:

ok

Test #66:

score: 75

Accepted

time: 15ms

memory: 3824kb

input:

output:

result:

ok

Test #67:

score: 75

Accepted

time: 4ms

memory: 3820kb

input:

output:

result:

ok

Test #68:

score: 58

Acceptable Answer

time: 15ms

memory: 4104kb

input:

output:

result:

points 0.77333333330 points  0.77333333330

Test #69:

score: 57.79

Acceptable Answer

time: 22ms

memory: 3896kb

input:

output:

result:

points 0.77053333330 points  0.77053333330

Test #70:

score: 54.7

Acceptable Answer

time: 5ms

memory: 3768kb

input:

output:

result:

points 0.72933333330 points  0.72933333330

Test #71:

score: 53.22

Acceptable Answer

time: 7ms

memory: 3816kb

input:

output:

result:

points 0.70960 points  0.70960

Test #72:

score: 70.11

Acceptable Answer

time: 22ms

memory: 4108kb

input:

output:

result:

points 0.93480 points  0.93480

Test #73:

score: 64.89

Acceptable Answer

time: 25ms

memory: 3816kb

input:

output:

result:

points 0.86520 points  0.86520

Test #74:

score: 75

Accepted

time: 0ms

memory: 3768kb

input:

output:

result:

ok

Test #75:

score: 75

Accepted

time: 0ms

memory: 3816kb

input:

output:

result:

ok

Test #76:

score: 59.02

Acceptable Answer

time: 13ms

memory: 3792kb

input:

output:

result:

points 0.78693333330 points  0.78693333330

Test #77:

score: 58.83

Acceptable Answer

time: 12ms

memory: 3792kb

input:

output:

result:

points 0.78440 points  0.78440

Test #78:

score: 67.23

Acceptable Answer

time: 18ms

memory: 3900kb

input:

output:

result:

points 0.89640 points  0.89640

Test #79:

score: 67.08

Acceptable Answer

time: 10ms

memory: 4112kb

input:

output:

result:

points 0.89440 points  0.89440

Test #80:

score: 64.93

Acceptable Answer

time: 24ms

memory: 3852kb

input:

output:

result:

points 0.86573333330 points  0.86573333330

Test #81:

score: 64.74

Acceptable Answer

time: 8ms

memory: 3816kb

input:

output:

result:

points 0.86320 points  0.86320

Test #82:

score: 55.55

Acceptable Answer

time: 27ms

memory: 3828kb

input:

output:

result:

points 0.74066666670 points  0.74066666670

Test #83:

score: 57.86

Acceptable Answer

time: 18ms

memory: 3816kb

input:

output:

result:

points 0.77146666670 points  0.77146666670

Test #84:

score: 75

Accepted

time: 7ms

memory: 3872kb

input:

output:

result:

ok

Test #85:

score: 75

Accepted

time: 4ms

memory: 4072kb

input:

output:

result:

ok

Test #86:

score: 72.67

Acceptable Answer

time: 11ms

memory: 3764kb

input:

output:

result:

points 0.96893333330 points  0.96893333330

Test #87:

score: 75

Accepted

time: 3ms

memory: 3792kb

input:

output:

result:

ok

Test #88:

score: 75

Accepted

time: 0ms

memory: 3816kb

input:

output:

result:

ok

Test #89:

score: 75

Accepted

time: 5ms

memory: 4120kb

input:

output:

result:

ok