oj.uz

Submission #232881

# Submission time Handle Problem Language Result Execution time Memory
232881 2020-05-18T14:36:25 Z Charis02 Library (JOI18_library) C++14
0 / 100
 545 ms 504 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(prefix[i]-prefix[i-1] > 1)
            {
                low = pos+1;
                high=i-1;
                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].second = pos;
            }
        }
        if(i < N-1 && suffix[i+1] < suffix[i])
        {
            int low = i+1;
            int high = N-1;
            int pos = i+1;

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

                if(join_suf(mid,i) > suffix[mid])
                {
                    low=mid+1;
                    pos=max(pos,mid);
                }
                else
                    high=mid-1;
            }

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

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

                    if(join_suf(mid,i) > suffix[mid])
                    {
                        low=mid+1;
                        pos=max(pos,mid);
                    }
                    else
                        high=mid-1;
                }


                adj[i].second = pos;
            }
        }
    }

	vector<int> res(N);

	int cur = 0;
	int par = 0;

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

  //  cout << "here\n";
    for(int i = 0;i < N;i++)
    {
        res[i] = cur+1;
//        cout << cur << " ";
        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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 384 KB Wrong Answer [6]
2 Incorrect 59 ms 384 KB Wrong Answer [6]
3 Incorrect 53 ms 384 KB Wrong Answer [6]
4 Incorrect 56 ms 384 KB Wrong Answer [6]
5 Incorrect 58 ms 384 KB Wrong Answer [5]
6 Incorrect 55 ms 384 KB Wrong Answer [6]
7 Incorrect 63 ms 384 KB Wrong Answer [6]
8 Incorrect 61 ms 384 KB Wrong Answer [6]
9 Incorrect 62 ms 384 KB Wrong Answer [6]
10 Incorrect 35 ms 384 KB Wrong Answer [6]
11 Correct 5 ms 384 KB # of queries: 2
12 Correct 5 ms 384 KB # of queries: 6
13 Correct 5 ms 384 KB # of queries: 11
14 Correct 5 ms 256 KB # of queries: 17
15 Incorrect 7 ms 384 KB Wrong Answer [6]
16 Incorrect 8 ms 256 KB Wrong Answer [6]

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 384 KB Wrong Answer [6]
2 Incorrect 59 ms 384 KB Wrong Answer [6]
3 Incorrect 53 ms 384 KB Wrong Answer [6]
4 Incorrect 56 ms 384 KB Wrong Answer [6]
5 Incorrect 58 ms 384 KB Wrong Answer [5]
6 Incorrect 55 ms 384 KB Wrong Answer [6]
7 Incorrect 63 ms 384 KB Wrong Answer [6]
8 Incorrect 61 ms 384 KB Wrong Answer [6]
9 Incorrect 62 ms 384 KB Wrong Answer [6]
10 Incorrect 35 ms 384 KB Wrong Answer [6]
11 Correct 5 ms 384 KB # of queries: 2
12 Correct 5 ms 384 KB # of queries: 6
13 Correct 5 ms 384 KB # of queries: 11
14 Correct 5 ms 256 KB # of queries: 17
15 Incorrect 7 ms 384 KB Wrong Answer [6]
16 Incorrect 8 ms 256 KB Wrong Answer [6]
17 Incorrect 519 ms 392 KB Wrong Answer [3]
18 Incorrect 532 ms 384 KB Wrong Answer [6]
19 Incorrect 544 ms 384 KB Wrong Answer [6]
20 Incorrect 502 ms 384 KB Wrong Answer [6]
21 Incorrect 431 ms 384 KB Wrong Answer [6]
22 Incorrect 540 ms 384 KB Wrong Answer [3]
23 Incorrect 515 ms 384 KB Wrong Answer [3]
24 Incorrect 202 ms 384 KB Wrong Answer [6]
25 Incorrect 528 ms 384 KB Wrong Answer [5]
26 Incorrect 448 ms 504 KB Wrong Answer [6]
27 Incorrect 185 ms 384 KB Wrong Answer [5]
28 Correct 542 ms 384 KB # of queries: 19452
29 Correct 542 ms 384 KB # of queries: 19430
30 Correct 545 ms 384 KB # of queries: 19452