Submission #168059

#	Time	Username	Problem	Language	Result	Execution time	Memory
168059		egekabas	Zagonetka (COI18_zagonetka)	C++14	9 / 100	47 ms	376 KiB

zagonetka

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
int n;
int a[109];
int b[109];
int q(int ar[]){
    cout << "query ";
    vector<int> v(n);
    //v.clear();
    for(int i = 0; i < n; ++i)
        v[ar[i]] = i+1;
    for(auto u : v)
        cout << u << " ";
    cout << endl;
    int t1;
    cin >> t1;
    return t1;
}
    
void sf1(int l, int r){
    if(l >= r)
        return;
    int mini = 1e9;
    int id = -1;
    for(int i = l; i <= r; ++i){
        if(a[i] < mini){
            mini = a[i];
            id = i;
        }
    }
    sf1(l, id-1);
    for(id = id-1; id >= l; --id){
        swap(a[id+1], a[id]);
        if(q(a) == 0){
            swap(a[id+1], a[id]);
            break;
        }
    }
    id++;
    sf1(id+1, r);
}
void sf2(int l, int r){
    if(l >= r)
        return;
    int maxi = -1e9;
    int id = -1;
    for(int i = l; i <= r; ++i){
        if(b[i] > maxi){
            maxi = b[i];
            id = i;
        }
    }
    sf2(l, id-1);
    for(id = id-1; id >= l; --id){
        swap(b[id+1], b[id]);
        if(q(b) == 0){
            swap(b[id+1], b[id]);
            break;
        }
    }
    id++;
    sf2(id+1, r);
}
    
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n;
    for(int i = 0; i < n; ++i){
        int t1;
        cin >> t1;
        a[t1-1] = i;
        b[t1-1] = i;
    }
    sf1(0, n-1);
    sf2(0, n-1);
    cout << "end\n";
    vector<int> v1(n);
    vector<int> v2(n);
    
    for(int i = 0; i < n; ++i)
        v1[a[i]] = i+1;
    for(auto u : v1)
        cout << u << " ";
    cout << "\n";
    
    for(int i = 0; i < n; ++i)
        v1[b[i]] = i+1;
    for(auto u : v1)
        cout << u << " ";
}

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