oj.uz

답안 #439548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
439548 2021-06-30T08:34:35 Z 8e7 Monster Game (JOI21_monster) C++17
0 / 100
 147 ms 4400 KB 
#include "monster.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <time.h>
#include <random>

#define maxn 1005
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ";debug(b ...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
namespace {
	bool res[maxn][maxn];
	bool found[maxn][maxn];
	int num = 0, save = 0;
}  // namespace
bool que(int a, int b) {
	if (found[a][b]) return save++, res[a][b];
	bool ret = Query(a, b);
	found[a][b] = found[b][a] = 1;
	res[a][b] = ret, res[b][a] = ret ^ 1;
	num++;
	return ret;
}
void mergesort(vector<int> &v) {
	if (v.size() <= 1) {
		return;
	}
	vector<int> lef, rig;
	for (int i = 0;i < v.size();i++) {
		if (i < (v.size() / 2)) lef.push_back(v[i]);
		else rig.push_back(v[i]);
	}
	mergesort(lef), mergesort(rig);	
	vector<int> ret;
	int ind = 0;
	for (int i = 0;i < lef.size();i++) {
		while (ind < rig.size() && que(lef[i], rig[ind])) {
			ret.push_back(rig[ind]);
			ind++;
		}
		ret.push_back(lef[i]);
	}
	while (ind < rig.size()) ret.push_back(rig[ind++]);
	v = ret;
}

vector<int> Solve(int N) {
	vector<int> ret;
	vector<int> cand;
	for (int i = 0;i < N;i++) cand.push_back(i);
	mergesort(cand);
	//cout << num << endl;
	vector<pii> cur;
	bool done = 0;
	for (int i = N - 1;i >= 0;i--) {
		int loss = 0;	
		for (auto &j:cur) {
			if (que(cand[i], cand[j.ff])) j.ss++;
			else loss++;	
		}
		for (int j = cur.size() - 1;j >= 0;j--) {
			if (cur[j].ss > 1) {
				cur.erase(cur.begin() + j);		
			} else if (cur[j].ff > i + 2) {
				done = 1;
				break;
			}
		}
		if (done) break;
		if (loss < 2) cur.push_back({i, loss});
	}	
	//cout << num << " " << save << endl;
	int big;
	if (cur.size() == 1) big = cur[0].ff;
	else if (cur.size() == 2) {
		if (cur[0].ff == cur[1].ff + 1) big = cur[1].ff;
		else big = cur[0].ff;
	} else {
		big = cur[0].ff;
		for (int i = 0;i < 2;i++) {
			if (cur[i + 1].ff == cur[i].ff - 1) big = cur[i + 1].ff;
			else {
				break;
			}
		}
	}
	for (int i = big;i < N;i++) ret.push_back(cand[i]);
	int comp = N - 1;
	for (int i = big - 1;i >= 0;i--) {
		if (que(cand[i], cand[comp])) {
			for (int j = i;j < big;j++) ret.push_back(cand[j]);
			comp = big - 1, big = i;
		}
	}
	reverse(ret.begin(), ret.end());
	vector<int> a (N, 0);
	for (int i = 0;i < N;i++) a[ret[i]] = i;
	return a;
}
/*
5
3 1 4 2 0

8
7 3 4 2 1 5 6 0

10
0 2 8 3 9 4 6 7 5 1
*/

Compilation message

monster.cpp: In function 'void mergesort(std::vector<int>&)':
monster.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0;i < v.size();i++) {
      |                 ~~^~~~~~~~~~
monster.cpp:39:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   if (i < (v.size() / 2)) lef.push_back(v[i]);
      |       ~~^~~~~~~~~~~~~~~~
monster.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0;i < lef.size();i++) {
      |                 ~~^~~~~~~~~~~~
monster.cpp:46:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   while (ind < rig.size() && que(lef[i], rig[ind])) {
      |          ~~~~^~~~~~~~~~~~
monster.cpp:52:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  while (ind < rig.size()) ret.push_back(rig[ind++]);
      |         ~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Incorrect 1 ms 200 KB Wrong Answer [3]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Incorrect 1 ms 200 KB Wrong Answer [3]
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 2244 KB Output is correct
2 Correct 86 ms 2272 KB Output is correct
3 Correct 92 ms 2308 KB Output is correct
4 Correct 80 ms 2228 KB Output is correct
5 Correct 86 ms 2388 KB Output is correct
6 Correct 92 ms 2280 KB Output is correct
7 Correct 93 ms 2264 KB Output is correct
8 Correct 83 ms 2332 KB Output is correct
9 Runtime error 147 ms 4400 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -