oj.uz

Submission #423731

# Submission time Handle Problem Language Result Execution time Memory
423731 2021-06-11T12:02:58 Z patrikpavic2 Monster Game (JOI21_monster) C++17
0 / 100
 102 ms 200 KB 
#include "monster.h"
#include <vector>
#include <cstdio>
#include <ctime>
#include <algorithm>
#include <unistd.h>

#define PB push_back

using namespace std;

typedef vector < int > vi;

namespace {

bool example_variable;

void merge_sort(vi &v){
	if((int)v.size() <= 1) return;
	vi A[2];
	for(int i = 0;i < (int)v.size();i++)
		A[i & 1].PB(v[i]);
	merge_sort(A[0]); merge_sort(A[1]);
	v.clear();
	int i = 0, j = 0;
	for(;i < (int)A[0].size() || j < (int)A[1].size();){
		if(i == (int)A[0].size()) v.PB(A[1][j++]);
		else if(j == (int)A[1].size()) v.PB(A[0][i++]); 
		else if(!Query(A[0][i], A[1][j])) v.PB(A[0][i++]);
		else v.PB(A[1][j++]);
	}
}

}  // namespace

vi Solve(int n) {
	vi v, ret(n); 
	for(int i = 0;i < n;i++)
		v.PB(i);
	merge_sort(v);
	int pref = 0, cnt = 0;
	for(int i = 1;i < n;i++)
		cnt += Query(v[0], v[i]);
	if(cnt == 1){
		int cnt2 = 0;
		for(int i = 2;i < n;i++)
			cnt2 += Query(v[1], v[i]);
		if(cnt2 == 0)
			pref = 1;
		else
			pref = 0;
	}
	else
		pref = cnt;
	int lst = pref;
	reverse(v.begin(), v.begin() + pref + 1);
	for(int i = lst + 1;i < n;i++){
		while(i < (int)v.size() && !Query(v[lst], v[i]))
			i++;
		reverse(v.begin() + lst + 1, v.begin() + i + 1);
		lst = i;
	}	
	for(int i = 0;i < n;i++)
		ret[v[i]] = i;
	return v;
}

Compilation message

monster.cpp:16:6: warning: '{anonymous}::example_variable' defined but not used [-Wunused-variable]
   16 | bool example_variable;
      |      ^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Incorrect 0 ms 200 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Incorrect 0 ms 200 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

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