QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#858398#4754. Ballsrotcar07AC ✓273ms4352kbC++23612b2025-01-16 16:57:162025-01-16 16:57:18

Judging History

This is the latest submission verdict.

  • [2025-01-16 16:57:18]
  • Judged
  • Verdict: AC
  • Time: 273ms
  • Memory: 4352kb
Show
  • [2025-01-16 16:57:16]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int B=400,N=2e5+5;
double f[3][B+5];
int ans[N];
inline void solve(){
    int n;cin>>n;
    cout<<ans[n]<<'\n';
}
int main(){
    for(int i=1;i<=200000;i++){
        auto g=[&](int x,int y) -> double {if(y<=0) return 0;if(x<=y)return 1;return f[x%3][y];};
        for(int j=0;j<=min(i,B);j++) f[i%3][j]=g(i-2,j)*(i-j)/i+g(i-2,j-1)*j/i;
        double dt=1;
        for(int j=0;j<=min(i,B);j++){
            double z=f[i%3][j],w=fabs(z-0.5);
            if(dt>w) dt=w,ans[i]=j;
        }
    }
    int t;cin>>t;
    while(t--) solve();
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 234ms
memory: 4352kb

input:

5
2
3
6
7
8

output:

1
1
2
1
2

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 269ms
memory: 4224kb

input:

100000
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101...

output:

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

result:

ok 100000 lines

Test #3:

score: 0
Accepted
time: 273ms
memory: 4096kb

input:

100000
100001
100002
100003
100004
100005
100006
100007
100008
100009
100010
100011
100012
100013
100014
100015
100016
100017
100018
100019
100020
100021
100022
100023
100024
100025
100026
100027
100028
100029
100030
100031
100032
100033
100034
100035
100036
100037
100038
100039
100040
100041
100042...

output:

156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
213
156
...

result:

ok 100000 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

伺服器時間: 2025-04-12 04:08:33 | 開源專案