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 |
|
|
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 |