Submission #2627523


Source Code Expand

#include<bits/stdc++.h>

using namespace std;

int nr, N, a[100009], b[100009], A[100009], B[100009], id[100009], sz[100009], may[100009], both1[100009], dp[100009][2];
const int INF = 1e8;

bool cmp (int i, int j)
{
    if (A[i] + B[i] == A[j] + B[j]) return (A[i] < A[j]);
    return (A[i] + B[i] < A[j] + B[j]);
}

int findPair (int x, int y)
{
    int p = 1, u = nr, mij;
    while (p <= u)
    {
        mij = (p + u) >> 1;
        if (a[mij] == x && b[mij] == y) return mij;
        if (a[mij] + b[mij] < x + y || (a[mij] + b[mij] == x + y && a[mij] < x)) p = mij + 1;
        else u = mij - 1;
    }
    return 0;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d", &N);
printf ("-1\n");
return 0;
for (int i=1; i<=N; i++)
    scanf ("%d %d", &A[i], &B[i]), id[i] = i;
sort (id + 1, id + N + 1, cmp);
if (A[2] != B[1] || A[id[1]] + B[id[1]] < A[2] || A[1] != 0 || B[2] != 0)
{
    printf ("-1\n");
    return 0;
}
for (int i=1; i<=N; i++)
    if ((A[i] == 0 && i != 1) || (B[i] == 0 && i != 2))
    {
        printf ("-1\n");
        return 0;
    }
for (int i=1; i<=N; i++)
{
    int j = i;
    while (j + 1 <= N && A[id[j]] == A[id[j + 1]] && B[id[j]] == B[id[j + 1]])
        j ++;
    a[++nr] = A[id[i]], b[nr] = B[id[i]], sz[nr] = j - i + 1;
    i = j;
}
for (int i=1; i<=nr; i++)
    may[i] = (findPair (a[i] + 1, b[i] - 1) != 0),
    both1[i] = (findPair (a[i] - 1, b[i] - 1) != 0);
if (!may[1])
{
    printf ("-1\n");
    return 0;
}
for (int i=1; i<=nr; i++)
    if ((a[i] > 0 && findPair (a[i] - 1, b[i]) == 0 && findPair (a[i] - 1, b[i] + 1) == 0 && both1[i] == 0) ||
        (b[i] > 0 && findPair (a[i], b[i] - 1) == 0 && findPair (a[i] + 1, b[i] - 1) == 0 && both1[i] == 0))
        {
            printf ("-1\n");
            return 0;
        }
for (int i=1; i<=nr; i++)
    for (int j=0; j<2; j++)
        dp[i][j] = INF;
dp[1][1] = 1;
for (int i=1; i<nr; i++)
    for (int j=0; j<=may[i]; j++)
        for (int k=0; k<=may[i + 1]; k++)
        {
            if (k == 0 && both1[i + 1] == 1)
                dp[i + 1][k] = min (dp[i + 1][k], dp[i][j] + sz[i + 1]);
            int curr = dp[i][j];
            if (j == 0)
            {
                if (findPair (a[i + 1] - 1, b[i + 1]) == 0 && both1[i + 1] == 0) continue;
                curr += sz[i + 1];
            }
            if (k == 0 && b[i + 1] > 0)
            {
                if (findPair (a[i + 1], b[i + 1] - 1) == 0 && both1[i + 1] == 0) continue;
                curr += sz[i + 1];
            }
            if (curr < dp[i + 1][k])
                dp[i + 1][k] = curr;
        }
printf ("%d\n", min (dp[nr][0], dp[nr][1]));
return 0;
}

Submission Info

Submission Time
Task A - Distance Pairs
User geniucos
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2778 Byte
Status WA
Exec Time 1 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:32:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &N);
                 ^
./Main.cpp:36:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &A[i], &B[i]), id[i] = i;
                                             ^

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 1500
Status
AC × 1
WA × 1
AC × 13
WA × 22
Set Name Test Cases
sample sample-01.txt, sample-02.txt
All sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt WA 1 ms 256 KB
01-04.txt WA 1 ms 256 KB
01-05.txt WA 1 ms 256 KB
01-06.txt WA 1 ms 256 KB
01-07.txt WA 1 ms 256 KB
01-08.txt WA 1 ms 256 KB
01-09.txt WA 1 ms 256 KB
01-10.txt WA 1 ms 256 KB
01-11.txt WA 1 ms 256 KB
01-12.txt WA 1 ms 256 KB
01-13.txt WA 1 ms 256 KB
01-14.txt WA 1 ms 256 KB
01-15.txt WA 1 ms 256 KB
01-16.txt WA 1 ms 256 KB
01-17.txt WA 1 ms 256 KB
01-18.txt WA 1 ms 256 KB
01-19.txt WA 1 ms 256 KB
01-20.txt WA 1 ms 256 KB
01-21.txt WA 1 ms 256 KB
01-22.txt WA 1 ms 256 KB
01-23.txt AC 1 ms 256 KB
01-24.txt AC 1 ms 256 KB
01-25.txt AC 1 ms 256 KB
01-26.txt AC 1 ms 256 KB
01-27.txt AC 1 ms 256 KB
01-28.txt AC 1 ms 256 KB
01-29.txt AC 1 ms 256 KB
01-30.txt AC 1 ms 256 KB
01-31.txt AC 1 ms 256 KB
sample-01.txt WA 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB