我感到我的人生已经完整了。
yet another 北京游记

CF 240E, 一些意外状况.

Ruchiose posted @ Oct 31, 2014 04:02:13 PM in sigh with tags , 1893 阅读

这个题在Codeforces上是比较弱的……所以在CF上AC不一定是对的……

我现在在造这个题的数据……然后用了一些奇怪的方法gen数据……

然后发现某种姿势下我的朱刘/Edmonds会MLE……

然后为了获得正确的out在CF上拉了几段AC代码然后跑出了不同的out……

我造了一个比较小的数据是这样的:

1000 3983
1 2 1
2 3 1
3 4 1
4 5 1
......
997 998 1
998 999 1
999 1000 1
4 1 0
5 2 0
6 3 0
......
997 994 0
998 995 0
999 996 0
1000 997 0
7 1 0
8 2 0
9 3 0
10 4 0
......
998 992 0
999 993 0
1000 994 0
8 1 0
9 2 0
10 3 0
......
997 990 0
998 991 0
999 992 0
1000 993 0

它是用这段程序生成的:

// Author: Ruchiose
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define i64 long long
#define d64 long double
#define fortodo(i, f, t) for (i = f; i <= t; i++)
using namespace std;

int main()
{
	int N = 1000;
	printf("%d %d\n", N, N * 4 - 17);
	int i;
	fortodo(i, 1, N - 1) printf("%d %d 1\n", i, i + 1);
	fortodo(i, 1, N - 3) printf("%d %d 0\n", i + 3, i);
	fortodo(i, 1, N - 6) printf("%d %d 0\n", i + 6, i);
	fortodo(i, 1, N - 7) printf("%d %d 0\n", i + 7, i);
}

显然,为了从1到达i必须要先到达i-1,因此后3N-16条边都是没用的,答案应该是修复所有需要修复的边。

下面是拉来的一些AC代码的输出:

-1
3
997 998 999
-1
999
629 2514 2515 2516 2517 2518 2519 2520 25......
-1
999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17......
999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17......

(似乎-1会被代码高亮君吃掉囧)

看起来只有jiry_2和sone的程序可以跑出正常的结果。

可是这两个程序里面M开了200万,而这样的数据似乎会让空间开销到N^2级别……

然后N取5000的时候这两个程序已经输出-1了。

然后我已经找不到可以确定是正确的程序了……

(杜教:你可以去学习一下O(MlogN)的写法)

所以这个姿势的数据就只能放到N=1000……感到非常囧。

关于这两个程序在其它姿势gen的数据里是否和我的程序一样还没有测试……因为spj还没写……

多半最后是拿这三个程序的众数造out了囧。

 

UPD:

数据&SPJ已造。我的7915842造出的数据,sone的7184472和jiry的8162109都AC了(tsinsen: 978615&978616)。

大概是随机数据很弱的原因,Stilwell的5485603和vfk的2406412通过了除了#12以外的所有测试点(tsinsen: 978619&978623)。

其中#12就是上面构造的那个数据。那么感觉这题的数据应该是没有问题了。如有问题请联系我。

Avatar_small
mega888 official doa 说:
Aug 30, 2021 12:06:24 AM

In this case you will begin it is important, it again produces a web site a strong significant internet site:

Avatar_small
Satta king 说:
Sep 25, 2021 05:15:32 AM

In this particular article, you will see a summary, satisfy browse this post.

Avatar_small
Kerala 11th Question 说:
Aug 16, 2022 10:10:34 PM

The Keralan government offers top-notch instruction, top-notch facilities, and a clean learning atmosphere. As a result of the state board's extensive provision of educational facilities, there has been a yearly increase in education at all levels in the state. On the official website, the Kerala +1 Important Question Paper 2023 was posted. Kerala 11th Question Paper 2023 The Kerala +1 Important Question Paper 2023 will be released as soon as it is ready, and the Kerala 11th Model Question Paper of the exams was posted fairly quickly on the official website. By utilising their registration number and Subjects-wise, they may check their Kerala +1 Important Question Paper 2023.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter