oj.uz

답안 #58190

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58190 2018-07-17T06:20:50 Z 정원준(#1691) 도서관 (JOI18_library) C++11
100 / 100
 641 ms 576 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){
	if(N==1)
	{
		vector<int>yewe;
		yewe.push_back(1);
		Answer(yewe);
		return;
	}
	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:74:8: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ans[0]=start;
  ~~~~~~^~~~~~
library.cpp:93:8: warning: 'secon' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ans[1]=secon;
  ~~~~~~^~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 396 KB Output is correct
2 Correct 49 ms 396 KB Output is correct
3 Correct 53 ms 436 KB Output is correct
4 Correct 32 ms 436 KB Output is correct
5 Correct 44 ms 492 KB Output is correct
6 Correct 44 ms 496 KB Output is correct
7 Correct 49 ms 496 KB Output is correct
8 Correct 46 ms 516 KB Output is correct
9 Correct 53 ms 532 KB Output is correct
10 Correct 27 ms 532 KB Output is correct
11 Correct 2 ms 532 KB Output is correct
12 Correct 3 ms 532 KB Output is correct
13 Correct 3 ms 532 KB Output is correct
14 Correct 2 ms 532 KB Output is correct
15 Correct 5 ms 532 KB Output is correct
16 Correct 4 ms 532 KB Output is correct

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 396 KB Output is correct
2 Correct 49 ms 396 KB Output is correct
3 Correct 53 ms 436 KB Output is correct
4 Correct 32 ms 436 KB Output is correct
5 Correct 44 ms 492 KB Output is correct
6 Correct 44 ms 496 KB Output is correct
7 Correct 49 ms 496 KB Output is correct
8 Correct 46 ms 516 KB Output is correct
9 Correct 53 ms 532 KB Output is correct
10 Correct 27 ms 532 KB Output is correct
11 Correct 2 ms 532 KB Output is correct
12 Correct 3 ms 532 KB Output is correct
13 Correct 3 ms 532 KB Output is correct
14 Correct 2 ms 532 KB Output is correct
15 Correct 5 ms 532 KB Output is correct
16 Correct 4 ms 532 KB Output is correct
17 Correct 507 ms 568 KB Output is correct
18 Correct 614 ms 572 KB Output is correct
19 Correct 610 ms 572 KB Output is correct
20 Correct 518 ms 572 KB Output is correct
21 Correct 618 ms 572 KB Output is correct
22 Correct 526 ms 576 KB Output is correct
23 Correct 474 ms 576 KB Output is correct
24 Correct 152 ms 576 KB Output is correct
25 Correct 641 ms 576 KB Output is correct
26 Correct 588 ms 576 KB Output is correct
27 Correct 248 ms 576 KB Output is correct
28 Correct 536 ms 576 KB Output is correct
29 Correct 592 ms 576 KB Output is correct
30 Correct 520 ms 576 KB Output is correct