oj.uz

Submission #108644

# Submission time Handle Problem Language Result Execution time Memory
108644 2019-04-30T13:12:25 Z someone_aa Library (JOI18_library) C++17
19 / 100
 527 ms 644 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() == 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 50 ms 384 KB # of queries: 3164
2 Correct 47 ms 348 KB # of queries: 3145
3 Correct 46 ms 384 KB # of queries: 3316
4 Correct 54 ms 348 KB # of queries: 3316
5 Correct 67 ms 356 KB # of queries: 6284
6 Correct 44 ms 512 KB # of queries: 3316
7 Correct 52 ms 384 KB # of queries: 3316
8 Correct 44 ms 384 KB # of queries: 3182
9 Correct 49 ms 348 KB # of queries: 3297
10 Correct 17 ms 348 KB # of queries: 1965
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 2 ms 384 KB # of queries: 8
13 Correct 2 ms 256 KB # of queries: 17
14 Correct 2 ms 384 KB # of queries: 38
15 Correct 4 ms 256 KB # of queries: 137
16 Correct 6 ms 256 KB # of queries: 303

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 384 KB # of queries: 3164
2 Correct 47 ms 348 KB # of queries: 3145
3 Correct 46 ms 384 KB # of queries: 3316
4 Correct 54 ms 348 KB # of queries: 3316
5 Correct 67 ms 356 KB # of queries: 6284
6 Correct 44 ms 512 KB # of queries: 3316
7 Correct 52 ms 384 KB # of queries: 3316
8 Correct 44 ms 384 KB # of queries: 3182
9 Correct 49 ms 348 KB # of queries: 3297
10 Correct 17 ms 348 KB # of queries: 1965
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 2 ms 384 KB # of queries: 8
13 Correct 2 ms 256 KB # of queries: 17
14 Correct 2 ms 384 KB # of queries: 38
15 Correct 4 ms 256 KB # of queries: 137
16 Correct 6 ms 256 KB # of queries: 303
17 Runtime error 519 ms 636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 487 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 454 ms 624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Correct 443 ms 368 KB # of queries: 19652
21 Correct 489 ms 368 KB # of queries: 18527
22 Runtime error 527 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 477 ms 624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Correct 161 ms 256 KB # of queries: 9785
25 Runtime error 472 ms 644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Correct 351 ms 364 KB # of queries: 19216
27 Correct 128 ms 444 KB # of queries: 9739
28 Runtime error 395 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 390 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 517 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)