QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#832881#9239. Hieroglyphshansiyuan#3 43ms29256kbC++141.4kb2024-12-26 10:10:352024-12-26 10:10:36

Judging History

你现在查看的是最新测评结果

  • [2024-12-26 10:10:36]
  • 评测
  • 测评结果：3
  • 用时：43ms
  • 内存：29256kb
查看
  • [2024-12-26 10:10:35]
  • 提交

answer

#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,tot,want,mxi;
vector<int> posA[N],posB[N];
struct nd{int x,y,num,f,pre;} p[10000000];
int mx[N],mxh[N];
vector<int> ans;
void update(int i,int x,int h){
    for(;i<=m;i+=i&-i)
        if(x>mx[i]) mx[i]=x,mxh[i]=h;
}
int query(int i){
    int res=0,id=0;
    for(;i;i-=i&-i)
        if(mx[i]>res) res=mx[i],id=mxh[i];
    return id;
}
void dfs(int i){
    if(!i) return;
    dfs(p[i].pre);
    ans.push_back(p[i].num);
}
bool cmp(nd x,nd y){
    if(x.x==y.x) return x.y>y.y;
    return x.x<y.x;
}
vector<int> ucs(vector<int> A, vector<int> B) {
    n = A.size();
    m = B.size();
    for(int i=0;i<n;i++)
        posA[A[i]].push_back(i);
    for(int i=0;i<m;i++)
        posB[B[i]].push_back(i);
    for(int i=0;i<2e5;i++){
        want += min(posA[i].size(),posB[i].size());
        for(int x:posA[i])
            for(int y:posB[i])
                p[++tot] = {x+1,y+1,i,1,0};
    }
    sort(p+1,p+tot+1,cmp);
    // for(int i=1;i<=tot;i++) cerr<<p[i].x<<' '<<p[i].y<<' '<<p[i].num<<endl;
    for(int i=1;i<=tot;i++){
        for(int j=p[i].y;j;j-=j&-j)
            if(mx[j]+1>p[i].f) p[i].f=mx[j]+1,p[i].pre=mxh[j];
        if(p[i].f>p[mxi].f) mxi=i;
        update(p[i].y+1,p[i].f,i);
    }
    if(p[mxi].f!=want){
        ans.push_back(-1);
        return ans;
    }
    dfs(mxi);
    return ans;
}
源文件, 语言: C++14

详细

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 0ms
memory: 17284kb

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: 3ms
memory: 14228kb

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: 3ms
memory: 16256kb

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: 3ms
memory: 14132kb

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: 3
Accepted
time: 37ms
memory: 29256kb

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:

IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ
OK
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 5596...

result:

ok

Test #6:

score: 3
Accepted
time: 34ms
memory: 24076kb

input:

vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB
100000 100000
57387 11861 84433 84680 51764 17643 86122 83141 74972 47794 40972 60391 93655 62206 23852 51121 39250 5924 83139 29296 56131 49532 51226 82006 3512 64857 97761 67854 81216 44976 43459 57540 14182 6532 49925 71980 75037 14724 22961 5863 51568 85048 44306...

output:

IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ
OK
1
-1

result:

ok

Test #7:

score: 3
Accepted
time: 32ms
memory: 24768kb

input:

vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB
100000 100000
84974 12498 84270 93621 94069 64811 16796 8508 5403 97838 69731 94154 34731 38790 45254 19912 63443 17097 25188 8738 22665 3307 92076 63795 24089 54926 82925 31639 81818 84608 65732 50776 53506 41939 34765 62498 39249 80937 95327 706 45760 39603 10343 6...

output:

IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ
OK
1
-1

result:

ok

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 15
Accepted
time: 36ms
memory: 25900kb

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:

IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ
OK
60000
187180 47437 150113 199404 61979 49501 167910 175137 104441 155514 170025 181983 117868 13573 149717 166954 145922 29787 93788 58581 158693 51768 120499 17700 4746 119328 138501 137246 33450 135751 84363 168724 157010 108760 44137 113102 139611 199377 86291 ...

result:

ok

Test #9:

score: 15
Accepted
time: 41ms
memory: 25652kb

input:

vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB
90003 90000
14155 14155 151711 151711 31573 66800 139383 1925 46366 116207 18428 18428 66618 83155 133084 9526 176340 87155 193385 52734 133084 1925 79878 137917 176340 32150 15872 66618 116207 194766 40942 31265 147928 124727 97615 58260 161323 8229 74777 146601 959...

output:

IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ
OK
60001
14155 151711 31573 66800 139383 46366 18428 83155 9526 87155 193385 52734 133084 1925 79878 137917 176340 32150 15872 66618 116207 194766 40942 31265 147928 124727 97615 58260 161323 8229 74777 146601 37955 95987 118028 29763 15233 101780 54731 36231 65482 3...

result:

ok

Test #10:

score: 0
Wrong Answer
time: 43ms
memory: 25588kb

input:

vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB
89985 90021
192793 185974 48491 162906 75646 99166 183316 75646 52957 33987 83321 64287 83321 123979 130761 130761 154020 134587 154020 186921 178874 71496 184891 82981 123873 186777 127271 139973 67220 127271 140236 191126 67220 36003 36003 23064 43454 116351 168977...

output:

IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ
OK
60002
192793 185974 48491 162906 99166 183316 75646 52957 33987 64287 83321 123979 130761 134587 154020 186921 178874 71496 184891 82981 123873 186777 139973 127271 140236 191126 67220 36003 23064 43454 116351 168977 63200 132243 153847 21074 108613 25083 115379 5...

result:

wrong answer 3rd lines differ - on the 1st token, expected: '1', found: '60002'

Subtask #3:

score: 0
Runtime Error

Test #71:

score: 0
Runtime Error

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: 14
Accepted
time: 8ms
memory: 16232kb

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
2800
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 268 ...

result:

ok

Test #133:

score: 14
Accepted
time: 6ms
memory: 16440kb

input:

vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB
2999 2999
161 462 13 332 346 475 194 20 36 323 39 256 432 278 259 480 97 464 354 69 375 262 103 321 65 264 31 471 439 314 169 353 165 346 444 148 337 326 359 397 396 489 391 74 168 209 496 183 481 9 485 46 174 410 158 363 179 56 118 294 350 290 154 74 95 202 490 62 3...

output:

IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ
OK
2700
161 462 13 332 346 475 194 20 36 323 39 256 432 278 259 480 97 464 354 69 375 262 103 321 65 264 31 471 439 314 169 353 165 346 444 148 337 326 359 397 396 489 391 74 168 209 496 183 481 9 485 46 174 410 158 363 179 56 118 294 350 290 154 74 95 202 490 62 397...

result:

ok

Test #134:

score: 14
Accepted
time: 3ms
memory: 16660kb

input:

vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB
2999 2999
843 300 400 262 3 359 867 592 609 694 416 694 749 14 997 584 22 452 74 61 908 659 456 301 694 412 793 433 213 885 304 161 506 502 462 654 694 875 983 177 743 313 380 316 473 748 254 659 997 132 100 335 437 825 192 182 213 575 740 442 622 833 694 914 332 341...

output:

IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ
OK
2500
843 300 400 262 3 359 867 592 609 416 749 14 997 584 22 452 74 61 908 659 456 301 412 793 433 213 885 304 161 506 502 462 654 875 983 177 743 313 380 316 473 748 254 659 997 132 100 335 437 825 192 182 213 575 740 442 622 833 914 332 341 153 931 749 819 985 8...

result:

ok

Test #135:

score: 14
Accepted
time: 0ms
memory: 15564kb

input:

vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB
2999 2999
863 1603 1420 106 1789 1690 1900 525 13 1749 747 263 87 0 1117 24 1318 1166 1233 749 337 1130 1780 1156 1918 1245 526 204 507 1440 728 1038 685 83 723 1929 1011 386 1132 1358 1022 1611 861 388 1168 1302 197 1958 1110 1573 1129 1808 357 1656 323 1670 799 983...

output:

IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ
OK
2300
863 1603 1420 106 1789 1690 13 1749 747 0 1117 24 1318 1166 749 337 1130 1780 1156 1918 1245 526 204 507 728 1038 685 83 723 1929 1011 386 1132 1358 1022 1611 388 1168 1302 197 1110 1573 1129 1808 357 1656 323 1670 641 1673 633 188 1557 1747 322 807 544 1118 ...

result:

ok

Test #136:

score: 0
Wrong Answer
time: 3ms
memory: 17960kb

input:

vHwzrZUx9chlYIJ7zODvOcQbZwj3OxhB
2801 2999
242 250 180 109 252 104 276 77 206 10 83 106 187 18 185 122 29 94 87 53 142 172 135 197 70 55 243 242 289 268 125 66 293 276 133 121 299 113 279 71 195 221 23 139 85 246 287 128 198 184 145 140 268 129 210 148 7 222 186 14 282 184 121 42 146 222 239 184 217...

output:

IyRwUZ9rsuq5tjuK54lpSvORqGQyBWEZ
OK
2800
242 250 180 109 252 104 276 77 206 10 83 106 187 18 185 122 29 94 87 53 142 172 135 197 70 55 243 242 289 268 125 66 293 276 133 121 299 113 279 71 195 221 23 139 85 246 287 128 198 184 145 140 268 129 210 148 7 222 186 14 282 184 121 42 146 222 239 184 217 5...

result:

wrong answer 3rd lines differ - on the 1st token, expected: '1', found: '2800'

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

服务器时间: 2025-02-01 19:40:57 | 开源项目