QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214940 | #6550. Elimination Race | ucup-team180# | TL | 1ms | 3840kb | C++23 | 9.2kb | 2023-10-15 01:35:20 | 2023-10-15 01:35:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using ull = unsigned long long;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
template<class T> using pqmin = priority_queue<T, vector<T>, greater<T>>;
template<class T> using pqmax = priority_queue<T>;
const ll inf=LLONG_MAX/3;
const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define si(x) ll(x.size())
#define rep(i,n) for(ll i=0;i<n;i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define rng(i,l,r) for(ll i=l;i<r;i++)
#define gnr(i,l,r) for(ll i=r-1;i>=l;i--)
#define fore(i, a) for(auto &&i : a)
#define fore2(a, b, v) for(auto &&[a, b] : v)
#define fore3(a, b, c, v) for(auto &&[a, b, c] : v)
template<class T> bool chmin(T& a, const T& b){ if(a <= b) return 0; a = b; return 1; }
template<class T> bool chmax(T& a, const T& b){ if(a >= b) return 0; a = b; return 1; }
template<class T, class U> bool chmin(T& a, const U& b){ return chmin(a, (T)b); }
template<class T, class U> bool chmax(T& a, const U& b){ return chmax(a, (T)b); }
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type>name(__VA_ARGS__)
#define VEC(type,name,size) vector<type>name(size);in(name)
#define VLL(name,size) vector<ll>name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>> name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,w) vector<vector<type>> name(h,vector<type>(w));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>> name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
#define SUM(...) accumulate(all(__VA_ARGS__),0LL)
template<class T> auto min(const T& a){ return *min_element(all(a)); }
template<class T> auto max(const T& a){ return *max_element(all(a)); }
template<class T, class F = less<>> void sor(T& a, F b = F{}){ sort(all(a), b); }
template<class T> void uniq(T& a){ sor(a); a.erase(unique(all(a)), end(a)); }
void outb(bool x){cout<<(x?"Yes":"No")<<"\n";}
ll max(int x, ll y) { return max((ll)x, y); }
ll max(ll x, int y) { return max(x, (ll)y); }
int min(int x, ll y) { return min((ll)x, y); }
int min(ll x, int y) { return min(x, (ll)y); }
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{}))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{}))
ll gcd(ll a,ll b){return (b?gcd(b,a%b):a);}
vector<pll> factor(ull x){ vector<pll> ans; for(ull i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; }
vector<ll> divisor(ull x){ vector<ll> ans; for(ull i = 1; i * i <= x; i++) if(x % i == 0) ans.push_back(i); per(i,ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]); return ans; }
vll prime_table(ll n){vec(ll,isp,n+1,1);vll res;rng(i,2,n+1)if(isp[i]){res.pb(i);for(ll j=i*i;j<=n;j+=i)isp[j]=0;}return res;}
template <class T, class S> pair<T, S> operator-(const pair<T, S> &x) { return pair<T, S>(-x.first, -x.second); }
template <class T, class S> pair<T, S> operator-(const pair<T, S> &x, const pair<T, S> &y) { return pair<T, S>(x.fi - y.fi, x.se - y.se); }
template <class T, class S> pair<T, S> operator+(const pair<T, S> &x, const pair<T, S> &y) { return pair<T, S>(x.fi + y.fi, x.se + y.se); }
template <class T> pair<T, T> operator&(const pair<T, T> &l, const pair<T, T> &r) { return pair<T, T>(max(l.fi, r.fi), min(l.se, r.se)); }
template <class T, class S> pair<T, S> operator+=(pair<T, S> &l, const pair<T, S> &r) { return l = l + r; }
template <class T, class S> pair<T, S> operator-=(pair<T, S> &l, const pair<T, S> &r) { return l = l - r; }
template <class T> bool intersect(const pair<T, T> &l, const pair<T, T> &r) { return (l.se < r.se ? r.fi < l.se : l.fi < r.se); }
template <class T> vector<T> &operator++(vector<T> &v) {
fore(e, v) e++;
return v;
}
template <class T> vector<T> operator++(vector<T> &v, int) {
auto res = v;
fore(e, v) e++;
return res;
}
template <class T> vector<T> &operator--(vector<T> &v) {
fore(e, v) e--;
return v;
}
template <class T> vector<T> operator--(vector<T> &v, int) {
auto res = v;
fore(e, v) e--;
return res;
}
template <class T> vector<T> &operator+=(vector<T> &l, const vector<T> &r) {
fore(e, r) l.eb(e);
return l;
}
template<class... Ts> void in(Ts&... t);
[[maybe_unused]] void print(){}
template<class T, class... Ts> void print(const T& t, const Ts&... ts);
template<class... Ts> void out(const Ts&... ts){ print(ts...); cout << '\n'; }
namespace IO{
#define VOID(a) decltype(void(a))
struct S{ S(){ cin.tie(nullptr)->sync_with_stdio(0); fixed(cout).precision(12); } }S;
template<int I> struct P : P<I-1>{};
template<> struct P<0>{};
template<class T> void i(T& t){ i(t, P<3>{}); }
void i(vector<bool>::reference t, P<3>){ int a; i(a); t = a; }
template<class T> auto i(T& t, P<2>) -> VOID(cin >> t){ cin >> t; }
template<class T> auto i(T& t, P<1>) -> VOID(begin(t)){ for(auto&& x : t) i(x); }
template<class T, size_t... idx> void ituple(T& t, index_sequence<idx...>){ in(get<idx>(t)...); }
template<class T> auto i(T& t, P<0>) -> VOID(tuple_size<T>{}){ ituple(t, make_index_sequence<tuple_size<T>::value>{}); }
template<class T> void o(const T& t){ o(t, P<4>{}); }
template<size_t N> void o(const char (&t)[N], P<4>){ cout << t; }
template<class T, size_t N> void o(const T (&t)[N], P<3>){ o(t[0]); for(size_t i = 1; i < N; i++){ o(' '); o(t[i]); } }
template<class T> auto o(const T& t, P<2>) -> VOID(cout << t){ cout << t; }
template<class T> auto o(const T& t, P<1>) -> VOID(begin(t)){ bool first = 1; for(auto&& x : t) { if(first) first = 0; else o(' '); o(x); } }
template<class T, size_t... idx> void otuple(const T& t, index_sequence<idx...>){ print(get<idx>(t)...); }
template<class T> auto o(T& t, P<0>) -> VOID(tuple_size<T>{}){ otuple(t, make_index_sequence<tuple_size<T>::value>{}); }
#undef VOID
}
#define unpack(a) (void)initializer_list<int>{(a, 0)...}
template<class... Ts> void in(Ts&... t){ unpack(IO::i(t)); }
template<class T, class... Ts> void print(const T& t, const Ts&... ts){ IO::o(t); unpack(IO::o((cout << ' ', ts))); }
#undef unpack
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
LL(n);
VV(ll,ord,n-1,n);
vv(ll,rank,n-1,n);
rep(j,n-1){
rep(i,n){
ord[j][i]--;
rank[j][ord[j][i]]=i;
}
}
rep(x,n){
vv(ll,g,n-1);//race j -> person i, rank lower->higher
rep(j,n-1){
per(r,n){
if(ord[j][r]==x)break;
g[j].pb(ord[j][r]);
}
}
vec(ll,p,n-1,-1);
vec(ll,rp,n,-1);
bool ok=1;
rep(len,n-1){
vec(ll,befl,n-1,-1);
vec(ll,befr,n,-1);
queue<pll> que;
rep(j,n-1)if(!~p[j]){
befl[j]=-2;
que.push({j,0});
}
bool done=0;
while(!que.empty()){
auto [v,typ]=que.front();
que.pop();
if(typ==0){
rep(k,si(g[v])){
ll u=g[v][k];
if(befr[u]==-1){
befr[u]=v;
que.push({u,1});
}
}
}
else{
if(~rp[v]){
ll u=rp[v];
if(befl[u]==-1){
befl[u]=v;
que.push({u,0});
}
}
else{
while(1){
ll re=v;
ll le=befr[v];
p[le]=re;
rp[re]=le;
v=befl[le];
if(v==-2)break;
}
done=1;
break;
}
}
}
if(!done){
ok=0;
break;
}
}
// auto pp=p;
// pp++;
// out("p=",pp);
// cout<<flush;
vll ans;
if(ok){
vec(ll,used_race,n-1,0);
vec(ll,used_value,n,0);
vec(ll,last,n-1,n-1);
while(si(ans)<n-1){
vec(ll,f,n,-1);
rep(j,n-1)if(!used_race[j]){
f[p[j]]=ord[j][last[j]];
}
// out("f=",f);
vec(ll,deg,n,0);
{//namori->cycle
rep(i,n)if(~f[i]){
deg[f[i]]++;
}
// out("deg=",deg);
queue<ll> q;
rep(i,n){
if(deg[i]==0&&~f[i])q.push(i);
}
while(!q.empty()){
auto ii=q.front();
q.pop();
deg[f[ii]]--;
if(deg[f[ii]]==0){
q.push(f[ii]);
}
}
}
auto cop=p;
rep(j,n-1)if(deg[p[j]]>0){
cop[j]=f[p[j]];
}
// rep(i,n)if(deg[i]>0){
// rep(j,n-1)if(p[j]==i){
// cop[j]=f[i];
// }
// }
swap(p,cop);
// out("deg=",deg);
// cout<<flush;
bool done=0;
rep(j,n-1)if(!used_race[j]&&p[j]==ord[j][last[j]]){
done=1;
ans.pb(j);
used_race[j]=1;
used_value[p[j]]=1;
rep(jj,n-1)if(!used_race[jj]){
while(used_value[ord[jj][last[jj]]])last[jj]--;
}
// break;
}
assert(done);
}
}
if(si(ans)==n-1){
outb(1);
ans++;
out(ans);
}
else{
outb(0);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3840kb
input:
4 1 2 3 4 2 1 3 4 4 3 1 2
output:
Yes 1 2 3 No No No
result:
ok n=4, yes=1, no=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3540kb
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: 3484kb
input:
2 1 2
output:
Yes 1 No
result:
ok n=2, yes=1, no=1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
2 2 1
output:
No Yes 1
result:
ok n=2, yes=1, no=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3608kb
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 1 2 3 4 5 6 7 9 10 8 No No No No No No Yes 2 3 5 6 7 8 9 1 4 10 Yes 1 2 3 4 5 6 7 8 9 10 Yes 2 3 4 5 6 7 9 10 1 8 No
result:
ok n=11, yes=4, no=7
Test #6:
score: 0
Accepted
time: 0ms
memory: 3800kb
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:
Yes 1 2 4 5 6 7 9 10 3 8 No No Yes 1 2 3 5 6 7 8 9 10 4 No No Yes 1 2 3 4 5 6 7 8 9 10 No Yes 1 2 3 5 6 10 4 8 9 7 No No
result:
ok n=11, yes=4, no=7
Test #7:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
11 3 5 9 7 4 1 8 11 10 2 6 9 7 10 4 8 3 1 6 5 2 11 9 5 11 3 8 7 1 6 2 4 10 8 9 11 1 4 3 10 6 7 2 5 11 3 7 8 5 9 1 2 10 6 4 8 3 10 11 1 4 2 5 6 7 9 5 9 10 2 4 3 7 1 11 6 8 11 8 10 3 5 7 4 1 2 6 9 7 8 1 9 10 5 3 11 2 6 4 2 4 6 9 5 11 7 1 8 10 3
output:
Yes 1 2 3 5 6 7 8 10 9 4 No No No No No Yes 1 2 3 4 5 6 7 8 9 10 No No No No
result:
ok n=11, yes=2, no=9
Test #8:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
11 3 5 9 2 11 1 4 8 6 10 7 8 3 4 9 1 5 6 2 7 10 11 10 6 4 7 11 9 1 3 5 8 2 9 3 2 7 8 4 5 10 1 11 6 3 4 9 10 1 8 2 7 6 11 5 9 4 7 8 1 11 6 3 5 2 10 5 11 4 10 6 3 2 1 9 8 7 10 11 8 5 2 1 9 7 4 6 3 6 3 8 9 4 11 1 2 10 7 5 8 3 11 10 9 1 6 5 7 2 4
output:
Yes 1 2 3 4 6 8 9 10 5 7 No No No No No No Yes 2 3 4 5 7 10 1 6 8 9 Yes 1 2 3 4 5 6 7 8 9 10 No No
result:
ok n=11, yes=3, no=8
Test #9:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
11 3 5 7 10 9 6 2 1 11 8 4 3 6 1 7 5 11 4 10 9 8 2 10 4 6 7 11 3 1 2 9 5 8 10 4 1 9 11 5 3 8 6 7 2 11 5 9 1 10 4 8 6 7 2 3 3 2 7 9 11 10 1 5 8 4 6 4 5 11 8 6 7 10 1 2 3 9 2 7 3 11 8 1 9 6 4 10 5 4 8 2 7 5 10 6 1 11 3 9 9 6 3 5 1 10 11 7 8 4 2
output:
Yes 1 2 3 4 5 6 7 8 9 10 No No No No No Yes 3 4 5 6 7 8 9 10 1 2 No No Yes 2 3 4 5 6 7 8 9 10 1 Yes 1 3 5 6 8 9 10 2 4 7
result:
ok n=11, yes=4, no=7
Test #10:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
11 6 5 11 2 8 9 7 10 1 4 3 11 4 3 6 10 7 9 1 8 5 2 3 2 6 8 5 7 9 1 10 4 11 11 6 9 1 3 10 4 2 7 8 5 5 6 8 7 11 9 1 3 4 2 10 6 5 3 9 2 1 10 11 8 4 7 9 3 4 6 2 1 5 7 8 10 11 11 6 9 8 1 4 3 2 5 10 7 6 4 7 11 3 2 1 5 8 10 9 10 3 8 6 4 1 11 7 9 2 5
output:
No No No Yes 1 3 4 5 6 7 8 9 10 2 No Yes 1 2 3 4 5 6 7 8 9 10 No Yes 1 2 4 5 6 7 8 9 3 10 No No No
result:
ok n=11, yes=3, no=8
Test #11:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
11 10 5 4 6 11 1 3 7 9 8 2 2 8 10 4 6 1 7 9 3 11 5 5 7 11 8 3 1 9 2 4 10 6 5 6 11 10 3 1 2 9 8 4 7 6 3 4 9 11 5 1 2 8 10 7 8 7 6 1 10 3 5 11 9 4 2 5 11 9 4 6 2 7 1 8 3 10 10 11 2 1 9 4 3 5 8 6 7 9 3 4 6 5 1 11 8 2 7 10 7 10 4 5 9 6 8 1 3 11 2
output:
Yes 2 3 4 5 7 8 10 1 6 9 No Yes 2 3 4 7 8 10 1 5 6 9 Yes 2 3 4 5 6 7 8 9 10 1 No No No Yes 1 2 5 8 9 10 4 7 3 6 Yes 1 2 3 4 5 6 7 8 9 10 No Yes 2 3 4 8 9 10 1 5 6 7
result:
ok n=11, yes=6, no=5
Test #12:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
11 7 8 4 5 1 3 6 9 11 10 2 8 10 9 7 1 3 5 4 2 11 6 4 11 9 5 3 1 2 10 8 6 7 9 6 7 1 3 8 2 4 10 5 11 9 3 10 2 4 1 6 7 5 11 8 9 3 1 7 2 6 5 8 11 4 10 2 4 9 3 1 5 11 6 7 8 10 3 4 11 10 8 6 1 5 2 7 9 4 11 7 6 8 1 10 9 3 5 2 8 7 4 9 10 3 1 5 2 6 11
output:
Yes 1 2 3 5 6 8 10 7 9 4 No Yes 2 3 4 5 8 9 1 6 7 10 Yes 1 2 3 4 5 6 7 8 9 10 Yes 4 5 6 7 8 9 10 1 2 3 No No No No No No
result:
ok n=11, yes=4, no=7
Test #13:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
11 4 8 10 9 6 3 1 5 2 7 11 10 8 7 4 9 1 6 11 3 2 5 3 10 11 6 1 4 5 2 7 9 8 4 9 8 3 1 6 11 7 5 2 10 8 2 11 7 3 1 5 6 10 4 9 4 9 3 6 5 1 7 10 11 2 8 4 3 6 7 1 5 8 2 9 11 10 10 7 4 1 9 8 2 3 6 11 5 10 7 2 8 5 1 11 6 4 3 9 7 6 9 8 1 11 5 4 2 3 10
output:
Yes 1 2 3 5 6 7 8 9 10 4 Yes 1 2 4 6 7 8 10 3 5 9 Yes 1 2 3 6 8 9 10 4 5 7 Yes 1 2 3 5 6 8 9 10 4 7 No Yes 2 3 4 5 6 8 9 10 1 7 Yes 1 2 3 4 5 6 7 8 9 10 No No No No
result:
ok n=11, yes=6, no=5
Test #14:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
11 8 5 9 7 6 1 10 4 2 3 11 3 6 5 11 9 7 1 2 4 10 8 2 11 3 8 1 6 7 5 4 10 9 7 5 8 6 4 9 1 2 3 10 11 6 7 8 1 2 3 11 9 10 5 4 7 4 10 9 1 2 8 5 11 3 6 10 7 5 6 11 3 1 2 9 4 8 5 2 6 8 10 1 9 3 4 7 11 5 7 3 11 8 2 1 6 9 4 10 2 3 10 4 1 11 5 7 8 9 6
output:
Yes 1 2 3 5 6 7 8 9 10 4 Yes 1 2 3 4 6 7 8 9 10 5 Yes 1 2 3 4 5 6 7 8 9 10 No Yes 1 2 3 4 5 7 8 10 6 9 No Yes 2 3 5 7 8 10 1 4 6 9 No No No No
result:
ok n=11, yes=5, no=6
Test #15:
score: -100
Time Limit Exceeded
input:
500 446 156 267 294 482 398 430 13 311 318 474 426 140 484 83 387 257 136 69 305 295 283 287 55 52 65 322 249 43 56 331 443 226 214 341 182 389 464 84 477 187 40 327 411 248 10 223 165 379 293 12 9 5 230 309 367 2 397 265 59 361 118 196 316 390 213 194 167 483 452 114 345 263 219 87 94 160 224 200 2...
output:
Yes 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 ...