oj.uz

Submission #259766

# Submission time Handle Problem Language Result Execution time Memory
259766 2020-08-08T13:24:35 Z Kastanda Chameleon's Love (JOI20_chameleon) C++14
40 / 100
 17 ms 512 KB 
// M
#include<bits/stdc++.h>
#include "chameleon.h"
#define pb push_back
using namespace std;

const int N = 505;
int M[N], MC[N];
vector < int > V[N];

void Recur(vector < int > vec)
{
        for (int i = 0; i < (int)vec.size(); i ++)
                if (V[vec[i]].size() == 3)
                        swap(vec[i], vec.back()), vec.pop_back(), i --;
        if (!vec.size())
                return ;

        /*printf("Now : ");
        for (int i : vec)
                printf("%d ", i);
        printf("\n");
        fflush(stdout);*/

        vector < int > tmp, bad;
        tmp.pb(vec[0]);
        for (int i = 1; i < (int)vec.size(); i ++)
        {
                tmp.pb(vec[i]);
                if (Query(tmp) == (int)tmp.size())
                        continue;
                else
                        bad.pb(vec[i]), tmp.pop_back();
        }
        assert((int)tmp.size() >= (int)vec.size() / 4);
        for (int i : bad)
        {
                int le = 0, ri = (int)tmp.size(), md;
                while (true)
                {
                        vector < int > ff(tmp.begin() + le, tmp.begin() + ri);
                        ff.pb(i);
                        if (le > 0 && Query(ff) == (int)ff.size())
                                break;
                        while (ri - le > 1)
                        {
                                md = (le + ri) >> 1;
                                ff = vector < int > (tmp.begin() + le, tmp.begin() + md);
                                ff.pb(i);
                                if (Query(ff) == (int)ff.size())
                                        le = md;
                                else
                                        ri = md;
                        }
                        V[i].push_back(tmp[le]);
                        V[tmp[le]].push_back(i);

                        le ++;
                        ri = (int)tmp.size();
                }
        }
        Recur(bad);
}

void Solve(int n)
{
        vector < int > vec;
        for (int i = 1; i <= n + n; i ++)
                vec.push_back(i);
        Recur(vec);

        for (int i = 1; i <= n + n; i ++)
                if (V[i].size() == 1) // Part of a cycle of length 2
                {
                        MC[i] = V[i][0];
                        MC[V[i][0]] = i;
                }

        for (int i = 1; i <= n + n; i ++)
                if (MC[i] == 0)
                {
                        assert((int)V[i].size() == 3);
                        vector < int > All;
                        memset(M, 0, sizeof(M));
                        M[i] = 1;
                        for (int a : V[i])
                                M[a] = 1;
                        for (int v = 1; v <= n + n; v ++)
                                if (!M[v])
                                        All.pb(v);

                        for (int a : V[i])
                        {
                                vector < int > tmp(All.begin(), All.end());
                                for (int b : V[i])
                                        if (a != b)
                                                tmp.pb(b);
                                if (Query(tmp) < n)
                                {
                                        MC[i] = a;
                                        MC[a] = i;
                                        break;
                                }
                        }
                        assert(MC[i]);
                }
        for (int i = 1; i <= n + n; i ++)
                if (i < MC[i])
                        Answer(i, MC[i]);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Runtime error 11 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Runtime error 17 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Runtime error 11 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -