oj.uz

Submission #48072

# Submission time Handle Problem Language Result Execution time Memory
48072 2018-05-10T02:47:54 Z kawaiigrabrielneko Library (JOI18_library) C++14
0 / 100
 51 ms 528 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

void Solve(int N){
	vector<int> A(N);
	vector<int> B(N);
	vector<int> AP(N);
	vector<int> AMB(N);
	vector<int> APUB(N);
	int na = N/2;
	vector<int> ans(N);
	for (int i = 0; i < N/2; i++){
        A[i] = 1;
        AP[i] = 0;
	}
	for (int i = N/2; i < N; i++){
        A[i] = 0;
        AP[i] = 1;
	}
	if (Query(A)<Query(AP)){
        for (int i = 0; i < N; i++){
            A[i] = 1 - A[i];
            AP[i] = 1 - AP[i];
        }
        na = N - na;
	}
	// A contains an endpoint
	while (na > 1){
        int nb = na/2;
        int ct = 0;
        for (int i = 0; i < N; i++){
            if (A[i]==1&&ct<nb){
                B[i] = 1;
                ct++;
            }
            else B[i] = 0;
            AMB[i] = A[i] - B[i];
            APUB[i] = 1 - AMB[i];
        }
        if (Query(AMB)<Query(APUB)){ // Endpoint in B
            for (int i = 0; i < N; i++){
                A[i] = B[i];
            }
            na = nb;
        }
        else { // Endpoint in A - B
            for (int i = 0; i < N; i++){
                A[i] = AMB[i];
            }
            na = na - nb;
        }
	}
	for (int i = 0; i < N; i++){
        if (A[i] == 1) ans[0] = i;
	}
	vector<int> M(N);
	vector<int> K(N);
	for (int i = 1; i < N; i++){
        int nm = N-i;
        for (int j = 0; j < N; j++){
            M[j] = 1;
        }
        for (int j = 0; j < i; j++){
            M[ans[j]] = 0;
        }
        while (nm > 1){
            int nk = nm/2;
            int ct = 0;
            for (int j = 0; j < N; j++){
                if (M[j]==1&&ct<nk){
                    ct++;
                    K[j] = 1;
                }
                else K[j] = 0;
            }
            int x = Query(K);
            K[ans[i-1]] = 1;
            if (x==Query(K)){
                K[ans[i-1]] = 0;
                nm = nk;
                for (int j = 0; j < N; j++){
                    M[j] = K[j];
                }
            }
            else {
                K[ans[i-1]] = 0;
                nm = nm - nk;
                for (int j = 0; j < N; j++){
                    M[j] = M[j] - K[j];
                }
            }
        }
        for (int j = 0; j < N; j++){
            if (M[j]==1) ans[i] = j;
        }
	}
	for (int i = 0; i < N; i++){
        ans[i]++;
	}
	Answer(ans);
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 248 KB Output is correct
2 Correct 33 ms 468 KB Output is correct
3 Correct 40 ms 468 KB Output is correct
4 Correct 34 ms 468 KB Output is correct
5 Correct 41 ms 468 KB Output is correct
6 Correct 41 ms 468 KB Output is correct
7 Correct 31 ms 468 KB Output is correct
8 Correct 51 ms 504 KB Output is correct
9 Correct 40 ms 528 KB Output is correct
10 Correct 21 ms 528 KB Output is correct
11 Incorrect 2 ms 528 KB Wrong Answer [2]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 248 KB Output is correct
2 Correct 33 ms 468 KB Output is correct
3 Correct 40 ms 468 KB Output is correct
4 Correct 34 ms 468 KB Output is correct
5 Correct 41 ms 468 KB Output is correct
6 Correct 41 ms 468 KB Output is correct
7 Correct 31 ms 468 KB Output is correct
8 Correct 51 ms 504 KB Output is correct
9 Correct 40 ms 528 KB Output is correct
10 Correct 21 ms 528 KB Output is correct
11 Incorrect 2 ms 528 KB Wrong Answer [2]
12 Halted 0 ms 0 KB -