Contest Duration: - (local time) (90 minutes) Back to Home

Submission #2616436

Source Code Expand

Copy
```import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.NoSuchElementException;

public class Main {
private static void solve() {
int n = nei();
int m = nei();
int k = nei();
int[][] abs = nis2(m, 2);
boolean[][] ng = new boolean[n][n];
for (int i = 0; i < m; i++) {
int p = abs[i][0];
int q = abs[i][1];
ng[p][q] = true;
ng[q][p] = true;
}
int[] hito = new int[n];
long st = System.currentTimeMillis();
long totalCount = 0;
long okCount = 0;
while (totalCount % 100 != 0 || System.currentTimeMillis() - st < 8000) {
for (int i = 0; i < n; i++) {
hito[i] = i;
}
for (int i = 0; i < k; i++) {
int x = (int) (Math.random() * n);
int y = (int) (Math.random() * (n - 1)) + 1;
if (x == y)
y = 0;
int tmp = hito[x];
hito[x] = hito[y];
hito[y] = tmp;
}
boolean isOk = true;
for (int i = 0; i < n; i++) {
if (ng[hito[i]][hito[(i + 1) % n]]) {
isOk = false;
break;
}
}
totalCount++;
if (isOk)
okCount++;
}
out((double) okCount / totalCount);
}

// returns (x, y, d) s.t. ax + by = d
static long[] exgcd(long a, long b) {
int sa = a < 0 ? -1 : 1;
int sb = b < 0 ? -1 : 1;
a *= sa;
b *= sb;
long x = 1;
long y = 0;
long z = 0;
long w = 1;
while (b > 0) {
long q = a / b;
long t = z;
z = x - q * z;
x = t;
t = w;
w = y - q * w;
y = t;
t = b;
b = a - q * b;
a = t;
}
return new long[] { x * sa, y * sb, a };
}

static int[] lis(int[] s) {
int n = s.length;
int[] dp = new int[n];
int[] ids = new int[n];
int[] pids = new int[n];
dp[0] = s[0];
int len = 1;
int lidx = 0;
for (int i = 1; i < n; i++) {
int idx = bs(s[i], dp, 0, len);
dp[idx] = s[i];
ids[idx] = i;
if (idx == len) {
lidx = i;
len++;
}
if (idx > 0)
pids[i] = ids[idx - 1];
}
int[] lis = new int[len];
lis[len - 1] = s[lidx];
for (int i = len - 1; i >= 0; i--) {
lis[i] = s[lidx];
lidx = pids[lidx];
}
return lis;
}

static int bs(int a, int[] as, int from, int num) {
int min = from;
int max = from + num - 1;
while (min < max) {
int mid = min + max >> 1;
if (as[mid] < a)
min = mid + 1;
else if (as[mid] > a)
max = mid;
else
return mid;
}
return as[min] < a ? min + 1 : min;
}

static int gcd(int x, int y) {
x = (x ^ x >> 31) - (x >> 31);
y = (y ^ y >> 31) - (y >> 31);
if (x < y) {
x ^= y;
y ^= x;
x ^= y;
}
int z = x % y;
if (z == 0)
return y;
return gcd(y, z);
}

static long gcd(long x, long y) {
x = (x ^ x >> 63) - (x >> 63);
y = (y ^ y >> 63) - (y >> 63);
if (x < y) {
x ^= y;
y ^= x;
x ^= y;
}
long z = x % y;
if (z == 0)
return y;
return gcd(y, z);
}

static long modinv(long a, long mod) {
return BigInteger.valueOf(a).modInverse(BigInteger.valueOf(mod)).longValueExact();
}

static int lcm(int x, int y) {
x = (x ^ x >> 31) - (x >> 31);
y = (y ^ y >> 31) - (y >> 31);
return x / gcd(x, y) * y;
}

static long lcm(long x, long y) {
x = (x ^ x >> 63) - (x >> 63);
y = (y ^ y >> 63) - (y >> 63);
return x / gcd(x, y) * y;
}

static int abs(int x) {
return x < 0 ? -x : x;
}

static long abs(long x) {
return x < 0 ? -x : x;
}

static int min(int a, int b) {
return a < b ? a : b;
}

static long min(long a, long b) {
return a < b ? a : b;
}

static int max(int a, int b) {
return a > b ? a : b;
}

static long max(long a, long b) {
return a > b ? a : b;
}

static int clamp(int a, int min, int max) {
return a < min ? min : a > max ? max : a;
}

static long clamp(long a, long min, long max) {
return a < min ? min : a > max ? max : a;
}

static void out(String val) {
IO.out(val);
}

static void out(Object val) {
IO.out(String.valueOf(val));
}

static void out(int val) {
IO.out(String.valueOf(val));
}

static void out(long val) {
IO.out(String.valueOf(val));
}

static void out(char val) {
IO.out(String.valueOf(val));
}

static void out(float val) {
IO.out(String.valueOf(val));
}

static void out(double val) {
IO.out(String.valueOf(val));
}

static void out(boolean val) {
IO.out(String.valueOf(val));
}

static void kil(String val) {
IO.out(val);
IO.flush();
System.exit(0);
}

static void kil(Object val) {
IO.out(String.valueOf(val));
IO.flush();
System.exit(0);
}

static void kil(int val) {
IO.out(String.valueOf(val));
IO.flush();
System.exit(0);
}

static void kil(long val) {
IO.out(String.valueOf(val));
IO.flush();
System.exit(0);
}

static void kil(char val) {
IO.out(String.valueOf(val));
IO.flush();
System.exit(0);
}

static void kil(float val) {
IO.out(String.valueOf(val));
IO.flush();
System.exit(0);
}

static void kil(double val) {
IO.out(String.valueOf(val));
IO.flush();
System.exit(0);
}

static void kil(boolean val) {
IO.out(String.valueOf(val));
IO.flush();
System.exit(0);
}

static String nes() {
return IO.next();
}

static int nei() {
return IO.nextInt();
}

static long nel() {
return IO.nextLong();
}

static double ned() {
return IO.nextDouble();
}

static char nec() {
return IO.nextChar();
}

static String[] nss(int n) {
String[] as = new String[n];
for (int i = 0; i < n; i++) {
as[i] = IO.next();
}
return as;
}

static int[] nis(int n) {
int[] as = new int[n];
for (int i = 0; i < n; i++) {
as[i] = IO.nextInt();
}
return as;
}

static long[] nls(int n) {
long[] as = new long[n];
for (int i = 0; i < n; i++) {
as[i] = IO.nextLong();
}
return as;
}

static double[] nds(int n) {
double[] as = new double[n];
for (int i = 0; i < n; i++) {
as[i] = IO.nextDouble();
}
return as;
}

static char[] ncs(int n) {
char[] as = new char[n];
for (int i = 0; i < n; i++) {
as[i] = IO.nextChar();
}
return as;
}

static String[][] nss2(int n, int m) {
String[][] as = new String[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
as[i][j] = IO.next();
}
}
return as;
}

static int[][] nis2(int n, int m) {
int[][] as = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
as[i][j] = IO.nextInt();
}
}
return as;
}

static long[][] nls2(int n, int m) {
long[][] as = new long[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
as[i][j] = IO.nextLong();
}
}
return as;
}

static double[][] nds2(int n, int m) {
double[][] as = new double[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
as[i][j] = IO.nextDouble();
}
}
return as;
}

static char[][] ncs2(int n, int m) {
char[][] as = new char[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
as[i][j] = IO.nextChar();
}
}
return as;
}

static int parseInt(String val) {
return Integer.parseInt(val);
}

static int parseInt(char val) {
return Integer.parseInt(String.valueOf(val));
}

static long parseLong(String val) {
return Long.parseLong(val);
}

public static void main(String[] args) {
try {
solve();
IO.flush();
} catch (Exception e) {
e.printStackTrace();
}
}
}

final class IO {
private static final InputStream in = System.in;
private static final PrintWriter out = new PrintWriter(System.out, false);
private static final byte[] buffer = new byte[1024];
private static int ptr = 0;
private static int len = 0;

private static boolean hasNextByte() {
if (ptr < len)
return true;
ptr = 0;
try {
} catch (IOException e) {
e.printStackTrace();
}
return len > 0;
}

if (hasNextByte())
return buffer[ptr++];
else
return -1;
}

static boolean hasNext() {
byte c;
while (hasNextByte() && ((c = buffer[ptr]) < '!' || c > '~'))
ptr++;
return hasNextByte();
}

static String next() {
if (!hasNext())
throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
while (b >= '!' && b <= '~') {
sb.append((char) b);
}
return sb.toString();
}

static char nextChar() {
if (!hasNext())
throw new NoSuchElementException();
}

static long nextLong() {
if (!hasNext())
throw new NoSuchElementException();
long n = 0;
int sign = 1;
if (b == '-') {
sign = -1;
}
if (b < '0' || '9' < b)
throw new NumberFormatException();
while (true) {
if ('0' <= b && b <= '9')
n = n * 10 + b - '0';
else if (b == -1 || b < '!' || b > '~')
return n * sign;
else
throw new NumberFormatException();
}
}

static int nextInt() {
if (!hasNext())
throw new NoSuchElementException();
int n = 0;
int sign = 1;
if (b == '-') {
sign = -1;
}
if (b < '0' || '9' < b)
throw new NumberFormatException();
while (true) {
if ('0' <= b && b <= '9')
n = n * 10 + b - '0';
else if (b == -1 || b < '!' || b > '~')
return n * sign;
else
throw new NumberFormatException();
}
}

static double nextDouble() {
return Double.parseDouble(next());
}

static void out(String val) {
out.println(val);
}

static void flush() {
out.flush();
}
}
```

Submission Info

Submission Time 2018-06-04 16:00:58+0900 D - シャッフル席替え saharan Java8 (OpenJDK 1.8.0) 100 9948 Byte AC 8074 ms 25920 KB

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
 AC × 71
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_rnd_11_01.txt, 01_rnd_11_02.txt, 01_rnd_11_03.txt, 01_rnd_11_04.txt, 01_rnd_11_05.txt, 01_rnd_11_06.txt, 01_rnd_11_07.txt, 01_rnd_11_08.txt, 01_rnd_11_09.txt, 01_rnd_11_10.txt, 01_rnd_11_11.txt, 01_rnd_11_12.txt, 01_rnd_11_13.txt, 01_rnd_11_14.txt, 01_rnd_11_15.txt, 01_rnd_11_16.txt, 01_rnd_11_17.txt, 01_rnd_11_18.txt, 01_rnd_11_19.txt, 01_rnd_11_20.txt, 01_rnd_11_21.txt, 01_rnd_11_22.txt, 01_rnd_7_01.txt, 01_rnd_7_02.txt, 01_rnd_7_03.txt, 01_rnd_7_04.txt, 01_rnd_7_05.txt, 01_rnd_7_06.txt, 01_rnd_7_07.txt, 01_rnd_7_08.txt, 01_rnd_7_09.txt, 01_rnd_7_10.txt, 01_rnd_7_11.txt, 01_rnd_7_12.txt, 01_rnd_7_13.txt, 01_rnd_7_14.txt, 01_rnd_7_15.txt, 01_rnd_7_16.txt, 01_rnd_7_17.txt, 01_rnd_7_18.txt, 01_rnd_7_19.txt, 01_rnd_7_20.txt, 01_rnd_7_21.txt, 01_rnd_7_22.txt, 01_rnd_8_01.txt, 01_rnd_8_02.txt, 01_rnd_8_03.txt, 01_rnd_8_04.txt, 01_rnd_8_05.txt, 01_rnd_8_06.txt, 01_rnd_8_07.txt, 01_rnd_8_08.txt, 01_rnd_8_09.txt, 01_rnd_8_10.txt, 01_rnd_8_11.txt, 01_rnd_8_12.txt, 01_rnd_8_13.txt, 01_rnd_8_14.txt, 01_rnd_8_15.txt, 01_rnd_8_16.txt, 01_rnd_8_17.txt, 01_rnd_8_18.txt, 01_rnd_8_19.txt, 01_rnd_8_20.txt, 01_rnd_8_21.txt, 01_rnd_8_22.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 8068 ms 18388 KB
00_mini_02.txt AC 8070 ms 20172 KB
00_sample_01.txt AC 8068 ms 19312 KB
00_sample_02.txt AC 8071 ms 19924 KB
00_sample_03.txt AC 8071 ms 19900 KB
01_rnd_11_01.txt AC 8071 ms 20712 KB
01_rnd_11_02.txt AC 8071 ms 20728 KB
01_rnd_11_03.txt AC 8070 ms 19188 KB
01_rnd_11_04.txt AC 8070 ms 22592 KB
01_rnd_11_05.txt AC 8070 ms 19636 KB
01_rnd_11_06.txt AC 8070 ms 22328 KB
01_rnd_11_07.txt AC 8070 ms 22576 KB
01_rnd_11_08.txt AC 8072 ms 21308 KB
01_rnd_11_09.txt AC 8070 ms 22836 KB
01_rnd_11_10.txt AC 8070 ms 22452 KB
01_rnd_11_11.txt AC 8072 ms 22204 KB
01_rnd_11_12.txt AC 8071 ms 20844 KB
01_rnd_11_13.txt AC 8071 ms 22424 KB
01_rnd_11_14.txt AC 8070 ms 20076 KB
01_rnd_11_15.txt AC 8070 ms 19648 KB
01_rnd_11_16.txt AC 8070 ms 21076 KB
01_rnd_11_17.txt AC 8072 ms 21824 KB
01_rnd_11_18.txt AC 8071 ms 22080 KB
01_rnd_11_19.txt AC 8073 ms 19864 KB
01_rnd_11_20.txt AC 8072 ms 17204 KB
01_rnd_11_21.txt AC 8071 ms 20876 KB
01_rnd_11_22.txt AC 8072 ms 21124 KB
01_rnd_7_01.txt AC 8071 ms 20136 KB
01_rnd_7_02.txt AC 8070 ms 22800 KB
01_rnd_7_03.txt AC 8072 ms 22204 KB
01_rnd_7_04.txt AC 8071 ms 22996 KB
01_rnd_7_05.txt AC 8071 ms 20396 KB
01_rnd_7_06.txt AC 8072 ms 20016 KB
01_rnd_7_07.txt AC 8070 ms 20532 KB
01_rnd_7_08.txt AC 8071 ms 22356 KB
01_rnd_7_09.txt AC 8072 ms 20052 KB
01_rnd_7_10.txt AC 8069 ms 22784 KB
01_rnd_7_11.txt AC 8070 ms 19924 KB
01_rnd_7_12.txt AC 8068 ms 19900 KB
01_rnd_7_13.txt AC 8072 ms 25920 KB
01_rnd_7_14.txt AC 8071 ms 19892 KB
01_rnd_7_15.txt AC 8073 ms 22776 KB
01_rnd_7_16.txt AC 8073 ms 20148 KB
01_rnd_7_17.txt AC 8071 ms 20856 KB
01_rnd_7_18.txt AC 8071 ms 19328 KB
01_rnd_7_19.txt AC 8070 ms 19796 KB
01_rnd_7_20.txt AC 8069 ms 20204 KB
01_rnd_7_21.txt AC 8071 ms 22228 KB
01_rnd_7_22.txt AC 8071 ms 22228 KB
01_rnd_8_01.txt AC 8070 ms 22572 KB
01_rnd_8_02.txt AC 8074 ms 18116 KB
01_rnd_8_03.txt AC 8073 ms 20288 KB
01_rnd_8_04.txt AC 8071 ms 22672 KB
01_rnd_8_05.txt AC 8070 ms 21180 KB
01_rnd_8_06.txt AC 8072 ms 23124 KB
01_rnd_8_07.txt AC 8072 ms 21812 KB
01_rnd_8_08.txt AC 8071 ms 20368 KB
01_rnd_8_09.txt AC 8071 ms 19632 KB
01_rnd_8_10.txt AC 8071 ms 22228 KB
01_rnd_8_11.txt AC 8071 ms 17364 KB
01_rnd_8_12.txt AC 8072 ms 22068 KB
01_rnd_8_13.txt AC 8070 ms 22792 KB
01_rnd_8_14.txt AC 8072 ms 19768 KB
01_rnd_8_15.txt AC 8071 ms 20740 KB
01_rnd_8_16.txt AC 8071 ms 20224 KB
01_rnd_8_17.txt AC 8071 ms 19844 KB
01_rnd_8_18.txt AC 8073 ms 20624 KB
01_rnd_8_19.txt AC 8074 ms 22272 KB
01_rnd_8_20.txt AC 8071 ms 20396 KB
01_rnd_8_21.txt AC 8071 ms 18644 KB
01_rnd_8_22.txt AC 8071 ms 23124 KB