Submission #170587

#	Time	Username	Problem	Language	Result	Execution time	Memory
170587		AlexLuchianov	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	632 KiB

messy

#include <vector>
#include <set>
#include <iostream>
#include <fstream>

#include "messy.h"

int const lgmax = 8;
std::set<int> myset[1 + lgmax];

std::vector<int> restore_permutation(int n, int w, int r) {
  int p = 0;
  while((1 << p) < n)
    p++;

  std::vector<int> known;

  //std::cout << p << '\n';

  for(int i = 0; i < p; i++){
    std::string s;
    s.resize(n);
    for(int j = 0; j < n; j++)
      s[j] = '0';
    for(int j = 0; j < known.size(); j++)
      s[known[j]] = '1';

    if(i == p - 1)
      for(int j = 0; j < n; j++)
        s[j] = '1';

    for(int j = 0; j < n; j++)
      if(0 < ((1 << i) & j)) {
        if(s[j] == '0')
          s[j] = '1';
        else
          s[j] = '0';
        add_element(s);
        //std::cout << i << " " << j << " " << s << '\n';
        if(s[j] == '0')
          s[j] = '1';
        else
          s[j] = '0';
        known.push_back(j);
      }
  }
  //std::cout << '\n';

  compile_set();
  known.clear();
  for(int i = 0; i < p; i++){
    std::string s;
    s.resize(n);
    for(int j = 0; j < n; j++)
      s[j] = '0';
    for(int j = 0; j < known.size(); j++)
      s[known[j]] = '1';

    if(i == p - 1)
      for(int j = 0; j < n; j++)
        s[j] = '1';

    for(int j = 0; j < n; j++){
      if(s[j] == '0')
        s[j] = '1';
      else
        s[j] = '0';
      //std::cout << i << " " << j << " " << s << " " << check_element(s) << '\n';

      if(check_element(s) == 1) {
        myset[i].insert(j);
        known.push_back(j);
      }

      if(s[j] == '0')
        s[j] = '1';
      else
        s[j] = '0';
    }
  }

  std::vector<int> sol(n);
  for(int i = 0; i < n; i++){
    int number = 0;
    for(int j = 0; j < p; j++)
      if(myset[j].find(i) != myset[j].end())
        number += (1 << j);
    sol[i] = number;
  }

  return sol;
}

Compilation message (stderr)

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:25:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < known.size(); j++)
                    ~~^~~~~~~~~~~~~~
messy.cpp:56:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < known.size(); j++)
                    ~~^~~~~~~~~~~~~~

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