Submission #423933

#	Time	Username	Problem	Language	Result	Execution time	Memory
423933		lyc	Chameleon's Love (JOI20_chameleon)	C++14	0 / 100	68 ms	384 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<int> f2;
    set<ii> ans;
    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);

        //TRACE(x _ pos1 _ pos2 _ pos3 _ M[pos1] _ M[pos2] _ M[pos3]);
        if (pos2 >= N) { // >= N sz 2 cyc
            ans.insert(ii(x,M[pos1]));
            //TRACE(x _ M[pos1]);
            paired[x] = paired[M[pos1]] = 1;
        } else {
            if (!pointto(x,M,M[pos1])) ans.insert(ii(x,M[pos1]));
            if (!pointto(x,M,M[pos2])) ans.insert(ii(x,M[pos2]));
            if (!pointto(x,M,M[pos3])) ans.insert(ii(x,M[pos3]));
            f2.push_back(x);
        }
    }

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

    for (int& x : M) {
        int pos1 = findedge(x,F,0,N-1);
        int pos2 = findedge(x,F,pos1+1,N-1);
        int pos3 = findedge(x,F,pos2+1,N-1);

        if (pos2 >= N) { // >= N sz 2 cyc
            ans.insert(ii(F[pos1],x));
            //TRACE(x _ F[pos1]);
            paired[x] = paired[F[pos1]] = 1;
        } else {
            int a1 = pointto(x,F,F[pos1]);
            int a2 = pointto(x,F,F[pos2]);
            int a3 = pointto(x,F,F[pos3]);
            //TRACE(x _ a1 _ a2 _ a3 _ F[pos1] _ F[pos2] _ F[pos3]);

            if (pointto(x,F,F[pos1])) ans.erase(ii(F[pos1],x));
            if (pointto(x,F,F[pos2])) ans.erase(ii(F[pos2],x));
            if (pointto(x,F,F[pos3])) ans.erase(ii(F[pos3],x));
        }
    }

    //for (auto& x : ans) { TRACE(x.first _ x.second); }

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

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:84:17: warning: unused variable 'a1' [-Wunused-variable]
   84 |             int a1 = pointto(x,F,F[pos1]);
      |                 ^~
chameleon.cpp:85:17: warning: unused variable 'a2' [-Wunused-variable]
   85 |             int a2 = pointto(x,F,F[pos2]);
      |                 ^~
chameleon.cpp:86:17: warning: unused variable 'a3' [-Wunused-variable]
   86 |             int a3 = pointto(x,F,F[pos3]);
      |                 ^~

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