제출 #862693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862693		eitanelb	도서관 (JOI18_library)	C++14	100 / 100	265 ms	1224 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int n,x,y;
void search(vector<int> &st, vector<int>&rest, int r){
    if(st.size() == 1){
        if(x==-1) x=st[0];
        else y=st[0];
        return;
    }
    vector<int> v1(n,0),v2(n,0);
    int m = st.size() / 2;
    for(int i=0;i<m;i++){
        v1[st[i]]=1;
    }
    for(int i=m;i<st.size();i++){
        v2[st[i]]=1;
    }
    for(int i : rest) v2[i]=1;
    int a1 = Query(v1), a2 = Query(v2);
    if(r==2){
        if(a1 == a2){
            vector<int> n1, n2, rest1=rest, rest2=rest;
            for(int i= 0;i<m;i++){
                n1.push_back(st[i]); rest2.push_back(st[i]);
            }
            for(int i=m;i<st.size();i++){
                n2.push_back(st[i]); rest1.push_back(st[i]);
            }
            search(n1,rest1,1);
            search(n2,rest2,1);
        }
        else if(a2 > a1){
            vector<int> st0;
            for(int i= 0;i<m;i++) rest.push_back(st[i]);
            for(int i=m;i<st.size();i++) st0.push_back(st[i]);
            search(st0,rest,2);
        }
        else{
            vector<int> st0;
            for(int i= 0;i<m;i++) st0.push_back(st[i]);
            for(int i=m;i<st.size();i++) rest.push_back(st[i]);
            search(st0,rest,2);
        }
    }
    else{
        if(a1 >= a2){
            vector<int> st0;
            for(int i= 0;i<m;i++) st0.push_back(st[i]);
            for(int i=m;i<st.size();i++) rest.push_back(st[i]);
            search(st0,rest,1);
        }
        else{
            vector<int> st0;
            for(int i= 0;i<m;i++) rest.push_back(st[i]);
            for(int i=m;i<st.size();i++) st0.push_back(st[i]);
            search(st0,rest,1);
        }
    }
}

void Solve(int N){
	n=N;
	set<int> st;
	for(int i = 0; i<n;i++) st.insert(i);
	vector<int> res(n);
	while(st.size() > 1){
	    x=y=-1;
	    vector<int> vec,rest;
	    for(int i : st) vec.push_back(i);
	    search(vec,rest,2);
	    if(st.size() == n){
	        res[0] = x;
	        res[n-1] = y;
	    }
	    else{
	        int u = (n - st.size()) / 2;
	        vector<int> m(n,0); m[x]=1; m[res[u-1]]=1;
	        if(Query(m) == 1){
	            res[u]=x; res[n-u-1]=y;
	        }
	        else{
	            res[u]=y; res[n-u-1]=x;
	        }
	    }
	    st.erase(st.find(x));
	    st.erase(st.find(y));
	}
	if(st.size() == 1) res[n/2] = *st.begin();
	for(int&i:res)i++;
	Answer(res);
}

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

library.cpp: In function 'void search(std::vector<int>&, std::vector<int>&, int)':
library.cpp:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=m;i<st.size();i++){
      |                 ~^~~~~~~~~~
library.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             for(int i=m;i<st.size();i++){
      |                         ~^~~~~~~~~~
library.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             for(int i=m;i<st.size();i++) st0.push_back(st[i]);
      |                         ~^~~~~~~~~~
library.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             for(int i=m;i<st.size();i++) rest.push_back(st[i]);
      |                         ~^~~~~~~~~~
library.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for(int i=m;i<st.size();i++) rest.push_back(st[i]);
      |                         ~^~~~~~~~~~
library.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             for(int i=m;i<st.size();i++) st0.push_back(st[i]);
      |                         ~^~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:72:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |      if(st.size() == n){
      |         ~~~~~~~~~~^~~~

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81