oj.uz

답안 #1056861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1056861 2024-08-13T11:55:26 Z shiocan Floppy (RMI20_floppy) C++17
7 / 100
 1000 ms 77052 KB 
#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
/*
    #define cin fin
    #define cout fout
    string __fname = ""; ifstream fin(__fname + ".in"); ofstream fout(__fname + ".out");
*/

#define ull unsigned long long 
#define ll long long
//#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
int mod = 1e9 + 7; 
//const int inf = 1e18;
const int N = 2e5 + 100;

#include "floppy.h"

int get(const vector<int> & v, int l, int r, vector<vector<int>> st){
    int i = 64 - __builtin_clzll(r - l + 1) - 1;

    if(v[st[i][l]] > v[st[i][r - (1 << i) + 1]])
        return st[i][l];
    return st[i][r - (1 << i) + 1];    
}

void dfs(const vector<int> & v, int l, int r, int p, vector<int> & euler, vector<vector<int>> st){
    if(l > r){
        return;
    }

    int mid = get(v, l, r, st);
    euler.push_back(mid - p);

    dfs(v, l, mid - 1, mid, euler, st);
    dfs(v, mid + 1, r, mid, euler, st);
    euler.push_back(p - mid);
}

void read_array( int subtask_id , const std :: vector<int> &v){
    int n = v.size();

    const int K = 20;
    vector<int> euler;
    vector<vector<int>> st;

    string bits = "";

    st = vector<vector<int>> (K, vector<int> (n+2, 0ll));

    for(int i = 0; i<n; i++)
        st[0][i] = i;
        
    for(int i = 1; i<K; i++)
        for(int j = 0; j + (1 << i) <= n; j++)
            if(v[st[i-1][j]] > v[st[i-1][j + (1 << (i - 1))]])
                st[i][j] = st[i-1][j];
            else
                st[i][j] = st[i-1][j + (1 << (i - 1))];
    
    // cout << m << '\n';

    dfs(v, 0, n - 1, 0, euler, st);

    // for(auto i : euler)
    //     cout << i << ' ';
    // cout << '\n';

    // cout << "YAS\n";

    for(auto i : euler){
        int x = i;

        if(x < 0)
            bits.push_back('1'), x = -x;
        else    
            bits.push_back('0');
        for(int i = 15; i >= 0; i--)
            if(((x >> i) & 1))
                bits.push_back('1');
            else    
                bits.push_back('0');
    }

    save_to_floppy(bits);
}

std :: vector<int> solve_queries ( int subtask_id,
    int N, const std :: string &bits,
    const std :: vector<int> &a,
    const std :: vector<int> &b){

    int q = a.size();
    vector<int> ans;

    int n = N;

    vector<int> euler;

    for(int i = 0; i < bits.size(); i += 17){
        int x = 0;
        int neg = 1;

        if(bits[i] == '1')
            neg = -1;

        for(int j = i + 1; j < i + 17; j++)
            if(bits[j] == '1')
                x += (1 << (16 - (j - i)));

        x *= neg;

        euler.push_back(x);
    }

    // cout << "bist_size : " << bits.size() << '\n';

    // for(auto i : euler)
    //     cout << i << ' ';
    // cout << '\n';

    int x = 0;
    vector<int> pre;
    for(int i = 0; i < euler.size() - 1; i++)
        x += euler[i], pre.push_back(x);

    // for(auto i : pre)
    //     cout << i << ' ';
    // cout << '\n';

    vector<int> tin(n, -1), tout(n, -1);

    for(int i = 0; i < pre.size(); i++){
        if(tin[pre[i]] == -1)
            tin[pre[i]] = i;

        tout[pre[i]] = i;
    }

    // cout << "tin : ";
    // for(auto i : tin)
    //     cout << i << ' ';
    // cout << '\n';
    // cout << "tout : ";
    // for(auto i : tout)
    //     cout << i << ' ';
    // cout << '\n';

    for(int i = 0; i < q; i++){
        int l = a[i], r = b[i];

        if(tin[l] > tin[r])
            swap(l, r);

        pii ele = {0, -1};
        for(int j = tin[l]; j <= tin[r]; j++){
            if(tout[pre[j]] > ele.second)
                ele = {pre[j], tout[pre[j]]};
        }

        ans.push_back(ele.first);
    }

    return ans;
}

Compilation message

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i = 0; i < bits.size(); i += 17){
      |                    ~~^~~~~~~~~~~~~
floppy.cpp:127:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int i = 0; i < euler.size() - 1; i++)
      |                    ~~^~~~~~~~~~~~~~~~~~
floppy.cpp:136:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for(int i = 0; i < pre.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
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1852 KB Output is correct
2 Correct 5 ms 1600 KB Output is correct
3 Correct 8 ms 13980 KB Output is correct
4 Correct 7 ms 8184 KB Output is correct
5 Correct 5 ms 1840 KB Output is correct

Subtask #2
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1045 ms 27584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 72.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1043 ms 77052 KB Time limit exceeded
2 Halted 0 ms 0 KB -