QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214990#6550. Elimination Raceucup-team180#Compile Error//C++1715.4kb2023-10-15 01:59:502023-10-15 01:59:52

Judging History

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

  • [2023-10-15 01:59:52]
  • 评测
  • [2023-10-15 01:59:50]
  • 提交

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
} // namespace IO
#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

template <typename T = long long, const int sz = 5 * 10000000> struct IIO {
    char reader[sz], writer[sz];
    char *now, *now2 = writer;
    IIO() {
        reader[fread(reader, sizeof(char), sizeof(char) * sz, stdin)];
        now = reader;
    }
    inline T read() {
        while(*now && *now <= 32) now++;
        if(*now == '-') {
            now++;
            T res = 0;
            while('0' <= *now and *now <= '9') { res = res * 10 + *now++ - '0'; }
            return -res;
        } else {
            T res = 0;
            while('0' <= *now and *now <= '9') { res = res * 10 + *now++ - '0'; }
            return res;
        }
    }
    inline void read(T &res) {
        while(*now && *now <= 32) now++;
        if(*now == '-') {
            now++;
            res = 0;
            while('0' <= *now and *now <= '9') { res = res * 10 + *now++ - '0'; }
            res = -res;
        } else {
            res = 0;
            while('0' <= *now and *now <= '9') { res = res * 10 + *now++ - '0'; }
        }
    }
    inline string read_str() {
        while(*now && *now <= 32) now++;
        string res;
        while(*now and *now != '\n' and *now != ' ') res += *now++;
        now++;
        return res;
    }
    template <class S> inline void write(S x, char margin = ' ') {
        if(x == 0) {
            putchar('0');
            putchar(margin);
            return;
        }
        if(x < 0) {
            putchar('-');
            x = -x;
        }
        while(x) {
            *now2 = '0' + x % 10;
            now2++;
            x /= 10;
        }
        do {
            now2--;
            putchar(*now2);
        } while(now2 != writer);
        putchar(margin);
    }
    inline void write_str(string s, char margin = ' ') {
        for(auto c : s) putchar(c);
        putchar(margin);
    }
};
IIO<int> io;
inline int read() { return io.read(); }
inline void write(ll x) { io.write(x); }
int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(0);
    ll n = read();
    vv(ll, ord, n - 1, n);
    rep(i, n - 1) rep(j, n) ord[i][j] = read();
    vv(ll, rank, n - 1, n);
    rep(j, n - 1) {
        rep(i, n) {
            ord[j][i]--;
            rank[j][ord[j][i]] = i;
        }
    }
    vec(ll, ideal_p, n - 1, -1);
    ll max_pairs = 0;
    queue<pll> que;
    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);

        rep(j, n - 1) if(~ideal_p[j]) {
            if(rank[j][x] < rank[j][ideal_p[j]]) {
                p[j] = ideal_p[j];
                rp[p[j]] = j;
            }
        }

        while(1) {
            while(!que.empty()) que.pop();
            vec(ll, befl, n - 1, -1);
            vec(ll, befr, n, -1);
            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) { break; }
        }

        ll cnt = 0;
        rep(j, n - 1) cnt += p[j] >= 0;
        bool ok = cnt == n - 1;
        if(cnt > max_pairs) {
            max_pairs = cnt;
            ideal_p = p;
        }
        // cout<<"cnt="<<cnt<<endl;

        // 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) {
            io.write("Yes", '\n');
            ans++;
            rep(i, ans.size()) { io.write(ans[i], " \n"[i == ans.size() - 1]); }
        } else {
            io.write("No", '\n');
        }
    }
}

详细

answer.code: In instantiation of ‘void IIO<T, sz>::write(S, char) [with S = const char*; T = int; int sz = 50000000]’:
answer.code:410:21:   required from here
answer.code:243:14: error: ordered comparison of pointer with integer zero (‘const char*’ and ‘int’)
  243 |         if(x < 0) {
      |            ~~^~~
answer.code:245:18: error: wrong type argument to unary minus
  245 |             x = -x;
      |                  ^
answer.code:248:29: error: invalid operands of types ‘const char*’ and ‘int’ to binary ‘operator%’
  248 |             *now2 = '0' + x % 10;
      |                           ~~^~~~
answer.code:250:15: error: invalid operands of types ‘const char*’ and ‘int’ to binary ‘operator/’
  250 |             x /= 10;
      |             ~~^~~~~
answer.code:250:15: note:   in evaluation of ‘operator/=(const char*, int)’