제출 #1219408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219408		KindaGoodGames	Floppy (RMI20_floppy)	C++20	100 / 100	72 ms	6076 KiB

floppy

#pragma GCC optimize("O3, unroll-loops, Ofast")
#include <stdlib.h>
#include <string.h>
#include<bits/stdc++.h>

#include "floppy.h"
#define pii pair<int,int>

using namespace std;
int B = 0;
int INF = numeric_limits<int>::max()/2;

struct SegmentTree{
    vector<pii> S;
    int len = 1;

    SegmentTree(vector<int>arr){
        int n = arr.size();
        while(len < n) len <<= 1;
        
        S.resize(2*len, {-INF,-1});
        for(int i = 0; i < n;i++){
            S[i+len] = {arr[i],i};
        }

        for(int i = len-1; i > 0; i--){
            S[i] = max(S[i*2],S[i*2+1]);
        }
    }

    pii query(int ql, int qr, int l = 0, int r = -2, int i = 1){
        if(r == -2) r = len;
        if(ql <= l && r <= qr) return S[i];
        if(r <= ql || qr <= l) return {-INF,-1};
    
        int mid = (l+r)/2;
        return max(query(ql,qr,l,mid,i*2),query(ql,qr,mid,r,i*2+1));
    }
};

void build(int l, int r, SegmentTree& seg, string& bits){
    if(l == r){
        bits += "00";
        return;
    } 

    pii res = seg.query(l,r+1);
    if(res.second == l){
        bits += "01";
        build(l+1, r, seg, bits);
    }else if(res.second == r){
        bits += "10";
        build(l, r-1, seg, bits); 
    }else{ 
        bits += "11";
        build(l, res.second-1, seg, bits); 
        build(res.second+1, r, seg, bits); 
    }
}

void read_array(int subtask_id, const std::vector<int> &arr) { 
    vector<int >v = arr;
    int n =v.size();
     
    string bits = "";
    
    SegmentTree seg(v);
    build(0,n-1,seg,bits);

    cerr << bits<<endl;
    save_to_floppy(bits);
}
 
int counter = 0;
struct Node{
    int v;
    int l = -1, r = -1;
    int sz = 1;
    int lsz = 0, rsz= 0;
};
vector<Node> cart;
 
void reconstruct(string& bits){
    bool b1 = bits[counter] == '1';     
    bool b2 = bits[counter+1] == '1';
    counter += 2;
    
    int v = cart.size();
    cart.push_back(Node{});
    if(b1){
        cart[v].l = cart.size();
        reconstruct(bits);
        cart[v].sz += cart[cart[v].l].sz; 
        cart[v].lsz = cart[cart[v].l].sz; 
    }
    if(b2){
        cart[v].r = cart.size();
        reconstruct(bits);
        cart[v].sz += cart[cart[v].r].sz;
        cart[v].rsz = cart[cart[v].r].sz;
    }
}

void buildInd(int v, int l, int r){
    cart[v].v = cart[v].lsz + l;

    if(cart[v].l != -1){
        buildInd(cart[v].l, l, cart[v].v-1);
    }
    if(cart[v].r != -1){
        buildInd(cart[v].r,cart[v].v+1, r);
    }
} 

std::vector<int> solve_queries(int subtask_id, int N, const std::string &input, const std::vector<int> &a, const std::vector<int> &b) { 
    int n = N; 
    string bits = input;
    B = ceil(log2(n));
    int qu = a.size();
 
    reconstruct(bits);
    buildInd(0,0,n-1);


    vector<int> arr(n);
    queue<int> q;
    q.push(0);

    int label = n+2;
    while(q.size()){
        int v = q.front();
        q.pop();

        arr[cart[v].v] = label--;
        if(cart[v].l != -1){
            q.push(cart[v].l);
        }
        if(cart[v].r != -1){
            q.push(cart[v].r);
        }
    }

    SegmentTree seg(arr);
    vector<int> answers(qu);

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

        if(l == r){
            answers[i] = l;
            continue;
        }
        pii res = seg.query(l,r+1);
        answers[i] = res.second;
    }
    return answers;
}

컴파일 시 표준 에러 (stderr) 메시지

floppy.cpp:1:47: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("O3, unroll-loops, Ofast")
      |                                               ^
floppy.cpp:1:47: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
In file included from floppy.cpp:6:
floppy.h:4:58: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
    4 | void read_array(int subtask_id, const std::vector<int> &v);
      |                                                          ^
floppy.h:4:58: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.h:4:58: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
floppy.h:4:58: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.h:6:44: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
    6 | void save_to_floppy(const std::string &bits);
      |                                            ^
floppy.h:6:44: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.h:6:44: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
floppy.h:6:44: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.h:10:57: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   10 |                                const std::vector<int> &b);
      |                                                         ^
floppy.h:10:57: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.h:10:57: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
floppy.h:10:57: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:17:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   17 |     SegmentTree(vector<int>arr){
      |                               ^
floppy.cpp:17:31: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:31:63: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   31 |     pii query(int ql, int qr, int l = 0, int r = -2, int i = 1){
      |                                                               ^
floppy.cpp:31:63: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:41:56: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   41 | void build(int l, int r, SegmentTree& seg, string& bits){
      |                                                        ^
floppy.cpp:41:56: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:61:60: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   61 | void read_array(int subtask_id, const std::vector<int> &arr) {
      |                                                            ^
floppy.cpp:61:60: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:83:30: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   83 | void reconstruct(string& bits){
      |                              ^
floppy.cpp:83:30: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:104:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  104 | void buildInd(int v, int l, int r){
      |                                  ^
floppy.cpp:104:34: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:115:133: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  115 | std::vector<int> solve_queries(int subtask_id, int N, const std::string &input, const std::vector<int> &a, const std::vector<int> &b) {
      |                                                                                                                                     ^
floppy.cpp:115:133: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]

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