Submission #240881

#	Time	Username	Problem	Language	Result	Execution time	Memory
240881		NONAME	Zagonetka (COI18_zagonetka)	C++14	100 / 100	90 ms	564 KiB

zagonetka

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e2;

int n, p[N], pos[N];
bool is[N][N];
vector <int> g[N];

bool gd(vector <int> q) {
    cout << "query ";
    for (int i : q)
        cout << i << " ";
    cout << endl;
    
    //cerr << "query ";
    //for (int i : q)
        //cerr << i << " ";
    //cerr << "\n";
    
    bool x;
    cin >> x;
    return x;
}

void dfs(vector <int> &v, int u, int &cur, int upd) {
    if (v[u] != 0)
        return;
        
    for (int to : g[u])
        dfs(v, to, cur, upd);
    
    v[u] = cur;
    cur += upd;
}

void solve(vector <int> &v, int cur, int upd) {
    for (int i = 0; i < n; ++i)
        sort(g[i].begin(), g[i].end());
    
    for (int i = 0; i < n; ++i)
        if (v[i] == 0)
            dfs(v, i, cur, upd);
        
    for (int i = 0; i < n; ++i)
        g[i].clear();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        pos[p[i]] = i;
    }
    
    for (int i = 1; i <= n; ++i)
        is[i][i] = 1;
    
    for (int t = 1; t <= n; ++t)
    for (int i = 1; i + t <= n; ++i) {
        int j = i + t;
        
        bool f = 0;
        
        for (int k = i + 1; k < j; ++k)
            if (is[i][k] && is[k][j])
                f = 1;
        
        if (f) {
            is[i][j] = 1;
            continue;
        }
        
        //cerr << i << " " << j << " ";
        
        vector <int> vec;
        vec.clear();
        
        for (int k = i; k <= j; ++k)
            if (is[i][k] || is[k][j])
                vec.push_back(k);
                
        reverse(vec.begin(), vec.end());
                
        vector <int> qu;
        
        for (int k = 0; k < n; ++k)
            qu.push_back(p[k]);
        
        int ps = 0;
        
        for (int k = j; k >= i; --k)
            if (is[i][k])
                qu[pos[k]] = vec[ps++];
                
        for (int k = j; k >= i; --k)
            if (is[k][j])
                qu[pos[k]] = vec[ps++];
              
        f = gd(qu);
        //cerr << f << "\n";
                
        is[i][j] = f ^ 1;
    }
    
    vector <int> mn(n, 0), mx(n, 0);
    
    for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
        if (is[i][j])
            g[pos[j]].push_back(pos[i]);
    solve(mn, 1, +1);
    
    for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
        if (is[i][j])
            g[pos[i]].push_back(pos[j]);
    solve(mx, n, -1);
    
    cout << "end" << endl;
    
    for (int i = 0; i < n; ++i)
        cout << mn[i] << " ";
    cout << endl;
    
    for (int i = 0; i < n; ++i)
        cout << mx[i] << " ";
    cout << endl;
    
    //for (int i : mn)
        //cerr << i << " ";
    //cerr << "\n";
    
    //for (int i : mx)
        //cerr << i << " ";
    //cerr << "\n";
    
    //for (int i = 1; i <= n; ++i, cerr << endl)
    //for (int j = 1; j <= n; ++j)
        //cerr << is[i][j] << " ";
}

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