QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#719319#4740. Plan metranathan46900 12ms54376kbC++172.9kb2024-11-07 00:14:342024-11-07 00:14:37

Judging History

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

  • [2024-11-07 00:14:37]
  • 评测
  • 测评结果:0
  • 用时:12ms
  • 内存:54376kb
  • [2024-11-07 00:14:34]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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

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

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

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

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

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

input:

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

output:

TAK
1 7 50
7 3 58
7 6 64
7 5 70
7 8 29
8 2 4
8 9 53
8 4 101
8 10 11

result:

wrong answer incorrect solution

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%