QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #558577 | #9239. Hieroglyphs | zhouhuanyi | 0 | 28ms | 82564kb | C++17 | 1.3kb | 2024-09-11 16:54:19 | 2024-09-11 16:54:19 |
Judging History
answer
#include "hieroglyphs.h"
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define N 3000
#define M 200000
using namespace std;
const int inf=(int)(1e9);
int tong[N+1],num[M+1],leng,length,dp[N+1][N+1],tr[N+1][N+1],nt[N+1][N+1];
bool used[M+1];
std::vector<int> ucs(std::vector<int> A, std::vector<int> B)
{
vector<int>v;
int x,y;
for (int i=1;i<=A.size();++i)
for (int j=1;j<=B.size();++j)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if (A[i-1]==B[j-1]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
}
x=A.size(),y=B.size();
while (x&&y)
{
if (A[x-1]==B[y-1]&&dp[x][y]==dp[x-1][y-1]+1) tong[++length]=A[x-1],x--,y--;
else if (dp[x-1][y]==dp[x][y]) x--;
else y--;
}
reverse(tong+1,tong+length+1);
for (int i=1;i<=length;++i) used[tong[i]]=1;
for (int i=1;i<=M;++i)
if (used[i])
num[i]=++leng;
for (int i=length;i>=0;--i)
{
for (int j=1;j<=leng;++j) nt[i][j]=nt[i+1][j];
if (i+1<=length) nt[i][num[tong[i+1]]]=i+1;
}
for (int i=1;i<=A.size();++i)
for (int j=1;j<=B.size();++j)
{
tr[i][j]=max(tr[i-1][j],tr[i][j-1]);
if (A[i-1]==B[j-1])
{
if (!nt[tr[i-1][j-1]][num[A[i-1]]]) return {-1};
tr[i][j]=max(tr[i][j],nt[tr[i-1][j-1]][num[A[i-1]]]);
}
}
for (int i=1;i<=length;++i) v.push_back(tong[i]);
return v;
}
詳細信息
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 3
Accepted
time: 1ms
memory: 3828kb
input:
vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB 10 10 7 1 9 2 3 5 0 6 8 4 7 1 9 2 3 5 0 6 8 4
output:
IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ OK 10 7 1 9 2 3 5 0 6 8 4
result:
ok
Test #2:
score: 3
Accepted
time: 1ms
memory: 3816kb
input:
vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB 10 10 7 9 4 5 6 8 2 1 3 0 7 9 4 5 8 6 2 1 3 0
output:
IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ OK 1 -1
result:
ok
Test #3:
score: 3
Accepted
time: 7ms
memory: 32932kb
input:
vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB 1000 1000 227 14 144 355 329 614 282 987 90 67 421 904 584 672 129 286 187 498 450 29 342 688 521 133 585 769 794 138 731 946 28 996 402 935 96 855 2 186 361 1 451 914 318 720 296 389 356 364 400 971 387 979 520 885 604 62 814 474 479 952 394 640 959 246 509 171 486 ...
output:
IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ OK 1000 227 14 144 355 329 614 282 987 90 67 421 904 584 672 129 286 187 498 450 29 342 688 521 133 585 769 794 138 731 946 28 996 402 935 96 855 2 186 361 1 451 914 318 720 296 389 356 364 400 971 387 979 520 885 604 62 814 474 479 952 394 640 959 246 509 171 486 35...
result:
ok
Test #4:
score: 3
Accepted
time: 5ms
memory: 25348kb
input:
vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB 997 997 615 691 867 398 544 236 744 802 466 701 700 106 636 993 668 105 409 810 957 249 619 293 729 339 189 537 70 237 487 360 276 693 181 954 85 310 669 52 86 12 209 787 294 188 64 561 828 44 564 480 895 283 289 924 192 783 890 948 674 279 114 229 822 771 458 179 65...
output:
IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ OK 1 -1
result:
ok
Test #5:
score: 0
Runtime Error
input:
vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB 100000 100000 19751 36170 33104 26686 54203 5214 37609 58763 10536 82655 80942 70794 54794 16739 55137 38172 11159 41408 34850 54300 58781 6684 19791 28867 83340 19360 7277 54060 59942 87198 45397 49198 66950 26865 7468 7059 58566 43804 99565 76536 48614 34101 26106 ...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #8:
score: 0
Runtime Error
input:
vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB 89984 90016 167910 187180 47437 150113 199404 61979 49501 155514 167910 175137 104441 149717 155514 13573 170025 181983 117868 13573 149717 166954 145922 29787 93788 58581 158693 51768 120499 17700 17700 4746 119328 33450 138501 137246 33450 135751 84363 168724 15701...
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #71:
score: 0
Time Limit Exceeded
input:
vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB 100000 100000 0 1 0 0 1 1 1 1 0 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 0 1 0...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #97:
score: 0
Runtime Error
input:
vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB 20000 30000 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110955 110...
output:
result:
Subtask #5:
score: 0
Wrong Answer
Test #132:
score: 0
Wrong Answer
time: 28ms
memory: 82564kb
input:
vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB 2800 2999 47 51 42 122 38 125 170 11 119 48 289 297 27 150 207 271 11 15 67 287 149 220 76 274 128 151 60 117 39 123 254 75 170 198 72 179 274 203 13 88 139 153 46 288 13 282 16 219 284 91 274 63 190 157 72 286 238 1 219 82 82 31 285 128 198 172 161 271 36 111 160 26...
output:
IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ OK 1 -1
result:
wrong answer 3rd lines differ - on the 1st token, expected: '2800', found: '1'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%