A5253 | $模拟器$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

定义： 第五分块 这是一个数据结构问题。 给定整数 $n,m$ ，以及长度 $n$ 的序列 $x_1,\dots,x_n$ 和 $y_1,\dots,y_n$ ，共 $m$ 次操作。 需要维护序列 $s_1,\dots,s_n$ ，初值为0。 每次操作给出 $a,b,c,v$ 表示对 $ax_i+by_i+c<0$ 的每个 $i$ ，将 $s_i$ 修改为 $s_i+v$ ，然后查询被修改的 $s_i$ 的和。 要求 $1\le n\le 3\times 10^4,\;1\le m\le 1\times 10^5,\; 1\le x_i,y_i,a,b,c,v\le 10^9$ ，所有数值为整数。 输入格式为依次输入 $n,m,x_1,y_1,\dots,x_n,y_n$ ，然后依次输入每个操作的 $a,b,c,v$。 输出格式为对每个操作依次输出一个整数表示答案。 定义： 01矩阵乘法 $a,b,c$ 分别是 $n_1\times n_2,\;n_2\times n_3,\;n_1\times n_3$ 规模的由 $[0,1]$ 范围内的整数构成的矩阵，满足： $c_{i,k}=\sum\limits_{j=1}^{n_2}a_{i,j}b_{j,k}$ 。 $a,b$ 矩阵中的元素在范围内独立均匀随机选取。 输入格式为依次输入 $n_1,n_2,n_3$ ，然后依次输入 $a$ 和 $b$ 矩阵。 输出格式为输出 $c$ 矩阵。 输入（输出）一个 $A\times B$ 规模的矩阵 $v$ 时，需要对 $i=1,\dots,A$ 依次输入（输出）$v_{i,1},\dots,v_{i,B}$ 。 你需要解决的问题 你需要编写一个程序，这个程序的输入为空，输出是一个由 指令 构成的程序，这个程序用于求解 01矩阵乘法 （需要按输入格式读若干个整数，最后按输出格式写若干个整数），且可以调用一次对 第五分块 的求解（对应的指令是特殊函数调用3，需要先按输入格式写若干个整数表示问题描述，调用后按输出格式读若干个整数得到答案）和若干次读写整数（对应的指令是特殊函数调用1,2）。 下发的库 （std.cpp）可以简化生成指令的过程，你可以基于下发的库编写程序。 下发的 模拟器 （chk.cpp）可以执行由指令构成的程序，并给出得分。 模拟器的编译运行方式可以参考下发的 makefile 。

> 输入文件名： mode.in 输出文件名 mode.out T4相关文件下载 评分方式 如果你的程序不能正常结束，或输出的指令格式错误，或输出行数超过 $1024$，或输出的一行中超过 $1024$ 个字符，则不能得到任何分数。 输出的指令构成的程序格式正确时，模拟器将对输出的程序进行评测。 输出的程序将被执行 $4$ 次，依次对应 $n_1=n_2=n_3=50,100,150,200$ 。如果某次执行出现运行时错误（例如），则本题得 $0$ 分；否则每次执行如果输出了正确的答案并正常结束，则可以得到 $25\left(\min(1,\max(0,2-\frac{M}{M_0}))\cdot\min(1,\max(0,2-\frac{T}{T_0}))\right)$ 的分数。设每次执行的分数之和为 $S$ ，则总分为不超过 $S$ 的最大的 $20$ 的倍数（即下取整到 $0,20,40,60,80,100$ 之一）。 其中 $M$ 为内存访问次数，$T$ 为指令执行条数，在 指令和模拟器 一节定义。 $M_0=160000$ $T_0=3000000$ 指令和模拟器 以下简单介绍评测用的模拟器支持的指令，更详细的指令行为可以查看模拟器的源代码。 内存模型和计算代价统计： 可以读写的内存被表示为由 int64_t 整数组成的数组 M ，大小为 $2^{24}$ ，初值为 0； 指针 S 初始值为 M ，可能被 call 和 ret 指令修改； 指令的操作数表示为 M[S[<Int32>]] 或 S[<Int32>] ，用于读写内存； 指令不保存在 M 中，不能读写。 模拟器统计的计算代价包括 指令执行条数 和 内存访问次数。 一条指令（不包括 <Label>: ）被执行时， 指令执行条数增加 1 ，指令中出现的每个 M[S[<Int>]] 导致 内存访问次数增加 1 。 模拟器从第一条指令开始执行，执行 exit 后结束执行。 指令默认顺序执行，但对于指令说明中要求跳转的情况，执行完当前指令后调整到相应位置继续执行。 指令中需要用到以下语法元素： 语法元素说明<A>可以是 M[S[<Int>]] 或 S[<Int>] ，表示指令中需要读写的数据的来源<UOP>可以是 - !<BOP>可以是 `+ - * / % ^ &<< >> < <= > >= == !=`<Label>64位有符号整数常数，十进制，表示可以跳转到的标签<Int>64位有符号整数常数，十进制<Int32>32位有符号整数常数，十进制 支持的指令如下（需要严格满足描述的语法格式，不允许出现空格等）： 指令说明<A>=<A>赋值，读取右边的 <A> 写到左边的 <A><A>=<UOP><A>一元运算，语义和c++对 int64_t 的相应运算相同，运算结果写到左边的 <A><A>=<A><BOP><A>二元运算，语义和c++对 int64_t 的相应运算相同，运算结果写到左边的 <A><A>=<Int>赋值为常数<A>=&S[<Int>]取地址，相当于计算 S-M+<Int> 保存到 <A>if <A> goto <Label>条件跳转，如果 <A> 非零则跳转到 <Label>goto <Label>无条件跳转到 <Label>ret跳转到 S[0] 保存的指令地址，将 S 修改为 M+S[1]call <Label> <Int>保存下一条指令的地址到 S[<Int>] ，保存 S-M 到 S[<Int>+1] ，将 S 修改为 S+<Int> ，跳转到 <Label>exit结束执行ncall <Int> <A>特殊函数调用，<Int> 表示特殊函数的类型，可能读写 <A><Label>:标签，同个标签只能出现一次，不计入指令执行条数，用于表示跳转到的指令地址 特殊函数调用的规定： <Int><A>说明1读的整数的地址读一个整数2写的整数写一个整数3占位只能调用一次，功能在题目描述中指定 输入输出模型： 输入输出被保存在一个初始为空的由整数组成的队列中。 特殊函数 1 从队列开头中取出一个整数，作为读取的结果； 特殊函数 2 将待写的整数放到队列末尾； 特殊函数 3 按指定输入输出格式调用特殊函数 1,2 读写整数。 使用下发的库生成指令 为了方便地生成指令，你可以使用下发的基于宏定义的库作为你提交的源代码的一部分，编译运行后可以输出生成的指令到标准输出。 <Type> 可以为 Int 表示 int64_t，或者 Ptr<T> 表示类型 T 的指针，或者 Array<T,n> 表示类型 T 的大小 n 的数组。要求 T 是 <Type> 。 在表达式中， Int 之间可以使用二元运算符 + - * / % ^ & | << >> < <= > >= == != += -= *= /= %= ^= &= |= <<= >>= 和一元运算符 + - ! ，计算结果的表达式类型为 Int。 Ptr<T> 或 Array<T,n> 和 Int 之间可以使用二元运算符 + - ，计算结果的类型为 Ptr<T>。 Ptr<T> 或 Array<T,n> 可以使用一元运算符 * ，计算结果的类型为 T 。 表达式中可以出现数组访问运算符 <Expr>[<Expr>] ，要求左边为 Array<T,n> 或 Ptr<T> ，右边为 Int ，计算结果的类型为 T。 表达式中可以出现整数常量，可以被隐式转化为 Int 处理。 表达式中可以使用 () 改变运算符优先级。 表达式中可以出现类型转化 <Type>(<Expr>) ，仅限于 Array<T,n> 转为 Ptr<T> 或同个类型内的转化，以及 T 转为 Ptr<T> 表示c++中的 &。 表达式中可以出现赋值 <Expr>=<Expr> ，赋值时需要满足右侧类型能转化为左侧类型。 <Expr> 是表达式，只能包含整数或类型为某种 <Type> 的变量，变量的作用域规则和c++相同。 If(<Expr>) ... End 类似于c++中的if语句。 If(<Expr>) ... Else ... End 对应于c++中的if-else语句。 While(<Expr>) ... End 对应于c++中的while语句。 For(A,B,C) ... End 对应于c++中的for语句，其中 A,B,C为 <Expr> 。 Break; Continue; Return; 对应c++中相应的关键字。 <Expr>; 用于计算表达式，并处理表达式中可能出现的赋值。 <Type> x; 或 <Type> x=<Expr>; 用于在栈上定义变量。特别地，如果 <Expr> 的形式为 <Expr>[<Expr>] 或 <Expr> ，则 x 是右侧表达式的引用，而不是一个新的变量。 Func(name,args) ... End 用于定义无返回值的函数，args 为参数（可以为空，或包含形如 <Type> x; 的若干个定义），从第一个被定义的函数开始执行。函数定义不能嵌套，参数类型必须是 Int 或 Ptr<T>，语句必须出现在函数定义内。 Read(<Expr>); ，Write(<Expr>); ，Solve(); 分别表示特殊函数调用1,2,3。 未说明的用法可能能通过编译，但不一定能正确翻译为指令。 框架没有进行过多的优化，因此生成的指令可能有较高的指令执行条数。内存访问次数对应于形如 <Expr>[<Expr>] 或 *<Expr> 且类型不是数组的表达式的执行次数。

语法元素	说明
`<A>`	可以是 `M[S[<Int>]]` 或 `S[<Int>]` ，表示指令中需要读写的数据的来源
`<UOP>`	可以是 `- !`
`<BOP>`	可以是 `+ - * / % ^ &	<< >> < <= > >= == !=`
`<Label>`	64位有符号整数常数，十进制，表示可以跳转到的标签
`<Int>`	64位有符号整数常数，十进制
`<Int32>`	32位有符号整数常数，十进制

指令	说明
`<A>=<A>`	赋值，读取右边的 `<A>` 写到左边的 `<A>`
`<A>=<UOP><A>`	一元运算，语义和c++对 int64_t 的相应运算相同，运算结果写到左边的 `<A>`
`<A>=<A><BOP><A>`	二元运算，语义和c++对 int64_t 的相应运算相同，运算结果写到左边的 `<A>`
`<A>=<Int>`	赋值为常数
`<A>=&S[<Int>]`	取地址，相当于计算 `S-M+<Int>` 保存到 `<A>`
`if <A> goto <Label>`	条件跳转，如果 `<A>` 非零则跳转到 `<Label>`
`goto <Label>`	无条件跳转到 `<Label>`
`ret`	跳转到 `S[0]` 保存的指令地址，将 `S` 修改为 `M+S[1]`
`call <Label> <Int>`	保存下一条指令的地址到 `S[<Int>]` ，保存 `S-M` 到 `S[<Int>+1]` ，将 `S` 修改为 `S+<Int>` ，跳转到 `<Label>`
`exit`	结束执行
`ncall <Int> <A>`	特殊函数调用，`<Int>` 表示特殊函数的类型，可能读写 `<A>`
`<Label>:`	标签，同个标签只能出现一次，不计入指令执行条数，用于表示跳转到的指令地址

`<Int>`	`<A>`	说明
1	读的整数的地址	读一个整数
2	写的整数	写一个整数
3	占位	只能调用一次，功能在题目描述中指定

C++ 编辑器

输入

输出

A5253 | 模拟器

题目描述

定义： 第五分块

定义： 01矩阵乘法

你需要解决的问题

评分方式

指令和模拟器

使用下发的库生成指令

A5253 | $模拟器$

定义：第五分块