QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#128350#6400. Game: CelesteEnergy_is_not_overWA 181ms363548kbC++175.0kb2023-07-20 21:38:112023-07-20 21:38:12

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:38:12]
  • 评测
  • 测评结果:WA
  • 用时:181ms
  • 内存:363548kb
  • [2023-07-20 21:38:11]
  • 提交

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];

vector<int> vh[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;

hash_type combine_hashes(const hash_type& lhs, const hash_type& rhs)
{
    pii res;
    res.fir=(1ll*(lhs.fir+10)*base+(rhs.fir+100))%md1;
    res.sec=(1ll*(lhs.fir+10)*base+(rhs.fir+100))%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);
    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=0;i<n;i++){
        vh[i].clear();
    }

    for (int i=1;i<n;i++){
        if (l[i]<=r[i]){
            vh[r[i]].pb(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() || q[0]>r[i] ? -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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 20ms
memory: 363548kb

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: 181ms
memory: 363352kb

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 20 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 9th lines differ - expected: '18', found: '19'