oj.uz

Submission #108656

# Submission time Handle Problem Language Result Execution time Memory
108656 2019-04-30T13:30:54 Z someone_aa Library (JOI18_library) C++17
0 / 100
 557 ms 868 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 {
        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;
        }
    }

    if(adj[1].size() == 1) return;

    /*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:80:10: warning: unused variable 'check' [-Wunused-variable]
     bool check = false;
          ^~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 436 KB # of queries: 3134
2 Correct 62 ms 256 KB # of queries: 3115
3 Correct 50 ms 384 KB # of queries: 3286
4 Correct 48 ms 256 KB # of queries: 3286
5 Correct 47 ms 304 KB # of queries: 3284
6 Correct 68 ms 352 KB # of queries: 3286
7 Correct 66 ms 352 KB # of queries: 3286
8 Correct 35 ms 460 KB # of queries: 3152
9 Correct 47 ms 356 KB # of queries: 3267
10 Correct 42 ms 384 KB # of queries: 1935
11 Correct 3 ms 384 KB # of queries: 0
12 Incorrect 2 ms 384 KB Wrong Answer [7]
13 Correct 2 ms 304 KB # of queries: 8
14 Incorrect 3 ms 384 KB Wrong Answer [7]
15 Incorrect 3 ms 256 KB Wrong Answer [7]
16 Correct 6 ms 256 KB # of queries: 285

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 436 KB # of queries: 3134
2 Correct 62 ms 256 KB # of queries: 3115
3 Correct 50 ms 384 KB # of queries: 3286
4 Correct 48 ms 256 KB # of queries: 3286
5 Correct 47 ms 304 KB # of queries: 3284
6 Correct 68 ms 352 KB # of queries: 3286
7 Correct 66 ms 352 KB # of queries: 3286
8 Correct 35 ms 460 KB # of queries: 3152
9 Correct 47 ms 356 KB # of queries: 3267
10 Correct 42 ms 384 KB # of queries: 1935
11 Correct 3 ms 384 KB # of queries: 0
12 Incorrect 2 ms 384 KB Wrong Answer [7]
13 Correct 2 ms 304 KB # of queries: 8
14 Incorrect 3 ms 384 KB Wrong Answer [7]
15 Incorrect 3 ms 256 KB Wrong Answer [7]
16 Correct 6 ms 256 KB # of queries: 285
17 Runtime error 557 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 496 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Incorrect 455 ms 384 KB Wrong Answer [3]
20 Correct 506 ms 552 KB # of queries: 19614
21 Correct 484 ms 592 KB # of queries: 18489
22 Runtime error 488 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 475 ms 868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Correct 228 ms 488 KB # of queries: 9747
25 Runtime error 486 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Correct 431 ms 480 KB # of queries: 19178
27 Correct 210 ms 424 KB # of queries: 9705
28 Incorrect 491 ms 484 KB Wrong Answer [3]
29 Incorrect 407 ms 552 KB Wrong Answer [3]
30 Incorrect 460 ms 484 KB Wrong Answer [3]