QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#459059 | #7615. Sequence Folding | kia | TL | 3960ms | 24692kb | C++17 | 2.1kb | 2024-06-29 21:45:46 | 2024-06-29 21:45:46 |
Judging History
answer
/*
IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) ((ll)x.size())
#define all(x) (x).begin(),(x).end()
#define kill(x) cout << x << '\n', exit(0);
#define fuck(x) cout << "(" << #x << " , " << x << ")" << endl
#define endl '\n'
const int N = 3e5+23, lg = 18;
ll Mod = 1e9+7; //998244353;
inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
ll ans = 1;
a=MOD(a, mod);
while (b) {
if (b & 1) ans = MOD(ans*a, mod);
b >>= 1;
a = MOD(a*a, mod);
}
return ans;
}
ll t, n, m, a[N], cnt;
map<ll, int> mp;
int main () {
ios_base::sync_with_stdio(false), cin.tie(0);
cin>>n>>m;
for(int i=1; i<=m; i++) {
cin>>a[i]; mp[a[i]] = 1;
}
ll ans = 0;
while(n > 1) {
map<ll, int> mp2;
for(auto it : mp) {
if(mp.find(n-it.F+1) == mp.end()) mp[n-it.F+1] = 0;
}
for(auto it : mp) {
if(it.F <= n/2ll) {
int x = mp[n-it.F+1];
if(it.S == x) mp2[it.F] = it.S;
else {
if(x == -1 || it.S == -1) {
mp2[it.F] = max(x, it.S);
} else {
ans++; mp2[it.F] = -1;
}
}
}
}
swap(mp, mp2); n/=(2ll);
}
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3400kb
input:
8 3 1 5 8
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 1267ms
memory: 23012kb
input:
17179869184 100000 138476 774165 993977 1152277 1236393 1244970 1534017 1693701 1763926 1778781 1842066 1874644 1885666 2120429 2485344 2977941 3158255 3340476 3504862 4000117 4066652 4197639 4338723 4389163 4576965 4761601 5097091 5175412 5295902 5810551 5855982 6001770 6111262 6163309 6351547 6582...
output:
99999
result:
ok single line: '99999'
Test #4:
score: 0
Accepted
time: 1710ms
memory: 24692kb
input:
549755813888 100000 16886305 20807233 27844305 30727441 30898344 35755457 38085835 43336454 47877882 50347884 53237225 53718183 60030541 66954859 80773500 82511603 84025040 86398615 93070876 94502940 98906398 100677488 103720017 105522694 116741042 122492007 135222584 155167916 160926866 166110647 1...
output:
100000
result:
ok single line: '100000'
Test #5:
score: 0
Accepted
time: 2269ms
memory: 23044kb
input:
17592186044416 100000 44842545 229248515 253567434 347949154 349195610 404810585 639421407 650796923 1019260054 1250861689 1315840401 1318619991 1339387462 1388173647 1406074815 1459749263 1707998226 1902480662 2060860604 2075157570 2410720375 2589192480 2742051226 2784829021 3019629868 3194189913 3...
output:
100000
result:
ok single line: '100000'
Test #6:
score: 0
Accepted
time: 2659ms
memory: 23244kb
input:
562949953421312 100000 8468403039 19260915102 24550792804 45571277635 47757798888 50487845666 53656890708 58778712483 63838097144 65697633747 74717895118 75607193564 75790076603 82739180544 88493216722 90960251492 93191423725 93775335122 96870622706 97818052601 107098516035 116573978680 117388104977...
output:
100000
result:
ok single line: '100000'
Test #7:
score: 0
Accepted
time: 3308ms
memory: 23008kb
input:
18014398509481984 100000 595466408158 695142884370 811588821663 938951385045 955148012821 1074515190235 1209454535782 1319295844076 1465300774125 1634202068435 1761189966958 2474372766317 2493877995320 2532743464849 2607093321941 2755490217777 3183921545337 3499339208003 3649317240659 3873577127103 ...
output:
100000
result:
ok single line: '100000'
Test #8:
score: 0
Accepted
time: 3956ms
memory: 24692kb
input:
576460752303423488 100000 13970345269592 15376826852028 24802122999858 27223268306434 36702541028981 43837014560573 44921933577642 58096934157757 59667447677923 66975875846281 84770936584661 86367511887665 89865085383436 91951807720175 103815897231785 104261045426912 107706410045438 108769878131800 ...
output:
100000
result:
ok single line: '100000'
Test #9:
score: 0
Accepted
time: 42ms
memory: 10088kb
input:
65536 65536 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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 78ms
memory: 15796kb
input:
131072 100000 1 2 4 5 6 9 11 12 14 15 17 18 19 21 22 23 24 26 28 30 31 32 33 34 37 39 40 41 43 44 45 46 47 48 49 51 52 53 54 55 56 57 61 62 64 65 66 67 68 69 70 72 73 74 75 76 77 78 80 81 82 83 84 85 86 87 88 89 90 91 92 93 96 97 98 100 102 103 104 105 106 107 108 109 110 111 112 113 115 116 117 118...
output:
27315
result:
ok single line: '27315'
Test #11:
score: 0
Accepted
time: 44ms
memory: 9624kb
input:
131072 35791 1 3 4 7 10 12 16 18 27 33 41 51 54 63 68 69 85 93 94 100 101 103 105 109 113 114 115 117 118 123 129 132 135 137 139 141 144 146 150 152 153 161 165 170 172 175 177 179 192 195 196 197 201 202 205 207 208 210 212 213 217 218 225 228 229 236 239 242 256 259 265 270 273 285 295 297 299 30...
output:
30694
result:
ok single line: '30694'
Test #12:
score: 0
Accepted
time: 60ms
memory: 11964kb
input:
131072 53908 4 6 12 13 14 16 20 23 24 31 33 35 37 39 40 42 46 47 48 52 53 55 57 58 60 61 62 66 68 69 75 79 80 81 82 83 87 90 94 95 97 98 100 103 105 106 107 109 110 111 112 117 120 123 127 128 131 132 138 146 147 148 154 155 159 161 163 164 168 171 172 173 174 177 178 179 181 183 187 188 189 190 192...
output:
40848
result:
ok single line: '40848'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3404kb
input:
2 1 2
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 111ms
memory: 19668kb
input:
262144 100000 3 6 10 12 23 27 30 31 32 35 36 38 39 40 43 44 45 47 49 50 51 52 54 55 60 62 66 68 69 70 71 73 77 79 80 81 82 86 88 91 94 95 98 100 101 102 107 109 113 123 125 126 127 128 131 132 138 142 144 146 147 149 150 151 156 157 166 167 169 170 171 174 176 177 181 184 188 190 195 197 198 203 204...
output:
78358
result:
ok single line: '78358'
Test #15:
score: 0
Accepted
time: 124ms
memory: 19660kb
input:
262144 100000 4 6 8 13 16 18 19 20 21 27 28 32 36 37 38 42 44 47 51 53 55 56 61 62 65 66 68 80 81 82 84 85 88 89 90 92 96 110 112 113 114 117 118 121 123 124 127 129 131 133 136 137 140 142 152 153 156 161 162 163 164 167 174 176 177 178 182 183 188 190 192 194 195 198 200 207 208 210 211 212 214 21...
output:
78283
result:
ok single line: '78283'
Test #16:
score: 0
Accepted
time: 112ms
memory: 19352kb
input:
262144 100000 8 13 17 18 24 25 28 33 42 43 45 47 49 53 63 65 67 68 69 71 75 80 81 82 91 98 99 100 101 107 109 110 113 114 115 118 119 121 125 128 129 131 133 136 142 145 147 148 149 150 151 153 161 167 168 169 171 174 175 176 178 185 187 188 190 192 193 195 197 198 200 202 203 205 206 207 211 223 22...
output:
78377
result:
ok single line: '78377'
Test #17:
score: 0
Accepted
time: 3937ms
memory: 22940kb
input:
288230376151711744 100000 2051253087133 5034791117487 16277884254216 18748708512249 25161273356777 36308675496739 36396901330480 36762586969507 37497387695665 37563665735752 39576584265761 41873710679871 49534817047754 53927300913267 54227259634409 56761933827487 57956114073060 63040701064548 641255...
output:
100000
result:
ok single line: '100000'
Test #18:
score: 0
Accepted
time: 3960ms
memory: 22936kb
input:
288230376151711744 100000 13673747777668 15739859999866 21203445973142 23798904995363 26158220623088 28986290989623 33184712388237 35166671949347 36281038226194 41488068526902 47701082448077 63719553846332 64908694760680 73471939044692 73685979018933 75730004826420 81098014344469 81935325531771 8353...
output:
100000
result:
ok single line: '100000'
Test #19:
score: 0
Accepted
time: 3875ms
memory: 23004kb
input:
288230376151711744 100000 595301495104 1718356412302 3503997570218 5034929023689 5044869417779 9078189744121 12507129448076 13515421734092 14995690016321 17184354842267 18805440477175 19403492814747 20651814136440 21836850228253 24681339065751 26416497021478 27195137574686 28473163660886 30072237858...
output:
100000
result:
ok single line: '100000'
Test #20:
score: -100
Time Limit Exceeded
input:
576460752303423488 100000 8107391531049 8397412343932 11817015312495 18591269865678 24476561473901 29556407820988 34956326024323 37463753731130 42304557847636 47883181462463 48668327829946 49181951408615 75388508288926 83647541308487 86526892361219 91560373134632 99258585092530 99439609915249 108353...
output:
100000