oj.uz

Submission #108654

# Submission time Handle Problem Language Result Execution time Memory
108654 2019-04-30T13:26:50 Z someone_aa Library (JOI18_library) C++17
19 / 100
 581 ms 772 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;
    int br = 0;
    for(int i=0;i<N;i++) {
        int X;
        if(st == 1) {
            if(br == 0) {
                X = find_neighbour(st);
                br++;
            }
            else if(br == 1) {
                X = find_neighbour(st);
                br++;
            }
            else {
                break;
            }
        }
        else {
            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 424 KB # of queries: 3134
2 Correct 43 ms 348 KB # of queries: 3115
3 Correct 41 ms 384 KB # of queries: 3286
4 Correct 68 ms 412 KB # of queries: 3286
5 Correct 53 ms 352 KB # of queries: 3284
6 Correct 34 ms 356 KB # of queries: 3286
7 Correct 43 ms 436 KB # of queries: 3286
8 Correct 52 ms 424 KB # of queries: 3152
9 Correct 53 ms 384 KB # of queries: 3267
10 Correct 36 ms 348 KB # of queries: 1935
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 2 ms 384 KB # of queries: 4
13 Correct 2 ms 256 KB # of queries: 8
14 Correct 2 ms 256 KB # of queries: 18
15 Correct 4 ms 256 KB # of queries: 130
16 Correct 5 ms 384 KB # of queries: 285

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 424 KB # of queries: 3134
2 Correct 43 ms 348 KB # of queries: 3115
3 Correct 41 ms 384 KB # of queries: 3286
4 Correct 68 ms 412 KB # of queries: 3286
5 Correct 53 ms 352 KB # of queries: 3284
6 Correct 34 ms 356 KB # of queries: 3286
7 Correct 43 ms 436 KB # of queries: 3286
8 Correct 52 ms 424 KB # of queries: 3152
9 Correct 53 ms 384 KB # of queries: 3267
10 Correct 36 ms 348 KB # of queries: 1935
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 2 ms 384 KB # of queries: 4
13 Correct 2 ms 256 KB # of queries: 8
14 Correct 2 ms 256 KB # of queries: 18
15 Correct 4 ms 256 KB # of queries: 130
16 Correct 5 ms 384 KB # of queries: 285
17 Runtime error 442 ms 744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 389 ms 744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 424 ms 752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Correct 494 ms 616 KB # of queries: 19614
21 Correct 410 ms 380 KB # of queries: 18489
22 Runtime error 467 ms 628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 477 ms 636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Correct 157 ms 352 KB # of queries: 9747
25 Runtime error 390 ms 628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Correct 410 ms 424 KB # of queries: 19178
27 Correct 183 ms 376 KB # of queries: 9705
28 Runtime error 581 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 406 ms 752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 493 ms 772 KB Execution killed with signal 11 (could be triggered by violating memory limits)