oj.uz

Submission #95554

# Submission time Handle Problem Language Result Execution time Memory
95554 2019-02-02T04:00:48 Z hihi Unscrambling a Messy Bug (IOI16_messy) C++11
100 / 100
 7 ms 616 KB 
#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> ans;
void addStuff(int start, int stop, int flagStart, int flagStop) {
    for (int i=start;i<(start+stop)/2;i++) {
        string s = "";
        for (int j=0;j<N;j++) {
            if (j == i || (flagStart <= j && j < flagStop)) {
                s += "1";
            } else {
                s += "0";
            }
        }
        add_element(s);
    }
    if (stop - start > 2) {
        addStuff(start, (start+stop)/2, (start+stop)/2, stop);
        addStuff((start+stop)/2, stop, start, (start+stop)/2);
    }
}
void checkStuff(int start, int stop, vector<int>& flags, vector<int>& candidates) {
    vector<int> zeroFlags, oneFlags;
    string s = "";
    for (int i=0;i<N;i++) s += "0";
    for (int i=0;i<flags.size();i++) s[flags[i]] = '1';
    for (int i=0;i<candidates.size();i++) {
        string q = s;
        q[candidates[i]] = '1';
        if (check_element(q)) {
            oneFlags.push_back(candidates[i]);
        } else {
            zeroFlags.push_back(candidates[i]);
        }
    }
    if (stop - start > 2) {
        checkStuff(start, (start+stop)/2, zeroFlags, oneFlags);
        checkStuff((start+stop)/2, stop, oneFlags, zeroFlags);
    } else {
        ans[oneFlags[0]] = start;
        ans[zeroFlags[0]] = start + 1;
    }
}


vector<int> restore_permutation(int _n, int w, int r) {
    N = _n;
    addStuff(0, N, -1, -1);
    compile_set();
    ans.resize(N);
    vector<int> x;
    vector<int> all;
    all.resize(N);
    for (int i=0;i<N;i++) all[i] = i;
    checkStuff(0, N, x, all);
    return ans;
}

Compilation message

messy.cpp: In function 'void checkStuff(int, int, std::vector<int>&, std::vector<int>&)':
messy.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<flags.size();i++) s[flags[i]] = '1';
                  ~^~~~~~~~~~~~~
messy.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<candidates.size();i++) {
                  ~^~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 256 KB n = 8
2 Correct 2 ms 256 KB n = 8
3 Correct 2 ms 384 KB n = 8
4 Correct 2 ms 384 KB n = 8
5 Correct 2 ms 256 KB n = 8
6 Correct 2 ms 384 KB n = 8
7 Correct 2 ms 284 KB n = 8
8 Correct 2 ms 256 KB n = 8
9 Correct 2 ms 384 KB n = 8
10 Correct 2 ms 384 KB n = 8
11 Correct 2 ms 384 KB n = 8
12 Correct 2 ms 384 KB n = 8
13 Correct 2 ms 356 KB n = 8
14 Correct 2 ms 384 KB n = 8
15 Correct 2 ms 384 KB n = 8

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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