제출 #575147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
575147		AugustinasJucas	Unscrambling a Messy Bug (IOI16_messy)	C++14	70 / 100	2 ms	468 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"

using namespace std;
int n, w, r;

string orig;
string inv(string a) {
    for(auto &x : a) {
        if(x  == '0') x = '1';
        else x = '0';
    }
    return a;
}
int lg(int n) {
    if(n == 1) return 0;
    return lg(n / 2) + 1;
}
string toBits(int a) {
    a++;
    string ret = "";
    for(int i = 0; i < 3; i++) {
        if((1 << i) & a) ret.push_back('1');
        else ret.push_back('0');
    }
    return ret;
}
string f(int bitas, int ind, vector<int> vec) {
    string sitas = orig;
    string bts = toBits(bitas);
    for(int i = 0; i < 3; i++) {
        sitas[vec[i]] = bts[i];
    }
    sitas[ind] = '1';
    return sitas;
}

vector<int> find3(){
    vector<int> ret;
    string last = orig;
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < n; j++) {
            if(last[j] == '1') continue;
            last[j] = '1';

            if(check_element(inv(last))) {
          //      cout << i << "-asis eina i " << j << "-aja pozicija, nes " << inv(last) << " egzistuoja" << endl;
                ret.push_back(j);
                break;
            }
            last[j] = '0';
        }
    }
    return ret;
}
vector<int> restore_permutation(int N, int W, int R) {
/*    add_element("0");
    compile_set();
    check_element("0");
*/
  //  cout << "vcia" << endl;
    n = N; w = W; r = R;
    orig = "";
    int lg2 = lg(n);
    for(int i = 0; i < n; i++) orig.push_back('0');

    for(int i = 0; i < 3; i++) {
        string sitas = orig;
        for(int j = 0; j <= i; j++) {
            sitas[j] = '1';
        }
        sitas = inv(sitas);
      //  cout << "Idedu " << sitas << endl;
        add_element(sitas);
    }
    for(int i = 0; i < lg2; i++){
      //  cout << "ziuriu i " << i << "-aji bita:" << endl;
        for(int j = 3; j < n; j++) {
            if((1 << i) & j) {
                string toAdd = f(i, j, {0, 1, 2});
      //          cout << "Idedu " << toAdd << endl;
                add_element(toAdd);
            }
        }
    }
   // cout << "kompiliuojame!" << endl;
    compile_set();
    vector<int> pirmiTrys = find3();

    for(int i = 0; i < 3; i++) {
   //     cout << i << "-etas tampa " << pirmiTrys[i] << endl;
    }

    vector<int> visi = pirmiTrys;
    visi.resize(n);
    for(int i = 0; i < n; i++) {
        int sk = 0;
        if(i == pirmiTrys[0] || i == pirmiTrys[1] || i == pirmiTrys[2]) continue;
        //cout << "ziuriu, kuriuos bitus turi skaicius " << i << endl;
        for(int j = 0; j < lg2; j++) {

            string sitas = f(j, i, pirmiTrys);
            if(check_element(sitas)) {
           //     cout << j << " bita turi, nes yra " << sitas << endl;
                sk += (1 << j);
            }else {
         //       cout << j << " bito neturi, nes nera " << sitas << endl;
            }
        }
      //  cout << sk << "-etas tampa " << i << endl;
        visi[sk] = i;
    }
    vector<int> ans(n);
    for(int i = 0; i < n; i++) {
        ans[visi[i]] = i;
    }
    return ans;

}
/*
8 100 100
7 4 5 3 1 0 2 6
*/

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