oj.uz

Submission #423984

# Submission time Handle Problem Language Result Execution time Memory
423984 2021-06-11T14:58:14 Z lyc Chameleon's Love (JOI20_chameleon) C++14
60 / 100
 63 ms 456 KB 
#include "chameleon.h"
#include <vector>

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef pair<int,int> ii;

namespace {
    int N;
    vector<int> F, M;
    bool paired[1001];

    int findedge(int x, vector<int> v, int l, int r) {
        int lo = l-1, hi = r+1;
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;

            vector<int> qv = {x};
            FOR(i,l,mid) qv.push_back(v[i]);
            int col = Query(qv);

            if (col != mid-(l-1)+1) hi = mid;
            else lo = mid;
        }
        return hi;
    }

    bool pointto(int x, vector<int> v, int y) {
        vector<int> qv = {x};
        for (int& a : v) if (a != y) qv.push_back(a);
        int col = Query(qv);
        //TRACE(x _ y _ col);
        //for (int& a : qv) { cout << a << ' '; } cout << endl << endl;
        return col == SZ(v)-2;
    }

    vector<int> al[1001];
    bool vis[1001];
    vector<int> st[2];

    void dfs(int i, int c) {
        st[c].push_back(i);
        vis[i] = 1;
        for (int& v: al[i]) if (!vis[v]) dfs(v,!c);
    }
}  // namespace

void mysolve(vector<int> F, vector<int> M) {
    int N = SZ(F);

    vector<ii> ans, ans2;
    for (int& x : F) {
        vector<int> pos;
        vector<ii> cur;

        int prv = -1;
        FOR(i,0,2){
            int p = findedge(x,M,prv+1,N-1);
            if (p >= N) break;
            prv = p;
            pos.push_back(M[p]);
        }

        if (SZ(pos) == 1) {
            ans.push_back(ii(x,pos[0]));
            paired[x] = paired[pos[0]] = 1;

        } else {
            for (int& y : pos) {
                if (!paired[y] && !pointto(x,M,y)) cur.push_back(ii(x,y));
            }

            if (SZ(cur) == 1) {
                ans.push_back(ii(x,cur[0].second));
                paired[x] = paired[cur[0].second] = 1;
            } else {
                for (auto& a : cur) ans2.push_back(a);
            }
        }
    }

        //cout << "ans" << endl; for (auto& x : ans) { cout << x.first _ x.second << endl; } cout << endl;
        //cout << "ans2" << endl; for (auto& x : ans2) { cout << x.first _ x.second << endl; } cout << endl;

        for (int& x : M) if (!paired[x]) {
            for (auto& p : ans2) if (x == p.second) {
                if (!pointto(x,F,p.first)) ans.push_back(p);
            }
        }

        //cout << "ans" << endl; for (auto& x : ans) { cout << x.first _ x.second << endl; } cout << endl;

        for (auto& x : ans) {
            Answer(x.first, x.second);
        }

}


void Solve(int _N) {
    N = _N;
    memset(paired,0,sizeof paired);

    if (N <= 50) {
        N *= 2;
        FOR(i,1,N){
            FOR(j,i+1,N){
                if (Query({i,j}) == 1) {
                    al[i].push_back(j);
                    al[j].push_back(i);
                }
            }
        }

        memset(vis,0,sizeof vis);
        FOR(i,1,N) if (!vis[i]) {
            st[0].clear();
            st[1].clear();
            dfs(i,0);
            mysolve(st[0],st[1]);
        }

    } else {
        F.assign(N,0);
        M.assign(N,0);
        iota(ALL(F),1);
        iota(ALL(M),N+1);
        mysolve(F,M);
    }
}

Subtask #1
0 / 4.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.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 61 ms 352 KB Output is correct
4 Correct 54 ms 328 KB Output is correct
5 Correct 57 ms 348 KB Output is correct
6 Correct 57 ms 328 KB Output is correct
7 Correct 63 ms 348 KB Output is correct
8 Correct 62 ms 456 KB Output is correct
9 Correct 54 ms 348 KB Output is correct

Subtask #5
0 / 36.0

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