oj.uz

Submission #25643

# Submission time Handle Problem Language Result Execution time Memory
25643 2017-06-23T10:36:50 Z Extazy Tram (CEOI13_tram) C++14
45 / 100
 1000 ms 3180 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 150007;
const long long INF = (1e18) + 7;

int n,q;
pair < int, int > save[N];
bool have[N][2];
long long dist[N][2];
int sz;

long long get_dist(pair < int, int > a, pair < int, int > b) {
    return ((a.first-b.first)*1ll*(a.first-b.first) + (a.second-b.second)*1ll*(a.second-b.second));
}

pair < int, int > enter() {
    if(sz==0) {
        return make_pair(1,0);
    }

    int i,j;
    int last0,last1;
    long long max_dist=-INF;

    for(i=1;i<=n;i++) {
        for(j=0;j<2;j++) {
            dist[i][j]=INF;
        }
    }

    last0=0;
    last1=0;
    for(i=1;i<=n;i++) {
        for(j=0;j<2;j++) if(!have[i][j]) {
            if(last0!=0) dist[i][j]=min(dist[i][j],get_dist(make_pair(i,j),make_pair(last0,0)));
            if(last1!=0) dist[i][j]=min(dist[i][j],get_dist(make_pair(i,j),make_pair(last1,1)));
            if(have[i][1-j]) dist[i][j]=1;
        }
        if(have[i][0]) last0=i;
        if(have[i][1]) last1=i;
    }

    last0=0;
    last1=0;
    for(i=n;i>=1;i--) {
        for(j=0;j<2;j++) if(!have[i][j]) {
            if(last0!=0) dist[i][j]=min(dist[i][j],get_dist(make_pair(i,j),make_pair(last0,0)));
            if(last1!=0) dist[i][j]=min(dist[i][j],get_dist(make_pair(i,j),make_pair(last1,1)));
            max_dist=max(max_dist,dist[i][j]);
        }
        if(have[i][0]) last0=i;
        if(have[i][1]) last1=i;
    }

    for(i=1;i<=n;i++) {
        for(j=0;j<2;j++) if(!have[i][j]) {
            if(max_dist==dist[i][j]) {
                return make_pair(i,j);
            }
        }
    }
}

int main() {
    int i,x;
    char type[4];
    
    scanf("%d %d", &n, &q);
    for(i=1;i<=q;i++) {
        scanf("%s", type);
        if(type[0]=='E') {
            save[i]=enter();
            have[save[i].first][save[i].second]=true;
            printf("%d %d\n", save[i].first, save[i].second+1);
            ++sz;
        }
        else {
            scanf("%d", &x);
            have[save[x].first][save[x].second]=false;
            --sz;
        }
    }

    return 0;
}

Compilation message

tram.cpp: In function 'std::pair<int, int> enter()':
tram.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
   64 | }
      | ^
tram.cpp: In function 'int main()':
tram.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |         scanf("%s", type);
      |         ~~~~~^~~~~~~~~~~~
tram.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 19 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 420 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 15 ms 364 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 3024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 3052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 3180 KB Time limit exceeded
2 Halted 0 ms 0 KB -