Submission #11225279
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[202020]; int R[202020]; int RC[202020]; map<int,int> num; vector<int> P[202020]; void hoge(vector<pair<int,int>> V) { ZERO(RC); int i; FOR(i,M+1) P[i].clear(); 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 | 0 |
Code Size | 1903 Byte |
Status | RE |
Exec Time | 161 ms |
Memory | 9588 KB |
Judge Result
Set Name | Subtask01 | Subtask02 | Subtask03 | Subtask04 | Subtask05 | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 15 | 0 / 30 | 0 / 10 | 0 / 25 | 0 / 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 | 3 ms | 6400 KB |
01-02.txt | AC | 3 ms | 6400 KB |
01-03.txt | AC | 3 ms | 6400 KB |
01-04.txt | AC | 3 ms | 6400 KB |
01-05.txt | AC | 3 ms | 6400 KB |
01-06.txt | AC | 3 ms | 6400 KB |
01-07.txt | AC | 3 ms | 6400 KB |
01-08.txt | AC | 3 ms | 6400 KB |
01-09.txt | AC | 3 ms | 6400 KB |
01-10.txt | AC | 3 ms | 6400 KB |
01-11.txt | WA | 3 ms | 6400 KB |
01-12.txt | WA | 3 ms | 6400 KB |
01-13.txt | AC | 3 ms | 6400 KB |
01-14.txt | AC | 3 ms | 6400 KB |
01-15.txt | AC | 3 ms | 6400 KB |
01-16.txt | AC | 3 ms | 6400 KB |
01-17.txt | WA | 3 ms | 6400 KB |
01-18.txt | AC | 3 ms | 6400 KB |
01-19.txt | AC | 3 ms | 6400 KB |
01-20.txt | AC | 3 ms | 6400 KB |
01-21.txt | AC | 3 ms | 6400 KB |
01-22.txt | AC | 3 ms | 6400 KB |
01-23.txt | AC | 3 ms | 6400 KB |
01-24.txt | AC | 3 ms | 6400 KB |
01-25.txt | AC | 3 ms | 6400 KB |
01-26.txt | AC | 3 ms | 6400 KB |
02-01.txt | AC | 50 ms | 8568 KB |
02-02.txt | AC | 49 ms | 8696 KB |
02-03.txt | AC | 52 ms | 8568 KB |
02-04.txt | AC | 49 ms | 8696 KB |
02-05.txt | AC | 52 ms | 8568 KB |
02-06.txt | AC | 48 ms | 8696 KB |
02-07.txt | AC | 51 ms | 8568 KB |
02-08.txt | AC | 49 ms | 8696 KB |
03-01.txt | AC | 32 ms | 8568 KB |
03-02.txt | AC | 32 ms | 8568 KB |
03-03.txt | AC | 32 ms | 8560 KB |
03-04.txt | AC | 33 ms | 8568 KB |
03-05.txt | AC | 32 ms | 8568 KB |
03-06.txt | AC | 24 ms | 8568 KB |
03-07.txt | AC | 25 ms | 8568 KB |
03-08.txt | AC | 23 ms | 8568 KB |
03-09.txt | AC | 25 ms | 8568 KB |
03-10.txt | AC | 25 ms | 8568 KB |
03-11.txt | AC | 25 ms | 8568 KB |
03-12.txt | AC | 23 ms | 8568 KB |
03-13.txt | AC | 24 ms | 8568 KB |
04-01.txt | WA | 23 ms | 7424 KB |
04-02.txt | WA | 22 ms | 7424 KB |
04-03.txt | WA | 22 ms | 7424 KB |
04-04.txt | WA | 20 ms | 7424 KB |
04-05.txt | WA | 19 ms | 7424 KB |
04-06.txt | WA | 21 ms | 7424 KB |
04-07.txt | WA | 19 ms | 7424 KB |
04-08.txt | WA | 19 ms | 7424 KB |
04-09.txt | WA | 19 ms | 7424 KB |
05-01.txt | RE | 118 ms | 8952 KB |
05-02.txt | RE | 116 ms | 7424 KB |
05-03.txt | RE | 122 ms | 7932 KB |
05-04.txt | RE | 117 ms | 7424 KB |
05-05.txt | RE | 120 ms | 9588 KB |
05-06.txt | RE | 117 ms | 7424 KB |
05-07.txt | RE | 116 ms | 7424 KB |
05-08.txt | RE | 118 ms | 7424 KB |
05-09.txt | WA | 161 ms | 8668 KB |
sample-01.txt | AC | 4 ms | 6400 KB |
sample-02.txt | AC | 3 ms | 6400 KB |
sample-03.txt | AC | 3 ms | 6400 KB |