oj.uz

Submission #295778

# Submission time Handle Problem Language Result Execution time Memory
295778 2020-09-09T23:08:53 Z fivefourthreeone Mechanical Doll (IOI18_doll) C++17
100 / 100
 118 ms 12020 KB 
#include "doll.h"
//#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(auto i=(a);i<(b); ++i)
#define uwu(i,a, b) for(auto i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
 
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 1<<19;
int n, m;
int temp[mxN];
int idx[mxN];
void create_circuit(int M, vector<int> a) {
    m = M;
    a.senpai(0);
    n = a.size();
    int k = 1;
    while(k < n) {
        k<<=1;
    }
    owo(i, 0, k) {
        temp[i + k]=mxN;
    }
    int tt = 0;
    owo(i, 0, k) {
        idx[i] = idx[i>>1];
        if(i&1) {
            idx[i]|=k;
        }
        idx[i]>>=1;
        if(idx[i] > k-n-1)  temp[idx[i] + k] = a[tt++];
    }
    vector<int> x, y;
    int cnt = 0;
    for(int i=k; --i;) {
        int left = i<<1;
        int right = i<<1|1;
        if(temp[left]^temp[right]) {
            temp[i] = --cnt;
            x.senpai(temp[left]);
            y.senpai(temp[right]);
        }else {
            temp[i] = temp[left];
        }
    }
    owo(i, 0, -cnt) {
        if(x[i]==mxN) {
            x[i] = temp[1];
        }
        if(y[i]==mxN) {
            y[i] = temp[1];
        }
    }
    vector<int> c(m+1, temp[1]);
    answer(c, x, y);
}

Compilation message

doll.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
doll.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 39 ms 5992 KB Output is correct
3 Correct 33 ms 5656 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 50 ms 7464 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 39 ms 5992 KB Output is correct
3 Correct 33 ms 5656 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 50 ms 7464 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 73 ms 8876 KB Output is correct
9 Correct 67 ms 9556 KB Output is correct
10 Correct 97 ms 12020 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 39 ms 5992 KB Output is correct
3 Correct 33 ms 5656 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 50 ms 7464 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 73 ms 8876 KB Output is correct
9 Correct 67 ms 9556 KB Output is correct
10 Correct 97 ms 12020 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 83 ms 11164 KB Output is correct
15 Correct 54 ms 8192 KB Output is correct
16 Correct 118 ms 10872 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 110 ms 11532 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 19 ms 4404 KB Output is correct
3 Correct 20 ms 4296 KB Output is correct
4 Correct 29 ms 4920 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 19 ms 4404 KB Output is correct
3 Correct 20 ms 4296 KB Output is correct
4 Correct 29 ms 4920 KB Output is correct
5 Correct 81 ms 10612 KB Output is correct
6 Correct 88 ms 10252 KB Output is correct
7 Correct 101 ms 10356 KB Output is correct
8 Correct 87 ms 10012 KB Output is correct
9 Correct 40 ms 7512 KB Output is correct
10 Correct 72 ms 9256 KB Output is correct
11 Correct 87 ms 9516 KB Output is correct
12 Correct 54 ms 8740 KB Output is correct
13 Correct 56 ms 7752 KB Output is correct
14 Correct 53 ms 7888 KB Output is correct
15 Correct 55 ms 8120 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 72 ms 7108 KB Output is correct
18 Correct 67 ms 8632 KB Output is correct
19 Correct 48 ms 8632 KB Output is correct
20 Correct 73 ms 9724 KB Output is correct
21 Correct 73 ms 9660 KB Output is correct
22 Correct 90 ms 9652 KB Output is correct