oj.uz

답안 #908706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
908706 2024-01-16T17:21:34 Z JakobZorz 자리 배치 (IOI18_seats) C++17
11 / 100
 4000 ms 99276 KB 
#include"seats.h"
#include<iostream>
#include<algorithm>
using namespace std;

int w,h;
vector<int>x,y;
vector<vector<int>>mat;
int arr[1000000];

int get_mat(int x,int y){
    if(x<0||x>=w||y<0||y>=h)
        return w*h;
    return mat[x][y];
}

void upd_sq(int x,int y,int mul){ // 1 for adding and -1 for removing
    vector<int>vals={get_mat(x,y),get_mat(x+1,y),get_mat(x,y+1),get_mat(x+1,y+1)};
    sort(vals.begin(),vals.end());
    /*for(int i:vals)
        cout<<i<<" ";
    cout<<endl;*/
    for(int i=vals[0];i<vals[1];i++)
        arr[i]+=mul;
    for(int i=vals[2];i<vals[3];i++)
        arr[i]+=mul;
}

void give_initial_chart(int H,int W,vector<int>R,vector<int>C){
    x=C;
    y=R;
    h=H;
    w=W;
    mat=vector<vector<int>>(w,vector<int>(h));
    for(int i=0;i<w*h;i++)
        mat[x[i]][y[i]]=i;
    for(int x=-1;x<w;x++)
        for(int y=-1;y<h;y++)
            upd_sq(x,y,1);
}

int swap_seats(int a,int b){
    upd_sq(x[a]-1,y[a]-1,-1);
    upd_sq(x[a]-1,y[a],-1);
    upd_sq(x[a],y[a]-1,-1);
    upd_sq(x[a],y[a],-1);
    upd_sq(x[b]-1,y[b]-1,-1);
    upd_sq(x[b]-1,y[b],-1);
    upd_sq(x[b],y[b]-1,-1);
    upd_sq(x[b],y[b],-1);
    swap(mat[x[a]][y[a]],mat[x[b]][y[b]]);
    swap(x[a],x[b]);
    swap(y[a],y[b]);
    upd_sq(x[a]-1,y[a]-1,1);
    upd_sq(x[a]-1,y[a],1);
    upd_sq(x[a],y[a]-1,1);
    upd_sq(x[a],y[a],1);
    upd_sq(x[b]-1,y[b]-1,1);
    upd_sq(x[b]-1,y[b],1);
    upd_sq(x[b],y[b]-1,1);
    upd_sq(x[b],y[b],1);
    
    int res=0;
    for(int i=0;i<w*h;i++)
        if(arr[i]==4)
            res++;
    return res;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 604 KB Output is correct
2 Correct 7 ms 552 KB Output is correct
3 Correct 9 ms 604 KB Output is correct
4 Correct 7 ms 604 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 8 ms 460 KB Output is correct
7 Correct 9 ms 604 KB Output is correct
8 Correct 7 ms 604 KB Output is correct
9 Correct 7 ms 604 KB Output is correct
10 Correct 10 ms 600 KB Output is correct
11 Correct 9 ms 604 KB Output is correct
12 Correct 6 ms 604 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 604 KB Output is correct
2 Correct 7 ms 552 KB Output is correct
3 Correct 9 ms 604 KB Output is correct
4 Correct 7 ms 604 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 8 ms 460 KB Output is correct
7 Correct 9 ms 604 KB Output is correct
8 Correct 7 ms 604 KB Output is correct
9 Correct 7 ms 604 KB Output is correct
10 Correct 10 ms 600 KB Output is correct
11 Correct 9 ms 604 KB Output is correct
12 Correct 6 ms 604 KB Output is correct
13 Correct 151 ms 860 KB Output is correct
14 Correct 198 ms 964 KB Output is correct
15 Correct 192 ms 1480 KB Output is correct
16 Correct 102 ms 860 KB Output is correct
17 Correct 162 ms 1188 KB Output is correct
18 Correct 97 ms 860 KB Output is correct
19 Correct 103 ms 1108 KB Output is correct
20 Correct 96 ms 984 KB Output is correct
21 Correct 96 ms 1372 KB Output is correct
22 Correct 96 ms 1008 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 1116 KB Output is correct
2 Correct 512 ms 6488 KB Output is correct
3 Correct 3332 ms 47668 KB Output is correct
4 Execution timed out 4014 ms 47556 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 2088 KB Output is correct
2 Correct 51 ms 2088 KB Output is correct
3 Correct 59 ms 2012 KB Output is correct
4 Correct 152 ms 2072 KB Output is correct
5 Correct 1513 ms 3404 KB Output is correct
6 Execution timed out 4018 ms 99276 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 604 KB Output is correct
2 Correct 7 ms 552 KB Output is correct
3 Correct 9 ms 604 KB Output is correct
4 Correct 7 ms 604 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 8 ms 460 KB Output is correct
7 Correct 9 ms 604 KB Output is correct
8 Correct 7 ms 604 KB Output is correct
9 Correct 7 ms 604 KB Output is correct
10 Correct 10 ms 600 KB Output is correct
11 Correct 9 ms 604 KB Output is correct
12 Correct 6 ms 604 KB Output is correct
13 Correct 151 ms 860 KB Output is correct
14 Correct 198 ms 964 KB Output is correct
15 Correct 192 ms 1480 KB Output is correct
16 Correct 102 ms 860 KB Output is correct
17 Correct 162 ms 1188 KB Output is correct
18 Correct 97 ms 860 KB Output is correct
19 Correct 103 ms 1108 KB Output is correct
20 Correct 96 ms 984 KB Output is correct
21 Correct 96 ms 1372 KB Output is correct
22 Correct 96 ms 1008 KB Output is correct
23 Execution timed out 4042 ms 47888 KB Time limit exceeded
24 Halted 0 ms 0 KB -