oj.uz

Submission #697065

# Submission time Handle Problem Language Result Execution time Memory
697065 2023-02-08T06:12:01 Z gustjwkd1007 Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 3 ms 468 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(x, y) uniform_int_distribution<int>(x, y)(rng)

void wa();
bool check(const string& x);
void add_element(string x);
bool check_element(string x);
void compile_set();

ll mod(ll a, ll b) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    ll g = a; x = 1, y = 0;
    if(b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
    return g;
}
ll inv(ll a, ll m) {
    ll x, y; ll g = ext_gcd(a, m, x, y);
    if(g > 1) return -1;
    return mod(x, m);
}
int N;
string to_string(int s, int e){
    string re = "";
    for(int i=0; i<N; i++)
        re.append((i>=s&&i<=e)?"0":"1");
    return re;
}
void build(int s, int e){
    string base = to_string(s, e);
    if(s==e)
        return;
    int m = (s+e)/2;
    for (int i=s;i<=m;i++){
        base[i] = '1';
        add_element(base);
        base[i] = '0';
    }
    build(s, m);
    build(m+1, e);
}
vector <int> dap;
void solve(int s, int e, set <int> now){
//    cout << "solve (" << s << ", " << e << ") : " << now << "\n";
    if(s==e){
        dap[*(now.begin())]=s;
        return;
    }
    int mid = (s+e)/2;
    set <int> left, right;
    string base;
    for(int i=0;i<N;i++)
        base.append((now.find(i)!=now.end())?"0":"1");
    for(int i:now){
        base[i] = '1';
        if(check_element(base))
            left.insert(i);
        else
            right.insert(i);
        base[i] = '0';
    }
    solve(s, mid, left);
    solve(mid+1, e, right);
}

std::vector<int> restore_permutation(int n, int w, int r) {
    N = n;
    build(0, n-1);
    compile_set();
    dap.resize(n);
    set <int> now;
    for(int i=0;i<n;i++)
        now.insert(i);
    solve(0, n-1, now);
    return dap;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 8
2 Correct 1 ms 212 KB n = 8
3 Correct 1 ms 212 KB n = 8
4 Correct 1 ms 308 KB n = 8
5 Correct 1 ms 212 KB n = 8
6 Correct 1 ms 304 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 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 0 ms 300 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 0 ms 300 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 1 ms 212 KB n = 32
4 Correct 1 ms 212 KB n = 32
5 Correct 1 ms 300 KB n = 32
6 Correct 1 ms 212 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 1 ms 304 KB n = 32
9 Correct 1 ms 304 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 1 ms 212 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 1 ms 296 KB n = 32
14 Correct 1 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 304 KB n = 32
2 Correct 1 ms 212 KB n = 32
3 Correct 1 ms 304 KB n = 32
4 Correct 1 ms 212 KB n = 32
5 Correct 1 ms 212 KB n = 32
6 Correct 1 ms 212 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 1 ms 212 KB n = 32
9 Correct 1 ms 212 KB n = 32
10 Correct 1 ms 212 KB n = 32
11 Correct 1 ms 212 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 1 ms 212 KB n = 32
14 Correct 1 ms 212 KB n = 32
15 Correct 1 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 428 KB n = 128
6 Correct 3 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 428 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 428 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 432 KB n = 128
3 Correct 2 ms 428 KB n = 128
4 Correct 2 ms 468 KB n = 128
5 Correct 3 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 436 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