oj.uz

Submission #95227

# Submission time Handle Problem Language Result Execution time Memory
95227 2019-01-28T17:55:40 Z Bodo171 Library (JOI18_library) C++14
100 / 100
 277 ms 3040 KB 
#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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 516 KB # of queries: 1352
2 Correct 24 ms 248 KB # of queries: 1354
3 Correct 26 ms 376 KB # of queries: 1428
4 Correct 23 ms 248 KB # of queries: 1404
5 Correct 26 ms 376 KB # of queries: 1411
6 Correct 24 ms 248 KB # of queries: 1417
7 Correct 15 ms 344 KB # of queries: 1407
8 Correct 17 ms 352 KB # of queries: 1347
9 Correct 15 ms 348 KB # of queries: 1408
10 Correct 14 ms 248 KB # of queries: 844
11 Correct 2 ms 252 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 2
13 Correct 2 ms 248 KB # of queries: 4
14 Correct 2 ms 376 KB # of queries: 8
15 Correct 3 ms 376 KB # of queries: 54
16 Correct 3 ms 248 KB # of queries: 120

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 516 KB # of queries: 1352
2 Correct 24 ms 248 KB # of queries: 1354
3 Correct 26 ms 376 KB # of queries: 1428
4 Correct 23 ms 248 KB # of queries: 1404
5 Correct 26 ms 376 KB # of queries: 1411
6 Correct 24 ms 248 KB # of queries: 1417
7 Correct 15 ms 344 KB # of queries: 1407
8 Correct 17 ms 352 KB # of queries: 1347
9 Correct 15 ms 348 KB # of queries: 1408
10 Correct 14 ms 248 KB # of queries: 844
11 Correct 2 ms 252 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 2
13 Correct 2 ms 248 KB # of queries: 4
14 Correct 2 ms 376 KB # of queries: 8
15 Correct 3 ms 376 KB # of queries: 54
16 Correct 3 ms 248 KB # of queries: 120
17 Correct 269 ms 448 KB # of queries: 9268
18 Correct 271 ms 508 KB # of queries: 9198
19 Correct 261 ms 376 KB # of queries: 9271
20 Correct 223 ms 376 KB # of queries: 8675
21 Correct 222 ms 504 KB # of queries: 8221
22 Correct 277 ms 492 KB # of queries: 9421
23 Correct 275 ms 360 KB # of queries: 9293
24 Correct 87 ms 488 KB # of queries: 4253
25 Correct 251 ms 344 KB # of queries: 9075
26 Correct 225 ms 388 KB # of queries: 8520
27 Correct 58 ms 344 KB # of queries: 4302
28 Correct 53 ms 2960 KB # of queries: 1998
29 Correct 70 ms 2984 KB # of queries: 1996
30 Correct 61 ms 3040 KB # of queries: 1998