이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "gondola.h"
//#include "grader.cpp"
#include <map>
#include <set>
#include <vector>
#include <cstring>
#include <assert.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 5;
namespace Valid
{
bool sortedL[MAXN], sortedR[MAXN];
bool check(int n, int a[], int relevant)
{
int maxVal = 0;
for(int i = 0;i<n;i++)
{
maxVal = max(maxVal, a[i]);
sortedL[i] = sortedR[i] = false;
}
set <int> s;
for(int i = 0;i<n;i++)
{
if(s.count(a[i])==true) return false;
s.insert(a[i]);
}
sortedL[0] = true;
int lastRelevant = -1;
for(int i = 1;i<n;i++)
{
if(a[i]>relevant) sortedL[i] = sortedL[i-1];
else sortedL[i] = (sortedL[i-1]&(lastRelevant<a[i])), lastRelevant = a[i];
}
lastRelevant = MAXN;
sortedR[n-1] = true;
for(int i = n-2;i>=0;i--)
{
if(a[i]>relevant) sortedR[i] = sortedR[i+1];
else sortedR[i] = (sortedR[i+1]&(a[i]<lastRelevant)), lastRelevant = a[i];
}
if(sortedL[n-1]==true && (a[n-1]==n || (a[n-1]>relevant && s.count(n)==false))) return true;
for(int i = 0;i<n-1;i++)
{
if(sortedL[i]==true && sortedR[i+1]==true)
{
if(a[i]>relevant || a[i+1]>relevant)
{
if(((a[i]>relevant && s.count(n)==false) || a[i]==n) &&
((a[i+1]>relevant && s.count(1)==false) || a[i+1]==1))
{
return true;
}
}
else
{
if(a[i]==n && a[i+1]==1)
{
return true;
}
}
}
}
return false;
}
};
namespace Replacement
{
bool checkSpecial(int n, int a[])
{
for(int i = 0;i<n;i++)
{
if(a[i]<=n) return false;
}
return true;
}
vector <pair <int, int>> genRaw(int n, int a[])
{
int shift = -1;
for(int i = 0;i<n;i++)
{
if(a[i]<=n)
{
if(a[i]<=i+1) shift = (i + 1) - a[i];
else shift = (n - a[i]) + (i + 1);
break;
}
}
vector <pair <int, int>> out;
for(int i = 0;i<n;i++)
{
if(a[i]>n)
{
out.push_back({a[i], (i-shift+n)%n+1});
}
}
return out;
}
vector <pair <int, int>> genRawSpecial(int n, int a[])
{
vector <pair <int, int>> out;
for(int i = 0;i<n;i++)
{
out.push_back({a[i], i+1});
}
return out;
}
vector <int> solve(int n, int a[])
{
vector <int> answer;
vector <pair <int, int>> raw;
if(checkSpecial(n, a)==false) raw = genRaw(n, a);
else raw = genRawSpecial(n, a);
int num = n + 1;
sort(raw.begin(), raw.end());
for(pair <int, int> x: raw)
{
if(num!=x.first)
{
answer.push_back(x.second);
num++;
while(num<=x.first)
{
answer.push_back(num-1);
num++;
}
}
else
{
answer.push_back(x.second);
num++;
}
}
return answer;
}
};
namespace CountReplacements
{
const long long mod = 1e9 + 9;
struct FenwickTree
{
int n;
int tree[MAXN];
FenwickTree(){}
FenwickTree(int n)
{
this->n = n;
memset(this->tree, 0, sizeof(this->tree));
}
void update(int ind, int val)
{
ind++;
while(ind<=n)
{
tree[ind] += val;
ind += ind&(-ind);
}
}
int query(int ind)
{
ind++;
int sum = 0;
while(ind>0)
{
sum += tree[ind];
ind -= ind&(-ind);
}
return sum;
}
};
long long fastPow(long long x, long long p)
{
long long ans = 1, curr = x;
while(p!=0)
{
if(p%2!=0) ans = (ans*curr)%mod;
p/=2;
curr = (curr*curr)%mod;
}
return ans;
}
long long inv(long long x)
{
return fastPow(x, mod-2);
}
map <int, int> code;
void compress(vector <pair <int, int>> &raw)
{
set <int> s;
for(pair <int, int> x: raw) s.insert(x.second);
int ind = 0;
for(int x: s) code[x] = ind, ind++;
}
long long solve(vector <pair <int, int>> &raw, int n)
{
FenwickTree T(MAXN-5);
compress(raw);
int num = n + 1;
long long answer = 1;
for(pair <int, int> x: raw)
T.update(code[x.second], +1);
for(pair <int, int> x: raw)
{
while(num<x.first)
{
auto it = code.lower_bound(num);
it--;
int cnt = T.query(it->second);
answer = (answer*cnt)%mod;
num++;
}
if(num==x.first)
{
T.update(code[x.second], -1);
num++;
continue;
}
}
return answer;
}
};
int valid(int n, int inputSeq[])
{
return Valid::check(n, inputSeq, n);
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector <int> v = Replacement::solve(n, gondolaSeq);
for(int i = 0;i<v.size();i++) replacementSeq[i] = v[i];
return v.size();
}
int countReplacement(int n, int inputSeq[])
{
if(Valid::check(n, inputSeq, n)==false) return 0;
vector <pair <int, int>> raw;
if(Replacement::checkSpecial(n, inputSeq)==false) raw = Replacement::genRaw(n, inputSeq);
else raw = Replacement::genRawSpecial(n, inputSeq);
sort(raw.begin(), raw.end());
long long answer = CountReplacements::solve(raw, n);
if(Replacement::checkSpecial(n, inputSeq)==true) answer = (answer*n)%CountReplacements::mod;
return answer;
}
컴파일 시 표준 에러 (stderr) 메시지
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:282:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
282 | for(int i = 0;i<v.size();i++) replacementSeq[i] = v[i];
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |