#P11710. 「KTSC 2020 R2」一二三【暂时无法评测】

    ID: 13000 远端评测题 3000ms 1024MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>2020交互题Special JudgeKOI(韩国)

「KTSC 2020 R2」一二三【暂时无法评测】

题目背景

交互+spj 的功能洛谷疑似爆了

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码:

#include <vector>

void maximize(std::vector<int> A);
void answer(int i, int j, int k);
  

题目译自 2020년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2「 하나 둘 셋

题目描述

有一个长度为 NN 的数组 AA,这个数组只包含数字 112233。我们需要在这个数组中找到尽可能多的满足以下条件的三元组 (i,j,k)(i, j, k)

对于数组中的三个索引 i,j,k(0i<j<k<N)i, j, k \quad(0 \leq i < j < k < N),要么 A[i]=1,A[j]=2,A[k]=3A[i]=1, A[j]=2, A[k]=3,要么 A[i]=3,A[j]=2,A[k]=1A[i]=3, A[j]=2, A[k]=1。并且,每个索引最多只能出现在一个三元组中。

例如,给定 A={1,2,3,2,3,1}A=\{1,2,3,2,3,1\},满足条件的三元组是 (0,1,4)(0,1,4)(2,3,5)(2,3,5)(A[0]=1,A[1]=2,A[4]=3)(A[0]=1, A[1]=2, A[4]=3)(A[2]=3,A[3]=2,A[5]=1)(A[2]=3, A[3]=2, A[5]=1)

编写一个程序,在给定数组 AA 的情况下,找到尽可能多的满足条件的三元组 (i,j,k)(i, j, k)

你需要实现以下函数:

void maximize(vector<int> A);

  • 参数 A 是一个长度为 Nvector,只包含数字 112233。函数 maximize 需要在数组 A 中找到尽可能多的满足条件的三元组 (i,j,k)(i, j, k),并且对于找到的每个三元组 (i,j,k)(i, j, k),调用 graderanswer(int i, int j, int k) 函数一次。如果有多种方法找到最大数量的三元组,可以任选一种。三元组的调用顺序无关紧要。例如,对于问题中的示例,可以先调用 answer(0,1,4),再调用 answer(2,3,5),也可以先调用 answer(2,3,5),再调用 answer(0,1,4)

输入格式

评测程序按以下格式读取输入:

  • 11 行:NN
  • 22 行:NN 个整数,每个整数为 112233

输出格式

评测程序将首先输出 maximize 函数调用 answer(i, j, k) 函数的次数,然后对于每次 answer(i, j, k) 调用,输出 i,j,ki, j, k 的值。

6
1 2 3 2 3 1
2
0 1 4
2 3 5

提示

样例说明 #1

以下是样例中函数调用及其结果的顺序:

函数调用 返回值
maximize({1, 2, 3, 2, 3, 1}) 2
answer(0,1,4) 0 1 4
answer(2,3,5) 2 3 5

数据范围

对于所有输入数据,满足:

  • 3N15,0003 \leq N \leq 15,000

详细子任务附加限制及分值如下表所示。

Subtask 分值 约束
11 1414 N18N \leq 18
22 2929 N100N \leq 100
33 5353 N3,000N \leq 3,000
44 5454 无附加限制

本题满分为 150150 分。