oj.uz

Submission #752196

# Submission time Handle Problem Language Result Execution time Memory
752196 2023-06-02T13:14:02 Z Sam_a17 Ancient Machine (JOI21_ancient_machine) C++17
30 / 100
 118 ms 14596 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 random generations
// mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
// // mt19937 myrand(131);

// // 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);
//   } else {
//     // freopen("input.txt", "r", stdin);
//     // freopen("output.txt", "w", stdout);
//   }
// }
 
// // Indexed Set
// template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void Send(int a);

void Anna(int N, std::vector<char> S) {
  for(int i = 0; i < N; i++) {
    if(S[i] == 'X') {
      Send(0);
      Send(1);
    } else if(S[i] == 'Y') {
      Send(1);
      Send(0);
    } else {
      Send(1);
      Send(1);
    }
  }
}

#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 blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
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(long double t) {cerr << t;}
void print(unsigned long long 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, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } 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 << "]";}
template <class T, class V> void print(unordered_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>;

void Remove(int d);

void Bruno(int N, int L, std::vector<int> A) {
  vector<int> a;
  for(int i = 1; i < L; i += 2) {
    if(A[i - 1] == 1 && A[i] == 1) {
      a.push_back(2);
    } else if(A[i - 1] == 1) {
      a.push_back(1);
    } else {
      a.push_back(0);
    }
  }

  set<int> st[3];
  vector<bool> have(N);

  auto dll = [&](int l, int r)-> void {
    for(int i = 0; i < 3; i++) {
      auto it = st[i].lower_bound(l);
      vector<int> to_del;
      while(it != st[i].end() && *it < r) {
        to_del.push_back(*it);
        it = next(it);
      }

      for(auto j: to_del) {
        have[j] = true;
        Remove(j);
        st[i].erase(j);
      }
    }
  };

  int cnt = 0;
  for (int i = 0; i < N; i++) {
    int ok = 0;
    if(a[i] == 2) {
      while(!st[1].empty() && !st[0].empty()) {
        auto itr = *st[1].rbegin();
        auto itl = *st[0].begin();

        if(itl < itr) {
          dll(itr + 1, i);
          itl = *st[0].rbegin();
          dll(itl + 1, itr);

          //
          st[1].erase(itr);
          Remove(itr);
          have[itr] = true;
          cnt++;
          ok = 1;
        } else {
          break;
        }
      }
    }

    st[a[i]].insert(i);
  }

  for(int i = 0; i < 3; i++) {
    for(auto j: st[i]) {
      Remove(j);
    }
  }
}

Compilation message

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:109:9: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  109 |     int ok = 0;
      |         ^~
Bruno.cpp: In function 'void setIO(std::string)':
Bruno.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 + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Bruno.cpp:67:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 516 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 1 ms 508 KB Output is correct
4 Correct 0 ms 516 KB Output is correct
5 Correct 0 ms 508 KB Output is correct
6 Correct 0 ms 508 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 1 ms 508 KB Output is correct
9 Correct 0 ms 516 KB Output is correct
10 Correct 1 ms 508 KB Output is correct
11 Correct 1 ms 508 KB Output is correct

Subtask #2
25.0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 108 ms 11012 KB Partially correct
2 Partially correct 95 ms 11108 KB Partially correct
3 Partially correct 107 ms 11244 KB Partially correct
4 Partially correct 97 ms 11484 KB Partially correct
5 Partially correct 99 ms 11304 KB Partially correct
6 Partially correct 96 ms 11428 KB Partially correct
7 Partially correct 107 ms 11492 KB Partially correct
8 Partially correct 96 ms 11484 KB Partially correct
9 Partially correct 100 ms 11508 KB Partially correct
10 Partially correct 92 ms 11436 KB Partially correct
11 Partially correct 96 ms 11508 KB Partially correct
12 Partially correct 104 ms 11384 KB Partially correct
13 Partially correct 118 ms 10324 KB Partially correct
14 Partially correct 87 ms 9872 KB Partially correct
15 Partially correct 99 ms 12968 KB Partially correct
16 Partially correct 78 ms 9740 KB Partially correct
17 Partially correct 105 ms 14596 KB Partially correct
18 Partially correct 104 ms 14524 KB Partially correct
19 Partially correct 97 ms 14584 KB Partially correct
20 Partially correct 79 ms 9840 KB Partially correct
21 Partially correct 78 ms 9956 KB Partially correct
22 Partially correct 99 ms 10704 KB Partially correct
23 Partially correct 96 ms 10732 KB Partially correct
24 Partially correct 89 ms 10676 KB Partially correct
25 Partially correct 103 ms 14564 KB Partially correct
26 Partially correct 107 ms 14492 KB Partially correct
27 Partially correct 99 ms 14572 KB Partially correct
28 Partially correct 99 ms 14544 KB Partially correct
29 Partially correct 102 ms 14448 KB Partially correct
30 Partially correct 110 ms 14540 KB Partially correct
31 Partially correct 100 ms 14480 KB Partially correct
32 Partially correct 96 ms 10732 KB Partially correct
33 Partially correct 102 ms 10604 KB Partially correct