Submission #1159235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159235		dibamboo23	The Potion of Great Power (CEOI20_potion)	C++20	38 / 100	1961 ms	4356 KiB

potion

#include <bits/stdc++.h>

using namespace std;

#define sz size()

const int N=(int)1e5+3;

int h[N],a[N],b[N];
int cnt[N],cnt1[N];
int n,d;
int m;

void init(int N, int D, int H[]) {
	n=N;
	d=D;
	for(int i=0;i<N;i++)h[i]=H[i];
}

void curseChanges(int U, int A[], int B[]) {
	m=U;
	for(int i=0;i<m;i++)a[i]=A[i],b[i]=B[i];
}

int question(int x, int y, int v) {
	// cerr<<x<<" "<<y<<" "<<v<<"\n";
	for(int i=0;i<v;i++){
		if(a[i]==x)cnt[b[i]]^=1;
		else if(b[i]==x)cnt[a[i]]^=1;
		
		if(a[i]==y)cnt1[b[i]]^=1;
		else if(b[i]==y)cnt1[a[i]]^=1;
	}
	vector<int>vec,vec1;
	for(int i=0;i<v;i++){
		if(cnt[a[i]]==1){
			vec.push_back(h[a[i]]);
			cnt[a[i]]=0;
		}
		if(cnt[b[i]]==1){
			vec.push_back(h[b[i]]);
			cnt[b[i]]=0;
		}
		
		if(cnt1[a[i]]==1){
			vec1.push_back(h[a[i]]);
			cnt1[a[i]]=0;
		}
		if(cnt1[b[i]]==1){
			vec1.push_back(h[b[i]]);
			cnt1[b[i]]=0;
		}
	}
	if(vec.empty()||vec1.empty())return (int)1e9;
	sort(vec.begin(),vec.end());
	sort(vec1.begin(),vec1.end());
	// for(auto to:vec1)cout<<to<<" ";
	// cout<<"\n";
	// for(auto to:vec)cout<<to<<" ";
	// cout<<"\n";
	int mn=(int)1e9;
	int j=0;
	for(auto to:vec){
		while(j<(int)vec1.sz-1&&vec1[j]<to)j++;
		mn=min(mn,abs(vec1[j]-to));
		if(j>0)mn=min(mn,abs(to-vec1[j-1]));
	}
	return mn;
}

// int main() {
  // int N, D, U, Q;
  // std::ios::sync_with_stdio(false); std::cin.tie(NULL);
  // std::cin >> N >> D >> U >> Q;
// 
  // int *F = new int[N];
  // for (int i=0; i<N; i++)
    // std::cin >> F[i];
  // init(N, D, F);
// 
  // int *A = new int[U], *B = new int[U];
  // for (int i=0; i<U; i++) {
    // std::cin >> A[i] >> B[i];
  // }
  // curseChanges(U, A, B);
// 
  // bool correct = true;
  // for (int i=0; i<Q; i++) {
    // int X,Y,V,CorrectAnswer;
    // std::cin >> X >> Y >> V >> CorrectAnswer;
    // int YourAnswer = question(X,Y,V);
    // if (YourAnswer != CorrectAnswer) {
      // std::cout << "WA! Question: " << i
		// << " (X=" << X << ", Y=" << Y << ", V=" << V << ") "
		// <<  "Your answer: " << YourAnswer
                // << " Correct Answer: " << CorrectAnswer << std::endl;
      // correct = false;
    // } else {
      // std::cerr << YourAnswer << " - OK" << std::endl;
    // }
  // }
// 
  // if (correct) {
    // std::cout << "Correct." << std::endl;
  // } else std::cout << "Incorrect." << std::endl;
  // return 0;
// }

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 30