oj.uz

답안 #47118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
47118 2018-04-27T17:44:47 Z vanogam 도서관 (JOI18_library) C++14
0 / 100
 23 ms 376 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int d[1002][2],tmp=0,tt;
vector<int> emp;
vector<int> M,res;
int bs(vector<int> v,int t,int k){
    //for(auto it:v) cout<<it<<" ";cout<<endl;
    int sum=0;
    for(auto it:v) sum+=it;
    if(!sum) return -1;
    //cout<<sum<<"&";
    if(sum==2) {
        for(int i=0;i<v.size();i++)if(v[i] && i!=t) {
            if(d[i][0]==i && d[t][1]==t) {swap(d[i][0],d[t][1]);} else {swap(d[i][1],d[t][0]);}
            //cout<<"#"<<d[i][0]<<" "<<d[i][1]<<" "<<i<<"#";cout<<"#";cout<<"["<<i<<" "<<t<<"]";cout<<"{"<<i<<" "<<t<<"}";
            if(d[i][0]!=i && d[i][1]!=i) {M[i]=0;}
            if(d[t][0]!=t && d[t][1]!=t) {tmp++;}
            return i;
        }
    }
    int cnt=0,j=0,k1=0;
    int N=v.size();
    vector<int> v1=emp;
    v1[t]=1;//cout<<k<<":";
    for(int i=0;i<N;i++){
        if(i==t) continue;
        cnt+=v[i];
        if(cnt==2) {
            cnt=0;
            v[i]=0;

            if(!v[d[i][0]] && !v[d[i][1]]) k--;
            if(!v1[d[i][0]] && !v1[d[i][1]]) k1++;

            v1[i]=1;
        }
    }//cout<<"("<<k<<" "<<k1<<" "<<Query(v)<<")\n";

    if(Query(v)<=k) return bs(v,t,k); else return bs(v1,t,k1);
}

void Solve(int N)
{


    for(int i=0;i<N;i++){
        d[i][0]=i;
        d[i][1]=i;
        M.push_back(0);
    }
    emp=M;
	M[0]=1;
    int k=1,j;

    for(int i=1;i<N;i++){
        k=0;
        for(int i=0;i<N;i++){
            if(M[i]){
                //if(d[i][0]==i && d[i][1]==i) k++;
                if(d[i][0]==i) k++; else
                if(d[i][1]==i && !M[d[i][0]]) k++;
            }
        }
        M[i]=1;
        int l=Query(M);
        //cout<<l<<" "<<k<<":"<<endl;
        //for(auto it:M) cout<<it<<" ";cout<<endl;
        if(l>k) {k++;continue;}

        if(l<=k){
            j=bs(M,i,k);//cout<<"*"<<j<<" "<<tmp<<"*";
            if(l==k){k-=tmp;tmp=0;continue;}
            //k-=tmp;tmp=0;
        }

        //cout<<"!!!";
        tt=M[j];
        M[j]=0;
        //tt=0;
        if(d[j][0]==j || d[j][0]==i) k--; else
        if((d[j][1]==j || d[j][1]==i) && (!M[d[j][0]] ||d[j][0]==i)) k--;//cout<<"&&&"<<k<<" "<<d[j][0]<<" "<<d[j][1]<<" "<<j<<"&&";
        bs(M,i,k);
        //if(d[j][0]==j || d[j][1]==j) {k++;}
        //k-=tmp;tmp=0;
        M[j]=tt;
        M[i]=0;


    }
    int idx=0,pr=-1;
    for(int i=0;i<N;i++){
        if(d[i][0]==i || d[i][1]==i) {idx=i;break;}
    }//cout<<idx<<"%%";

    for(int i=0;i<N;i++){
        res.push_back(idx+1);
        //cout<<idx+1<<" ";
        if(d[idx][0]!=idx && d[idx][0]!=pr){pr=idx;idx=d[idx][0];}
        else {pr=idx;idx=d[idx][1];}
    }
	Answer(res);
}

Compilation message

library.cpp: In function 'int bs(std::vector<int>, int, int)':
library.cpp:14:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v.size();i++)if(v[i] && i!=t) {
                     ~^~~~~~~~~
library.cpp:22:15: warning: unused variable 'j' [-Wunused-variable]
     int cnt=0,j=0,k1=0;
               ^

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 376 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 376 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -