QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#841466 | #9915. General Symmetry | zhenjianuo2025 | TL | 1538ms | 54996kb | C++20 | 2.2kb | 2025-01-03 19:18:23 | 2025-01-03 19:18:23 |
Judging History
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...