oj.uz

Submission #232954

# Submission time Handle Problem Language Result Execution time Memory
232954 2020-05-18T18:22:57 Z Charis02 Library (JOI18_library) C++14
100 / 100
 326 ms 388 KB 
#include <cstdio>
#include <vector>
#include<iostream>
#define MAXN 1004
#include "library.h"
using namespace std;

pair < int,int > adj[MAXN];
int prefix[MAXN];
int suffix[MAXN];
int NN;

int adjacencies(vector < int > M)
{
    int ones = 0;
    for(int i = 0;i < NN;i++)
        ones+=M[i];
    return ones-Query(M);
}

int join_pref(int pref,int el)
{
    vector < int > M(NN);

    for(int i = 0;i < NN;i++)
        M[i]=0;
    M[el]=1;
    for(int i = 0;i <= pref;i++)
        M[i] = 1;

    return adjacencies(M);
}

int join_suf(int suf,int el)
{
    vector < int > M(NN);

    for(int i = 0;i < NN;i++)
        M[i]=0;
    M[el]=1;
    for(int i = NN-1;i>=suf;i--)
        M[i] = 1;

    return adjacencies(M);
}

void Solve(int N)
{
    NN=N;
	vector<int> M(N);

	for(int i = 0;i< N;i++)
        M[i] = 0;

	for(int i = 0; i < N; i++)
	{
	    adj[i] = make_pair(-1,-1);
	    M[i] = 1;

        prefix[i] = adjacencies(M);
	}

	for(int i = 0;i< N;i++)
        M[i] = 0;

    for(int i = N-1;i>=0;i--)
    {
        M[i]=1;
        suffix[i] = adjacencies(M);
    }

	for(int i = 0;i < N;i++)
    {
        if(i >= 0 && prefix[i-1] < prefix[i])
        {
            int low = 0;
            int high = i-1;
            int pos = i-1;

            while(low<=high)
            {
                int mid = (low+high)/2;

                if(join_pref(mid,i) > prefix[mid])
                {
                    high=mid-1;
                    pos=min(pos,mid);
                }
                else
                    low=mid+1;
            }

            adj[i].first = pos;

            if(adj[pos].first==-1)
                adj[pos].first=i;
            else
                adj[pos].second=i;
        }
        if(prefix[i]-prefix[i-1] == 2)
        {
            int low = adj[i].first+1;
            int high=i-1;
            int pos = i-1;

            while(low<=high)
            {
                int mid = (low+high)/2;

                if(join_pref(mid,i) > prefix[mid]+1)
                {
                    high=mid-1;
                    pos=min(pos,mid);
                }
                else
                    low=mid+1;
            }

            adj[i].second = pos;
            if(adj[pos].first==-1)
                adj[pos].first=i;
            else
                adj[pos].second=i;
        }
    }

	vector<int> res(N);

	int cur = 0;

	int par = 0;

	for(int i = 0;i < N;i++)
    {
        if(adj[i].first==-1||adj[i].second == -1)
        {
            cur=i;
            break;
        }
    }

    par=-1;

   // cout << endl << endl;

   // cout << "here " << cur << " " << adj[cur].first << "  " << adj[cur].second << " " << suffix[cur] << " " << suffix[cur+1] << " " << join_suf(cur,cur+1) <<endl;

   // cout << "here " << 68 << " " << adj[68].first << " " << adj[68].second << endl;
    for(int i = 0;i < N;i++)
    {
        res[i] = cur+1;
     //   cout << res[i] << endl;

        if(adj[cur].first==par)
        {
            par=cur;
            cur = adj[cur].second;
        }
        else
        {
            par=cur;
            cur=adj[cur].first;
        }
    }

	Answer(res);
}

/*
5
4 2 5 3 1
*/

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 384 KB # of queries: 1658
2 Correct 35 ms 256 KB # of queries: 1659
3 Correct 41 ms 384 KB # of queries: 1735
4 Correct 36 ms 384 KB # of queries: 1746
5 Correct 36 ms 384 KB # of queries: 1746
6 Correct 31 ms 384 KB # of queries: 1730
7 Correct 35 ms 384 KB # of queries: 1744
8 Correct 25 ms 388 KB # of queries: 1654
9 Correct 36 ms 384 KB # of queries: 1749
10 Correct 25 ms 384 KB # of queries: 1038
11 Correct 4 ms 384 KB # of queries: 2
12 Correct 4 ms 256 KB # of queries: 5
13 Correct 5 ms 384 KB # of queries: 8
14 Correct 4 ms 384 KB # of queries: 12
15 Correct 5 ms 388 KB # of queries: 72
16 Correct 7 ms 384 KB # of queries: 158

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 384 KB # of queries: 1658
2 Correct 35 ms 256 KB # of queries: 1659
3 Correct 41 ms 384 KB # of queries: 1735
4 Correct 36 ms 384 KB # of queries: 1746
5 Correct 36 ms 384 KB # of queries: 1746
6 Correct 31 ms 384 KB # of queries: 1730
7 Correct 35 ms 384 KB # of queries: 1744
8 Correct 25 ms 388 KB # of queries: 1654
9 Correct 36 ms 384 KB # of queries: 1749
10 Correct 25 ms 384 KB # of queries: 1038
11 Correct 4 ms 384 KB # of queries: 2
12 Correct 4 ms 256 KB # of queries: 5
13 Correct 5 ms 384 KB # of queries: 8
14 Correct 4 ms 384 KB # of queries: 12
15 Correct 5 ms 388 KB # of queries: 72
16 Correct 7 ms 384 KB # of queries: 158
17 Correct 285 ms 388 KB # of queries: 11045
18 Correct 267 ms 388 KB # of queries: 10930
19 Correct 301 ms 384 KB # of queries: 11044
20 Correct 297 ms 384 KB # of queries: 10303
21 Correct 227 ms 388 KB # of queries: 9713
22 Correct 283 ms 388 KB # of queries: 11071
23 Correct 292 ms 384 KB # of queries: 11039
24 Correct 111 ms 384 KB # of queries: 5182
25 Correct 286 ms 384 KB # of queries: 10815
26 Correct 255 ms 384 KB # of queries: 10099
27 Correct 101 ms 384 KB # of queries: 5164
28 Correct 290 ms 364 KB # of queries: 10977
29 Correct 326 ms 384 KB # of queries: 10965
30 Correct 284 ms 388 KB # of queries: 10977