oj.uz

Submission #1060217

# Submission time Handle Problem Language Result Execution time Memory
1060217 2024-08-15T11:39:15 Z YassineBenYounes Mechanical Doll (IOI18_doll) C++17
100 / 100
 90 ms 42276 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;
}
 
int num;
void dfs(int node, int l, int r){
    if(r < num){
        return;
    }
    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;
    }
}
 
int cur = -1;
void build(int node, int l , int r){
    if(l == r){
        return;
    }
    value[node] = cur--;
    X.pb(0);
    Y.pb(0);
    state[node] = 0;
    int md = (l+r)/2;
    if(node != 1){
        if(node % 2 == 0)X[-value[node/2]-1] = value[node];
        else Y[-value[node/2]-1] = value[node];
    }
    if(md < num){
        X[-value[node]-1] = value[1];
    }
    else{
        build(node*2, l, md);
    }
    build(node*2+1, md+1, r);
}
 
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);
    cur = -1;
    vi nodes = A;
    nodes.pb(0);
    for(int i = 0; i <= m;i++){
        C[i] = -1;
    }
    /*for(int x : nodes){
        cout << x << endl;
    }*/
    int k = _count(nodes.size());
    int n = (1 << k);
    num = n - nodes.size();
    build(1, 0, n-1);
    v.clear();
    for(int i = 0; i < n;i++){
        dfs(1, 0, n-1);
    }
    /*for(int x : v){
        cout << x << endl;
    }*/
    int ind = 0;
    for(int x : v){
        int node = x/2;
        if(x % 2 == 0){
            X[-value[node]-1] = nodes[ind];
            //cout << value[node] << " X " << graph[i][ind] << endl;
            ind++;
        }
        else{
            Y[-value[node]-1] = nodes[ind];
            //cout << value[node] << " Y " << graph[i][ind] << endl;
            ind++;
        } 
    }
    answer(C, X, Y);
}
/*
int32_t main(){
    init();
    speed;
    create_circuit(5, {1, 2, 1, 2, 1, 2, 1, 5, 1});
}*/
 
/*
    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 4 ms 26456 KB Output is correct
2 Correct 39 ms 34876 KB Output is correct
3 Correct 34 ms 34788 KB Output is correct
4 Correct 5 ms 26456 KB Output is correct
5 Correct 10 ms 27616 KB Output is correct
6 Correct 50 ms 37916 KB Output is correct
7 Correct 4 ms 26456 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26456 KB Output is correct
2 Correct 39 ms 34876 KB Output is correct
3 Correct 34 ms 34788 KB Output is correct
4 Correct 5 ms 26456 KB Output is correct
5 Correct 10 ms 27616 KB Output is correct
6 Correct 50 ms 37916 KB Output is correct
7 Correct 4 ms 26456 KB Output is correct
8 Correct 57 ms 37364 KB Output is correct
9 Correct 61 ms 38644 KB Output is correct
10 Correct 85 ms 42276 KB Output is correct
11 Correct 4 ms 26460 KB Output is correct
12 Correct 4 ms 26596 KB Output is correct
13 Correct 4 ms 26588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26456 KB Output is correct
2 Correct 39 ms 34876 KB Output is correct
3 Correct 34 ms 34788 KB Output is correct
4 Correct 5 ms 26456 KB Output is correct
5 Correct 10 ms 27616 KB Output is correct
6 Correct 50 ms 37916 KB Output is correct
7 Correct 4 ms 26456 KB Output is correct
8 Correct 57 ms 37364 KB Output is correct
9 Correct 61 ms 38644 KB Output is correct
10 Correct 85 ms 42276 KB Output is correct
11 Correct 4 ms 26460 KB Output is correct
12 Correct 4 ms 26596 KB Output is correct
13 Correct 4 ms 26588 KB Output is correct
14 Correct 79 ms 40736 KB Output is correct
15 Correct 53 ms 35824 KB Output is correct
16 Correct 79 ms 39828 KB Output is correct
17 Correct 5 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 90 ms 41160 KB Output is correct
21 Correct 4 ms 26460 KB Output is correct
22 Correct 4 ms 26460 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26460 KB Output is correct
2 Correct 49 ms 34524 KB Output is correct
3 Correct 46 ms 34408 KB Output is correct
4 Correct 65 ms 37528 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26460 KB Output is correct
2 Correct 49 ms 34524 KB Output is correct
3 Correct 46 ms 34408 KB Output is correct
4 Correct 65 ms 37528 KB Output is correct
5 Correct 80 ms 40480 KB Output is correct
6 Correct 77 ms 40020 KB Output is correct
7 Correct 77 ms 40096 KB Output is correct
8 Correct 71 ms 39580 KB Output is correct
9 Correct 49 ms 34476 KB Output is correct
10 Correct 69 ms 38808 KB Output is correct
11 Correct 71 ms 39204 KB Output is correct
12 Correct 47 ms 35896 KB Output is correct
13 Correct 58 ms 35828 KB Output is correct
14 Correct 54 ms 36084 KB Output is correct
15 Correct 55 ms 36340 KB Output is correct
16 Correct 6 ms 26716 KB Output is correct
17 Correct 45 ms 35912 KB Output is correct
18 Correct 47 ms 35076 KB Output is correct
19 Correct 47 ms 35788 KB Output is correct
20 Correct 69 ms 38688 KB Output is correct
21 Correct 67 ms 38692 KB Output is correct
22 Correct 66 ms 38436 KB Output is correct