Submission #1107493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107493		SonicML	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	2 ms	808 KiB

messy

#include <vector>
#include <string>

#include "messy.h"

using namespace std;

//int freqW, freqR;

string add;

void setAddInterval(int from, int to, char val) {
  for(int i = from;i <= to;i++) {
    add[i] = val;
  }
}

void build(int from, int to) {
  if(from == to) {
    return; 
  }else {
    int mid = (from + to) / 2;
    for(int i = from;i <= mid;i++) {
      add[i] = '1';
      //freqW++;
      //cerr << freqW << '\n';
      //cerr << add << '\n';
      add_element(add); 
      add[i] = '0';
    }
    setAddInterval(mid+1, to, '1');
    build(from, mid);
    setAddInterval(mid+1, to, '0');
    
    setAddInterval(from, mid, '1');
    build(mid+1, to);
    setAddInterval(from, mid, '0');
  }
}

string ser;

int const NMAX = 128;
int pos[1 + NMAX];
int perm[1 + NMAX];

bool outside[1 + NMAX];

void search(int from, int to, int n) {
  if(from == to) {
    for(int i = 0;i < n;i++) {
      if(!outside[i]) {
        pos[from] = i;
        perm[pos[from]] = from;   
        return;
      }
    }
  }else { 
    int mid = (from + to) / 2;
    for(int i = 0;i < n;i++) {
      if(outside[i]) {
	ser[i] = '1';
      }else {
	ser[i] = '0';
      }
    }
    vector <int> half1;
    vector <int> half2;
    for(int i = 0;i < n;i++) {
      if(!outside[i]) {
        ser[i] = '1';
	//freqR++;
	//cerr << freqR << '\n';
	if(check_element(ser)) {
          half1.push_back(i);
        }else {
	  half2.push_back(i);
        }
        ser[i] = '0';	
      }
    }
   
    for(int i = 0;i < half2.size();i++) {
      outside[half2[i]] = true;
    }
    search(from, mid, n);
    for(int i = 0;i < half2.size();i++) {
      outside[half2[i]] = false;
    }

    for(int i = 0;i < half1.size();i++) {
      outside[half1[i]] = true;
    } 
    search(mid+1, to, n);
    for(int i = 0;i < half1.size();i++) { 
      outside[half1[i]] = false;
    }
  }
}

vector <int> restore_permutation(int n, int w, int r) {
  add.resize(n);
  setAddInterval(0, n-1, '0');

  build(0, n-1);
  compile_set();

  ser.resize(n);
  search(0, n-1, n);

  vector <int> ans;
  ans.resize(n);
  //cerr << n << '\n';
  for(int i = 0;i < n;i++) {
    ans[i] = perm[i];
    //cerr << perm[i];
  }
  return ans;
}

Compilation message (stderr)

messy.cpp: In function 'void search(int, int, int)':
messy.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 0;i < half2.size();i++) {
      |                   ~~^~~~~~~~~~~~~~
messy.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i = 0;i < half2.size();i++) {
      |                   ~~^~~~~~~~~~~~~~
messy.cpp:91:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i = 0;i < half1.size();i++) {
      |                   ~~^~~~~~~~~~~~~~
messy.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i = 0;i < half1.size();i++) {
      |                   ~~^~~~~~~~~~~~~~

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