Submission #72894

#	Time	Username	Problem	Language	Result	Execution time	Memory
72894		ainta	Key of Impassable Doors (FXCUP3_key)	C++17	100 / 100	39 ms	7172 KiB

key

#include "key.h"
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>G[1010];
vector<int>U[1010], B[1010], V[1010];
 
int S[1010][1010], Nxt[1010], vis[1010], isU[1010];
 
int Num[1010], D[1010];
vector<int>T[1010];
 
void Go(int i, int x) {
	if (U[i].empty()) {
		U[i].push_back(x);
		return;
	}
	int b = 1, e = U[i].size(), mid, r = 0, j;
	while (b <= e) {
		mid = (b + e) >> 1;
		for (j = 0; j < mid; j++) {
			TakeKey(U[i][j]);
		}
		TakeKey(x);
		if (Explore() == i * (mid + 1)) {
			r = mid;
			b = mid + 1;
		}
		else e = mid - 1;
	}
	if (r == U[i].size()) {
		U[i].push_back(x);
	}
	else {
		Num[x] = U[i][r];
	}
}
 
void TakeAll(int b, int e) {
	int i;
	for (i = b; i <= e; i++) {
		for (auto &x : V[i])TakeKey(x);
	}
}
 
void EnsureKeyInfo(int N) {
	int i, j, k;
	for (i = 1; i <= N; i++) {
		TakeKey(i);
		int t = Explore();
		G[t].push_back(i);
	}
	int Mn = -1;
	for (i = 1; i <= N; i++) {
		if (G[i].empty()) {
			D[i] = D[i - 1];
			continue;
		}
		if (Mn == -1) {
			Mn = i;
			for (auto &x : G[i]) {
				Go(i, x);
			}
		}
		else {
			for (auto &x : G[i]) {
				TakeAll(1, i - 1);
				TakeKey(x);
				if (Explore() == D[i - 1] + i) {
					Go(i, x);
					continue;
				}
 
				int b = 1, e = V[i - 1].size() - 1, r = V[i - 1].size(), mid;
				while (b <= e) {
					mid = (b + e) >> 1;
					TakeAll(1, i - 2);
					for (j = 0; j < mid; j++) {
						TakeKey(V[i - 1][j]);
					}
					TakeKey(x);
					int t = Explore();
					if (S[i - 1][mid] + 1 == t) {
						r = mid;
						e = mid - 1;
					}
					else b = mid + 1;
				}
 
				Nxt[x] = V[i - 1][r - 1];
				B[i].push_back(x);
			}
		}
		for (auto &x : U[i]) {
			V[i].push_back(x);
			isU[x] = 1;
		}
		for (auto &x : B[i])V[i].push_back(x);
		for (j = 0; j <= V[i].size(); j++) {
			if (j == 0) {
				if (Mn == i)S[i][j] = 0;
				else S[i][j] = D[i - 1];
				continue;
			}
			else {
				int x = V[i][j - 1];
				if (isU[x]) S[i][j] = S[i][j - 1] + i;
				else S[i][j] = S[i][j - 1] + 1;
			}
		}
		D[i] = S[i][V[i].size()];
	}
 
	for (i = 1; i <= N; i++)for (auto &x : U[i])Num[x] = x;
 
 
	for (i = 1; i <= N; i++) {
		if (Num[i]) {
			for (j = 1; j <= N; j++) {
				if (Num[j] == Num[i])Report(i, j);
			}
			continue;
		}
		else {
			for (j = 1; j <= N; j++)vis[j] = 0;
			int x = i;
			while (x) {
				vis[x] = 1;
				x = Nxt[x];
			}
			for (j = 1; j <= N; j++) {
				if (vis[j] || vis[Num[j]])Report(i, j);
			}
		}
 
	}
 
}

Compilation message (stderr)

key.cpp: In function 'void Go(int, int)':
key.cpp:32:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (r == U[i].size()) {
      ~~^~~~~~~~~~~~~~
key.cpp: In function 'void EnsureKeyInfo(int)':
key.cpp:100:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j <= V[i].size(); j++) {
               ~~^~~~~~~~~~~~~~
key.cpp:48:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^

• Subtask 1: 23 / 23
• Subtask 2: 34 / 34
• Subtask 3: 43 / 43