Submission #11225312
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- int N,M; int C[1202020]; int R[1202020]; int RC[1202020]; map<int,int> num; vector<int> P[1202020]; void hoge(vector<pair<int,int>> V) { ZERO(RC); int i; FOR(i,M+1) P[i].clear(); RC[M]=-2; FORR(v,V) { RC[v.first]++; RC[v.second]++; P[v.first].push_back(v.second); P[v.second].push_back(v.first); } num.clear(); num[0]=10101010; FOR(i,M+1) num[RC[i]]++; FOR(i,M) { int dif=0; int difsum=N-RC[i]; num[RC[i]]--; FORR(p,P[i]) { if(p!=i) { difsum--; num[RC[p]]--; RC[p]--; num[RC[p]]++; dif++; } } while(num.rbegin()->second==0) num.erase(num.rbegin()->first); dif+=difsum-num.rbegin()->first; R[i]=min(R[i],dif); num[RC[i]]++; FORR(p,P[i]) { if(p!=i) { num[RC[p]]--; RC[p]++; num[RC[p]]++; } } } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; if(M==1) return _P("0\n"); C[0]=M; FOR(i,N) { cin>>C[i+1]; C[i+1]--; R[i]=1<<20; } C[N+1]=M; vector<pair<int,int>> V[2]; for(i=1;i<=N;i+=2) V[0].push_back({C[i],C[i+1]}); for(i=0;i<=N;i+=2) V[1].push_back({C[i],C[i+1]}); hoge(V[0]); hoge(V[1]); FOR(i,M) cout<<R[i]<<endl; } int main(int argc,char** argv){ string s;int i; if(argc==1) ios::sync_with_stdio(false), cin.tie(0); FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin); cout.tie(0); solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 縄 (Rope) |
User | kmjp |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1919 Byte |
Status | AC |
Exec Time | 2127 ms |
Memory | 91560 KB |
Judge Result
Set Name | Subtask01 | Subtask02 | Subtask03 | Subtask04 | Subtask05 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 15 / 15 | 30 / 30 | 10 / 10 | 25 / 25 | 20 / 20 | ||||||||||
Status |
|
|
|
|
|
Set Name | Test Cases |
---|---|
Subtask01 | 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Subtask02 | 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Subtask03 | 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Subtask04 | 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 04-01.txt, 04-02.txt, 04-03.txt, 04-04.txt, 04-05.txt, 04-06.txt, 04-07.txt, 04-08.txt, 04-09.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Subtask05 | 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 04-01.txt, 04-02.txt, 04-03.txt, 04-04.txt, 04-05.txt, 04-06.txt, 04-07.txt, 04-08.txt, 04-09.txt, 05-01.txt, 05-02.txt, 05-03.txt, 05-04.txt, 05-05.txt, 05-06.txt, 05-07.txt, 05-08.txt, 05-09.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 13 ms | 37120 KB |
01-02.txt | AC | 13 ms | 37120 KB |
01-03.txt | AC | 12 ms | 37120 KB |
01-04.txt | AC | 13 ms | 37120 KB |
01-05.txt | AC | 13 ms | 37120 KB |
01-06.txt | AC | 13 ms | 37120 KB |
01-07.txt | AC | 13 ms | 37120 KB |
01-08.txt | AC | 12 ms | 37120 KB |
01-09.txt | AC | 13 ms | 37120 KB |
01-10.txt | AC | 12 ms | 37120 KB |
01-11.txt | AC | 13 ms | 37120 KB |
01-12.txt | AC | 13 ms | 37120 KB |
01-13.txt | AC | 12 ms | 37120 KB |
01-14.txt | AC | 13 ms | 37120 KB |
01-15.txt | AC | 13 ms | 37120 KB |
01-16.txt | AC | 13 ms | 37120 KB |
01-17.txt | AC | 13 ms | 37120 KB |
01-18.txt | AC | 13 ms | 37120 KB |
01-19.txt | AC | 12 ms | 37120 KB |
01-20.txt | AC | 13 ms | 37120 KB |
01-21.txt | AC | 12 ms | 37120 KB |
01-22.txt | AC | 10 ms | 28928 KB |
01-23.txt | AC | 12 ms | 37120 KB |
01-24.txt | AC | 12 ms | 37120 KB |
01-25.txt | AC | 13 ms | 37120 KB |
01-26.txt | AC | 10 ms | 28928 KB |
02-01.txt | AC | 56 ms | 38904 KB |
02-02.txt | AC | 55 ms | 39032 KB |
02-03.txt | AC | 58 ms | 38904 KB |
02-04.txt | AC | 55 ms | 39032 KB |
02-05.txt | AC | 58 ms | 38904 KB |
02-06.txt | AC | 54 ms | 39032 KB |
02-07.txt | AC | 57 ms | 38904 KB |
02-08.txt | AC | 55 ms | 39032 KB |
03-01.txt | AC | 39 ms | 38904 KB |
03-02.txt | AC | 40 ms | 38904 KB |
03-03.txt | AC | 39 ms | 38776 KB |
03-04.txt | AC | 39 ms | 38896 KB |
03-05.txt | AC | 39 ms | 38896 KB |
03-06.txt | AC | 32 ms | 38904 KB |
03-07.txt | AC | 32 ms | 38904 KB |
03-08.txt | AC | 30 ms | 38904 KB |
03-09.txt | AC | 32 ms | 38904 KB |
03-10.txt | AC | 32 ms | 38904 KB |
03-11.txt | AC | 32 ms | 38904 KB |
03-12.txt | AC | 31 ms | 38904 KB |
03-13.txt | AC | 32 ms | 38904 KB |
04-01.txt | AC | 316 ms | 60072 KB |
04-02.txt | AC | 314 ms | 60396 KB |
04-03.txt | AC | 316 ms | 60072 KB |
04-04.txt | AC | 328 ms | 60072 KB |
04-05.txt | AC | 336 ms | 59116 KB |
04-06.txt | AC | 217 ms | 59304 KB |
04-07.txt | AC | 191 ms | 58280 KB |
04-08.txt | AC | 189 ms | 58152 KB |
04-09.txt | AC | 176 ms | 57836 KB |
05-01.txt | AC | 2127 ms | 91560 KB |
05-02.txt | AC | 1382 ms | 76328 KB |
05-03.txt | AC | 1391 ms | 76328 KB |
05-04.txt | AC | 1552 ms | 80084 KB |
05-05.txt | AC | 1565 ms | 80168 KB |
05-06.txt | AC | 729 ms | 68008 KB |
05-07.txt | AC | 1016 ms | 71976 KB |
05-08.txt | AC | 852 ms | 69544 KB |
05-09.txt | AC | 456 ms | 63016 KB |
sample-01.txt | AC | 14 ms | 37120 KB |
sample-02.txt | AC | 13 ms | 37120 KB |
sample-03.txt | AC | 13 ms | 37120 KB |