oj.uz

Submission #1068805

# Submission time Handle Problem Language Result Execution time Memory
1068805 2024-08-21T12:17:29 Z _8_8_ Chameleon's Love (JOI20_chameleon) C++17
4 / 100
 48 ms 624 KB 
#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 12;
vector<int> g[N];
int n;
void make(vector<int> &l,vector<int> &r,int i) {
    l.clear();
    r.clear();
    vector<int> d(N,0);
    function<void(int)>dfs = [&](int v) {
        if(d[v] & 1) {
            l.push_back(v);
        } else {
            r.push_back(v);
        }
        for(int to:g[v]) {
            if(!d[to]) {
                d[to] = d[v] + 1;
                dfs(to);
            }
        }
    };
    for(int j = 1;j < i;j++) {
        if(!d[j]) {
            d[j] = 1;
            dfs(j);
        }
    }
}
bool vis[N];
void Solve(int n_) {
    n = n_;
    vector<int> l,r;
    for(int i = 2;i <= n + n;i++) {
        make(l,r,i);
        auto ed = [&](vector<int> &x) -> void{
            int it = 0,m = (int)x.size();
            while(it < m) {
                int l = it - 1,r = m;
                while(r - l > 1) {
                    int mid = (l + r) >> 1;
                    vector<int> t(1,i);
                    for(int j = it; j <= mid; ++j) {
                        t.push_back(x[j]);
                    }
                    if(Query(t) != (int)t.size()) {
                        r = mid; 
                    } else {
                        l = mid;
                    }
                }
                if(r != m) {
                    g[i].push_back(x[r]);
                    g[x[r]].push_back(i);
                }
                it = r + 1;
            }
        };
        ed(l);
        ed(r);
        // return; 
    }
    for(int i = 1;i <= n + n;i++) {
        if(vis[i]) continue;
        Answer(i,g[i][0]);
        vis[g[i][0]] = 1;
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 36 ms 624 KB Output is correct
4 Correct 41 ms 600 KB Output is correct
5 Correct 36 ms 600 KB Output is correct
6 Correct 36 ms 600 KB Output is correct
7 Correct 36 ms 600 KB Output is correct
8 Correct 48 ms 620 KB Output is correct
9 Correct 45 ms 600 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 0 ms 600 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 0 ms 600 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Incorrect 0 ms 600 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 36 ms 624 KB Output is correct
4 Correct 41 ms 600 KB Output is correct
5 Correct 36 ms 600 KB Output is correct
6 Correct 36 ms 600 KB Output is correct
7 Correct 36 ms 600 KB Output is correct
8 Correct 48 ms 620 KB Output is correct
9 Correct 45 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Incorrect 0 ms 600 KB Wrong Answer [6]
12 Halted 0 ms 0 KB -