Submission #232901

#	Time	Username	Problem	Language	Result	Execution time	Memory
232901		shayan_p	Zagonetka (COI18_zagonetka)	C++14	100 / 100	29 ms	512 KiB

zagonetka

// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int n;
int arr[maxn], a[maxn];

bool ask(vector<int> a, bool rev = 0){
    if(rev)
	reverse(a.begin(), a.end());
    for(int i = 0; i < n; i++)
	arr[a[i]] = i;
    cout << "query ";
    for(int i = 0; i < n; i++)
	cout << arr[i]+1 << " ";
    cout << endl;
    bool x;
    cin >> x;
    return x;
}
vector<int> input(){
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
	int x;
	cin >> x;
	--x;
	v[x] = i;
    }
    return v;
}
vector<int> shiftr(vector<int> v, int pos, int k){
    for(int i = 0; i < k; i++){
	if(pos == n-1)
	    break;
	swap(v[pos], v[pos+1]);
	pos++;
    }
    return v;
}
vector<int> shiftl(vector<int> v, int pos, int k){
    for(int i = 0; i < k; i++){
	if(pos == 0)
	    break;
	swap(v[pos-1], v[pos]);
	pos--;
    }
    return v;
}
void print(vector<int> a){
    for(int i = 0; i < n; i++)
	arr[a[i]] = i;
    for(int i = 0; i < n; i++)
	cout << arr[i]+1 << " ";
    cout << endl;
}

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

    vector<int> v = input();
    vector<int> ans1 = v, ans2 = v;

    for(int i = 0; i < n; i++){
	int l = 0, r = i+1;
	while(r-l > 1){
	    int mid = (l+r) >> 1;
	    if(ask(shiftl(ans1, i, mid)))
		l = mid;
	    else
		r = mid;
	}
	int SZ = i-l, pt = i;
	for(int j = i-1; j >= SZ; j--)
	    if(ans1[j] < ans1[i])
		pt = j;
	ans1 = shiftl(ans1, i, i-pt);
    }
    reverse(ans2.begin(), ans2.end());
    for(int i = 0; i < n; i++){
	int l = 0, r = i+1;
	while(r-l > 1){
	    int mid = (l+r) >> 1;
	    if(ask(shiftl(ans2, i, mid), 1))
		l = mid;
	    else
		r = mid;
	}
	int SZ = i-l, pt = i;
	for(int j = i-1; j >= SZ; j--)
	    if(ans2[j] < ans2[i])
		pt = j;
	ans2 = shiftl(ans2, i, i-pt);
    }
    
    cout << "end" << endl;
    reverse(ans2.begin(), ans2.end());
    print(ans2);
    print(ans1);
    return 0;
}

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