제출 #1226647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226647		ssafarov	Minerals (JOI19_minerals)	C++20	80 / 100	22 ms	3936 KiB

minerals

#define Magic ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "minerals.h"
#define ll int
#define ld long long double
#define en '\n'
#define tsts int tetss; cin >> tetss; while(tetss--)
#define all(a) a.begin() , a.end()
#define pb push_back
#define ld long long double
#define fi first
#define se second

using namespace std;

int lst;
int op[100000] = {};
int ps[100000] = {};

void func(vector<int> v, bool ok){
	// cout << lst << " " << ok << en;
	// for(auto g : v) cout << g << " ";
	// cout << en;
	vector<int> v1, v2;
	int st = lst;
	int gps = v.size() / 2;
	if(v.size() == 2){
		Answer(v[0], v[1]);
		return;
	}
	if(ok){
		int sb = (gps + 1) / 2;
		for(auto g : v){
			int nw = lst;
			if(op[g]){
				if(sb){
					v1.push_back(g);
					sb--;
				}else{
					v2.push_back(g);
					nw = Query(g);
					ps[g] ^= 1;
				}
			}else{
				nw = Query(g);
				if(ps[g]){
					if(nw == lst){
						v1.push_back(g);
					}else{
						v2.push_back(g);
					}
				}else{
					if(nw != lst){
						v1.push_back(g);
					}else{
						v2.push_back(g);
					}
				}
				ps[g] ^= 1;
			}
			lst = nw;
		}
	}else{
		int sb = (gps + 1) / 2;
		for(auto g : v){
			int nw = lst;
			if(op[g]){
				if(sb){
					v1.push_back(g);
					sb--;
				}else{
					v2.push_back(g);
					nw = Query(g);
					ps[g] ^= 1;
				}
			}else{
				nw = Query(g);
				if(ps[v[0]]){
					if(nw == lst){
						v1.push_back(g);
					}else{
						v2.push_back(g);
					}
				}else{
					if(nw != lst){
						v1.push_back(g);
					}else{
						v2.push_back(g);
					}
				}
				ps[g] ^= 1;
			}
			lst = nw;
		}
	}
	func(v1, !ok);
	func(v2, ok);
}

void Solve(int n){
	for(int i = 1; i <= 2 * n; ++i){
		int nw = Query(i);
		ps[i] = 1;
		if(nw != lst) op[i] = 1;
		lst = nw;
	}
	vector<int> v;
	for(int i = 1; i <= 2 * n; ++i){
		v.push_back(i);
	}
	func(v, 1);
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10