oj.uz

Submission #754659

# Submission time Handle Problem Language Result Execution time Memory
754659 2023-06-08T08:35:41 Z Sam_a17 Gondola (IOI14_gondola) C++17
75 / 100
 39 ms 12708 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
// #include <rail.h>
#include "gondola.h"
#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};
 
long long ka() {
	long long x = 0;
	bool z = false;
	while (1)
	{
		char y = getchar();
		if (y == '-')
			z = true;
		else if ('0' <= y && y <= '9')
			x = x * 10 + y - '0';
		else
		{
			if (z)
				x *= -1;
			return x;
		}
	}
}
 
// 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 if(str == "input") {
    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>;
const long long mod = 1000000009;
const int N = 2e6 + 10;
int cnt[N], cnt2[N];

int valid(int n, int inputSeq[]) {
  
  for(int i = 0; i < n; i++) {
    cnt[inputSeq[i]]++;
    if(cnt[inputSeq[i]] > 1) {
      return 0;
    }
  }

  for(int i = 0; i < n; i++) {
    if(inputSeq[i] <= n) {
      int lef = inputSeq[i] - 1;
      if(lef == 0) lef = n;

      int li = (i - 1 + n) % n;
      if(inputSeq[li] <= n && inputSeq[li] != lef) {
        return 0;
      }


      int rig = inputSeq[i] + 1;
      if(rig > n) {
        rig = 1;
      }
      int ri = (i + 1) % n;
      
      if(inputSeq[ri] <= n && inputSeq[ri] != rig) {
        return 0;
      }
    }
  }

  return 1;
}


int valid2(int n, vector<int> inputSeq) {
  memset(cnt, 0, sizeof(cnt));
  for(int i = 0; i < n; i++) {
    cnt[inputSeq[i]]++;
    if(cnt[inputSeq[i]] > 1) {
      return 0;
    }
  }

  for(int i = 0; i < n; i++) {
    if(inputSeq[i] <= n) {
      int lef = inputSeq[i] - 1;
      if(lef == 0) lef = n;

      int li = (i - 1 + n) % n;
      if(inputSeq[li] <= n && inputSeq[li] != lef) {
        return 0;
      }


      int rig = inputSeq[i] + 1;
      if(rig > n) {
        rig = 1;
      }
      int ri = (i + 1) % n;
      
      if(inputSeq[ri] <= n && inputSeq[ri] != rig) {
        return 0;
      }
    }
  }

  return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
  set<pair<int, int>> st;
  int mx = 0;
  int ok = 0;

  vector<int> which(n);
  for(int i = 0; i < n; i++) {
    if(gondolaSeq[i] > n) {
      mx = max(mx, gondolaSeq[i]);
      st.insert({gondolaSeq[i], i});
    } else if(!ok) {
      int j = i, it = gondolaSeq[i];
      for(int k = 0; k < n; k++) {
        which[j] = it;

        it++;
        if(it == n + 1) {
          it = 1;
        }

        j++;
        j %= n;
      }

      ok = 1;
    }
  }

  if(!ok) {
    for(int i = 0; i < n; i++) {
      which[i] = (i + 1);
    }
  }

  int bit = 0;
  for(int i = n + 1; i <= mx; i++) {
    if(st.begin()->first == i) {
      replacementSeq[bit] = which[st.begin()->second];
      st.erase(st.begin());
    } else {
      auto it = st.rbegin()->second;
      replacementSeq[bit] = which[it];
      which[it] = i;
    }  

    bit++;
  }

  assert(sz(st) == 0);

  return bit;
}

long long add(long long a, long long b) {
  return (a + b) % mod;
}

long long mult(long long a, long long b) {
  return (a * b) % mod;
}

long long sub(long long a, long long b) {
  return (a - b + 2 * mod) % mod;
}

int countReplacement(int n, int inputSeq[]) {
  vector<int> veci;
  for(int i = 0; i < n; i++) {
    veci.push_back(inputSeq[i]);
  }

  if(!valid2(n, veci)) {
    return 0;
  }

  set<pair<long long, long long>> st;
  long long mx = 0;

  for(int i = 0; i < n; i++) {
    if(inputSeq[i] > n) {
      mx = max(mx, (long long)inputSeq[i]);
      st.insert({inputSeq[i], i});
    }
  }

  long long ct = sz(st);
  long long answ = 1;
  for(int i = n + 1; i <= mx; i++) {
    if(st.begin()->first == i) {
      ct--;
      st.erase(st.begin());
    } else {
      answ = mult(answ, ct);
    }
  }

  assert(answ >= 0);
  return answ;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 8 ms 724 KB Output is correct
7 Correct 9 ms 1492 KB Output is correct
8 Correct 8 ms 1236 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 9 ms 1356 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 8 ms 1468 KB Output is correct
8 Correct 10 ms 1280 KB Output is correct
9 Correct 3 ms 520 KB Output is correct
10 Correct 13 ms 1364 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 5 ms 1484 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 9 ms 1612 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 280 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 268 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 8 ms 1364 KB Output is correct
12 Correct 9 ms 1484 KB Output is correct
13 Correct 21 ms 2756 KB Output is correct
14 Correct 8 ms 1300 KB Output is correct
15 Correct 24 ms 3028 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8164 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 3 ms 8128 KB Output is correct
4 Correct 3 ms 8148 KB Output is correct
5 Correct 4 ms 8132 KB Output is correct
6 Correct 4 ms 8128 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 3 ms 8148 KB Output is correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8136 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8128 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 3 ms 8148 KB Output is correct
9 Correct 39 ms 12664 KB Output is correct
10 Correct 22 ms 11640 KB Output is correct
11 Correct 12 ms 9860 KB Output is correct
12 Correct 17 ms 10192 KB Output is correct
13 Incorrect 7 ms 8660 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8136 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 3 ms 8148 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 30 ms 12708 KB Output is correct
10 Correct 22 ms 11648 KB Output is correct
11 Correct 12 ms 9832 KB Output is correct
12 Correct 14 ms 10196 KB Output is correct
13 Incorrect 7 ms 8672 KB Output isn't correct
14 Halted 0 ms 0 KB -