QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #279302 | #1833. Deleting | rageOfThunder# | WA | 3ms | 13864kb | C++14 | 1.8kb | 2023-12-08 15:43:20 | 2023-12-08 15:43:20 |
Judging History
answer
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) {x = max(x, y);}
template <typename T> inline void chkmin(T& x, T y) {x = min(x, y);}
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
const int N = 4010;
int n, cost[N][N], x[N * N], y[N * N];
bitset <N> f1[N], f2[N], g[N];
void doit(int l, int r) {
f1[l][r] = f2[r][l] = true;
if (g[l - 1][r + 1]) doit(l - 1, r + 1);
// 找右端点
{
bitset <N> t = f1[l];
t.flip();
t &= f1[r];
vector <int> w;
for (int i = t._Find_first(); i < N; i = t._Find_next(i)) w.push_back(i);
reverse(all(w));
for (int i: w) doit(l, i);
}
// 找左端点
{
bitset <N> t = f2[r];
t.flip();
t &= f2[l - 1];
vector <int> w;
for (int i = t._Find_first(); i < N; i = t._Find_next(i)) w.push_back(i);
reverse(all(w));
for (int i: w) doit(i, r);
}
}
signed main() {
read(n);
F(i, 1, n)
for (int j = i + 1; j <= n; j += 2) {
read(cost[i][j]);
x[cost[i][j]] = i;
y[cost[i][j]] = j;
}
// F(i, 0, n) f1[i + 1][i] = true;
F(i, 1, (n / 2) * (n / 2)) {
g[x[i]][y[i]] = true;
if (!f1[x[i]][y[i]] && (f1[x[i] + 1][y[i] - 1] || x[i] + 1 == y[i])) doit(x[i], y[i]);
if (f1[1][n]) {
cout << i;
return 0;
}
}
return 0;
}
/* why?
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11680kb
input:
2 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 9956kb
input:
6 2 1 3 4 5 6 7 8 9
output:
6
result:
ok 1 number(s): "6"
Test #3:
score: 0
Accepted
time: 0ms
memory: 11972kb
input:
10 20 21 2 11 25 3 24 18 8 6 17 7 5 22 4 23 14 15 1 19 16 12 10 13 9
output:
14
result:
ok 1 number(s): "14"
Test #4:
score: 0
Accepted
time: 0ms
memory: 13864kb
input:
16 49 48 18 41 52 64 4 6 22 20 32 50 56 36 9 3 1 27 58 51 35 40 61 43 38 12 7 34 8 59 39 25 46 16 44 29 15 17 24 10 47 2 57 62 14 5 23 33 30 45 19 60 63 28 13 54 55 26 53 31 11 42 21 37
output:
30
result:
ok 1 number(s): "30"
Test #5:
score: 0
Accepted
time: 2ms
memory: 11816kb
input:
20 91 19 90 92 5 41 15 50 18 36 97 8 23 74 53 67 83 40 26 4 16 31 82 80 28 49 6 21 58 63 70 34 27 89 68 20 55 100 35 77 52 24 11 87 94 13 66 1 32 54 86 60 79 75 93 45 73 2 48 72 12 37 29 95 56 17 44 84 30 22 14 65 76 69 62 47 78 7 57 42 39 61 99 81 88 25 98 59 85 38 10 33 51 71 64 46 43 3 96 9
output:
54
result:
ok 1 number(s): "54"
Test #6:
score: 0
Accepted
time: 3ms
memory: 13852kb
input:
100 750 481 1065 911 1943 427 1633 45 1841 234 1376 1075 1603 1682 1581 1284 28 5 1567 1540 2409 1430 695 667 1246 392 1183 1090 594 1481 524 2023 354 778 584 827 1516 796 1675 1829 189 1688 706 1679 1483 1010 1209 1393 399 210 40 149 1040 351 1435 320 340 577 898 449 1896 224 2168 1456 1222 1216 19...
output:
1289
result:
ok 1 number(s): "1289"
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 11800kb
input:
100 561 1112 852 529 2112 323 265 2038 1970 1681 556 2261 887 277 1171 553 1887 48 2432 266 1304 1764 853 2205 2320 1532 571 1870 193 544 1135 874 2132 1162 102 2179 2307 2068 1990 1111 2420 2077 1779 2000 1996 2297 1981 450 1091 992 140 2474 744 537 42 1051 1086 1685 1307 1282 2387 167 31 1179 301 ...
output:
1169
result:
wrong answer 1st numbers differ - expected: '1082', found: '1169'