oj.uz

Submission #1051984

# Submission time Handle Problem Language Result Execution time Memory
1051984 2024-08-10T10:54:16 Z YassineBenYounes Mechanical Doll (IOI18_doll) C++17
53 / 100
 86 ms 44456 KB 
#include<bits/stdc++.h>
#include<chrono>
#include<random>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
int dx[8] = {1, 0, 0, -1, 1, 1, -1, -1};
int dy[8] = {0, 1, -1, 0, 1, -1, -1, 1};
#define endl "\n"
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree<pii, null_type, less<pii>,rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

////////////////////Only Clear Code//////////////////////////

void usaco_problem(){
    freopen("milkvisits.in", "r", stdin);
    freopen("milkvisits.out", "w", stdout);
}

void init(){
    #ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
const int mx = 1e6+5;
const int LOG = 22;
const int inf = 1e9;
const ll mod = 1e9+7;
const int sq = 300;

#include "doll.h"
vi C;
vi X, Y;
vi graph[mx];
bool state[mx];
int value[mx];
vi v;
int _count(int n){
    int x = 0;
    int cnt = 1;
    while(cnt < n){
        cnt *=2;
        x++;
    }
    return x;
}



void dfs(int node, int l, int r){
    if(l == r){
        v.pb(node);
        return;
    }
    int md = (l+r)/2;
    if(state[node] == 0){
        dfs(node*2, l, md);
        state[node] = 1;
    }
    else{
        dfs(node*2+1, md+1, r);
        state[node] = 0;
    }
}

void create_circuit(int m, vi A){
    int N = A.size();
    C.clear();
    C.resize(m+1);
    X.clear();
    Y.clear();
    graph[0].pb(A[0]);
    for(int i = 0;(i+1) < N;i++){
        graph[A[i]].pb(A[i+1]);
    }
    graph[A[N-1]].pb(0);
    int cur = -1;
    for(int i = 0; i <= m;i++){
        if(graph[i].size() == 0)continue;
        if(graph[i].size() == 1){
            C[i] = graph[i][0];
            //cout << i << "       " << graph[i][0] << endl;
        }
        else{
            int k = _count(graph[i].size());
            int ind = 0;
            int n = (1 << k);
            for(int l = 1; l <= n-1;l++){
                value[l] = cur--;
                X.pb(0);
                Y.pb(0);
                state[l] = 0;
            }
            C[i] = value[1];
            //cout << i << " " << value[1] << endl;
            for(int l = 1; l <= ((n-1)/2);l++){
                X[-value[l]-1] = (value[l*2]);
                //cout << value[l] << " " << value[l*2] << endl;
                Y[-value[l]-1] = (value[l*2+1]);
                //cout << value[l] << " " << value[l*2+1] << endl;
            }
            v.clear();
            for(int i = 0; i < n;i++){
                dfs(1, 0, n-1);
            }
            int num = n - graph[i].size();
            for(int x : v){
                if(num > 0){
                    int node = x/2;
                    if(x % 2 == 0){
                        X[-value[node]-1] = value[1];
                        //cout << value[node] << " " << i << endl;
                    }
                    else{
                        Y[-value[node]-1] = value[1];
                        //cout << value[node] << " " << i << endl;
                    }
                    num--;
                }
                else{
                    int node = x/2;
                    if(x % 2 == 0){
                        X[-value[node]-1] = graph[i][ind];
                        //cout << value[node] << " " << graph[i][ind] << endl;
                        ind++;
                    }
                    else{
                        Y[-value[node]-1] = graph[i][ind];
                        //cout << value[node] << " " << graph[i][ind] << endl;
                        ind++;
                    }
                }
                //cout << x << endl;

            }
            //cout << endl;
        }
    }
    answer(C, X, Y);
}
/*
int32_t main(){
    init();
    speed;
    create_circuit(4, {1, 2, 1, 3, 1, 4});
}*/

/*
    NEVER GIVE UP!
    DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
    Your Guide when stuck:
    - Continue keyword only after reading the whole input
    - Don't use memset with testcases
    - Check for corner cases(n=1, n=0)
    - Check where you declare n(Be careful of declaring it globally and in main)
*/

Compilation message

doll.cpp: In function 'void usaco_problem()':
doll.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen("milkvisits.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("milkvisits.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void init()':
doll.cpp:43:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp:44:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24412 KB Output is correct
2 Correct 15 ms 28236 KB Output is correct
3 Correct 13 ms 27736 KB Output is correct
4 Correct 4 ms 24412 KB Output is correct
5 Correct 8 ms 25688 KB Output is correct
6 Correct 18 ms 29532 KB Output is correct
7 Correct 3 ms 24408 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24412 KB Output is correct
2 Correct 15 ms 28236 KB Output is correct
3 Correct 13 ms 27736 KB Output is correct
4 Correct 4 ms 24412 KB Output is correct
5 Correct 8 ms 25688 KB Output is correct
6 Correct 18 ms 29532 KB Output is correct
7 Correct 3 ms 24408 KB Output is correct
8 Correct 28 ms 32200 KB Output is correct
9 Correct 27 ms 32468 KB Output is correct
10 Correct 38 ms 35020 KB Output is correct
11 Correct 4 ms 26460 KB Output is correct
12 Correct 4 ms 26460 KB Output is correct
13 Correct 4 ms 26456 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24412 KB Output is correct
2 Correct 15 ms 28236 KB Output is correct
3 Correct 13 ms 27736 KB Output is correct
4 Correct 4 ms 24412 KB Output is correct
5 Correct 8 ms 25688 KB Output is correct
6 Correct 18 ms 29532 KB Output is correct
7 Correct 3 ms 24408 KB Output is correct
8 Correct 28 ms 32200 KB Output is correct
9 Correct 27 ms 32468 KB Output is correct
10 Correct 38 ms 35020 KB Output is correct
11 Correct 4 ms 26460 KB Output is correct
12 Correct 4 ms 26460 KB Output is correct
13 Correct 4 ms 26456 KB Output is correct
14 Correct 70 ms 36496 KB Output is correct
15 Correct 27 ms 32204 KB Output is correct
16 Correct 39 ms 35472 KB Output is correct
17 Correct 4 ms 26456 KB Output is correct
18 Correct 4 ms 26460 KB Output is correct
19 Correct 4 ms 26460 KB Output is correct
20 Correct 43 ms 36880 KB Output is correct
21 Correct 4 ms 26460 KB Output is correct
22 Correct 3 ms 26460 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 26460 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 4 ms 26460 KB Output is partially correct
2 Correct 36 ms 34900 KB Output is correct
3 Partially correct 65 ms 38516 KB Output is partially correct
4 Partially correct 66 ms 39788 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 26460 KB Output is partially correct
2 Correct 36 ms 34900 KB Output is correct
3 Partially correct 65 ms 38516 KB Output is partially correct
4 Partially correct 66 ms 39788 KB Output is partially correct
5 Partially correct 54 ms 39960 KB Output is partially correct
6 Partially correct 63 ms 41288 KB Output is partially correct
7 Partially correct 57 ms 40852 KB Output is partially correct
8 Partially correct 59 ms 41680 KB Output is partially correct
9 Partially correct 63 ms 39036 KB Output is partially correct
10 Partially correct 86 ms 44456 KB Output is partially correct
11 Partially correct 62 ms 42448 KB Output is partially correct
12 Partially correct 41 ms 36776 KB Output is partially correct
13 Partially correct 44 ms 36108 KB Output is partially correct
14 Partially correct 71 ms 35752 KB Output is partially correct
15 Partially correct 41 ms 35356 KB Output is partially correct
16 Partially correct 4 ms 26716 KB Output is partially correct
17 Partially correct 34 ms 34628 KB Output is partially correct
18 Partially correct 36 ms 34664 KB Output is partially correct
19 Partially correct 43 ms 35180 KB Output is partially correct
20 Partially correct 53 ms 37912 KB Output is partially correct
21 Partially correct 61 ms 40316 KB Output is partially correct
22 Partially correct 45 ms 37184 KB Output is partially correct