oj.uz

Submission #864656

# Submission time Handle Problem Language Result Execution time Memory
864656 2023-10-23T11:23:10 Z mychecksedad Parking (CEOI22_parking) C++17
20 / 100
 62 ms 18328 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;
array<int, 2> col[N][2];
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;
  vector<int> E;
  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;
          v[one[v[i][0]]].pb(v[i][0]);
          ans.pb({i, one[v[i][0]]});
          v[i].clear();
          E.pb(i);
          continue;
        }
        if(up[v[i][0]] != -1){
          ok = 1;
          v[up[v[i][0]]].pop_back();
          v[i].pb(v[i][0]);
          ans.pb({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();
            ans.pb({i, pos});
            ans.pb({up[v[i][1]], pos});
            v[pos].pb(v[i][1]);
            v[pos].pb(v[i][1]);
            v[up[v[i][1]]].pop_back();
            v[i].pop_back();
            ok = 1;
            continue;
          }
        }
        if(one[v[i][1]] != -1){
          ok = 1;
          v[one[v[i][1]]].pb(v[i][1]);
          ans.pb({i, one[v[i][1]]});
          v[i].pop_back();
          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;
        ans.pb({i, E.back()});
        v[E.back()].pb(v[i][1]);
        v[i].pop_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:111:15: warning: unused variable 'aa' [-Wunused-variable]
  111 |   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 4440 KB Output is correct
3 Correct 1 ms 4696 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 4700 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 4440 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 15584 KB Output is correct
2 Correct 62 ms 18328 KB Output is correct
3 Correct 47 ms 15432 KB Output is correct
4 Correct 45 ms 15208 KB Output is correct
5 Correct 61 ms 18272 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4456 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 4456 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 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 4444 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 4440 KB Output is correct
3 Correct 1 ms 4696 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 4700 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 4440 KB Output is correct
11 Correct 54 ms 15584 KB Output is correct
12 Correct 62 ms 18328 KB Output is correct
13 Correct 47 ms 15432 KB Output is correct
14 Correct 45 ms 15208 KB Output is correct
15 Correct 61 ms 18272 KB Output is correct
16 Incorrect 1 ms 4456 KB Output isn't correct
17 Halted 0 ms 0 KB -