Submission #1318051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318051		edo	Zagonetka (COI18_zagonetka)	C++20	100 / 100	28 ms	568 KiB

zagonetka

#include <bits/stdc++.h>

using namespace std;
using ll   = long long;
using vi   = vector<int>;
using vll  = vector<ll>;
using vvi  = vector<vi>;
using vvll = vector<vll>;
using pii  = pair<int,int>;
using pll  = pair<ll,ll>;
using ui    = unsigned int;
using ull   = unsigned long long;
using pui   = pair<ui,ui>;
using pull  = pair<ull,ull>;
using i128 = __int128_t;

template<typename T>
using vc = std::vector<T>;


#define YES cout << "YES\n"
#define NO  cout << "NO\n"
#define yes cout << "yes\n"
#define no  cout << "no\n"
#define Yes cout << "Yes\n"
#define No  cout << "No\n"

template<typename T> void sc(T &x) { cin >> x; }
template<typename T, typename U> void sc(pair<T,U> &p) { sc(p.first), sc(p.second); }
template<typename T> void sc(vector<T> &v) { for (auto &x : v) sc(x); }
template<typename... A> void sc(A&... a) { (sc(a), ...); }


template<typename T> void _pt(const T &x){cout << x;}
template<typename T, typename U> void _pt(const pair<T,U> &p){_pt(p.first); cout << ' '; _pt(p.second);}
template<typename T> void _pt(const vector<T> &v){bool f=1; for(auto &x:v){if(!f) cout<<' '; _pt(x); f=0;}}
template<typename... A> void pt(const A&... a){(_pt(a), ...);}


template<typename T, typename U> bool umin(T &a, const U &b) { return b < a ? (a = b, true) : false; }
template<typename T, typename U> bool umax(T &a, const U &b) { return b > a ? (a = b, true) : false; }
template<typename T> T maxel(const vector<T>& v){ return *max_element(v.begin(), v.end()); }
template<typename T> T minel(const vector<T>& v){ return *min_element(v.begin(), v.end()); }
template<typename T, int N> T maxel(T (&a)[N]) { return *max_element(a, a + N); }
template<typename T, int N> T minel(T (&a)[N]) { return *min_element(a, a + N); }


template<typename C, typename T> auto lb(C& c, const T& x){ return std::lower_bound(c.begin(), c.end(), x); }
template<typename C, typename T> auto ub(C& c, const T& x){ return std::upper_bound(c.begin(), c.end(), x); }

template<typename T> auto lb(std::set<T>& s, const T& x){ return s.lower_bound(x); }
template<typename T> auto ub(std::set<T>& s, const T& x){ return s.upper_bound(x); }
template<typename T> auto lb(const std::set<T>& s, const T& x){ return s.lower_bound(x); }
template<typename T> auto ub(const std::set<T>& s, const T& x){ return s.upper_bound(x); }

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define FOR1(n)            for (int i=0; i<(n); ++i)
#define FOR2(i,n)          for (int i=0; i<(n); ++i)
#define FOR3(i,l,r)        for (int i=(l); i<(r); ++i)
#define FOR4(i,l,r,k)      for (int i=(l); i<(r); i+=(k))
#define FOR(...)           GET_MACRO(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define ROF1(n)            for (int i=(n)-1; i>=0; --i)
#define ROF2(i,n)          for (int i=(n)-1; i>=0; --i)
#define ROF3(i,l,r)        for (int i=(r)-1; i>=(l); --i)
#define ROF4(i,l,r,k)      for (int i=(r)-1; i>=(l); i-=(k))
#define ROF(...)           GET_MACRO(__VA_ARGS__, ROF4, ROF3, ROF2, ROF1)(__VA_ARGS__)
#define all(c)   (c).begin(), (c).end()
#define allr(c)  (c).rbegin(), (c).rend()
#define eb       emplace_back
#define mp       make_pair
#define mt       make_tuple
#define fi       first
#define se       second
#define pb       push_back
#define trav(x,a) for (auto &x : (a))
#define sz(a) ((int)(a).size())
#define mem(a,v) memset(a, v, sizeof(a))
#define nl pt("\n")


int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    sc(n);
    
    vi p(n), p2(n), pos(n + 1), ans(n);
    FOR(n) {
        sc(p[i]);
        p2[i] = p[i];
        pos[p[i]] = i;
    }

    auto ask = [&]() -> int {
        pt("query ");
        pt(p2);
        cout << endl;
        int ok;
        sc(ok);
        return ok ^ 1;
    };

    vvi V(n, vi(n, -1));
    FOR(n) 
        FOR(j, n) 
            if(p[i] >= p[j])
                V[i][j] = 0;

    function<int(int, int)> calc = [&](int a, int b) -> int {
        if(V[a][b] != -1) return V[a][b];

        vi v, m, s;
        FOR(val, p[a] + 1, p[b]) {
            int x = pos[val];

            int ax = calc(a, x);
            int xb = calc(x, b);

            if(ax == 1) v.pb(x);
            else if(xb == 1) m.pb(x);
            else s.pb(x);

            if(ax & xb) return V[a][b] = 1;
        }        

        int br = p[a];
        trav(x, m) p2[x] = br++;
        p2[b] = br++;
        trav(x, s) p2[x] = br++;
        p2[a] = br++;
        trav(x, v) p2[x] = br++;
    
        V[a][b] = ask();

        p2 = p;
        return V[a][b];
    };

    vi pref[n], suf[n];
    FOR(n) 
        FOR(j, n) 
            if(calc(i, j)) {
                pref[j].pb(i);
                suf[i].pb(j);
            }
        
    FOR(n) {
        sort(all(pref[i]));
        sort(all(suf[i]));
    }

    pt("end"); cout << endl;

    function<int(int, int)> dfs1 = [&](int x, int l) -> int {
        int need = 0;
        trav(y, pref[x]) if(ans[y] == 0) ++need;
        ans[x] = l + need;

        trav(y, pref[x]) 
            if(ans[y] == 0)
                l += dfs1(y, l);

        return need + 1;
    };

    int br = 1;
    FOR(n) 
        if(ans[i] == 0)
            br += dfs1(i, br);

    pt(ans); cout << endl; 

    vi(n, 0).swap(ans);

    function<int(int, int)> dfs2 = [&](int x, int l) -> int {
        int need = 0;
        trav(y, suf[x]) if(ans[y] == 0) ++need;
        ans[x] = l - need;

        trav(y, suf[x]) 
            if(ans[y] == 0)
                l -= dfs2(y, l);

        return need + 1;
    };

    br = n;
    FOR(n) 
        if(ans[i] == 0) 
            br -= dfs2(i, br);
    
    pt(ans);
    cout << endl;

    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 51 / 51