QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#291160 | #6154. 保龄球 | MoRanSky | 100 ✓ | 8ms | 4100kb | C++23 | 1.1kb | 2023-12-26 05:08:38 | 2023-12-26 05:08:39 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N = 55;
int n, X[N], Y[N], m, p[N];
int ans = 0, sum;
int inline get() {
int res = sum;
for (int i = 1; i < m; i++)
if (X[p[i]] == 10) res += X[p[i + 1]] + Y[p[i + 1]];
else if (X[p[i]] + Y[p[i]] == 10) res += X[p[i + 1]];
ans = max(ans, res);
return res;
}
double inline rd() {
return (double)rand() / RAND_MAX;
}
void inline simulateAnneal() {
int v = get();
for (double t = 1e4; t > 1e-4; t *= 0.99) {
int a = rand() % m + 1, b = rand() % m + 1;
swap(p[a], p[b]);
if (n + (X[p[n]] == 10) == m) {
int nv = get();
if (exp(-((double)v - nv) / t) <= rd()) swap(p[a], p[b]);
else v = nv;
} else swap(p[a], p[b]);
}
}
int main() {
srand(time(0)); double s = clock();
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", X + i, Y + i);
if (X[n] == 10) scanf("%d%d", X + n + 1, Y + n + 1);
m = n + (X[n] == 10);
for (int i = 1; i <= m; i++) sum += X[i] + Y[i], p[i] = i;
for (int i = 0; i < 30; i++) simulateAnneal();
printf("%d", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 4ms
memory: 3960kb
input:
9 10 0 10 0 10 0 10 0 10 0 1 9 5 5 7 3 3 7
output:
170
result:
ok 1 number(s): "170"
Test #2:
score: 10
Accepted
time: 4ms
memory: 4020kb
input:
8 2 0 5 5 9 1 10 0 3 4 1 4 4 6 3 6
output:
96
result:
ok 1 number(s): "96"
Test #3:
score: 10
Accepted
time: 3ms
memory: 4036kb
input:
20 6 4 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 0 5
output:
400
result:
ok 1 number(s): "400"
Test #4:
score: 10
Accepted
time: 6ms
memory: 3980kb
input:
20 6 3 10 0 2 8 10 0 0 10 4 0 10 0 6 4 0 10 10 0 10 0 10 0 0 10 9 0 3 7 7 1 0 4 8 0 3 6 10 0 10 0
output:
330
result:
ok 1 number(s): "330"
Test #5:
score: 10
Accepted
time: 6ms
memory: 4100kb
input:
20 6 3 10 0 10 0 3 7 1 3 7 1 10 0 10 0 8 0 10 0 3 6 8 2 10 0 10 0 10 0 3 1 10 0 5 2 3 3 10 0 5 4
output:
303
result:
ok 1 number(s): "303"
Test #6:
score: 10
Accepted
time: 7ms
memory: 3752kb
input:
50 10 0 5 5 10 0 7 3 0 10 9 1 10 0 10 0 4 6 10 0 10 0 10 0 3 7 10 0 10 0 10 0 2 8 3 7 2 8 7 3 10 0 6 4 1 9 0 10 10 0 6 4 8 2 10 0 2 8 3 7 7 3 9 1 2 8 1 9 10 0 10 0 10 0 1 9 1 9 10 0 9 1 10 0 6 4 2 8 4 6 4 6 5 5 0 10 10 0 10 0 9 1
output:
987
result:
ok 1 number(s): "987"
Test #7:
score: 10
Accepted
time: 7ms
memory: 3960kb
input:
49 4 6 3 7 5 5 1 9 0 10 10 0 0 10 2 8 10 0 8 2 8 2 4 6 10 0 10 0 8 2 6 4 5 5 10 0 1 9 2 8 10 0 3 7 10 0 10 0 10 0 7 3 2 8 8 2 8 2 10 0 10 0 9 0 5 5 10 0 6 4 10 0 5 5 10 0 10 0 8 2 8 2 5 5 0 10 0 10 8 1 10 0 0 10 8 2 10 0 1 9
output:
939
result:
ok 1 number(s): "939"
Test #8:
score: 10
Accepted
time: 2ms
memory: 4084kb
input:
50 5 5 7 3 7 3 6 4 3 7 10 0 2 8 1 9 7 3 9 1 7 3 9 1 5 5 2 8 3 7 7 3 0 10 4 6 0 10 0 10 8 2 7 3 4 6 9 0 8 2 2 8 9 1 4 6 7 3 0 10 9 1 5 5 3 7 7 3 4 6 9 1 0 10 0 10 7 3 2 8 3 7 2 8 9 1 4 6 5 5 2 8 0 10 9 1 7 3 6 4
output:
754
result:
ok 1 number(s): "754"
Test #9:
score: 10
Accepted
time: 8ms
memory: 3980kb
input:
50 9 1 5 5 0 10 5 5 3 4 10 0 3 7 5 0 4 6 7 1 2 4 9 1 3 0 2 8 5 5 7 2 5 4 7 1 6 4 8 2 3 7 0 6 0 4 1 7 2 6 4 0 6 4 1 9 1 9 6 3 2 8 5 3 4 3 0 2 0 0 5 5 1 3 4 1 0 10 9 0 4 6 0 10 4 5 4 6 10 0 2 8 9 0 3 7 1 9 8 0
output:
593
result:
ok 1 number(s): "593"
Test #10:
score: 10
Accepted
time: 7ms
memory: 3752kb
input:
50 7 2 1 1 2 8 7 3 9 1 0 10 6 4 3 7 3 7 2 8 10 0 8 2 6 1 4 3 0 3 8 2 9 1 9 1 5 5 0 0 1 1 6 4 4 0 1 5 10 0 8 2 9 0 2 8 1 6 8 2 8 0 1 0 5 0 8 2 3 7 1 9 6 3 7 3 1 9 2 0 9 0 5 5 1 2 4 2 5 5 7 3 3 5 5 5 0 10 10 0 0 10
output:
649
result:
ok 1 number(s): "649"