题目:ARC200C
构造每个人的座位时为什么倒着安排可以正着就不行?求 hack。
当然也可能是我代码写挂了,在此附上:
//WA
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<random>
#include<unordered_map>
#include<complex>
using namespace std;
namespace code{
using ll=long long;
using ull=unsigned long long;
using uint=unsigned int;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F(i,x,y) for(int i=(x),__tt2__=(y);i<=__tt2__;i++)
#define R(i,x,y) for(int i=(x),__tt2__=(y);i>=__tt2__;i--)
#define _F(i,x,y) for(int i=(x),__tt2__=(y);i<__tt2__;i++)
#define _R(i,x,y) for(int i=(x),__tt2__=(y);i>__tt2__;i--)
#define debug(x) cerr<<#x<<'='<<(x)<<endl
#define lbt(x) (x&(~x+1))
#define e1 first
#define e2 second
constexpr int N=505;
int ind[N],l[N],r[N],ans[N];
vector<int>way[N];
signed main(){
cin.tie(0)->sync_with_stdio(0);
int T;
cin>>T;
while(T--){
int n;
cin>>n;
F(i,1,n)ind[i]=0,way[i].clear();
F(i,1,n)cin>>l[i]>>r[i];
F(i,1,n){
F(j,1,n){
if(l[j]<l[i]&&r[i]<r[j]){
way[i].push_back(j);
ind[j]++;
}
}
}
priority_queue<int,vector<int>,greater<>>q;
F(i,1,n){
if(ind[i]==0)q.push(i);
}
F(i,1,n){
int u=q.top();
q.pop();
ans[u]=i;
for(auto v:way[u]){
ind[v]--;
if(ind[v]==0)q.push(v);
}
}
F(i,1,n)cout<<ans[i]<<' ';
cout<<'\n';
}
return 0;
}
}
signed main(){return code::main();}
//AC
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<random>
#include<unordered_map>
#include<complex>
using namespace std;
namespace code{
using ll=long long;
using ull=unsigned long long;
using uint=unsigned int;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F(i,x,y) for(int i=(x),__tt2__=(y);i<=__tt2__;i++)
#define R(i,x,y) for(int i=(x),__tt2__=(y);i>=__tt2__;i--)
#define _F(i,x,y) for(int i=(x),__tt2__=(y);i<__tt2__;i++)
#define _R(i,x,y) for(int i=(x),__tt2__=(y);i>__tt2__;i--)
#define debug(x) cerr<<#x<<'='<<(x)<<endl
#define lbt(x) (x&(~x+1))
#define e1 first
#define e2 second
constexpr int N=505;
int ind[N],l[N],r[N],ans[N];
vector<int>way[N];
signed main(){
cin.tie(0)->sync_with_stdio(0);
int T;
cin>>T;
while(T--){
int n;
cin>>n;
F(i,1,n)ind[i]=0,way[i].clear();
F(i,1,n)cin>>l[i]>>r[i];
F(i,1,n){
F(j,1,n){
if(l[j]<l[i]&&r[i]<r[j]){
way[j].push_back(i);
ind[i]++;
}
}
}
priority_queue<int>q;
F(i,1,n){
if(ind[i]==0)q.push(i);
}
R(i,n,1){
int u=q.top();
q.pop();
ans[u]=i;
for(auto v:way[u]){
ind[v]--;
if(ind[v]==0)q.push(v);
}
}
F(i,1,n)cout<<ans[i]<<' ';
cout<<'\n';
}
return 0;
}
}
signed main(){return code::main();}