oj.uz

Submission #388961

# Submission time Handle Problem Language Result Execution time Memory
388961 2021-04-13T11:45:53 Z mehrdad_sohrabi Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 3 ms 516 KB 
// Black lives matter
#include <bits/stdc++.h>
#include "messy.h"
/// 500 485 462 A4
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
/*
void add_element(string x);
bool check_element (string x);
void compile_set();
*/
const int N=200;
void add(ll l,ll r,ll n){
    if (r-l<=1) return ;
    string s="";
    for (int i=0;i<l;i++) s+='1';
    for (int i=l;i<(r+l)/2;i++) s+='0';
    for (int i=(r+l)/2;i<r;i++) s+='0';
    for (int i=r;i<n;i++) s+='1';
    ll mid=(r+l)/2;
    for (int i=l;i<mid;i++){
        s[i]='1';

        add_element(s);
        s[i]='0';
    }
    add(l,mid,n);
    add(mid,r,n);
}
ll W[N];

vector <int> seg[N*4];
ll vis[N];
void solve(ll nod,ll l,ll r,ll n){
    if (r-l==1){
        if (seg[nod].size()!=1){
            cout << 1/0 << endl;
        }
        W[seg[nod][0]]=l;
        return ;
    }
    string s="";
    memset(vis,0,sizeof vis);
    for (auto u : seg[nod]) vis[u]=1;
    for (int i=0;i<n;i++){
        if (vis[i]) s+='0';
        else s+='1';
    }
    for (auto u : seg[nod]){
        s[u]='1';
        ll e=check_element(s);
      //  if (u==3) cout << s << " rfjn " << e << endl;
        if (e) seg[nod*2].pb(u);
        else seg[nod*2+1].pb(u);
        s[u]='0';
    }
    ll mid=(r+l)/2;
    solve(nod*2,l,mid,n);
    solve(nod*2+1,mid,r,n);
    return;
}
std::vector<int32_t> restore_permutation(int32_t N, int32_t w, int32_t r) {
    ll n=N;
    add(0,n,n);
    compile_set();
    for (int i=0;i<n;i++) seg[1].pb(i);
    solve(1,0,n,n);
    vector <int32_t> ans;
    for (int i=0;i<n;i++){
        ans.pb(W[i]);
    }
    return ans;
}
/*
namespace helper {

    set<string> set_;
    bool compiled = false;
    int n;
    vector<int> p;
    int w;
    int r;

    int read_int() {
        int x;
        cin >> x;
        return x;
    }

}

using namespace helper;


// A convenience function.
int get_p(int i) {
    int ret = p[i];
    return ret;
}

int32_t main() {
    n = read_int();
    w = read_int();
    r = read_int();
    p = vector<int>(n);
    for (int i = 0; i < n; i++) {
        p[i] = read_int();
    }
    vector<int32_t> answer = restore_permutation(n, w, r);

    if (answer.size() != n) {
        printf("WA\n");
        return 0;
    }
    printf("%d", answer[0]);

    for (int i = 1; i < n; i++) {
        printf(" %d", answer[i]);
    }
    printf("\n");
    return 0;
}

void wa() {
    printf("WA\n");
    exit(0);
}

bool check(const string& x) {
    if ((int)x.length() != n) {
        return false;
    }
    for (int i = 0; i < n; i++) {
        if (x[i] != '0' && x[i] != '1') {
            return false;
        }
    }
    return true;
}

void add_element(string x) {
   // cout << "udhc " <<  x << endl;
    if (--w < 0 || compiled || !check(x)) {
        wa();
    }
    set_.insert(x);
}

bool check_element(string x) {
    if (--r < 0 || !compiled || !check(x)) {
        wa();
    }
    return set_.count(x);
}

void compile_set() {
    if (compiled) {
        wa();
    }
    compiled = true;
    set<string> compiledSet;
    string compiledElement = string(n, ' ');
    for (set<string>::iterator it = set_.begin(); it != set_.end(); it++) {
        string s = *it;
        for (int i = 0; i < n; i++) {
            compiledElement[i] = s[get_p(i)];
        }
        compiledSet.insert(compiledElement);
    }
    set_ = compiledSet;
}
*/

Compilation message

messy.cpp: In function 'void solve(ll, ll, ll, ll)':
messy.cpp:48:22: warning: division by zero [-Wdiv-by-zero]
   48 |             cout << 1/0 << endl;
      |                     ~^~

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB n = 128
2 Correct 2 ms 460 KB n = 128
3 Correct 2 ms 460 KB n = 128
4 Correct 2 ms 460 KB n = 128
5 Correct 3 ms 460 KB n = 128
6 Correct 2 ms 460 KB n = 128
7 Correct 2 ms 440 KB n = 128
8 Correct 2 ms 460 KB n = 128
9 Correct 2 ms 516 KB n = 128
10 Correct 2 ms 460 KB n = 128
11 Correct 2 ms 460 KB n = 128
12 Correct 2 ms 460 KB n = 128
13 Correct 2 ms 460 KB n = 128
14 Correct 2 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 2 ms 460 KB n = 128
2 Correct 2 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 448 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 2 ms 460 KB n = 128
11 Correct 3 ms 460 KB n = 128
12 Correct 2 ms 460 KB n = 128
13 Correct 2 ms 460 KB n = 128
14 Correct 2 ms 460 KB n = 128
15 Correct 2 ms 460 KB n = 128