QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#128364 | #6400. Game: Celeste | Energy_is_not_over | WA | 183ms | 380316kb | C++17 | 5.2kb | 2023-07-20 21:47:13 | 2023-07-20 21:47:14 |
Judging History
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*22];
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*pw_md1[right_size]%md1+rhs.fir)%md1;
res.sec=(1ll*lhs.sec*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]);
int last_added_r=-1;
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: 20ms
memory: 379648kb
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: 183ms
memory: 380316kb
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 85th lines differ - expected: '-1', found: '2'