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

Submission #19089

Source Code Expand

Copy
```module main;

import std.stdio;
import std.string;
import std.array;
import std.algorithm;
import std.conv;
import std.random;
import std.range;

void main()
{
solve_D();
}

void solve_D()
{
auto n = to!int(buf[0]);
auto taboo_count = to!int(buf[1]);
auto swaps = to!int(buf[2]);
debug
{
writefln("n = %d, taboo = %d, swap_count = %d", n, taboo_count, swaps);
}
int[][] taboos = [];
foreach (i; 0..taboo_count)
{
taboos ~= [to!int(buf[0]), to!int(buf[1])];
}
debug
{
foreach (taboo; taboos)
{
writefln("%d >< %d", taboo[0], taboo[1]);
}
}

double success = 0;
foreach (t; 0..2000000)
{
success += try_D(n, taboos, swaps);
}
writefln("%f", success / 2000000);
}

int try_D(int n, int[][] taboos, int swaps)
{
int[] position = [];
foreach (i; 0..n)
{
position ~= i;
}
foreach (i; 0..swaps)
{
auto s0 = uniform(0, n);
auto s1 = (s0 + uniform(1, n)) % n;
swap(position[s0], position[s1]);
}
foreach (i; 0..n)
{
auto a0 = position[i];
auto a1 = position[(i+1)%n];
foreach (taboo; taboos)
{
if (taboo[0] == a0 && taboo[1] == a1)
{
return 0;
}
if (taboo[1] == a0 && taboo[0] == a1)
{
return 0;
}
}
}
return 1;
}
```

#### Submission Info

Submission Time 2012-05-27 20:56:45+0900 D - シャッフル席替え majiang D (DMD 2.060) 100 1620 Byte AC 6923 ms 1852 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 3364 ms 1792 KB
00_mini_02.txt AC 3369 ms 1792 KB
00_sample_01.txt AC 1385 ms 1784 KB
00_sample_02.txt AC 5333 ms 1848 KB
00_sample_03.txt AC 1737 ms 1788 KB
01_rnd_11_01.txt AC 6078 ms 1784 KB
01_rnd_11_02.txt AC 6167 ms 1788 KB
01_rnd_11_03.txt AC 6318 ms 1780 KB
01_rnd_11_04.txt AC 6466 ms 1792 KB
01_rnd_11_05.txt AC 6539 ms 1780 KB
01_rnd_11_06.txt AC 6694 ms 1792 KB
01_rnd_11_07.txt AC 6817 ms 1780 KB
01_rnd_11_08.txt AC 6828 ms 1784 KB
01_rnd_11_09.txt AC 6864 ms 1848 KB
01_rnd_11_10.txt AC 6794 ms 1784 KB
01_rnd_11_11.txt AC 6923 ms 1792 KB
01_rnd_11_12.txt AC 5504 ms 1792 KB
01_rnd_11_13.txt AC 2391 ms 1792 KB
01_rnd_11_14.txt AC 2885 ms 1808 KB
01_rnd_11_15.txt AC 6311 ms 1788 KB
01_rnd_11_16.txt AC 4915 ms 1764 KB
01_rnd_11_17.txt AC 4104 ms 1784 KB
01_rnd_11_18.txt AC 5482 ms 1788 KB
01_rnd_11_19.txt AC 6564 ms 1848 KB
01_rnd_11_20.txt AC 6506 ms 1788 KB
01_rnd_11_21.txt AC 5185 ms 1792 KB
01_rnd_11_22.txt AC 4228 ms 1780 KB
01_rnd_7_01.txt AC 5632 ms 1788 KB
01_rnd_7_02.txt AC 5336 ms 1784 KB
01_rnd_7_03.txt AC 5406 ms 1788 KB
01_rnd_7_04.txt AC 5448 ms 1792 KB
01_rnd_7_05.txt AC 5461 ms 1788 KB
01_rnd_7_06.txt AC 5569 ms 1796 KB
01_rnd_7_07.txt AC 5560 ms 1792 KB
01_rnd_7_08.txt AC 5573 ms 1840 KB
01_rnd_7_09.txt AC 5565 ms 1792 KB
01_rnd_7_10.txt AC 5540 ms 1784 KB
01_rnd_7_11.txt AC 5519 ms 1784 KB
01_rnd_7_12.txt AC 3579 ms 1780 KB
01_rnd_7_13.txt AC 5177 ms 1780 KB
01_rnd_7_14.txt AC 3917 ms 1804 KB
01_rnd_7_15.txt AC 3605 ms 1776 KB
01_rnd_7_16.txt AC 5183 ms 1784 KB
01_rnd_7_17.txt AC 3122 ms 1784 KB
01_rnd_7_18.txt AC 4010 ms 1776 KB
01_rnd_7_19.txt AC 2581 ms 1784 KB
01_rnd_7_20.txt AC 2914 ms 1788 KB
01_rnd_7_21.txt AC 3863 ms 1848 KB
01_rnd_7_22.txt AC 2440 ms 1788 KB
01_rnd_8_01.txt AC 5635 ms 1796 KB
01_rnd_8_02.txt AC 5771 ms 1796 KB
01_rnd_8_03.txt AC 5821 ms 1784 KB
01_rnd_8_04.txt AC 5899 ms 1792 KB
01_rnd_8_05.txt AC 6003 ms 1784 KB
01_rnd_8_06.txt AC 6015 ms 1748 KB
01_rnd_8_07.txt AC 6057 ms 1792 KB
01_rnd_8_08.txt AC 6076 ms 1780 KB
01_rnd_8_09.txt AC 6074 ms 1788 KB
01_rnd_8_10.txt AC 6092 ms 1852 KB
01_rnd_8_11.txt AC 6053 ms 1796 KB
01_rnd_8_12.txt AC 4343 ms 1788 KB
01_rnd_8_13.txt AC 2092 ms 1784 KB
01_rnd_8_14.txt AC 4583 ms 1788 KB
01_rnd_8_15.txt AC 3840 ms 1788 KB
01_rnd_8_16.txt AC 3587 ms 1784 KB
01_rnd_8_17.txt AC 5651 ms 1800 KB
01_rnd_8_18.txt AC 2847 ms 1764 KB
01_rnd_8_19.txt AC 4002 ms 1788 KB
01_rnd_8_20.txt AC 4793 ms 1764 KB
01_rnd_8_21.txt AC 2923 ms 1792 KB
01_rnd_8_22.txt AC 5696 ms 1788 KB