QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #359611 | #5173. 染色 | zyc070419 | 0 | 70ms | 12148kb | C++14 | 1.6kb | 2024-03-20 19:26:55 | 2024-03-20 19:26:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
const int B = 15;
inline int read() {
char ch = getchar(); int x = 0;
while (!isdigit(ch)) {ch = getchar();}
while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
return x;
}
int n, T, a[N], dp[N][15], pre[N][15], lst[N], cnt[N];
set<int> S;
int main() {
n = read(); T = read();
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = 1; i <= n; ++i) {
if (S.find(lst[a[i]]) != S.end()) S.erase(lst[a[i]]);
if (S.find(lst[a[i]]) == S.end()) S.insert(i);
lst[a[i]] = i;
if (S.size() > B) S.erase(S.begin());
auto it = S.begin();
while (it != S.end()) pre[i][cnt[i]++] = a[*it], it++;
}
// for (int i = 1; i <= n; ++i) {
// for (int j = 0; j < B; ++j)
// printf("%d ", pre[i][j]);
// puts("");
// }
int l, r;
while (T--) {
l = read(); r = read();
if (l > r) swap(l, r);
for (int i = 0; i < B; ++i) dp[l][i] = 1e9;
dp[l][0] = 0;
for (int i = l; i < r; ++i) {
for (int j = 0; j < B; ++j) dp[i + 1][j] = 1e9;
for (int p = 0; p < B; ++p) {
if (!pre[i][p]) continue;
for (int q = 0; q < B; ++q) {
if (!pre[i + 1][q]) continue;
// printf("{%d} %d\n", i + 1, q);
dp[i + 1][q] = min(dp[i + 1][q], dp[i][p] + (pre[i][p] != pre[i + 1][q]) + (pre[i + 1][q] != a[i + 1]));
}
}
for (int j = 0; j < B; ++j) dp[i + 1][j]++;
// for (int j = 0; j < B; ++j) printf("dp[%d][%d] = %d\n", i + 1, j, dp[i + 1][j]);
}
int ans = 1e9;
for (int j = 0; j < B; ++j) ans = min(ans, dp[r][j]);
printf("%d\n", ans);
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 70ms
memory: 12148kb
input:
10000 100 84 85 52 2 78 53 20 21 23 76 37 44 18 5 37 8 81 65 46 58 69 1 69 37 53 46 37 35 35 89 1 77 35 6 46 59 89 46 25 55 50 38 61 67 44 23 29 24 46 4 42 15 34 77 20 34 83 79 12 50 69 26 38 14 9 66 80 72 22 26 9 68 35 38 19 84 92 30 83 62 100 71 81 60 7 37 64 50 33 60 86 75 45 78 32 53 3 48 87 60 ...
output:
3673 4579 5981 8394 731 7020 183 7330 493 1141 254 2253 13247 6260 456 7521 2168 10495 1792 2677 4809 294 6006 627 6662 6187 11431 2716 3163 7847 17812 512 5495 17866 9575 6155 5002 14599 671 463 15638 12687 8882 7844 11004 6611 6407 5027 9111 8541 2175 10315 2701 12555 4967 2146 8823 1911 6486 2831...
result:
wrong answer 1st words differ - expected: '3668', found: '3673'
Subtask #2:
score: 0
Time Limit Exceeded
Test #7:
score: 0
Time Limit Exceeded
input:
100000 100000 3 2 3 3 3 3 2 3 2 1 3 1 1 1 3 2 1 3 1 2 2 1 3 1 2 2 1 1 1 3 2 1 3 3 3 3 1 1 1 2 3 3 2 1 1 1 3 1 3 1 3 2 1 3 2 3 3 2 3 3 2 3 3 3 3 3 2 3 2 3 1 3 3 3 3 3 3 3 1 2 3 3 1 3 1 1 2 2 3 1 1 2 3 2 3 1 3 2 1 3 2 3 2 1 1 3 3 1 3 1 2 2 2 3 2 3 2 3 2 1 1 3 1 3 2 2 3 3 3 1 2 2 3 3 2 1 3 1 2 2 2 3 2 ...
output:
113195 133098 54920 6484 9200 78290 93920 29191 38940 111588 66620 7227 66020 42775 44639 49274 11103 107721 71677 10709 4735 87162 46860 75806 27270 10951 12238 59513 18640 55104 11625 7849 5520 38727 67277 58327 16940 70130 70341 53674 51865 550 18480 119885 4017 43297 62514 33972 9870 24982 33222...
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #15:
score: 0
Time Limit Exceeded
input:
5000 5000 256 63 197 36 75 66 33 72 27 75 66 248 29 166 209 252 141 95 84 226 147 249 116 94 192 256 199 273 182 166 116 274 27 211 154 144 283 23 53 110 215 11 164 284 161 221 251 96 43 47 18 115 12 51 156 61 116 209 93 98 47 165 174 106 83 67 184 75 12 290 183 197 112 240 67 56 215 148 104 5 141 2...
output:
1328 2708 1751 2619 4781 5015 2964 1333 885 5101 7846 4878 939 932 812 7301 7700 5348 3829 3239 4496 1583 2553 40 905 302 4370 3900 3829 5768 4629 1666 439 1422 3640 5280 569 119 2052 7652 9157 2055 3133 3699 2896 422 731 4023 179 3246 1445 1606 7162 3022 5979 8122 1544 3823 366 4494 3316 1749 819 2...
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #23:
score: 0
Time Limit Exceeded
input:
1000000 1000000 1105 3246 1880 3554 818 2331 2576 4140 149 4562 3498 3536 3400 4788 4363 4742 1216 4218 4032 1701 1489 4889 1761 3022 3145 4945 3067 4304 5016 4624 1612 13 1335 3613 1086 2210 386 3464 1156 3352 4341 5006 3465 3900 622 654 1826 2983 1250 4164 3335 4308 2995 1982 1347 4335 2535 5054 4...