Submission #284572

#	Time	Username	Problem	Language	Result	Execution time	Memory
284572		A02	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	10 ms	672 KiB

messy

#include <vector>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <iostream>

#include "messy.h"

using namespace std;

vector<string> gen_input(int n){

    if (n == 2){
        vector<string> result;
        result.push_back("10");
        return result;
    }

    vector<string> reduced_result = gen_input(n / 2);

    vector<string> result;

    for (int i = 0; i < reduced_result.size(); i++){
        string s1 = reduced_result[i];
        string s2 = reduced_result[i];

        for (int i = 0; i < n / 2; i++){
            s1 = '1' + s1;
            s2 = s2 + '1';
        }

        result.push_back(s1);
        result.push_back(s2);
    }

    string s = "";

    for (int i = 0; i < n; i++){
        s += "0";
    }

    for (int i = 0; i < n / 2; i++){
        string s1 = s;
        s1[i] = '1';
        result.push_back(s1);
    }

    return result;

}

void determine_answer(int l, int width, vector<int> &known_permutation, int n, vector<bool> known_image){

    string s = "";

    for (int i = 0; i < n; i++){
        s += "0";
    }

    vector<int> possible_image;

    for (int i = 0; i < n; i++){
        if (known_image[i] == false){
            s[i] = '1';
        } else {
            possible_image.push_back(i);
        }
    }


    if (width == 2){

        s[possible_image[0]] = '1';
        if (check_element(s)){
            known_permutation[l] = possible_image[0];
            known_permutation[l + 1] = possible_image[1];
        } else {
            known_permutation[l] = possible_image[1];
            known_permutation[l + 1] = possible_image[0];
        }

        return;
    }

    vector<int> left_interval_image;

    for (int i = 0; i < possible_image.size(); i++){
        string s1 = s;
        s1[possible_image[i]] = '1';
        if (check_element(s1)){
            left_interval_image.push_back(possible_image[i]);
        }
    }

    //cout << l << 'w' << width << endl;
//    for (int i = 0; i < left_interval_image.size(); i++){
//        cout << left_interval_image[i] << ' ';
//    }
    //cout << endl << endl;

    vector<bool> left_known_image (n, false);
    vector<bool> right_known_image = known_image;

    for (int i = 0; i < left_interval_image.size(); i++){
        left_known_image[left_interval_image[i]] = true;
        right_known_image[left_interval_image[i]] = false;
    }

    determine_answer(l, width / 2, known_permutation, n, left_known_image);
    determine_answer(l + width / 2, width / 2, known_permutation, n, right_known_image);

}

std::vector<int> restore_permutation(int n, int w, int r) {

    vector<string> test = gen_input(n);

    for (int i = 0; i < test.size(); i++){
        add_element(test[i]);
        //cout << test[i] << endl;
    }

    compile_set();

    vector<int> known_permutation (n, -1);
    vector<bool> known_image (n, true);

    determine_answer(0, n, known_permutation, n, known_image);

    vector<int> inversep (n, -1);

    for (int i = 0; i < n; i++){
        inversep[known_permutation[i]] = i;
    }

    return inversep;
}

Compilation message (stderr)

messy.cpp: In function 'std::vector<std::__cxx11::basic_string<char> > gen_input(int)':
messy.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0; i < reduced_result.size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~
messy.cpp: In function 'void determine_answer(int, int, std::vector<int>&, int, std::vector<bool>)':
messy.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < possible_image.size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~
messy.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int i = 0; i < left_interval_image.size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for (int i = 0; i < test.size(); i++){
      |                     ~~^~~~~~~~~~~~~

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