oj.uz

답안 #58188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58188 2018-07-17T06:18:02 Z 정원준(#1691) 도서관 (JOI18_library) C++11
0 / 100
 72 ms 496 KB 
#include "library.h"
#include <bits/stdc++.h>
#define L long long

using namespace std;

//int Query(const vector<int>&M);
//void Answer(const vector<int>&res);

int ans[1010],chk[1010];

int f(int pos,int s,int e,vector<int>&get,vector<int>&input){
	/*printf("f %d %d %d\n",pos,s,e);
	for(int i=s;i<=e;i++)
	{
		printf("%d ",get[i]);
	}
	puts("");*/
	if(s==e) return get[s];
	int mid=(s+e)/2,i,temp1,temp2;
	
	for(i=s;i<=mid;i++)
	{
		input[get[i]]=1;
	}
	/*printf("input ");
	for(i=0;i<5;i++)
		printf("%d ",input[i]);
	puts("");*/
	temp1=Query(input);
	//printf("%d\n",temp1);
	input[ans[pos-1]]=0;
	/*printf("input ");
	for(i=0;i<5;i++)
		printf("%d ",input[i]);
	puts("");*/
	temp2=Query(input);
	//printf("%d\n",temp2);
	input[ans[pos-1]]=1;
	for(i=s;i<=mid;i++)
	{
		input[get[i]]=0;
	}
	if(temp1!=temp2) return f(pos,s,mid,get,input);
	else return f(pos,mid+1,e,get,input);
	
}

void Solve(int N){
	int i,j,start,secon;
	vector<int>input(N,0);
	for(i=0;i<N;i++)
	{
		input[i]=1;
	}
	for(i=0;i<N;i++)
	{
		input[i]=0;
		int temp=Query(input);
		input[i]=1;
		if(temp==1)
		{
			start=i;
			break;
		}
	}
	ans[0]=start;
	//printf("start %d\n",start);
	chk[start]=1;
	vector<int>input3(N,0);
	input3[start]=1;
	for(i=0;i<N;i++)
	{
		if(i!=start)
		{
			input3[i]=1;
			int temp=Query(input3);
			input3[i]=0;
			if(temp==1)
			{
				secon=i;
				break;
			}
		}
	}
	ans[1]=secon;
	chk[secon]=1;
	//printf("second %d\n",secon);
	
	for(i=2;i<N;i++)
	{
		vector<int>give;
		vector<int>input2(N,0);
		for(j=0;j<N;j++)
		{
			if(!chk[j]) give.push_back(j);
			else input2[j]=1;
		} 
		int temp=f(i,0,give.size()-1,give,input2);//���� i���� �پ��ִ� ���Ҹ� ã�´�. 
		ans[i]=temp;
		chk[temp]=1;
	}
	
	vector<int>giveans;
	for(i=0;i<N;i++)
	{
		giveans.push_back(ans[i]+1);
	}
	Answer(giveans);
}

/*
int n,a[1010],chk2[1010],loc[1010];

int Query(const vector<int>&M){
	int i,ret=0;
	for(i=0;i<n;i++)
	{
		chk2[i]=0;
	}
	for(i=0;i<n;i++)
	{
		if(M[i]) chk2[loc[i]]=1;
	}
	for(i=0;i<n;i++)
	{
		if(chk2[i])
		{
			if(i==0||!chk2[i-1]) ret++;
		}
	}
	return ret;
}

void Answer(const vector<int>&res){
	int i;
	for(i=0;i<n;i++)
	{
		printf("%d ",res[i]);
	}
	return;
}*/

/*
int main()
{
	scanf("%d",&n);
	int i;
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		loc[a[i]-1]=i;
	}
	Solve(n);
}*/

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:67:8: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ans[0]=start;
  ~~~~~~^~~~~~
library.cpp:86:8: warning: 'secon' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ans[1]=secon;
  ~~~~~~^~~~~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 320 KB Output is correct
2 Correct 30 ms 484 KB Output is correct
3 Correct 39 ms 484 KB Output is correct
4 Correct 56 ms 484 KB Output is correct
5 Correct 40 ms 484 KB Output is correct
6 Correct 48 ms 484 KB Output is correct
7 Correct 66 ms 496 KB Output is correct
8 Correct 62 ms 496 KB Output is correct
9 Correct 72 ms 496 KB Output is correct
10 Correct 31 ms 496 KB Output is correct
11 Incorrect 3 ms 496 KB Wrong Answer [2]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 320 KB Output is correct
2 Correct 30 ms 484 KB Output is correct
3 Correct 39 ms 484 KB Output is correct
4 Correct 56 ms 484 KB Output is correct
5 Correct 40 ms 484 KB Output is correct
6 Correct 48 ms 484 KB Output is correct
7 Correct 66 ms 496 KB Output is correct
8 Correct 62 ms 496 KB Output is correct
9 Correct 72 ms 496 KB Output is correct
10 Correct 31 ms 496 KB Output is correct
11 Incorrect 3 ms 496 KB Wrong Answer [2]
12 Halted 0 ms 0 KB -