QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#128357#6400. Game: CelesteEnergy_is_not_overWA 216ms349640kbC++175.2kb2023-07-20 21:43:212023-07-20 21:43:34

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-20 21:43:34]
  • 评测
  • 测评结果:WA
  • 用时:216ms
  • 内存:349640kb
  • [2023-07-20 21:43:21]
  • 提交

answer

//
// Created by Barichek on 20.07.2023 14:00:52
//

#include <bits/stdc++.h>

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

#ifdef Energy_is_not_over
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 1e6+10, inf = 1000111222;

int x[max_n];
int a[max_n];

int l[max_n];
int r[max_n];

int dp[max_n];

typedef pii hash_type;

struct vertex
{
    int l,r;
    hash_type h;
};

vertex V[max_n+max_n*20];
int last_v=0;

int build_empty_tree(int l,int r)
{
    int res=last_v++;
    if (l==r){
        return res;
    }
    int m=(l+r)/2;
    V[res].l=build_empty_tree(l,m);
    V[res].r=build_empty_tree(m+1,r);
    return res;
}

const int md1=1e9+7;
const int md2=1e9+9;

const int base=12412527;

int pw_md1[max_n];
int pw_md2[max_n];

auto pw_md1_md2=[]()
{
    pw_md1[0]=1;
    pw_md2[0]=1;
    for (int i=1;i<max_n;i++){
        pw_md1[i]=1ll*pw_md1[i-1]*base%md1;
        pw_md2[i]=1ll*pw_md2[i-1]*base%md2;
    }
    return 1;
}();

hash_type combine_hashes(const hash_type& lhs, const hash_type& rhs, int right_size)
{
    pii res;
    res.fir=(1ll*lhs.fir*base%md1*pw_md1[right_size]%md1+rhs.fir)%md1;
    res.sec=(1ll*lhs.sec*base%md2*pw_md2[right_size]%md2+rhs.sec)%md2;
    return res;
}

int apply(int v,int l,int r,int pos)
{
    int res=last_v++;
    V[res]=V[v];
    if (l==r){
        V[res].h.fir++;
        V[res].h.sec++;
        return res;
    }
    int m=(l+r)/2;
    if (pos<=m){
        V[res].l=apply(V[v].l,l,m,pos);
    }
    else{
        V[res].r=apply(V[v].r,m+1,r,pos);
    }
    V[res].h=combine_hashes(V[V[res].l].h,V[V[res].r].h,r-(m+1)+1);
    return res;
}

bool better(int v1,int v2,int l,int r)
{
    if (l==r){
        LOG("compare better",l,V[v1].h.fir,V[v2].h.fir);
        return V[v1].h.fir>V[v2].h.fir;
    }
    int m=(l+r)/2;
    if (V[V[v1].r].h != V[V[v2].r].h){
        return better(V[v1].r,V[v2].r,m+1,r);
    }
    else{
        return better(V[v1].l,V[v2].l,l,m);
    }
}

void get_result(int v,int l,int r,vector<int>& res)
{
    if (l==r){
        for (int i=0;i<V[v].h.fir;i++){
            res.pb(l);
        }
        return;
    }
    int m=(l+r)/2;
    get_result(V[v].r,m+1,r,res);
    get_result(V[v].l,l,m,res);
}

void solve()
{
    int n,L,R;
    cin>>n>>L>>R;
    for (int i=0;i<n;i++){
        cin>>x[i];
    }
    for (int i=0;i<n;i++){
        cin>>a[i];
    }

    /// l[i] r[i]
    {
        int cur_l=0;
        int cur_r=-1;
        for (int i=0;i<n;i++){
            while (x[i]-x[cur_l]>R){
                cur_l++;
            }
            while (cur_r+1<i && x[i]-x[cur_r+1]>=L){
                cur_r++;
            }
            l[i]=cur_l;
            r[i]=cur_r;
            LOG(i,l[i],r[i]);
        }
    }

    for (int i=1;i<n;i++){
        if (l[i]<=r[i]){
            dp[i]=+inf;
        }
        else{
            dp[i]=-inf;
        }
    }

    deque<int> q;
    dp[0]=apply(build_empty_tree(1,n),1,n,a[0]);
    q.pb(0);
    int last_added_r=0;
    for (int i=1;i<n;i++){
        while (!q.empty() && q[0]<l[i]){
            q.pop_front();
        }
        while (last_added_r+1<=r[i]){
            last_added_r++;
            while (dp[last_added_r]!=-inf && !q.empty() && better(dp[last_added_r],dp[q.back()],1,n)){
                q.pop_back();
            }
            if (dp[last_added_r]!=-inf){
                q.push_back(last_added_r);
            }
        }
        DEBUG{
            LOG("when taking",i);
            cerr<<"q :: ";
            for (auto i:q){
                cerr<<i<<" ";
            }
            cerr<<"\n";
        };
        int buf=(dp[i]==-inf || q.empty() ? -inf : dp[q[0]]);
        if (buf!=-inf){
            buf=apply(buf,1,n,a[i]);
        }
        dp[i]=buf;
        /// 16:20

        DEBUG{
            LOG(i);
            if (dp[i]==-inf){
                LOG("-inf");
            }
            else{
                vector<int> res;
                get_result(dp[i],1,n,res);
                cerr<<"res :: ";
                for (auto i:res){
                    cerr<<i<<" ";
                }
                cerr<<"\n";
            }
        };
    }
    if (dp[n-1]==-inf){
        cout<<-1<<"\n";
    }
    else{
        vector<int> res;
        get_result(dp[n-1],1,n,res);
        cout<<len(res)<<"\n";
        for (auto i:res){
            cout<<i<<" ";
        }
        cout<<"\n";
    }
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int tests;
    cin>>tests;
    while (tests--){
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 15ms
memory: 347828kb

input:

2
5 2 3
1 2 3 4 5
5 2 3 1 4
3 1 2
1 4 7
3 3 3

output:

3
5 4 3 
-1

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 216ms
memory: 349640kb

input:

10000
57 8 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
11 16 7 7 10 13 9 14 10 1 12 4 8 13 3 20 16 7 16 19 20 8 19 7 16 6 17 13 7 19 17 11 12 17 6 3 7 8 14 2 4 15 5 18 16 7 20 9 1...

output:

7
20 19 19 14 12 11 3 
-1
6
6 5 3 2 1 1 
-1
185
20 20 20 20 20 20 20 20 19 19 19 19 19 19 19 19 19 19 19 19 18 18 18 18 18 17 17 17 17 17 17 17 17 16 16 16 16 16 16 16 16 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 14 14 14 14 14 14 14 13 13 13 13 13 13 13 13 13 12 12 12 12 12 12 12 ...

result:

wrong answer 2nd lines differ - expected: '20 20 19 14 12 11 3', found: '20 19 19 14 12 11 3 '