QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#750717	#9733. Heavy-light Decomposition	552Hz^#	WA	6ms	5904kb	C++17	2.3kb	2024-11-15 15:36:49	2024-11-15 15:36:49

Judging History

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

[2024-11-15 15:36:49]
评测

测评结果：WA
用时：6ms
内存：5904kb

查看

[2024-11-15 15:36:49]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<#x<<": "<<x<<endl
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll=long long;
using ull=unsigned long long;
const int N=200010;
ll a[N],n,k;
struct node
{
    int l,r,len;
    bool operator<(const node & a)const{
        return len<a.len;
    }
}que[N];
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        a[i]=0;
    }
    for(int i=1;i<=k;i++){
        cin>>que[i].l>>que[i].r;
        que[i].len=que[i].r-que[i].l+1;
    }
    sort(que+1,que+1+k);
    if(k==1){
        cout<<0<<" ";
        for(int i=1;i<n;i++){
            cout<<i<<" ";
        }
        cout<<endl;
        return;
    }
    if(que[k].len==que[k-1].len&&((k==2||que[1].len==que[k].len)||que[k].len==2)){
        cout<<"IMPOSSIBLE"<<endl;
        return;
    }
    reverse(que+1,que+1+k);
    
    if(que[1].len!=que[2].len){
        for(int i=1;i<=k;i++){
            if(i==1){
                for(int j=que[i].l+1;j<=que[i].r;j++){
                    a[j]=j-1;
                }
            }else{
                a[que[i].l]=que[1].l;
                for(int j=que[i].l+1;j<=que[i].r;j++){
                    a[j]=j-1;
                }
            }
        }
    }else{
        for(int i=1;i<=k;i++){
            if(i==1){
                for(int j=que[i].l+1;j<=que[i].r;j++){
                    a[j]=j-1;
                }
            }else{
                if(que[i].len==que[1].len){
                    a[que[i].l]=que[1].l;
                    for(int j=que[i].l+1;j<=que[i].r;j++){
                        a[j]=j-1;
                    }
                }else{
                    a[que[i].l]=que[1].l+1;
                    for(int j=que[i].l+1;j<=que[i].r;j++){
                        a[j]=j-1;
                    }
                               
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}
/*
贡献法
正难则反
数小状压
关系连边
拆位
广义单调性
最长转最短
*/

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 5688kb

input:

output:

0 1 2 3 4 1 1 7 1 9 10 1 
2 0 2 2 
IMPOSSIBLE

result:

ok Correct. (3 test cases)

Test #2:

score: -100

Wrong Answer

time: 6ms

memory: 5904kb

input:

10
1 1
1 1
100000 1
1 100000
12 4
1 3
4 6
7 9
10 12
6 3
4 6
2 3
1 1
8999 3
1 3000
3001 6000
6001 8999
14 4
1 3
4 6
7 10
11 14
17 5
1 3
4 6
7 10
11 14
15 17
19999 2
1 9999
10000 19999
1 1
1 1
5 3
1 1
2 3
4 5

output:

0 
0 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...

result:

wrong answer 3003 should be a heavy child, but the maximum one with size 2999 and 2998 found. (test case 5)