Submission #261996

#	Time	Username	Problem	Language	Result	Execution time	Memory
261996		patrikpavic2	Minerals (JOI19_minerals)	C++17	6 / 100	108 ms	768 KiB

minerals

#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 / 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