oj.uz

Submission #776039

# Submission time Handle Problem Language Result Execution time Memory
776039 2023-07-07T08:54:12 Z Magikarp4000 Mechanical Doll (IOI18_doll) C++17
53 / 100
 113 ms 25896 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 = 4e5+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 6 ms 9636 KB Output is correct
2 Correct 22 ms 13512 KB Output is correct
3 Correct 19 ms 13124 KB Output is correct
4 Correct 4 ms 9676 KB Output is correct
5 Correct 12 ms 10956 KB Output is correct
6 Correct 28 ms 14992 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9636 KB Output is correct
2 Correct 22 ms 13512 KB Output is correct
3 Correct 19 ms 13124 KB Output is correct
4 Correct 4 ms 9676 KB Output is correct
5 Correct 12 ms 10956 KB Output is correct
6 Correct 28 ms 14992 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 40 ms 15940 KB Output is correct
9 Correct 46 ms 16324 KB Output is correct
10 Correct 59 ms 19644 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9636 KB Output is correct
2 Correct 22 ms 13512 KB Output is correct
3 Correct 19 ms 13124 KB Output is correct
4 Correct 4 ms 9676 KB Output is correct
5 Correct 12 ms 10956 KB Output is correct
6 Correct 28 ms 14992 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 40 ms 15940 KB Output is correct
9 Correct 46 ms 16324 KB Output is correct
10 Correct 59 ms 19644 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct
14 Correct 69 ms 21464 KB Output is correct
15 Correct 40 ms 15660 KB Output is correct
16 Correct 63 ms 18484 KB Output is correct
17 Correct 4 ms 9600 KB Output is correct
18 Correct 4 ms 9596 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 63 ms 20132 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 5 ms 9600 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9684 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 5 ms 9684 KB Output is partially correct
2 Correct 63 ms 15840 KB Output is correct
3 Partially correct 90 ms 17816 KB Output is partially correct
4 Partially correct 91 ms 19572 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 9684 KB Output is partially correct
2 Correct 63 ms 15840 KB Output is correct
3 Partially correct 90 ms 17816 KB Output is partially correct
4 Partially correct 91 ms 19572 KB Output is partially correct
5 Partially correct 87 ms 23212 KB Output is partially correct
6 Partially correct 84 ms 24492 KB Output is partially correct
7 Partially correct 83 ms 24076 KB Output is partially correct
8 Partially correct 85 ms 25128 KB Output is partially correct
9 Partially correct 83 ms 19500 KB Output is partially correct
10 Partially correct 113 ms 24856 KB Output is partially correct
11 Partially correct 92 ms 25896 KB Output is partially correct
12 Partially correct 61 ms 19884 KB Output is partially correct
13 Partially correct 55 ms 18440 KB Output is partially correct
14 Partially correct 56 ms 18060 KB Output is partially correct
15 Partially correct 52 ms 17704 KB Output is partially correct
16 Partially correct 6 ms 9940 KB Output is partially correct
17 Partially correct 50 ms 17068 KB Output is partially correct
18 Partially correct 50 ms 17092 KB Output is partially correct
19 Partially correct 51 ms 17628 KB Output is partially correct
20 Partially correct 65 ms 21168 KB Output is partially correct
21 Partially correct 87 ms 23432 KB Output is partially correct
22 Partially correct 61 ms 20320 KB Output is partially correct