QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#841466#9915. General Symmetryzhenjianuo2025TL 1538ms54996kbC++202.2kb2025-01-03 19:18:232025-01-03 19:18:23

Judging History

This is the latest submission verdict.

  • [2025-01-03 19:18:23]
  • Judged
  • Verdict: TL
  • Time: 1538ms
  • Memory: 54996kb
  • [2025-01-03 19:18:23]
  • Submitted

answer

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
bool Mbg;
using namespace std;
#define vec vector
#define pb push_back
#define eb emplace_back
#define siz(vec) ((int)(vec).size())
#define all(vec) (vec).begin(),(vec).end()
template<class T>
void operator +=(vec<T> &a,T b){a.push_back(b);}
template<class T>
void operator --(vec<T> &a){a.pop_back();}
#define pii pair<int,int>
#define x first
#define y second
#define mp make_pair
#define exc(exp) if(exp)continue;
#define stop(exp) if(exp)break;
#define ret(exp) if(exp)return;
#define deb(var) cerr<<#var<<'='<<(var)<<"; "
#define debl(var) cerr<<#var<<'='<<(var)<<";\n"
#define ins insert
#define era erase
#define lb lower_bound
#define ub upper_bound
#define ll long long
#define inf (long long)(1e18)
template<class T>
bool Min(T &x,T y){return x>y?x=y,1:0;}
template<class T>
bool Max(T &x,T y){return x<y?x=y,1:0;}
const int mod=998244353;
void Add(int &x,int y){x=x+y<mod?x+y:x+y-mod;}
void Dec(int &x,int y){x=x>=y?x-y:x-y+mod;}
int fpm(int x,int y){
    int ans=1;for(;y;y>>=1,(x*=x)%=mod)if(y&1)(ans*=x)%=mod;return ans;
}

const int V=1e3;
int n,k,a[200002],cov[400002];

bitset<400002> bt,cons[1002];
void work(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=V;i++)cons[i][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=a[i]+k+1;j<=V;j++)cons[j][i]=1;
        for(int j=a[i]-k-1;j>=1;j--)cons[j][i]=1;
        auto FREE=(cons[a[i]]<<i)&~bt;
        for(int j=FREE._Find_first();j<=2*n;j=FREE._Find_next(j)){
            bt[j]=1;
            cov[j]=i;
        }
    }

    for(int i=2;i<=2*n;i++){
        if(!bt[i]){
            cov[i]=n+1;
        }
    }
    for(int i=2;i<=2*n;i+=2){
        cout<<2*cov[i]-i-1<<' ';
    }
    cout<<'\n';
    for(int i=3;i<=2*n;i+=2){
        cout<<2*cov[i]-i+1-2<<' ';
    }
    cout<<'\n';

}
bool Med;
signed main(){
    ios::sync_with_stdio(0),
    cin.tie(0),cout.tie(0);
    int T=1;while(T--)work();
    // cerr<<"Time: "<<clock()<<" ms;\n";
    // cerr<<"Memory: "<<abs(&Med-&Mbg)/1024.0/1024.0<<" MiB.\n";
}
/*
- CONTINUE, NON-STOPPING, FOR THE FAITH
- START TYPING IF YOU DON'T KNOW WHAT TO DO
- STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 53144kb

input:

5 0
1 2 1 2 1

output:

1 3 5 3 1 
0 0 0 0 

result:

ok 9 numbers

Test #2:

score: 0
Accepted
time: 3ms
memory: 52912kb

input:

5 1
1 2 1 3 1

output:

1 3 5 3 1 
2 2 0 0 

result:

ok 9 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 53052kb

input:

10 0
1 2 3 4 500 5 501 6 499 503

output:

1 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 

result:

ok 19 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 54996kb

input:

10 1
1 2 3 4 500 5 501 6 499 503

output:

1 1 1 1 3 3 5 1 1 1 
2 2 2 0 0 0 0 0 0 

result:

ok 19 numbers

Test #5:

score: 0
Accepted
time: 3ms
memory: 53056kb

input:

10 2
1 2 3 4 500 5 501 6 499 503

output:

1 3 3 1 3 5 5 3 1 1 
2 2 2 0 0 0 0 0 0 

result:

ok 19 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 53152kb

input:

10 10
1 2 3 4 500 5 501 6 499 503

output:

1 3 3 1 3 5 5 3 1 1 
2 4 2 0 0 0 0 0 2 

result:

ok 19 numbers

Test #7:

score: 0
Accepted
time: 1369ms
memory: 53600kb

input:

100000 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177...

result:

ok 199999 numbers

Test #8:

score: 0
Accepted
time: 1374ms
memory: 53560kb

input:

100000 0
2 1 2 1 1 1 1 1 2 1 2 1 1 1 1 1 2 1 1 2 1 2 1 2 2 1 1 1 2 2 2 2 2 1 1 2 2 1 2 1 2 2 1 1 1 2 2 2 1 2 1 2 2 1 2 1 2 1 1 2 2 2 1 2 2 2 1 1 2 2 2 2 1 1 1 1 2 1 2 2 1 2 1 1 2 2 1 1 1 2 1 2 1 2 2 2 1 2 1 1 1 2 1 2 1 2 1 1 2 1 1 2 2 1 1 2 2 1 1 2 1 2 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 2...

output:

1 3 3 1 3 11 3 1 3 17 3 1 3 9 3 1 5 1 1 3 5 5 3 1 1 1 7 1 1 3 9 3 1 1 1 1 1 3 11 3 1 1 1 7 1 1 5 1 3 7 3 1 1 3 5 5 3 1 1 1 5 1 13 1 5 1 1 1 1 3 3 1 1 3 3 1 3 3 1 1 3 3 1 1 1 1 1 5 1 3 5 5 3 1 9 1 3 3 1 9 1 3 5 9 5 3 1 1 7 1 1 1 1 1 1 1 1 1 1 3 7 3 1 3 3 1 1 3 3 1 1 3 5 9 5 3 1 3 13 3 1 3 9 3 1 5 1 1...

result:

ok 199999 numbers

Test #9:

score: 0
Accepted
time: 1360ms
memory: 53724kb

input:

100000 1
2 2 1 2 1 2 1 1 2 1 1 2 1 2 2 2 1 1 1 1 2 2 2 1 1 2 1 2 2 2 2 2 1 1 2 2 2 1 2 2 2 2 2 1 2 1 2 2 1 2 1 2 2 1 2 2 1 2 2 1 1 1 2 1 1 1 2 1 2 2 1 2 2 2 2 1 2 2 1 2 2 2 1 1 1 2 1 1 1 2 1 2 2 1 2 2 1 1 1 1 2 2 2 1 1 2 2 2 1 2 1 2 2 2 1 1 1 1 2 2 1 1 1 1 2 1 2 2 2 2 1 1 1 2 1 2 1 1 2 2 1 1 2 2 1 2...

output:

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177...

result:

ok 199999 numbers

Test #10:

score: 0
Accepted
time: 1538ms
memory: 53100kb

input:

100000 1000
732 864 923 542 711 842 80 128 371 633 258 351 763 694 384 254 328 863 981 613 558 596 470 246 925 811 893 9 872 685 177 696 665 294 972 124 915 480 67 558 391 433 538 415 832 840 206 489 895 964 952 891 671 373 257 528 337 497 296 929 154 465 150 783 305 849 107 178 417 51 877 508 13 81...

output:

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177...

result:

ok 199999 numbers

Test #11:

score: -100
Time Limit Exceeded

input:

200000 1
2 2 2 1 2 1 1 2 2 2 2 2 1 2 2 1 1 1 2 1 1 1 2 2 1 2 1 2 2 1 1 2 2 1 1 2 1 2 1 1 2 1 1 2 1 2 1 2 1 1 2 2 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 2 2 1 1 1 2 1 1 1 2 2 2 2 1 2 2 2 2 2 2 1 1 1 2 2 1 2 1 2 2 2 1 1 2 2 1 2 2 1 1 2 2 1 1 2 2 2 1 2 1 2 1 1 2 2 1 1 2 2 2 2 2 2 1 1 1 2 2 2 1 2 2 1 2 1 1 1...

output:


result: