oj.uz

Submission #261999

# Submission time Handle Problem Language Result Execution time Memory
261999 2020-08-12T09:03:48 Z patrikpavic2 Minerals (JOI19_minerals) C++17
6 / 100
 174 ms 1272 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);
		random_shuffle(v.begin() + i, v.begin() + j);
		random_shuffle(v.begin() + i, v.begin() + j);
		random_shuffle(v.begin() + i, v.begin() + j);
		random_shuffle(v.begin() + i, v.begin() + 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) {
	srand(69);
	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 sad = 1, pitaj = 2 * n;pitaj + 2 * n <= 1e6; pitaj += 2 * n, sad = !sad)
		probaj(sad);
	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 110 ms 256 KB Output is correct
2 Correct 119 ms 376 KB Output is correct
3 Correct 131 ms 380 KB Output is correct
4 Correct 129 ms 376 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 384 KB Output is correct
2 Correct 165 ms 504 KB Output is correct
3 Correct 174 ms 632 KB Output is correct
4 Correct 173 ms 768 KB Output is correct
5 Incorrect 169 ms 1272 KB Wrong Answer [5]

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 256 KB Output is correct
2 Correct 119 ms 376 KB Output is correct
3 Correct 131 ms 380 KB Output is correct
4 Correct 129 ms 376 KB Output is correct
5 Correct 150 ms 384 KB Output is correct
6 Correct 165 ms 504 KB Output is correct
7 Correct 174 ms 632 KB Output is correct
8 Correct 173 ms 768 KB Output is correct
9 Incorrect 169 ms 1272 KB Wrong Answer [5]

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 256 KB Output is correct
2 Correct 119 ms 376 KB Output is correct
3 Correct 131 ms 380 KB Output is correct
4 Correct 129 ms 376 KB Output is correct
5 Correct 150 ms 384 KB Output is correct
6 Correct 165 ms 504 KB Output is correct
7 Correct 174 ms 632 KB Output is correct
8 Correct 173 ms 768 KB Output is correct
9 Incorrect 169 ms 1272 KB Wrong Answer [5]

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 256 KB Output is correct
2 Correct 119 ms 376 KB Output is correct
3 Correct 131 ms 380 KB Output is correct
4 Correct 129 ms 376 KB Output is correct
5 Correct 150 ms 384 KB Output is correct
6 Correct 165 ms 504 KB Output is correct
7 Correct 174 ms 632 KB Output is correct
8 Correct 173 ms 768 KB Output is correct
9 Incorrect 169 ms 1272 KB Wrong Answer [5]

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 256 KB Output is correct
2 Correct 119 ms 376 KB Output is correct
3 Correct 131 ms 380 KB Output is correct
4 Correct 129 ms 376 KB Output is correct
5 Correct 150 ms 384 KB Output is correct
6 Correct 165 ms 504 KB Output is correct
7 Correct 174 ms 632 KB Output is correct
8 Correct 173 ms 768 KB Output is correct
9 Incorrect 169 ms 1272 KB Wrong Answer [5]

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 256 KB Output is correct
2 Correct 119 ms 376 KB Output is correct
3 Correct 131 ms 380 KB Output is correct
4 Correct 129 ms 376 KB Output is correct
5 Correct 150 ms 384 KB Output is correct
6 Correct 165 ms 504 KB Output is correct
7 Correct 174 ms 632 KB Output is correct
8 Correct 173 ms 768 KB Output is correct
9 Incorrect 169 ms 1272 KB Wrong Answer [5]

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 256 KB Output is correct
2 Correct 119 ms 376 KB Output is correct
3 Correct 131 ms 380 KB Output is correct
4 Correct 129 ms 376 KB Output is correct
5 Correct 150 ms 384 KB Output is correct
6 Correct 165 ms 504 KB Output is correct
7 Correct 174 ms 632 KB Output is correct
8 Correct 173 ms 768 KB Output is correct
9 Incorrect 169 ms 1272 KB Wrong Answer [5]

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 256 KB Output is correct
2 Correct 119 ms 376 KB Output is correct
3 Correct 131 ms 380 KB Output is correct
4 Correct 129 ms 376 KB Output is correct
5 Correct 150 ms 384 KB Output is correct
6 Correct 165 ms 504 KB Output is correct
7 Correct 174 ms 632 KB Output is correct
8 Correct 173 ms 768 KB Output is correct
9 Incorrect 169 ms 1272 KB Wrong Answer [5]