oj.uz

Submission #484015

# Submission time Handle Problem Language Result Execution time Memory
484015 2021-11-01T22:35:17 Z gmyu Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 3 ms 460 KB 
/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/IOI16_messy
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 300007
#define MAXE 100007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
    bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

bool debug=false;

/** use divide and conquer
 *  we add elements the region of interest is 0. For the first half of this region, we flip 0 -> 1 one at a time
 *  then we do the check, we binary check whether that elements is in the left or right
 */
#include "messy.h"
vi p;

void dnc_add(int l, int r, int n){
    if (l>r) return;
    if (l==r) return;

    if(debug) cout << "range " << l << " - " << r << endl;
    string s = "";
    for (int i=0;i<n;i++)
        s += (l<=i && i <=r) ? "0" : "1";

    int m = (l+r)/2;
    for (int i=l;i<=m;i++){  //
        s[i] = '1';
        add_element(s);
        if(debug) cout << "  .. add " << s << endl;
        s[i] = '0';
    }
    dnc_add(l, m, n); dnc_add(m+1, r, n);
}

void dnc_check(int l, int r, int n, vi plist){
    if(plist.empty()) return;
    if(l>r) return;

    if(debug) {
        cout << "search range " << l << " - " << r << endl << "  ";
        for(auto i : plist) cout << i << " ";
        cout << endl;
    }

    if (l==r){
        p[plist[0]] = l; return;
    }

    string s(n, '1');
    for (auto i : plist) s[i] = '0';

    vector<int> L, R;
    L.clear(); R.clear();
    for (auto i : plist){
        s[i] = '1';
        if (check_element(s)) L.pb(i);
        else R.pb(i);
        s[i] = '0';
    }

    int m = (l+r)/2;
    dnc_check(l, m, n, L); dnc_check(m+1, r, n, R);
}

vi restore_permutation(int n, int w, int r) {
    p.resize(n);
    dnc_add(0, n-1, n);
    compile_set();

    if(debug) cout << "now find p" << endl;
    vi idx;
    for (int i=0;i<n;i++) idx.pb(i);
    dnc_check(0, n-1, n, idx);

    return p;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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