oj.uz

Submission #45157

# Submission time Handle Problem Language Result Execution time Memory
45157 2018-04-11T14:46:18 Z ikura355 Library (JOI18_library) C++14
0 / 100
 67 ms 804 KB 
#include "library.h"
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 5;

int n;
int head[maxn], good[maxn], com[maxn];
vector<int> way[maxn];
vector<int> ans;

int ask(int l, int r, int x) {
    vector<int> vec;
    for(int i=1;i<=n;i++) {
        if(i==x || (l<=i && i<=r)) vec.push_back(1);
        else vec.push_back(0);
    }
    return Query(vec);
}

int findhead(int x) {
    if(head[x]==x) return x;
    return head[x] = findhead(head[x]);
}

int solve(int l, int r) {
    for(int u=1;u<=n;u++) {
        good[u] = (l<=u && u<=r);
        head[u] = u;
        com[u] = 0;
    }
    for(int u=1;u<=n;u++) {
        if(!good[u]) continue;
        for(auto v : way[u]) {
            if(!good[v]) continue;
            head[findhead(u)] = findhead(v);
        }
    }
    for(int u=1;u<=n;u++) if(good[u]) com[head[u]] = 1;
    int res = 0;
    for(int u=1;u<=n;u++) res += com[u];
    return res;
}

void addedge(int x, int l, int r) {
    if(l>r) return ;
//    printf("ask [%d, %d] : %d = %d\n",l,r,x,ask(l,r,x));
//    printf("solve [%d, %d] : %d\n",l,r,solve(l,r));
    if(ask(l,r,x)>solve(l,r)) return ;
    if(l==r) {
//        printf("%d <-> %d\n",l,x);
        way[x].push_back(l);
        way[l].push_back(x);
        return ;
    }
    int mid = (l+r)/2;
    addedge(x,l,mid); addedge(x,mid+1,r);
}

void dfs(int u, int last) {
    ans.push_back(u);
    for(auto v : way[u]) {
        if(v==last) continue;
        dfs(v, u);
    }
}

void Solve(int N) {
    n = N;
    for(int x=2;x<=n;x++) addedge(x,1,x-1);
    for(int x=1;x<=n;x++) {
        if(way[x].size()==1) {
            dfs(x, 0);
            Answer(ans);
            return ;
        }
    }
    assert(0);
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 324 KB Output is correct
2 Correct 59 ms 408 KB Output is correct
3 Correct 56 ms 408 KB Output is correct
4 Correct 51 ms 444 KB Output is correct
5 Correct 62 ms 588 KB Output is correct
6 Correct 67 ms 588 KB Output is correct
7 Correct 66 ms 588 KB Output is correct
8 Correct 57 ms 588 KB Output is correct
9 Correct 51 ms 588 KB Output is correct
10 Correct 32 ms 588 KB Output is correct
11 Runtime error 2 ms 804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 324 KB Output is correct
2 Correct 59 ms 408 KB Output is correct
3 Correct 56 ms 408 KB Output is correct
4 Correct 51 ms 444 KB Output is correct
5 Correct 62 ms 588 KB Output is correct
6 Correct 67 ms 588 KB Output is correct
7 Correct 66 ms 588 KB Output is correct
8 Correct 57 ms 588 KB Output is correct
9 Correct 51 ms 588 KB Output is correct
10 Correct 32 ms 588 KB Output is correct
11 Runtime error 2 ms 804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -