CQUPT OJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#21805 #2043. 线段树 Accepted 100 198 ms 1480 K C++ 17 / 1.3 K 192022211836 2024-12-14 20:29:13
显示原始代码 
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <string>
#include <queue>
using namespace std;
const int N = 1010;
const int M = 1e6 + 10;
int n, m;
int ans[M];
struct node {
    long long zh;
    int lson, rson, floor;
} a[N];
bool cmp(node x, node y) { return x.zh < y.zh; }
void pr(int x) {
    a[x].floor = 1;
    int l = 1, r = x - 1;
    while (l <= r) {
        if (a[l].zh + a[r].zh < a[x].zh)
            l++;
        else if (a[l].zh + a[r].zh > a[x].zh)
            r--;
        else {
            if (a[x].floor < min(a[l].floor, a[r].floor) + 1) {
                a[x].floor = min(a[l].floor, a[r].floor) + 1;
                a[x].lson = l;
                a[x].rson = r;
            }
            l++;
            r--;
        }
    }
}
void print(int x) {
    ans[1] = x;
    for (int i = 1; i <= n / 2; i++) {
        ans[i * 2] = a[ans[i]].lson;
        ans[i * 2 + 1] = a[ans[i]].rson;
    }
    for (int i = 1; i <= n; i++) cout << a[ans[i]].zh << " ";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) cin >> a[i].zh;
    sort(a + 1, a + m + 1, cmp);
    for (int i = 1; i <= m; i++) pr(i);
    int n0 = 1, nx = n;
    while (nx != 1) {
        n0++;
        nx = nx / 2;
    }
    for (int i = 1; i <= m; i++) {
        if (a[i].floor == n0) {
            cout << "Yes\n";
            print(i);
            return 0;
        }
    }
    cout << "No";
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：4 ms
内存：324 KiB

输入文件（0.in） 

3 3
1 2 4

答案文件（0.out） 

Yes

用户输出 

Yes
2 1 1

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：4 ms
内存：412 KiB

输入文件（1.in） 

5 7
8 3 5 1 2

答案文件（1.out） 

YES
8 3 5 1 2 3 2

用户输出 

Yes
5 2 3 1 1 1 2

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：4 ms
内存：412 KiB

输入文件（2.in） 

5 7
114 514 1919 810 1

答案文件（2.out） 

NO

用户输出 

No

Special Judge 信息 

AC

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：32 ms
内存：1404 KiB

输入文件（3.in） 

1000 262143
196459294168122057 634354265635305343 769826666322937037 727838616694226973 13432407572
<18754 bytes omitted>

答案文件（3.out） 

YES
1152921504606846976 576460752303423488 576460752303423488 288230376151711744 288230376151711744
<3819552 bytes omitted>

用户输出 

Yes
144115188075855872 72057594037927936 72057594037927936 36028797018963968 36028797018963968 36028797018963968 360287970189639
<3688579 bytes omitted>

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：32 ms
内存：1404 KiB

输入文件（4.in） 

1000 262143
196459294168122057 634354265635305343 769826666322937037 727838616694226973 13432407572
<18754 bytes omitted>

答案文件（4.out） 

YES
1152921504606846976 576460752303423488 576460752303423488 288230376151711744 288230376151711744
<3819552 bytes omitted>

用户输出 

Yes
144115188075855872 72057594037927936 72057594037927936 36028797018963968 36028797018963968 36028797018963968 360287970189639
<3688579 bytes omitted>

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：32 ms
内存：1480 KiB

输入文件（5.in） 

1000 262143
903180121091114613 611535431953358118 77828605464411109 545275249615134953 879799372887
<18765 bytes omitted>

答案文件（5.out） 

YES
288230376151711744 144115188075855872 144115188075855872 72057594037927936 72057594037927936 72
<3707315 bytes omitted>

用户输出 

Yes
144115188075855872 72057594037927936 72057594037927936 36028797018963968 36028797018963968 36028797018963968 360287970189639
<3688579 bytes omitted>

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：4 ms
内存：320 KiB

输入文件（6.in） 

2 1
114514 1919810

答案文件（6.out） 

YES
114514

用户输出 

Yes
114514

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：5 ms
内存：456 KiB

输入文件（7.in） 

1000 262143
263 120 395 789 44 641 819 1894 6987 36 460 1065 112 216 151 8940694 4990 832 308 375 1
<4677 bytes omitted>

答案文件（7.out） 

NO

用户输出 

No

Special Judge 信息 

AC

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：5 ms
内存：452 KiB

输入文件（8.in） 

1000 262143
2238 1591 113 2438 325528815460 171 573 218 1387 742 1295 2527 2613 43 6213263926707787
<4617 bytes omitted>

答案文件（8.out） 

NO

用户输出 

No

Special Judge 信息 

AC

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：4 ms
内存：320 KiB

输入文件（9.in） 

4 7
3 5 1 2

答案文件（9.out） 

YES
5 3 2 1 2 1 1

用户输出 

Yes
5 2 3 1 1 1 2

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：7 ms
内存：368 KiB

输入文件（10.in） 

1000 262143
224485016991701037 288836471541711053 342664574046288584 370246615337682648 65992527767
<18804 bytes omitted>

答案文件（10.out） 

NO

用户输出 

No

Special Judge 信息 

AC

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：4 ms
内存：412 KiB

输入文件（11.in） 

4 7
3000000000000000 5000000000000000 1000000000000000 2000000000000000

答案文件（11.out） 

YES
5000000000000000 3000000000000000 2000000000000000 1000000000000000 2000000000000000 1000000000
<25 bytes omitted>

用户输出 

Yes
5000000000000000 2000000000000000 3000000000000000 1000000000000000 1000000000000000 1000000000000000 2000000000000000

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：7 ms
内存：460 KiB

输入文件（12.in） 

1000 262143
493 973 44 921 1534 1904 1425 1655 260 1564 1420 1155 1971 1079 731 1690 996 1512 1679 
<4371 bytes omitted>

答案文件（12.out） 

NO

用户输出 

No

Special Judge 信息 

AC

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：7 ms
内存：368 KiB

输入文件（13.in） 

1000 262143
599 1305 813 662 1286 205 1831 1229 1160 1276 814 947 1150 1023 1888 1399 1469 20 1593 
<4342 bytes omitted>

答案文件（13.out） 

NO

用户输出 

No

Special Judge 信息 

AC

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：25 ms
内存：1416 KiB

输入文件（14.in） 

1000 262143
187372299518279260 43602130474742763 44819282172062712 812635660484197841 2263756353061
<18513 bytes omitted>

答案文件（14.out） 

YES
7340032 3670016 3670016 1835008 1835008 1835008 1835008 917504 917504 917504 917504 917504 9175
<926754 bytes omitted>

用户输出 

Yes
917504 458752 458752 229376 229376 229376 229376 114688 114688 114688 114688 114688 114688 114688 114688 57344 57344 57344 5
<672781 bytes omitted>

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：22 ms
内存：1440 KiB

输入文件（15.in） 

20 262143
176 11 720896 1441792 2816 5632 22 360448 5767168 704 90112 2883584 352 1408 22528 45056 
<20 bytes omitted>

答案文件（15.out） 

YES
5767168 2883584 2883584 1441792 1441792 1441792 1441792 720896 720896 720896 720896 720896 7208
<861154 bytes omitted>

用户输出 

Yes
1441792 720896 720896 360448 360448 360448 360448 180224 180224 180224 180224 180224 180224 180224 180224 90112 90112 90112 
<805006 bytes omitted>

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
CQUPT OJ Powered by SYZOJ.