QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#359259 | #6550. Elimination Race | Kevin5307 | WA | 1ms | 3872kb | C++20 | 1.7kb | 2024-03-20 15:25:41 | 2024-03-20 15:25:42 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int grid[505][505];
int pos[505][505];
set<int> st[505];
bool used[505];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<n;i++)
for(int j=1;j<=n;j++)
{
cin>>grid[i][j];
pos[i][grid[i][j]]=j;
}
for(int i=1;i<=n;i++)
{
bool flag=1;
vector<int> ans;
for(int j=1;j<n;j++)
st[j].clear();
for(int j=1;j<n;j++)
for(int x=pos[j][i]+1;x<=n;x++)
st[j].insert(x);
memset(used,0,sizeof(used));
for(int j=1;j<n;j++)
{
int p=0;
for(int x=1;x<n;x++) if(!used[x])
if(!p||sz(st[x])<sz(st[p]))
p=x;
if(!sz(st[p]))
{
flag=0;
break;
}
used[p]=1;
int ppos=*st[p].rbegin();
st[p].erase(ppos);
int value=grid[p][ppos];
for(int x=1;x<n;x++)
if(pos[x][value]>pos[x][i])
st[x].erase(pos[x][value]);
ans.pb(p);
}
if(!flag)
cout<<"No\n";
else
{
cout<<"Yes\n";
for(auto x:ans)
cout<<x<<" ";
cout<<'\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3872kb
input:
4 1 2 3 4 2 1 3 4 4 3 1 2
output:
Yes 3 1 2 No No No
result:
ok n=4, yes=1, no=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
3 2 1 3 2 1 3
output:
No Yes 1 2 No
result:
ok n=3, yes=1, no=2
Test #3:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
2 1 2
output:
Yes 1 No
result:
ok n=2, yes=1, no=1
Test #4:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
2 2 1
output:
No Yes 1
result:
ok n=2, yes=1, no=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
11 4 3 6 1 11 10 5 7 8 9 2 11 6 5 1 10 3 8 2 7 9 4 5 9 2 11 3 4 1 10 8 6 7 9 11 8 3 5 4 1 6 7 10 2 3 9 7 6 5 10 1 4 11 8 2 8 2 4 1 5 9 3 7 6 10 11 3 8 2 9 1 4 5 10 11 6 7 10 11 4 1 7 5 2 6 8 9 3 10 6 9 3 2 1 4 8 11 7 5 8 11 9 1 4 10 2 5 3 7 6
output:
Yes 3 4 5 9 1 8 2 10 6 7 No No No No No No Yes 5 1 8 2 3 9 4 6 7 10 Yes 1 2 8 6 9 7 10 3 4 5 Yes 4 6 7 3 10 1 2 5 8 9 No
result:
ok n=11, yes=4, no=7
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3644kb
input:
11 6 7 8 9 3 4 1 11 5 10 2 7 10 6 3 1 2 5 11 4 9 8 4 3 9 1 10 2 5 7 6 8 11 10 4 2 11 8 1 5 7 9 6 3 11 9 4 6 8 2 1 7 3 5 10 9 10 2 7 4 11 6 1 3 8 5 11 8 4 9 7 1 2 10 5 3 6 5 7 9 10 1 8 4 2 6 11 3 4 2 9 7 10 1 6 8 3 5 11 2 7 6 10 5 11 1 8 4 9 3
output:
No No No Yes 2 10 8 6 1 4 5 3 7 9 No No Yes 3 4 5 7 9 6 10 1 2 8 No Yes 2 10 4 7 9 1 3 5 6 8 No No
result:
wrong answer Jury has the answer but participant has not