QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#140416	#4565. Rarest Insects	somethingnew^#	89.92	22ms	4092kb	C++20	4.6kb	2023-08-15 21:18:44	2024-07-04 01:44:54

Judging History

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

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

测评结果：89.92
用时：22ms
内存：4092kb

查看

[2023-08-15 21:18:44]
提交

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);
    int timka = 1;
    for (int i = 0; i < N; ++i) {
        swap(iba[i], iba[rnd() % N]);
    }
    int cnt = 0;
    int gcnt = 0;
    int prvl = 3;
    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] = timka;
        }
    }
    timka++;
    gcnt = cnt * 2;
    cnt = gcnt;
    for (int i = (lstch + 1) % N; i != lstch; i = (i + 1) % N) {
        //cerr << i << endl;
        if (ex[i] == 0) {
            //cerr << i << endl;
            move_inside(iba[i]);
            if (prvl < press_button()) {
                move_outside(iba[i]);
            } else {
                ex[i] = timka;
                cnt--;
                lstch = i;
                if (cnt == 0) {
                    timka++;
                    cnt = gcnt;
                    prvl += 2;
                }
            }
        }
    }
    cnt = gcnt / 2;
    prvl--;
    for (int i = 0; i < N; ++i) {
        if (ex[i] == timka) {
            //cout << i << endl;
            ex[i] = 0;
            move_outside(iba[i]);

        }
    }
    for (int i = 0; i < N; ++i) {
        if (ex[i] == 0) {
            //cerr << i << endl;
            move_inside(iba[i]);
            if (prvl != press_button()) {
                move_outside(iba[i]);
            } else {
                ex[i] = timka;
                cnt--;
                if (cnt == 0) {
                    prvl++;
                    break;
                }
            }
        }
    }
    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() {
    N=2000;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;
        Ti = i % 6 + 1;
        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: 3872kb

input:

output:

result:

ok

Test #2:

score: 0

Accepted

time: 1ms

memory: 3780kb

input:

output:

result:

ok

Test #3:

score: 0

Accepted

time: 1ms

memory: 3800kb

input:

2
1
1

output:

result:

ok

Test #4:

score: 0

Accepted

time: 0ms

memory: 3796kb

input:

output:

result:

ok

Test #5:

score: 0

Accepted

time: 1ms

memory: 3804kb

input:

output:

result:

ok

Test #6:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

output:

result:

ok

Test #7:

score: 0

Accepted

time: 3ms

memory: 4088kb

input:

output:

result:

ok

Test #8:

score: 0

Accepted

time: 0ms

memory: 3792kb

input:

output:

result:

ok

Test #9:

score: 0

Accepted

time: 4ms

memory: 3792kb

input:

output:

result:

ok

Test #10:

score: 0

Accepted

time: 4ms

memory: 3764kb

input:

output:

result:

ok

Test #11:

score: 0

Accepted

time: 3ms

memory: 4064kb

input:

output:

result:

ok

Test #12:

score: 0

Accepted

time: 3ms

memory: 4060kb

input:

output:

result:

ok

Test #13:

score: 0

Accepted

time: 0ms

memory: 4032kb

input:

output:

result:

ok

Test #14:

score: 0

Accepted

time: 3ms

memory: 3728kb

input:

output:

result:

ok

Test #15:

score: 0

Accepted

time: 0ms

memory: 3800kb

input:

output:

result:

ok

Test #16:

score: 0

Accepted

time: 0ms

memory: 3772kb

input:

output:

result:

ok

Test #17:

score: 0

Accepted

time: 3ms

memory: 3792kb

input:

output:

result:

ok

Test #18:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

output:

result:

ok

Test #19:

score: 0

Accepted

time: 0ms

memory: 3772kb

input:

output:

result:

ok

Test #20:

score: 0

Accepted

time: 4ms

memory: 3776kb

input:

output:

result:

ok

Test #21:

score: 0

Accepted

time: 3ms

memory: 3728kb

input:

output:

result:

ok

Test #22:

score: 0

Accepted

time: 3ms

memory: 4068kb

input:

output:

result:

ok

Test #23:

score: 0

Accepted

time: 2ms

memory: 3800kb

input:

output:

result:

ok

Subtask #2:

score: 15

Accepted

Test #24:

score: 15

Accepted

time: 12ms

memory: 4036kb

input:

output:

result:

ok

Test #25:

score: 0

Accepted

time: 6ms

memory: 4040kb

input:

output:

result:

ok

Test #26:

score: 0

Accepted

time: 5ms

memory: 3868kb

input:

output:

result:

ok

Test #27:

score: 0

Accepted

time: 3ms

memory: 3804kb

input:

output:

result:

ok

Test #28:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok

Test #29:

score: 0

Accepted

time: 0ms

memory: 3736kb

input:

output:

result:

ok

Test #30:

score: 0

Accepted

time: 0ms

memory: 3784kb

input:

output:

result:

ok

Test #31:

score: 0

Accepted

time: 10ms

memory: 3864kb

input:

output:

result:

ok

Test #32:

score: 0

Accepted

time: 0ms

memory: 4036kb

input:

output:

result:

ok

Test #33:

score: 0

Accepted

time: 0ms

memory: 4040kb

input:

output:

result:

ok

Test #34:

score: 0

Accepted

time: 17ms

memory: 3780kb

input:

output:

result:

ok

Test #35:

score: 0

Accepted

time: 8ms

memory: 3808kb

input:

output:

result:

ok

Test #36:

score: 0

Accepted

time: 3ms

memory: 4068kb

input:

output:

result:

ok

Test #37:

score: 0

Accepted

time: 0ms

memory: 3808kb

input:

output:

result:

ok

Test #38:

score: 0

Accepted

time: 13ms

memory: 3816kb

input:

output:

result:

ok

Test #39:

score: 0

Accepted

time: 14ms

memory: 4064kb

input:

output:

result:

ok

Test #40:

score: 0

Accepted

time: 2ms

memory: 3808kb

input:

output:

result:

ok

Test #41:

score: 0

Accepted

time: 4ms

memory: 3784kb

input:

output:

result:

ok

Test #42:

score: 0

Accepted

time: 2ms

memory: 3872kb

input:

output:

result:

ok

Subtask #3:

score: 64.92

Acceptable Answer

Test #43:

score: 75

Accepted

time: 0ms

memory: 3796kb

input:

output:

result:

ok

Test #44:

score: 75

Accepted

time: 0ms

memory: 3768kb

input:

2
1
1

output:

result:

ok

Test #45:

score: 75

Accepted

time: 0ms

memory: 3788kb

input:

output:

result:

ok

Test #46:

score: 75

Accepted

time: 1ms

memory: 3740kb

input:

output:

result:

ok

Test #47:

score: 75

Accepted

time: 0ms

memory: 3756kb

input:

output:

result:

ok

Test #48:

score: 75

Accepted

time: 0ms

memory: 4076kb

input:

output:

result:

ok

Test #49:

score: 75

Accepted

time: 4ms

memory: 3784kb

input:

output:

result:

ok

Test #50:

score: 70.7

Acceptable Answer

time: 8ms

memory: 3816kb

input:

output:

result:

points 0.94266666670 points  0.94266666670

Test #51:

score: 66.61

Acceptable Answer

time: 13ms

memory: 3820kb

input:

output:

result:

points 0.88813333330 points  0.88813333330

Test #52:

score: 75

Accepted

time: 13ms

memory: 3876kb

input:

output:

result:

ok

Test #53:

score: 75

Accepted

time: 4ms

memory: 3792kb

input:

output:

result:

ok

Test #54:

score: 71.65

Acceptable Answer

time: 18ms

memory: 3748kb

input:

output:

result:

points 0.95533333330 points  0.95533333330

Test #55:

score: 74.98

Acceptable Answer

time: 10ms

memory: 3824kb

input:

output:

result:

points 0.99973333330 points  0.99973333330

Test #56:

score: 71.31

Acceptable Answer

time: 0ms

memory: 3872kb

input:

output:

result:

points 0.95080 points  0.95080

Test #57:

score: 65.26

Acceptable Answer

time: 4ms

memory: 3776kb

input:

output:

result:

points 0.87013333330 points  0.87013333330

Test #58:

score: 68.2

Acceptable Answer

time: 12ms

memory: 4076kb

input:

output:

result:

points 0.90933333330 points  0.90933333330

Test #59:

score: 69.76

Acceptable Answer

time: 7ms

memory: 3792kb

input:

output:

result:

points 0.93013333330 points  0.93013333330

Test #60:

score: 69.94

Acceptable Answer

time: 8ms

memory: 4088kb

input:

output:

result:

points 0.93253333330 points  0.93253333330

Test #61:

score: 64.92

Acceptable Answer

time: 4ms

memory: 4080kb

input:

output:

result:

points 0.86560 points  0.86560

Test #62:

score: 68.87

Acceptable Answer

time: 12ms

memory: 4092kb

input:

output:

result:

points 0.91826666670 points  0.91826666670

Test #63:

score: 71.61

Acceptable Answer

time: 0ms

memory: 3816kb

input:

output:

result:

points 0.95480 points  0.95480

Test #64:

score: 73.92

Acceptable Answer

time: 17ms

memory: 3796kb

input:

output:

result:

points 0.98560 points  0.98560

Test #65:

score: 75

Accepted

time: 15ms

memory: 3764kb

input:

output:

result:

ok

Test #66:

score: 75

Accepted

time: 7ms

memory: 4088kb

input:

output:

result:

ok

Test #67:

score: 75

Accepted

time: 7ms

memory: 3792kb

input:

output:

result:

ok

Test #68:

score: 71

Acceptable Answer

time: 11ms

memory: 3788kb

input:

output:

result:

points 0.94666666670 points  0.94666666670

Test #69:

score: 70.89

Acceptable Answer

time: 22ms

memory: 3816kb

input:

output:

result:

points 0.94520 points  0.94520

Test #70:

score: 69.24

Acceptable Answer

time: 7ms

memory: 3820kb

input:

output:

result:

points 0.92320 points  0.92320

Test #71:

score: 69.17

Acceptable Answer

time: 10ms

memory: 4028kb

input:

output:

result:

points 0.92226666670 points  0.92226666670

Test #72:

score: 71.02

Acceptable Answer

time: 0ms

memory: 3788kb

input:

output:

result:

points 0.94693333330 points  0.94693333330

Test #73:

score: 69.8

Acceptable Answer

time: 8ms

memory: 4084kb

input:

output:

result:

points 0.93066666670 points  0.93066666670

Test #74:

score: 75

Accepted

time: 5ms

memory: 4044kb

input:

output:

result:

ok

Test #75:

score: 74.35

Acceptable Answer

time: 10ms

memory: 3768kb

input:

output:

result:

points 0.99133333330 points  0.99133333330

Test #76:

score: 70.13

Acceptable Answer

time: 12ms

memory: 3816kb

input:

output:

result:

points 0.93506666670 points  0.93506666670

Test #77:

score: 69.46

Acceptable Answer

time: 8ms

memory: 3868kb

input:

output:

result:

points 0.92613333330 points  0.92613333330

Test #78:

score: 72.03

Acceptable Answer

time: 12ms

memory: 3808kb

input:

output:

result:

points 0.96040 points  0.96040

Test #79:

score: 72.05

Acceptable Answer

time: 14ms

memory: 3820kb

input:

output:

result:

points 0.96066666670 points  0.96066666670

Test #80:

score: 73.24

Acceptable Answer

time: 0ms

memory: 3784kb

input:

output:

result:

points 0.97653333330 points  0.97653333330

Test #81:

score: 73.25

Acceptable Answer

time: 0ms

memory: 4048kb

input:

output:

result:

points 0.97666666670 points  0.97666666670

Test #82:

score: 68.13

Acceptable Answer

time: 6ms

memory: 3796kb

input:

output:

result:

points 0.90840 points  0.90840

Test #83:

score: 70.37

Acceptable Answer

time: 6ms

memory: 3792kb

input:

output:

result:

points 0.93826666670 points  0.93826666670

Test #84:

score: 73.26

Acceptable Answer

time: 5ms

memory: 3772kb

input:

output:

result:

points 0.97680 points  0.97680

Test #85:

score: 71.9

Acceptable Answer

time: 4ms

memory: 3784kb

input:

output:

result:

points 0.95866666670 points  0.95866666670

Test #86:

score: 75

Accepted

time: 4ms

memory: 3872kb

input:

output:

result:

ok

Test #87:

score: 75

Accepted

time: 10ms

memory: 3820kb

input:

output:

result:

ok

Test #88:

score: 75

Accepted

time: 7ms

memory: 3796kb

input:

output:

result:

ok

Test #89:

score: 75

Accepted

time: 5ms

memory: 4092kb

input:

output:

result:

ok