oj.uz

Submission #989516

# Submission time Handle Problem Language Result Execution time Memory
989516 2024-05-28T08:50:15 Z steveonalex Mechanical Doll (IOI18_doll) C++17
100 / 100
 184 ms 26756 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 << n << "\n";
 
        if (X.size() > n * 2) {
            cout << "Wrong answer! (switch limit exceeded)\n";
            exit(1);
        } 
 
        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";
            return;
        }
        exit(1);
    }
 
    void solve(){
        // cin >> n >> m;
        n = rngesus(1, 1024), m = rngesus(1, 1024);
        a = vector<int>(n);
        // for(int i =0; i<n; ++i) cin >> a[i];
        for(int i = 0; i<n; ++i) a[i] = rngesus(1, m);
 
        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 k = MASK(logOf(a.size()) + 1);
    vector<int> perm(k);
    for(int i = 0; i<k; ++i) perm[i] = i;
    a.push_back(0);
    n = a.size();
 
    toss(perm);
 
    vector<int> b;
    for(int i = k-n; i < k; ++i) b.push_back(perm[i]);
    sort(ALL(b));
    map<int, int> mp;
    for(int i = 0; i<b.size(); ++i)
        mp[b[i]] = a[i];
 
    vector<int> kus(k, -1);
    for(int i = k-n; i<k; ++i) kus[i] = mp[perm[i]];
 
    int cur = 0;
    vector<int> mariana(k);
    for(int j: kus) mariana.push_back(j);
    mariana[1] = --cur;
 
    vector<int> check(mariana.size());
    for(int i = k; i<k*2; ++i) if (mariana[i] == -1) check[i] = 1;
    int ma = 0;
    for(int i = k-1; i>=1; --i) {
        if (check[i * 2] && check[i * 2 + 1]){
            check[i] = check[i * 2] + 1;
        }
        maximize(ma, check[i]);
    }
 
    for(int i = 2; i<k; ++i){
        if (check[i] == 0){
            mariana[i] = --cur;
        }
        else mariana[i] = -1;
    }
 
    while(X.size() < -cur){
        X.push_back(0);
        Y.push_back(0);
    }
 
    for(int i = 1; i<k; ++i) if (check[i] == 0){
        int pos = -mariana[i] - 1;
        X[pos] = mariana[i * 2];
        Y[pos] = mariana[i * 2 + 1];
    }
 
    
    answer(C, X, Y);
}
 
 
// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
//     int t; cin >> t;
//     for(int iteration = 1; iteration <= t; ++iteration)
//     solve();
 
//     return 0;
// }

Compilation message

doll.cpp: In function 'void Grader::answer(std::vector<int>, std::vector<int>, std::vector<int>)':
doll.cpp:55:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |         if (X.size() > n * 2) {
      |             ~~~~~~~~~^~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:152:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for(int i = 0; i<b.size(); ++i)
      |                    ~^~~~~~~~~
doll.cpp:180:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  180 |     while(X.size() < -cur){
      |           ~~~~~~~~~^~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 43 ms 9564 KB Output is correct
3 Correct 46 ms 10320 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 77 ms 14028 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 43 ms 9564 KB Output is correct
3 Correct 46 ms 10320 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 77 ms 14028 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 82 ms 16796 KB Output is correct
9 Correct 95 ms 19644 KB Output is correct
10 Correct 168 ms 26756 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 43 ms 9564 KB Output is correct
3 Correct 46 ms 10320 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 77 ms 14028 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 82 ms 16796 KB Output is correct
9 Correct 95 ms 19644 KB Output is correct
10 Correct 168 ms 26756 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 159 ms 26416 KB Output is correct
15 Correct 99 ms 19552 KB Output is correct
16 Correct 157 ms 26224 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 436 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 166 ms 26508 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 75 ms 15924 KB Output is correct
3 Correct 86 ms 19304 KB Output is correct
4 Correct 154 ms 25164 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 75 ms 15924 KB Output is correct
3 Correct 86 ms 19304 KB Output is correct
4 Correct 154 ms 25164 KB Output is correct
5 Correct 160 ms 26004 KB Output is correct
6 Correct 154 ms 26076 KB Output is correct
7 Correct 157 ms 26164 KB Output is correct
8 Correct 153 ms 26032 KB Output is correct
9 Correct 105 ms 19272 KB Output is correct
10 Correct 156 ms 25784 KB Output is correct
11 Correct 170 ms 25472 KB Output is correct
12 Correct 86 ms 19112 KB Output is correct
13 Correct 76 ms 16456 KB Output is correct
14 Correct 90 ms 19524 KB Output is correct
15 Correct 87 ms 19524 KB Output is correct
16 Correct 3 ms 856 KB Output is correct
17 Correct 85 ms 16200 KB Output is correct
18 Correct 77 ms 16196 KB Output is correct
19 Correct 90 ms 19292 KB Output is correct
20 Correct 166 ms 25740 KB Output is correct
21 Correct 184 ms 25500 KB Output is correct
22 Correct 159 ms 25652 KB Output is correct