oj.uz

Submission #537672

# Submission time Handle Problem Language Result Execution time Memory
537672 2022-03-15T11:12:37 Z Cross_Ratio Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 2 ms 468 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 8
2 Correct 1 ms 300 KB n = 8
3 Correct 1 ms 212 KB n = 8
4 Correct 1 ms 212 KB n = 8
5 Correct 1 ms 212 KB n = 8
6 Correct 1 ms 212 KB n = 8
7 Correct 1 ms 212 KB n = 8
8 Correct 1 ms 212 KB n = 8
9 Correct 1 ms 212 KB n = 8
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 304 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 32
2 Correct 1 ms 212 KB n = 32
3 Correct 1 ms 212 KB n = 32
4 Correct 1 ms 212 KB n = 32
5 Correct 1 ms 300 KB n = 32
6 Correct 1 ms 304 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 1 ms 212 KB n = 32
9 Correct 1 ms 212 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 1 ms 212 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 1 ms 300 KB n = 32
14 Correct 1 ms 300 KB n = 32
15 Correct 1 ms 308 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 32
2 Correct 1 ms 212 KB n = 32
3 Correct 1 ms 212 KB n = 32
4 Correct 1 ms 212 KB n = 32
5 Correct 1 ms 300 KB n = 32
6 Correct 1 ms 300 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 1 ms 300 KB n = 32
9 Correct 1 ms 304 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 1 ms 212 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 1 ms 212 KB n = 32
14 Correct 1 ms 212 KB n = 32
15 Correct 1 ms 212 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB n = 128
2 Correct 1 ms 468 KB n = 128
3 Correct 1 ms 468 KB n = 128
4 Correct 2 ms 468 KB n = 128
5 Correct 2 ms 468 KB n = 128
6 Correct 2 ms 468 KB n = 128
7 Correct 2 ms 468 KB n = 128
8 Correct 2 ms 468 KB n = 128
9 Correct 2 ms 468 KB n = 128
10 Correct 2 ms 468 KB n = 128
11 Correct 2 ms 432 KB n = 128
12 Correct 1 ms 468 KB n = 128
13 Correct 2 ms 468 KB n = 128
14 Correct 2 ms 468 KB n = 128
15 Correct 1 ms 428 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB n = 128
2 Correct 1 ms 432 KB n = 128
3 Correct 1 ms 468 KB n = 128
4 Correct 1 ms 468 KB n = 128
5 Correct 2 ms 468 KB n = 128
6 Correct 1 ms 468 KB n = 128
7 Correct 1 ms 468 KB n = 128
8 Correct 2 ms 392 KB n = 128
9 Correct 2 ms 468 KB n = 128
10 Correct 1 ms 468 KB n = 128
11 Correct 1 ms 468 KB n = 128
12 Correct 2 ms 468 KB n = 128
13 Correct 1 ms 468 KB n = 128
14 Correct 2 ms 468 KB n = 128
15 Correct 2 ms 468 KB n = 128