QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#739136 | #9733. Heavy-light Decomposition | Aicu123 | WA | 0ms | 3876kb | C++20 | 1.3kb | 2024-11-12 20:58:47 | 2024-11-12 20:58:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define fi first
#define se second
//cout<<setiosflags(ios::fixed)<<setprecision(K);
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
const double eps=1e-9;
const double PI=acos(-1.0);
const int inf=1e9+7;
const int mod=998244353;
const int N=2e5+10,M=N<<1;
void solve(){
int n,m;
cin>>n>>m;
vector<pii>a(m);
for(int i=0;i<m;i++){
int l,r;
cin>>l>>r;
a[i]={r-l+1,l};
}
sort(a.begin(),a.end(),greater<pii>());
if(m==1){
for(int i=0;i<n;i++){
cout<<i<<' ';
}
cout<<'\n';
return;
}
if(a[0].fi<2){
cout<<"IMPOSSIBLE\n";
return;
}
vector<int>p(n+1);
auto [sz,L]=a[0];
int R=L+sz-1;
p[L]=0;
for(int i=L+1;i<=R;i++){
p[i]=i-1;
}
int rt=L;
for(int i=1;i<m;i++){
auto [sz,l]=a[i];
int r=l+sz-1;
for(int i=l+1;i<=r;i++){
p[i]=i-1;
}
p[l]=rt;
}
for(int i=1;i<=n;i++){
cout<<p[i]<<' ';
}
cout<<'\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;
cin>>T;
while(T--){
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
input:
3 12 5 1 5 9 11 7 8 6 6 12 12 4 3 1 1 4 4 2 3 2 2 1 1 2 2
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: 0ms
memory: 3876kb
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 11 should be a heavy child, but the maximum one with size 3 and 2 found. (test case 3)