제출 #1291947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291947		serkanrashid	카멜레온의 사랑 (JOI20_chameleon)	C++17	0 / 100	78 ms	488 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>


using namespace std;

//int Query(const std::vector<int> &p)
//void Answer(int a, int b)

const int MAXN = 1024;

int n;
vector<int>g[MAXN];
bool vis[MAXN];


/*
4
0 0 0 0 1 1 1 1
1 2 3 4 1 2 3 4
6 7 8 5 4 3 2 1
*/



int in[MAXN],ou[MAXN];
vector<int>p;

vector<int> subred(int l, int r)
{
    vector<int>res;
    for(int i = l; i <= r; i++) res.push_back(i);
    return res;
}

int bin_s(int i, pair<int,int> bef)
{
    int l = 1;
    int r = 2*n;
    int mid;

    while(l <= r)
    {
        //cout << "too much?" << " " << l << " " << r << endl;
        mid = (l+r)/2;
        p.clear();
        for(int j = 1; j <= mid; j++) if(j != i && j != bef.first && j != bef.second) p.push_back(j);
        int raz = Query(p);
        p.push_back(i);
        raz = raz + 1 - Query(p);

        if(raz >= 1) r = mid-1;
        else l = mid+1;
    }
    return l;
}

void SOLVE4(int i)
{
    //cout << "yeya" << endl;
    p.clear();
    for(int j = 1; j <= 2*n; j++) if(j != i) p.push_back(j);
    int raz = Query(p);
    p.push_back(i);
    raz = raz + 1 - Query(p);


    int gr = 3;
    if(raz == 1) gr = 1;

    pair<int,int>bef = {0,-1};
    for(int j = 0; j < gr; j++)
    {
        //cout << bef.first << " " << bef.second << "eho" << endl;
        int pos = bin_s(i,bef);
        //if(pos == bef.first || pos == bef.second) pos++;
        //if(pos == bef.first || pos == bef.second) pos++;

        g[i].push_back(pos);

        bef.second = bef.first;
        bef.first = pos;
    }
}

void Solve(int N)
{
    n = N;


    for(int i = 1; i <= 2*n; i++) SOLVE4(i);
    /*for(int i = 1; i <= 2*n; i++)
    {
        cout << i << " -> ";
        for(int nb : g[i]) cout << nb << " ";
        cout << endl;
    }*/

    for(int i = 1; i <= 2*n; i++)
    {
        if(g[i].size() == 1)
        {
            if(!vis[i] && !vis[g[i][0]]) Answer(i,g[i][0]);
            vis[i] = 1;
            vis[g[i][0]] = 1;
            continue;
        }

        int ab = Query({i,g[i][0],g[i][1]});
        int ac = Query({i,g[i][0],g[i][2]});
        int bc = Query({i,g[i][1],g[i][2]});

        if(ab == ac) in[g[i][0]] = i;
        if(ab == bc) in[g[i][1]] = i;
        if(bc == ac) in[g[i][2]] = i;
    }
    for(int i = 1; i <= 2*n; i++) ou[in[i]] = i;

    for(int i = 1; i <= 2*n; i++)
    {
        if(vis[i]) continue;

        for(int j = 0; j < 3; j++)
        {
            if(j > g[i].size()-1) break;

            if(g[i][j] != in[i] && g[i][j] != ou[i])
            {
                if(!vis[i] && !vis[g[i][j]]) Answer(i,g[i][j]);
                vis[i] = 1;
                vis[g[i][j]] = 1;
                break;
            }
        }
    }
}

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