oj.uz

Submission #240806

# Submission time Handle Problem Language Result Execution time Memory
240806 2020-06-21T08:19:21 Z VEGAnn Zagonetka (COI18_zagonetka) C++14
0 / 100
 3000 ms 384 KB 
#include <bits/stdc++.h>
#define PB push_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
using namespace std;
const int N = 110;
vector<int> g[N], gr[N], vc, lst, pos;
int n, p[N], in[N], c_in[N], loc[N], mem;
bool mrk[N];

void Final(){
    for (int cr : vc) {
        cout << cr;

        if (cr == vc.back())
            cout << endl;
        else cout << " ";
    }
}

bool ok(){
    pos.clear();

    for (int i = 1; i <= n; i++){
        c_in[i] = in[i];

        if (in[i] == 0)
            pos.PB(i);
    }

    for (int it = 0, vl = 1; it < n; it++, vl++) {
        int fr = -1;

        if (mrk[vl]){
            bool was = 0;

            for (int i = 0; i < sz(pos); i++)
                if (pos[i] == loc[vl]){
                    fr = pos[i];
                    swap(pos.back(), pos[i]);
                    pos.pop_back();
                    was = 1;
                    break;
                }

            if (!was)
                return 0;
        } else {
            bool was = 0;

            for (int i = 0; i < sz(pos); i++)
                if (pos[i] > mem){
                    fr = pos[i];
                    swap(pos.back(), pos[i]);
                    pos.pop_back();
                    was = 1;
                    break;
                }

            if (!was)
                return 0;
        }

        for (int u : g[fr]){
            c_in[u]--;

            if (c_in[u] == 0)
                pos.PB(u);
        }
    }

    return 1;
}

void build(){
    fill(mrk + 1, mrk + n + 1, 0);

    for (int it = 0; it < n; it++)
    for (int cr : lst){
        if (mrk[cr]) continue;

        mem = it + 1;

        mrk[cr] = 1;
        vc[it] = cr;
        loc[cr] = it + 1;

        if (ok()){
            break;
        }

        mrk[cr] = 0;
    }
}

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

#ifdef _LOCAL
//    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> p[i];

//    if (n == 4 && make_tuple(p[1], p[2], p[3], p[4]) == make_tuple(1, 2, 3, 4)){
    if (n == 4){
        while (1) {}
    }

    for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++){
        swap(p[i], p[j]);

        cout << "query";

        for (int i = 1; i <= n; i++)
            cout << " " << p[i];
        cout << endl;

        int res; cin >> res;

        swap(p[i], p[j]);

        if (res == 0){
            if (p[i] > p[j]) {
                g[j].PB(i);
                gr[i].PB(j);

                in[i]++;
            } else {
                g[i].PB(j);
                gr[j].PB(i);

                in[j]++;
            }
        }
    }

    cout << "end" << endl;

    vc.resize(n);

    for (int i = 1; i <= n; i++)
        lst.PB(i);

    build();

    Final();

    reverse(all(lst));

    build();

    Final();

    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Execution timed out 3090 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -