oj.uz

Submission #827380

# Submission time Handle Problem Language Result Execution time Memory
827380 2023-08-16T12:03:01 Z lukameladze Mechanical Doll (IOI18_doll) C++17
9 / 100
 96 ms 36028 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define ll long long
#define pb push_back
const int MX = 3e5 + 5;
int n, p[MX], cnt[MX], cur;
int resc[MX], resx[MX], resy[MX];
vector <int> v[MX];
vector < int > lst;
void go(int idx, int val) {
    if (val == 0) {
        lst.pb(idx); lst.pb(idx);
        // cout<<"add "<<idx<<"\n";
        return ;
    }
    // cout<<idx<<" --- > "<<cur - 1<<" "<<cur - 2<<"\n";
    resx[-idx] = --cur;
    resy[-idx] = --cur;
    lst.clear();
    vector <int> lst1, lst2;
    go(resx[-idx], val - 1);
    lst1 = lst;
    lst.clear();
    go(resy[-idx], val - 1);
    for (int i = 0; i < lst.size(); i++) lst2.pb(lst1[i]), lst2.pb(lst[i]);
    lst.clear();
    lst = lst2; 
    if (val == 0) return ;
}
void create_circuit(int M, vector<int> A) {
    n = A.size();
    for (int i = 0; i < n; i++) p[i] = A[i];
    p[n] = 0;
    for (int i = 0; i < n; i++) {
        cnt[p[i]]++;
        v[p[i]].pb(p[i + 1]);
    }
    resc[0] = p[0]; // resc.size() == M + 1
    vector <int> vis(MX, 0); 
    for (int i = 1; i <= n; i++) {
        if (!cnt[i]) continue;
        int bit = 0;
        lst.clear();
        for (int j = 0;; j++) if ((1<<j) >= cnt[i]) {bit = j; break;}
        if (bit == 0) {
            resc[i] = v[i][0]; continue;
        }
        resc[i] = --cur; int st = cur;
        // cout<<i<<"       "<<bit<<"\n";
        go(cur, bit - 1);
        int rem = (1<<bit) - cnt[i];
        assert((int)lst.size() == (1<<bit));
        // cout<<"order ";
        // for (int x : lst) cout<<x<<" ";
        // cout<<"\n";
        for (int i = 0; i < rem; i++) {
            // cout<<"trigg_back"<<-lst[i]<<" "<<-st<<"\n";
            vis[-lst[i]]++;
            if (vis[-lst[i]] % 2 == 1) resx[-lst[i]] = st;
            else resy[-lst[i]] = st;
        }
        for (int j = rem; j < (int)lst.size(); j++) {
            // cout<<"trig_front"<<-lst[j]<<" "<<v[i][j - rem]<<"\n";
            vis[-lst[j]]++;
            if (vis[-lst[j]] % 2 == 1) resx[-lst[j]] = v[i][j - rem];
            else resy[-lst[j]] = v[i][j - rem];
        }
    }
    vector <int> C(M + 1, 0);
    vector<int> X(-cur + 1, 0), Y(-cur + 1, 0);
    for (int i = 0; i < M + 1; i++) C[i] = resc[i];
    // for (int i = 0; i < M + 1; i++) cout<<C[i]<<" ";
    // cout<<"\n";
    for (int i = 0; i < -cur; i++) X[i] = resx[i + 1], Y[i] = resy[i + 1];//, cout<<resx[i + 1]<<" "<<resy[i + 1]<<"\n";
    // cout<<"\n";
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void go(int, int)':
doll.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < lst.size(); i++) lst2.pb(lst1[i]), lst2.pb(lst[i]);
      |                     ~~^~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8532 KB Output is correct
2 Incorrect 22 ms 13632 KB wrong motion
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8532 KB Output is correct
2 Incorrect 22 ms 13632 KB wrong motion
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8532 KB Output is correct
2 Incorrect 22 ms 13632 KB wrong motion
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
9.0000000018 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 8508 KB Output is partially correct
2 Correct 52 ms 16100 KB Output is correct
3 Partially correct 72 ms 21664 KB Output is partially correct
4 Partially correct 78 ms 23016 KB Output is partially correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 8508 KB Output is partially correct
2 Correct 52 ms 16100 KB Output is correct
3 Partially correct 72 ms 21664 KB Output is partially correct
4 Partially correct 78 ms 23016 KB Output is partially correct
5 Partially correct 96 ms 24140 KB Output is partially correct
6 Runtime error 62 ms 36028 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -