Submission #77109

#	Time	Username	Problem	Language	Result	Execution time	Memory
77109		shoemakerjo	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	5 ms	640 KiB

messy

#include <bits/stdc++.h>

using namespace std;

#include "messy.h"

// add_element("0");
//     compile_set();
//     check_element("0");

bool isin[130];
int p[130];

int N;

void addstuff(vector<int> indos) {
	fill(isin, isin+130, false);
	for (int vv : indos) isin[vv] = true;
	if (indos.size() == 1) return;
	for (int i = 0; i < indos.size()/2; i++) {
		string s = "";
		for (int j = 0; j < N; j++) {
			if (isin[j] && j != indos[i]) {
				s += "1";
			}
			else s += "0";
		}
		add_element(s);
	}

	vector<int> lh, rh;
	for (int i = 0; i < indos.size()/2; i++) {
		lh.push_back(indos[i]);
		rh.push_back(indos[i+indos.size()/2]);
	}
	addstuff(lh);
	addstuff(rh);
}

void decode(vector<int> indos, vector<int> ots) {
	//deccide if in first half
	fill(isin, isin+130, false);
	for (int vv : ots) isin[vv] = true;
	if (indos.size() == 1) {
		p[ots[0]] = indos[0];
		return;
	}
	vector<int> firsthalf;
	vector<int> secondhalf;
	for (int i = 0; i < ots.size(); i++) {
		string s = "";
		for (int j = 0; j < N; j++) {
			if (isin[j] && j != ots[i]) {
				s += "1";
			}
			else s += "0";
		}
		if (check_element(s)) {
			firsthalf.push_back(ots[i]);
		}
		else secondhalf.push_back(ots[i]);
	}
	vector<int> lh, rh;
	for (int i = 0; i < indos.size()/2; i++) {
		lh.push_back(indos[i]);
		rh.push_back(indos[i+indos.size()/2]);
	}
	decode(lh, firsthalf);
	decode(rh, secondhalf);

}

vector<int> restore_permutation(int n, int w, int r) {
    N = n;
    vector<int> allstuff;
    for (int i = 0; i < n; i++) {
    	allstuff.push_back(i);
    }
    addstuff(allstuff);
    compile_set();
    decode(allstuff, allstuff);
    vector<int> ans;
    for (int i = 0; i < n; i++) {
    	ans.push_back(p[i]);
    }
    return ans;
}

Compilation message (stderr)

messy.cpp: In function 'void addstuff(std::vector<int>)':
messy.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < indos.size()/2; i++) {
                  ~~^~~~~~~~~~~~~~~~
messy.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < indos.size()/2; i++) {
                  ~~^~~~~~~~~~~~~~~~
messy.cpp: In function 'void decode(std::vector<int>, std::vector<int>)':
messy.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ots.size(); i++) {
                  ~~^~~~~~~~~~~~
messy.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < indos.size()/2; i++) {
                  ~~^~~~~~~~~~~~~~~~

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