oj.uz

Submission #1060185

# Submission time Handle Problem Language Result Execution time Memory
1060185 2024-08-15T11:22:16 Z YassineBenYounes Mechanical Doll (IOI18_doll) C++17
85.553 / 100
 93 ms 37772 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;
    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 n = (1 << k);
            num = n - graph[i].size();
            build(1, 0, n-1);
            C[i] = value[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] = graph[i][ind];
                    //cout << value[node] << " X " << graph[i][ind] << endl;
                    ind++;
                }
                else{
                    Y[-value[node]-1] = graph[i][ind];
                    //cout << value[node] << " Y " << graph[i][ind] << endl;
                    ind++;
                } 
            }
        }
    }
    answer(C, X, Y);
}
 
/*
    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 6 ms 24412 KB Output is correct
2 Correct 27 ms 28596 KB Output is correct
3 Correct 27 ms 28336 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 9 ms 25544 KB Output is correct
6 Correct 22 ms 30300 KB Output is correct
7 Correct 6 ms 24408 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24412 KB Output is correct
2 Correct 27 ms 28596 KB Output is correct
3 Correct 27 ms 28336 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 9 ms 25544 KB Output is correct
6 Correct 22 ms 30300 KB Output is correct
7 Correct 6 ms 24408 KB Output is correct
8 Correct 33 ms 32972 KB Output is correct
9 Correct 35 ms 33492 KB Output is correct
10 Correct 51 ms 36400 KB Output is correct
11 Correct 5 ms 26596 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 6 ms 24412 KB Output is correct
2 Correct 27 ms 28596 KB Output is correct
3 Correct 27 ms 28336 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 9 ms 25544 KB Output is correct
6 Correct 22 ms 30300 KB Output is correct
7 Correct 6 ms 24408 KB Output is correct
8 Correct 33 ms 32972 KB Output is correct
9 Correct 35 ms 33492 KB Output is correct
10 Correct 51 ms 36400 KB Output is correct
11 Correct 5 ms 26596 KB Output is correct
12 Correct 4 ms 26460 KB Output is correct
13 Correct 4 ms 26456 KB Output is correct
14 Correct 57 ms 37772 KB Output is correct
15 Correct 32 ms 32460 KB Output is correct
16 Correct 51 ms 35576 KB Output is correct
17 Correct 4 ms 26460 KB Output is correct
18 Correct 4 ms 26460 KB Output is correct
19 Correct 5 ms 26712 KB Output is correct
20 Correct 51 ms 37096 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 4 ms 26456 KB Output is correct
2 Correct 4 ms 26460 KB Output is correct
3 Correct 6 ms 26604 KB Output is correct
4 Correct 5 ms 26456 KB Output is correct
5 Correct 7 ms 26460 KB Output is correct
6 Correct 4 ms 26456 KB Output is correct
7 Correct 4 ms 26588 KB Output is correct
8 Correct 6 ms 26460 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26456 KB Output is correct
2 Correct 63 ms 34024 KB Output is correct
3 Correct 74 ms 34396 KB Output is correct
4 Correct 67 ms 36588 KB Output is correct

Subtask #6
41.5530038336 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26456 KB Output is correct
2 Correct 63 ms 34024 KB Output is correct
3 Correct 74 ms 34396 KB Output is correct
4 Correct 67 ms 36588 KB Output is correct
5 Partially correct 68 ms 37204 KB Output is partially correct
6 Partially correct 59 ms 36828 KB Output is partially correct
7 Partially correct 65 ms 36928 KB Output is partially correct
8 Partially correct 55 ms 36220 KB Output is partially correct
9 Partially correct 46 ms 34260 KB Output is partially correct
10 Partially correct 80 ms 37628 KB Output is partially correct
11 Partially correct 93 ms 35004 KB Output is partially correct
12 Partially correct 34 ms 32124 KB Output is partially correct
13 Partially correct 39 ms 33316 KB Output is partially correct
14 Partially correct 72 ms 33240 KB Output is partially correct
15 Partially correct 54 ms 33452 KB Output is partially correct
16 Partially correct 5 ms 26716 KB Output is partially correct
17 Partially correct 32 ms 31864 KB Output is partially correct
18 Partially correct 34 ms 32452 KB Output is partially correct
19 Partially correct 36 ms 31652 KB Output is partially correct
20 Partially correct 48 ms 34604 KB Output is partially correct
21 Partially correct 89 ms 34388 KB Output is partially correct
22 Partially correct 46 ms 34236 KB Output is partially correct