oj.uz

Submission #447241

# Submission time Handle Problem Language Result Execution time Memory
447241 2021-07-25T10:47:58 Z jwvg0425 Chameleon's Love (JOI20_chameleon) C++17
24 / 100
 63 ms 456 KB 
#include "chameleon.h"
#include <assert.h>
#include <vector>

using namespace std;

vector<int> con[1005];
bool visit[1005];
bool answered[1005];
int l[1005];

vector<int> xs;
vector<int> ys;

int Query(int x, int s, int e)
{
	vector<int> v = { xs[x] };
	for (int i = s; i <= e; i++)
		v.push_back(ys[i]);

	return Query(v);
}

int Bisearch(int x, int l, int r, int d)
{
	int lo = l, hi = r;
	int res = 0;

	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		int q = Query(x, l, mid);
		int sz = mid - l + 2;
		if (q <= sz + d)
		{
			res = mid;
			hi = mid - 1;
		}
		else
		{
			lo = mid + 1;
		}
	}

	return res;
}

void Solve(int N)
{
	for (int i = 1; i <= 2 * N; i++)
	{
		xs.push_back(i);
		if (Query(xs) != xs.size())
		{
			xs.pop_back();
			ys.push_back(i);
		}
	}

	xs.insert(xs.begin(), 0);
	ys.insert(ys.begin(), 0);
	assert(xs.size() == ys.size());

	for (int i = 1; i <= N; i++)
	{
		if (Query(i, 1, N) == N)
		{
			auto x = Bisearch(i, 1, N, -1);
			con[xs[i]] = { ys[x] };
			con[ys[x]].push_back(xs[i]);
			continue;
		}

		auto b = Bisearch(i, 1, N, -2);
		auto a = Bisearch(i, 1, b - 1, -1);
		con[ys[a]].push_back(xs[i]);
		con[ys[b]].push_back(xs[i]);
		if (Query(i, 1, a - 1) != a)
		{
			auto c = Bisearch(i, 1, a - 1, -1);
			con[xs[i]] = { ys[a], ys[b], ys[c] };
			con[ys[c]].push_back(xs[i]);
		}
		else if (Query(i, a + 1, b - 1) != b - a)
		{
			auto c = Bisearch(i, a + 1, b - 1, -1);
			con[xs[i]] = { ys[a], ys[b], ys[c] };
			con[ys[c]].push_back(xs[i]);
		}
		else
		{
			auto c = Bisearch(i, b + 1, N, -1);
			con[xs[i]] = { ys[a], ys[b], ys[c] };
			con[ys[c]].push_back(xs[i]);
		}
	}

	for (int i = 1; i <= 2 * N; i++)
	{
		if (visit[i])
			continue;

		if (con[i].size() == 1)
		{
			Answer(i, con[i][0]);
			visit[i] = visit[con[i][0]] = true;
			answered[i] = answered[con[i][0]] = true;
			continue;
		}

		if (con[con[i][0]].size() == 1)
		{
			Answer(i, con[i][0]);
			visit[i] = visit[con[i][0]] = true;
			answered[i] = answered[con[i][0]] = true;
		}
		else if (con[con[i][1]].size() == 1)
		{
			Answer(i, con[i][1]);
			visit[i] = visit[con[i][1]] = true;
			answered[i] = answered[con[i][1]] = true;
		}
		else if (con[con[i][2]].size() == 1)
		{
			Answer(i, con[i][2]);
			visit[i] = visit[con[i][2]] = true;
			answered[i] = answered[con[i][2]] = true;
		}
		else
		{
			vector<int> a = { i, con[i][0], con[i][1] };
			vector<int> b = { i, con[i][0], con[i][2] };
			vector<int> c = { i, con[i][1], con[i][2] };

			auto aq = Query(a);
			auto bq = Query(b);

			if (aq == 1)
			{
				visit[i] = true;
				l[i] = con[i][2];
			}
			else if (bq == 1)
			{
				visit[i] = true;
				l[i] = con[i][1];
			}
			else
			{
				visit[i] = true;
				l[i] = con[i][0];
			}
		}
	}

	for (int i = 1; i <= 2 * N; i++)
	{
		if (answered[i])
			continue;

		for (auto& c : con[i])
		{
			if (c == l[i] || l[c] == i || answered[c])
				continue;

			Answer(i, c);
			answered[i] = answered[c] = true;
			break;
		}
	}
}

Compilation message

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   if (Query(xs) != xs.size())
      |       ~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 29 ms 328 KB Output is correct
4 Correct 34 ms 336 KB Output is correct
5 Correct 29 ms 328 KB Output is correct
6 Correct 29 ms 328 KB Output is correct
7 Correct 29 ms 336 KB Output is correct
8 Correct 29 ms 328 KB Output is correct
9 Correct 29 ms 340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Runtime error 1 ms 456 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Runtime error 1 ms 456 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 61 ms 336 KB Output is correct
4 Correct 58 ms 332 KB Output is correct
5 Correct 57 ms 328 KB Output is correct
6 Correct 58 ms 344 KB Output is correct
7 Correct 57 ms 328 KB Output is correct
8 Correct 58 ms 340 KB Output is correct
9 Correct 63 ms 332 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 29 ms 328 KB Output is correct
4 Correct 34 ms 336 KB Output is correct
5 Correct 29 ms 328 KB Output is correct
6 Correct 29 ms 328 KB Output is correct
7 Correct 29 ms 336 KB Output is correct
8 Correct 29 ms 328 KB Output is correct
9 Correct 29 ms 340 KB Output is correct
10 Correct 0 ms 200 KB Output is correct
11 Correct 0 ms 200 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Runtime error 1 ms 456 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -