| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 787802 |
2023-07-19T12:51:52 Z |
doowey |
Parking (CEOI22_parking) |
C++14 |
|
2000 ms |
524288 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)2e5 + 10;
vector<pii> P[N];
int park[N][2];
vector<pii> res;
int pt[N];
int n, m;
set<int> empt;
set<int> C[5];
int get_case(int it){
if(P[it][0].fi == P[it][1].fi) return -1;
for(int j = 0 ; j < 2; j ++ ){
if(P[it][j].se == 1 && P[it][(j^1)].se == 0 && park[P[it][j].fi][0] == 0){
return 0;
}
}
if(P[it][0].se == 1 && P[it][1].se == 1 && park[P[it][0].fi][0] == 0 && park[P[it][1].fi][0] == 0){
return 1;
}
for(int j = 0 ; j < 2; j ++ ){
if(P[it][j].se == 1 && P[it][(j^1)].se == 1 && park[P[it][j].fi][0] == 0){
return 2;
}
}
int rev;
int pa, pb;
if(P[it][0].se != P[it][1].se){
rev = (P[it][0].se ^ 1);
pa = P[it][0].fi;
pb = P[it][1].fi;
if(park[pa][rev] == park[pb][rev]){
return 3;
}
}
for(int it = 1; it <= n; it ++ ){
return 4;
}
return -1;
}
void apply_operation(int x, int y){
res.push_back(mp(x,y));
int ci = 0;
int cj = 0;
if(empt.count(x)) empt.erase(x);
if(empt.count(y)) empt.erase(y);
if(park[x][ci] == 0) ci ++ ;
if(park[y][cj+1] == 0) cj ++ ;
set<int> E;
for(int j = 0 ; j < 2; j ++ ){
if(park[x][j] != 0) E.insert(park[x][j]);
if(park[y][j] != 0) E.insert(park[y][j]);
}
int c;
for(auto x : E){
c = get_case(x);
if(c >= 0) C[c].erase(x);
}
// x -> y
int id = park[x][ci];
if(P[id][0] == mp(x, ci))
P[id].erase(P[id].begin());
else
P[id].erase(P[id].begin() + 1);
park[y][cj] = id;
park[x][ci] = 0;
P[id].push_back(mp(y, cj));
if(park[x][0] + park[x][1] == 0) empt.insert(x);
if(park[y][0] + park[y][1] == 0) empt.insert(y);
for(auto x : E){
c = get_case(x);
if(c >= 0) C[c].insert(x);
}
}
bool car_sort(){
// Case 1:
int it;
if(!C[0].empty()){
it = *C[0].begin();
for(int j = 0 ; j < 2; j ++ ){
if(P[it][j].se == 1 && P[it][(j^1)].se == 0 && park[P[it][j].fi][0] == 0){ // up is empty
apply_operation(P[it][(j^1)].fi, P[it][j].fi);
return true;
}
}
}
// Case 2:
if(!C[1].empty()){
it = *C[1].begin();
apply_operation(P[it][0].fi, P[it][1].fi);
return true;
}
if(empt.empty()) return false;
int emp = *empt.begin();
// Case 3:
if(!C[2].empty()){
it = *C[2].begin();
for(int j = 0 ; j < 2; j ++ ){
if(P[it][j].se == 1 && P[it][(j^1)].se == 1 && park[P[it][j].fi][0] == 0){
apply_operation(P[it][j^1].fi, emp);
apply_operation(P[it][j].fi, P[it][j^1].fi);
return true;
}
}
}
// Case 4:
int rev;
int pa, pb;
if(!C[3].empty()){
it = *C[3].begin();
rev = (P[it][0].se ^ 1);
pa = P[it][0].fi;
pb = P[it][1].fi;
apply_operation(pa, emp);
apply_operation(pb, emp);
apply_operation(pa, pb);
return true;
}
// Case 5:
if(!C[4].empty()){
it = *C[4].begin();
apply_operation(P[it][0].fi, emp);
return true;
}
return false;
}
vector<array<int,2>> pp;
set<vector<array<int,2>>> G;
int solve(){
for(int i = 1; i <= m; i ++ ){
pp.push_back({park[i][0], park[i][1]});
}
queue<vector<array<int,2>>> que;
map<vector<array<int,2>>, int> res;
que.push(pp);
res[pp]=0;
int d;
while(!que.empty()){
pp=que.front();
que.pop();
bool good = true;
for(int i = 0; i < m ; i ++ ){
if(pp[i][0] != pp[i][1]){
good = false;
}
}
d=res[pp];
if(good){
return d;
}
int t1;
int t2;
//return;
/*
for(int i = 0 ; i < m ; i ++ ){
cout << pp[i][0] << " ";
}
cout << "|\n";
for(int i = 0 ; i < m ; i ++ ){
cout << pp[i][1] << " ";
}
cout << "|\n";
cout << "-------------\n";
*/
for(int i = 0; i < m; i ++ ){
if(pp[i][0] == pp[i][1]) continue; // dont move it
t1 = 0;
if(pp[i][0] == 0) t1 = 1;
for(int j = 0; j < m ; j ++ ){
if(j == i) continue;
if(pp[j][0] != 0) continue;
if(pp[j][1] == 0) t2 = 1;
else t2 = 0;
if(t2 == 0 && pp[i][t1] != pp[j][t2 + 1]) continue;
pp[j][t2]=pp[i][t1];
pp[i][t1]=0;
if(!res.count(pp)){
res[pp]=d+1;
que.push(pp);
}
pp[i][t1]=pp[j][t2];
pp[j][t2]=0;
}
}
}
return -1;
}
int main(){
fastIO;
//freopen("in.txt", "r", stdin);
cin >> n >> m;
int v;
for(int i = 1; i <= m ; i ++ ){
cin >> park[i][1] >> park[i][0];
for(int j = 0 ; j < 2; j ++ ){
if(park[i][j] > 0) P[park[i][j]].push_back(mp(i,j));
}
if(park[i][0] + park[i][1] == 0) empt.insert(i);
}
for(int i = 1; i <= n ; i ++ ){
int v = get_case(i);
if(v >= 0){
C[v].insert(i);
}
}
int s = solve();
cout << s << "\n";
return 0;
/*
cout << "COMP: " << s << "\n";
while(car_sort());
for(int i = 1; i <= m; i ++ ){
if(park[i][0] != park[i][1]){
cout << "-1\n";
return 0;
}
}
cout << res.size() << "\n";
for(auto p : res){
cout << p.fi << " " << p.se << "\n";
}
*/
return 0;
}
Compilation message
Main.cpp: In function 'bool car_sort()':
Main.cpp:123:9: warning: variable 'rev' set but not used [-Wunused-but-set-variable]
123 | int rev;
| ^~~
Main.cpp: In function 'int main()':
Main.cpp:212:9: warning: unused variable 'v' [-Wunused-variable]
212 | int v;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
2 ms |
4948 KB |
Output is partially correct |
| 2 |
Partially correct |
3 ms |
4948 KB |
Output is partially correct |
| 3 |
Partially correct |
2 ms |
4948 KB |
Output is partially correct |
| 4 |
Partially correct |
3 ms |
4948 KB |
Output is partially correct |
| 5 |
Partially correct |
2 ms |
4948 KB |
Output is partially correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Partially correct |
3 ms |
4948 KB |
Output is partially correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4992 KB |
Output is correct |
| 10 |
Partially correct |
3 ms |
4948 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
263 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2087 ms |
459756 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2087 ms |
459756 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2065 ms |
448388 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
2 ms |
4948 KB |
Output is partially correct |
| 2 |
Partially correct |
3 ms |
4948 KB |
Output is partially correct |
| 3 |
Partially correct |
2 ms |
4948 KB |
Output is partially correct |
| 4 |
Partially correct |
3 ms |
4948 KB |
Output is partially correct |
| 5 |
Partially correct |
2 ms |
4948 KB |
Output is partially correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Partially correct |
3 ms |
4948 KB |
Output is partially correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4992 KB |
Output is correct |
| 10 |
Partially correct |
3 ms |
4948 KB |
Output is partially correct |
| 11 |
Runtime error |
263 ms |
524288 KB |
Execution killed with signal 9 |
| 12 |
Halted |
0 ms |
0 KB |
- |
