所以cpp代码试图使用一些随机数和BSGS算法来解决codeforces上的问题。
我在调试这个问题时遇到了问题,因为它通过 STDIN 和 STDOUT 与另一个程序对话。我尝试使用命名管道:
准备工作:首先将下面的python判断器代码保存到gen.py
. 然后将下面的cpp代码编译成g2.exe
. 然后在工作目录中创建 2 个名为 fifo 的makefifo g2in; makefifo g2out;
.
打开 2 个终端并在每个终端中执行 cmd:./g2 < g2in > g2out
并且./gen.py < g2out > g2in
两个终端都永远挂起并且根本没有任何进展。
但如果我在其中一个命令中执行 tee,情况就会有所不同:./g2 < g2in | tee g2out
和./gen.py < g2out > g2in
。程序按预期进行和退出,判断者可以判断程序的行为是否正确。
我试图把strace记录下来:
左边是有T恤的,右边是没有T恤的。我想知道这里发生了什么以及是什么造成了不同?
这是python判断器代码:
#!/usr/bin/env python
import sys
import random
import subprocess
def main():
n = random.randint(1, 1e6)
sys.stderr.write(f"begin with {n=}\n")
v = [x + 1 for x in range(n)]
random.shuffle(v)
idx = 0
opt = 0
print(f"{v[idx]}")
sys.stdout.flush()
while True:
#sys.stdin.flush()
#line = process.stdout.readline().strip()
line = input()
#sys.stderr.write(f"read {line}\n")
if not line:
break
if line[0] == '!':
exp = int(line[1:])
if exp == n:
sys.stderr.write(f"get right ans {exp=}\n")
return 0
else:
raise Exception(f"real {n=}, {exp=}\n")
else:
op = line[0]
cnt = int(line[1:])
sys.stderr.write(f"get a query request at {cnt=}\n")
if op == '+':
idx = (idx + cnt) % n
else:
assert op == '-', f"{op} not '-'"
idx = (idx - cnt) % n
print(f"{v[idx]}")
sys.stdout.flush()
sys.stderr.write(f"write and flush ans {v[idx]=} done\n")
opt += 1
if opt % 100 == 0:
sys.stderr.write(f"opt get ${opt}\n")
if opt >= 1000:
break
raise Exception("Too many try")
if __name__ == "__main__":
main()
这是被接受的正确 cpp 代码:
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifdef __DEBUG__
#include "dbg.h"
#else
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int get_rdn() { return rng() % int(1e6 + 3); }
int main(int argc, char **argv)
{
int x, m = 0;
scanf("%d", &m);
dbg(m);
for (int i = 0; i < 300; ++i) {
int roll = get_rdn();
printf("+ %d\n", roll), fflush(stdout);
scanf("%d", &x);
m = max(m, x);
}
dbg(m);
map<int, int> cnt;
int offset = 0;
for (int i = 0; i < 340; ++i) {
printf("+ 1\n"), fflush(stdout);
scanf("%d", &x);
if (cnt.count(x)) {
printf("! %d\n", offset), fflush(stdout);
return 0;
}
cnt[x] = offset++;
}
dbg(offset);
printf("+ %d\n", m - 340), fflush(stdout);
scanf("%d", &x);
offset = 0;
for (int i = 0; i < 340; ++i) {
printf("+ 340\n"), fflush(stdout);
scanf("%d", &x);
if (cnt.count(x)) {
dbg(offset + m + 339 - cnt[x]);
printf("! %d\n", offset + m + 339 - cnt[x]), fflush(stdout);
return 0;
}
offset += 340;
}
return 0;
};
我正在使用 WSL2 顺便说一句:Linux Ubuntu-WSL2 4.19.128-microsoft-standard #1 SMP Tue Jun 23 12:58:10 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
顺序很重要。当您尝试打开 FIFO 进行读取时,它会阻塞,直到有其他东西打开另一端进行写入(反之亦然)。Shell 重定向按从左到右的顺序执行。因此,在您的第一个命令中
./g2 < g2in > g2out
,shell 尝试打开g2in
以进行读取,并阻止等待它也打开以进行写入。该g2
计划还没有开始;这是在所有重定向设置完成后发生的。使用第二个命令 时./gen.py < g2out > g2in
,shell 首先尝试打开g2out
以进行读取,这会再次阻塞等待某些内容打开管道的另一端。这些命令陷入僵局,每个命令都等待对方做一些它不会做的事情,直到对方先做其他事情。如果您在方向上保持相同的文件顺序,则通过运行
./g2 < g2in > g2out
和,首先打开 FIFO./gen.py > g2in < g2out
的两端,然后打开 , 的两端,并且两个程序都被执行并且可以相互通信。g2in
g2out
./g2 < g2in | tee g2out
之所以有效,是因为 shell 只有一个重定向, ofg2in
,并且当它阻塞等待该 FIFO 的写入端打开时,管道的其余部分也在并行执行;tee
打开g2out
写入,允许./gen.py < g2out > g2in
运行其余部分(Afterg2out
两端都打开,g2in
打开写入(允许g2 < g2in
命令继续),然后./gen.py
执行)。