QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214923#6550. Elimination Raceucup-team180#TL 0ms3796kbC++239.1kb2023-10-15 01:25:402023-10-15 01:25:40

Judging History

你现在查看的是最新测评结果

  • [2023-10-15 01:25:40]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3796kb
  • [2023-10-15 01:25:40]
  • 提交

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(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;

				rep(j,n-1)if(!used_race[j]&&p[j]==ord[j][last[j]]){
					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;
				}
			}
    }
		if(si(ans)==n-1){
			outb(1);
      ans++;
      out(ans);
		}
    else{
      outb(0);
    }
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3500kb

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: 3532kb

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: 3628kb

input:

2
1 2

output:

Yes
1
No

result:

ok n=2, yes=1, no=1

Test #4:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

2
2 1

output:

No
Yes
1

result:

ok n=2, yes=1, no=1

Test #5:

score: 0
Accepted
time: 0ms
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
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: 3544kb

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: 0ms
memory: 3636kb

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: 3628kb

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: 3616kb

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: 3604kb

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: 3548kb

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: 3796kb

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: 3620kb

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: 3620kb

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 ...

result: