oj.uz

Submission #53288

# Submission time Handle Problem Language Result Execution time Memory
53288 2018-06-29T07:49:20 Z 노영훈(#1400) Tram (CEOI13_tram) C++11
25 / 100
 1000 ms 492 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=30010, inf=2e9;

int n, m;
pii P[MX];

inline int sq(int x){
    return x*x;
}
inline int _min(int x, int y){
    return x<y ? x : y;
}

pii solve(){
    int dist[1510][2];
    for(int i=1; i<=n; i++)
        dist[i][0]=dist[i][1]=inf;
    int mx=-1, x0=0, y0=0;
    for(int j=1; j<=m; j++){
        int x,y; tie(x,y)=P[j];
        if(x==0) continue;
        for(int i=1; i<=n; i++){
            dist[i][0]=_min(dist[i][0], sq(i-x)+sq(0-y));
            dist[i][1]=_min(dist[i][1], sq(i-x)+sq(1-y));
        }
    }
    for(int i=1; i<=n; i++){
        if(mx<dist[i][0]) mx=dist[i][0], x0=i, y0=0;
        if(mx<dist[i][1]) mx=dist[i][1], x0=i, y0=1;
    }
    return {x0,y0};
}

void pop(int idx){
    P[idx]={0,0};
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        char ord; int x; cin>>ord;
        if(ord=='E'){
            P[i]=solve();
            cout<<P[i].first<<' '<<P[i].second+1<<'\n';
        }
        else{
            cin>>x;
            pop(x);
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -