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 buf = readln().strip().split();
    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)
    {
        buf = readln().strip().split();
        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
Task D - シャッフル席替え
User majiang
Language D (DMD 2.060)
Score 100
Code Size 1620 Byte
Status AC
Exec Time 6923 ms
Memory 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