이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int mxn=1e5+5;
int n,k,a[mxn],ans=0,res[mxn],mx,dis[mxn],sz[mxn];
vector<int>v[mxn],state[mxn],par[mxn];
set<int>s;
set<int>tree;
bool mark[mxn];
void dfs(int z){
//cout<<z<<" ";
for(auto i:v[z]){
dfs(i);
sz[z]++;
}
if(!v[z].size())s.insert(z);
}
void solve(int x=1){
if(x==n+1){
ans++;
return;
}
auto y=s.upper_bound(0);
while(y!=s.end()){
int z=*y;
s.erase(z);
for(auto j:par[z]){
sz[j]--;
if(!sz[j])
s.insert(j);
}
solve(x+1);
s.insert(z);
for(auto j:par[z]){
sz[j]++;
if(sz[j])
s.insert(j);
}
if(ans==k){
res[z]=x;
break;
}
y=s.upper_bound(z);
}
}
void make(int x,int y){
//cout<<x<<" "<<y<<'\n';
par[y].push_back(x);
tree.insert(x);
tree.insert(y);
v[x].push_back(y);
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==-1){
state[n+1].push_back(i);
a[i]=n+1;
}
else{
state[a[i]].push_back(i);
mx=max(mx,a[i]);
}
}
//assert(state[n+1].size());
if (!state[n+1].size() || state[n+1].back()!=n){
cout<<-1;
return 0;
}
for(int i=1;i<state[n+1].size();i++){
make(state[n+1][i-1],state[n+1][i]);
}
tree.insert(state[n+1][0]);
while(mx){
if(state[mx].size()==0){
cout<<-1;
return 0;
}
reverse(state[mx].begin(),state[mx].end());
for(auto i:state[mx]){
auto x=tree.lower_bound(i);
if(x!=tree.begin()){
x--;
make(*x,i);
}
x=tree.upper_bound(i);
if(x!=tree.end()){
make(*x,i);
}
}
mx--;
}
dfs(state[n+1][0]);
solve();
if(ans<k){
cout<<-1;
}
else{
for(int i=1;i<=n;i++){
cout<<res[i]<<" ";
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:76:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i=1;i<state[n+1].size();i++){
| ~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |