Submission #63913329

Source Code Expand

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
	int s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline ll lread()
{
	ll s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
char a[1000005];
char b[1000005];
int n;
inline vc<int>run (vc<int>A,int X)
{
	vc<int>ans;int lst=-0x3f3f3f3f;
	for(int p:A)
	{
		p=p<X?p+1:(p==X?p:(p-1));
		if(p!=lst) ans.push_back(p),lst=p;
	}
	return ans;
}
inline int get(vc<int>A,vc<int>B)
{
	int cnt=(A.back()-A[0])-(B.back()-B[0]);
	if((cnt&1)||cnt<0) return 0x3f3f3f3f;
	cnt>>=1;

	int ans=cnt+abs(B[0]-(A[0]+cnt));
	unsigned now=0;//匹配到 B 的哪个位置了

	for(unsigned i=1;i<A.size()&&now+1<B.size();i++)
	{
		int len=A[i]-A[i-1],lenB=B[now+1]-B[now];
		if(len>lenB||(len==lenB&&(A[i-1]+A[0]+B[now]+B[0])%2==0)) now++;
	}
	return now+1<B.size()?0x3f3f3f3f:ans;
}
inline void solve()
{
	n=read();scanf("%s%s",a+1,b+1);vc<int>A,B;
	for(int i=1;i<=n;i++)
	{
		if(a[i]=='1') A.push_back(i);
		if(b[i]=='1') B.push_back(i);
	}
	if(A.size()==1)
	{
		if(B.size()>1) printf("-1\n");
		else printf("%d\n",abs(B[0]-A[0]));
		return ;
	}
	int ans=0x3f3f3f3f;
	for(int L=0;L<2;L++) for(int R=0;R<2;R++)
	{
		vc<int>C=A;
		if(L) C=run(C,C[0]);
		if(R) C=run(C,C.back());
		ans=min(ans,get(C,B)+L+R);
		// printf("L=%d R=%d : %d\n",L,R,get(C,B));
	}
	printf("%d\n",ans==0x3f3f3f3f?-1:ans);
}
int main()
{
	int T=read();
	while(T--) solve();
	return 0;
}

Submission Info

Submission Time
Task D - Magnets
User shijiuwan
Language C++ 20 (gcc 12.2)
Score 1000
Code Size 1922 Byte
Status AC
Exec Time 128 ms
Memory 32948 KiB

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:58:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |         n=read();scanf("%s%s",a+1,b+1);vc<int>A,B;
      |                  ~~~~~^~~~~~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 1
AC × 97
Set Name Test Cases
Sample example0.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, 063.txt, 064.txt, 065.txt, 066.txt, 067.txt, 068.txt, 069.txt, 070.txt, 071.txt, 072.txt, 073.txt, 074.txt, 075.txt, 076.txt, 077.txt, 078.txt, 079.txt, 080.txt, 081.txt, 082.txt, 083.txt, 084.txt, 085.txt, 086.txt, 087.txt, 088.txt, 089.txt, 090.txt, 091.txt, 092.txt, 093.txt, 094.txt, 095.txt, example0.txt
Case Name Status Exec Time Memory
000.txt AC 109 ms 3728 KiB
001.txt AC 31 ms 3672 KiB
002.txt AC 108 ms 3600 KiB
003.txt AC 80 ms 3760 KiB
004.txt AC 128 ms 3636 KiB
005.txt AC 6 ms 5752 KiB
006.txt AC 6 ms 5588 KiB
007.txt AC 40 ms 28892 KiB
008.txt AC 9 ms 9364 KiB
009.txt AC 33 ms 28768 KiB
010.txt AC 9 ms 9440 KiB
011.txt AC 33 ms 28776 KiB
012.txt AC 9 ms 9412 KiB
013.txt AC 32 ms 18924 KiB
014.txt AC 30 ms 18844 KiB
015.txt AC 48 ms 32680 KiB
016.txt AC 30 ms 18828 KiB
017.txt AC 31 ms 18824 KiB
018.txt AC 47 ms 32820 KiB
019.txt AC 4 ms 4944 KiB
020.txt AC 24 ms 14684 KiB
021.txt AC 11 ms 8060 KiB
022.txt AC 22 ms 13688 KiB
023.txt AC 4 ms 5008 KiB
024.txt AC 33 ms 18892 KiB
025.txt AC 32 ms 18796 KiB
026.txt AC 33 ms 18820 KiB
027.txt AC 32 ms 18832 KiB
028.txt AC 33 ms 18956 KiB
029.txt AC 10 ms 7388 KiB
030.txt AC 22 ms 13816 KiB
031.txt AC 25 ms 15388 KiB
032.txt AC 19 ms 13844 KiB
033.txt AC 25 ms 17648 KiB
034.txt AC 8 ms 6564 KiB
035.txt AC 21 ms 15732 KiB
036.txt AC 25 ms 15624 KiB
037.txt AC 35 ms 21216 KiB
038.txt AC 12 ms 8208 KiB
039.txt AC 15 ms 9496 KiB
040.txt AC 18 ms 10960 KiB
041.txt AC 8 ms 6448 KiB
042.txt AC 17 ms 10920 KiB
043.txt AC 11 ms 7948 KiB
044.txt AC 11 ms 8036 KiB
045.txt AC 13 ms 10340 KiB
046.txt AC 15 ms 10676 KiB
047.txt AC 42 ms 26532 KiB
048.txt AC 41 ms 27812 KiB
049.txt AC 49 ms 32324 KiB
050.txt AC 40 ms 23584 KiB
051.txt AC 30 ms 19024 KiB
052.txt AC 41 ms 29264 KiB
053.txt AC 40 ms 27928 KiB
054.txt AC 39 ms 28696 KiB
055.txt AC 34 ms 23448 KiB
056.txt AC 25 ms 15756 KiB
057.txt AC 22 ms 13684 KiB
058.txt AC 27 ms 17296 KiB
059.txt AC 30 ms 16540 KiB
060.txt AC 23 ms 14236 KiB
061.txt AC 25 ms 14252 KiB
062.txt AC 29 ms 15192 KiB
063.txt AC 22 ms 14736 KiB
064.txt AC 10 ms 7228 KiB
065.txt AC 49 ms 32784 KiB
066.txt AC 6 ms 5896 KiB
067.txt AC 31 ms 19024 KiB
068.txt AC 31 ms 18852 KiB
069.txt AC 16 ms 11848 KiB
070.txt AC 6 ms 5756 KiB
071.txt AC 15 ms 9872 KiB
072.txt AC 33 ms 18548 KiB
073.txt AC 47 ms 31272 KiB
074.txt AC 6 ms 5680 KiB
075.txt AC 8 ms 6332 KiB
076.txt AC 15 ms 9636 KiB
077.txt AC 21 ms 14960 KiB
078.txt AC 6 ms 5680 KiB
079.txt AC 20 ms 12368 KiB
080.txt AC 26 ms 14908 KiB
081.txt AC 49 ms 32832 KiB
082.txt AC 49 ms 32948 KiB
083.txt AC 30 ms 18936 KiB
084.txt AC 6 ms 5616 KiB
085.txt AC 6 ms 5540 KiB
086.txt AC 49 ms 32384 KiB
087.txt AC 48 ms 32376 KiB
088.txt AC 30 ms 18900 KiB
089.txt AC 30 ms 18976 KiB
090.txt AC 6 ms 5696 KiB
091.txt AC 6 ms 5796 KiB
092.txt AC 42 ms 30932 KiB
093.txt AC 41 ms 30784 KiB
094.txt AC 6 ms 5588 KiB
095.txt AC 6 ms 5584 KiB
example0.txt AC 1 ms 3812 KiB