AdditionalFile5102.zip

P3487 [POI 2009] ARC-Architects

题目描述

给定一个序列 $a_i$（$1\leq a_i\leq 10^9$）且 $1\leq i\le n$ 且 $n\leq 1.5\times 10^7$，和一个整数 $k$（$k\leq n$ 且 $k\leq 10^6$），求出 $a$ 的一个长度为 $k$ 的子序列 $a_{b_i}$ 满足：

1. $1 \leq b_1 < b_2< \ldots< b_k \leq n$
2. 在满足 $1$ 的情况下 $a_{b_1}, a_{b_2},\ldots , a_{b_k}$ 字典序最大。

输入格式

第一行一个数 $k$，以下一行，为序列 $a_i$。以一个单独的 $0$ 结束。

输出格式

$k$ 行，每行一个数，其中第 $i$ 行为 $a_{b_i}$。

输入输出样例 #1

输入 #1

3
12 5 8 3 15 8 0

输出 #1

12
15
8

说明/提示

本题原为交互题，为评测方便，需要将下面的代码粘贴到文件中。

将第一次输入改为 =inicjuj() 形式，将之后的每一次输入改为 =wczytaj() 形式，将输出改为 wypisz(jakoscProjektu) 形式（jakoscProjektu 代表你输出的数）。

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAGIC_BEGIN -435634223
#define MAGIC_END -324556462

#define MIN_K 1
#define MAX_K 1000000
#define MAX_N 15000000
#define MIN_A 1
#define MAX_A 1000000000
#define MIN_TYP 1
#define MAX_TYP 3
#define MIN_PAR 0
#define MAX_PAR 1000000000

#define ERROR 0
#define CORRECT 1

#define unlikely(x) __builtin_expect(!!(x), 0)

static int init = 0; // czy zostala juz wywolana funkcja inicjuj()
static int lib_n; // ile biblioteka podala juz liczb
static int con_k; // ile zawodnik podal liczb

static int N, K, A, TYP, PAR; // parametry testu wczytywane z pliku
static int bre, len_sub, bou, is_end; // zmienne pomocnicze

static int rand2_status = 198402041;

static inline int rand2(int a, int b){
  rand2_status = rand2_status * 1103515245ll + 12345;
  int x = rand2_status;
  if (x < 0) x = -x; // -2^31 sie nie zdarza :D
  x >>= 1;
  x = a + x % (b - a + 1);
  return x;
}

/* test losowy */
static inline int random_test()
{
    return rand2(1, A);
}

/* test z dlugim podciagiem nierosnacym */
static inline int decreasing_test()
{
    int tmp;
    if(bre == 0) {
        bre = rand2(0, (N - lib_n + 1 - len_sub));
        tmp = A;
        A -= rand2(0, (A - 1) / len_sub);
        len_sub--;
    }
    else {
        bre--;
        tmp = rand2(1, A);
    }
    return tmp;
}

/* test z dlugim podciagiem niemalejacym */
static inline int increasing_test()
{
    return bou - decreasing_test();
}

static void finish(int res, const char com[])
{
    if(res == ERROR)
        printf("%s\n", com);
    exit(0);
}

/* Inicjuje dane wejsciowe i zwraca liczbe projektow */
int inicjuj()
{
    if(init == 1)
        finish(ERROR, "Program zawodnika moze wywolac funkcje inicjuj tylko raz!!!");
    init = 1;
    scanf("%d", &K);
    if (K > 0){
      TYP = 0;
      N = MAX_N + 2;
      return K;
    }
    int magic_begin, magic_end;
    scanf("%d%d", &magic_begin, &TYP);
    if(magic_begin != MAGIC_BEGIN || TYP < MIN_TYP || TYP > MAX_TYP)
        finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
    scanf("%d%d%d%d", &N, &K, &A, &PAR);
    if(N < 1 || N > MAX_N || N < K || K > MAX_K || A < MIN_A || A > MAX_A 
        || PAR < MIN_PAR || PAR > MAX_PAR)
        finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
    scanf("%d", &magic_end);
    if(magic_end != MAGIC_END)
        finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
    con_k = 0;
    lib_n = 0;
    is_end = 0;
    if(TYP == 2 || TYP == 3) {
        len_sub = PAR;
        bre = 0;
    }
    if(TYP == 2)
        bou = A--;
    return K;
}

/* Sluzy do wczytania ciagu reprezentujacego jakosci projektow */
int wczytaj()
{
    if(unlikely(init == 0))
        finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!");
    if(unlikely(lib_n > N || is_end == 1))
        finish(ERROR, "Program zawodnika wywolal funkcje wczytaj po otrzymaniu informacji o koncu ciagu!!!");
    if(unlikely(lib_n == N))
        return 0;
    lib_n++;
    switch (TYP) {
      case 0:
        scanf("%d", &A);
        if(A == 0)
          is_end = 1;
        return A;
        break;
      case 1: return random_test(); break;
      case 2: return increasing_test(); break;
      case 3: return decreasing_test(); break;
      default:
              finish(ERROR, "Nieznany typ testu");
    }
    return -1;
}

/* Sluzy do wypisania wyznaczonego podciagu */
void wypisz(int jakoscProjektu)
{
    if(init == 0)
        finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!");
    printf("%d\n", jakoscProjektu);
    if(++con_k == K)
        finish(CORRECT, "");
}

#5102. 「POI2009 R2」建筑师 Architect

标签: 传统 | 时间限制: 10000 ms | 内存限制: 64 MiB |

题目描述

题目译自 XVI OI Olimpiada Informatyczna – II etap Architekci

国王 Bajtazar 计划兴建一座新宫殿，宣布举办建筑设计大赛，征集最佳方案。为激励建筑师加紧工作，他规定将按提交顺序评审设计。

这项任务声名显赫，吸引了全球建筑师向王室办公厅提交方案。提案数量庞大，Bajtazar 无暇逐一审阅，遂委托大法官初步筛选，遵循以下规则：

• 大法官需挑选 $k$ 个方案，立即淘汰其余——Bajtazar 知晓自己最多只能审阅 $k$ 个方案。
• 方案须按提交顺序呈交，Bajtazar 将依此顺序评审，符合其承诺。
• 在满足上述条件的所有 $k$ 个方案序列中，大法官需选出最佳序列，定义如下：

序列 $(p_1, p_2, \ldots, p_k)$ 优于 $(r_1, r_2, \ldots, r_k)$，若存在 $l \geq 1$，使得前 $l-1$ 个方案两序列等同（即 $p_i = r_i$，对 $i < l$），但第 $l$ 个方案 $p_l > r_l$。

方案源源不断提交，截止日期未定。大法官不愿临近截止才选方案，又恐出错惹国王震怒，遂向你求助。

编写程序，完成以下任务：

• 通过提供的库读取 $k$ 和表示方案质量的序列。
• 确定符合规则的最佳 $k$ 个方案序列。
• 通过库返回所选方案的质量。

交互方式

使用库需在程序中引入：

• C/C++：#include "carclib.h"
• Pascal：uses parclib;
• Java：无需额外操作，但运行时需确保编译好的库 jarclib.class 与程序在同一目录。

库提供以下三个函数：

• inicjuj：返回整数 $k$ $(1 \leq k \leq 1000000)$，表示结果序列应包含的方案数。需在程序开始时调用一次。
  • C/C++：int inicjuj();
  • Pascal：function inicjuj(): longint;
  • Java：public static int inicjuj();（jarclib 类静态方法）
• wczytaj：第 $i$ 次调用返回整数 $p_i$ $(1 \leq p_i \leq 1000000000)$，表示第 $i$ 个方案的质量（越大越好），或 $0$，表示无更多方案。方案总数未知，但保证至少 $k$ 个，最多 $15000000$ 个。需反复调用直至返回 $0$，不可多调用。
  • C/C++：int wczytaj();
  • Pascal：function wczytaj(): longint;
  • Java：public static int wczytaj();（jarclib 类静态方法）
• wypisz：用于提交大法官选出的方案质量，需调用 $k$ 次，第 $i$ 次提交第 $i$ 个方案的质量。第 $k$ 次调用后程序终止。
  • C/C++：void wypisz(int jakoscProjektu);
  • Pascal：procedure wypisz(jakoscProjektu: longint);
  • Java：public static void wypisz(int jakoscProjektu);（jarclib 类静态方法）

程序不得打开文件或使用标准输入输出。编译命令：

• C：gcc -O2 -static carclib.c arc.c -lm
• C++：g++ -O2 -static carclib.c arc.cpp -lm
• Java：javac arc.java，需确保 jarclib.class 在同一目录。
• Pascal：ppc386 -O2 -XS -Xt arc.pas，需确保 parclib 在同一目录。

示例库和参考代码位于 「文件」中。示例库从标准输入读取测试场景，格式如下：

• 第一行：正整数 $k$。
• 后续行：每行一个正整数 $p_i$，表示第 $i$ 个方案质量。
• 最后一行：$0$，表示方案结束。

示例库将程序提交的 $k$ 个方案质量输出到标准输出，每行一个。

样例

数据范围与提示

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