oj.uz

Submission #412098

# Submission time Handle Problem Language Result Execution time Memory
412098 2021-05-26T13:54:35 Z benedict0724 Library (JOI18_library) C++17
0 / 100
 53 ms 324 KB 
#include <cstdio>
#include <vector>
#include <assert.h>
#include "library.h"
using namespace std;

vector<int> adj[1000];
int lin[1000], U[1000];
int _find(int x)
{
    if(x == lin[x]) return x;
    return lin[x] = _find(lin[x]);
}

void Solve(int N)
{
	vector<int> M(N);
	for(int i=0;i<N;i++) adj[i].clear();
	for(int i=0;i<N;i++) M[i] = 0;
	M[0] = 1;
	int P = 1;
	for(int i = 1; i < N; i++) {
        int l = 0, r = i-1;
        M[i] = 1;
        int Q = Query(M);
        if(P < Q) { P = Q; continue; }
        while(l < r)
        {
            vector<int> v(N);
            int mid = (l + r)/2;
            for(int j=0;j<=mid;j++) v[j] = 1;
            int A, B;
            A = Query(v);
            v[i] = 1;
            B = Query(v);

            if(A >= B) r = mid;
            else l = mid+1;
        }
        adj[i].push_back(l);
        adj[l].push_back(i);

        if(P == Q) continue;
        l = 0, r = i-1;
        while(l < r)
        {
            vector<int> v(N);
            int mid = (l + r)/2;
            for(int j=0;j<=mid;j++) v[j] = 1;
            int A, B;
            A = Query(v);
            v[i] = 1;
            B = Query(v);
            if(A > B) r = mid;
            else l = mid+1;
        }

        adj[l].push_back(i);
        adj[i].push_back(l);

        P = Q;
	}

	vector<int> res(N);

	int st = -1;
	for(int i=0;i<N;i++) if(adj[i].size() == 1) st = i;
	int sum = 0;
	for(int i=0;i<N;i++) sum += adj[i].size();
	for(int i=0;i<N;i++) for(int j : adj[i]) assert(j >= 0 && j < N);
	assert(sum == 2 * N - 2);
	for(int i=0,now=st;i<N;i++)
    {
        res[i] = now+1;
        int tmp = -1;
        for(int nxt : adj[now])
        {
            if(!U[nxt])
            {
                tmp = nxt;
                break;
            }
        }
        U[now] = 1;
        now = tmp;
    }

	Answer(res);
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 200 KB # of queries: 2853
2 Correct 38 ms 200 KB # of queries: 2820
3 Correct 51 ms 304 KB # of queries: 2973
4 Correct 35 ms 320 KB # of queries: 2967
5 Correct 41 ms 324 KB # of queries: 2953
6 Correct 51 ms 316 KB # of queries: 2963
7 Correct 52 ms 300 KB # of queries: 2997
8 Correct 43 ms 200 KB # of queries: 2840
9 Correct 53 ms 308 KB # of queries: 2996
10 Correct 26 ms 200 KB # of queries: 1750
11 Incorrect 1 ms 200 KB Wrong Answer [5]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 200 KB # of queries: 2853
2 Correct 38 ms 200 KB # of queries: 2820
3 Correct 51 ms 304 KB # of queries: 2973
4 Correct 35 ms 320 KB # of queries: 2967
5 Correct 41 ms 324 KB # of queries: 2953
6 Correct 51 ms 316 KB # of queries: 2963
7 Correct 52 ms 300 KB # of queries: 2997
8 Correct 43 ms 200 KB # of queries: 2840
9 Correct 53 ms 308 KB # of queries: 2996
10 Correct 26 ms 200 KB # of queries: 1750
11 Incorrect 1 ms 200 KB Wrong Answer [5]
12 Halted 0 ms 0 KB -