Submission #243459

#	Time	Username	Problem	Language	Result	Execution time	Memory
243459		kartel	Zagonetka (COI18_zagonetka)	C++14	18 / 100	82 ms	640 KiB

zagonetka

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +405
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e9)
//#define el '\n'
#define el endl
#define pii pair <int, int>
#define err ld(1e-9)
#define last(x) x.back()
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

vector <int> ans[2], g[N];
int L, R, mid, i, p[N], pos[N], good[N][N], n, len, v;

bool check(vector <int> &v)
{
    cout << "query";
    for (auto x : v) cout << " " << x + 1;

    bool x;
    cout << el;
    cin >> x;

    return x;
}

void dfs(vector <int> &ans, int v, int &nxt, int up)
{
    if (ans[v])
        return;

    for (auto u : g[v]) dfs(ans, u, nxt, up);

    ans[v] = nxt;
    nxt += up;
}

void solve(vector <int> &ans, int nxt, int up)
{
    ans.resize(n);

    for (i = 0; i < n; i++)
        if (ans[i] == 0)
          dfs(ans, i, nxt, up);
}

int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    //in("input.txt");
    //out("output.txt");

    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> p[i];
        p[i]--;
        pos[p[i]] = i;
        good[i][i] = 1;
    }

    for (len = 1; len < n; len++)
    for (int L = 0; L < n; L++)
    {
        int R = L + len;

        if (R >= n) break;

        bool bad = 1;

        for (mid = L + 1; mid < R; mid++)
            if (good[L][mid] && good[mid][R])
              bad = 0;

        if (!bad)
        {
            good[L][R] = 1;
            continue;
        }

        vector <int> v, fc;
        fc.resize(n);

        for (int i = 0; i < n; i++) fc[i] = p[i];

        for (int mid = L; mid <= R; mid++)
            if (good[L][mid] || good[mid][R])
              v.pb(mid);

        reverse(v.begin(), v.end());
        int i = 0;

        for (int mid = R; mid >= L; mid--)
            if (good[L][mid])
                fc[pos[mid]] = v[i++];

        for (int mid = R; mid >= L; mid--)
            if (good[mid][R])
              fc[pos[mid]] = v[i++];

        int ch = check(fc);

        good[L][R] = ch ^ 1;
    }

    for (L = 0; L < n; L++)
    for (R = L + 1; R < n; R++)
      if (good[L][R])
        g[pos[R]].pb(pos[L]);

    solve(ans[0], 1, 1);

    for (i = 0; i < n; i++) g[i].clear();

    for (L = 0; L < n; L++)
    for (R = L + 1; R < n; R++)
      if (good[L][R])
        g[pos[L]].pb(pos[R]);

    solve(ans[1], n, -1);

    cout << "end" << el;

    for (auto x : ans[0]) cout << x << " ";
    cout << el;

    for (auto x : ans[1]) cout << x << " ";
    cout << el;
}

//
//00000
//00110
//00111
//00011
//00000

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