AtCoder Grand Contest 019

Submission #5798454

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define mod 1000000007
#define eps 1e-13
#define PI 3.141592653589793238L
#define INF 1000000011
#define INFLL 1000000000000000011LL
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define fo(i,a,n) for(i = (a); i < (n); i++)
#define gtl(x) getline(cin, (x))
#define flsh fflush(stdout)
#define sws ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define gcd __gcd
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
#define io_file freopen("D:/Coding Problems/Contest/input_file.in", "r", stdin); freopen("D:/Coding Problems/Contest/output_file.out", "w", stdout)

ll modx(ll Base, ll exponent)
{
	ll ans = 1;
	if(Base == 1)
		return Base;
	while(exponent)
	{
		if(exponent & 1)
			ans = (ans * Base)%mod;
		Base = (Base * Base)%mod;
		exponent = exponent >> 1;
	}
	return ans;
}

ll inmodx(ll num)
{
	return (modx(num, mod-2LL));
}

bool cmp(pair < vi, int > a, pair < vi, int > b)//true for a before b
{
	if(a.F.empty())
		return 1;
	if(b.F.empty())
		return 0;
	int i;
	fo(i,0,min(sz(a.F),sz(b.F)))
	{
		if(a.F[i] < b.F[i])
			return 1;
		else if(a.F[i] > b.F[i])
			return 0;
	}
	return (sz(a.F) <= sz(b.F));
}

const int N = (2e3) + 9;
const int M = (N<<2) + 9;
const int LOGN = ((int)log2(N)) + 3;
const int LOGM = ((int)log2(M)) + 3;
const int BUCK = 900;
const int SQRT = BUCK+9;

const int MAX = 2000;
string a, b;
int prefix[N], suffix[N];
set < pii > st;

void pre(int ind, int n)
{
	int i, j;
	fo(i,0,n)
	{
		j = (i+ind)%n;
		if(b[j] == '1')
		{
			prefix[i] = min(prefix[i], ind);
			suffix[i] = max(suffix[i], (ind == 0) ? n : ind);
		}
	}
	return;
}

int func(int ind, int n)
{
	int i, j, ans = INF, val, cnt = 0;
	fo(i,0,n)
	{
		j = (i+ind)%n;
		if(a[j] != b[i])
			cnt++;
	}
	st.clear();
	fo(i,0,n)
	{
		j = (i+ind)%n;
		if(a[j] == '1' && b[i] == '0')
			st.insert({suffix[i],i});
	}
	fo(i,0,n)
	{
		st.erase({suffix[i],i});
		if(st.empty())
			val = i + min(abs(ind-i),n-(ind-i));
		else
		{
			j = st.begin()->F;
			val = 2*i + (n-j) + min(abs(ind-j),n-abs(ind-j));
		}
		ans = min(ans, val);
	}
	st.clear();
	fo(i,0,n)
	{
		j = (i+ind)%n;
		if(a[j] == '1' && b[i] == '0')
			st.insert({-prefix[i],(i == 0) ? n : i});
	}
	for(i = n; i > 0; i--)
	{
		st.erase({-prefix[i],i});
		if(st.empty())
			val = (n-i) + min(abs(ind-i),n-abs(ind-i));
		else
		{
			j = -st.begin()->F;
			val = 2*(n-i) + j + min(abs(ind-j),n-abs(ind-j));
		}
		ans = min(ans, val);
	}
	ans += cnt;
	return ans;
}

void solve()
{
	int n, i, ans = INF;
	bool has1 = 0;
	cin >> a;
	cin >> b;
	n = a.length();
	for(auto x : b)
		has1 |= (x == '1');
	if(!has1)
	{
		if(a == b)
			cout << 0 << '\n';
		else
			cout << -1 << '\n';
		return;
	}
	if(n == 1)
	{
		if(a == b)
			cout << 0 << '\n';
		else
			cout << 1 << '\n';
		return;
	}
	fo(i,0,n)
	{
		prefix[i] = INF;
		suffix[i] = -INF;
	}
	fo(i,0,n)
		pre(i,n);
	suffix[n] = suffix[0];
	prefix[n] = prefix[0];
	fo(i,0,n)
		ans = min(ans, func(i,n));
	cout << ans << '\n';
	return;
}

int main()
{
	sws;
	clock_t clk;
	clk = clock();
	// io_file;
	// srand (time(NULL));

	//Code here
	int t = 1, cs;
	cout << fixed << setprecision(15);
	// cin >> t;
	fo(cs,1,t+1)
	{
		// cout << "Case #" << cs << ": ";
		solve();
	}
	// Code ends here

	clk = clock() - clk;
	cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
	return 0;
}

Submission

Task問題 D - Shift and Flip
User nameユーザ名 abhishek_1997
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 3864 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt
All 0 / 1000 sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt,sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt,subtask_1_01.txt,subtask_1_02.txt,subtask_1_03.txt,subtask_1_04.txt,subtask_1_05.txt,subtask_1_06.txt,subtask_1_07.txt,subtask_1_08.txt,subtask_1_09.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_12.txt,subtask_1_13.txt,subtask_1_14.txt,subtask_1_15.txt,subtask_1_16.txt,subtask_1_17.txt,subtask_1_18.txt,subtask_1_19.txt,subtask_1_20.txt,subtask_1_21.txt,subtask_1_22.txt,subtask_1_23.txt,subtask_1_24.txt,subtask_1_25.txt,subtask_1_26.txt,subtask_1_27.txt,subtask_1_28.txt,subtask_1_29.txt,subtask_1_30.txt,subtask_1_31.txt,subtask_1_32.txt,subtask_1_33.txt,subtask_1_34.txt,subtask_1_35.txt,subtask_1_36.txt,subtask_1_37.txt,subtask_1_38.txt,subtask_1_39.txt,subtask_1_40.txt,subtask_1_41.txt,subtask_1_42.txt,subtask_1_43.txt,subtask_1_44.txt,subtask_1_45.txt,subtask_1_46.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt AC 1 ms 256 KB
subtask_1_05.txt AC 134 ms 256 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 140 ms 256 KB
subtask_1_08.txt AC 1 ms 256 KB
subtask_1_09.txt AC 1 ms 256 KB
subtask_1_10.txt AC 3 ms 256 KB
subtask_1_11.txt AC 705 ms 256 KB
subtask_1_12.txt AC 438 ms 256 KB
subtask_1_13.txt AC 703 ms 256 KB
subtask_1_14.txt AC 720 ms 384 KB
subtask_1_15.txt AC 834 ms 384 KB
subtask_1_16.txt AC 1000 ms 384 KB
subtask_1_17.txt AC 989 ms 384 KB
subtask_1_18.txt AC 1120 ms 384 KB
subtask_1_19.txt AC 1142 ms 384 KB
subtask_1_20.txt AC 1066 ms 384 KB
subtask_1_21.txt WA
subtask_1_22.txt WA
subtask_1_23.txt AC 991 ms 384 KB
subtask_1_24.txt AC 997 ms 384 KB
subtask_1_25.txt AC 990 ms 384 KB
subtask_1_26.txt WA
subtask_1_27.txt WA
subtask_1_28.txt WA
subtask_1_29.txt WA
subtask_1_30.txt WA
subtask_1_31.txt WA
subtask_1_32.txt WA
subtask_1_33.txt WA
subtask_1_34.txt WA
subtask_1_35.txt WA
subtask_1_36.txt WA
subtask_1_37.txt WA
subtask_1_38.txt AC 7 ms 256 KB
subtask_1_39.txt WA
subtask_1_40.txt WA
subtask_1_41.txt WA
subtask_1_42.txt WA
subtask_1_43.txt WA
subtask_1_44.txt WA
subtask_1_45.txt WA
subtask_1_46.txt WA