oj.uz

Submission #776030

# Submission time Handle Problem Language Result Execution time Memory
776030 2023-07-07T08:45:25 Z Magikarp4000 Mechanical Doll (IOI18_doll) C++17
25 / 100
 89 ms 18792 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 2e5+5;
int n,m;
vector<int> c,x,y,nxt[MAXN];
bool z[MAXN], t[MAXN];

void create_circuit(int M, vector<int> a) {
    n = a.size(), m = M;
    FOR(_,0,m+1) c.PB(0);
    c[0] = a[0];
    a.PB(0);
    FOR(i,0,n) {
        nxt[a[i]].PB(a[i+1]);
    }
    int cur = -1;
    FOR(i,0,n) {
        if (z[a[i]]) continue;
        z[a[i]] = 1;
        int cnt = nxt[a[i]].size(), start = cur;
        if (cnt == 1) {
            c[a[i]] = nxt[a[i]][0];
            continue;
        }
        c[a[i]] = cur;
        cur--;
        int tgt = x.size()+cnt-1;
        int num = 2;
        int lg = ceil(log2(cnt));
        int cnt1 = 1<<lg;
        int thrsh = 2*cnt-cnt1;
        while (num < cnt1) {
            x.PB(cur--);
            num++;
            y.PB(cur--);
            num++;
        }
        int xsz = x.size(), ysz = y.size();
        FOR(_,0,thrsh/2) {
            x.PB(-INF);
            y.PB(-INF);
        }
        FOR(_,0,cnt-thrsh) {
            x.PB(start);
            y.PB(-INF);
        }
        int ball = start, idx = 0;
        while (idx < cnt) {
            int real = -ball-1;
            ball = t[real] ? y[real] : x[real];
            if (ball == -INF) {
                if (t[real] == 0) x[real] = nxt[a[i]][idx];
                else y[real] = nxt[a[i]][idx];
                idx++;
                ball = start;
            }
            t[real] ^= 1;
        }
    }
    // FORX(u,c) cout << u << " ";
    // cout << ln;
    // FORX(u,x) cout << u << " ";
    // cout << ln;
    // FORX(u,y) cout << u << " ";
    // cout << ln;
    answer(c,x,y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:50:13: warning: unused variable 'tgt' [-Wunused-variable]
   50 |         int tgt = x.size()+cnt-1;
      |             ^~~
doll.cpp:61:13: warning: unused variable 'xsz' [-Wunused-variable]
   61 |         int xsz = x.size(), ysz = y.size();
      |             ^~~
doll.cpp:61:29: warning: unused variable 'ysz' [-Wunused-variable]
   61 |         int xsz = x.size(), ysz = y.size();
      |                             ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 21 ms 8840 KB Output is correct
3 Correct 17 ms 8452 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 9 ms 6348 KB Output is correct
6 Correct 25 ms 10268 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 21 ms 8840 KB Output is correct
3 Correct 17 ms 8452 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 9 ms 6348 KB Output is correct
6 Correct 25 ms 10268 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 36 ms 11272 KB Output is correct
9 Correct 38 ms 11644 KB Output is correct
10 Correct 55 ms 14956 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 21 ms 8840 KB Output is correct
3 Correct 17 ms 8452 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 9 ms 6348 KB Output is correct
6 Correct 25 ms 10268 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 36 ms 11272 KB Output is correct
9 Correct 38 ms 11644 KB Output is correct
10 Correct 55 ms 14956 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 67 ms 16740 KB Output is correct
15 Correct 37 ms 10960 KB Output is correct
16 Correct 56 ms 13864 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 63 ms 15344 KB Output is correct
21 Correct 2 ms 4948 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 4948 KB Output is partially correct
2 Correct 44 ms 11144 KB Output is correct
3 Partially correct 85 ms 13156 KB Output is partially correct
4 Partially correct 89 ms 14852 KB Output is partially correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 4948 KB Output is partially correct
2 Correct 44 ms 11144 KB Output is correct
3 Partially correct 85 ms 13156 KB Output is partially correct
4 Partially correct 89 ms 14852 KB Output is partially correct
5 Incorrect 81 ms 18792 KB wrong motion
6 Halted 0 ms 0 KB -