CQUPT OJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#20224 #2043. 线段树 Accepted 100 1225 ms 2576 K C++ 17 / 2.5 K admin 2024-12-10 22:31:42
显示原始代码 
#ifdef ONLINE_JUDGE
#pragma GCC optimize(2, "Ofast", "inline")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define rt return

#define pi pair<int, int>

#define pl pair<ll, ll>

#define pu pair<ull, ull>

#define int long long

#define ll long long

#define ull unsigned long long

#define endl '\n'

#define Endl endl

#define all(x) x.begin(), x.end()

#define all1(x) next(x.begin()), x.end()

#define lll __int128_t

#define ulll __uint128_t

using namespace std;
const int64_t maxn = 1e5 + 50;
const int64_t mod = 998244353;
const int64_t maxl = (int64_t)(2e18) + 5;
const int64_t maxi = 1e9 + 7;
void init() {}
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    vector<pi> fa(n + 1);
    vector<int> depp(n + 1);
    vector<int> sgt(m + 1);
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]] = i;
    }
    m++;
    int dep = 0;
    int xx = m;
    while (xx) {
        xx >>= 1;
        dep++;
    }
    dep--;
    m--;
    for (int i = 0; i < dep; i++) {
        for (int j = 1; j <= n; j++) {
            if (depp[j] < i)
                continue;
            for (int k = j; k <= n; k++) {
                if (depp[k] < i)
                    continue;
                if (mp.find(a[j] + a[k]) == mp.end())
                    continue;
                int tp = mp[a[j] + a[k]];
                depp[tp] = i + 1;
                fa[tp].first = j;
                fa[tp].second = k;
            }
        }
    }
    int maxx = 0;
    if (*max_element(all1(depp)) < dep - 1) {
        cout << "NO" << endl;
        rt;
    } else {
        cout << "YES" << endl;
        maxx = max_element(all1(depp)) - depp.begin();
    }
    auto dfs = [&](auto &&self, int idx, int idx2) -> void {
        sgt[idx] = a[idx2];
        if (idx * 2 <= m) {
            self(self, idx * 2, fa[idx2].first);
            self(self, idx * 2 + 1, fa[idx2].second);
        }
    };
    dfs(dfs, 1, maxx);
    for (int i = 1; i <= m; i++) {
        cout << sgt[i] << " \n"[i == m];
    }
}
signed main() {
#ifndef ONLINE_JUDGE
    freopen("1.txt", "r", stdin);
    freopen("2.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int __ = 1;
    // std::cin >> __;
    init();
    while (__--) {
        solve();
        // cerr<<"TIME"<<qq-__<<endl;
    }
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：4 ms
内存：320 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
内存：328 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 3 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
用时：51 ms
内存：2568 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
1152921504606846976 576460752303423488 576460752303423488 288230376151711744 288230376151711744 288230376151711744 288230376
<3819522 bytes omitted>

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：52 ms
内存：2548 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
1152921504606846976 576460752303423488 576460752303423488 288230376151711744 288230376151711744 288230376151711744 288230376
<3819522 bytes omitted>

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：49 ms
内存：2544 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
288230376151711744 144115188075855872 144115188075855872 72057594037927936 72057594037927936 72057594037927936 7205759403792
<3707285 bytes omitted>

Special Judge 信息 

AC!

系统信息 

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

输入文件（6.in） 

2 1
114514 1919810

答案文件（6.out） 

YES
114514

用户输出 

YES
114514

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：280 ms
内存：2460 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
用时：270 ms
内存：2500 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
内存：328 KiB

输入文件（9.in） 

4 7
3 5 1 2

答案文件（9.out） 

YES
5 3 2 1 2 1 1

用户输出 

YES
5 3 2 1 2 1 1

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：23 ms
内存：2476 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
用时：3 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 3000000000000000 2000000000000000 1000000000000000 2000000000000000 1000000000000000 1000000000000000

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：193 ms
内存：2576 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
用时：218 ms
内存：2572 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
用时：43 ms
内存：2564 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
7340032 3670016 3670016 1835008 1835008 1835008 1835008 917504 917504 917504 917504 917504 917504 917504 917504 458752 45875
<926724 bytes omitted>

Special Judge 信息 

AC!

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：23 ms
内存：2456 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.