Submission #1056932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056932		ssense	Floppy (RMI20_floppy)	C++14	0 / 100	124 ms	13428 KiB

floppy

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include "floppy.h"
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <limits.h>
#include <cassert>
 
#define fr first
#define sc second
 
using namespace std;

#define NMAX 100000
#define MMAX 100000

// int subtask_id, N, M;
// std::vector<int> v, sorted_v;
// std::vector<int> a, b;
// std::vector<int> correct_answers;

// // Print score to stdout and exit.
// void score_and_exit(const double pts, const char *verdict) {
//     fprintf(stderr, "%s", verdict);
//     fprintf(stdout, "%f", pts);
//     exit(0);
// }

// // Contestant sent too many bits.
// void too_many_bits() {
//     score_and_exit(0, "Too many stored bits!");
// }

// // Contestant did not send any bits.
// void misformatted_stored_bits() {
//     score_and_exit(0, "Misformatted stored bits or save_to_floppy not called!");
// }

// // Contestant did not call the answer function.
// void answer_not_provided() {
//     score_and_exit(0, "Answer not provided!");
// }

// // Contestant sent a wrong answer.
// void wrong_answer() {
//     score_and_exit(0, "Wrong answer to query!");
// }

// // Contestant sent a correct answer.
// void correct_answer() {
//     score_and_exit(1, "OK!");
// }

// void read_test() {
//     assert(scanf("%d", &subtask_id) == 1);
//     assert(scanf("%d%d", &N, &M) == 2);
//     assert(1 <= N && N <= NMAX);
//     assert(0 <= M && M <= MMAX);
//     v.resize(N);
//     for (int i = 0; i < N; ++i) {
//         assert(scanf("%d", &v[i]) == 1);
//     }

//     // Check all values are distinct.
//     sorted_v.resize(N);
//     for (int i = 0; i < N; ++i) {
//         sorted_v[i] = v[i];
//     }
//     std::sort(sorted_v.begin(), sorted_v.end());
//     for (int i = 0; i + 1 < N; ++i) {
//         assert(sorted_v[i] < sorted_v[i + 1]);
//     }

//     a.resize(M);
//     b.resize(M);
//     correct_answers.resize(M);
//     for (int i = 0; i < M; ++i) {
//         assert(scanf("%d%d%d", &a[i], &b[i], &correct_answers[i]) == 3);
//         assert(0 <= a[i] && a[i] <= correct_answers[i] &&
//               correct_answers[i] <= b[i] && b[i] < N);
//     }
// }

int leftc[NMAX], rightc[NMAX];

int par[18][NMAX], depth[NMAX];

int timer = 0;

void dfs_1(int u, const string &bits)
{
    if(bits[2*u] == '1')
    {
        int new_node = timer++;
        par[0][new_node] = u;
        leftc[u] = new_node;
        depth[new_node] = depth[u]+1;
        dfs_1(new_node, bits);
    }
    if(bits[2*u+1] == '1')
    {
        int new_node = timer++;
        par[0][new_node] = u;
        rightc[u] = new_node;
        depth[new_node] = depth[u]+1;
        dfs_1(new_node, bits);
    }
}

int jump(int a, int l)
{
    for(int i = 0; i < 18; i++)
    {
        if((l&(1<<i)) != 0)
        {
            a = par[i][a];
        }
    }
    return a;
}

int lca(int a, int b)
{
    if(depth[a] < depth[b])
    {
        swap(a, b);
    }
    a = jump(a, depth[a]-depth[b]);
    if(a == b)
    {
        return a;
    }
    for(int i = 17; i >= 0; i--)
    {
        if(par[i][a] != par[i][b])
        {
            a = par[i][a];
            b = par[i][b];
        }
    }
    return par[0][a];
}

int trans[NMAX], inv_trans[NMAX];

int code = 0;

void dfs_2(int u)
{
    if(leftc[u] != -1)
    {
        dfs_2(leftc[u]);
    }
    trans[u] = code;
    inv_trans[code] = u;
    code++;
    if(rightc[u] != -1)
    {
        dfs_2(rightc[u]);
    }
}

vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b)
{
    for(int i = 0; i <= n; i++)
    {
        leftc[i] = -1;
        rightc[i] = -1;
        par[0][i] = -1;
    }
    dfs_1(0, bits);
    // cout << "DEPTH: " << endl;
    // for(int i = 0; i < n; i++)
    // {
    //     cout << depth[i] << " ";
    // }
    // cout << endl;
    dfs_2(0);
    // cout << "TRANS: " << endl;
    // for(int i = 0; i < n; i++)
    // {
    //     cout << trans[i] << " ";
    // }
    // cout << endl;
    vector<int> answers;
    // cout << "ANSWERS: " << endl;
    for(int i = 0; i < a.size(); i++)
    {
        // cout << "A[i]: " << inv_trans[a[i]] << " B[i]: " << inv_trans[b[i]] << " LCA: " << lca(inv_trans[a[i]], inv_trans[b[i]]) << endl;
        answers.push_back(trans[lca(inv_trans[a[i]], inv_trans[b[i]])]);
        cout << answers.back() << endl;
    }
    return answers;
}

// void save_to_floppy(const std::string &bits) {
//     std::vector<int> contestant_answers = solve_queries(subtask_id, N, bits, a, b);
//     for (int i = 0; i < M; ++i) {
//         if (contestant_answers[i] != correct_answers[i]) {
//             wrong_answer();
//         }
//     }
//     correct_answer();
//     exit(0);
// }

void read_array(int subtask_id, const vector<int> &v)
{
    int n = v.size();
    int rc[n], lc[n], p[n];
    for(int i = 0; i < n; i++)
    {
        rc[i] = -1;
        lc[i] = -1;
        p[i] = -1;
    }
    int root = 0;
    for(int i = 1; i < n; i++)
    {
        int last_val = i-1;
        while(last_val != -1)
        {
            if(-v[last_val] < -v[i])
            {
                lc[i] = rc[last_val];
                rc[last_val] = i;
                p[i] = last_val;
                p[lc[i]] = i;
                break;
            }
            last_val = p[last_val];
        }
        if(last_val == -1)
        {
            lc[i] = root;
            p[root] = i;
            root = i;
        }
    }
    string bits = "";
    stack<int> s;
    s.push(root);
    while(!s.empty())
    {
        int nw = s.top();
        s.pop();
        string bruh = "00";
        if(rc[nw] != -1)
        {
            bruh[1] = '1';
            s.push(rc[nw]);
        }
        if(lc[nw] != -1)
        {
            bruh[0] = '1';
            s.push(lc[nw]);
        }
        bits+=bruh;
    }
    // cout << bits << endl;
    save_to_floppy(bits);
}

// int main(int argc, char **argv) {
//     // Read input data.
//     read_test();

//     // Send subtask_id, v.
//     read_array(subtask_id, v);
    
//     answer_not_provided();
//     return 0;
// }

 
/*
3
4 10
40 20 30 10
0 0 0
0 1 0
0 2 0
0 3 0
1 1 1
1 2 2
1 3 2
2 2 2
2 3 2
3 3 3
*/
 
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/

Compilation message (stderr)

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:200:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |     for(int i = 0; i < a.size(); i++)
      |                    ~~^~~~~~~~~~
stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     if (query_answers.size() != M) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 21
• Subtask 3: 0 / 72