oj.uz

Submission #284572

# Submission time Handle Problem Language Result Execution time Memory
284572 2020-08-27T16:32:47 Z A02 Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 10 ms 672 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB n = 8
2 Correct 0 ms 256 KB n = 8
3 Correct 0 ms 256 KB n = 8
4 Correct 1 ms 256 KB n = 8
5 Correct 0 ms 256 KB n = 8
6 Correct 0 ms 256 KB n = 8
7 Correct 0 ms 256 KB n = 8
8 Correct 1 ms 256 KB n = 8
9 Correct 1 ms 256 KB n = 8
10 Correct 0 ms 256 KB n = 8
11 Correct 0 ms 256 KB n = 8
12 Correct 1 ms 256 KB n = 8
13 Correct 1 ms 256 KB n = 8
14 Correct 1 ms 256 KB n = 8
15 Correct 1 ms 384 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 32
2 Correct 1 ms 384 KB n = 32
3 Correct 1 ms 384 KB n = 32
4 Correct 1 ms 384 KB n = 32
5 Correct 1 ms 384 KB n = 32
6 Correct 1 ms 384 KB n = 32
7 Correct 1 ms 384 KB n = 32
8 Correct 1 ms 372 KB n = 32
9 Correct 1 ms 384 KB n = 32
10 Correct 1 ms 384 KB n = 32
11 Correct 1 ms 384 KB n = 32
12 Correct 1 ms 384 KB n = 32
13 Correct 1 ms 384 KB n = 32
14 Correct 1 ms 384 KB n = 32
15 Correct 1 ms 384 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 32
2 Correct 1 ms 384 KB n = 32
3 Correct 1 ms 384 KB n = 32
4 Correct 1 ms 384 KB n = 32
5 Correct 1 ms 384 KB n = 32
6 Correct 1 ms 384 KB n = 32
7 Correct 1 ms 360 KB n = 32
8 Correct 1 ms 384 KB n = 32
9 Correct 1 ms 384 KB n = 32
10 Correct 1 ms 384 KB n = 32
11 Correct 1 ms 384 KB n = 32
12 Correct 1 ms 384 KB n = 32
13 Correct 1 ms 384 KB n = 32
14 Correct 1 ms 384 KB n = 32
15 Correct 1 ms 384 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB n = 128
2 Correct 7 ms 640 KB n = 128
3 Correct 7 ms 672 KB n = 128
4 Correct 7 ms 640 KB n = 128
5 Correct 7 ms 640 KB n = 128
6 Correct 9 ms 640 KB n = 128
7 Correct 7 ms 640 KB n = 128
8 Correct 9 ms 640 KB n = 128
9 Correct 7 ms 640 KB n = 128
10 Correct 6 ms 640 KB n = 128
11 Correct 7 ms 640 KB n = 128
12 Correct 7 ms 640 KB n = 128
13 Correct 7 ms 640 KB n = 128
14 Correct 9 ms 640 KB n = 128
15 Correct 8 ms 640 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB n = 128
2 Correct 7 ms 596 KB n = 128
3 Correct 7 ms 640 KB n = 128
4 Correct 7 ms 640 KB n = 128
5 Correct 6 ms 640 KB n = 128
6 Correct 7 ms 640 KB n = 128
7 Correct 7 ms 640 KB n = 128
8 Correct 7 ms 640 KB n = 128
9 Correct 7 ms 640 KB n = 128
10 Correct 9 ms 640 KB n = 128
11 Correct 7 ms 640 KB n = 128
12 Correct 8 ms 640 KB n = 128
13 Correct 7 ms 640 KB n = 128
14 Correct 8 ms 640 KB n = 128
15 Correct 7 ms 640 KB n = 128