제출 #20629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20629		khsoo01	Unscrambling a Messy Bug (IOI16_messy)	C++11	100 / 100	5 ms	640 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
int n;

void Add (int S, int E) {
	if(S>=E) return;
	int mid = (S+E)/2;
	for(int k = S; k <= mid; k++) {
		string ret = "";
		for(int i = 0; i < n; i++) {
			if(i < S || i > E || i == k) ret += '1';
			else ret += '0';
		}
		add_element(ret);
	}
	Add(S, mid); Add(mid+1, E);
}

vector<int> Solve (vector<int> C) {
	vector<int> va, vb, a, b;
	if(C.size() == 1) {
		a.push_back(C[0]);
		return a;
	}
	string tmp = "";
	for(int i=0;i<n;i++) tmp += '1';
	for(int i=0;i<C.size();i++) tmp[C[i]] = '0';
	for(int i=0;i<C.size();i++) {
		tmp[C[i]] = '1';
		if(check_element(tmp)) va.push_back(C[i]);
		else vb.push_back(C[i]);
		tmp[C[i]] = '0';
	}
	a = Solve(va); b = Solve(vb);
	for(int i=0;i<b.size();i++) a.push_back(b[i]);
	return a;
}


std::vector<int> restore_permutation(int N, int W, int R) {
	n = N;
    Add(0, n-1);
    compile_set();
    vector<int> cand, ans;
    for(int i=0;i<n;i++) {
		cand.push_back(i);
    }
    vector<int> tmp = Solve(cand);
    for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(tmp[j] == i) {ans.push_back(j); break;}
		}
    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

messy.cpp: In function 'std::vector<int> Solve(std::vector<int>)':
messy.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<C.size();i++) tmp[C[i]] = '0';
              ~^~~~~~~~~
messy.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<C.size();i++) {
              ~^~~~~~~~~
messy.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b.size();i++) a.push_back(b[i]);
              ~^~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30