oj.uz

Submission #748236

# Submission time Handle Problem Language Result Execution time Memory
748236 2023-05-25T20:31:24 Z Sam_a17 Parking (CEOI22_parking) C++17
12 / 100
 506 ms 411656 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
 
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ld long double
#define ll long long
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
void print(long double t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T> void print(T v[],T n) {cerr << "["; for(int i = 0; i < n; i++) {cerr << v[i] << " ";} cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
 
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 3e5 + 10;
long long n, m, d;
deque<int> a[N];
deque<pair<int, int>> color[N];
 
void solve_() {
  cin >> n >> m;
 
  vector<int> empty, non_match;
  for(int i = 0; i < m; i++) {
    a[i].resize(2);
    cin >> a[i][0] >> a[i][1];
 
    if(a[i][0] && a[i][1] && a[i][0] != a[i][1]) {
      color[a[i][0]].push_back({32, i});
      color[a[i][1]].push_back({8, i});
    } else if(a[i][0] && a[i][0] != a[i][1]) {
      color[a[i][0]].push_back({1, i});
    }
 
    if(!a[i][0]) {
      empty.push_back(i + 1);
      a[i].pop_back();
      a[i].pop_back();
    }
  }
 
  set<pair<int, int>> st;
  for(int i = 1; i <= n; i++) {
    if(color[i].empty()) continue;
    st.insert({color[i][0].first + color[i][1].first, i});
  }
 
  vector<pair<int, int>> answer;
  while(!st.empty()) {
    auto u = *st.begin();
    st.erase(st.begin());
 
    if(u.first == 2) {
      int curr_color = u.second;
      int ft = color[curr_color][0].second;
      int sc = color[curr_color][1].second;
      answer.push_back({ft + 1, sc + 1});
      
      // a[ft].pop_front();    
      empty.push_back(ft + 1);
    } else if(u.first == 9) {
      int curr_color = u.second;
      int ft = color[curr_color][0].second;
      int sc = color[curr_color][1].second;
 
      if(color[curr_color][0].first < color[curr_color][1].first) {
        swap(ft, sc);
      }
 
      answer.push_back({ft + 1, sc + 1});
      // a[ft].pop_back();
 
      int need_to_update = a[ft][0];
      int sum = color[need_to_update][0].first + color[need_to_update][1].first;
      
      auto need_to_find = st.find({sum, need_to_update});
      // assert(need_to_find != st.end());
      st.erase(need_to_find);
 
      if(color[need_to_update][0].second == ft) {
        color[need_to_update][0].first = 1;
      } else {
        color[need_to_update][1].first = 1;
      }
 
      st.insert({color[need_to_update][0].first + color[need_to_update][1].first, need_to_update});
    } else if(u.first == 16) {
      if(empty.empty()) {
        cout << -1 << endl;
        return;
      }


      int curr_color = u.second;
      int ft = color[curr_color][0].second;
      int sc = color[curr_color][1].second;
 
      auto empty_pos = empty.back();
      empty.pop_back();
      answer.push_back({ft + 1, empty_pos}); 
      answer.push_back({sc + 1, empty_pos});
 
      {
        // a[ft].pop_back();
        int need_to_update = a[ft][0];
        int sum = color[need_to_update][0].first + color[need_to_update][1].first;
        
        auto need_to_find = st.find({sum, need_to_update});
        st.erase(need_to_find);
 
        if(color[need_to_update][0].second == ft) {
          color[need_to_update][0].first = 1;
        } else {
          color[need_to_update][1].first = 1;
        }
 
        st.insert({color[need_to_update][0].first + color[need_to_update][1].first, need_to_update});
      }
 
      {
        ft = sc;
        // a[ft].pop_back();
        int need_to_update = a[ft][0];
        int sum = color[need_to_update][0].first + color[need_to_update][1].first;
        
        auto need_to_find = st.find({sum, need_to_update});
        // if(need_to_find != st.end()) {
        st.erase(need_to_find);
        // }
 
        if(color[need_to_update][0].second == ft) {
          color[need_to_update][0].first = 1;
        } else {
          color[need_to_update][1].first = 1;
        }
 
        st.insert({color[need_to_update][0].first + color[need_to_update][1].first, need_to_update});
      }
 
    } else if(u.first == 40 || u.first == 33) {
      if(empty.empty()) {
        cout << -1 << endl;
        return;
      }
 
      int curr_color = u.second;
      int ft = color[curr_color][0].second;
      int sc = color[curr_color][1].second;
 
      if(color[curr_color][0].first < color[curr_color][1].first) {
        swap(ft, sc);
      }
      
      // dbg(ft)
      // ft takna
      auto empty_pos = empty.back();
      empty.pop_back();
      
      {
        //taki vriny qcum enq empty_pos
        answer.push_back({ft + 1, empty_pos});
 
        {
          // hanum qcum enq
          // a[empty_pos].push_back(a[ft].back());
          // dbg(a[empty_pos])
          // a[ft].pop_back();
 
          int need_to_update = a[ft][1];
          int sum = color[need_to_update][0].first + color[need_to_update][1].first;
          
          auto need_to_find = st.find({sum, need_to_update});
          // if(need_to_find != st.end()) {
          st.erase(need_to_find);
          // }
          // dbg(color[need_to_update][0])
          // dbg(color[need_to_update][1])
 
 
          if(color[need_to_update][0].second == ft) {
            color[need_to_update][0].first = 1;
            color[need_to_update][0].second = empty_pos;
          } else {
            color[need_to_update][1].first = 1;
            color[need_to_update][1].second = empty_pos;
          }
 
          st.insert({color[need_to_update][0].first + color[need_to_update][1].first, need_to_update});
        }
 
        int need_to_update = a[ft][0];
        if(color[need_to_update][0].second == ft) {
          color[need_to_update][0].first = 1;
        } else {
          color[need_to_update][1].first = 1;
        }
        st.insert({color[need_to_update][0].first + color[need_to_update][1].first, need_to_update});
      }
    }  else {
      cout << -1 << endl;
      return;
    }
  }
 
  cout << sz(answer) << endl;
  for(auto i: answer) {
    cout << i.first << " " << i.second << endl;
  } 
}
 
int main () {
  setIO("");
 
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1; 
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:66:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 404140 KB Output is correct
2 Correct 238 ms 404120 KB Output is correct
3 Correct 233 ms 404132 KB Output is correct
4 Partially correct 243 ms 404140 KB Output is partially correct
5 Correct 233 ms 404148 KB Output is correct
6 Correct 232 ms 404152 KB Output is correct
7 Correct 246 ms 404216 KB Output is correct
8 Correct 228 ms 404176 KB Output is correct
9 Correct 240 ms 404172 KB Output is correct
10 Correct 236 ms 404172 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 410168 KB Output is correct
2 Correct 506 ms 411656 KB Output is correct
3 Correct 374 ms 408748 KB Output is correct
4 Correct 367 ms 408796 KB Output is correct
5 Correct 475 ms 411276 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 404172 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 234 ms 404172 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 242 ms 404244 KB Output is correct
2 Correct 260 ms 404208 KB Output is correct
3 Correct 246 ms 404276 KB Output is correct
4 Partially correct 239 ms 404300 KB Output is partially correct
5 Correct 230 ms 404160 KB Output is correct
6 Correct 230 ms 404240 KB Output is correct
7 Correct 232 ms 404272 KB Output is correct
8 Incorrect 233 ms 404172 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 238 ms 404140 KB Output is correct
2 Correct 238 ms 404120 KB Output is correct
3 Correct 233 ms 404132 KB Output is correct
4 Partially correct 243 ms 404140 KB Output is partially correct
5 Correct 233 ms 404148 KB Output is correct
6 Correct 232 ms 404152 KB Output is correct
7 Correct 246 ms 404216 KB Output is correct
8 Correct 228 ms 404176 KB Output is correct
9 Correct 240 ms 404172 KB Output is correct
10 Correct 236 ms 404172 KB Output is correct
11 Correct 429 ms 410168 KB Output is correct
12 Correct 506 ms 411656 KB Output is correct
13 Correct 374 ms 408748 KB Output is correct
14 Correct 367 ms 408796 KB Output is correct
15 Correct 475 ms 411276 KB Output is correct
16 Incorrect 234 ms 404172 KB Output isn't correct
17 Halted 0 ms 0 KB -