oj.uz

Submission #864721

# Submission time Handle Problem Language Result Execution time Memory
864721 2023-10-23T13:47:37 Z mychecksedad Parking (CEOI22_parking) C++17
20 / 100
 63 ms 17872 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(i, pos);
            move(up[v[i][1]], 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 4444 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 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4572 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 16688 KB Output is correct
2 Correct 62 ms 17744 KB Output is correct
3 Correct 46 ms 15220 KB Output is correct
4 Correct 43 ms 14920 KB Output is correct
5 Correct 63 ms 17872 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 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4656 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 4440 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 4444 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 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4572 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 55 ms 16688 KB Output is correct
12 Correct 62 ms 17744 KB Output is correct
13 Correct 46 ms 15220 KB Output is correct
14 Correct 43 ms 14920 KB Output is correct
15 Correct 63 ms 17872 KB Output is correct
16 Incorrect 1 ms 4440 KB Output isn't correct
17 Halted 0 ms 0 KB -