oj.uz

답안 #931808

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
931808 2024-02-22T11:10:06 Z boris_mihov 카멜레온의 사랑 (JOI20_chameleon) C++17
44 / 100
 35 ms 556 KB 
#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);
                }

                lastAdded = curr;
                cntFound++;
            }
        }

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

                lastAdded = curr;
                cntFound++;
            }
        }

        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

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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 22 ms 496 KB Output is correct
4 Correct 22 ms 344 KB Output is correct
5 Correct 22 ms 496 KB Output is correct
6 Correct 22 ms 340 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 23 ms 344 KB Output is correct
9 Correct 23 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Incorrect 1 ms 344 KB Wrong Answer [6]
11 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 35 ms 344 KB Output is correct
4 Correct 34 ms 344 KB Output is correct
5 Correct 34 ms 344 KB Output is correct
6 Correct 34 ms 552 KB Output is correct
7 Correct 34 ms 344 KB Output is correct
8 Correct 34 ms 344 KB Output is correct
9 Correct 34 ms 556 KB Output is correct

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 22 ms 496 KB Output is correct
4 Correct 22 ms 344 KB Output is correct
5 Correct 22 ms 496 KB Output is correct
6 Correct 22 ms 340 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 23 ms 344 KB Output is correct
9 Correct 23 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Incorrect 1 ms 344 KB Wrong Answer [6]
20 Halted 0 ms 0 KB -