oj.uz

Submission #430701

# Submission time Handle Problem Language Result Execution time Memory
430701 2021-06-17T01:17:56 Z fivefourthreeone Chameleon's Love (JOI20_chameleon) C++17
4 / 100
 55 ms 400 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include "chameleon.h"
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 1001;
int type[mxN], col[mxN], nxt[mxN];
/*void Answer(int a, int b) {
    if(col[a]^col[b]) {
        cout<<a<<" "<<b<<" you suck!\n";
        exit(0);
    }
}*/
int query(vector<int> &p) {
    return Query(p);
    /*set<int> colors;
    vector<bool> here(mxN, 0);
    for(int k: p) {
        here[k] = 1;
    }
    for(int k: p) {
        if(here[nxt[k]])colors.insert(col[nxt[k]]);
        else colors.insert(col[k]);
    }
    return colors.size();*/
}
vector<int> getrange(int a, int b, vector<int> &c, int d) {
    if(a > b)return {};
    vector<int> q;
    owo(i, a, b+1) {
        q.senpai(c[i]);
    }
    int l = a;
    int r = b;
    q.senpai(d);
    if(query(q) > b-a+1)return {};
    while(l < r) {
        q.clear();
        int m = (l + r) >> 1;
        owo(i, a, m+1) {
            q.senpai(c[i]);
        }
        q.senpai(d);
        if(query(q)==m-a+1)r = m;
        else l = m + 1;
    }
    vector<int> res = getrange(l+1, b, c, d);
    res.senpai(c[l]);
    return res;
}
vector<int> adj[mxN];
void bipartite(int n, vector<int> &l, vector<int> &r) {
    vector<int> col(n+1, -1);
    owo(i, 1, n+1) {
        if(col[i]!=-1)continue;
        queue<int> q;
        q.push(i);
        col[i] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int v: adj[u]) {
                if(col[v]==-1) {
                    col[v] = col[u]^1;
                    q.push(v);
                }
            }
        }
    }
    owo(i, 1, n+1) {
        if(col[i])r.senpai(i);
        else l.senpai(i);
    }
}
void Solve(int n) {
    vector<bool> done(2*n+1);
    vector<int> point(2*n+1);
    owo(i, 2, 2*n+1) {
        vector<int> l, r;
        bipartite(i-1, l, r);
        vector<int> edges = getrange(0, l.size()-1, l, i);
        for(int k: edges) {
            adj[k].senpai(i);
            adj[i].senpai(k);
        }
        edges = getrange(0, r.size()-1, r, i);
        for(int k: edges) {
            adj[k].senpai(i);
            adj[i].senpai(k);
        }
    }
    owo(i, 1, 2*n+1) {
        if(done[i])continue;
        if(adj[i].size()==1) {
            Answer(i, adj[i][0]);
            done[adj[i][0]] = 1;
        }else if(adj[i].size()==3) {
            vector<int> q = {i, adj[i][0], adj[i][1]};
            if(query(q)==1) {
                point[i] = adj[i][2];
            }else {
                q = {i, adj[i][0], adj[i][2]};
                if(query(q)==1) {
                    point[i] = adj[i][1];
                }else {
                    point[i] = adj[i][0];
                }
            }
        }
    }
    owo(i, 1, 2*n+1) {
        if(adj[i].size()==3) {
            int o = point[i];
            if(done[o])continue;
            int sam = i^adj[o][0]^adj[o][1]^adj[o][2]^point[o];
            Answer(o, sam);
            done[o] = 1;
            done[sam] = 1;
        }
    }
}
/*int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    int n;
    for(int tc = 1; tc <= T; tc++) {
        cin>>n;
        owo(i, 1, 2*n+1) {
            cin>>type[i];
        }
        owo(i, 1, 2*n+1) {
            cin>>col[i];
        }
        owo(i, 1, 2*n+1) {
            cin>>nxt[i];
        }
        Solve(n);
    }
    return 0;
}*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 51 ms 392 KB Output is correct
4 Correct 51 ms 392 KB Output is correct
5 Correct 50 ms 328 KB Output is correct
6 Correct 50 ms 392 KB Output is correct
7 Correct 49 ms 388 KB Output is correct
8 Correct 50 ms 328 KB Output is correct
9 Correct 55 ms 400 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 0 ms 344 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 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 51 ms 392 KB Output is correct
4 Correct 51 ms 392 KB Output is correct
5 Correct 50 ms 328 KB Output is correct
6 Correct 50 ms 392 KB Output is correct
7 Correct 49 ms 388 KB Output is correct
8 Correct 50 ms 328 KB Output is correct
9 Correct 55 ms 400 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Incorrect 0 ms 340 KB Wrong Answer [6]
13 Halted 0 ms 0 KB -