Submission #423971

#	Time	Username	Problem	Language	Result	Execution time	Memory
423971		lyc	Chameleon's Love (JOI20_chameleon)	C++14	20 / 100	60 ms	332 KiB

chameleon

#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;
    }
}  // namespace


void Solve(int _N) {
    N = _N;
    F.assign(N,0);
    M.assign(N,0);
    iota(ALL(F),1);
    iota(ALL(M),N+1);
    memset(paired,0,sizeof paired);

    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);
    }
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 36