Submission #931809

#	Time	Username	Problem	Language	Result	Execution time	Memory
931809		boris_mihov	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	44 ms	596 KiB

chameleon

#include "chameleon.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

const int MAXN = 1000 + 10;

namespace
{
    int n;
    int perm[MAXN];
    int before[MAXN];
    bool found[2 * MAXN];
    std::vector <int> candidates[MAXN];
    std::vector <int> x, y;
}

int runBinary(int fromPos, std::vector <int> &from, int value)
{
    int l = fromPos - 1, r = from.size(), mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        std::vector <int> curr;
        curr.push_back(value);

        for (int j = fromPos ; j <= mid ; ++j)
        {
            curr.push_back(from[j]);
        }

        if (Query(curr) == curr.size()) l = mid;
        else r = mid;
    }

    return r;
}

int timer;
int vis[MAXN];
void rebuild(int node, int side)
{
    if (side == 0)
    {
        x.push_back(node);
    } else
    {
        y.push_back(node);
    }

    vis[node] = timer;
    for (const int &u : candidates[node])
    {
        if (vis[u] != timer)
        {
            rebuild(u, side ^ 1);
        }
    }
}

void Solve(int n) 
{
    ::n = n;
    for (int i = 1 ; i <= 2 * n ; ++i)
    {
        timer++;
        bool shouldTryX = true;
        bool shouldTryY = true;
        x.push_back(i);
        y.push_back(i);

        if (Query(x) == x.size())
        {
            shouldTryX = false;
        }

        if (Query(y) == y.size())
        {
            shouldTryY = false;
        }

        x.pop_back();
        y.pop_back();
        int cntFound = 0;

        if (shouldTryX)
        {
            int lastAdded = -1;
            while (cntFound < 3 && lastAdded + 1 < x.size())
            {
                int curr = runBinary(lastAdded + 1, x, i);
                if (curr != x.size())
                {
                    candidates[i].push_back(x[curr]);
                    candidates[x[curr]].push_back(i);
                    cntFound++;
                }

                lastAdded = curr;
            }
        }

        if (shouldTryY)
        {
            int lastAdded = -1;
            while (cntFound < 3 && lastAdded + 1 < y.size())
            {
                int curr = runBinary(lastAdded + 1, y, i);
                if (curr != y.size())
                {
                    candidates[i].push_back(y[curr]);
                    candidates[y[curr]].push_back(i);
                    cntFound++;
                }

                lastAdded = curr;
            }
        }

        x.clear();
        y.clear();
        for (int u = 1 ; u <= i ; ++u)
        {
            if (vis[u] != timer)
            {
                rebuild(u, 0);
            }
        }
    }

    for (int i = 1 ; i <= 2 * n ; ++i)
    {
        if (candidates[i].size() == 3)
        {
            if (Query({candidates[i][0], candidates[i][2], i}) == 1)
            {
                std::swap(candidates[i].back(), candidates[i][1]);
            } else if (Query({candidates[i][1], candidates[i][2], i}) == 1)
            {
                std::swap(candidates[i].back(), candidates[i][0]);
            }

            candidates[i].pop_back();
        }
    }

    std::iota(perm + 1, perm + 1 + 2 * n, 1);
    std::sort(perm + 1, perm + 1 + 2 * n, [&](int x, int y)
    {
        return candidates[x].size() < candidates[y].size();
    });
    
    for (int idx = 1 ; idx <= 2 * n ; ++idx)
    {
        int i = perm[idx];
        if (found[i])
        {
            continue;
        }

        if (candidates[i].size() == 1)
        {
            Answer(i, candidates[i][0]);
            found[candidates[i][0]] = true;
            continue;
        }
        
        assert(candidates[i].size() == 2);
        bool shouldBreak = false;

        for (const int &j : candidates[i])
        {
            for (const int &x : candidates[j])
            {
                if (x == i)
                {
                    Answer(i, j);
                    found[j] = true;
                    shouldBreak = true;
                    break;
                }
            }
            
            if (shouldBreak)
            {
                break;
            }
        }
    }
}

Compilation message (stderr)

chameleon.cpp: In function 'int runBinary(int, std::vector<int>&, int)':
chameleon.cpp:35:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if (Query(curr) == curr.size()) l = mid;
      |             ~~~~~~~~~~~~^~~~~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         if (Query(x) == x.size())
      |             ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         if (Query(y) == y.size())
      |             ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp:92:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             while (cntFound < 3 && lastAdded + 1 < x.size())
      |                                    ~~~~~~~~~~~~~~^~~~~~~~~~
chameleon.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |                 if (curr != x.size())
      |                     ~~~~~^~~~~~~~~~~
chameleon.cpp:109:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |             while (cntFound < 3 && lastAdded + 1 < y.size())
      |                                    ~~~~~~~~~~~~~~^~~~~~~~~~
chameleon.cpp:112:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                 if (curr != y.size())
      |                     ~~~~~^~~~~~~~~~~
chameleon.cpp: At global scope:
chameleon.cpp:15:9: warning: '{anonymous}::before' defined but not used [-Wunused-variable]
   15 |     int before[MAXN];
      |         ^~~~~~

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