oj.uz

Submission #168017

# Submission time Handle Problem Language Result Execution time Memory
168017 2019-12-11T07:31:33 Z egekabas Zagonetka (COI18_zagonetka) C++14
0 / 100
 12 ms 248 KB 
#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 dp[109][109];
int q(int idx, int put, int a[]){
    if(dp[idx][put] != -1)
        return dp[idx][put];
    cout << "query ";
    for(int i = 0; i < put; ++i){
        if(i == idx) continue;
        cout << a[i] << " ";
    }
    cout << a[idx] << " ";
    for(int i = put; i < n; ++i){
        if(i == idx) continue;
        cout << a[i] << " ";    
    }
    cout << endl;
    cin >> dp[idx][put];
    return dp[idx][put];
}
void put(int cur, int tar, int a[]){
    while(tar < cur){
        swap(a[cur], a[cur-1]);
        --cur;
    }
    while(tar > cur){
        swap(a[cur], a[cur+1]);
        ++cur;
    }
}
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(int i = id-1; i >= l; --i){
        if(q(id, i, a) == 0){
            put(id, i+1, a);
            id = i+1;
            goto END;
        }
    }
    put(id, l, a);    
    id = l;
    END:;
    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(int i = id-1; i >= l; --i){
        if(q(id, i, b) == 0){
            put(id, i+1, b);
            id = i+1;
            goto END;
        }
    }
    put(id, l, b);    
    id = l;
    END:;
    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){
        cin >> a[i];
        b[i] = a[i];
    }
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= n; ++j)
            dp[i][j] = -1;
    sf1(0, n-1);
    sf2(0, n-1);
    cout << "end\n";
    for(int i = 0; i < n; ++i)
        cout << a[i] << " ";
    cout << "\n";

    for(int i = 0; i < n; ++i)
        cout << b[i] << " ";
    cout << "\n";
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Incorrect 2 ms 248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 51.0

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