Submission #423955

#	Time	Username	Problem	Language	Result	Execution time	Memory
423955		lyc	Chameleon's Love (JOI20_chameleon)	C++14	0 / 100	24 ms	712 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[501];

    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);
        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) {
        int pos1 = findedge(x,M,0,N-1);
        int pos2 = findedge(x,M,pos1+1,N-1);
        int pos3 = findedge(x,M,pos2+1,N-1);

        if (pos2 >= N) { // >= N sz 2 cyc
            ans.push_back(ii(x,M[pos1]));
            paired[x] = paired[M[pos1]] = 1;
        } else {
            vector<ii> cur;
            TRACE(x _ pos1 _ pos2 _ pos3 _ M[pos1] _ M[pos2] _ M[pos3]);
            if (!paired[M[pos1]] && !pointto(x,M,M[pos1])) cur.push_back(ii(x,M[pos1]));
            if (!paired[M[pos2]] && !pointto(x,M,M[pos2])) cur.push_back(ii(x,M[pos2]));
            if (!paired[M[pos3]] && !pointto(x,M,M[pos3])) cur.push_back(ii(x,M[pos3]));
            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);
            }
        }
    }

    //for (auto& x : ans) { cout << x.first _ x.second << endl; } cout << 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);
        }
    }

    //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: 0 / 20
• Subtask 5: 0 / 36