Submission #128793

#	Time	Username	Problem	Language	Result	Execution time	Memory
128793		roseanne_pcy	Minerals (JOI19_minerals)	C++14	70 / 100	54 ms	2692 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;

int last = 0;

int ask(int x)
{
	return Query(x);
}

int n;
vector<int> Left, Right;

int match[maxn];

void solve(int L, int M, int R, vector<int> vec)
{
	// printf("solving [%d %d]\n", L, R);
	// for(int i = 1; i< (int) vec.size(); i++) printf("%d ", vec[i]); printf("\n");
	if(L == R)
	{
		last = ask(Right[L]);
		match[vec[1]] = Right[L];
		return;
	}
	vector<int> v1, v2;
	v1.pb(0); v2.pb(0);
	// printf("last = %d\n", last);
	for(int x : vec)
	{
		if(!x) continue;
		int y = ask(x);
		// printf("go %d now %d\n", x, y);
		if(y == last) v1.pb(x);
		else v2.pb(x);
		last = y;
	}
	int M1 = (L+M)/2, M2 = (M+R)/2;
	for(int i = M1+1; i<= M; i++) last = ask(Right[i]);
	solve(L, M1, M, v1);
	for(int i = M+1; i<= M2; i++) last = ask(Right[i]);
	solve(M+1, M2, R, v2);
}

void Solve(int N)
{
	n = N;
	Left.pb(0); Right.pb(0);
	for(int i = 1; i<= 2*N; i++)
	{
		int x = ask(i);
		if(x != last) Left.pb(i);
		else Right.pb(i);
		last = x;
	}
	int M = (1+N)/2;
	for(int i = M+1; i<= N; i++)
	{
		// printf("rem %d\n", Right[i]);
		last = ask(Right[i]);
		// printf("now %d\n", last);
	}
	vector<int> trash;
	for(int i = 0; i<= N; i++) trash.pb(Left[i]);
	solve(1, M, N, trash);
	for(int i = 1; i<= 2*N; i++)
	{
		if(match[i])
		{
			// printf("match %d with %d\n", i, match[i]);
			Answer(i, match[i]);
		}
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10