QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#500744#5466. Permutation CompressionSakib_SafwanWA 0ms3836kbC++203.5kb2024-08-01 19:27:032024-08-01 19:27:03

Judging History

你现在查看的是最新测评结果

  • [2024-08-01 19:27:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3836kb
  • [2024-08-01 19:27:03]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;


typedef long long ll;
typedef long double ld;

#define endl "\n"
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
// #define int long long



// Don't Start typing till you complete the idea.


// Check these things for WA and before submitting
// 1. Did you clear all the global arrays
// 2. Did you checked your <= >= < > 
// 3. Did you take the input properly. Did you use break or return while taking input?
// 4. Did you divide by 0.
// 5. Check array , vector , etc size
// 6. in the while loop did you miss something that would cause infinite loop?
// 7. Did you save your dp?
// 8. Are you trying to use something after deleting it?
// 9. Did you read the problem statement wrong?
// 10. Did you check the constrains of the problem properly
// 11. Did you checked for smaller cases like 1 , 0 , etc
// 12. Is it something to with overflow?
// 13. Did you initialized all the variables properly?
// 14. Did you use the formulas correctly?

// STRESS TESTING !!!!!! STRESS TESTING !!!!!
// STRESS Testing Not working?
// Stress test for multiple cases? 
// Stress test for big inputs?
// Stress test for really small inputs?
// Even then if it doesn't work -> Did you wrote the wrong Brute force code


// Check these things if you are not generating ideas
// 1. Did you try thinking it in reverse?
// 2. Read the problem statement again
// 3. Check the constraints again
// 4. Try smaller cases in notebook and try to expand
// 5. Think about invariants
// 6. Think simpler ideas maybe?
// 7. Think brute force and try to get something out of it.
// 8. Maybe take a deep breath and take a break for few minutes and drink some water? :3 

template <class T>
struct BIT { //1-indexed
  int n; vector<T> t;
  BIT() {}
  BIT(int _n) {
    n = _n; t.assign(n + 1, 0);
  }
  T query(int i) {
    T ans = 0;
    for (; i >= 1; i -= (i & -i)) ans += t[i];
    return ans;
  }
  void upd(int i, T val) {
    if (i <= 0) return;
    for (; i <= n; i += (i & -i)) t[i] += val;
  }
  void upd(int l, int r, T val) {
    upd(l, val);
    upd(r + 1, -val);
  }
  T query(int l, int r) {
    return query(r) - query(l - 1);
  }
};

void GG()
{
	int n , m , k;
  cin >> n >> m >> k;
  vector<int> v(n);
  multiset<int> ase;
  vector<int> bad(n + 1);
  vector<int> ind(n + 1);
  set<int> boro;
  for(int i = 0; i < n; i++) {
    cin >> v[i];
    ind[v[i]] = i + 1;
  }
  for(int i = 0; i < m; i++){
    int x;
    cin >> x; 
    bad[x]++;
  }
  for(int i = 0; i < k; i++){
    int x;
    cin >> x;
    ase.insert(x);
  }
  BIT<int> bit(n);
  for(int i = n; i >= 1; i--){
    if(!bad[i]){
      int r = n;
      int l = 1;
      auto itr = boro.lower_bound(ind[i]);
      if(itr != boro.end()) r = *itr - 1;
      if(itr != boro.begin()){
        --itr;
        l = *itr + 1;
      }
      int gese = bit.query(l , r);
      int lagbe = r - l + 1 - gese;
      auto xtr = ase.upper_bound(lagbe);
      // cout << i << ' ' << l << ' ' << r << ' ' << lagbe << ' ' << gese << endl;
      if(xtr == ase.begin()){
        cout << "NO" << endl;
        return;
      }
      xtr--;
      ase.erase(xtr);
      bit.upd(ind[i] , 1);
    }
    else boro.insert(ind[i]);
  }
  cout << "YES" << endl;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int ttc=1;
	cin>>ttc;
	//int cnt=0;
	while(ttc--)
	{
		//cout<<"Case "<<++cnt<<": ";
		GG();
	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3784kb

input:

3
5 2 3
5 1 3 2 4
5 2
1 2 4
5 5 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
3 2 2
3 1 2
3 2
2 3

output:

YES
YES
NO

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3836kb

input:

100
2 1 2
2 1
2
1 1
2 1 2
1 2
1
2 2
2 1 1
1 2
1
2
6 1 5
3 4 2 5 6 1
3
5 2 1 1 1
6 1 6
2 1 3 6 4 5
1
4 1 2 2 1 4
3 3 2
2 1 3
2 1 3
2 2
1 1 1
1
1
1
1 1 1
1
1
1
2 1 2
2 1
2
1 2
4 4 3
2 1 3 4
2 1 3 4
4 3 1
1 1 1
1
1
1
6 5 1
6 2 5 4 3 1
6 2 4 3 1
4
1 1 1
1
1
1
6 5 3
3 6 1 4 5 2
3 6 1 4 2
3 3 4
4 3 4
3 4 ...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
Y...

result:

wrong answer 45th lines differ - expected: 'NO', found: 'YES'