oj.uz

Submission #836404

# Submission time Handle Problem Language Result Execution time Memory
836404 2023-08-24T10:54:15 Z nigus Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 2 ms 596 KB 
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#include "messy.h"

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int N;
string alf = "01";

string str(vi mask){
    string s = "";
    rep(c1,0,N){
        s += alf[mask[c1]];
    }
    return s;
}

vi add(vi mask, int i){
    mask[i] = 1;
    return mask;
}

void write_dq(int lo, int hi, vi mask){
    //cerr << lo << " " << hi << "\n";
    if(lo == hi-1)return;
    int mid = (lo+hi)/2;
    vi mask2 = mask;
    vi mask3 = mask;
    rep(c1,lo,mid){
        mask2[c1] = 1;
    }
    rep(c1,mid,hi){
        mask3[c1] = 1;
    }
    rep(c1,lo,mid){
        string s = str(add(mask, c1));
        add_element(s);
      //  cerr << s << "\n";
    }
    write_dq(lo,mid,mask3);
    write_dq(mid,hi,mask2);

}

int ANS[400] = {0};

void read_dq(int lo, int hi, vi mask){
    if(lo == hi-1){
        int smalls = 0;
        rep(c1,0,N){
            if(mask[c1] == 0){
                ANS[lo] = c1;
                smalls++;
            }
        }
        return;
    }
    int mid = (lo+hi)/2;
    vi mask2 = mask;
    vi mask3 = mask;

    rep(c1,0,N){
        if(mask[c1] == 0){
            string s = str(add(mask, c1));
            bool hej = check_element(s);
            if(hej){
                // was in left half
                mask2[c1] = 1;
            }
            else{
                mask3[c1] = 1;
            }
          //  cerr << s << "  ->  " << hej << "\n";
        }
    }

    read_dq(lo,mid,mask3);
    read_dq(mid,hi,mask2);

}

std::vector<int> restore_permutation(int n, int w, int r) {
    N = n;
    
    vi mask(n, 0);
    write_dq(0, n, mask);
  //  cerr << "WRITE DONE\n\n";
    compile_set();

    read_dq(0, n, mask);

    vi ans(n, 0);
    rep(c1,0,n){
        ans[ANS[c1]] = c1;
        //ans[c1] = ANS[c1];
    }

    return ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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