QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#520339#4565. Rarest Insectskimmoqt0 14ms4120kbC++202.4kb2024-08-15 13:03:212024-08-15 13:03:21

Judging History

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

  • [2024-08-15 13:03:21]
  • 评测
  • 测评结果：0
  • 用时：14ms
  • 内存：4120kb
查看
  • [2024-08-15 13:03:21]
  • 提交

answer

#include "insects.h"

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int cnt[2005];

int min_cardinality(int N) {
        vector<bool> vis(N);

        // strategy 1 : large distinct (>= 52)

        vector<int> pos;
        for(int i=0;i<N;i++) {
                if(vis[i]) continue;
                move_inside(i);

                if(press_button()==2) {
                        move_outside(i);
                } else {
                        vis[i]=true;
                        pos.push_back(i);
                }
        }

        if(pos.size()>=52) {
                int p=pos.size(),res=1;
                while(true) {
                        for(auto x:pos) {
                                move_outside(x);
                        }
                        pos.clear();

                        for(int i=0;i<N;i++) {
                                if(vis[i]) continue;
                                move_inside(i);

                                if(press_button()==2) {
                                        move_outside(i);
                                } else {
                                        vis[i]=true;
                                        pos.push_back(i);
                                }
                        }

                        if(pos.size()!=p) break;
                        res++;
                }

                return res;
        } else {
                for(int i=0;i<N;i++) {
                        if(vis[i]) continue;

                        move_inside(i);

                        vector<bool> done(pos.size());
                        while(true) {
                                int id=rng()%pos.size();
                                if(done[id]) continue;
                                done[id]=true;
                                move_outside(pos[id]);
                                if(press_button()==1) {
                                        cnt[pos[id]]+=1;
                                        break;
                                }
                                move_inside(pos[id]);
                        }

                        move_outside(i);
                }

                int res=N;
                for(auto j:pos) {
                        res=min(res,cnt[j]);
                }

                return res+1;
        }
}
源文件, 语言: C++20

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 1ms
memory: 3876kb

input:

6
1
1
1
2
2
2
1
2
2
1
1

output:

8
0 0
8
2
8
0 1
8
2
8
0 2
8
2
8
0 3
8
2
8
1 3
8
0 4
8
2
8
1 4
8
0 5
8
2
8
1 5
8
0 3
8
1 0
8
2
8
1 3
8
0 4
8
1 1
8
2
8
0 1
8
1 0
8
2
8
0 0
8
1 2
8
2
8
1 4
8
0 5
8
1 0
8
2
8
1 5
8
3 1

result:

ok

Test #2:

score: 10
Accepted
time: 0ms
memory: 3880kb

input:

2
1
2
1

output:

8
0 0
8
2
8
0 1
8
2
8
1 1
8
0 1
8
1 0
8
2
8
1 1
8
3 2

result:

ok

Test #3:

score: 10
Accepted
time: 0ms
memory: 3852kb

input:

2
1
1

output:

8
0 0
8
2
8
0 1
8
2
8
3 1

result:

ok

Test #4:

score: 10
Accepted
time: 0ms
memory: 3812kb

input:

3
1
1
2
1

output:

8
0 0
8
2
8
0 1
8
2
8
0 2
8
2
8
1 2
8
0 2
8
1 1
8
2
8
1 2
8
3 1

result:

ok

Test #5:

score: 10
Accepted
time: 1ms
memory: 3880kb

input:

5
1
1
2
2
2
1
1
1

output:

8
0 0
8
2
8
0 1
8
2
8
0 2
8
2
8
1 2
8
0 3
8
2
8
1 3
8
0 4
8
2
8
1 4
8
0 2
8
1 1
8
2
8
1 2
8
0 3
8
1 0
8
2
8
1 3
8
0 4
8
1 0
8
2
8
1 4
8
3 2

result:

ok

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 4112kb

input:

8
1
1
2
2
2
2
2
1
2
1
1
1
1
1

output:

8
0 0
8
2
8
0 1
8
2
8
0 2
8
2
8
1 2
8
0 3
8
2
8
1 3
8
0 4
8
2
8
1 4
8
0 5
8
2
8
1 5
8
0 6
8
2
8
1 6
8
0 7
8
2
8
0 2
8
1 7
8
2
8
0 7
8
1 1
8
2
8
1 2
8
0 3
8
1 0
8
2
8
1 3
8
0 4
8
1 7
8
2
8
1 4
8
0 5
8
1 0
8
2
8
1 5
8
0 6
8
1 1
8
2
8
1 6
8
3 2

result:

wrong answer Wrong answer.

Subtask #2:

score: 0
Wrong Answer

Test #24:

score: 15
Accepted
time: 0ms
memory: 3804kb

input:

1000
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2...

output:

8
0 0
8
2
8
0 1
8
2
8
1 1
8
0 2
8
2
8
1 2
8
0 3
8
2
8
1 3
8
0 4
8
2
8
1 4
8
0 5
8
2
8
1 5
8
0 6
8
2
8
1 6
8
0 7
8
2
8
1 7
8
0 8
8
2
8
1 8
8
0 9
8
2
8
1 9
8
0 10
8
2
8
1 10
8
0 11
8
2
8
1 11
8
0 12
8
2
8
1 12
8
0 13
8
2
8
1 13
8
0 14
8
2
8
1 14
8
0 15
8
2
8
1 15
8
0 16
8
2
8
1 16
8
0 17
8
2
8
1 17
8
...

result:

ok

Test #25:

score: 15
Accepted
time: 5ms
memory: 3856kb

input:

1000
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

output:

8
0 0
8
2
8
0 1
8
2
8
0 2
8
2
8
0 3
8
2
8
0 4
8
2
8
0 5
8
2
8
0 6
8
2
8
0 7
8
2
8
0 8
8
2
8
0 9
8
2
8
0 10
8
2
8
0 11
8
2
8
0 12
8
2
8
0 13
8
2
8
0 14
8
2
8
0 15
8
2
8
0 16
8
2
8
0 17
8
2
8
0 18
8
2
8
0 19
8
2
8
0 20
8
2
8
0 21
8
2
8
0 22
8
2
8
0 23
8
2
8
0 24
8
2
8
0 25
8
2
8
0 26
8
2
8
0 27
8
2
8
...

result:

ok

Test #26:

score: 0
Wrong Answer
time: 14ms
memory: 3872kb

input:

999
1
1
1
1
1
1
1
1
1
2
1
1
1
1
2
2
1
1
1
1
1
1
2
2
2
2
2
2
2
2
1
2
2
1
2
2
2
2
1
1
1
1
2
2
1
2
1
1
2
2
2
1
2
2
2
2
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

output:

8
0 0
8
2
8
0 1
8
2
8
0 2
8
2
8
0 3
8
2
8
0 4
8
2
8
0 5
8
2
8
0 6
8
2
8
0 7
8
2
8
0 8
8
2
8
0 9
8
2
8
1 9
8
0 10
8
2
8
0 11
8
2
8
0 12
8
2
8
0 13
8
2
8
0 14
8
2
8
1 14
8
0 15
8
2
8
1 15
8
0 16
8
2
8
0 17
8
2
8
0 18
8
2
8
0 19
8
2
8
0 20
8
2
8
0 21
8
2
8
0 22
8
2
8
1 22
8
0 23
8
2
8
1 23
8
0 24
8
2
8...

result:

wrong answer Wrong answer.

Subtask #3:

score: 0
Wrong Answer

Test #43:

score: 75
Accepted
time: 1ms
memory: 3872kb

input:

2
1
2
1

output:

8
0 0
8
2
8
0 1
8
2
8
1 1
8
0 1
8
1 0
8
2
8
1 1
8
3 2

result:

ok

Test #44:

score: 75
Accepted
time: 1ms
memory: 3888kb

input:

2
1
1

output:

8
0 0
8
2
8
0 1
8
2
8
3 1

result:

ok

Test #45:

score: 75
Accepted
time: 1ms
memory: 3820kb

input:

3
1
1
2
1

output:

8
0 0
8
2
8
0 1
8
2
8
0 2
8
2
8
1 2
8
0 2
8
1 1
8
2
8
1 2
8
3 1

result:

ok

Test #46:

score: 0
Wrong Answer
time: 1ms
memory: 4120kb

input:

6
1
2
1
2
2
2
1
1
1
1

output:

8
0 0
8
2
8
0 1
8
2
8
1 1
8
0 2
8
2
8
0 3
8
2
8
1 3
8
0 4
8
2
8
1 4
8
0 5
8
2
8
1 5
8
0 1
8
1 0
8
2
8
1 1
8
0 3
8
1 2
8
2
8
1 3
8
0 4
8
1 0
8
2
8
1 4
8
0 5
8
1 2
8
2
8
1 5
8
3 3

result:

wrong answer Wrong answer.
English 繁體中文 简体中文

伺服器時間: 2024-11-30 12:49:30 | 開源專案