제출 #1140558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140558		marinov	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	268 ms	4340 KiB

Main

// Author: Jiří Kalvoda
#include<bits/stdc++.h>
using namespace std;

using ll = long long;

#define printe(a...) fprintf(stderr, a)

const int NMAX = 112345;

int s[NMAX];
int f[NMAX];

const int DPLEN=3;
const int DPCHECKDELAY=1;
const int MAX=1'000'000'001;

int opt_from[NMAX][1<<DPLEN];
int N,M;

bool test(int K)
{
	int fi=0;
	for(int i=DPLEN; i<N; i++)
	{
		for (int mask=0; mask<(1<<DPLEN); mask++)
		{
			opt_from[i][mask] = -1;
			for (int case_id=0; case_id< 2; case_id++)
			{
				int full_mask = mask + (case_id<<DPLEN);
				int from_mask = full_mask>>1;
				if(opt_from[i-1][from_mask] == -1) goto nook;
				for(int fj=fi; fj<M && f[fj]<=s[i-DPCHECKDELAY]; fj++)
				{
					for(int k=i-DPLEN;k<=i;k++)
					{
						if(f[fj] == s[k]) goto ok;;
						if((f[fj] >= s[k]) == ((full_mask>>(i-k))&1) && abs(f[fj]-s[k]) <= K) goto ok;
					}
					goto nook;
					ok:;
				}
				opt_from[i][mask] = from_mask;
				nook:;
			}
		}
		while(fi<M && f[fi]<=s[i-DPCHECKDELAY]) fi++;
	}

	return opt_from[N-1][0] != -1;
}

int main(int argc, char ** argv)
{
	scanf("%d%d", &N, &M);
	for (int i=0; i<DPLEN; i++) s[i] = -2'000'000'011; // We will add some sprinklers far away at the begin
	for (int i=0; i<N; i++) scanf("%d", s+DPLEN+i);
	for (int i=0; i<M; i++) scanf("%d", f+i);

	N+=DPLEN;
	for (int i=0; i<DPLEN; i++) s[N++] = 2'000'000'011; // We will add some sprinklers far away at the end

	int kmin=0, kmax=MAX;
	while(kmin<kmax)
	{
		int K=(kmin+kmax)/2;
		if(test(K))
			kmax=K;
		else
			kmin=K+1;
	}
	int K = kmin;
	test(K);


	if(K > 1'000'000'000)
		printf("-1\n");
	else
	{
		string out(N, ' ');
		for(int i=N-1, j=0; i>=0;i--)
		{
			out[i] = (j&1) ? 'R' : 'L';
			j = opt_from[i][j];
		}
		out[N-DPLEN]=0;

		printf("%d\n%s\n", K, out.c_str()+DPLEN);
	}

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main(int, char**)':
Main.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d%d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:58:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         for (int i=0; i<N; i++) scanf("%d", s+DPLEN+i);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:59:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         for (int i=0; i<M; i++) scanf("%d", f+i);
      |                                 ~~~~~^~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 17 / 17
• Subtask 4: 27 / 27
• Subtask 5: 47 / 47