oj.uz

Submission #748243

# Submission time Handle Problem Language Result Execution time Memory
748243 2023-05-25T20:40:28 Z Sam_a17 Parking (CEOI22_parking) C++17
20 / 100
 513 ms 411508 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;


      // dbg(make_pair(ft, sc))
      // dbg(curr_color)
 
      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])
          // dbg(color[need_to_update])
 
 
          if(color[need_to_update][0].second == ft) {
            color[need_to_update][0].first = 1;
            color[need_to_update][0].second = empty_pos - 1;
          } else {
            color[need_to_update][1].first = 1;
            color[need_to_update][1].second = empty_pos - 1;
          }
 
          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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 404128 KB Output is correct
2 Correct 235 ms 404192 KB Output is correct
3 Correct 233 ms 404300 KB Output is correct
4 Correct 224 ms 404116 KB Output is correct
5 Correct 223 ms 404172 KB Output is correct
6 Correct 222 ms 404212 KB Output is correct
7 Correct 232 ms 404140 KB Output is correct
8 Correct 227 ms 404152 KB Output is correct
9 Correct 240 ms 404200 KB Output is correct
10 Correct 241 ms 404188 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 410048 KB Output is correct
2 Correct 490 ms 411508 KB Output is correct
3 Correct 369 ms 408820 KB Output is correct
4 Correct 358 ms 408828 KB Output is correct
5 Correct 513 ms 411204 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 229 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 229 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 230 ms 404204 KB Output is correct
2 Correct 237 ms 404256 KB Output is correct
3 Correct 239 ms 404180 KB Output is correct
4 Correct 241 ms 404172 KB Output is correct
5 Correct 244 ms 404164 KB Output is correct
6 Correct 234 ms 404172 KB Output is correct
7 Correct 232 ms 404264 KB Output is correct
8 Incorrect 226 ms 404216 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 231 ms 404128 KB Output is correct
2 Correct 235 ms 404192 KB Output is correct
3 Correct 233 ms 404300 KB Output is correct
4 Correct 224 ms 404116 KB Output is correct
5 Correct 223 ms 404172 KB Output is correct
6 Correct 222 ms 404212 KB Output is correct
7 Correct 232 ms 404140 KB Output is correct
8 Correct 227 ms 404152 KB Output is correct
9 Correct 240 ms 404200 KB Output is correct
10 Correct 241 ms 404188 KB Output is correct
11 Correct 421 ms 410048 KB Output is correct
12 Correct 490 ms 411508 KB Output is correct
13 Correct 369 ms 408820 KB Output is correct
14 Correct 358 ms 408828 KB Output is correct
15 Correct 513 ms 411204 KB Output is correct
16 Incorrect 229 ms 404172 KB Output isn't correct
17 Halted 0 ms 0 KB -