oj.uz

Submission #864724

# Submission time Handle Problem Language Result Execution time Memory
864724 2023-10-23T13:51:54 Z mychecksedad Parking (CEOI22_parking) C++17
20 / 100
 61 ms 16996 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


int n, m, A[N], B[N], AA = MOD;
vector<pair<int, int>> ans;
vector<vector<int>> v;
vector<int> E;
array<int, 2> col[N][2];

void move(int i, int j){
  if(i==j) return;
  int x = v[i].back();
  ans.pb({i, j});
  v[j].pb(x);
  v[i].pop_back();
  if(v[i].empty()) E.pb(i);
}

void solve(){
  cin >> n >> m;
  v.resize(m);
  for(int i = 0; i < m; ++i){
    cin >> B[i] >> A[i];
    if(B[i] > 0) v[i].pb(B[i]);
    if(A[i] > 0) v[i].pb(A[i]);
  }
  bool ok = 1;
  for(int i = 0; i < m; ++i) if(v[i].empty()) E.pb(i);
  while(ok){
    ok = 0;
    vector<int> one(n+1, -1), up(n+1, -1);
    for(int i = 0; i < m; ++i){
      if(v[i].empty()) continue;
      else if(v[i].size() == 1){
        if(one[v[i][0]] != -1){
          ok = 1;
          move(i, one[v[i][0]]);
          continue;
        }
        if(up[v[i][0]] != -1){
          ok = 1;
          move(up[v[i][0]], i);
          continue;
        }
        one[v[i][0]] = i;
      }else{
        if(v[i][0] == v[i][1]) continue;
        if(up[v[i][1]] != -1){
          if(!E.empty()){
            int pos = E.back();
            E.pop_back();
            move(up[v[i][1]], pos);
            move(i, pos);
            ok = 1;
          }
          continue;   
        }
        if(one[v[i][1]] != -1){
          ok = 1;
          move(i, one[v[i][1]]);
          continue;
        }
        up[v[i][1]] = i;
      }
    }
    if(ok) continue;
    if(E.empty()) break;
    for(int i = 0; i < m; ++i){
      if(v[i].size() == 2){
        if(v[i][0] == v[i][1]) continue;
        move(i, E.back());
        E.pop_back();
        ok = 1;
        break;
      }
    }
  }
  ok = 1;
  for(int i = 0; i < m; ++i){
    if(v[i].empty()) continue;
    if(v[i].size() == 1) ok = 0;
    else{
      ok &= (v[i][0] == v[i][1]);
    }
  }

  if(!ok){
    cout << -1;
    return;
  }

  cout << ans.size() << '\n';
  for(auto x: ans) cout << x.first + 1 << ' ' << x.second + 1 << '\n';
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:108:15: warning: unused variable 'aa' [-Wunused-variable]
  108 |   int tt = 1, aa;
      |               ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 15584 KB Output is correct
2 Correct 60 ms 16720 KB Output is correct
3 Correct 45 ms 14520 KB Output is correct
4 Correct 53 ms 14152 KB Output is correct
5 Correct 61 ms 16996 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Incorrect 1 ms 4440 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 53 ms 15584 KB Output is correct
12 Correct 60 ms 16720 KB Output is correct
13 Correct 45 ms 14520 KB Output is correct
14 Correct 53 ms 14152 KB Output is correct
15 Correct 61 ms 16996 KB Output is correct
16 Incorrect 1 ms 4440 KB Output isn't correct
17 Halted 0 ms 0 KB -