oj.uz

Submission #264749

# Submission time Handle Problem Language Result Execution time Memory
264749 2020-08-14T08:58:30 Z 반딧불(#5094) Tram (CEOI13_tram) C++17
40 / 100
 1000 ms 976 KB 
#include <bits/stdc++.h>
#define SQR(x) ((x)*(x))

using namespace std;

typedef long long ll;

int n, m, p;
ll x[150002], y[150002];
int idx[150002];
bool occupied[150002][3];

struct dat{
    ll l, r, v;
    bool cmp;
    dat* opp = nullptr;

    dat(){}
    dat(ll l, ll r, ll v, bool cmp): l(l), r(r), v(v), cmp(cmp){}
    bool operator<(const dat &t)const{
        if(!cmp) return v==t.v?(l==t.l?r<t.r:l<t.l):v>t.v;
        return l<t.l;
    }

    ll recalculate(){
        v = 0;
        if(occupied[l][1] ^ occupied[l][2]) v = 1;
        if(occupied[r][1] ^ occupied[r][2]) v = 1;
        vector<ll> vec {(l+r)/2, (l+r)/2+1, l, r};
        for(auto &tmp: vec){
            for(ll i=1; i<=2; i++){
                if(occupied[tmp][i]) continue;
                ll tdist = 1e18;
                for(ll j=1; j<=2; j++){
                    if(occupied[l][j]) tdist = min(tdist, SQR(l - tmp) + SQR(i - j));
                    if(occupied[r][j]) tdist = min(tdist, SQR(r - tmp) + SQR(i - j));
                }
                v = max(v, tdist);
            }
        }

        if((occupied[l][1] || occupied[l][2]) ^ (occupied[r][1] || occupied[r][2])){
            v = SQR(r-l) + 1;
        }

        return v;
    }

    pair<ll, ll> location(){
        v = 0;
        pair<ll, ll> ret (1LL, 1LL);
        if(occupied[l][1] ^ occupied[l][2]) v = 1, ret = {l, occupied[l][1] ? 2 : 1};
        else if(occupied[r][1] ^ occupied[r][2]) v = 1, ret = {r, occupied[r][1] ? 2 : 1};
        vector<ll> vec {(l+r)/2, (l+r)/2+1, l, r};
        for(auto &tmp: vec){
            for(ll i=1; i<=2; i++){
                if(occupied[tmp][i]) continue;
                ll tdist = 1e18;
                for(ll j=1; j<=2; j++){
                    if(occupied[l][j]) tdist = min(tdist, SQR(l - tmp) + SQR(i - j));
                    if(occupied[r][j]) tdist = min(tdist, SQR(r - tmp) + SQR(i - j));
                }
                if(v < tdist || (v == tdist && ret > make_pair(tmp, i))) v = tdist, ret = make_pair(tmp, i);
            }
        }

        if(!(occupied[l][1] || occupied[l][2])){
            if(occupied[r][2]) v = SQR(r-l)+1, ret = {l, 1};
            else if(occupied[r][1]) v = SQR(r-l)+1, ret = {l, 2};
        }
        else if(!(occupied[r][1] || occupied[r][2])){
            if(occupied[l][2]) v = SQR(r-l)+1, ret = {r, 1};
            else if(occupied[l][1]) v = SQR(r-l)+1, ret = {r, 2};
        }

        return ret;
    }
};

int main(){
    int cnt = 0;
    scanf("%d %d", &n, &m);
    for(int q=1; q<=m; q++){
        char c;
        scanf(" %c", &c);
        if(c == 'E'){
            cnt++;
            ll dist = -1;
            pair<ll, ll> ans;

            vector<ll> v;
            for(int i=1; i<=n; i++){
                if(i==1 || i==n || occupied[i][1] || occupied[i][2]) v.push_back(i);
            }

            for(int i=0; i<(int)v.size()-1; i++){
                dat tmp = dat(v[i], v[i+1], 0, 0);
                if(tmp.recalculate() > dist){
                    dist = tmp.v;
                    ans = tmp.location();
                }
            }

            x[q] = ans.first, y[q] = ans.second;
            occupied[x[q]][y[q]] = 1;
        }
        else{
            cnt--;
            int p;
            scanf("%d", &p);
            occupied[x[p]][y[p]] = 0;
        }
    }
    for(int i=1; i<=m; i++){
        if(x[i]) printf("%lld %lld\n", x[i], y[i]);
    }
}

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
tram.cpp:110:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |             scanf("%d", &p);
      |             ~~~~~^~~~~~~~~~

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
0 / 15.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 420 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 16 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 428 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 15 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 864 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 192 ms 748 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 876 KB Output is correct
2 Incorrect 4 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1038 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 1076 ms 976 KB Time limit exceeded
2 Halted 0 ms 0 KB -