답안 #959573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
959573 2024-04-08T13:10:33 Z LCJLY Xylophone (JOI18_xylophone) C++14
컴파일 오류
0 ms 0 KB
#include <cstdio>
#include <cstdlib>
#include "xylophone.h"

static const int N_MAX = 5000;
static const int Q_MAX = 10000;
static int N;
static int A[N_MAX];
static bool used[N_MAX];
static int query_c;
static int answer_c;

int query(int s, int t) {
	if(query_c >= Q_MAX) {
		printf("Wrong Answer\n");
		exit(0);
	}
	query_c++;
	if(!(1 <= s && s <= t && t <= N)) {
		printf("Wrong Answer2\n");
		exit(0);
	}
	int mx = 0, mn = N + 1;
	for(int i = s - 1; i < t; i++) {
		if(mx < A[i]) {
			mx = A[i];
		}
		if(mn > A[i]) {
			mn = A[i];
		}
	}
	return mx - mn;
}

void answer(int i, int a) {
	answer_c++;
	if(!(1 <= i && i <= N)) {
		printf("Wrong Answer\n");
		exit(0);
	}
	if(!(1 <= a && a <= N)) {
		printf("Wrong Answer\n");
		exit(0);
	}
	if(used[i - 1]) {
		printf("Wrong Answer\n");
		exit(0);
	}
	if(a != A[i - 1]) {
		printf("Wrong Answer\n");
		exit(0);
	}
	used[i - 1] = true;
}

//code

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<pii,pii>pi2;

//static int A[5000];

//query(l,r)
//answer(index,val)


void solve(int n) {
	//find index of value 1
	int l=1;
	int r=n;
	int mid;
	int one=1;
	
	while(l<=r){
		mid=(l+r)/2;
		int hold=query(mid,n);
		//show2(mid,mid,hold,hold);
		if(hold==n-1){
			one=mid;
			l=mid+1;;
		}
		else r=mid-1;
	}
	
	//show(one,one);
	
	int ans[n+5];
	memset(ans,-1,sizeof(ans));
	ans[one]=1;
	
	//neighbour values
	if(one>1){
		ans[one-1]=1+query(one-1,one);
	}
	if(one<n){
		ans[one+1]=1+query(one,one+1);
	}
	
	//recover other values
	for(int x=one-2;x>=1;x--){
		int a=query(x,x+1);
		int b=query(x,x+2);
		int diff=abs(ans[x+1]-ans[x+2]);
		if(b==diff&&a<b){
			//mid
			if(ans[x+1]>ans[x+2]){
				ans[x]=ans[x+1]-a;
			}
			else{
				ans[x]=ans[x+1]+a;
			}
		}
		else if(a>b){
			if(ans[x+1]>ans[x+2]){
				ans[x]=ans[x+1]-a;
			}
			else{
				ans[x]=ans[x+1]+a;
			}
		}
		else{
			if(ans[x+2]>ans[x+1]){
				ans[x]=ans[x+1]-a;
			}
			else{
				ans[x]=ans[x+1]+a;
			}
		}
	}	
	
	for(int x=one+2;x<=n;x++){
		int a=query(x-1,x);
		int b=query(x-2,x);
		int diff=abs(ans[x-1]-ans[x-2]);
		if(b==diff&&a<b){
			//mid
			if(ans[x-1]>ans[x-2]){
				ans[x]=ans[x-1]-a;
			}
			else{
				ans[x]=ans[x-1]+a;
			}
		}
		else if(a>b){
			if(ans[x-1]>ans[x-2]){
				ans[x]=ans[x-1]-a;
			}
			else{
				ans[x]=ans[x-1]+a;
			}
		}
		else{
			if(ans[x-2]>ans[x-1]){
				ans[x]=ans[x-1]-a;
			}
			else{
				ans[x]=ans[x-1]+a;
			}
		}
	}	
	

	//show4(ans,ans);
	
	for(int x=1;x<=n;x++){
		answer(x,ans[x]);
	}
}

//code

int main() {
	query_c = 0;
	answer_c = 0;
	if(scanf("%d", &N) != 1) {
		fprintf(stderr, "Error while reading input\n");
		exit(1);
	}
	for(int i = 0; i < N; i++) {
		if(scanf("%d", A + i) != 1) {
			fprintf(stderr, "Error while reading input\n");
			exit(1);
		}
		used[i] = false;
	}
	solve(N);
	if(!(answer_c == N)) {
		printf("Wrong Answer\n");
		exit(0);
	}
	printf("Accepted : %d\n", query_c);
}

Compilation message

/usr/bin/ld: /tmp/ccBqR89Y.o: in function `query(int, int)':
grader.cpp:(.text+0x0): multiple definition of `query(int, int)'; /tmp/ccdpS4yW.o:xylophone.cpp:(.text+0x0): first defined here
/usr/bin/ld: /tmp/ccBqR89Y.o: in function `answer(int, int)':
grader.cpp:(.text+0xa0): multiple definition of `answer(int, int)'; /tmp/ccdpS4yW.o:xylophone.cpp:(.text+0xc0): first defined here
/usr/bin/ld: /tmp/ccBqR89Y.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccdpS4yW.o:xylophone.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status