oj.uz

Submission #67915

# Submission time Handle Problem Language Result Execution time Memory
67915 2018-08-15T13:58:53 Z Talant Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 4 ms 512 KB 
#include "messy.h"
//#include "grader.cpp"

#include <bits/stdc++.h>

#define sc second
#define fr first
#define mk make_pair
#define pb push_back

using namespace std;

const int N = (1e6 + 5);
const int inf = (1e9 + 7);

string s;
vector <int> ans,res;

void fun(int n,int l,int r) {
      if (l >= r) return;
      s = "";

      for (int i = 0; i <= n; i ++) {
            if (l <= i && i <= r) s += '0';
            else s += '1';
      }
      int md = (l + r) >> 1;
      for (int i = l; i <= md; i ++) {
            s[i] = '1';
            add_element(s);
            s[i] = '0';
      }
      fun(n,l,md);
      fun(n,md + 1,r);
}
void rec(int n,int l,int r) {
      if (l >= r) return;

      s = "";
      for (int i = 0; i <= n; i ++) s += '0';

      for (int i = 0; i <= n; i ++) {
            if (l <= i && i <= r) s[ans[i]] = '0';
            else s[ans[i]] = '1';
      }
      int md = (l + r) >> 1;

      vector <int> v1,v2;

      for (int i = l; i <= r; i ++) {
            s[ans[i]] = '1';
            if (check_element(s))
                  v1.pb(ans[i]);
            else
                  v2.pb(ans[i]);
            s[ans[i]] = '0';
      }
      int id = 0,id1 = 0;
      for (int i = l; i <= r; i ++) {
            if (i <= md) ans[i] = v1[id ++];
            else ans[i] = v2[id1 ++];
      }
      rec(n,l,md);
      rec(n,md + 1,r);
}
vector<int> restore_permutation(int n, int w, int r) {
      ans.resize(n);
      res.resize(n);

      n --;

      for (int i = 0; i <= n; i ++)
            ans[i] = i;

      fun(n,0,n);
      compile_set();
      rec(n,0,n);

      for (int i = 0; i <= n; i ++)
            res[ans[i]] = i;

      return res;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 256 KB n = 8
5 Correct 2 ms 256 KB n = 8
6 Correct 2 ms 256 KB n = 8
7 Correct 2 ms 256 KB n = 8
8 Correct 2 ms 384 KB n = 8
9 Correct 2 ms 256 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 384 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 256 KB n = 32
2 Correct 3 ms 384 KB n = 32
3 Correct 2 ms 256 KB n = 32
4 Correct 2 ms 384 KB n = 32
5 Correct 2 ms 384 KB n = 32
6 Correct 3 ms 384 KB n = 32
7 Correct 3 ms 512 KB n = 32
8 Correct 2 ms 384 KB n = 32
9 Correct 2 ms 384 KB n = 32
10 Correct 3 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 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 3 ms 428 KB n = 32
4 Correct 2 ms 384 KB n = 32
5 Correct 2 ms 384 KB n = 32
6 Correct 2 ms 256 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 256 KB n = 32
11 Correct 2 ms 256 KB n = 32
12 Correct 2 ms 384 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 #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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