oj.uz

Submission #951196

# Submission time Handle Problem Language Result Execution time Memory
951196 2024-03-21T10:53:53 Z kilkuwu Unscrambling a Messy Bug (IOI16_messy) C++17
38 / 100
 1 ms 548 KB 
#include <bits/stdc++.h>

#ifndef LOCAL
#include "messy.h"
#else

#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <cstdlib>
#include <iostream>

void add_element(std::string x);
bool check_element(std::string x);
void compile_set();

std::vector<int> restore_permutation(int n, int w, int r);


namespace helper {

std::set<std::string> set_;
bool compiled = false;
int n;
std::vector<int> p;
int w;
int r;

int read_int() {
  int x;
  std::cin >> x;
  return x;
}

}


int get_p(int i) {
  using namespace helper;
  int ret = p[i];
  return ret;
}

int main() {
  using namespace helper;
  n = read_int();
  w = read_int();
  r = read_int();
  p = std::vector<int>(n);
  for (int i = 0; i < n; i++) {
    p[i] = read_int();
  }
  std::vector<int> answer = restore_permutation(n, w, r);

  if ((int) answer.size() != n) {
    printf("WA\n");
    return 0;
  }


  printf("%d", answer[0]);

  for (int i = 1; i < n; i++) {
    printf(" %d", answer[i]);
  }
  printf("\n");
  return 0;
}

void wa() {
  printf("WA\n");
  exit(0);
}

bool check(const std::string& x) {
  using namespace helper;
  if ((int)x.length() != n) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    if (x[i] != '0' && x[i] != '1') {
      return false;
    }
  }
  return true;
}

void add_element(std::string x) {
  using namespace helper;
  if (--w < 0 || compiled || !check(x)) {
    wa();
  }
  set_.insert(x);
}

bool check_element(std::string x) {
  using namespace helper;
  if (--r < 0 || !compiled || !check(x)) {
    wa();
  }
  return set_.count(x);
}

void compile_set() {
  using namespace helper;
  if (compiled) {
    wa();
  }
  compiled = true;
  std::set<std::string> compiledSet;
  std::string compiledElement = std::string(n, ' ');
  for (std::set<std::string>::iterator it = set_.begin(); it != set_.end(); it++) {
    std::string s = *it;
    for (int i = 0; i < n; i++) {
      compiledElement[i] = s[get_p(i)];
    }
    compiledSet.insert(compiledElement);
  }
  set_ = compiledSet;
}
#endif

std::vector<int> restore_permutation(int n, int w, int r) {
  std::vector<int> p(n);

  std::string s(n, '0');
  for (int i = 0; i + 1 < n; i++) {
    p.back() ^= n - i - 1;
    s[i] = '1';
    add_element(s);
  }

  compile_set();

  std::vector<int> found(n);

  s = std::string(n, '0');
  for (int i = 0; i + 1 < n; i++) {
    for (int j = 0; j < n; j++) {
      if (found[j] == 0) {
        s[j] = '1';
        int res = check_element(s);
        if (res) {
          p[i] = j;
          found[j] = 1;
          p.back() ^= j;
          break;
        }
        s[j] = '0';
      }
    }
  }

  std::vector<int> res(n);
  for (int i = 0; i < n; i++) {
    res[p[i]] = i;
  }

  return res;
}

Subtask #1
20.0 / 20.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 548 KB n = 32
2 Correct 0 ms 348 KB n = 32
3 Incorrect 0 ms 348 KB grader returned WA
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 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 348 KB grader returned WA
2 Halted 0 ms 0 KB -