Submission #114560

#	Time	Username	Problem	Language	Result	Execution time	Memory
114560		tincamatei	Minerals (JOI19_minerals)	C++14	6 / 100	42 ms	1024 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 43000;

struct Mineral {
	int st, dr, mid, id;
} v[2*MAX_N];

int p = 0; // All minerals from 0 to p are added
int lastrez = 0; // Result for minerals from 0 to p

void movePointer(int x) {
	while(p < x) {
		p++;
		lastrez = Query(p);
	}

	while(p > x) {
		lastrez = Query(p);
		p--;
	}
}

bool hasPair(int x) {
	bool frez;
	int rez = Query(x);
	if(rez == lastrez)
		frez = true;
	else
		frez = false;
	Query(x);
	return frez;
}

bool lefttoright = false;
bool cmp(Mineral a, Mineral b) {
	if(lefttoright)
		return a.mid < b.mid;
	else
		return a.mid > b.mid;
}

void Solve(int N) {
	for(int i = 0; i < 2 * N; ++i) {
		v[i].st = 0;
		v[i].dr = i + 1;
		v[i].id = i + 1;
	}
	
	int activeQueries = 0;
	for(int i = 0; i < 2 * N; ++i) {
		if(v[i].dr - v[i].st > 1)
			activeQueries++;
		v[i].mid = (v[i].st + v[i].dr) / 2;
	}
	
	while(activeQueries > 0) {
		sort(v, v + 2 * N, cmp);
		lefttoright ^= 1;
		
		for(int i = 0; i < 2 * N; ++i) {
			if(v[i].dr - v[i].st > 1) {
				movePointer(v[i].mid);
				if(hasPair(v[i].id))
					v[i].dr = v[i].mid;
				else
					v[i].st = v[i].mid;
			}
		}

		activeQueries = 0;
		for(int i = 0; i < 2 * N; ++i) {
			if(v[i].dr - v[i].st > 1)
				activeQueries++;
			v[i].mid = (v[i].st + v[i].dr) / 2;
		}
	}

	for(int i = 0; i < 2 * N; ++i)
		if(v[i].dr != v[i].id)
			Answer(v[i].id, v[i].dr);
}

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