Submission #95227

#	Time	Username	Problem	Language	Result	Execution time	Memory
95227		Bodo171	Library (JOI18_library)	C++14	100 / 100	277 ms	3040 KiB

library

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include "library.h"
using namespace std;
const int nmax=1005;
int n;
vector<int> M;
vector<int> compo[nmax];
vector<int> rel;
int prz[nmax];
int ad[2];
int i,j,wh,curr,p,nr;
int D(int cate)
{
    for(i=0;i<n;i++)
        M[i]=0;
    for(i=0;i<cate;i++)
    {
        wh=rel[i];
        for(j=0;j<compo[wh].size();j++)
        {
            M[compo[wh][j]-1]=1;
        }
    }
    M[curr-1]=1;
    return (cate-Query(M));
}
void bs(int dif)
{
    int ret=0;
    for(p=9;p>=0;p--)
        if(ret+(1<<p)<rel.size()&&D(ret+(1<<p))<dif)
             ret+=(1<<p);
    ad[dif]=rel[ret];
}
bool adiacent(int x,int y)
{
    for(i=0;i<n;i++)
        M[i]=0;
    M[x-1]=M[y-1]=1;
    return (Query(M)==1);
}
void lipeste()
{
    ++nr;
    if(ad[0])
    {
        if(!adiacent(compo[ad[0]].back(),curr))
            reverse(compo[ad[0]].begin(),compo[ad[0]].end());
        for(i=0;i<compo[ad[0]].size();i++)
            compo[nr].push_back(compo[ad[0]][i]);
        compo[ad[0]].clear();
    }
    compo[nr].push_back(curr);
    if(ad[1])
    {
        if(!adiacent(compo[ad[1]][0],curr))
            reverse(compo[ad[1]].begin(),compo[ad[1]].end());
        for(i=0;i<compo[ad[1]].size();i++)
            compo[nr].push_back(compo[ad[1]][i]);
        compo[ad[1]].clear();
    }
}
void Solve(int N)
{
    n=N;
    for(i=0;i<n;i++)
        M.push_back(0);
    nr=1;compo[nr].push_back(1);
    prz[1]=1;
    for(curr=2;curr<=N;curr++)
    {
        for(j=0;j<n;j++)
            M[j]=0;
        for(j=0;j<curr;j++)
            M[j]=1;
        prz[curr]=Query(M);
        rel.clear();
        for(i=1;i<=nr;i++)
            if(compo[i].size())
              rel.push_back(i);
        ad[0]=ad[1]=0;
        if(prz[curr]<=prz[curr-1]) bs(0);
        if(prz[curr]==prz[curr-1]-1) bs(1);
        lipeste();
    }
    vector<int> res(N);
	for(int i = 0; i < N; i++) {
		res[i] = compo[nr][i];
	}
	Answer(res);
}

Compilation message (stderr)

library.cpp: In function 'int D(int)':
library.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<compo[wh].size();j++)
                 ~^~~~~~~~~~~~~~~~~
library.cpp: In function 'void bs(int)':
library.cpp:34:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ret+(1<<p)<rel.size()&&D(ret+(1<<p))<dif)
            ~~~~~~~~~~^~~~~~~~~~~
library.cpp: In function 'void lipeste()':
library.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<compo[ad[0]].size();i++)
                 ~^~~~~~~~~~~~~~~~~~~~
library.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<compo[ad[1]].size();i++)
                 ~^~~~~~~~~~~~~~~~~~~~

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