oj.uz

Submission #1068883

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

const int N = 5e3 + 12;
vector<int> g[N];
int n;
vector<int> f;
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 k = 0;k < i;k++) {
        int j = f[k];
        if(!d[j]) {
            d[j] = 1;
            dfs(j);
        }
    }
}
bool vis[N];
int to[N],fr[N];
set<int> st[N];
mt19937 rng(12321);
void Solve(int n_) {
    n = n_;
    vector<int> l,r;
    f.resize(n + n);
    iota(f.begin(),f.end(),1);
    shuffle(f.begin(),f.end(),rng);
    for(int _ = 1; _ < (int)f.size(); _++) {
        int i = f[_];
        make(l,r,_);
        auto ed = [&](vector<int> &x) -> void{
            int it = 0,m = (int)x.size();
            while(it < m) {
                if((int)g[i].size() == 3) break;
                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);
                }
                if((int)g[i].size() == 3) break;
                it = r + 1;
            }
        };
        ed(l);
        ed(r);
    }
    for(int i = 1;i <= n + n;i++) {
        if(vis[i]) continue;
        if(g[i].size() == 1) {
            Answer(i,g[i][0]);
            vis[i] = vis[g[i][0]] = 1;
        }
    }
    for(int i = 1;i <= n + n;i++) {
        if(vis[i]) continue;
        for(int j:g[i]) {
            if(vis[j]) continue;
            st[i].insert(j);
        }
    }
    for(int i = 1;i <= n + n;i++) {
        if(vis[i]) continue;
        if((int)st[i].size() == 1) continue;
        if((int)g[i].size() >= 2 &&Query({i,g[i][0],g[i][1]}) == 1) {
            st[i].erase(g[i][2]);
            st[g[i][2]].erase(i);
        } else if(g[i].size() >= 3 && Query({i,g[i][2],g[i][1]}) == 1) {
            st[i].erase(g[i][0]);
            st[g[i][0]].erase(i);
        } else if(g[i].size() >= 3 && Query({i,g[i][0],g[i][2]}) == 1){
            st[i].erase(g[i][1]);
            st[g[i][1]].erase(i);
        }
    }
    for(int i = 1;i <= n + n;i++) {
        if(vis[i] || st[i].empty()) continue;
        int t = (*st[i].begin());
        Answer(i,t);
        vis[i] = vis[t] = 1;
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 41 ms 844 KB Output is correct
4 Correct 40 ms 856 KB Output is correct
5 Correct 46 ms 848 KB Output is correct
6 Correct 40 ms 860 KB Output is correct
7 Correct 46 ms 856 KB Output is correct
8 Correct 40 ms 856 KB Output is correct
9 Correct 40 ms 856 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 0 ms 856 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 856 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 0 ms 856 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 856 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 2 ms 856 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 2 ms 856 KB Output is correct
18 Correct 1 ms 856 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 41 ms 844 KB Output is correct
4 Correct 40 ms 856 KB Output is correct
5 Correct 46 ms 848 KB Output is correct
6 Correct 40 ms 860 KB Output is correct
7 Correct 46 ms 856 KB Output is correct
8 Correct 40 ms 856 KB Output is correct
9 Correct 40 ms 856 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 0 ms 856 KB Output is correct
17 Correct 1 ms 856 KB Output is correct
18 Correct 1 ms 856 KB Output is correct
19 Correct 1 ms 856 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 856 KB Output is correct
22 Correct 1 ms 856 KB Output is correct
23 Correct 1 ms 856 KB Output is correct
24 Correct 2 ms 856 KB Output is correct
25 Correct 2 ms 600 KB Output is correct
26 Correct 2 ms 856 KB Output is correct
27 Correct 1 ms 856 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 1 ms 600 KB Output is correct
30 Incorrect 39 ms 856 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -