QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719357#4740. Plan metranathan469011 10ms54632kbC++173.0kb2024-11-07 00:24:262024-11-07 00:24:26

Judging History

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

  • [2024-11-07 00:24:26]
  • 评测
  • 测评结果：11
  • 用时：10ms
  • 内存：54632kb
查看
  • [2024-11-07 00:24:26]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn = 1e6+5, inf=1e18;

struct Edge{
    int u, v, w;
    Edge(){};
    Edge(int u, int v, int w): u(u), v(v), w(w){};
};

int n,d[maxn], l[maxn];
vector<int> mp[2*maxn], allv;
vector<Edge> ans;

bool cmp(int x, int y){
    return d[x] < d[y];
}

bool solve(int duv){
    for(int item: allv){
        mp[item + maxn].clear();
    }
    allv.clear();
    ans.clear();
    for(int i=2;i<n;i++){
        int diff = d[i] - l[i];
        if(mp[diff + maxn].empty()) allv.push_back(diff);
        mp[diff + maxn].push_back(i);
    }
//    int duv = 1e9;
//    for(int i=2;i<n;i++) duv = min(duv, d[i] + l[i]);
//    if(abs(*allv.begin()) == abs(*allv.rbegin()) && allv.size() <= 2) duv = abs(*allv.begin());
    if(mp[duv+maxn].empty()) allv.push_back(duv);
    if(mp[-duv+maxn].empty()) allv.push_back(-duv);
    mp[-duv+maxn].push_back(1); l[1] = duv;
    mp[duv+maxn].push_back(n); d[n] = duv;
    int rem2 = allv[0] & 1;
    for(int item: allv) {
        if((item & 1) != rem2) return false;
        sort(mp[item + maxn].begin(), mp[item + maxn].end(), cmp);
    }
    sort(allv.begin(), allv.end());
    int pre = 1, dst = 0;
    for(int item: allv){
        int u = mp[item + maxn][0];
//        cout << item << ' ' << u << ' ' << d[u] << ' ' << dst << endl;
//        for(Edge e: ans){
//            cout << e.u << ' ' << e.v << ' ' << e.w << '\n';
//        }
        if(u > 1){
            if(dst >= d[u]) return false;
            ans.push_back(Edge(pre, u, d[u] - dst));
            dst = d[u];
            if(duv - dst != l[u]) return false;
            pre = u;
        }
        // int dst2 = dst;
        for(int i=1;i<mp[item+maxn].size();i++){
            int v = mp[item+maxn][i];
            ans.push_back(Edge(u, v, d[v] - dst));
            if(duv - dst + (d[v] - dst) != l[v]) return false;
        }
    }
    cout << "TAK\n";
    for(Edge e: ans){
        cout << e.u << ' ' << e.v << ' ' << e.w << '\n';
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n;
    if(n == 2){
        cout << "TAK\n1 2 1\n";
        return 0;
    }
    for(int i=2;i<n;i++) cin >> d[i];
    for(int i=2;i<n;i++) cin >> l[i];
    for(int i=2;i<n;i++){
        int diff = d[i] - l[i];
        if(mp[diff + maxn].empty()) allv.push_back(diff);
        mp[diff + maxn].push_back(i);
    }
    sort(allv.begin(), allv.end());
    int duv = 1e9, duv2 = 1;
    for(int i=2;i<n;i++) duv = min(duv, d[i] + l[i]);
    duv2 = abs(*allv.begin());
    if(solve(duv)) return 0;
    if(solve(duv2)) return 0;
    cout << "NIE\n";
    return 0;
}
源文件, 语言: C++17

详细

Subtask #1:

score: 11
Accepted

Test #1:

score: 11
Accepted
time: 0ms
memory: 52768kb

input:

7
6 6 2 2 1
5 3 5 1 4

output:

TAK
1 6 1
1 4 2
1 5 2
5 2 4
5 7 1
7 3 3

result:

ok good solution

Test #2:

score: 11
Accepted
time: 0ms
memory: 54372kb

input:

10
31 89 20 19 19 20 19 164
70 88 20 20 20 19 20 125

output:

NIE

result:

ok no solution

Test #3:

score: 11
Accepted
time: 3ms
memory: 52664kb

input:

10
57 106 79 12 139 103 103 85
110 53 28 65 98 86 50 117

output:

NIE

result:

ok no solution

Test #4:

score: 11
Accepted
time: 8ms
memory: 53888kb

input:

10
13 62 24 125 13 15 54 94
1 76 14 113 1 1 68 82

output:

NIE

result:

ok no solution

Test #5:

score: 11
Accepted
time: 3ms
memory: 52856kb

input:

10
123 146 139 5 192 80 77 118
97 172 165 31 166 106 51 92

output:

TAK
1 5 5
1 7 80
1 4 139
1 3 146
1 10 26
10 8 51
10 9 92
10 2 97
10 6 166

result:

ok good solution

Test #6:

score: 11
Accepted
time: 10ms
memory: 54060kb

input:

10
112 67 152 16 6 28 1 8
111 82 137 31 21 41 14 7

output:

TAK
1 6 6
1 5 16
1 3 67
1 8 1
8 7 27
8 9 7
9 2 104
9 10 7
10 4 137

result:

ok good solution

Test #7:

score: 11
Accepted
time: 5ms
memory: 53916kb

input:

10
83 108 180 120 114 50 79 132
15 176 112 188 182 118 11 64

output:

TAK
1 7 50
1 3 108
1 6 114
1 5 120
1 10 68
10 8 11
10 2 15
10 9 64
10 4 112

result:

ok good solution

Test #8:

score: 11
Accepted
time: 7ms
memory: 52692kb

input:

10
65 149 150 119 51 90 64 172
66 150 151 120 52 91 65 173

output:

TAK
1 6 51
6 8 13
6 2 14
6 7 39
6 5 68
6 3 98
6 4 99
6 9 121
6 10 52

result:

ok good solution

Test #9:

score: 11
Accepted
time: 8ms
memory: 51908kb

input:

2

output:

TAK
1 2 1

result:

ok good solution

Test #10:

score: 11
Accepted
time: 0ms
memory: 53108kb

input:

10
46 145 46 19 165 20 145 99
47 146 47 112 76 112 146 6

output:

NIE

result:

ok no solution

Test #11:

score: 11
Accepted
time: 4ms
memory: 52660kb

input:

10
4 3 4 150 114 86 99 86
2 3 2 155 118 80 105 80

output:

NIE

result:

ok no solution

Test #12:

score: 11
Accepted
time: 3ms
memory: 54524kb

input:

10
6 7 12 168 171 12 7 7
6 5 14 180 159 14 6 5

output:

NIE

result:

ok no solution

Test #13:

score: 11
Accepted
time: 3ms
memory: 54036kb

input:

10
13 170 28 134 10 117 117 90
98 85 113 49 95 32 32 5

output:

TAK
1 6 10
1 2 13
1 4 28
1 10 85
10 9 5
10 7 32
10 8 32
10 5 49
10 3 85

result:

ok good solution

Test #14:

score: 11
Accepted
time: 0ms
memory: 53300kb

input:

10
90 2 53 53 158 58 1 114
89 1 54 54 161 59 2 111

output:

TAK
1 6 158
1 8 1
8 4 52
8 5 52
8 7 57
8 3 1
3 2 88
3 10 1
10 9 111

result:

ok good solution

Test #15:

score: 11
Accepted
time: 0ms
memory: 53120kb

input:

10
47 2 198 181 29 192 192 2
187 142 58 41 169 52 52 142

output:

TAK
1 3 2
1 9 2
1 6 29
1 2 47
1 10 140
10 5 41
10 7 52
10 8 52
10 4 58

result:

ok good solution

Test #16:

score: 11
Accepted
time: 3ms
memory: 53740kb

input:

10
78 128 140 162 140 110 191 70
79 129 141 163 141 111 192 71

output:

TAK
1 9 70
9 2 8
9 7 40
9 3 58
9 4 70
9 6 70
9 5 92
9 8 121
9 10 71

result:

ok good solution

Test #17:

score: 11
Accepted
time: 6ms
memory: 53428kb

input:

3
1
2

output:

TAK
1 2 1
2 3 2

result:

ok good solution

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #18:

score: 22
Accepted
time: 3ms
memory: 53072kb

input:

1000
998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 970 969 968 967 966 965 964 963 962 961 960 959 958 957 956 955 954 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 933 932 931 930 929 928 927 926 925...

output:

TAK
1 999 1
999 998 1
998 997 1
997 996 1
996 995 1
995 994 1
994 993 1
993 992 1
992 991 1
991 990 1
990 989 1
989 988 1
988 987 1
987 986 1
986 985 1
985 984 1
984 983 1
983 982 1
982 981 1
981 980 1
980 979 1
979 978 1
978 977 1
977 976 1
976 975 1
975 974 1
974 973 1
973 972 1
972 971 1
971 970 ...

result:

ok good solution

Test #19:

score: 22
Accepted
time: 0ms
memory: 53304kb

input:

1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

TAK
1 2 1
2 3 1
2 4 2
2 5 3
2 6 4
2 7 5
2 8 6
2 9 7
2 10 8
2 11 9
2 12 10
2 13 11
2 14 12
2 15 13
2 16 14
2 17 15
2 18 16
2 19 17
2 20 18
2 21 19
2 22 20
2 23 21
2 24 22
2 25 23
2 26 24
2 27 25
2 28 26
2 29 27
2 30 28
2 31 29
2 32 30
2 33 31
2 34 32
2 35 33
2 36 34
2 37 35
2 38 36
2 39 37
2 40 38
2 ...

result:

ok good solution

Test #20:

score: 22
Accepted
time: 6ms
memory: 53556kb

input:

3000
3246 3738 4685 1539 2140 2026 4814 4815 2059 2686 4692 4403 2701 1596 4878 2470 3194 2272 2171 4120 2654 3349 1842 2046 4360 4529 4792 3250 1741 4766 4337 1559 1601 2362 2295 4463 4987 4119 3847 2272 1522 2882 4556 2484 2864 3002 1446 1772 3089 3092 2562 1461 3630 1879 1899 4881 2334 3189 1794 ...

output:

NIE

result:

ok no solution

Test #21:

score: 22
Accepted
time: 4ms
memory: 53952kb

input:

3000
4130 2457 3399 3125 2758 4911 615 1200 3017 4249 4344 2200 4005 876 4946 976 3067 2029 2158 2667 4183 1380 40 919 3377 2618 3007 1818 1033 227 4422 2971 3208 893 3079 1691 663 4139 2833 1218 4741 2450 789 4493 971 3215 4274 3039 2060 3742 2302 1506 4156 607 773 3151 2661 3913 4082 2956 4454 192...

output:

NIE

result:

ok no solution

Test #22:

score: 22
Accepted
time: 3ms
memory: 54384kb

input:

3000
954 3442 341 795 3138 3391 4895 1174 3801 2933 3695 3388 1743 2942 1572 1029 2173 1438 2270 724 4007 896 2465 4667 3054 249 246 4977 3675 2669 3911 339 2771 984 3399 1237 349 3190 1834 3114 4549 3675 4487 1586 881 2723 677 1290 2979 2710 4746 2994 2524 682 3646 2776 317 4457 2636 2524 3278 465 ...

output:

NIE

result:

ok no solution

Test #23:

score: 22
Accepted
time: 8ms
memory: 53036kb

input:

3000
1236 2492 766 600 2029 4796 1025 4509 3655 4410 1132 3591 2190 3687 3393 1965 4342 3081 4140 2178 476 425 3368 2239 3481 245 548 4122 2637 4282 2385 606 2502 1565 1925 1754 2384 4313 3465 1490 2259 4430 1678 1632 1938 2513 3731 1713 3283 3289 3403 1979 1846 668 2635 3797 4226 4092 614 2677 1977...

output:

TAK
1 1265 2
1 200 3
1 1737 4
1 2550 5
1 834 6
1 299 7
1 1328 8
1 1856 10
1 1747 15
1 2087 16
1 2862 17
1 1309 18
1 2362 19
1 1624 26
1 2307 27
1 1324 29
1 1190 30
1 2645 32
1 626 36
1 2007 39
1 994 42
1 612 46
1 580 48
1 1401 49
1 2418 50
1 2864 51
1 2723 52
1 2573 59
1 2966 60
1 526 64
1 2988 65
1...

result:

ok good solution

Test #24:

score: 22
Accepted
time: 0ms
memory: 54632kb

input:

3000
2567 1720 478 391 3422 4790 4949 2339 4239 919 1382 3856 4907 3545 4073 2037 3854 4075 2618 1578 2198 1964 2263 3825 2860 3242 2777 3795 2069 1280 1188 645 2323 4900 4781 4018 4425 4246 4049 2145 2096 1017 3644 3069 3423 3773 3587 4999 4324 1368 677 803 2346 4166 2428 4842 3374 2423 4618 2514 3...

output:

TAK
1 2559 5
1 2742 37
1 2133 97
1 1717 260
1 143 263
1 939 363
1 2756 381
1 2417 390
1 873 414
1 1728 532
1 1993 622
1 1801 669
1 1279 689
1 1905 751
1 457 766
1 53 803
1 168 837
1 2190 842
1 1235 881
1 1844 887
1 2476 972
1 1746 975
1 1433 999
1 819 1008
1 2615 1023
1 1794 1058
1 2317 1132
1 571 1...

result:

ok good solution

Test #25:

score: 22
Accepted
time: 4ms
memory: 53628kb

input:

3000
4989 4334 179 1994 2064 2545 1064 4694 1823 4758 688 3273 875 708 2573 451 2326 4205 4815 1534 3459 2928 3565 3638 1987 4345 1414 4035 2531 1228 1589 3596 4318 3415 4512 2953 2003 2151 1650 4365 1935 4182 1154 1660 1760 1644 2423 1301 3310 2072 3024 1718 4061 1106 2165 4436 2082 1667 3732 260 3...

output:

TAK
1 304 1
304 959 1
304 2292 6
304 2603 14
304 1611 15
304 936 16
304 2710 18
304 2092 19
304 650 20
304 2459 23
304 1790 25
304 1446 26
304 1154 34
304 1407 42
304 1854 50
304 2769 52
304 2471 53
304 2959 73
304 2432 79
304 2500 83
304 2287 86
304 838 87
304 699 89
304 740 95
304 1467 96
304 906 ...

result:

ok good solution

Test #26:

score: 22
Accepted
time: 3ms
memory: 54480kb

input:

3000
1352 2311 3356 3752 3704 2206 3802 2718 1693 3838 2439 1539 2157 2532 3342 2895 2380 1628 3603 3822 1283 4277 3128 4180 2361 3794 3853 4837 3991 4926 2307 4054 3399 3864 1265 2472 4890 1604 1800 4204 4133 4192 4630 3934 4785 3913 1573 4835 2828 3636 2702 2551 4335 2662 4159 2147 3808 3148 3371 ...

output:

TAK
1 2681 1260
2681 1296 9
2681 264 10
2681 1165 13
2681 686 37
2681 1349 46
2681 1744 57
2681 552 60
2681 2011 70
2681 1618 89
2681 2783 103
2681 748 107
2681 101 135
2681 254 167
2681 1917 168
2681 2616 194
2681 1872 204
2681 2116 215
2681 2818 218
2681 564 220
2681 1376 224
2681 2781 229
2681 22...

result:

ok good solution

Test #27:

score: 22
Accepted
time: 6ms
memory: 52944kb

input:

3000
3097 3903 4418 1796 1042 4657 1430 2005 2767 3209 4552 1943 4809 4841 1355 4449 1330 1489 4339 886 749 4199 4558 4731 4947 601 3155 2695 3142 962 3101 2429 737 1891 3333 4856 3247 2016 2097 2504 4465 4420 2036 3511 1433 3773 1896 4490 2307 1489 2123 4623 2931 840 2268 3805 1984 2726 1790 1120 4...

output:

NIE

result:

ok no solution

Test #28:

score: 22
Accepted
time: 3ms
memory: 53392kb

input:

3000
886 2441 1532 1519 993 2071 1533 706 3290 3577 2399 3107 1818 2494 4684 3579 1157 3779 2708 1157 2737 1792 967 3015 2289 2691 4486 2122 2800 2027 3277 4540 3785 1152 4885 2099 1008 2799 3230 1610 3568 4055 2860 1931 1482 4322 3415 3720 3930 3986 2518 1314 1596 1392 469 3657 1438 4159 2898 2654 ...

output:

NIE

result:

ok no solution

Test #29:

score: 0
Wrong Answer
time: 0ms
memory: 52916kb

input:

3000
2696 919 556 3002 1270 4174 2500 353 1352 3944 635 3440 4641 1575 4667 3561 3900 3147 1359 3273 938 829 900 2902 83 1087 302 1109 1910 4061 966 2803 4023 3639 2809 1303 1344 3385 2796 1538 1498 4548 1707 1888 3827 69 2512 557 610 3502 3360 1799 4427 669 3527 2313 4578 4303 2867 1200 1568 488 28...

output:

TAK
1 1591 49
1 333 111
1 1723 126
1 138 156
1 594 206
1 1263 234
1 2695 240
1 2909 256
1 1823 260
1 1589 344
1 2553 378
1 1470 381
1 1665 384
1 2395 392
1 2246 395
1 340 402
1 1999 427
1 250 444
1 2217 447
1 2571 466
1 2887 565
1 2129 580
1 1439 594
1 993 606
1 1845 630
1 2655 655
1 2483 690
1 2638...

result:

wrong answer wrong solution (expected no solution)

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

服务器时间: 2024-11-30 08:45:08 | 开源项目