oj.uz

Submission #114560

# Submission time Handle Problem Language Result Execution time Memory
114560 2019-06-01T18:36:38 Z tincamatei Minerals (JOI19_minerals) C++14
6 / 100
 42 ms 1024 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 10 ms 640 KB Output is correct
4 Correct 22 ms 888 KB Output is correct
5 Incorrect 42 ms 1024 KB Wrong Answer [2]

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 22 ms 888 KB Output is correct
9 Incorrect 42 ms 1024 KB Wrong Answer [2]

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 22 ms 888 KB Output is correct
9 Incorrect 42 ms 1024 KB Wrong Answer [2]

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 22 ms 888 KB Output is correct
9 Incorrect 42 ms 1024 KB Wrong Answer [2]

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 22 ms 888 KB Output is correct
9 Incorrect 42 ms 1024 KB Wrong Answer [2]

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 22 ms 888 KB Output is correct
9 Incorrect 42 ms 1024 KB Wrong Answer [2]

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 22 ms 888 KB Output is correct
9 Incorrect 42 ms 1024 KB Wrong Answer [2]

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 22 ms 888 KB Output is correct
9 Incorrect 42 ms 1024 KB Wrong Answer [2]