QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #469087 | #2906. XOR Island | ZhouShang | AC ✓ | 2240ms | 265900kb | C++20 | 988b | 2024-07-09 13:31:27 | 2024-07-09 13:31:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for (int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int, k>
template<class A, class B> void cmx(A &x, B y) { x = max<A>(x, y);}
template<class A, class B> void cmn(A &x, B y) { x = min<A>(x, y);}
typedef pair<int, int> pii;
typedef vector<int> vi;
int n,A,a[99],f[1<<25];
signed main() {
//cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
cin>>n,A=n-2;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
for(int k=j+1;k<n;k++)
if(!(a[i]^a[j]^a[k]))
f[(1<<i)|(1<<j)|(1<<k)]=1;
for(int i=0;i<(1<<n);i++){
if(__builtin_popcount(i)<3)
continue;
for(int j=0;j<n;j++)
if(i>>j&1)
f[i]|=f[i^(1<<j)];
if(!f[i])
A=min(A,n-__builtin_popcount(i));
}
cout<<A<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
3 1 2 3
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
11 9 1 14 2 11 7 6 7 6 5 3
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
6 18053353 18053353 31735788 31735788 16205573 16205573
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
9 8324820 8324820 8324820 21703420 21703420 21703420 20196392 20196392 20196392
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
12 13845321 13845321 13845321 13845321 15244518 15244518 15244518 15244518 3923887 3923887 3923887 3923887
output:
4
result:
ok single line: '4'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
15 22226925 22226925 22226925 22226925 22226925 11291487 11291487 11291487 11291487 11291487 33516722 33516722 33516722 33516722 33516722
output:
5
result:
ok single line: '5'
Test #7:
score: 0
Accepted
time: 17ms
memory: 5776kb
input:
18 15216629 15216629 15216629 15216629 15216629 15216629 9508343 9508343 9508343 9508343 9508343 9508343 7944706 7944706 7944706 7944706 7944706 7944706
output:
6
result:
ok single line: '6'
Test #8:
score: 0
Accepted
time: 126ms
memory: 19916kb
input:
21 13356922 13356922 13356922 13356922 13356922 13356922 13356922 32063243 32063243 32063243 32063243 32063243 32063243 32063243 19066993 19066993 19066993 19066993 19066993 19066993 19066993
output:
7
result:
ok single line: '7'
Test #9:
score: 0
Accepted
time: 1081ms
memory: 134600kb
input:
24 5624463 5624463 5624463 5624463 5624463 5624463 5624463 5624463 15098761 15098761 15098761 15098761 15098761 15098761 15098761 15098761 11776262 11776262 11776262 11776262 11776262 11776262 11776262 11776262
output:
8
result:
ok single line: '8'
Test #10:
score: 0
Accepted
time: 127ms
memory: 19976kb
input:
21 10 1 5 1 6 12 14 16 1 13 2 10 16 9 14 2 12 16 13 11 1
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 262ms
memory: 36276kb
input:
22 9 5 1 2 6 15 8 10 2 1 13 10 10 4 13 16 8 5 7 4 9 3
output:
7
result:
ok single line: '7'
Test #12:
score: 0
Accepted
time: 532ms
memory: 69120kb
input:
23 2 12 8 5 6 15 3 14 3 4 11 2 6 13 1 10 13 6 1 8 1 5 15
output:
7
result:
ok single line: '7'
Test #13:
score: 0
Accepted
time: 1119ms
memory: 134600kb
input:
24 4 13 10 8 4 12 10 1 13 16 1 10 5 3 6 3 9 6 14 4 7 4 9 2
output:
7
result:
ok single line: '7'
Test #14:
score: 0
Accepted
time: 2200ms
memory: 265672kb
input:
25 13 8 5 2 12 6 12 1 16 14 2 10 2 8 9 3 4 6 9 6 6 7 14 1 9
output:
7
result:
ok single line: '7'
Test #15:
score: 0
Accepted
time: 547ms
memory: 69044kb
input:
23 15925942 11051838 20346967 676939 779282 29980798 24484952 27328228 25636253 911824 30521853 23148136 24386971 30992542 4736184 8716393 26656418 1571228 10680642 25754292 7030770 9364603 4593643
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 1087ms
memory: 134664kb
input:
24 14308376 17302931 4737216 25548643 20448845 30163626 24015986 16874513 1363340 25740273 26055670 2065166 22649380 27657047 20575156 5465887 28406514 2855073 29537258 24129214 23999010 30352648 4252441 13105059
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 2240ms
memory: 265728kb
input:
25 7278802 5576962 9887589 28410596 6241564 4736865 29583733 13328658 24907097 21930886 31443909 25339020 20142713 32796255 4539481 28575359 13110054 13738964 14418498 10152417 4040993 5615463 16606164 25405528 15179433
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 539ms
memory: 69116kb
input:
23 1 131072 1 131072 131073 1 131073 131072 131072 131073 131072 131072 131073 131073 1 131072 131073 131073 1 131072 131073 131072 131073
output:
5
result:
ok single line: '5'
Test #19:
score: 0
Accepted
time: 546ms
memory: 69036kb
input:
23 1050688 1048576 2048 1048576 2048 1048640 1048576 1050624 1050688 1048640 2112 1048640 1048640 1048640 1050624 2048 1048640 1050688 1050624 1048640 1048576 1048576 1048640
output:
4
result:
ok single line: '4'
Test #20:
score: 0
Accepted
time: 1094ms
memory: 134600kb
input:
24 66560 1024 65536 66560 65536 1024 66560 66560 1024 66560 66560 66560 66560 66560 1024 65536 1024 1024 66560 65536 1024 1024 66560 66560
output:
4
result:
ok single line: '4'
Test #21:
score: 0
Accepted
time: 1075ms
memory: 134864kb
input:
24 32 256 32 800 800 512 512 256 256 800 512 544 544 544 512 288 800 800 768 256 512 32 256 256
output:
5
result:
ok single line: '5'
Test #22:
score: 0
Accepted
time: 2229ms
memory: 265672kb
input:
25 1056 1024 32 1024 32 1024 32 1056 1056 32 32 1056 32 32 1056 1056 1024 32 1056 1056 1024 32 32 1024 1024
output:
7
result:
ok single line: '7'
Test #23:
score: 0
Accepted
time: 2228ms
memory: 265900kb
input:
25 131328 131136 131136 64 131136 64 131072 131392 131136 131392 64 64 320 131136 320 131072 256 131328 131392 131072 131136 131136 131136 320 256
output:
7
result:
ok single line: '7'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3836kb
input:
15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
output:
7
result:
ok single line: '7'
Test #25:
score: 0
Accepted
time: 2229ms
memory: 265608kb
input:
25 27882881 30145540 6457733 28446363 30443294 7991967 5008288 31792673 3072549 5705914 33449275 27061438 3512639 25153864 14066889 18700493 23374418 13492179 11490902 17179607 20167400 10145641 16271084 14892534 21645431
output:
10
result:
ok single line: '10'
Test #26:
score: 0
Accepted
time: 2234ms
memory: 265548kb
input:
25 972439 2867411 2423978 50417 1961336 2373723 2430532 77343 2813644 3655493 1310494 125678 998521 922214 3790115 1885031 3734332 1836950 1233153 3686349 1185264 3740114 1911177 2478773 2763325
output:
11
result:
ok single line: '11'
Test #27:
score: 0
Accepted
time: 2202ms
memory: 265648kb
input:
25 2700755 2567664 923683 3765664 1288823 256516 1988688 1946196 969910 2809815 1277666 1086694 212625 913959 54421 3776821 2744646 2755394 1926849 1065075 2364257 2410484 861874 2619749 2002117
output:
9
result:
ok single line: '9'