QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719303#4740. Plan metranathan469011 11ms54068kbC++172.3kb2024-11-07 00:07:502024-11-07 00:07:51

Judging History

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

  • [2024-11-07 00:07:51]
  • 评测
  • 测评结果：11
  • 用时：11ms
  • 内存：54068kb
查看
  • [2024-11-07 00:07:50]
  • 提交

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];
}

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);
    }
    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 cout << "NIE\n", 0;
        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 cout << "NIE\n", 0;
            ans.push_back(Edge(pre, u, d[u] - dst));
            dst = d[u];
            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));
        }
    }
    cout << "TAK\n";
    for(Edge e: ans){
        cout << e.u << ' ' << e.v << ' ' << e.w << '\n';
    }
    return 0;
}
源文件, 语言: C++17

详细

Subtask #1:

score: 11
Accepted

Test #1:

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

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

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: 11ms
memory: 50480kb

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: 9ms
memory: 50544kb

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

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: 0ms
memory: 54068kb

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

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: 0ms
memory: 50548kb

input:

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

output:

TAK
1 6 51
1 8 64
1 2 65
1 7 90
1 5 119
1 3 149
1 4 150
1 9 172
1 10 1

result:

ok good solution

Test #9:

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

input:

2

output:

TAK
1 2 1

result:

ok good solution

Test #10:

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

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: 50536kb

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: 50548kb

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

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

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

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: 50480kb

input:

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

output:

TAK
1 9 70
1 2 78
1 7 110
1 3 128
1 4 140
1 6 140
1 5 162
1 8 191
1 10 1

result:

ok good solution

Test #17:

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

input:

3
1
2

output:

TAK
1 2 1
1 3 1

result:

ok good solution

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #18:

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

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: 0
Wrong Answer
time: 4ms
memory: 50492kb

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:

NIE

result:

wrong answer you didn't find a solution but jury did

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-12-02 11:37:16 | 开源项目