oj.uz

Submission #640626

# Submission time Handle Problem Language Result Execution time Memory
640626 2022-09-15T03:45:54 Z baokhue232005 Zagonetka (COI18_zagonetka) C++14
100 / 100
 82 ms 372 KB 
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

#include<bits/stdc++.h>
using namespace std;

#define all(flg) flg.begin(), flg.end()
#define pb push_back
#define fi first
#define se second
#define eb emplace_back
#define ii pair<int, int>
#define vi vector<int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define ld long double
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 300005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k;

int posy[101];
bool aw[101][101];
int ray[101];
int cnt[101];

vector<int> vc[101];

void solve(bool suck){
    priority_queue<int> pq;
    for1(i, 1, n){
        ray[i] = i;
        vc[i].clear();
        cnt[i] = 0;
    }
    //
    for1(i, 1, n) for1(j, 1, n) if(aw[i][j]){
        vc[posy[j]].pb(posy[i]);
        ++cnt[posy[i]];
    }
    x = n;
    for1(i, 1, n) if(!cnt[i]) pq.push(i);
    while(!pq.empty()){
        int node = pq.top(); pq.pop();
        a[node] = x--;
        for(int cc : vc[node]){
            --cnt[cc]; if(!cnt[cc]) pq.push(cc);
        }
    }
    if(suck) for1(i, 1, n) a[i] = n + 1 - a[i];
    for1(i, 1, n) cout << a[i] << " ";
    cout << endl;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for1(i, 1, n){
        cin >> x; posy[x] = i;
    }
    for1(len, 1, n) for1(l, 1, n){
        int r = l + len; if(r > n) continue;
        for1(i, 1, n){
            ray[i] = i;
            vc[i].clear();
            cnt[i] = 0;
        }
        for1(i, l, r) ray[i] = 0;
        int sta = r + 1;
        for1(i, l, r) for1(j, i + 1, r) if(aw[i][j]){
            vc[j].pb(i); ++cnt[i];
        }
        vc[l].pb(r); ++cnt[r];
        vector<int> stk;
        for1(i, l, r) if(!cnt[i]) stk.pb(i);
        while(!stk.empty()){
            int node = stk.back(); stk.pop_back();
            ray[node] = --sta;
            for(int cc : vc[node]){
                --cnt[cc]; if(!cnt[cc]) stk.pb(cc);
            }
        }
        x = 0;
        for1(i, 1, n) if(!ray[i]) x = 1;
        if(x){
            aw[l][r] = 1; continue;
        }
        for1(i, 1, n) a[posy[i]] = ray[i];
        cout << "query ";
        for1(i, 1, n) cout << a[i] << " ";
        cout << endl;
        cin >> x; if(!x) aw[l][r] = 1;
    }
    cout << "end\n";
    solve(0);
    for1(i, 1, n) for1(j, i + 1, n) if(aw[i][j]){
        aw[j][i] = 1; aw[i][j] = 0;
    }
    solve(1);
}

Subtask #1
9.0 / 9.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 208 KB Output is correct
2 Correct 26 ms 336 KB Output is correct
3 Correct 32 ms 336 KB Output is correct
4 Correct 31 ms 336 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 31 ms 336 KB Output is correct
7 Correct 5 ms 208 KB Output is correct
8 Correct 7 ms 208 KB Output is correct
9 Correct 30 ms 336 KB Output is correct
10 Correct 8 ms 336 KB Output is correct

Subtask #3
22.0 / 22.0

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

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 336 KB Output is correct
2 Correct 78 ms 208 KB Output is correct
3 Correct 74 ms 336 KB Output is correct
4 Correct 19 ms 368 KB Output is correct
5 Correct 27 ms 372 KB Output is correct
6 Correct 19 ms 364 KB Output is correct
7 Correct 34 ms 340 KB Output is correct
8 Correct 45 ms 344 KB Output is correct
9 Correct 43 ms 344 KB Output is correct
10 Correct 82 ms 336 KB Output is correct
11 Correct 67 ms 336 KB Output is correct
12 Correct 61 ms 208 KB Output is correct
13 Correct 79 ms 336 KB Output is correct
14 Correct 68 ms 336 KB Output is correct
15 Correct 81 ms 336 KB Output is correct
16 Correct 75 ms 336 KB Output is correct