oj.uz

Submission #243461

# Submission time Handle Problem Language Result Execution time Memory
243461 2020-07-01T08:22:25 Z kartel Zagonetka (COI18_zagonetka) C++14
100 / 100
 99 ms 640 KB 
#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)
{
    for (i = 0; i < n; i++)
        sort(g[i].begin(), g[i].end());

    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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB Output is correct
2 Correct 34 ms 384 KB Output is correct
3 Correct 39 ms 384 KB Output is correct
4 Correct 37 ms 384 KB Output is correct
5 Correct 16 ms 384 KB Output is correct
6 Correct 31 ms 512 KB Output is correct
7 Correct 12 ms 384 KB Output is correct
8 Correct 12 ms 384 KB Output is correct
9 Correct 39 ms 384 KB Output is correct
10 Correct 19 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 9 ms 384 KB Output is correct
4 Correct 9 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 8 ms 384 KB Output is correct
7 Correct 9 ms 384 KB Output is correct
8 Correct 9 ms 384 KB Output is correct
9 Correct 10 ms 512 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 9 ms 384 KB Output is correct
12 Correct 11 ms 384 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 512 KB Output is correct
2 Correct 83 ms 512 KB Output is correct
3 Correct 82 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 20 ms 540 KB Output is correct
8 Correct 37 ms 512 KB Output is correct
9 Correct 21 ms 512 KB Output is correct
10 Correct 92 ms 512 KB Output is correct
11 Correct 62 ms 632 KB Output is correct
12 Correct 85 ms 512 KB Output is correct
13 Correct 79 ms 512 KB Output is correct
14 Correct 73 ms 512 KB Output is correct
15 Correct 99 ms 512 KB Output is correct
16 Correct 71 ms 608 KB Output is correct