oj.uz

Submission #1061222

# Submission time Handle Problem Language Result Execution time Memory
1061222 2024-08-16T07:21:43 Z ttamx Monster Game (JOI21_monster) C++17
0 / 100
 72 ms 592 KB 
#include "monster.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> Solve(int n){
	vector<int> a(n),b(n);
	function<void(int,int)> msort=[&](int l,int r){
		if(l==r)return;
		int m=(l+r)/2;
		msort(l,m);
		msort(m+1,r);
		for(int i=l,j=m+1,p=l;p<=r;p++){
			if(j>r||(i<=m&&!Query(a[i],a[j]))){
				b[p]=a[i++];
			}else{
				b[p]=a[j++];
			}
		}
		for(int i=l;i<=r;i++)a[i]=b[i];
	};
	iota(a.begin(),a.end(),0);
	msort(0,n-1);
	int st=-1;
	if(Query(a[1],a[0])){
		st=1;
		for(int i=2;i<n;i++){
			if(Query(a[1],a[i])){
				st=-1;
				break;
			}
		}
	}
	if(st==-1){
		st=2;
		while(st<n&&(Query(a[st-1],a[st])||Query(a[st],a[0]))){
			st++;
		}
	}
	if(st==n)st=0;
	reverse(a.begin(),a.begin()+st+1);
	for(int i=st+1;i<n;i++){
		int j=i;
		while(!Query(a[i-1],a[j])){
			j++;
			assert(j<n);
		}
		reverse(a.begin()+i,a.begin()+j+1);
		i=j;
	}
	vector<int> ans(n);
	for(int i=0;i<n;i++)ans[a[i]]=i;
	return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 72 ms 420 KB Partially correct
2 Partially correct 48 ms 592 KB Partially correct
3 Partially correct 53 ms 340 KB Partially correct
4 Partially correct 45 ms 424 KB Partially correct
5 Partially correct 51 ms 344 KB Partially correct
6 Correct 48 ms 420 KB Output is correct
7 Correct 39 ms 420 KB Output is correct
8 Partially correct 62 ms 420 KB Partially correct
9 Runtime error 48 ms 592 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -