Submission #40969427
Source Code Expand
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 800005
#define inf 0x3f3f3f3f3f3f3f3f
int n,S,T,A,mxs;
int x[66],c[66],sx[666],sc[666];
int f[42][2][2][260],g[260];
bool vis[260];
signed main()
{
n=read(),S=read(),T=read(),A=read(),mxs=1<<n;
For(i,0,n-1)x[i]=read(),c[i]=read();
For(s,0,mxs-1)
For(i,0,n-1)
if(s>>i&1)sx[s]^=x[i],sc[s]+=c[i];
memset(f,63,sizeof f);
For(s,0,mxs-1)
For(i,0,1) For(j,0,1) f[0][i][j][s]=sc[s]+A*j;
For(i,0,39){
// from a to b
For(j0,0,1)For(j1,0,1){
int a=j0?0:(S>>i&1);
int b=j1?1:(T>>i&1);
For(s,0,mxs-1)
if((sx[s]>>i&1)==(a^b))
f[i+1][j0][j1][s]=f[i][j0][j1][s];
}
For(j0,0,1){
int a=j0?0:(S>>i&1);
memset(g,63,sizeof g);
memset(vis,0,sizeof vis);
For(s,0,mxs-1)
if((sx[s]>>i&1)==a) g[s]=f[i][j0][1][s];
while(1){
int mn=inf,u=-1;
For(s,0,mxs-1)
if(!vis[s] && g[s]<mn)mn=g[s],u=s;
if(u==-1)break;
vis[u]=1;
For(s,0,mxs-1)
if((sx[s]>>i&1)==1)
g[s^u]=min(g[s^u],g[u]+f[i][1][1][s]);
For(j1,0,1){
int b=j1?1:(T>>i&1);
For(s,0,mxs-1)
if((sx[s]>>i&1)==(b^1))
f[i+1][j0][j1][u^s]=min(g[u]+f[i][1][j1][s],f[i+1][j0][j1][u^s]);
}
}
}
}
int res=inf;
For(i,0,mxs-1)res=min(res,f[40][0][0][i]);
if(res==inf)puts("-1");
else cout<<res;
return 0;
}
Submission Info
Submission Time
2023-04-27 09:40:34+0900
Task
E - Increment or XOR
User
Rainbow_sjy
Language
C++ (GCC 9.2.1)
Score
1400
Code Size
1809 Byte
Status
AC
Exec Time
45 ms
Memory
3944 KiB
Compile Error
./Main.cpp: In function ‘long long int read()’:
./Main.cpp:11:2: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
11 | if(f)x=-x;return x;
| ^~
./Main.cpp:11:12: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
11 | if(f)x=-x;return x;
| ^~~~~~
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1400 / 1400
Status
Set Name
Test Cases
Sample
01.txt, 02.txt, 03.txt, 04.txt
All
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt
Case Name
Status
Exec Time
Memory
01.txt
AC 6 ms
3896 KiB
02.txt
AC 2 ms
3888 KiB
03.txt
AC 2 ms
3712 KiB
04.txt
AC 42 ms
3904 KiB
05.txt
AC 3 ms
3896 KiB
06.txt
AC 2 ms
3868 KiB
07.txt
AC 2 ms
3764 KiB
08.txt
AC 4 ms
3760 KiB
09.txt
AC 38 ms
3760 KiB
10.txt
AC 3 ms
3876 KiB
11.txt
AC 38 ms
3772 KiB
12.txt
AC 35 ms
3884 KiB
13.txt
AC 38 ms
3712 KiB
14.txt
AC 44 ms
3896 KiB
15.txt
AC 45 ms
3900 KiB
16.txt
AC 42 ms
3900 KiB
17.txt
AC 43 ms
3848 KiB
18.txt
AC 36 ms
3764 KiB
19.txt
AC 41 ms
3944 KiB
20.txt
AC 41 ms
3844 KiB
21.txt
AC 39 ms
3768 KiB
22.txt
AC 39 ms
3944 KiB
23.txt
AC 41 ms
3928 KiB
24.txt
AC 42 ms
3836 KiB
25.txt
AC 42 ms
3872 KiB
26.txt
AC 42 ms
3876 KiB
27.txt
AC 42 ms
3880 KiB
28.txt
AC 40 ms
3712 KiB
29.txt
AC 38 ms
3712 KiB
30.txt
AC 36 ms
3848 KiB
31.txt
AC 36 ms
3900 KiB
32.txt
AC 33 ms
3764 KiB
33.txt
AC 38 ms
3716 KiB
34.txt
AC 38 ms
3900 KiB
35.txt
AC 38 ms
3836 KiB
36.txt
AC 36 ms
3900 KiB
37.txt
AC 38 ms
3716 KiB
38.txt
AC 40 ms
3900 KiB
39.txt
AC 40 ms
3904 KiB
40.txt
AC 40 ms
3844 KiB
41.txt
AC 39 ms
3844 KiB
42.txt
AC 41 ms
3944 KiB
43.txt
AC 41 ms
3928 KiB
44.txt
AC 39 ms
3760 KiB
45.txt
AC 39 ms
3884 KiB
46.txt
AC 43 ms
3876 KiB
47.txt
AC 39 ms
3928 KiB
48.txt
AC 45 ms
3760 KiB
49.txt
AC 42 ms
3896 KiB
50.txt
AC 41 ms
3716 KiB
51.txt
AC 39 ms
3944 KiB
52.txt
AC 41 ms
3760 KiB
53.txt
AC 41 ms
3716 KiB
54.txt
AC 41 ms
3840 KiB
55.txt
AC 2 ms
3880 KiB
56.txt
AC 4 ms
3768 KiB
57.txt
AC 2 ms
3752 KiB