oj.uz

Submission #386468

# Submission time Handle Problem Language Result Execution time Memory
386468 2021-04-06T15:54:25 Z ACmachine Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 4 ms 492 KB 
#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)

const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;

template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}

template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }

std::vector<int> restore_permutation(int n, int w, int r) {
    function<void(int, int, int, int)> create_set = [&](int l, int r, int oth_l, int oth_r){
        if(l >= r) return;
        if(l + 1 == r) return; //?
        int mid = (l + r) >> 1;
        FOR(i,l, mid, 1){
            string tm(n, '0');
            tm[i] = '1';
            FOR(j, oth_l, oth_r, 1)
                tm[j] = '1';
            add_element(tm);
        }
        create_set(l, mid, mid, r);
        create_set(mid, r, l, mid);
    };
    create_set(0, n, -1, -1);
    compile_set();
    auto OR = [](string a, string b){
        string res(a.length(), '0');
        REP(i, a.length()){
            if(a[i] == '1' || b[i] == '1')
                res[i] = '1';
        }
        return res;
    };
    vector<int> ans(n, -1);
    function<void(int, int, string, string)> solve = [&](int l, int r, string to_add, string current_mapping){
        if(l >= r) return;
        if(l + 1 == r){
            REP(i, n){
                if(current_mapping[i] == '1')
                    ans[l] = i;
            }
            return;
        }
        int mid = (l + r) >> 1;
        string left_mapping = string(n, '0');
        string right_mapping = string(n, '0');
        REP(i, n){
            if(current_mapping[i] == '1'){
                string tm(n, '0');
                tm[i] = '1'; tm = OR(tm, to_add);
                if(check_element(tm)){
                    left_mapping[i] = '1';
                }
                else{
                    right_mapping[i] = '1';
                }
            }
        }
        solve(l, mid, right_mapping, left_mapping);
        solve(mid, r, left_mapping, right_mapping);
    };
    solve(0, n, string(n, '0'), string(n, '1'));
    vector<int> rev_ans(n);
    REP(i, n) rev_ans[ans[i]] = i;
    return rev_ans;
}

Compilation message

messy.cpp: In lambda function:
messy.cpp:20:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
messy.cpp:22:18: note: in expansion of macro 'FOR'
   22 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
messy.cpp:77:9: note: in expansion of macro 'REP'
   77 |         REP(i, a.length()){
      |         ^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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