Submission #1205164

#TimeUsernameProblemLanguageResultExecution timeMemory
1205164totoroUnscrambling a Messy Bug (IOI16_messy)C++20
20 / 100
1 ms584 KiB
#include "messy.h" #include <iostream> #include <string> #include <vector> void write_specials(int n, int special); void write_range(int l, int r, int n, int depth); std::vector<int> find_specials(int n, int special); void solve_range(int n, int l, int r, int depth, std::vector<int> indexes, std::vector<int> specials, std::vector<int>& ans); std::vector<int> restore_permutation(int n, int w, int r) { int logn = 0; while (1 << logn < n) ++logn; int special = logn - 1; // These are calculated explicitly write_specials(n, special); write_range(special, n - 1, n, 0); compile_set(); std::vector<int> specials = find_specials(n, special); std::vector<int> ans(n, -1); for (int i = 0; i < special; ++i) ans[specials[i]] = i; std::vector<int> nonspecial; for (int i = 0; i < n; ++i) { if (ans[i] == -1) nonspecial.push_back(i); } solve_range(n, special, n - 1, 0, nonspecial, specials, ans); return ans; } void write_specials(int n, int special) { for (int i = 0; i < special; ++i) { std::string writebuf(n, '1'); writebuf[i] = '0'; add_element(writebuf); } std::string writebuf(n, '0'); for (int i = 0; i < special; ++i) { writebuf[i] = '1'; add_element(writebuf); } } void write_range(int l, int r, int n, int depth) { // std::cout << "writing range from " << l << " to " << r << " with depth " << depth << '\n'; if (l > r) return; if (l == r) return; int m = (l + r - 1) / 2; std::string setspecials(n, '0'); // set first `depth` special bits for (int i = 0; i < depth; ++i) { setspecials[i] = '1'; } for (int i = l; i <= m; ++i) { std::string writebuf = setspecials; writebuf[i] = '1'; add_element(writebuf); } write_range(l, m, n, depth + 1); write_range(m + 1, r, n, depth + 1); } std::vector<int> find_specials(int n, int special) { std::vector<int> unordered; for (int i = 0; i < n; ++i) { std::string readbuf(n, '1'); readbuf[i] = '0'; if (check_element(readbuf)) { unordered.push_back(i); } } std::vector<int> seen(special); std::vector<int> ordered; for (int i = 0; i < special; ++i) { std::string readbuf = std::string(n, '0'); for (int k : ordered) { readbuf[k] = '1'; } for (int j = 0; j < special; ++j) { if (seen[j]) continue; readbuf[unordered[j]] = '1'; if (check_element(readbuf)) { seen[j] = true; ordered.push_back(unordered[j]); break; } } } return ordered; } void solve_range(int n, int l, int r, int depth, std::vector<int> indexes, std::vector<int> specials, std::vector<int>& ans) { if (l > r) return; if (l == r) { ans[indexes[0]] = l; return; } int m = (l + r - 1) / 2; int lcount = m - l + 1; std::vector<int> left, right; std::string setspecials(n, '0'); for (int i = 0; i < depth; ++i) setspecials[specials[i]] = '1'; for (int index : indexes) { if (index == indexes.back()) { if (left.size() < lcount) { left.push_back(index); } else { right.push_back(index); } break; } std::string readbuf = setspecials; readbuf[index] = '1'; if (check_element(readbuf)) { left.push_back(index); } else { right.push_back(index); } } solve_range(n, l, m, depth + 1, left, specials, ans); solve_range(n, m + 1, r, depth + 1, right, specials, ans); }

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...