oj.uz

Submission #412384

# Submission time Handle Problem Language Result Execution time Memory
412384 2021-05-26T19:00:58 Z Ahmadsm2005 Seats (IOI18_seats) C++14
11 / 100
 4000 ms 43720 KB 
#include "seats.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>MAT;
pair<int,int>MP[1000001];
int w,h;
int check(int L,int R,int L2,int R2){
int maxer=0;
for(int i=L;i<=R;i++){
for(int l=L2;l<=R2;l++)
maxer=max(maxer,MAT[i][l]);
}
return maxer;
}
int REC(int x1,int x2,int y1,int y2,int MAXER=0){
int MINER=INT_MAX,MINER2=INT_MAX,MINER3=INT_MAX,MINER4=INT_MAX;
int maxer=0;
if(x1)
MINER=check(x1-1,x1-1,y1,y2);
if(x2+1<h)
MINER2=check(x2+1,x2+1,y1,y2);
if(y1)
MINER3=check(x1,x2,y1-1,y1-1);
if(y2+1<w)
MINER4=check(x1,x2,y2+1,y2+1);
int MINER5=min(min(MINER,MINER2),min(MINER3,MINER4));
if(MINER5==INT_MAX)
return 1;
if(MINER5==MINER)
return REC(x1-1,x2,y1,y2,max(MAXER,MINER5))+((x2-x1+1)*(y2-y1+1)==(MAXER+1)?1:0);
else if(MINER5==MINER2)
return REC(x1,x2+1,y1,y2,max(MAXER,MINER5))+((x2-x1+1)*(y2-y1+1)==(MAXER+1)?1:0);
else if(MINER5==MINER3)
return REC(x1,x2,y1-1,y2,max(MAXER,MINER5))+((x2-x1+1)*(y2-y1+1)==(MAXER+1)?1:0);
else if(MINER5==MINER4)
return REC(x1,x2,y1,y2+1,max(MAXER,MINER5))+((x2-x1+1)*(y2-y1+1)==(MAXER+1)?1:0);
}
void give_initial_chart(int H,int W,vector<int>R,vector<int>C){
h=H,w=W;
MAT.resize(H);
for(int i=0;i<H;i++)
MAT[i].resize(W);
for(int i=0;i<H*W;i++)
MAT[R[i]][C[i]]=i,MP[i]={R[i],C[i]};
}
int swap_seats(int a,int b){
swap(MAT[MP[a].first][MP[a].second],MAT[MP[b].first][MP[b].second]);
swap(MP[a],MP[b]);
return REC(MP[0].first,MP[0].first,MP[0].second,MP[0].second);
}

Compilation message

seats.cpp: In function 'int REC(int, int, int, int, int)':
seats.cpp:18:5: warning: unused variable 'maxer' [-Wunused-variable]
   18 | int maxer=0;
      |     ^~~~~
seats.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 7 ms 428 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 7 ms 460 KB Output is correct
7 Correct 6 ms 444 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 6 ms 460 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 7 ms 428 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 7 ms 460 KB Output is correct
7 Correct 6 ms 444 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 6 ms 460 KB Output is correct
13 Correct 178 ms 768 KB Output is correct
14 Correct 130 ms 836 KB Output is correct
15 Correct 447 ms 776 KB Output is correct
16 Correct 291 ms 1348 KB Output is correct
17 Correct 196 ms 768 KB Output is correct
18 Correct 2816 ms 764 KB Output is correct
19 Correct 80 ms 716 KB Output is correct
20 Correct 166 ms 940 KB Output is correct
21 Correct 313 ms 780 KB Output is correct
22 Correct 288 ms 1292 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 716 KB Output is correct
2 Correct 1132 ms 4060 KB Output is correct
3 Execution timed out 4062 ms 43720 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2016 KB Output is correct
2 Correct 24 ms 1996 KB Output is correct
3 Correct 50 ms 1984 KB Output is correct
4 Correct 455 ms 1984 KB Output is correct
5 Execution timed out 4064 ms 2572 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 7 ms 428 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 7 ms 460 KB Output is correct
7 Correct 6 ms 444 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 6 ms 460 KB Output is correct
13 Correct 178 ms 768 KB Output is correct
14 Correct 130 ms 836 KB Output is correct
15 Correct 447 ms 776 KB Output is correct
16 Correct 291 ms 1348 KB Output is correct
17 Correct 196 ms 768 KB Output is correct
18 Correct 2816 ms 764 KB Output is correct
19 Correct 80 ms 716 KB Output is correct
20 Correct 166 ms 940 KB Output is correct
21 Correct 313 ms 780 KB Output is correct
22 Correct 288 ms 1292 KB Output is correct
23 Execution timed out 4065 ms 43708 KB Time limit exceeded
24 Halted 0 ms 0 KB -