CQUPT OJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#23873 #2043. 线段树 Accepted 100 371 ms 2548 K C++ 17 (Clang) / 1.5 K 192022211822 2024-12-18 15:14:22
显示原始代码 
#include <bits/stdc++.h>
// #include<iostream>
// #include<iomanip>
// #include<vector>
// #include<queue>
// #include<string>
// #include<map>
// #include <algorithm>
// #include<cmath>
// #include<unordered_map>
#define int long long

#define rep(i, l, r) for (int i = l; i <= r; i++)

using namespace std;
#define pii pair<int, int>

#define endl '\n'

const int M = 1e6 + 7;
const int N = 1e3 + 7;

int n, node;
vector<int> num;
unordered_map<int, int> m;
unordered_map<int, int> deep;
unordered_map<int, pii> lrtree;
int tree[M];

void dfs(int cur, int val, int p) {
    tree[p] = val;
    if (!cur)
        return;

    dfs(cur - 1, lrtree[val].first, p * 2);
    dfs(cur - 1, lrtree[val].second, p * 2 + 1);
}

signed main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> node;

    rep(i, 0, n - 1) {
        int a;
        cin >> a;
        num.push_back(a);
        m[a] = 1;
    }
    int d = log2(node + 1);
    sort(num.begin(), num.end());
    rep(i, 0, n - 1) { deep[num[i]] = 1; }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int other = num[i] - num[j];
            if (m.find(other) == m.end())
                continue;
            int mi = min(deep[num[j]], deep[other]) + 1;
            if (deep[num[i]] < mi) {
                deep[num[i]] = mi;
                lrtree[num[i]] = { num[j], other };
            }
        }
    }

    int val = -1;
    for (auto [x, y] : deep) {
        if (y >= d) {
            val = x;
            break;
        }
    }
    if (val == -1) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        dfs(d - 1, val, 1);
        rep(i, 1, node) cout << tree[i] << ' ';
    }
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：4 ms
内存：328 KiB

输入文件（0.in） 

3 3
1 2 4

答案文件（0.out） 

Yes

用户输出 

Yes
4 2 2

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
8 3 5 1 2 2 3

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：4 ms
内存：324 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
用时：54 ms
内存：2496 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
576460752303423488 288230376151711744 288230376151711744 144115188075855872 144115188075855872 144115188075855872 1441151880
<3744697 bytes omitted>

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：54 ms
内存：2500 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
576460752303423488 288230376151711744 288230376151711744 144115188075855872 144115188075855872 144115188075855872 1441151880
<3744697 bytes omitted>

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：54 ms
内存：2468 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
576460752303423488 288230376151711744 288230376151711744 144115188075855872 144115188075855872 144115188075855872 1441151880
<3744697 bytes omitted>

Special Judge 信息 

AC!

系统信息 

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

输入文件（6.in） 

2 1
114514 1919810

答案文件（6.out） 

YES
114514

用户输出 

Yes
1919810

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：20 ms
内存：548 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
用时：21 ms
内存：456 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
内存：412 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
用时：24 ms
内存：520 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
内存：320 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
用时：25 ms
内存：564 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
用时：24 ms
内存：572 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
用时：45 ms
内存：2548 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
用时：26 ms
内存：2416 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
5767168 2883584 2883584 1441792 1441792 1441792 1441792 720896 720896 720896 720896 720896 720896 720896 720896 360448 36044
<861124 bytes omitted>

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
CQUPT OJ Powered by SYZOJ.