글 읽기 - (Project Laptop #6) Choreography

jh05013 3년 전 2

데이터와 스페셜 저지를 추가해 주세요.

https://upload.acmicpc.net/658...

데이터 제작자: jh05013

스페셜 저지 제작자: jh05013

또한 이동 횟수가 2780554까지 나오는데 0.5초는 매우 부족한 시간 제한입니다. 2초로 늘려 주세요.

#include <bits/stdc++.h>
#include "testlib.h"

using namespace std;

const int MAXN = 5000;
const int MAXLEN = 10000;
const int MINCOORD = 0+1;
const int MAXCOORD = 1000000000-1;

int intervals[MAXN+1], S[MAXN+1], E[MAXN+1];

void check_nonint(int arr[], int n, int r, int start, int end){
	int rightcoord = -1;
	for(int i=start; i<=end; i++){
		int x = arr[i];
		if(intervals[x] <= rightcoord)
			quitf(_wa, "Conflict among dancers");
		rightcoord = intervals[x]+r;
	}
}

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);
    
    int member = inf.readInt(1, 5000, "m");
    int interval = inf.readInt(member, 5000, "n");
    int length = inf.readInt(1, 10000, "r");
    
    for(int i=1; i<=interval; i++)
    	intervals[i] = inf.readInt(MINCOORD, MAXCOORD, "i");
    for(int i=1; i<=member; i++)
    	S[i] = inf.readInt(1, interval, "s");
    for(int i=1; i<=member; i++)
    	E[i] = inf.readInt(1, interval, "e");
    
    int optimum = ans.readInt();
    int user_answer = ouf.readInt();
    if(optimum != user_answer) quitf(_wa, "Minimum not equal");
    
    // impossibility
    if(user_answer == -1){
    	if(!ouf.seekEof()) quitf(_wa, "Extra output");
    	quitf(_ok, "Impossible");
    }
    
    for(int TURN=0; TURN<user_answer; TURN++){
    	int a = ouf.readInt(1, interval, "a");
    	int b = ouf.readInt(1, interval, "b");
    	if(intervals[a]+length < intervals[b])
    		quitf(_wa, "%d and %d are disjoint; cannot move", a, b);
		int i = lower_bound(S, S+member+1, a) - S;
		if(!(1 <= i && i <= member && S[i] == a))
			quitf(_wa, "No member at %d", a);
		S[i] = b;
		check_nonint(S, member, length, max(1, i-2), min(member, i+2));
    }
    for(int i=1; i<=member; i++){
    	if(S[i] != E[i])
    		quitf(_wa, "Final state does not match");
    }
    
    if(!ouf.seekEof()) quitf(_wa, "Extra output");
    quitf(_ok, "%d moves", optimum);
}

jh05013 3년 전 0

Validator도 첨부합니다.

#include <bits/stdc++.h>
#include "testlib.h"

using namespace std;

const int MAXN = 5000;
const int MAXLEN = 10000;
const int MINCOORD = 0+1;
const int MAXCOORD = 1000000000-1;

int intervals[MAXN+1], S[MAXN+1], E[MAXN+1];

void check_ascending(int arr[], int n){
	for(int i=1; i<n; i++) assert(arr[i] < arr[i+1]);
}

void check_nonint(int arr[], int n, int r){
	int rightcoord = -1;
	for(int i=1; i<=n; i++){
		int x = arr[i];
		assert(intervals[x] > rightcoord);
		rightcoord = intervals[x]+r;
	}
}

int main(int argc, char* argv[]) {
    registerValidation(argc, argv);
    int member = inf.readInt(1, 5000, "m");
    inf.readSpace();
    int interval = inf.readInt(member, 5000, "n");
    inf.readEoln();
    int length = inf.readInt(1, 10000, "r");
    inf.readEoln();
    
    for(int i=1; i<=interval; i++){
    	intervals[i] = inf.readInt(MINCOORD, MAXCOORD, "i");
    	if(i == interval) inf.readEoln();
    	else inf.readSpace();
    }
    check_ascending(intervals, interval);
    
    for(int i=1; i<=member; i++){
    	S[i] = inf.readInt(1, interval, "s");
    	if(i == member) inf.readEoln();
    	else inf.readSpace();
    }
    check_ascending(intervals, interval);
    check_nonint(S, member, length);
    
    for(int i=1; i<=member; i++){
    	E[i] = inf.readInt(1, interval, "e");
    	if(i == member) inf.readEoln();
    	else inf.readSpace();
    }
    check_ascending(intervals, interval);
    check_nonint(E, member, length);
    
    inf.readEof();
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(Project Laptop #6) Choreography

jh05013 3년 전 2

jh05013 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말