Submission #1258842

#TimeUsernameProblemLanguageResultExecution timeMemory
1258842hamanp87JOIRIS (JOI16_joiris)C++20
100 / 100
1 ms328 KiB
#include<bits/stdc++.h> using namespace std; using ll=long long; //#pragma GCC optimize("03,unroll-loops") //#pragma GCC target("avx2") //#pragma GCC target("sse4") #define all(v) v.begin(),v.end() #define F first #define S second #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front //#define randi uniform_int_distribution<long long> #define damoon(v) v.resize(unique(all(v))-v.begin()) //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //randi dist(0,10000000000000000); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<int,bool> pib; typedef pair<long long,bool> plb; typedef pair<int,pii> pip; typedef pair<pii,int> ppi; typedef vector<int> veci; typedef vector<long long> vecl; typedef vector<bool> vecb; typedef vector<pii> vecp; typedef set<int> seti; typedef set<long long> setl; typedef set<pii> setp; typedef map<int,int> mapii; typedef map<long long,long long> mapll; typedef map<int,bool> mapib; typedef map<long long,bool> maplb; const int inf=1e9,mod=1e9+7,neginf=-1e9; const double PI=acos(-1); int n,k; veci a; vecp ans; void AV(int i) { a[i]+=k; ans.emplace_back(1,i); } void AH(int i) { for(int j=i;j<=i+k-1;j++) a[j]+=1; ans.emplace_back(2,i); } void update(int i) { int mx=*max_element(a.begin()+i,a.begin()+i+k)+k; for(int j=1;j<i;j++) while(a[j]<mx) AV(j); for(int j=i+k;j<=n;j++) while(a[j]<mx) AV(j); AH(i); } void solve() { cin>>n>>k; a.assign(n+2,0); for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n-k+1;i++) while(abs(a[i]-a[1])%k!=0) update(i); for(int i=n-k+1;i>0;i--) while(abs(a[i+k-1]-a[n])%k!=0) update(i); int mx=*max_element(a.begin()+1,a.begin()+n+1); for(int i=1;i<=n;i++) while(a[i]<mx) AV(i); for(int i=1;i<=n;i++) { if(a[i]!=mx) { cout<<"-1\n"; return; } } cout<<ans.size()<<"\n"; for(auto p:ans) cout<<p.F<<' '<<p.S<<"\n"; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); //ifstream fin("in.txt"); //ofstream fout("out.txt"); int t=1; //cin>>t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...