oj.uz

Submission #951343

# Submission time Handle Problem Language Result Execution time Memory
951343 2024-03-21T16:07:35 Z kilkuwu Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 2 ms 856 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

#ifdef LOCAL
#include "template\debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

std::vector<int> restore_permutation(int n, int w, int r) {
  std::string s(n, '1');
  
  for (int num_block = 1; num_block < n; num_block *= 2) {
    int block_size = n / num_block;
    for (int b = 0; b < num_block; b++) {
      int st = block_size * b;
      for (int i = st; i < st + block_size; i++) {
        s[i] = '0';
        // we will add into our element
      }
      for (int i = st; i < st + block_size / 2; i++) {
        s[i] = '1';
        add_element(s);
        s[i] = '0';
      }
      for (int i = st; i < st + block_size; i++) {
        s[i] = '1';
        // we will add into our element
      }
    }
  }


  compile_set();

  std::vector<int> p(n);
  std::iota(p.begin(), p.end(), 0);
  std::vector<int> marked(n);

  for (int num_block = 1; num_block < n; num_block *= 2) {
    int block_size = n / num_block;

    for (int b = 0; b < num_block; b++) {
      int st = block_size * b;
      for (int i = st; i < st + block_size; i++) {
        s[p[i]] = '0';
      }
      for (int i = st; i < st + block_size; i++) {
        s[p[i]] = '1';
        if (check_element(s)) {
          marked[i] = 1;
        }
        s[p[i]] = '0';
      }

      for (int i = st, j = st; i < st + block_size; i++) {
        if (marked[i]) {
          std::swap(p[i], p[j]);
          j++;
          marked[i] = 0;
        } 
      }

      for (int i = st; i < st + block_size; i++) {
        s[p[i]] = '1';
      }
    }
  }

  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 344 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 348 KB n = 8
6 Correct 1 ms 348 KB n = 8
7 Correct 0 ms 348 KB n = 8
8 Correct 1 ms 348 KB n = 8
9 Correct 0 ms 348 KB n = 8
10 Correct 1 ms 348 KB n = 8
11 Correct 0 ms 348 KB n = 8
12 Correct 1 ms 348 KB n = 8
13 Correct 0 ms 344 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 1 ms 344 KB n = 32
2 Correct 1 ms 348 KB n = 32
3 Correct 1 ms 348 KB n = 32
4 Correct 1 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 0 ms 348 KB n = 32
9 Correct 0 ms 348 KB n = 32
10 Correct 0 ms 348 KB n = 32
11 Correct 1 ms 432 KB n = 32
12 Correct 0 ms 348 KB n = 32
13 Correct 0 ms 348 KB n = 32
14 Correct 0 ms 348 KB n = 32
15 Correct 1 ms 348 KB n = 32

Subtask #3
11.0 / 11.0

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