oj.uz

Submission #108646

# Submission time Handle Problem Language Result Execution time Memory
108646 2019-04-30T13:13:38 Z someone_aa Library (JOI18_library) C++17
0 / 100
 519 ms 636 KB 
#include <cstdio>
#include <vector>
#include "library.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int maxn = 1500;
vector<int>adj[maxn];
vector<int>M;
int n;


int preQuery(vector<int>M) {
    int br = 0;
    for(int i:M) {
        if(i == 1) br++;
    }

    if(br == 0) return 0;
    else return Query(M);
}

int find_neighbour(int x, int l=1, int r=n) {
    if(l > r) return -1;

    if(l == r) {
        // check if X is connected to L or not

        M[l-1] = M[x-1] = 1;
        int curr = preQuery(M);
        M[l-1] = M[x-1] = 0;

        if(curr == 1) return l;
        else return -1;
    }

    int mid = (l + r) /2;
    for(int i=l-1;i<=mid-1;i++) {
        M[i] = 1;
    }

    for(int i:adj[x]) {
        M[i-1] = 0;
    }

    M[x-1] = 0;

    int Without = preQuery(M);
    M[x-1] = 1;
    int With = preQuery(M);
    M[x-1] = 0;

    for(int i=l-1;i<=mid-1;i++) {
        M[i] = 0;
    }

    if(With == Without) {
        return find_neighbour(x, l, mid);
    }
    else if(With < Without) {
        return find_neighbour(x, l, mid);
    }
    else {
        return find_neighbour(x, mid+1, r);
    }
}

void Solve(int N) {
    n = N;
	for(int i=0;i<N;i++) {
		M.pb(0);
	}

	if(N == 1) {
        vector<int>v;
        v.pb(1);
        Answer(v);
        return;
	}

	int st = 1;
    bool check = false;
    for(int i=0;i<2*N;i++) {
        int X = find_neighbour(st);
        if(X == -1) {
            // st is on corner
            if(st == 1) {
                break;
            }
            else {
                st = 1;
            }
        }
        else {
            adj[st].pb(X);
            adj[X].pb(st);
            st = X;
        }
    }

    /*for(int i=1;i<=n;i++) {
        cout<<i<<": \n";
        for(int j:adj[i]) {
            cout<<j<<" ";
        } cout<<"\n";
    }*/

    st = 1;
    bool found = false;
    for(int i=1;i<=N;i++) {
        if(adj[i].size() == 0 || adj[i].size() > 2) return;
        if(adj[i].size() == 1) {
            st = i;
            found = true;
            break;
        }
    }

    if(!found) {
        return;
    }

    vector<int>v;
    v.pb(st);
    st = adj[st][0];
    for(int i=0;i<N-1;i++) {
        if(adj[st][0] == v.back()) {
            v.pb(st);
            st = adj[st][1];
        }
        else {
            v.pb(st);
            st = adj[st][0];
        }
    }
    Answer(v);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:83:10: warning: unused variable 'check' [-Wunused-variable]
     bool check = false;
          ^~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 256 KB # of queries: 3164
2 Correct 35 ms 352 KB # of queries: 3145
3 Correct 56 ms 428 KB # of queries: 3316
4 Correct 41 ms 384 KB # of queries: 3316
5 Incorrect 79 ms 352 KB Wrong Answer [7]
6 Correct 43 ms 384 KB # of queries: 3316
7 Correct 39 ms 256 KB # of queries: 3316
8 Correct 30 ms 352 KB # of queries: 3182
9 Correct 58 ms 384 KB # of queries: 3297
10 Correct 41 ms 328 KB # of queries: 1965
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 3 ms 256 KB # of queries: 8
13 Correct 2 ms 384 KB # of queries: 17
14 Correct 2 ms 384 KB # of queries: 38
15 Correct 3 ms 256 KB # of queries: 137
16 Correct 5 ms 256 KB # of queries: 303

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 256 KB # of queries: 3164
2 Correct 35 ms 352 KB # of queries: 3145
3 Correct 56 ms 428 KB # of queries: 3316
4 Correct 41 ms 384 KB # of queries: 3316
5 Incorrect 79 ms 352 KB Wrong Answer [7]
6 Correct 43 ms 384 KB # of queries: 3316
7 Correct 39 ms 256 KB # of queries: 3316
8 Correct 30 ms 352 KB # of queries: 3182
9 Correct 58 ms 384 KB # of queries: 3297
10 Correct 41 ms 328 KB # of queries: 1965
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 3 ms 256 KB # of queries: 8
13 Correct 2 ms 384 KB # of queries: 17
14 Correct 2 ms 384 KB # of queries: 38
15 Correct 3 ms 256 KB # of queries: 137
16 Correct 5 ms 256 KB # of queries: 303
17 Incorrect 350 ms 380 KB Wrong Answer [3]
18 Incorrect 519 ms 372 KB Wrong Answer [3]
19 Runtime error 470 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Correct 489 ms 384 KB # of queries: 19652
21 Correct 477 ms 388 KB # of queries: 18527
22 Incorrect 482 ms 384 KB Wrong Answer [3]
23 Incorrect 392 ms 372 KB Wrong Answer [3]
24 Correct 214 ms 372 KB # of queries: 9785
25 Incorrect 509 ms 384 KB Wrong Answer [3]
26 Correct 345 ms 448 KB # of queries: 19216
27 Correct 172 ms 384 KB # of queries: 9739
28 Runtime error 416 ms 628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 431 ms 616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 396 ms 636 KB Execution killed with signal 11 (could be triggered by violating memory limits)