oj.uz

답안 #75664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
75664 2018-09-10T17:16:09 Z Osama_Alkhodairy 자리 배치 (IOI18_seats) C++17
5 / 100
 4000 ms 212128 KB 
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;

const int N = 1000001;

int h, w, n;
vector <int> r, c;
set <int> rs[N], cs[N];

void give_initial_chart(int H, int W, vector <int> R, vector <int> C) {
    h = H;
    w = W;
    r = R;
    c = C;
    n = h * w;
    for(int i = 0 ; i < H * W ; i++){
        rs[r[i]].insert(i);
        cs[c[i]].insert(i);
    }
}
int swap_seats(int a, int b) {
    int ret = 0;

    rs[r[a]].erase(a);
    cs[c[a]].erase(a);
    rs[r[b]].erase(b);
    cs[c[b]].erase(b);
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    rs[r[a]].insert(a);
    cs[c[a]].insert(a);
    rs[r[b]].insert(b);
    cs[c[b]].insert(b);

    set <int> ready;
    for(int i = 0 ; i < h ; i++){
        int cur = *rs[i].begin();
        if(cur > 0) ready.insert(cur - 1);
        ready.insert(cur);
    }
    for(int i = 0 ; i < w ; i++){
        int cur = *cs[i].begin();
        if(cur > 0) ready.insert(cur - 1);
        ready.insert(cur);
    }
    ready.insert(n - 1);
    int mnr = 1e9, mxr = -1, mnc = 1e9, mxc = -1;
    for(auto &i : ready){
        mnr = min(mnr, r[i]);
        mnc = min(mnc, c[i]);
        mxr = max(mxr, r[i]);
        mxc = max(mxc, c[i]);
        if((mxr - mnr + 1) * (mxc - mnc + 1) == i + 1) ret++;
    }
    return ret;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 94332 KB Output is correct
2 Correct 114 ms 94700 KB Output is correct
3 Correct 108 ms 94700 KB Output is correct
4 Correct 168 ms 94700 KB Output is correct
5 Correct 142 ms 94700 KB Output is correct
6 Correct 126 ms 94700 KB Output is correct
7 Correct 118 ms 94700 KB Output is correct
8 Correct 107 ms 94700 KB Output is correct
9 Correct 99 ms 94700 KB Output is correct
10 Correct 118 ms 94704 KB Output is correct
11 Correct 127 ms 94704 KB Output is correct
12 Correct 140 ms 94732 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 94332 KB Output is correct
2 Correct 114 ms 94700 KB Output is correct
3 Correct 108 ms 94700 KB Output is correct
4 Correct 168 ms 94700 KB Output is correct
5 Correct 142 ms 94700 KB Output is correct
6 Correct 126 ms 94700 KB Output is correct
7 Correct 118 ms 94700 KB Output is correct
8 Correct 107 ms 94700 KB Output is correct
9 Correct 99 ms 94700 KB Output is correct
10 Correct 118 ms 94704 KB Output is correct
11 Correct 127 ms 94704 KB Output is correct
12 Correct 140 ms 94732 KB Output is correct
13 Correct 262 ms 95756 KB Output is correct
14 Correct 244 ms 95828 KB Output is correct
15 Execution timed out 4035 ms 96272 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4030 ms 212100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 296 ms 212100 KB Output is correct
2 Correct 1025 ms 212100 KB Output is correct
3 Correct 3481 ms 212128 KB Output is correct
4 Execution timed out 4021 ms 212128 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 139 ms 212128 KB Output is correct
2 Correct 210 ms 212128 KB Output is correct
3 Correct 656 ms 212128 KB Output is correct
4 Execution timed out 4045 ms 212128 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 94332 KB Output is correct
2 Correct 114 ms 94700 KB Output is correct
3 Correct 108 ms 94700 KB Output is correct
4 Correct 168 ms 94700 KB Output is correct
5 Correct 142 ms 94700 KB Output is correct
6 Correct 126 ms 94700 KB Output is correct
7 Correct 118 ms 94700 KB Output is correct
8 Correct 107 ms 94700 KB Output is correct
9 Correct 99 ms 94700 KB Output is correct
10 Correct 118 ms 94704 KB Output is correct
11 Correct 127 ms 94704 KB Output is correct
12 Correct 140 ms 94732 KB Output is correct
13 Correct 262 ms 95756 KB Output is correct
14 Correct 244 ms 95828 KB Output is correct
15 Execution timed out 4035 ms 96272 KB Time limit exceeded
16 Halted 0 ms 0 KB -