你们可以去Dev试一下
2026-08-15 18:35:48
发布于：四川
#include<bits/stdc++.h>
#define pr(...) //printf("#[%d] ",(int)LINE);printf(VA_ARGS)
struct StackAllocator{
struct Seg{
size_t l,r;
bool operator<(const Seg &x)const{return l<x.l;}
};
stdmultiset<Seg> mem;
size_t top=0;
size_t alloc(size_t size){
pr("alloc %d,%d\n",(int)top,(int)size);
size_t ret=top;
top+=size;
return ret;
}
void free(size_t x,size_t size){
mem.insert(Seg{x,x+size});
while(mem.size()){
auto it=--mem.end();
if(it->rtop){
top=it->l;
mem.erase(it);
}else break;
}
pr("free %d,%d top=%d\n",(int)x,(int)size,(int)top);
}
}stack_allocator;
struct Addr{
enum AddrType{
NONE=0,STACK=1,MEM=2
};
AddrType type=NONE;
size_t offset=0;
void stack_alloc(size_t size){
type=STACK;
offset=stack_allocator.alloc(size);
}
void free(size_t size){
switch(type){
case NONE:{
break;
}
case STACK:
case MEM:{
stack_allocator.free(offset,size);
break;
}
}
}
bool is_stack_top(){
return typeSTACK && offsetstack_allocator.top-1;
}
void reset(){
*this=Addr();
}
friend bool operator(const Addr &a,const Addr &b){
return a.type!=NONE&&a.typeb.type&&a.offsetb.offset;
}
friend stdostream &operator<<(stdostream &os,const Addr &x){
switch(x.type){
case NONE:{
assert(0);
break;
}
case STACK:{
os<<"S["<<x.offset<<"]";
break;
}
case MEM:{
os<<"M[S["<<x.offset<<"]]";
break;
}
}
return os;
}
};
struct Instr{
enum Type{
LI, // op1 = x
UOP, // op1 = op(op2)
BOP, // op1 = op(op2,op3)
NCALL, // ncall x op2
JZ, // if op2 goto label
JMP, // goto label
RET, // ret
CALL, // call label x
EXIT, // exit
LABEL, // label:
}type;
const char *op;
Addr op1,op2,op3;
int64_t x,label;
static Instr li(Addr c,int64_t a){
return Instr{LI,NULL,c,Addr(),Addr(),a,0};
}
static Instr uop(Addr c,const char *name,Addr a){
return Instr{UOP,name,c,a,Addr(),0,0};
}
static Instr bop(Addr c,const char *name,Addr a,Addr b){
return Instr{BOP,name,c,a,b,0,0};
}
static Instr ncall(int64_t type,Addr a){
return Instr{NCALL,NULL,Addr(),a,Addr(),type,0};
}
static Instr jz(Addr a,int64_t label){
return Instr{JZ,NULL,Addr(),a,Addr(),0,label};
}
static Instr jmp(int64_t label){
return Instr{JMP,NULL,Addr(),Addr(),Addr(),0,label};
}
static Instr ret(){
return Instr{RET,NULL,Addr(),Addr(),Addr(),0,0};
}
static Instr call(int64_t sp,int64_t label){
return Instr{CALL,NULL,Addr(),Addr(),Addr(),sp,label};
}
static Instr exit(){
return Instr{EXIT,NULL,Addr(),Addr(),Addr(),0,0};
}
static Instr put_label(int64_t label){
return Instr{LABEL,NULL,Addr(),Addr(),Addr(),0,label};
}
friend stdostream &operator<<(stdostream &os,const Instr &w){
w.print(os);
return os;
}
void print(stdostream &os)const{
switch(type){
case LI:{
os<<op1<<'='<<x<<'\n';
break;
}
case UOP:{
os<<op1<<'='<<op<<op2<<'\n';
break;
}
case BOP:{
os<<op1<<'='<<op2<<op<<op3<<'\n';
break;
}
case NCALL:{
os<<"ncall "<<x<<' '<<op2<<'\n';
break;
}
case JZ:{
os<<"if "<<op2<<" goto "<<label<<'\n';
break;
}
case JMP:{
os<<"goto "<<label<<'\n';
break;
}
case RET:{
os<<"ret\n";
break;
}
case CALL:{
os<<"call "<<label<<' '<<x<<'\n';
break;
}
case EXIT:{
os<<"exit\n";
break;
}
case LABEL:{
os<<label<<":\n";
break;
}
}
}
};
stdlist<Instr> instrs;
struct Var{
Addr addr;
friend stdostream &operator<<(stdostream &os,const Var &x){
return os<<x.addr;
}
};
void li_instr(Addr c,int64_t a){
instrs.emplace_back(Instrli(c,a));
}
void uop_instr(Addr c,const char *name,Addr a){
if(!strcmp(name,"+"))name="";
instrs.emplace_back(Instruop(c,name,a));
}
void bop_instr(Addr c,const char *name,Addr a,Addr b){
instrs.emplace_back(Instrbop(c,name,a,b));
}
void native_call_instr(int64_t type,Addr a){
instrs.emplace_back(Instrncall(type,a));
}
#define default_alloc(A)
A(){
pr("%s: ",#A);
addr.stack_alloc(Asize);
}
~A(){
pr("%s: ",#A);
addr.free(Asize);
}
A(Addr a,int):A(){
assert(addr.type==AddrSTACK);
uop_instr(addr,"+",a);
addr.type=Addr::MEM;
}
A(A &&a){
assert(a.addr.is_stack_top());
addr=a.addr;
a.addr.reset();
}
#define default_value_copy(A)
A(const A &a):A(){*this=a;}
A(const Addr &a):A(){
uop_instr(addr,"+",a);
}
A(Addr &&a):A(){
addr=a;
a.type=Addr::NONE;
}
const A &operator=(const A &a)const{
uop_instr(addr,"+",a.addr);
return *this;
}
const A &operator=(A &&a)const{
if(!instrs.empty()){
auto &w=instrs.back();
if(w.op1==a.addr){
w.op1=addr;
return *this;
}
}
uop_instr(addr,"+",a.addr);
return *this;
}
static constexpr size_t size=1;
#define op_eq(T,T2,op,op_eq)
const T &operator op_eq(const T2 &a)const{
*this=*this op a;
return *this;
}
struct Int:Var{
default_alloc(Int)
default_value_copy(Int)
Int(int64_t a):Int(){*this=a;}
const Int &operator=(int64_t a){
li_instr(addr,a);
return *this;
}
#define uop(op) \
friend Int operator op(const Int &a){\
Int c;\
uop_instr(c.addr,#op,a.addr);\
return c;\
}
uop(+)
uop(-)
uop(!)
#undef uop
#define bop(op) \
friend Int operator op(const Int &a,const Int &b){\
Int c;\
bop_instr(c.addr,#op,a.addr,b.addr);\
return c;\
}
bop(+)
bop(-)
bop(*)
bop(/)
bop(%)
bop(^)
bop(&)
bop(|)
bop(<<)
bop(>>)
bop(<)
bop(<=)
bop(>)
bop(>=)
bop(==)
bop(!=)
#undef bop
#define bopeq(op,opeq) \
friend const Int &operator opeq(const Int &a,const Int &b){\
bop_instr(a.addr,#op,a.addr,b.addr);\
return a;\
}
bopeq(+,+=)
bopeq(-,-=)
bopeq(*,*=)
bopeq(/,/=)
bopeq(%,%=)
bopeq(^,^=)
bopeq(&,&=)
bopeq(|,|=)
bopeq(<<,<<=)
bopeq(>>,>>=)
#undef bopeq
};
template<class T>
struct Ptr:Var{
default_alloc(Ptr)
default_value_copy(Ptr)
Ptr(const T &a):Ptr(){
*this=a;
}
Ptr &operator=(const T &a){
set_addr(a.addr);
return this;
}
T operator()const{
return T(addr,0);
}
void set_addr(Addr a){
switch(a.type){
case AddrNONE:{
assert(0);
break;
}
case AddrSTACK:{
uop_instr(addr,"&",a);
break;
}
case AddrMEM:{
a.type=AddrSTACK;
uop_instr(addr,"+",a);
break;
}
}
}
T operator[](const Int &a)const{
return *(*this+a);
}
friend Ptr operator+(const Ptr &a,const Int &b){
if(T::size==1){
Ptr c;
bop_instr(c.addr,"+",a.addr,b.addr);
return c;
}
return Ptr((Int(a.addr)+b*T::size).addr);
}
friend Ptr operator+(const Int &b,const Ptr &a){
return a+b;
}
friend const Ptr &operator+=(const Ptr &a,const Int &b){
if(T::size==1){
bop_instr(a.addr,"+",a.addr,b.addr);
return a;
}
a=a+b;
return a;
}
friend Ptr operator-(const Ptr &a,const Int &b){
if(T::size==1){
Ptr c;
bop_instr(c.addr,"-",a.addr,b.addr);
return c;
}
return Ptr((Int(a.addr)-b*T::size).addr);
}
friend Int operator-(const Ptr &a,const Ptr &b){
if(T::size==1){
Int c;
bop_instr(c.addr,"-",a.addr,b.addr);
return c;
}
return (Int(a.addr)-Int(b.addr))/T::size;
}
#define bop(op) \
friend Int operator op(const Ptr &a,const Ptr &b){\
Int c;\
bop_instr(c.addr,#op,a.addr,b.addr);\
return c;\
}
bop(<)
bop(<=)
bop(>)
bop(>=)
bop(==)
bop(!=)
#undef bop
op_eq(Ptr,Int,-,-=)
};
template<class T,size_t n>
struct Array:Var{
default_alloc(Array)
Array(const Array &a)=delete;
static constexpr size_t size=n*T::size;
operator Ptr<T>()const{
Ptr<T> c;
c.set_addr(addr);
return c;
}
T operator[](const Int &a)const{
return *(*this+a);
}
friend Ptr<T> operator+(const Array &a,const Int &b){
if(T::size==1){
Ptr<T> c;
c.set_addr(a.addr);
bop_instr(c.addr,"+",c.addr,b.addr);
return c;
}
return Ptr<T>((Int(((Ptr<T>)a).addr)+b*T::size).addr);
}
friend Ptr<T> operator+(const Int &b,const Array &a){
return a+b;
}
friend Ptr<T> operator-(const Array &a,const Int &b){
return Ptr<T>((Int(((Ptr<T>)a).addr)-b*T::size).addr);
}
};
#undef op_eq
#define If(x) ctrl_if(x); {{
#define Elif(x) }}ctrl_elif(x);{{
#define Else }}ctrl_else();{{
#define End }}ctrl_end();
#define While(x) {
int _continue=ctx.label++;
put_label(_continue);
ctrl_while(_continue,x); {
#define For(A,B,C) {
int _continue=ctx.label++;
int _begin=ctx.label++;
A;
jmp(_begin);
put_label(_continue);
C;
put_label(_begin);
ctrl_while(_continue,B); {
#define Break ctrl_break();
#define Continue ctrl_continue();
#define Func(name,...) {Int __ra;Int __old_sp;ctrl_func(#name);VA_ARGS;{
#define Call(name,...) ctrl_call(#name,VA_ARGS)
#define Return ctrl_return()
#define Exit ctrl_exit()
struct Ctrl{
enum State{
IF,WHILE
}state;
int label1,label2;
};
struct Context{
const char *func=NULL;
stdvector<Ctrl> ctrl,loop;
int label=1;
stdmapstd::string,int func_label;
int get_label(const char *fn){
int &w=func_label[fn];
if(!w)w=label++;
return w;
}
~Context(){
assert(!func);
}
}ctx;
void jz(const Int &a,int64_t label){
instrs.emplace_back(Instrjz(a.addr,label));
}
void jmp(int64_t label){
instrs.emplace_back(Instrjmp(label));
}
void ret_instr(){
instrs.emplace_back(Instrret());
}
void call_instr(int64_t sp,int64_t label){
instrs.emplace_back(Instrcall(sp,label));
}
void exit_instr(){
instrs.emplace_back(Instrexit());
}
void put_label(int64_t label){
instrs.emplace_back(Instrput_label(label));
}
void ctrl_if(const Int &a){
pr("if\n");
int _else=ctx.label++;
int _endif=ctx.label++;
jz(a,_else);
ctx.ctrl.push_back(Ctrl{CtrlIF,_else,_endif});
}
void ctrl_elif(const Int &a){
pr("else if\n");
assert(ctx.ctrl.size());
auto &w=ctx.ctrl.back();
switch(w.state){
case CtrlIF:
jmp(w.label2);
put_label(w.label1);
w.label1=ctx.label++;
jz(a,w.label1);
break;
default:
assert(0);
}
}
void ctrl_else(){
pr("else\n");
assert(ctx.ctrl.size());
auto &w=ctx.ctrl.back();
switch(w.state){
case Ctrl::IF:
jmp(w.label2);
put_label(w.label1);
w.label1=0;
break;
default:
assert(0);
}
}
void ctrl_end(){
if(ctx.ctrl.empty()){
pr("end func\n");
assert(ctx.func);
ret_instr();
ctx.func=NULL;
for(const Instr &x:instrs){
std::cout<<x;
}
instrs.clear();
return;
}
auto &w=ctx.ctrl.back();
switch(w.state){
case Ctrl::IF:
pr("end if\n");
if(w.label1)put_label(w.label1);
put_label(w.label2);
ctx.ctrl.pop_back();
break;
case Ctrl::WHILE:
pr("end while\n");
jmp(w.label1);
put_label(w.label2);
ctx.ctrl.pop_back();
ctx.loop.pop_back();
break;
default:
assert(0);
}
}
void ctrl_while(int _continue,const Int &a){
pr("while\n");
int _break=ctx.label++;
jz(a,_break);
ctx.ctrl.push_back(Ctrl{CtrlWHILE,_continue,_break});
ctx.loop.push_back(Ctrl{CtrlWHILE,_continue,_break});
}
void ctrl_break(){
pr("break\n");
assert(ctx.loop.size());
jmp(ctx.loop.back().label2);
}
void ctrl_continue(){
pr("continue\n");
assert(ctx.loop.size());
jmp(ctx.loop.back().label1);
}
void ctrl_func(const char *name){
pr("func %s\n",name);
assert(!ctx.func);
ctx.func=name;
put_label(ctx.get_label(name));
}
int arg_pos=0;
void ctrl_call_args(const char *name){
}
template<class T>
void ctrl_call_args(const char *name,const T &x){
pr("arg %d\n",++arg_pos);
T arg=x;
ctrl_call_args(name);
}
template<class T,class ... Ts>
void ctrl_call_args(const char *name,const T &x,const Ts & ... xs){
pr("arg %d\n",++arg_pos);
T arg=x;
ctrl_call_args(name,xs...);
}
template<class ... Ts>
void ctrl_call(const char *name,const Ts & ... xs){
pr("call %s\n",name);
size_t sp=stack_allocator.top;
Int ra;
Int old_sp;
arg_pos=0;
ctrl_call_args(name,xs...);
call_instr(sp,ctx.get_label(name));
}
void ctrl_return(){
pr("return\n");
assert(ctx.func);
ret_instr();
}
void ctrl_exit(){
pr("exit\n");
assert(ctx.func);
exit_instr();
}
void Read(const Ptr<Int> &x){
pr("read\n");
native_call_instr(1,x.addr);
}
void Write(const Int &x){
pr("write\n");
native_call_instr(2,x.addr);
}
void Solve(){
pr("solve\n");
Int x;
native_call_instr(3,x.addr);
}
#define Fe(i,l,r) For(Int i=l,i<=r,i+=_1)
void W(){}
template<class ... T>
void W(const Int &x,const T & ... xs){
Write(x);
W(xs...);
}
const int MAX_MAT = 207;
int main(){
Func(main,)
// 1. 基础变量定义
Array<Array<Int, MAX_MAT>, MAX_MAT> A, B;
Int n1, n2, n3;
Int _1 = 1, _0 = 0, _neg1 = -1;
Int INF = 1000000000; // 足够大的重置值，不溢出
// 2. 读入矩阵维度与数据
Read(n1); Read(n2); Read(n3);
Fe(i, _1, n1)
Fe(j, _1, n2)
Read(A[i][j]);
End
End
Fe(j, _1, n2)
Fe(k, _1, n3)
Read(B[j][k]);
End
End
// =========================================================
// 核心：第五分块输入构造（100%符合协议）
// =========================================================
// 点设计：n = n2，每个j对应点(0, j)，y坐标为j，天然有序
Int tb5_n = n2;
// 操作数计算：每个i需要 2*n2(初始化s) + n3*2*n2(计算C) 次操作
Int op_per_i = n2 * 2 + n3 * n2 * 2;
Int tb5_m = n1 * op_per_i;
// 1. 写入第五分块的n和m
Write(tb5_n);
Write(tb5_m);
// 2. 写入n个点的坐标 (x_j=0, y_j=j)
Fe(j, _1, n2)
Write(_0); // x_j = 0
Write(j); // y_j = j
End
// 3. 写入m次操作（核心逻辑）
Fe(i, _1, n1)
// --------------------------
// 阶段1：初始化s[j] = A[i][j]
// 用差分法：2次操作给单个s[j]加A[i][j]
// --------------------------
// 先重置所有s[j]为0：全选操作，v=-INF，把s[j]拉到极小值
Write(_0); Write(_0); Write(_neg1); Write(-INF); // 0x+0y-1 <0 恒成立
// 再全选操作，v=INF，把s[j]重置为0
Write(_0); Write(_0); Write(_neg1); Write(INF);
// 逐个给s[j]赋值A[i][j]
Fe(j, _1, n2)
Int val = A[i][j];
// 操作1：y <= j → 给所有<=j的s加val
Write(_0); Write(_1); Write(-(j+_1)); Write(val); // 0x+1y - (j+1) <0 → y < j+1 → y<=j
// 操作2：y <= j-1 → 给所有<=j-1的s减val
Write(_0); Write(_1); Write(-j); Write(-val); // 0x+1y -j <0 → y <j → y<=j-1
End
// --------------------------
// 阶段2：计算C[i][k] = sum_j A[i][j] * B[j][k]
// 用前缀和差分，每次操作获取s[j]，累加符合B[j][k]=1的项
// --------------------------
Fe(k, _1, n3)
Fe(j, _1, n2)
// 仅当B[j][k]=1时，我们需要获取s[j]的值
If(B[j][k] == _1)
// 操作1：获取sum_{1~j} s → 前缀和
Write(_0); Write(_1); Write(-(j+_1)); Write(_0);
// 操作2：获取sum_{1~j-1} s → 前缀和
Write(_0); Write(_1); Write(-j); Write(_0);
Else
// 否则写入空操作，占位对齐
Write(_0); Write(_0); Write(_1); Write(_0); // 恒不成立
Write(_0); Write(_0); Write(_1); Write(_0); // 恒不成立
End
End
End
End
// =========================================================
// 唯一一次Solve()调用（严格符合强制要求）
// =========================================================
Solve();
// =========================================================
// 读取第五分块的输出，提取C[i][k]并输出
// =========================================================
Fe(i, _1, n1)
// 跳过初始化阶段的返回值（2*n2个）
Fe(t, _1, n2*2)
Int trash; Read(trash);
End
// 处理每个k的结果
Fe(k, _1, n3)
Int c_val = _0;
Fe(j, _1, n2)
Int sum_j, sum_j_1;
Read(sum_j); // sum_{1~j} s
Read(sum_j_1); // sum_{1~j-1} s
// 差分得到s[j]，累加到c_val
Int s_j = sum_j - sum_j_1;
c_val += s_j;
End
// 输出最终的C[i][k]（行主序）
Write(c_val);
End
End
Exit;
End
return 0;
}
这里空空如也
有帮助，赞一个