oj.uz

Submission #1074270

# Submission time Handle Problem Language Result Execution time Memory
1074270 2024-08-25T09:17:07 Z DeathIsAwe Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 2 ms 620 KB 
#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
bool visited[128];
vector<int> ansarr;
int mnmx[128][2];


void recuradd(pair<int,int> range, int n) {
    string sus(n, '1');
    for (int i=range.first;i<=range.second;i++) {
        sus[i] = '0';
    }
    int mid = (range.first + range.second + 1) / 2;
    for (int i=mid;i<=range.second;i++) {
        sus[i] = '1';
        add_element(sus);
        sus[i] = '0';
    }
    if (range.second - range.first != 1) {
        recuradd(make_pair(range.first, mid - 1), n);
        recuradd(make_pair(mid, range.second), n);
    }
}


void recurcheck(pair<int,int> range, int n) {
    string sus(n, '1');
    for (int i=0;i<n;i++) {
        if (mnmx[i][0] >= range.first && mnmx[i][1] <= range.second) {
            sus[i] = '0';
        }
    }
    int mid = (range.first + range.second + 1) / 2;
    for (int i=0;i<n;i++) {
        if (sus[i] == '0') {
            sus[i] = '1';
            if (check_element(sus)) {
                mnmx[i][0] = mid;
                if (mnmx[i][0] == mnmx[i][1]) {
                    ansarr[i] = mnmx[i][0];
                }
            } else {
                mnmx[i][1] = mid - 1;
                if (mnmx[i][0] == mnmx[i][1]) {
                    ansarr[i] = mnmx[i][0];
                }
            }
            sus[i] = '0';
        }
    }
    if (range.second - range.first != 1) {
        recurcheck(make_pair(range.first, mid - 1), n);
        recurcheck(make_pair(mid, range.second), n);
    }
}



vector<int> restore_permutation(int n, int w, int r) {
    recuradd(make_pair(0, n - 1), n);
    compile_set();


    for (int i=0;i<n;i++) {
        ansarr.push_back(-1);
        mnmx[i][0] = 0; mnmx[i][1] = n - 1;
    }
    recurcheck(make_pair(0, n - 1), n);
    
    return ansarr;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 8
2 Correct 1 ms 348 KB n = 8
3 Correct 0 ms 348 KB n = 8
4 Correct 0 ms 348 KB n = 8
5 Correct 1 ms 348 KB n = 8
6 Correct 1 ms 348 KB n = 8
7 Correct 1 ms 348 KB n = 8
8 Correct 0 ms 348 KB n = 8
9 Correct 0 ms 348 KB n = 8
10 Correct 1 ms 344 KB n = 8
11 Correct 0 ms 348 KB n = 8
12 Correct 0 ms 440 KB n = 8
13 Correct 0 ms 348 KB n = 8
14 Correct 0 ms 348 KB n = 8
15 Correct 0 ms 348 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 32
2 Correct 1 ms 344 KB n = 32
3 Correct 0 ms 348 KB n = 32
4 Correct 1 ms 348 KB n = 32
5 Correct 0 ms 464 KB n = 32
6 Correct 1 ms 348 KB n = 32
7 Correct 1 ms 440 KB n = 32
8 Correct 0 ms 440 KB n = 32
9 Correct 0 ms 348 KB n = 32
10 Correct 0 ms 348 KB n = 32
11 Correct 0 ms 344 KB n = 32
12 Correct 0 ms 348 KB n = 32
13 Correct 0 ms 348 KB n = 32
14 Correct 1 ms 348 KB n = 32
15 Correct 0 ms 348 KB n = 32

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB n = 128
2 Correct 1 ms 604 KB n = 128
3 Correct 1 ms 604 KB n = 128
4 Correct 1 ms 604 KB n = 128
5 Correct 1 ms 604 KB n = 128
6 Correct 2 ms 620 KB n = 128
7 Correct 1 ms 604 KB n = 128
8 Correct 1 ms 440 KB n = 128
9 Correct 1 ms 604 KB n = 128
10 Correct 1 ms 604 KB n = 128
11 Correct 1 ms 604 KB n = 128
12 Correct 1 ms 604 KB n = 128
13 Correct 1 ms 436 KB n = 128
14 Correct 1 ms 608 KB n = 128
15 Correct 1 ms 604 KB n = 128

Subtask #5
30.0 / 30.0

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