Codeforces Round # 679 (Div. 2) Review (10/25)
This time's results
Impressions of this time
This time, I was able to maintain my concentration properly during the contest, so I am relieved.
The reason for the victory is that I was able to pass a rather heavy implementation in the C problem. Today I was able to ** believe in my thoughts **, which made debugging easier.
Furthermore, from this time on, I feel that the accuracy has improved by performing print debugging every step. I will try it at the next contest.
Problem A
** It can always hold **, so select ** adjacent numbers ** and $ a \ _i \ times b \ _i + a \ _ {i + 1} \ times b \ _ {i + 1 To set} = 0 $, set $ (b \ _ i, b \ _ {i + 1}) = (-a \ _ {i + 1}, a \ _i) $. At this time, any $ b \ _ {i} $ fills the absolute value range and never becomes 0. Also, since the sequence is even in length, you can pair all adjacent numbers.
A.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n//2):
b[2*i]=-a[2*i+1]
b[2*i+1]=a[2*i]
print(" ".join(map(str,b)))
Problem B
I misread it and reversed the row and column conditions. It was dangerous ...
The first is the information for each row (the order of the rows is not always correct), and the second is the information for each column (the order of the columns is not always correct). Also, all elements of the matrix are given as different.
At this time, the ** column number of each element is uniquely determined from the first **, and the ** row number of each element is uniquely determined from the second **. Therefore, by creating a dictionary in the form of ** (element value): (row number, column number) **, the row number and column number of each element can be found, and the original matrix can be restored from this information. It's fine.
B.py
import sys
input=sys.stdin.readline
for _ in range(int(input())):
n,m=map(int,input().split())
ans=[[0]*m for i in range(n)]
d=dict()
for i in range(n):
l1=list(map(int,input().split()))
for j in range(m):
d[l1[j]]=[-1,j]
for i in range(m):
l2=list(map(int,input().split()))
for j in range(n):
d[l2[j]][0]=j
for i in d:
ans[d[i][0]][d[i][1]]=i
for i in range(n):
print(" ".join(map(str,ans[i])))
C problem
It was a little troublesome for my implementation and consideration, but I am happy to be able to fully consider it. By the way, the Range Minimum Queries that I solved the other day is a similar subject.
Consider finding the minimum value of the difference between the minimum and maximum values of $ j $ when $ b \ _k = a \ _ i + j $ is set with $ i $ set appropriately for any $ k $. I will. In addition, there are up to 6 candidates for $ j $ for each of the $ n $ sounds. Based on this, the minimum value of the difference between the minimum value and the maximum value is considered, but since the degree of freedom is high, the minimum value is fixed ** (** variable fixed! **). At this time, there are a maximum of $ 6n $ candidates for the minimum value, but when the minimum value is fixed at $ x $, the minimum $ j $ above $ x $ is seg tree for each $ b \ _k $. If you save it with such as **, you can see that the maximum value in it can be obtained at high speed without spending $ O (n) $ **. Also, it is necessary to update $ b \ _k $ saved in the seg tree in order to make it over $ x $, but ** the number of updates is about $ 6n $ by considering the amount of depreciation calculation **. You can expect that. Therefore, in the following, we will consider the implementation as well as the solution method.
First, prepare the following variables and then perform the discussion operation.
$ a [i]: = $ (value of the $ i $ th string) $ b [i]: = $ ($ i $ th note value) $ ind [i]: = $ ($ b [i] -a [j] $ value set (ascending order) when the $ i $ th note is played on the $ j $ th string) $ cand: = $ (minimum value: (map saved with index array of sound $ i $ that becomes that value)) $ itr [i]: = $ (** iterator ** of the minimum value of $ ind [i] $ when playing the $ i $ th note) $ maxseg [i]: = $ (value of $ itr [i] $) (** update one point, segment tree of maximum interval value **) $ ans: = $ (solution)
$ a, b $ is just received by input, $ ind $ is $ b [i] -a [j] > 0 $ consists of any $ i, j $, so just insert it by looping twice, $ cand $ just contains an element of $ ind $. Also, $ itr [i] $ should be $ begin () $ of $ ind [i] $ by definition. At this time, $ maxseg [i] $ is also set to the value of the element pointed to by the iterator of $ ind [i] $. Then, $ ans $ is initialized as (maximum value)-(minimum value) of the element pointed to by $ itr $.
From here, consider finding the minimum $ y $ above $ x $ and the minimum value of $ y-x $, with the minimum value being $ x $. ** $ x $ considers everything contained in $ cand $ in ascending order **. First, initialization considers when $ x $ is the minimum of all elements. When increasing the minimum value of $ x $ from here, it is necessary to delete the value smaller than that $ x $. All you have to do is update $ itr, maxseg $ for the element $ x $ contained in $ cand $ as seen from the smaller side. At this time, the index $ i $ included in $ cand [x] $ can be changed to $ itr [i] $ \ + \ +. It also updates the updated $ itr [i] $ value on $ maxseg $. Also, if ** $ itr [i] $ becomes $ end () $, it means that there is no string that can play the $ i $ th note **, and $ ans $ at that point is output and exit. To do. Also, when updating to delete a certain $ x $, the minimum value is the next smallest element after that $ x $, and the maximum value is the maximum value of the value managed by $ maxseg $, and this difference and ans are small. Update ans by yourself.
You can find the solution $ ans $ by exiting the above update.
C.cc
//Debugging options:-fsanitize=undefined,address
//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of endings)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
/* RMQ：[0,n-1]Structure that manages the minimum value for each section
update(i,x):Updated i-th element to x. O(log(n))
query(a,b): [a,b)Get the smallest element in. O(log(n))
*/
template <typename T>
struct RMQ {
const T INF = -1;
int n; //Number of leaves
vector<T> dat; //Full binary tree array
RMQ(int n_) : n(), dat(n_ * 4, INF) { //The number of leaves is 2^shape of x
int x = 1;
while (n_ > x) {
x *= 2;
}
n = x;
}
void update(int i, T x) {
i += n - 1;
dat[i] = x;
while (i > 0) {
i = (i - 1) / 2; // parent
dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);
}
}
// the minimum element of [a,b)
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) {
return INF;
} else if (a <= l && r <= b) {
return dat[k];
} else {
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return max(vl, vr);
}
}
};
signed main(){
//Output specification of decimal digits
//cout<<fixed<<setprecision(10);
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
vector<ll> a(6);REP(i,6)cin>>a[i];
ll n;cin>>n;
RMQ<ll> maxseg(n);
vector<ll> b(n);REP(i,n)cin>>b[i];
vector<set<ll>> ind(n);
REP(i,n){
REP(j,6){
ind[i].insert(b[i]-a[j]);
}
//cout<<SIZE(ind[i])<<endl;
}
map<ll,vector<ll>> cand;
REP(i,n){
FORA(j,ind[i]){
cand[j].PB(i);
}
}
//cout<<1<<endl;
vector<set<ll>::iterator> itr(n);
ll ma=-1;
REP(i,n){
itr[i]=ind[i].begin();
maxseg.update(i,*itr[i]);
ma=max(ma,*itr[i]);
}
ll ans=ma-cand.begin()->F;
for(auto i=cand.begin();i!=cand.end();i++){
FORA(j,i->S){
itr[j]++;
if(itr[j]==ind[j].end()){
cout<<ans<<endl;
return 0;
}
maxseg.update(j,*itr[j]);
}
ans=min(ans,maxseg.query(0,n)-(++i)->F);
i--;
}
cout<<ans<<endl;
}
D problem
I thought it would be better to greedily pack it to meet the conditions, but if it is from the front, it is difficult to set the conditions, so why not think from the back? I thought (** Think in reverse order! **).
When there is a set of numbers that need to be packed in the-position when viewed from behind (a set of +?? Numbers), ** assign to the-position in order from the smallest number ** Is the best. Each **-position is uniquely determined by this method **. Also, NO is output when the position of-cannot be determined (when the size of the set is 0), and NO is output even if even one? Of +? Does not satisfy the subject after determining the position of-. To do. If these judgments are cleared, YES should be output. (I haven't proved it, but I think it's valid enough)
D.cc
//Debugging options:-fsanitize=undefined,address
//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of endings)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
signed main(){
//Output specification of decimal digits
//cout<<fixed<<setprecision(10);
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
vector<ll> que(2*n,0);
REP(i,2*n){
string s;cin>>s;
if(s=="-"){
ll x;cin>>x;
que[i]=x;
}
}
set<ll> cand;
vector<ll> ans(n);
ll ind=n-1;
REPD(i,2*n){
if(que[i]!=0){
cand.insert(que[i]);
}else{
if(SIZE(cand)==0){
cout<<"NO"<<endl;
return 0;
}else{
ll y=*cand.begin();
ans[ind]=y;
ind--;
cand.erase(cand.begin());
}
}
}
ind++;
REP(i,2*n){
if(que[i]==0){
cand.insert(ans[ind]);
ind++;
}else{
ll y=*cand.begin();
if(que[i]!=y){
cout<<"NO"<<endl;
return 0;
}
cand.erase(cand.begin());
}
}
cout<<"YES"<<endl;
REP(i,n){
if(i==n-1)cout<<ans[i]<<endl;
else cout<<ans[i]<<" ";
}
}
E problem
I will skip this time.
Recommended Posts