oj.uz

답안 #232898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232898 2020-05-18T15:54:26 Z shayan_p Zagonetka (COI18_zagonetka) C++14
0 / 100
 7 ms 512 KB 
// 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;
	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;
    print(ans1);
    reverse(ans2.begin(), ans2.end());
    print(ans2);
    return 0;
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 384 KB not a permutation
2 Halted 0 ms 0 KB -