Submission #41317

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

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;

int ans[300], n;

string zero;

void solve_add(int ini, int fim)
{
  int mid = (ini + fim)/2;

  if(ini == fim) return;

  string s = zero;

  for(int i = ini; i <= fim; i++) s[i] = '1';

  //cout<<ini<<" "<<fim<<"\n";

  for(int i = mid + 1; i <= fim; i++)
  {
    s[i] = '0';

    //cout<<"ADD STRING "<<s<<" -> "<<novo(s)<<"\n";

    add_element(s);

    s[i] = '1';
  }

  //cout<<"\n";

  solve_add(ini, mid), solve_add(mid + 1, fim);
}

void solve_check(int ini, int fim, vector<int> free)
{
  //cout<<ini<<" "<<fim<<"\n";

  int mid = (ini + fim)/2;

  string s = zero;

  vector<int> esq, dir;

  if(ini == fim)
  {
    //cout<<free.size()<<"\n";
    
    if(free.size()) ans[free[0]] = ini;

    return;
  }

  for(int i = 0; i < free.size(); i++) s[ free[i] ] = '1';

  for(int i = 0; i < free.size(); i++)
  {
    int p = free[i];

    s[p] = '0';

    if(check_element(s))  dir.push_back(p);

    else esq.push_back(p);

    s[p] = '1';
  }

  //for(auto x: dir) cout<<"DIR "<<x<<"\n";

  //for(auto x: esq) cout<<"ESQ "<<x<<'\n';

  solve_check(ini, mid, esq), solve_check(mid + 1, fim, dir);
}

vector<int> vini, resp;

vector<int> restore_permutation(int N_, int w, int r)
{
  n = N_;

  for(int i = 0; i < n; i++) zero.push_back('0'), vini.push_back(i);

  solve_add(0, n - 1);

  compile_set();

  solve_check(0, n - 1, vini);

  for(int i = 0; i < n; i++) resp.push_back(ans[i]);

  return resp;
}

Compilation message (stderr)

messy.cpp: In function 'void solve_check(int, int, std::vector<int>)':
messy.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < free.size(); i++) s[ free[i] ] = '1';
                  ~~^~~~~~~~~~~~~
messy.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < free.size(); i++)
                  ~~^~~~~~~~~~~~~

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