oj.uz

Submission #989137

# Submission time Handle Problem Language Result Execution time Memory
989137 2024-05-27T15:17:29 Z steveonalex Mechanical Doll (IOI18_doll) C++17
47 / 100
 69 ms 15924 KB 
#include <bits/stdc++.h>
#include "doll.h"
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

void create_circuit(int m, vector<int> a);
namespace Grader{
    int n, m;
    vector<int> a;
    void answer(vector<int> C, vector<int> X, vector<int> Y){
        cout << "C: ";
        printArr(C);
        cout << "X: ";
        printArr(X); 
        cout << "Y: ";
        printArr(Y);

        if (X.size() > n * 2) {
            cout << "Wrong answer! (switch limit exceeded)\n";
            return;
        } 

        cout << "Validating...\n";
        int ball = 0;
        vector<int> ans;
        vector<bool> state(X.size());
        while(ball != 0 || ans.empty()){
            cout << "Ball: " << ball << endl;
            if (ball > 0) ans.push_back(ball);
            if (ball >= 0){
                ball = C[ball];
            }
            else {
                int cur = (-ball) - 1;
                if (state[cur]){
                    state[cur] = false;
                    ball = Y[cur];
                }
                else{
                    state[cur] = true;
                    ball = X[cur];
                }
            }
        }

        if (ans != a) cout << "Wrong answer! (incorrect sequence produced)\n";
        else if (*max_element(ALL(state)) == 1) cout << "Wrong answer! (there exists an Y switch)\n";
        else cout << "Correct answer!\n";
        cout << "Switch used: " << X.size() << "\n";
    }

    void solve(){
        cin >> n >> m;
        a = vector<int>(n);
        for(int i = 0; i<n; ++i) cin >> a[i];

        create_circuit(m, a);
    }

}

// using namespace Grader;

void toss(vector<int> &a){
    int n = a.size();
    vector<int> st(n*2);

    for(int i: a){
        int idx = 1;
        while(idx < n){
            if (!st[idx]){
                st[idx] = 1;
                idx = idx * 2;
            }
            else{
                st[idx] = 0;
                idx = idx * 2 + 1;
            }
        }
        st[idx] = i;
    }

    for(int i = n; i<n*2; ++i) a[i-n] = st[i];
}

void create_circuit(int m, vector<int> a) {
    vector<int> C(m+1, 0);
    vector<int> X, Y;

    int n = a.size();
    for(int i = 1; i<=m; ++i) C[i] = -1;
    C[0] = a[0];

    a.erase(a.begin());

    int aim = MASK(logOf(a.size()) + 1);
    while(a.size() < aim) a.push_back(-1);
    a.back() = 0;

    int k = a.size();
    toss(a);

    int cur = 0;
    vector<int> mariana(k);
    for(int i = 1; i<k; ++i) mariana[i] = --cur;

    for(int j: a) mariana.push_back(j);
    for(int i = 1; i<k; ++i){
        X.push_back(mariana[i * 2]);
        Y.push_back(mariana[i * 2 + 1]);
    }
    answer(C, X, Y);
}


// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
//     solve();
 
//     return 0;
// }

Compilation message

doll.cpp: In function 'void Grader::answer(std::vector<int>, std::vector<int>, std::vector<int>)':
doll.cpp:60:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |         if (X.size() > n * 2) {
      |             ~~~~~~~~~^~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:139:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  139 |     while(a.size() < aim) a.push_back(-1);
      |           ~~~~~~~~~^~~~~
doll.cpp:132:9: warning: unused variable 'n' [-Wunused-variable]
  132 |     int n = a.size();
      |         ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Output is partially correct
2 Correct 31 ms 7696 KB Output is correct
3 Partially correct 58 ms 14148 KB Output is partially correct
4 Partially correct 60 ms 14900 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Output is partially correct
2 Correct 31 ms 7696 KB Output is correct
3 Partially correct 58 ms 14148 KB Output is partially correct
4 Partially correct 60 ms 14900 KB Output is partially correct
5 Partially correct 69 ms 15772 KB Output is partially correct
6 Partially correct 68 ms 15672 KB Output is partially correct
7 Partially correct 64 ms 15924 KB Output is partially correct
8 Partially correct 62 ms 15664 KB Output is partially correct
9 Partially correct 55 ms 14144 KB Output is partially correct
10 Partially correct 64 ms 15544 KB Output is partially correct
11 Partially correct 63 ms 15156 KB Output is partially correct
12 Partially correct 56 ms 14408 KB Output is partially correct
13 Correct 35 ms 8276 KB Output is correct
14 Partially correct 60 ms 14828 KB Output is partially correct
15 Partially correct 63 ms 14828 KB Output is partially correct
16 Partially correct 2 ms 860 KB Output is partially correct
17 Correct 32 ms 8052 KB Output is correct
18 Correct 33 ms 8040 KB Output is correct
19 Partially correct 55 ms 14404 KB Output is partially correct
20 Partially correct 62 ms 15420 KB Output is partially correct
21 Partially correct 61 ms 15152 KB Output is partially correct
22 Partially correct 65 ms 15164 KB Output is partially correct