oj.uz

Submission #108647

# Submission time Handle Problem Language Result Execution time Memory
108647 2019-04-30T13:15:35 Z someone_aa Library (JOI18_library) C++17
19 / 100
 537 ms 872 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<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
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 384 KB # of queries: 3134
2 Correct 32 ms 384 KB # of queries: 3115
3 Correct 71 ms 384 KB # of queries: 3286
4 Correct 51 ms 436 KB # of queries: 3286
5 Correct 60 ms 348 KB # of queries: 3284
6 Correct 70 ms 356 KB # of queries: 3286
7 Correct 59 ms 304 KB # of queries: 3286
8 Correct 48 ms 356 KB # of queries: 3152
9 Correct 55 ms 256 KB # of queries: 3267
10 Correct 37 ms 356 KB # of queries: 1935
11 Correct 2 ms 256 KB # of queries: 0
12 Correct 2 ms 384 KB # of queries: 4
13 Correct 2 ms 384 KB # of queries: 8
14 Correct 3 ms 348 KB # of queries: 18
15 Correct 6 ms 256 KB # of queries: 130
16 Correct 7 ms 384 KB # of queries: 285

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 384 KB # of queries: 3134
2 Correct 32 ms 384 KB # of queries: 3115
3 Correct 71 ms 384 KB # of queries: 3286
4 Correct 51 ms 436 KB # of queries: 3286
5 Correct 60 ms 348 KB # of queries: 3284
6 Correct 70 ms 356 KB # of queries: 3286
7 Correct 59 ms 304 KB # of queries: 3286
8 Correct 48 ms 356 KB # of queries: 3152
9 Correct 55 ms 256 KB # of queries: 3267
10 Correct 37 ms 356 KB # of queries: 1935
11 Correct 2 ms 256 KB # of queries: 0
12 Correct 2 ms 384 KB # of queries: 4
13 Correct 2 ms 384 KB # of queries: 8
14 Correct 3 ms 348 KB # of queries: 18
15 Correct 6 ms 256 KB # of queries: 130
16 Correct 7 ms 384 KB # of queries: 285
17 Incorrect 437 ms 376 KB Wrong Answer [3]
18 Incorrect 418 ms 484 KB Wrong Answer [3]
19 Runtime error 447 ms 636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Correct 396 ms 488 KB # of queries: 19614
21 Correct 375 ms 368 KB # of queries: 18489
22 Incorrect 488 ms 620 KB Wrong Answer [3]
23 Incorrect 492 ms 428 KB Wrong Answer [3]
24 Correct 158 ms 384 KB # of queries: 9747
25 Incorrect 481 ms 620 KB Wrong Answer [3]
26 Correct 537 ms 504 KB # of queries: 19178
27 Correct 160 ms 376 KB # of queries: 9705
28 Runtime error 417 ms 872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 422 ms 648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 488 ms 616 KB Execution killed with signal 11 (could be triggered by violating memory limits)