Submission #1532030
Source Code Expand
#include <bits/stdc++.h> using namespace std; int main(void) { int N,M; cin >> N >> M; int a[M]; int b[M]; int t1[M]; int t2[M]; int tmp1,tmp2; int count = 0; int count2 = 0; int count3 = 0; for( int i = 0; i < M; i++){ cin >> tmp1 >> tmp2; if(tmp1 == 1 || tmp2 == N){ a[count] = tmp1; b[count] = tmp2; count++; } } sort(a, a+count); sort(b, b+count); //puts(""); for( int i = 0; i < count ; i++){ //printf("%d %d\n",a[i],b[i]); if( a[i] == 1 && (count3 == 0 || t1[count3-1] != a[i])){ t1[count3] = b[i]; count3++; } if( b[i] == N && (count2 == 0 || t2[count2-1] != a[i])){ t2[count2] = a[i]; count2++; } } //puts(""); if( count2 > count3){ for( int i = 0; i < count3; i++){ for( int j = 0; j < count2; j++){ if( t1[i] > t2[j+count2/2]){ j += count2/2; } //printf("%d %d\n",t1[i],t2[j]); if( t1[i] == t2[j] ){ printf("POSSIBLE"); return 0; } if( t1[i] < t2[j] ){ break; } } } }else{ for( int j = 0; j < count2; j++){ for( int i = 0; i < count3; i++){ if( t1[i+count2/2] > t2[j]){ i += count2/2; } //printf("i = %d, j = %d\n", i, j); //printf("%d %d\n",t2[j],t1[i]); if( t1[i] == t2[j] ){ printf("POSSIBLE"); return 0; } if( t2[j] < t1[i] ){ //printf("break!\n"); break; } } } } printf("IMPOSSIBLE"); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Cat Snuke and a Voyage |
User | toame |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2041 Byte |
Status | WA |
Exec Time | 1782 ms |
Memory | 2688 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 300 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2, example3 |
All | example0, example1, example2, example3, last0, last1, many0, many1, rand0, rand1, rand2 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
example3 | AC | 1 ms | 256 KB |
last0 | WA | 151 ms | 2304 KB |
last1 | AC | 148 ms | 256 KB |
many0 | AC | 1778 ms | 2560 KB |
many1 | WA | 1782 ms | 2688 KB |
rand0 | AC | 98 ms | 256 KB |
rand1 | AC | 145 ms | 256 KB |
rand2 | AC | 88 ms | 256 KB |