oj.uz

Submission #261996

# Submission time Handle Problem Language Result Execution time Memory
261996 2020-08-12T09:00:56 Z patrikpavic2 Minerals (JOI19_minerals) C++17
6 / 100
 108 ms 768 KB 
#include "minerals.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;

const int N = 1e5 + 500;
const int MOD = 1e9 + 7;

inline int add(int A, int B){
	if(A + B >= MOD) 
		return A + B - MOD;
	return A + B;
}

inline int mul(int A, int B){
	return (ll)A * B % MOD;
}

int lo[N], hi[N], p[N], h[N], n;
vector < int > v;

bool cmp(int x, int y){
	return h[x] < h[y];
}

void probaj(int tip){
	sort(v.begin(), v.end(), cmp);
	for(int i = 0;i < 2 * n;){
		int j = i;
		while(j < 2 * n && h[v[i]] == h[v[j]])
			j++;
		random_shuffle(v.begin() + i, v.begin() + j);
		i = j;
	}
	int lst = tip * n;
	for(int i = 0;i < 2 * n;i++){
		int nw = Query(v[i]);
		h[v[i]] = add(mul(2, h[v[i]]), abs(nw - lst) ^ p[v[i]]);
		lst = nw;
	}
}

void Solve(int nn) {
	n = nn;
	int lst = 0;
	for(int i = 1;i <= 2 * n;i++){
		int nw = Query(i);
		p[i] = nw - lst; 
		v.PB(i);	
		lst = nw;
	}
	for(int i = 0;i + 1 < (1e6 / (2 * n));i++)
		probaj((i + 1) & 1);
	sort(v.begin(), v.end(), cmp);
	for(int i = 0;i < n;i++){
	//	printf("%d %d : %d %d\n", v[2 * i], v[2 * i + 1], h[v[2 * i]], h[v[2 * i + 1]]);
		Answer(v[2 * i], v[2 * i + 1]);
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 376 KB Output is correct
2 Correct 48 ms 368 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 74 ms 376 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 384 KB Output is correct
2 Correct 100 ms 384 KB Output is correct
3 Correct 108 ms 632 KB Output is correct
4 Incorrect 108 ms 768 KB Wrong Answer [2]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 376 KB Output is correct
2 Correct 48 ms 368 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 74 ms 376 KB Output is correct
5 Correct 98 ms 384 KB Output is correct
6 Correct 100 ms 384 KB Output is correct
7 Correct 108 ms 632 KB Output is correct
8 Incorrect 108 ms 768 KB Wrong Answer [2]
9 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 376 KB Output is correct
2 Correct 48 ms 368 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 74 ms 376 KB Output is correct
5 Correct 98 ms 384 KB Output is correct
6 Correct 100 ms 384 KB Output is correct
7 Correct 108 ms 632 KB Output is correct
8 Incorrect 108 ms 768 KB Wrong Answer [2]
9 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 376 KB Output is correct
2 Correct 48 ms 368 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 74 ms 376 KB Output is correct
5 Correct 98 ms 384 KB Output is correct
6 Correct 100 ms 384 KB Output is correct
7 Correct 108 ms 632 KB Output is correct
8 Incorrect 108 ms 768 KB Wrong Answer [2]
9 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 376 KB Output is correct
2 Correct 48 ms 368 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 74 ms 376 KB Output is correct
5 Correct 98 ms 384 KB Output is correct
6 Correct 100 ms 384 KB Output is correct
7 Correct 108 ms 632 KB Output is correct
8 Incorrect 108 ms 768 KB Wrong Answer [2]
9 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 376 KB Output is correct
2 Correct 48 ms 368 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 74 ms 376 KB Output is correct
5 Correct 98 ms 384 KB Output is correct
6 Correct 100 ms 384 KB Output is correct
7 Correct 108 ms 632 KB Output is correct
8 Incorrect 108 ms 768 KB Wrong Answer [2]
9 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 376 KB Output is correct
2 Correct 48 ms 368 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 74 ms 376 KB Output is correct
5 Correct 98 ms 384 KB Output is correct
6 Correct 100 ms 384 KB Output is correct
7 Correct 108 ms 632 KB Output is correct
8 Incorrect 108 ms 768 KB Wrong Answer [2]
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 376 KB Output is correct
2 Correct 48 ms 368 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 74 ms 376 KB Output is correct
5 Correct 98 ms 384 KB Output is correct
6 Correct 100 ms 384 KB Output is correct
7 Correct 108 ms 632 KB Output is correct
8 Incorrect 108 ms 768 KB Wrong Answer [2]
9 Halted 0 ms 0 KB -