oj.uz

답안 #109203

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109203 2019-05-05T13:43:20 Z tjd229 통행이 제한된 저택 (FXCUP3_key) C++14
0 / 100
 2 ms 640 KB 
#include "key.h"
#include <vector>
#include <algorithm>
#define pii pair<int,int>
using namespace std;
int in[1001],vis[1001];
vector<int> v[1001];
void EnsureKeyInfo(int N) {
	int i,t=0;
	vector<int> hist[2];
	for (i = 1; i <= N; ++i) {
		TakeKey(i);
		int cnt = Explore();
		v[cnt].push_back(i);
	}
	for (auto x : v[1]) in[x] = x,hist[0].push_back(x);
	for (i = 2; i <= N; ++i) {//i=lev
		vector<int> cyc;
		for(auto x:v[i]){
			int l = 0, r = hist[t].size() - 1;
			int p = -1;
			while (l <= r) {
				int m = (l+r)>>1;
				int pred = 0;
				for (int j = l; j <= m; ++j) TakeKey(hist[t][j]),pred+=i-1;
				TakeKey(x);
				int cnt = Explore();
				if (cnt - pred == 1) p = m, r = m - 1;
				else l = m + 1;
				/*if (cnt - pred == 2) l = m + 1;
				else  p=m,r = m - 1;*/
				
			}
			if (p < 0) cyc.push_back(x);
			else {
				in[x] = hist[t][p];
				hist[1-t].push_back(x);
			}
		}
		
		vector<int> meta;
		int root[1001] = { 0 };
		for (int j = 0; j < cyc.size(); ++j) {
			if (!j) meta.push_back(cyc[j]);
			else {
				int l = 0, r = meta.size() - 1;
				int p = -1;
				while (l <= r) {
					int m = (l + r) >> 1;
					int pred = 0;
					for (int k = l; k <= m; ++k) TakeKey(meta[k]),pred+=i;
					TakeKey(cyc[j]);
					int cnt = Explore();
					if (cnt == pred) p = m, r = m - 1;
					else l = m + 1;
				}
				if (p < 0) meta.push_back(cyc[j]);
				else {
					in[cyc[j]] = meta[p];
					if (!root[p]) root[p] = meta[p];
					meta[p] = cyc[j];
				}
			}
		}
		for (int j = 0; j < meta.size(); ++j) {
			in[root[j]] = meta[j];
			hist[1 - t].push_back(meta[j]);
		}
		hist[t].clear();
		t = 1 - t;
		//tog
	}
	
	for (i = 1; i <= N; ++i) {
		int x = i;
		while (i!=vis[x]) {
			Report(i, x); vis[x] = i;
			x = in[x];
		}
	}
}

Compilation message

key.cpp: In function 'void EnsureKeyInfo(int)':
key.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < cyc.size(); ++j) {
                   ~~^~~~~~~~~~~~
key.cpp:65:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < meta.size(); ++j) {
                   ~~^~~~~~~~~~~~~

Subtask #1
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Runtime error 2 ms 640 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Runtime error 2 ms 640 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Runtime error 2 ms 640 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -