Submission #537672

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

messy

#include <bits/stdc++.h>
//#include "messy.h"
using namespace std;
void add_element(string);
void compile_set();
bool check_element(string);
bool type[130][9];
void DnC(int s, int e, string S, int lev) {
    if(e==s+1) return;
    int mid = (s + e) / 2;
    int i;
    for(i=s;i<e;i++) {
        S[i] = '0';
    }
    for(i=s;i<mid;i++) {
        S[i] = '1';
        /*cout << "Push ";
        for(int j=0;j<S.length();j++) cout <<S[j];
        cout << '\n';*/
        add_element(S);
        S[i] = '0';
        type[i][lev] = true;
    }
    for(i=s;i<mid;i++) S[i] = '1';
    DnC(mid, e, S, lev+1);
    for(i=s;i<mid;i++) S[i] = '0';
    for(i=mid;i<e;i++) S[i] = '1';
    DnC(s, mid, S, lev+1);
}
vector<vector<int>> seg;
void DnC2(string S, int n) {
    if(n>=seg.size()/2) return;
    int i;
    vector<int> A, B;
    for(int k : seg[n]) {
        S[k] = '0';
    }
    for(int k : seg[n]) {
        S[k] = '1';
        bool m = check_element(S);
        /*for(int j = 0; j < S.length();j++) cout << S[j];
        cout << " : ? " << (m ? "True\n" : "False\n");*/
        S[k] = '0';
        if(m) seg[2*n].push_back(k);
        else seg[2*n+1].push_back(k);
    }
    for(int k : seg[2*n]) {
        S[k] = '1';
    }
    DnC2(S, 2*n+1);
    for(int k : seg[2*n]) S[k] = '0';
    for(int k : seg[2*n+1]) S[k] = '1';
    DnC2(S, 2*n);
}
vector<int> restore_permutation(int N, int W, int R) {
    string S;
    S.resize(N);
    int i, j, k, a, b, c;
    DnC(0, N, S, 0);
    compile_set();
    seg.resize(2*N);
    for(i=0;i<N;i++) seg[1].push_back(i);
    for(i=0;i<N;i++) S[i] = '0';
    DnC2(S, 1);
    vector<int> V;
    V.resize(N);
    for(i=0;i<N;i++) {
        V[seg[i+N][0]] = i;
    }
    /*for(i=1;i<2*N;i++) {
        cout << i << " th Set\n";
        for(int k : seg[i]) cout << k << ' ';
        cout << '\n';
    }*/
    return V;
}

Compilation message (stderr)

messy.cpp: In function 'void DnC2(std::string, int)':
messy.cpp:32:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     if(n>=seg.size()/2) return;
      |        ~^~~~~~~~~~~~~~
messy.cpp:33:9: warning: unused variable 'i' [-Wunused-variable]
   33 |     int i;
      |         ^
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:58:12: warning: unused variable 'j' [-Wunused-variable]
   58 |     int i, j, k, a, b, c;
      |            ^
messy.cpp:58:15: warning: unused variable 'k' [-Wunused-variable]
   58 |     int i, j, k, a, b, c;
      |               ^
messy.cpp:58:18: warning: unused variable 'a' [-Wunused-variable]
   58 |     int i, j, k, a, b, c;
      |                  ^
messy.cpp:58:21: warning: unused variable 'b' [-Wunused-variable]
   58 |     int i, j, k, a, b, c;
      |                     ^
messy.cpp:58:24: warning: unused variable 'c' [-Wunused-variable]
   58 |     int i, j, k, a, b, c;
      |                        ^

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