oj.uz

Submission #711592

# Submission time Handle Problem Language Result Execution time Memory
711592 2023-03-17T09:28:35 Z TimDee Unscrambling a Messy Bug (IOI16_messy) C++17
49 / 100
 1 ms 340 KB 
#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
vector<int> restore_permutation(int n, int w, int r) {

    //1000
    //0100
    //? 1000 -> yes=>(1)/no=>(2)
    //(1): 
    //1100 -> 1010
    //(n/k)*(n/k)/2*k
    //n*n/2k
    // O(32) 11110000 -> 01100101
    // O(16*15/2) = O(8*15) = 120 for ?p[i], i>=n/2
    // O(16*15/2) = O(8*15) = 120 for ?p[i], i<n/2
    string z(n,'0');
    forn(i,n/2) {
        z[i]='1';
        add_element(z);
        z[i]='0';
    }
    for (int i=n-1; i>=n/2; --i) z[i]='1';
    for (int i=n/2-1; i>=0; --i) {
        z[i]='1';
        add_element(z);
    }
    for (int i=n-1; i>=n/2; --i) {
        z[i]='0';
        add_element(z);
    }
    compile_set();
    z.assign(n,'0');
    string ans(n,'0');
    vector<int> p(n,-1);
    vector<int> paiu;
    forn(i,n) {
        z[i]='1';
        int x=check_element(z);
        if (x) {
            ans[i]='1';
            paiu.push_back(i);
        }
        z[i]='0';
    }
    for (int i=n/2; i<n; ++i) {
        forn(j,n) {
            if (ans[j]=='1') continue;
            ans[j]='1';
            int x=check_element(ans);
            if (x) {
                p[j]=i;
                break;
            }
            ans[j]='0';
        }
    }
    assert(ans==string(n,'1'));
    for(auto&x:paiu) ans[x]='0';
    for (int i=n/2-1; i>=0; --i) {
        forn(j,n) {
            if (ans[j]=='1') continue;
            ans[j]='1';
            int x=check_element(ans);
            if (x) {
                p[j]=i;
                break;
            }
            ans[j]='0';
        }
    }
    assert(ans==string(n,'1'));
    return p;

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 8
2 Correct 0 ms 212 KB n = 8
3 Correct 0 ms 212 KB n = 8
4 Correct 1 ms 212 KB n = 8
5 Correct 0 ms 212 KB n = 8
6 Correct 0 ms 212 KB n = 8
7 Correct 1 ms 212 KB n = 8
8 Correct 1 ms 212 KB n = 8
9 Correct 0 ms 212 KB n = 8
10 Correct 0 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 0 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 0 ms 212 KB n = 32
2 Correct 1 ms 212 KB n = 32
3 Correct 1 ms 212 KB n = 32
4 Correct 0 ms 212 KB n = 32
5 Correct 1 ms 212 KB n = 32
6 Correct 0 ms 212 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 0 ms 212 KB n = 32
9 Correct 0 ms 212 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 0 ms 212 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 0 ms 212 KB n = 32
14 Correct 0 ms 212 KB n = 32
15 Correct 0 ms 212 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 212 KB n = 32
6 Correct 0 ms 212 KB n = 32
7 Correct 0 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 212 KB n = 32
14 Correct 1 ms 212 KB n = 32
15 Correct 1 ms 212 KB n = 32

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB grader returned WA
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB grader returned WA
2 Halted 0 ms 0 KB -